rete

原始论文

http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf

源码解读

https://github.com/GNaive/naive-rete

问题

由google gemini-pro-1.5回答

在rete算法中，TOKEN与WEM的区别是什么？

在 Rete 算法中，TOKEN 和 WEM (Working Memory Element) 是两个重要的概念，它们在规则引擎的工作机制中扮演着不同的角色。
TOKEN

• 定义: TOKEN 是一个数据结构，它代表一个事实或事件，可以被规则引擎用来匹配规则条件。
• 作用: TOKEN 存储了与特定事实或事件相关的信息，并参与规则匹配过程。
• 特性:
  • 不可变: 一旦创建，TOKEN 的内容通常是不可变的。
  • 携带信息: TOKEN 包含了与事实或事件相关的所有必要信息，例如属性、值等。
  • 匹配规则: TOKEN 被用来匹配规则中的条件，如果匹配成功，则触发相应的规则。

WEM (Working Memory Element)

• 定义: WEM 是一个数据结构，它代表一个在工作内存中的事实或事件。
• 作用: WEM 存储了所有当前有效的 Facts 或 Events，并参与规则匹配和更新操作。
• 特性:
  • 可变: WEM 的内容可以被更新或删除，以反映工作内存中的变化。
  • 跟踪变化: WEM 可以跟踪工作内存中的事实和事件的变化，例如添加、删除或修改。
  • 影响规则: WEM 中的变化可能会影响规则的匹配结果，例如触发新的规则或取消旧的规则。

区别总结:

举例:
假设有一个规则：

1
2

规则： IF A = 1 AND B = 2 THEN C = 3

• 当一个 TOKEN 携带信息 A = 1 和 B = 2 进入系统时，它会与规则中的条件进行匹配。
• 如果匹配成功，该 TOKEN 会触发规则，并创建一个新的 WEM 存储 C = 3。
• 之后，如果另一个 TOKEN 携带信息 A = 2 进入系统，它会与 WEM 中的 C = 3 进行匹配，可能会触发其他规则。

总结:
TOKEN 代表着具体的、不可变的事实或事件信息，用于匹配规则条件。WEM 代表着工作内存中的事实和事件，可变且跟踪变化，影响规则的匹配和执行。两者协同工作，共同构建了 Rete 算法的规则引擎机制。

在rete算法中，join node的作用是什么

在 Rete 算法中，Join Node 是非常重要的组成部分，它的作用是连接匹配不同规则条件的 Token，并将符合条件的 Token 组合起来，传递给后续节点。
简单来说，可以将 Join Node 想象成数据库中的 JOIN 操作，它根据一定的条件将来自不同来源的数据合并在一起。
更具体地说，Join Node 的作用体现在以下几个方面:
1. 模式匹配: 每个 Join Node 对应一个规则中的多个条件。当来自不同 Alpha Node (存储单个条件匹配结果的节点) 的 Token 进入 Join Node 时，它会检查这些 Token 是否满足连接条件。
2. 连接条件: Join Node 会存储连接条件，通常是用来比较两个 Token 的属性值是否相等。例如，一个 Join Node 的连接条件可能是 “Token1.customerID == Token2.customerID”，表示只有当两个 Token 的 customerID 属性相等时才会被连接。
3. Token 组合: 如果 Join Node 判断多个 Token 满足连接条件，就会将它们组合成一个新的 Token，这个新的 Token 包含了所有输入 Token 的信息。
4. 传递 Token: Join Node 会将组合后的新 Token 传递给它的后续节点，例如 Beta Node (存储部分或全部规则匹配结果的节点) 或另一个 Join Node。
Join Node 的优势:

• 提高效率: Join Node 通过提前执行连接操作，避免了在后续节点中进行重复的匹配工作，从而提高了规则匹配的效率。
• 支持复杂规则: 通过多个 Join Node 的级联，Rete 算法可以处理包含多个条件的复杂规则。

举例说明:
假设有一个规则：

1
2

规则:  IF  Person.city == "北京" AND Order.customerID == Person.customerID THEN ...

这个规则包含两个条件：

• 条件1: Person.city == “北京”
• 条件2: Order.customerID == Person.customerID

在 Rete 网络中，这两个条件会被分别存储在两个 Alpha Node 中。当有新的 Person 或 Order 对象进入系统时，对应的 Alpha Node 会生成 Token 并传递给后续的 Join Node。
Join Node 会检查来自两个 Alpha Node 的 Token 是否满足连接条件 “Order.customerID == Person.customerID”，如果满足，就会将它们组合成一个新的 Token，包含 Person 和 Order 的所有信息，并传递给后续节点。
总而言之，Join Node 是 Rete 算法中至关重要的组成部分，它通过连接匹配不同规则条件的 Token，将符合条件的 Token 组合起来，为高效执行复杂规则匹配提供了基础。

在rete算法中，否定条件的节点如何实现

在 Rete 算法中，否定条件的实现依赖于一种特殊的节点类型，称为 Not Node (否定节点) 或 Negative Node。 Not Node 用于处理规则中包含 “NOT”、”!==” 等否定语义的条件。
Not Node 的工作机制:

1. 接收 Token: Not Node 会从其左侧的节点（通常是 Alpha Node、Beta Node 或另一个 Not Node）接收 Token。这些 Token 代表着已经满足了规则中部分条件的数据。
2. 监听右侧输入: Not Node 同时还会监听来自其右侧的另一个分支的输入。这个分支通常连接到一个或多个 Alpha Node 或 Beta Node，用于匹配否定条件。
3. 判断否定条件: 一旦 Not Node 的右侧分支有新的 Token 输入，它会将该 Token 与自身存储的左侧 Token 进行比较。
   • 如果匹配: 表示否定条件成立，Not Node 会撤销之前传递给后续节点的左侧 Token，因为数据已经不再满足规则条件。
   • 如果不匹配: 表示否定条件不成立，Not Node 会将左侧 Token 继续传递给后续节点，因为数据仍然满足规则条件。
4. 传递 Token: 当 Not Node 的左侧收到新的 Token 时，它会重复步骤 2 和 3，以确保只有满足所有条件（包括否定条件）的 Token 才会被传递到后续节点。

Not Node 的特点:

• 延迟执行: Not Node 不会立即对其接收到的 Token 进行处理，而是会等待右侧分支的输入，再进行否定条件的判断。
• 撤销机制: 当否定条件成立时，Not Node 会主动撤销之前传递给后续节点的 Token，以维护数据的一致性。

示例说明:
假设有一条规则：

1
2

规则: IF Person.age > 18 AND NOT Order.product == "玩具" THEN ...

这条规则包含一个否定条件： NOT Order.product == "玩具"，表示只有当订单中的商品不是玩具时，规则才会被触发。
在 Rete 网络中，这个规则会被分解成多个节点，其中包含一个 Not Node 用于处理否定条件。

• 当一个 Person 对象的 age 属性大于 18 时，会生成一个 Token 并传递到 Not Node 的左侧。
• 当一个 Order 对象的 product 属性等于 “玩具” 时，会生成一个 Token 并传递到 Not Node 的右侧。
• Not Node 会比较这两个 Token，发现它们匹配（即否定条件成立），因此会撤销之前传递给后续节点的 Person Token。

总结:
Not Node 是 Rete 算法中处理否定条件的关键机制，它通过监听多个分支的输入、比较 Token 并撤销不符合条件的数据，确保了只有满足所有条件（包括否定条件）的数据才会触发规则。

rete算法中，Conjunctive Negations如何实现

在 Rete 算法中，Conjunctive Negations（合取否定）指的是规则中包含多个否定条件，并且这些否定条件之间是 AND 关系的情况。例如：

1
2

规则：IF A > 10 AND NOT B = 20 AND NOT C = 30 THEN ...

这个规则包含两个否定条件：NOT B = 20 和 NOT C = 30， 而且它们之间是 AND 的关系，也就是说只有当 B 不等于 20 并且 C 不等于 30 时，规则才会被触发。
实现 Conjunctive Negations 的关键在于如何协调多个否定条件的匹配结果，确保只有当所有否定条件都满足时才会触发规则。
在 Rete 网络中，通常有以下几种方式实现 Conjunctive Negations：
1. 级联 Not Node：

• 将多个 Not Node 级联起来，每个 Not Node 负责处理一个否定条件。
• 第一个 Not Node 接收来自左侧节点（例如 Alpha Node 或 Beta Node）的 Token，并监听其右侧分支（匹配第一个否定条件）的输入。
• 如果第一个否定条件成立，则第一个 Not Node 会将 Token 传递给第二个 Not Node，否则丢弃该 Token。
• 第二个 Not Node 重复上述过程，直到所有 Not Node 都满足条件，才会将 Token 传递给后续节点。

这种方式简单直观，但效率较低，因为需要在多个 Not Node 之间传递 Token，增加了网络的复杂度。
2. 专用 Join Node：

• 使用一个特殊的 Join Node 来处理多个否定条件。
• 该 Join Node 会接收来自多个 Alpha Node 或 Beta Node 的 Token，分别代表不同的否定条件。
• Join Node 会存储所有否定条件，并检查输入的 Token 是否与所有否定条件都匹配。
• 只有当一个 Token 与所有否定条件都匹配时，Join Node 才会将该 Token 传递给后续节点。

这种方式效率较高，因为它避免了在多个节点之间传递 Token，但需要设计专门的 Join Node 来处理否定条件的逻辑。
3. Negation Join Node + 共享 Beta Memory：

• 使用一种特殊的 Negation Join Node 来连接多个否定条件分支。
• 每个否定条件分支连接到一个 Beta Node，所有 Beta Node 共享同一个 Beta Memory。
• 当一个 Token 满足某个否定条件时，会将其加入到共享的 Beta Memory 中。
• Negation Join Node 会监听共享 Beta Memory 中数据的变化，只有当 Beta Memory 中包含所有否定条件对应的 Token 时，才会将左侧 Token 传递给后续节点。

这种方式结合了前两种方法的优点，既能高效地处理多个否定条件，又能保持 Rete 网络的结构简洁。
总而言之，Conjunctive Negations 是 Rete 算法中处理复杂规则的重要机制。选择哪种实现方式取决于具体的应用场景和性能需求。