Drools - Rete

title

Drools - Rete

author

Bernard Szlachta (NobleProg Ltd)

Drools -Rete

Copyright Notice

Copyright © 2004-2023 by NobleProg Limited All rights reserved.

This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise.

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

编译算法 。

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

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)

ObjectTypeNodes can propagate:

• AlphaNodes
• LeftInputAdapterNodes
• BetaNodes

ObjectTypeNode 。

• 一直在线, 虽然可能看不见。比如

CourseEvent(booked == true)

包含两个条件:

• • 一: "有一个 CourseEvent, in mvel

CourseEvent()

• • 二: 有一个 booking (booked == true)

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

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

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

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 ⌘

• 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.

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.

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