Drools - Rete

From Training Material
Revision as of 08:35, 12 August 2016 by Wang Hao (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
title
Drools - Rete
author
Bernard Szlachta (NobleProg Ltd)

Drools -Rete

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

Rete Nodes.png

编译算法 。

  • 描述如何处理生产内存中的规则
  • 输出是一个高效鉴别网络
  • 在顶端的node有很多的匹配
  • 在底端的规则准备启动(firing)

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)

Object_Type_Nodes.png

ObjectTypeNodes can propagate:

  • AlphaNodes
  • LeftInputAdapterNodes
  • BetaNodes

ObjectTypeNode 。

  • 一直在线, 虽然可能看不见。比如
CourseEvent(booked == true)

包含两个条件:

    • 一: "有一个 CourseEvent, in mvel
CourseEvent()
    • 二: 有一个 booking (booked == true)

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

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 条件

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

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

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.

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.

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

Official Drools Documentation