Wang Hao at 08:35, 12 August 2016

2016-08-12T08:35:23Z

New page

{{Cat|Drools|070}}

<slideshow style="nobleprog" headingmark="⌘" incmark="…" scaled="true" font="Trebuchet MS" lang="中文版" headingmark2="。" >
;title: Drools - Rete
;author: Bernard Szlachta (NobleProg Ltd)
</slideshow>

== Drools -Rete ==
{{Can I use your material}}

== Rete ⌘==
* Created by Dr. Charles Forgy in 1978
* In Latin Rete means "network"
* Made of two parts:
** Compilation
** Runtime Execution

== Rete 。==
* 创始人Dr. Charles Forgy 1978
* 拉丁语 Rete 的意思是网络（"network"）
* 两部分组成:
** 编译（Compilation）
** Runtime执行

== Compilation Algorithm ⌘==
* Describes how the Rules in the Production Memory are processed
* The output is an efficient discrimination network
* Nodes at the top have many matches
* At the bottom there are rules which are going to be fired

[[File:Rete Nodes.png]]

== 编译算法。==
* 描述如何处理生产内存中的规则
* 输出是一个高效鉴别网络
* 在顶端的node有很多的匹配
* 在底端的规则准备启动（firing）

[[File:Rete Nodes.png]]

== Rete Nodes ⌘==
== Rete Nodes 。==

=== ObjectTypeNode ⌘===
* always present, though may be implicit e.g.
CourseEvent(booked == true)
contains two conditions:
** first: "There is a CourseEvent, in mvel
CourseEvent()
** second: there is a booking (booked == true)

http://docs.jboss.org/drools/release/5.3.0.Final/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Object_Type_Nodes.png

ObjectTypeNodes can propagate:
* AlphaNodes
* LeftInputAdapterNodes
* BetaNodes

=== ObjectTypeNode 。===
* 一直在线, 虽然可能看不见。比如
CourseEvent(booked == true)
包含两个条件:
** 一: "有一个 CourseEvent, in mvel
CourseEvent()
** 二: 有一个 booking (booked == true)

http://docs.jboss.org/drools/release/5.3.0.Final/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Object_Type_Nodes.png

ObjectTypeNodes 可传播:
* AlphaNodes
* LeftInputAdapterNodes
* BetaNodes

=== AlphaNodes ⌘===
* evaluate literal conditions e.g.
** booked == ture
* multiple literal conditions for a single object type are linked together (i.e. object must first satisfy the first literal condition before it can proceed to the next AlphaNode) - AKA IntraElement conditions

http://docs.jboss.org/drools/release/5.3.0.Final/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Alpha_Nodes.png

Drools extends Rete by optimizing the propagation from ObjectTypeNode to AlphaNode using hashing. Each time an AlphaNode is added to an ObjectTypeNode it adds the literal value as a key to the HashMap with the AlphaNode as the value. When a new instance enters the ObjectType node, rather than propagating to each AlphaNode, it can instead retrieve the correct AlphaNode from the HashMap,thereby avoiding unnecessary literal checks.

=== AlphaNodes 。===
* 对文本条件进行运算，比如
** booked == ture
* 单独object type的多个文本条件连接在一起 (比如 object 必须首先满足第一个文本条件，然后才能处理下一个AlphaNode) - 也叫做 IntraElement 条件

http://docs.jboss.org/drools/release/5.3.0.Final/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Alpha_Nodes.png

Drools 扩展了 Rete 通过使用hashing优化从ObjectTypeNode到AlphaNode的传递。每次一个AlphaNode被加入到一个ObjectTypeNode，他将文本值作为一个键值（key）添加到HashMap中，对应的值即相应的AlphaNode。当一个新的实例进入ObjectTypeNode, 与其传递到每个AlphaNode, 它可以从HashMap里取得正确的AlphaNode, 这样可以避免不必要的文本检查。

== Beta Nodes ⌘==
* BetaNodes compare 2 objects and their fields
* Two inputs are referred as left and right
** Left input for a BetaNode is a list of objects (Tuple)
** Right input is a single object
* used to implement 'exists' checks (see _60ToBeOrNotToBe.drl)

* BetaNodes have memory
** The left input is called the Beta Memory and remembers all incoming tuples
** The right input is called the Alpha Memory and remembers all incoming objects

* Drools extends Rete by performing indexing on the BetaNodes

http://docs.jboss.org/drools/release/5.4.0.CR1/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Join_Node.png

== Beta Nodes 。==
* BetaNodes 比较两个objects和它们的fields
* 两个输入用左和右（left and right）代表
** 左输入（Left input）是一个objects列表（Tuple）
** 右输入是一个单独 object
* 用来做“存在”检验 (见 _60ToBeOrNotToBe.drl)

* BetaNodes 有记忆
** 左输入叫做Beta记忆，能记住所有输入的tuples
** 右输入叫做Alpha记忆，能记住所有的输入objects

* Drools 通过在BetaNodes做索引扩展了 Rete

http://docs.jboss.org/drools/release/5.4.0.CR1/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Join_Node.png

== Join Node ⌘==
* To enable the ''Cheese'' object to enter the network we use a LeftInputNodeAdapter
* LeftInputNodeAdapter this takes an Object as an input and propagates a single Object Tuple
* Terminal nodes are used to indicate a single rule having matched all its conditions (full match)
* A rule with an 'or' conditional disjunctive connective splits in subrule for each possible logically branch (one rule can have multiple terminal nodes)

* Drools also performs node sharing. Many rules repeat the same patterns, and node sharing allows us to collapse those patterns so that they don't have to be re-evaluated for every single instance.

http://docs.jboss.org/drools/release/5.4.0.CR1/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Node_Sharing.png

== Join Node 。==
* To enable the ''Cheese'' object to enter the network we use a LeftInputNodeAdapter
* LeftInputNodeAdapter this takes an Object as an input and propagates a single Object Tuple
* Terminal nodes用于表示一条规则成功匹配了所有的条件（全匹配）
* A rule with an 'or' conditional disjunctive connective splits in subrule for each possible logically branch (one rule can have multiple terminal nodes)

* Drools also performs node sharing. Many rules repeat the same patterns, and node sharing allows us to collapse those patterns so that they don't have to be re-evaluated for every single instance.

http://docs.jboss.org/drools/release/5.4.0.CR1/drools-expert-docs/html_single/images/Chapter-Rule_Engine/Node_Sharing.png

== Examples and Exercises ⌘==
1. See examples in _90_RETE folder

2. Draw a RETE tree for the rules below
TODO Copy the rules from the files

3. Optimize the rules below to make the RETE tree more optimal

== 举例和练习。==
1. 见 _90_RETE 文件夹中的例子

2. 根据下面的规则画一幅 RETE tree
TODO Copy the rules from the files

3. 优化下面的规则从而优化 RETE tree

== Sources ==
[http://docs.jboss.org/drools/release/5.4.0.CR1/drools-expert-docs/html_single/index.html Official Drools Documentation]

Drools - Rete - Revision history

Wang Hao at 08:35, 12 August 2016