北京航空航天大学硕士学位论文
第四章 鉴别网络的设计
鉴别网络（discrimination network）是RETE 算法的基础。本章将从设计的具体细节着手，在介绍鉴别网络的基本结构后，阐述alpha 和beta 网络生成算法的设计。最后通过实例给出了利用所设计的算法，由规则对象建立鉴别网络的过程。
4.1 鉴别网络的结构
鉴别网络是因规则的不断加入而形成的，是与加入的规则相对应的对象网络。在系统中只有一个鉴别网络存在，鉴别网络中包含有多个已定义规则。鉴别网络分为两部分：alpha 网络和beta 网络，如图10所示。
图10 鉴别网络结构图
规则在鉴别网络中表现为从根结点到终结点的一条路径。在该网络中，包含两条规则joinConversion1和joinConversion2，规则joinConversion1和joinConversion2在鉴别网络中表示的路径如图11所示。
3
254
7
0253
811
joinConversion1joinConversion2
图11 规则joinConversion1与规则joinConversion2的结点路径图
在alpha 网络中，每一个结点代表了规则的一个模式（除去左侧输入适配结点），在alpha 网络中的模式匹配都是单个事件实例的模式匹配。在beta 网络中的每一个结点代表了规则的一个模式，在beta 网络中的模式匹配都是多个事件实例的模式匹配，每个结点都是执行事件关联的结点。根结点是事件实例的输入结点，终结点规定了规则的右部
29
第四章 鉴别网络的设计
动作。
在鉴别网络中，CE 表示一条路径，从alpha 网络的第一个结点开始，到beta 网络的第一个结点结束。例如规则joinConversion1的CE0表示路径2，5，6；CE1表示路径3，4，6；规则joinConversion2(见附录) 的CE0表示路径2，5，10；CE1表示路径3，8，10。CE0是特殊的CE ，即规则的第0个CE ，只有CE0才能包含左侧输入适配结点。
在进行规则匹配时，事件实例从根节点进入鉴别网络并从根结点到终结点进行模式匹配。当事件实例经过的每一个结点都能够完成模式的成功匹配，则表示规则匹配的成功，则执行终结点所对应的规则右部动作。
4.2 基本元素定义
结点是鉴别网络中基本的元素，在本节中分别介绍了结点类型、图示、结点间关系和结点的存储区。
4.2.1 结点类型与模式
模式分为单一模式和复合模式。每一个alpha 结点（除去左侧输入适配结点）都有单一模式与之对应。Beta 结点中含有复合模式，是用于事件关联的结点类型。下面对各种类型的结点进行具体分析。
根结点：当规则加入到鉴别网络或者模式匹配开始时，都是从根结点开始的。
终结点：当事件实例匹配到终结点时，激发规则的右部动作，产生可能的故障假设。该结点没有相应的存储区与之对应。
alpha 网络中的结点称为alpha 结点，alpha 结点有三种类型：事件类型结点、Alpha 结点和左侧输入适配结点。
事件类型结点：保存了事件类型约束信息。例如规则joinConversion1的CE0所指定的事件类型约束EventOne ，该结点保存了事件类型约束信息EventOne 。
Alpha 结点：保存了字面量约束信息。例如规则joinConversion1的CE1所指定的字面量约束(shortAttr 100)，该结点保存了该字面量约束信息。
左侧输入适配结点：其输出指向Beta 结点的左侧输入。该结点是CE0路径的尾结点。该结点不存储事件信息，仅对Beta 结点的左侧输入进行适配。
，该结点保存了复合beta 网络中的结点称为Beta 结点（也称joinNode 和关联结点）
模式，即规定了规则中的事件关联条件。在规则的左部中，如果两个CE 有相互关系，
30
北京航空航天大学硕士学位论文
规则加入到鉴别网络时会生成Beta 结点，例如规则find_unaccessable_host指定的CE0中的变量dest_variable和CE1中的变量dest_variable是同一变量，表明这两个CE 规定的关联关系为“目标IP 相同”。而否定变量source_variable规定CE0与CE1之间的关联关系为“源IP 不相同”。
4.2.2 基本结点图示
为了表述方便，将各个结点的图示做如下规定，如图12所示。
图12 鉴别网络基本结点图示
4.2.3 结点间的关系限定
鉴别网络是一个有向无环图。因为各个结点的作用不同，结点之间的相互关系也不相同，RETE 算法对鉴别网络结点的关系做了如下规定：
(1) 根结点的入度为0，Beta 结点的入度是2，其他结点的入度均为1；
(2) 终结点的出度为0，其他结点的出度均大于0；
(3) 根结点的后继结点类型只能是事件类型结点；
(4) 事件类型结点的后继结点类型可以是左侧输入适配结点、终结点、Beta 结点、
或Alpha 结点；
(5) 左侧输入适配结点的后继结点类型是Beta 结点；
(6) Beta 结点的左侧输入结点类型只能是左侧输入适配结点或Beta 结点；
(7) Beta 结点的右侧输入结点类型只能是事件类型结点或Alpha 结点；
(8) Beta 结点的后继结点类型可以是终结点或Beta 结点；
终结点，Beta 结点或Alpha (9) Alpha 结点的后继结点类型可以是左侧输入适配结点，
结点。
4.2.4 结点与存储区的关系
为了使得部分匹配结果能够用于下次的再次匹配，提高retract 动作的执行效率，结点需要存储区来存储匹配结果，因此凡是具有模式约束的结点都有存储区。存储区分为
31
第四章 鉴别网络的设计
两种类型：alpha 存储区和beta 存储区。存储区和结点的关系如下：
(1) 根结点，左侧输入适配结点和终结点没有存储区，因为这些结点没有模式信息。
(2) 事件类型结点、Alpha 结点有alpha 存储区，前者具有事件类型的约束，后者具
有字面量约束。
一个是左侧存储区，另一个是右侧存储区。前者是beta (3) Beta 结点有两个存储区，
存储区，后者是alpha 存储区。Beta 结点具有复合模式。
4.3 规则加入到鉴别网络的过程
本节给出了一个由规则生成鉴别网络的例子，将规则joinConversion1做为第一条规则，加入到鉴别网络，继续添加规则joinConversion2(见附录) 到鉴别网络，两个规则加入到鉴别网络的过程如图13所示。
EventTwo EventOne
加入:j o
joinConversion1joinConversion2
图13 鉴别网络生成图
最终形成的鉴别网络中，joinConversion1的CE0代表该规则的第0个条件元素(EventOne (intAttr ?intA))，joinConversion1的CE1代表该规则的第1个条件元素(EventTwo(strAttr ?intA)(shortAttr 100))。将规则joinConversion2加入到鉴别网络后，和
32
北京航空航天大学硕士学位论文
规则JoinConversion1共享其中的某些结点产生新的路径：JoinConversion2的CE0代表该规则的第0个条件元素(EventOne (intAttr ?intA))；joinConversion2的CE1代表该规则的第1个条件元素(EventTwo(strAttr ~?intA)(shortAttr 101)。
4.4 规则对象的设计
对象是面向对象编程的术语，是类的实例。生成鉴别网络的前提是CLIPS 语言所指定的规则在词法分析和语法分析之后，形成了和规则对应的规则对象。本节对规则对象及其依赖的数据进行表示，以便于阐述鉴别网络生成算法的设计。
在生成鉴别网络时，一方面生成内存中的对象网络，另一方面将对规则对象的binds 和joins 属性以及condition 的nodes 、hasNotEqual 和hasPredicate 属性进行填充。
4.4.1 规则对象
为了阐述鉴别网络算法的设计，将规则对象中的关键成员变量抽取出来，用五元组表示为Rule=，对规则对象的属性规定如表1所示。
表1 规则对象属性表 name
conditions
binds
joins
actions 规则的名字 规则所包含的所有CE 列表 规则的所有被绑定变量 与该规则对应的所有Beta 结点 规则的右部动作
4.4.2 条件元素
对于规则对象中的每一个CE ，用condition 来表示。CE 有三种类型：ObjectCE 和ExistsCE 和Not CE。对这三种类型的CE 规定如下：
Object CE是一个六元组Object CE=，Exist CE是一个二元组Exist CE=。其中Not CE是negated=true的Object CE。在建立鉴别网络时，只处理Object CE和Exist CE两种情况，对于Not CE做为Object CE的一种特殊情况来处理。对Object CE属性的规定如表2所示。
表2 Object CE的属性表
template 该CE 对应的事件类型约束
33
第四章 鉴别网络的设计
约束信息
constraints
(字面量约束、变量绑定约束、谓词函数约束)
nodes
negated
hasNotEqual
hasPredicate 与该CE 所对应的alpha 结点和beta 结点 该CE 是否是Not CE 该CE 是否具有否定的变量绑定约束 该CE 是否具有谓词函数约束
4.4.3 变量
通过变量可以建立两个CE 间的联系，只有两个CE 存在联系，才能够进行多个事件实例的模式匹配。因此变量是进行事件关联的基础，是Beta 结点binds 列表中的元素。变量用六元组表示如下：bind=。对bind 的属性规定如表3所示。
表3 变量的属性
varName
rowId
leftIndex
rightIndex
negated
isPredJoin 变量绑定或者谓词函数变量的名字 被绑定变量所在的行号 被绑定变量所在的列号 绑定变量所在的列号 是否为否定的变量绑定 是否为谓词函数约束
变量分为绑定变量和被绑定变量。变量的第一次出现称为被绑定变量；变量的第n 次(n>1)出现称为绑定变量。被绑定变量只是对变量的定义，因此无论是肯定变量约束、否定变量约束还是谓词函数约束，被绑定变量的属性negated 和属性isPredJoin 值为空。rightIndex 指定了绑定变量所在列号，因此在被绑定变量中也为空。绑定变量的属性值都不为空。
4.5 alpha 网络生成算法的设计
规则对象加入到鉴别网络之前，首先是对规则所依赖的事件类型进行定义，该定义生成了鉴别网络中的事件类型结点。针对于规则中的每一个CE ，利用alpha 网络生成算法建立相应的alpha 网络，算法总体流程图如图14所示。alpha 网络生成算法总体流程图中，处于核心位置的是“建立alpha 网络”算法，其中包含对规则对象binds 属性的填充。
34
北京航空航天大学硕士学位论文
图14 alpha 网络生成算法总体流程图
Not CE做为Object CE的一种特殊类型，因此不对Not CE单独处理。该算法对于Exist CE到鉴别网络的转换，是取出该CE 中的Object CE，然后建立Object CE对应的alpha 网络。从Object CE建立alpha 网络是从Exist CE建立alpha 网络的子过程。
4.5.1 建立alpha 网络算法的设计
建立alpha 网络算法的流程图如图15所示。该算法主要完成两方面的工作：
建立alpha 结点串（如果鉴别网络中有相同模式的结点，(1) 对于字面量约束的模式，
则共享结点），并加入到condition 的nodes 列表中。
(2) 对于第一次出现的变量绑定约束或谓词函数约束，建立bind 变量并填充到规则
对象的binds 属性。
如果是从空的鉴别网络中加入规则，则不需考虑与已有规则的alpha 结点进行结点共享。如果鉴别网络中存在先前加入的规则，则需要考虑现有规则的加入与先前规则所对应网络中的结点的共享问题。对于alpha 结点的共享算法，在4.5.2节中进行详细阐述。
35
第四章 鉴别网络的设计
图15 建立alpha 网络程序流程图
算法的详细描述如下： 算法名称：建立alpha 网络
输入：条件元素condition ，条件元素位置position ，规则对象rule
输出：无
1) 获得condition 的事件类型约束template 。
2) 建立空的结点串nodesList 。
3) 获得condition 的下一个约束信息constraint 。若constraint 不是字面量约束，则
跳至6步。
4) 建立alpha 结点。
5) 将alpha 结点加入到nodesList 的最后一个位置，跳至7步。
6) 若constraint 是变量绑定约束或谓词函数约束且是第一次出现，则以constraint 、
template 和position 为参数调用“生成被绑定变量”算法得到bind ，将bind 填充
至规则对象的binds 属性。
7) 若存在下一个约束信息constraint ，则跳至3步。
8) 将nodesList 、template 和condition 做为参数，调用“共享alpha 网络”算法。 算法名称：生成被绑定变量
输入：约束信息constraint ，事件类型template 和约束所在CE 位置position
输出：被绑定变量bind
1) 建立bind 。
36
北京航空航天大学硕士学位论文
2) 将constraint 的变量名赋值给bind 的varName 。
3) 将position 赋值给bind 的leftRow 。
4) 通过constraint 对应的属性名，在template 中得到该约束所在的事件类型的插槽
位置并赋值给leftIndex 。
5) 返回该bind 元素。
在算法“建立alpha 网络”中，根据ObjectCE=中不同的constraint ，有着不同的处理：对于字面量约束建立Alpha 结点；而对于变量绑定约束和谓词函数约束的第一次出现只建立bind ，并加入到该ObjectCE 所在的Rule 的binds 属性，而不生成Alpha 结点。
在该规则加入到鉴别网络之前，网络中可能含有与新建立的结点串模式相同的结点，即有相同的字面量约束，因此需要对已存在结点进行共享。这样有利于节省内存，提高模式匹配效率。
4.5.2 alpha 网络中结点的共享
在建立新结点串时，“共享alpha 网络”算法用于和原鉴别网络进行Alpha 结点共享。算法的详细描述如下： 算法名称：共享alpha 网络
输入：已有结点existing ，新结点串alpha ，条件元素condition
输出：无
1) 若alpha 为空串，则结束。
2) 将existing 和alpha 做为参数，调用“获得共享结点”算法，得到共享结点share 。
若share 不为空，则跳至5步。
3) 将alpha 结点串的第一个结点做为existing 的后继结点。
4) 将alpha 结点串中的每一个结点取出，加入到condition 的nodes 列表；结束。 5) 将共享结点share 加入condition 的nodes 属性。
6) 获得alpha 结点串的下一个结点alphaSuc 。将共享结点share 、alphaSuc 和条件
元素condition 做为参数，递归调用“共享alpha 网络”算法。
算法名称：获得共享结点
输入：已存在的结点existing ，新结点串alpha
输出：共享结点share
1) 取出existing 的后继结点share ，若该结点和alpha 的第一个结点具有相同的字
面量约束，返回share 。
2) 如果existing 有其他的后继结点，则转向1步，否则返回空。
例如鉴别网络中已存在的规则有rule1和rule2，如图16所示。
37
第四章 鉴别网络的设计
EventOne e1-attr0=rule1rule2 图16 已有的鉴别网络
若再添加规则(defrule rule3 (EventOne (e1-attr0 "ok") (e1-attr1 200) )=>……)
，则通过该算法，将新建立的
alpha
结点串（如
图
17
所示）和现有的鉴别网络（如
图16）合并，共享现有结点
2，4，生成最终的规则网络，如图18所示。
图17 新规则所形成的alpha
结点路径
图18 新规则加入鉴别网络后，共享结点2，4形成的鉴别网络
下面根据此实例，在加入新规则时和已有的规则共享结点的过程对对“共享alpha 网络”算法进行详细阐述，即由图16转变成图18的过程。
在调用“共享alpha 网络”算法之前，对于Object CE的字面量约束建立了结点串。condition 的template 对应的事件类型结点做为算法的第一个参数existing ，alpha 指向该结点串的第一个结点并做为算法的第二个参数，condition 做为算法的第三个参数，传递到该算法。在调用算法前如图19所示。
38
北京航空航天大学硕士学位论文
图19 共享结点形成鉴别网络，调用算法前
首先获得共享的结点4，然后将序号为4的共享结点加入到该ObjectCE 中的nodes 列表，此时condition 中的nodes 列表中的元素为Node4。在递归调用“共享alpha 网络”算法前，所形成的鉴别网络如图20所示。递归执行该算法，将序号为9的非共享结点加入到该ObjectCE 中的nodes 列表，此时condition 中的nodes 列表中的元素为Node4和Node9。再将Node9加入到鉴别网络中，形成的alpha 网络（此时未形成终结点）如图21所示。到此为止，规则rule3加入鉴别网络，共享现有结点2，4。
图
20 共享结点形成鉴别网络，递归调用算法前
图21 共享结点形成鉴别网络，调用算法后
4.6 beta 网络生成算法的设计
Beta 结点是对多个事件实例进行模式匹配的结点。对于不同的事件关联类型，会产 39
第四章 鉴别网络的设计
生不同的Beta 结点。beta 网络生成算法的核心是建立包含有绑定变量列表的beta 结点并连接起来。绑定变量列表是进行事件关联的依据，指明了需要进行关联的事件实例的属性位置。
beta 网络的生成是根据上节所形成的规则中的binds 属性和conditions 属性来进行的，如果规则包含多个CE ，则对CE0建立左侧输入适配结点，对于其他的CE 建立beta 结点。对于仅有一个CE 的规则建立的是特殊的beta 结点：ExistJoinFirst 结点。本节主要阐述为含有多个CE 的规则建立beta 网络的算法。
算法的总体流程图如图22所示。
图22 beta 网络生成算法总体流程图
算法的详细描述如下： 算法名称：建立beta 网络
输入：规则对象rule
输出：无
1) 获得规则对象的条件元素列表conditions ，若条件元素个数等于1，则跳至7。 2) 建立preCondition 、currCondition 、preJoinNode 和curJoinNode ，并赋值为空。 3) 得到条件元素列表的第0个condition （CE0），建立左侧输入适配结点LIANode ，
40
北京航空航天大学硕士学位论文
4)
5)
6)
7) 将该结点做为condition 的nodes 列表的最后一个结点的后继结点；并将LIANode 加入到该condition 的nodes 列表。将该condition 做为preCondition 。 得到条件元素列表的下一个condition ，做为currCondition 。将currCondition 、条件元素位置position 和规则对象做为参数，调用“获得绑定变量列表”算法，得到绑定变量列表binds 。 将currCondition 和绑定变量列表binds 做为参数，调用“建立beta 结点”算法建立joinNode 做为curJoinNode 。 将preCondition ，currCondition ，preJoinNode 和curJoinNode 做为参数传递给“连接beta 结点”算法。若存在下一个condition ，则跳至4步；否则结束。 建立ExistJoinFirst ，加入该结点到rule 的nodes 列表；结束。
该算法的关键主要是第3、4、5、6步，在本节分四部分对这四步进行了阐述。
4.6.1 建立左侧输入适配结点
左侧输入适配结点是属于alpha 网络中的结点，但该结点是在beta 网络生成算法中建立的。在建立beta 网络时，CE0中不存在被绑定对象，因此有必要将CE0建立左侧输入适配结点和其他CE 建立beta 结点的过程分开。该步骤是建立和CE0对应的左侧输入适配结点，并加入到condition 的nodes 列表中。
4.6.2 获得绑定变量列表
在beta 结点中，绑定变量列表中的元素是bind=，每个元素都指定了CE 中用于事件关联的变量，该变量列表是基于插槽位置的事件实例查找方法和索引生成方法的基础。在建立beta 结点前，首先根据规
然后则中的被绑定变量和CE 中的constraint 元素获得与该CE 所对应的绑定变量列表，
将该列表加入到beta 结点中。对于CE 中的每一个复合模式，获得bind 变量的过程如下：
(1) 获得rule 中的被绑定变量。
对于变量绑定类型的约束，由于变量名是相同的，可以通过constraint 包含的变量名找到rule 中的被绑定变量；对于谓词函数约束的constraint 中，包含有变量名和被绑定的变量名，因此也能够找到rule 中的被绑定变量。
(2) 复制被绑定变量属性到绑定变量，生成绑定变量元素，并对CE 的hasNotEqual
和hasPredicate 属性进行初始化。
算法的详细描述如下：
算法名称：获得绑定变量列表
输入：条件元素condition 、条件元素位置position 和规则对象
输出：绑定变量列表binds
1) 从条件元素中获得非第一次出现的constraints 列表。
2) 建立空的绑定变量列表binds ；
41
第四章 鉴别网络的设计
3) 取出constraints 列表的元素constraint ，若该约束为否定约束，则将condition 的
hasNotEqual 属性设置为True ；若该约束为谓词函数约束，则将condition 的
hasPredicate 属性设置为True 。
4) 通过constraint 的名字，取出rule 中的被绑定变量binded ，建立绑定元素bind ，
复制binded 的varName 、leftRow 和leftIndex 属性到bind ；通过constraint 填充
其他的bind 属性。
5) 加入bind 到binds 列表。
6) 若constraints 含有下一个约束，转向3步，否则返回binds 。
4.6.3 建立beta 结点
为了提高模式匹配的效率，对于不同的CEn(n>0)建立不同的beta 结点，condition 中的hasNotEqual 和hasPredicate 属性指定了该CE 是否拥有否定的变量绑定约束和谓词函数约束，根据这两个属性和binds 列表来建立不同类型的beta 结点。
在模式匹配算法中，用于谓词函数约束的模式匹配方法可以用于变量绑定约束，用于否定的变量绑定约束的模式匹配方法可用于肯定的变量绑定约束。变量约束是存在优先级关系的，即谓词函数约束>否定变量约束>肯定变量约束。为了表述方便，做出规定如表4所示。因此说某个CE 具有某个类型的约束，或者某个beta 结点具有某个类型的约束。
根据所包含的约束类型不同和CE 的类型不同，建立的beta 结点也不相同，如表5所示。beta 结点的类型还有用于单个CE 的ExistJoinFirst ，仅表达CE 间“与”关系的ZJBetaNode 。
最后将由上节获得的binds 变量列表加入到生成的beta 结点中。
表4 具有不同约束的CE
约束定义 hasNotEqual hasPredicate
具有谓词函数约束具有否定的变量绑定约束具有肯定的变量绑定约束表5 beta 结点类型表
CE 类型 具有谓词函数约束 具有否定的变量绑定约束
Object CE
Exist CE
Not CE PredicateBNode ExistPredJoin NotJoin HashedNotEqBJoin ExistNeqJoin HashedNotEqNJoin 具有肯定的变量绑定约束 HashedEqBNode ExistJoin HashedEqNJoin
42
北京航空航天大学硕士学位论文
4.6.4 连接beta 结点
beta 结点是CE 的末尾结点，因此连接beta 结点是对两个CE 的连接。在“alpha 网络生成算法”中建立的condition 的nodes 列表用于CE 之间的连接，主要有两个过程：
(1) 获得前一个CE 对应的condition 的nodes 列表的最后一个结点或者前一个beta
结点，将该结点做为新beta 结点的左侧输入。
(2) 获得当前CE 对应的condition 的nodes 列表的最后一个结点或者condition 对应
的事件类型结点，将该结点做为新beta 结点的右侧输入。
算法的详细描述如下： 算法名称：连接beta 结点
输入：前一个条件元素preCondition ，当前条件元素condition 、前一个beta 结点preJoinNode 和当前beta 结点joinNode 。
输出：无
1) 若preJoinNode 不为空，将preJoinNode 做为joinNode 的前驱结点；否则将
preCondition 的nodes 列表的最后一个结点做为joinNode 的前驱结点。
2) 取出condition 的template ，得到事件类型结点objectTypeNode 。
3) 若condition 的nodes 列表不为空，取出该列表的最后一个结点做为joinNode 的
前驱结点；否则将objectTypeNode 做为joinNode 的前驱结点。
4.7 event-correlation-rule 加入鉴别网络的过程
规则event-correlation-rule 定义如下：
(defrule event-correlation-rule
(EventOne
(e1-attr0 "ok")
(e1-attr1 ?var1)
(e1-attr2 ?var2)
(e1-attr3 ?var3))
(not(EventTwo
(e2-attr0 ?var1)
(e2-attr2 ?var4&:(> ?var4 ?var2))))
(exists (EventThree
(e3-attr0 ~?var1)))
(EventFour
(e4-attr0 ?var5))
43
第四章 鉴别网络的设计
=>(printout t "event-correlation-rule fired " ?var5 ?var3 crlf))
规则event-correlation-rule 所涉及的事件如表6所示，该规则如表7所示。 表6 规则event-correlation-rule 的事件定义表
---------------------------------------
表7 规则event-correlation-rule 描述表 Slot0
False EventOne
True
EventTwo Slot2 ?var2 ?var4&: ?var1
~?var1
?var5无 (> ?var4 ?var2)
EventThree
False
EventFour
无
--------
无 无
------- ?var3 ?var1规则信息通过词法分析和语法分析之后，形成规则对象。此时的规则对象除了binds ，join 为空，其他都根据表7赋予相应的值。在规则对象的conditions 中的每一个condition ，除了nodes 之外，其他都赋予相应的值。因此得到了初始化的规则对象。
在利用deftemplate 进行事件的定义时，已经生成了事件类型结点，如图23所示。下面阐述alpha 网络和beta 网络的生成过程。
图23 加入事件类型后的鉴别网络
4.7.1 alpha 网络的建立
从event-correlation-rule 的CE0建立alpha 网络时，第一个约束为字面量约束，模式为
44
北京航空航天大学硕士学位论文
(e1-attr0 "ok")，建立的Alpha 结点对应为字面量约束”ok”，如图24所示。
图24 建立字面量约束的alpha 结点图
继续获得该CE0的模式，第二、三、四个模式是复合模式，是含有变量定义（第一次出现的变量约束和谓词函数定义的变量）的模式。因此参考表6建立binds ，如表8所示，并加入到规则对象中。 表8 获取CE0中被绑定元素列表
CE
CE0
CE0
CE0leftIndex rightIndex negated 形成binds 属性的过程是这样的：根据表7中所示，CE0定义了三个变量var1、var2、var3，这三个变量均在规则的第0个CE ，则将rowId 设置为0，三个变量所在的插槽分别为Slot1，Slot2，Slot3，因此将leftIndex 设置为1，2，3。
由于该规则不存在Alpha 结点的共享，因此event-correlation-rule 所形成的CE0对应的nodes 列表中的元素为Node6。至此对应于CE0的alpha 网络生成结束。
对于CE1，被绑定变量只有var4，因此仅生成一个bind ，并加入到rule 的binds 属性中。var1做为绑定变量并不生成bind 。
对于CE2，因为没有字面量约束，所以不生成Alpha 结点，而且CE2没有被绑定约束变量，也不生成bind 。
对于CE3，仅生成一个被绑定变量bind ，并加入到rule 的binds 属性中。
最终形成规则对象的binds 属性如表9所示。在alpha 网络生成算法之后，CE0对应的condition 的nodes 列表中的元素为Node6，其他condition 的nodes 列表长度均为0，而对于condition 的hasNotEqual 和hasPredicate 的属性的赋值将在建立beta 网络时进行。
45
第四章 鉴别网络的设计
表9 最终形成的event-correlation-rule 的binds 列表 leftIndex
rightIndex negated
4.7.2 beta 网络的建立
对于规则event-correlation-rule ，建立和CE0对应的左侧输入适配结点后的鉴别网络如图25所示。CE0对应的nodes 列表元素为Node6和Node7。
EventOne 图25 在CE0中加入左侧输入适配结点 对于CE1，找到CE1的第一个约束（变量绑定类型），约束名为var1。用该变量名var1查找表9，拷贝表9中CE0的被绑定变量var1的属性并对其他属性赋值，形成表10的第一行。找到CE1的第二个约束（谓词函数类型），约束名为var4，被绑定变量名为var2。
拷贝表9中CE0的被绑定变量var2的属性并对其他属性赋值，形成表用var2查找表9，
10的第二行。
表10 CE1的绑定变量列表
rightIndex 0 2 negated 在表10中，列varName 、rowId 、leftIndex 是从rule 的binds 属性中拷贝所得，其他列是分析约束信息所得。例如：第一行的rightIndex 指明绑定变量var1的值可以在CE1的第0个插槽位置上得到；negated=false说明该绑定变量是肯定类型的变量绑定约束。第二行指明绑定变量var4绑定了变量var2，该绑定变量var4的值可以在CE1的第2个插槽位置上得到；isPredJoin=true说明该变量为谓词函数约束。
46
北京航空航天大学硕士学位论文
此时CE1所对应的condition 的hasNotEqual 和hasPredicate 都为true 。然后根据condition 的类型和表5建立NotJoin 结点。将表10的绑定变量列表加入到该结点，如图26所示。
图26 第一次调用“连接beta 结点”算法前 在连接beta 结点时，CE0对应的condition 的nodes 列表为Node6、Node7。在Node7后加入Node8，因此Node8
的左侧输入为Node7。而此时CE0的condition 的nodes 列表保持不变，仅将Node8做为Node7的后继结点，如图27所示。
图27 加入Node8之后，CE0的Condition 的nodes 列表图
因为CE1没有建立alpha 结点，连接beta 结点时，CE1的condition 的nodes 列表为空，因此将该condition 对应的事件类型结点，做为Node8的右侧输入。连接Node8到鉴别网络的工作完成，如图28所示。
图28 连接Node8到鉴别网络完毕
由上述获得绑定变量列表、建立beta 结点的过程可知，对于CE2生成了类型为ExistNeqJoin 的Node9，鉴别网络如图29所示。Node8做为Node9的左侧输入连接到Node9。而同连接Node8的右侧输入相同，将Node4做为Node9的右侧输入连接到Node9。
继续连接由CE3生成的结点Node10，最终生成的alpha 网络和beta 网络如图30所示。 47
第四章 鉴别网络的设计
图29 连接Node9到鉴别网络之前
EventOne 图30 event-correlation-rule 形成的alpha 网络和beta 网络 通过前面beta 网络的建立过程的描述，最终生成的对应于每个CE 的condition 如表11所示。其中对于每个CE 建立的Beta 结点在表11的第六列，对于CE0的nodes 列表如图31所示。每个Beta 结点中所包含的绑定元素如表12所示。
表11 event-correlation-rule 中每个CE 的Condition 和Beta 结点 CE 类型列表
有
无
无
无
表12 由event-correlation-rule 生成的beta 结点列表
rowId leftIndex rightIndex hasPredicate hasNotEqual Beta 结点 无
48
北京航空航天大学硕士学位论文
1
无绑定元素
图31
event-correlation-rule
中CE0的condition 的nodes 列表
在形成alpha 网络和beta 网络之后，将规则的右部做为规则激发时的动作加入到终结点，并加入到鉴别网络当中，最终形成了与规则event-correlation-rule 相对应的鉴别网络。如图32所示。
图32 event-correlation-rule 所在的鉴别网络
4.8 本章总结
本章介绍了鉴别网络的基本结构及其基本元素。在介绍鉴别网络的生成前，首先对规则对象进行了设计，然后阐述了alpha 网络和beta 网络的生成算法的设计，最后讲述了event-correlation-rule 加入到鉴别网络的过程。
49
第五章 模式匹配的设计
第五章 模式匹配的设计
在鉴别网络中，alpha 结点（除去左侧输入适配结点）和beta 结点都有相应的存储区，满足结点约束的事件实例都被存储在相应的存储区中。存储区存储事件实例是事件实例匹配的基础。本章先介绍alpha 结点存储区和beta 结点存储区的构成，在此基础上介绍模式匹配。
在alpha 结点的模式匹配是单一模式匹配，在beta 结点中的模式匹配是复合模式匹配，两者都是以鉴别网络为基础。因为模式匹配是规则匹配的最小单位，所以本章重点介绍模式匹配，当一次模式匹配成功后，进行下一次模式匹配时，存在对事件实例的传播，因此本章在最后阐述了事件实例在beta 结点中的传播方式。
本文改进了RETE 算法对beta 结点的右侧存储区的设计，提出了一种基于插槽位置的索引生成方法来存储事件实例。在beta 结点进行左侧匹配时，采用事件实例查找方法找到事件实例集中的事件实例并生成索引，利用索引进行查找匹配的事件实例，提高了对具有变量绑定类型模式的匹配效率。
5.1 alpha 结点的存储区的设计
具有存储区的alpha 结点有两种类型：事件类型结点和Alpha 结点，其存储区结构如图33所示。
图33 Alpha 结点的存储区表示
每个Alpha 结点（除去左侧输入适配结点）都有存储区与之对应，存储区内保存了通过该结点并且匹配成功的事件实例。例如：满足约束e1-attr0(eventOne i ) =" ok " 的事件实例eventOne i 发生时，进入事件类型结点Node2和规定了字面量约束的Alpha 结点
Node6。事件实例eventOne i 被存储在相应的存储区，如图33所示。
50
北京航空航天大学硕士学位论文
5.2 beta 结点的存储区的设计
与beta 结点左侧输入相连的是左侧输入适配结点或beta 结点，这两个结点的输出都是多个事件实例，因此beta 结点的左侧输入是多个事件实例；与beta 结点右侧输入相连的是事件类型结点或者Alpha 结点，这两个结点的输出是单个事件实例，因此beta 结点的右侧输入是单个事件实例。
5.2.1 事件实例集
将beta 结点的左侧输入的多个事件实例称之为事件实例集（简称Index ）。例如：拥其中A 在Index 的0位置上，B 在Index 有事件实例A 和B 的Index 可以记为Index[A,B]，
的1位置上。事件实例集是基于插槽位置的事件查找方法的基础，本小节主要讲述了事件实例集的建立。
Index 是包含有事件实例的数组。当单个事件实例从左侧输入适配结点或者事件实例集从beta 结点向下一个beta 结点传播时，都会建立新的Index ，并将已有的事件实例按照先后顺序加入到该新建的Index 当中，并向下个结点传播。
例如：joinNode1，joinNode2，joinNode3，如图34所示。当事件实例A 通过左侧输入适配结点进入joinNode1时，先建立Index[A]，然后传播Index[A]到joinNode1的左侧输入。当joinNode1的右侧输入的事件实例B 加入到joinNode1时，如果满足传播条件，则以前建立的Index[A]封装事件实例B 形成Index[A,B]，并传播Index[A,B]到joinNode2的左侧输入，然后继续匹配并且填充Index 。
图34 事件实例集的生成图
对于路径CEn 来说，当n=0时，事件实例从左侧输入适配结点进入joinNode ，并添加到Index 的最后一个位置；当n>0时，事件实例从右侧输入进joinNode 时，都会添加到Index 的最后一个位置。
51
第五章 模式匹配的设计
因此得到如下结论：如果事件实例满足CEn ，则会存储在Index 中的位置n 上，即
CE 在规则中的位置等于满足该CE 的事件实例存储在Index 中的位置。 5.2.2 Beta 结点的左侧存储区
为了保存从beta 结点左侧进入的事件实例集，需要设置beta 结点的左侧存储区，对于具有不同约束类型的beta 结点，左侧存储区的类型是不同的，如表13所示。
表13 beta 结点的左侧存储区和存储区索引
约束类型 具有谓词函数约束 具有否定的变量绑定约束具有肯定的变量绑定约束
左侧存储区 匹配存储区 普通存储区 普通存储区
存储区索引Index 无 无
普通存储区和alpha 结点的存储区类似，如图33所示。不同的是前者存储的是事件实例集，而后者存储的是事件实例。
具有谓词函数约束的beta 结点在进行模式匹配时，因为谓词函数约束的匹配不是看两个变量是否相等，而是需要函数的运算，所以不能利用基于插槽位置的索引生成方法来生成索引进行模式匹配。所以将谓词函数约束的右侧存储区设置为普通存储区。
因为Exist CE和Not CE需要对部分匹配事件实例进行计数，来决定是否向下传播。而右侧存储区是普通存储区，不能用来存储匹配的事件实例，所以将左侧存储区设计成匹配存储区。该存储区的索引是从左侧进入的Index ，值是和该Index 相匹配的所有右侧输入进来的事件实例，如图35所示。
图35 beta 结点的左侧存储区
5.2.3 Beta 结点的右侧存储区
为了保存从beta 结点右侧进入的事件实例，需要设置beta 结点的右侧存储区，对于具有不同约束类型的beta 结点，右侧存储区的类型也是不同的，如表14所示。
52
北京航空航天大学硕士学位论文
表14 Beta 结点的右侧存储区和存储区索引 约束类型 具有谓词函数约束 具有否定的变量绑定约束具有肯定的变量绑定约束
右侧存储区普通存储区二级hash 一级hash
存储区索引
无
一级索引：NotEqlHashIndex 二级索引：EqHashIndex
EqHashIndex
普通存储区和alpha 结点的存储区类似，如图33所示，存储事件实例。
对于具有变量绑定约束的beta 结点的alpha 存储区是通过一级hash 存储区和二级
hash 存储区来实现的。当事件实例从右侧进入到具有变量绑定约束的beta 结点时，将该事件实例中的用于参与模式匹配的变量值做成hash 索引，存入存储区。下面从两方面介绍肯定和否定的变量绑定约束的存储区及存储区索引。
5.2.4 具有变量绑定约束的Beta 结点的右侧存储区索引
当事件实例从右侧进入到具有变量绑定约束的beta 结点时，由于采用的存储区不同，存储方式也不同，对于事件实例的存储过程如下：
(1) 取出该joinNode 对应的右侧存储区，如果没有则建立结点的存储区； (2) 根据joinNode 的bind 变量列表，建立与事件实例相对应的索引； (3) 将索引和事件实例加入到该joinNode 的右侧存储区。
具有肯定变量约束的beta 结点和具有否定变量约束的beta 结点对于事件实例的存储过程基本相同，都是建立索引，将索引和事件实例加入到存储区。索引实质上是事件实例某些属性值的hashCode ，joinNode 的bind 变量列表指定了这些属性的插槽位置。而两种结点存储事件实例过程的不同之处在于生成索引的方法，因此下面分两部分设计基于插槽位置的索引生成方法。
1. 具有肯定变量绑定约束的Beta 结点的右侧存储区索引
该索引的形式为EqHashIndex，其中hashCode 是该索引的值，算法详细描述如下：
算法名称：建立EqHashIndex 索引
输入：被绑定变量列表binds ，事件实例event 。 输出：EqHashIndex 索引 1) 创建对象数组。
2) 取出binds 的bind 变量，由bind 的rightIndex 获得事件实例event 在插槽位置
rightIndex 上的属性值，加入对象数组。若binds 中包含其他变量，跳到2步；否则转向3步。
3) 建立EqHashIndex索引。
53
第五章 模式匹配的设计
图36是对于规则event-correlation-rule2(见附录) ，在joinNode 结点右侧存储区存储事件实例eventTwo j 时，根据插槽位置0和2得到的属性值生成的索引eqHashIndex1。
图36 event-correlation-rule2的CE2对应的joinNode 的左右存储区
2. 具有否定变量绑定约束的Beta 结点的右侧存储区索引
该索引的形式为NotEqHashIndex，其中的EqHashIndex 是二级索引。BindValue是由事件实例的属性形成的二元组，value 指定了该属性值，negated 指定了该属性值在bind 变量列表中是否满足否定的变量绑定约束。
算法名称：建立NotEqHashIndex 索引
输入：被绑定变量列表binds ，事件实例event 。 输出：NotEqHashIndex 索引 1) 创建bindValue 数组。
2) 取出binds 的bind 变量，由bind 的rightIndex 获得事件实例event 属性的插槽
位置rightIndex
3) 获得事件实例在该位置上的bindValue值，加入到bindValue 数
组。若binds 中包含其他变量，跳到2步；否则转向4步。
4) 建立二级索引EqHashIndex ，计算否定的bindValue(即negated=true)的值，将所
有获得的属性值的hashCode 相加，做为索引EqHashIndex 的hashCode 。
5) 建立一级索引NotEqHashIndex ，计算肯定的bindValue(即negated=false)的值，
将所获得的属性值的hashCode 相加，做为一级索引NotEqHashIndex 的hashCode ，并将二级索引附着在一级索引上。 6) 返回NotEqHashIndex 索引。
图37是对于规则event-correlation-rule3(见附录) ，在joinNode 结点右侧存储区存储事件实例eventTwo j 时，根据插槽位置0和2得到的bindValue 值生成的一级索引
NotEqHashIndex1和二级索引eqHashIndex1。
54
北京航空航天大学硕士学位论文
图37 event-correlation-rule3的CE3对应的joinNode 的左右存储区
5.3 alpha 结点的模式匹配的设计
alpha 结点的模式匹配过程如下：
来获得事件实例在该插槽位置上的属性值； (1) 根据Alpha 结点中属性插槽位置ID ，
(2) 对Alpha 结点中的属性插槽值和事件实例的在插槽位置上的属性值进行匹配； (3) 若匹配成功，将事件实例存储在结点的存储区，然后直接传播该事件实例到下
一个结点；否则放弃该事件实例。
如图32所示，Node6的插槽ID 是0，插槽值是”ok”。事件实例eventOne i 在经过Node6时，获得事件实例 eventOne i 在插槽位置0上的属性值，如表16所示，即”ok”，然后对两者进行匹配，匹配成功，则传递到结点Node7。
事件类型结点做为特殊的Alpha 结点，在匹配时将插槽位置和插槽值改为类型信息，匹配过程与上述过程相似。
左侧输入适配结点只存在于CE0中。该结点不对事件实例进行匹配，仅对单个事件实例形成Index ，向下个beta 结点传播该Index 。
5.4 Beta 结点的模式匹配的设计
因为beta 结点是用于关联两个CE 的结点，因此进行模式匹配时必须等到两个或者两个以上的事件实例到达该结点，所以在进行模式匹配前，先对事件实例进行存储。然后等待其他事件实例的到来再进行匹配。beta 结点的模式匹配和传播方式程序流程如图38所示。
55
第五章 模式匹配的设计
图38 beta 结点模式匹配和传播方式流程图
为了方便阐述，将定义左侧匹配和右侧匹配的概念。
左侧匹配：事件实例集从左侧进入beta 结点，查找结点的右侧存储区，看是否存在和该事件实例集匹配的事件实例。
右侧匹配：事件实例从右侧进入beta 结点，查找结点的左侧存储区，看是否存在和该事件实例匹配的事件实例集。
无论是左侧匹配还是右侧匹配，从事件实例集中找到需要匹配的事件实例及其属性值是进行模式匹配的前提。本文采用一种基于插槽位置的事件实例查找方法从事件实例集中找到这些参与模式匹配的事件实例。
5.4.1 基于插槽位置的事件实例查找方法
插槽是事件定义中所规定的属性位置。该方法的主要目的就是找到Index 中所包含的用于参与模式匹配的事件实例。例如图32所示的鉴别网络，在eventTwo j 发生后传递到
Node8，查看左侧存储区中的所有事件实例集，从每个事件实例集中找到事件实例eventOne i ；在eventOne i 发生后，传递到Node8后，从左侧输入的事件实例集中找到eventOne i 用于和右侧存储区的eventTwo j 进行匹配。因此从事件实例集中找到eventOne i 就是该方法的应用。
因为CE 在规则中的位置等于满足该CE 的事件实例存储在Index 中的位置，而且
56
北京航空航天大学硕士学位论文
bind 变量列表的rowId 指明了被绑定元素的所在CE 的位置。所以有如下结论：
通过beta 结点bind 变量的rowId 可以找到被绑定元素所在的CE 的位置，而传递到该beta 结点左侧输入的Index 在该位置上的事件实例，就是需要进行模式匹配的事件实例。
为了证实该结论，将部分鉴别网络进行描述，如图39和图40所示。进入第i 个CE 对应的joinNode 的事件实例是eventi ，每一个joinNode 的左侧输入是Index 。本节分析了怎样在第n 个joinNode 中，根据该结点的bind 变量列表在Index 中找到合适的事件实例。
在图40中的第n 个joinNode 的第一个bind 变量rowId=k，即绑定变量在第k 个CE 上。若事件实例eventk 在通过第k 个CE 与第k-1个CE 的joinNode 时成功匹配，则eventk 被封装在了Index 的第k 个位置上。
因此可以在Index 中找到满足第k 个CE 与第k-1个CE 的joinNode 规定的关联条件的事件实例eventk ，也就是找到了在第n 个joinNode 中进行事件关联的事件实例
eventk 。
同理，通过bind 变量列表的第二个元素的rowId ，可以在Index 中找到eventj 。eventk 和eventj 同右侧的输入eventn 进行模式匹配。
模式匹配用来判断事件实例的属性是否满足模式所规定的约束信息，因此在找到参与模式匹配的事件实例后，需要进一步找到事件实例中的属性值。
图39 Beta 网络部分结点图（1）
57
第五章 模式匹配的设计
图40 Beta 网络部分结点图（2）
通过rowId 找到了用于模式匹配的事件实例在Index 中的位置，而leftIndex 和
rightIndex 指明了事件实例的属性插槽的位置，即eventk 的插槽m 上的属性值和eventn 的插槽n 上的属性值相对应，在模式匹配过程中，要判断出这两个值是否满足约束条件。同理，也需要判断eventj 的插槽o 上的属性值和eventn 的插槽p 上的属性值是否满足约束条件。
5.4.2 Beta 结点的模式匹配
在事件实例传播到joinNode 结点时，结点所对应的约束类型决定了模式匹配的实现方式，如表15所示。结点所对应的CE 类型决定了结点的传播方式。
表15 具有不同约束类型的beta 结点的左右匹配方式
约束类型 具有谓词函数约束 具有否定的变量绑定约束 具有肯定的变量绑定约束
左侧匹配 Bind 方式Hash 方式Hash 方式
右侧匹配Bind 方式Bind 方式Bind 方式
beta 结点的模式匹配按事件实例的来源分为左侧匹配和右侧匹配，按实现方式，分为Bind 方式和Hash 方式。这两种方式都是以基于插槽位置的事件实例查找方法为基础。
1. Bind 方式
58
北京航空航天大学硕士学位论文
若Index 从左侧输入，匹配过程如下：
(1) 通过基于插槽位置的事件实例查找方法，找到Index 中的事件实例及其属性值；
(2) 遍历右侧存储区内每一个事件实例，判断该事件实例的属性值是否和(1)的属性
值匹配。
若右侧存储区没有这样的事件实例，则匹配失败，不进行下一个模式匹配；否则进行下一个模式匹配。
若事件实例从右侧输入，匹配过程如下：
(1) 遍历左侧存储区内每一个事件实例集Index ；
(2) 通过基于插槽位置的事件实例查找方法，找到Index 中的事件实例及其属性值；
(3) 判断属性值是否和事件实例的属性值相匹配。
若左侧存储区没有这样的事件实例集，则匹配失败，不进行下一个模式匹配；否则进行下一个模式匹配。
2. Hash 方式
当Index 从左侧进入具有变量绑定约束的beta 结点时，利用该匹配方式来判断右侧存储区内是否存在满足约束的事件实例，匹配过程如下：
(1) 通过基于插槽位置的事件实例查找方法，查找到Index 中的事件实例；
(2) 利用基于插槽位置的索引生成方法，将这些事件实例的属性值转换为索引；
(3) 利用索引查找右侧存储区，看是否有相应的事件实例相匹配。
若查找到有相应的事件实例，则表明查到的事件实例和左侧的Index 模式匹配成功。
5.4.3 事件实例在beta 结点的模式匹配过程
假设鉴别网络是由规则event-correlation-rule 所生成，如图32所示。进入该鉴别网络的事件实例分别是eventOne i 和eventTwo j ，如表16所示。本节阐述了事件实例eventOne i 和eventTwo j 先后到达结点Node8时，在其中的模式匹配过程。
表16 事件实例表 事件实例eventOne i e1-attr0=”ok”e1-attr1=100e1-attr2=0e1-attr3=0
eventTwo j e2-attr0=”100”e2-attr1=300e2-attr2=20-------------
1. eventOne i 从左侧进入joinNode
59
第五章 模式匹配的设计
eventOne i 由CE0路径进入到Node8。由左侧输入进入到Node8之前，先通过左侧输入适配结点Node7进行适配，形成事件实例集Index1[eventOne i ]。
事件实例集Index1从左侧进入Node8后，被存储在Node8的左侧存储区。遍历右侧存储区，发现没有相匹配的事件实例，则等待右侧输入事件实例eventTwo j 的到来。此时Node8的左侧存储区如图35所示。
因为Node8是具有谓词函数约束的joinNode 。由表13可知该结点的左侧存储区是匹配存储区。其中哈希表的值指向了事件匹配列表，该列表中保存了和该事件eventOne i 匹配的事件实例；哈希表的关键字是Index1[eventOne i ]。
2. eventTwo j 从右侧进入joinNode
事件实例eventTwo j 发生后，从CE2路径传播到Node8的右侧输入，存储到Node8的右侧存储区。由表14可知该结点的右侧存储区是普通存储区，物理结构与图33相似。
3. eventOne i 和eventTwo j 在joinNode 的模式匹配
eventTwo j 存储到Node8后，利用Bind 方式进行模式匹配：遍历左侧存储区内的Index ，对每一个Index 用事件实例查找方法，看该Index 是否匹配eventTwo j ，如图41所示。
当遍历到Index1时，基于插槽位置的事件实例查找方法根据bind 变量列表来取出Index1中的将要参与模式匹配的事件实例。
表明被绑定变量在CE0中。同时指定了Index Node8中的两个bind 变量的rowId=0，
中的第0个位置的事件实例就是来自于CE0的事件实例，该事件实例是含有被绑定变量值的事件实例。此时Index 的第0个位置的事件实例是eventOne i 。
60
北京航空航天大学硕士学位论文
图41 joinNode的左右存储区
Node8中的第一个bind 变量leftIndex=1，表明被绑定变量值是事件实例eventOne i 的属性在插槽位置1上的属性值e 1−attr 1(eventOne i ) 。rightIndex=0表明绑定变量值是事件实例eventTwo j 的属性在插槽位置0上的属性值e 2−attr 0(eventTwo j ) 。
Node8的第一个bind 变量指明了该结点包含肯定的变量绑定约束e 1−attr 1(eventOne ) =e 2−attr 0(eventTwo ) ，判断得到的属性值e 1−attr 1(eventOne i ) 和e 2−attr 0(eventTwo j ) 是否相等，即是否满足该变量绑定约束。
但是该结点还含有谓词函数约束e 1−attr 2(eventOne i )
在本例中，由表16可知，事件实例eventOne i 和eventTwo j 满足上述约束。但是Node8是NotJoin 类型的JoinNode ，所以将eventTwo j 保存在左侧存储区的事件匹配列表中，并向下一个结点传播retract 动作，移除后继结点对左侧输入Index 的存储。
5.4.4 joinNode 结点中的事件传播方式
当左侧输入的Index 和右侧输入的事件实例满足事件关联的条件时，将传播Index 。根据不同类型的CE 对应的joinNode ，对事件实例有着不同的传播方式，如表17所示。
61
第五章 模式匹配的设计
表17 鉴别网络中事件实例的传播方式 CE 类型 动作
Assertleft
assert 该Index 。
若右侧存储区中的事件实例数由0个增加到1个且在左侧存储区
AssertRight
Not CE
retractLeft
retractRight
内有和该事件实例匹配的Index ，则向后续结点assert 该Index 。
若右侧存储区中与Index 匹配的事件实例数大于0，向后续结点
Assertleft
assert 该Index 。
若右侧存储区中的事件实例数由0个增加到1个且在左侧存储区
AssertRight
Exist CE
retractLeft
retractRight
内有和该事件实例匹配的Index ，则向后续结点retract 该Index 。
若右侧存储区中有与Index 匹配的事件实例，将该事件实例与该
Assertleft
Index 并形成新Index ，向后续结点assert 新Index 。
若左侧存储区内有和该事件实例匹配的Index ，将该事件实例与
AssertRight
该Index 合并形成新Index ，向后续结点assert 新Index 。
Object CE
若右侧存储区内有和该Index 匹配的事件实例，将该事件实例与
retractLeft
该Index 并成新Index ，向后续结点retract 新Index 。
若左侧存储区内有和该事件实例匹配的Index ，将该事件实例与
retractRight
该Index 并成新Index ，向后续结点retract 新Index 。 内有和该事件实例匹配的Index ，则向后续结点assert 该Index 。 直接向后续结点retract 该Index 。 若右侧存储区中的事件实例数由1个减少到0个且在左侧存储区内有和该事件实例匹配的Index ，则向后续结点retract 该Index 。 直接向后续结点retract 事件实例集。 若右侧存储区中的事件实例数由1个减少到0个且在左侧存储区解释 若右侧存储区中与Index 匹配的事件实例数为0，向后续结点
例如：规则event-correlation-rule 中CE2：(exists (EventThree (e3-attr0 ~?var1)))，如果Index 从左侧进入，查找右侧存储区相匹配的事件实例，若存在满足约束的事件实例则向后继结点传播该Index 。因为exists 不能定义被绑定变量，所以并不把右侧输入的事件实例加入到Index ；若事件实例从右侧进入，此时右侧存储区第一次存在和左侧存储区的某个Index 相匹配的事件实例，则传播该Index ，若在此之前右侧存储区已存在和左侧存储区的某个Index 相匹配的事件实例，则不进行传播，因为在此之前已经传播
62
北京航空航天大学硕士学位论文
了该Index 到下一结点。
retract 动作是将事件实例从存储区中移除的过程。例如Not CE，满足该CE 的事件实例从右侧输入时，该实例第一次进入beta 结点和左侧存储区的某个Index 相匹配，而在此之前，该Index 必定传播到了下一个joinNode ，此时该事件实例发生，意味着不满足该Not CE，需要从后继结点中移除本结点生成的部分匹配，因此传播retract 动作，移除后继结点对左侧输入Index 的存储。
CE 的类型决定了事件实例在模式匹配后的传播方式，表17详细描述了不同类型的CE 在执行模式匹配的assertLeft ，assertRight ，retractLeft 和retractRight 四个动作后，对匹配的事件实例集的传播。
5.5 规则激发和故障定位
当事件实例或者Index 能够传播到终结点时，说明有满足规则的事件实例的发生，因此会激发该规则，执行规则的右部动作，产生故障定位信息。
在产生故障定位信息的同时，满足规则的事件实例或Index 已存在于鉴别网络的存储区中。如果事件实例或Index 不用于今后的事件关联，则可以从鉴别网络中移除，当相同的事件实例再次发生时，重新进行关联，然后产生新的故障定位信息。
5.6 本章总结
本章首先介绍了事件实例集的概念，它是基于插槽位置的事件实例查找方法的基础。然后根据具有不同约束类型的beta 结点介绍了结点的左侧和右侧存储区的设计，对变量绑定类型的右侧存储区进行了详细阐述。
然后以鉴别网络和存储区为基础，介绍了alpha 结点和beta 结点的模式匹配、事件实例的传播和规则激发。
63
北京航空航天大学硕士学位论文
第四章 鉴别网络的设计
鉴别网络（discrimination network）是RETE 算法的基础。本章将从设计的具体细节着手，在介绍鉴别网络的基本结构后，阐述alpha 和beta 网络生成算法的设计。最后通过实例给出了利用所设计的算法，由规则对象建立鉴别网络的过程。
4.1 鉴别网络的结构
鉴别网络是因规则的不断加入而形成的，是与加入的规则相对应的对象网络。在系统中只有一个鉴别网络存在，鉴别网络中包含有多个已定义规则。鉴别网络分为两部分：alpha 网络和beta 网络，如图10所示。
图10 鉴别网络结构图
规则在鉴别网络中表现为从根结点到终结点的一条路径。在该网络中，包含两条规则joinConversion1和joinConversion2，规则joinConversion1和joinConversion2在鉴别网络中表示的路径如图11所示。
3
254
7
0253
811
joinConversion1joinConversion2
图11 规则joinConversion1与规则joinConversion2的结点路径图
在alpha 网络中，每一个结点代表了规则的一个模式（除去左侧输入适配结点），在alpha 网络中的模式匹配都是单个事件实例的模式匹配。在beta 网络中的每一个结点代表了规则的一个模式，在beta 网络中的模式匹配都是多个事件实例的模式匹配，每个结点都是执行事件关联的结点。根结点是事件实例的输入结点，终结点规定了规则的右部
29
第四章 鉴别网络的设计
动作。
在鉴别网络中，CE 表示一条路径，从alpha 网络的第一个结点开始，到beta 网络的第一个结点结束。例如规则joinConversion1的CE0表示路径2，5，6；CE1表示路径3，4，6；规则joinConversion2(见附录) 的CE0表示路径2，5，10；CE1表示路径3，8，10。CE0是特殊的CE ，即规则的第0个CE ，只有CE0才能包含左侧输入适配结点。
在进行规则匹配时，事件实例从根节点进入鉴别网络并从根结点到终结点进行模式匹配。当事件实例经过的每一个结点都能够完成模式的成功匹配，则表示规则匹配的成功，则执行终结点所对应的规则右部动作。
4.2 基本元素定义
结点是鉴别网络中基本的元素，在本节中分别介绍了结点类型、图示、结点间关系和结点的存储区。
4.2.1 结点类型与模式
模式分为单一模式和复合模式。每一个alpha 结点（除去左侧输入适配结点）都有单一模式与之对应。Beta 结点中含有复合模式，是用于事件关联的结点类型。下面对各种类型的结点进行具体分析。
根结点：当规则加入到鉴别网络或者模式匹配开始时，都是从根结点开始的。
终结点：当事件实例匹配到终结点时，激发规则的右部动作，产生可能的故障假设。该结点没有相应的存储区与之对应。
alpha 网络中的结点称为alpha 结点，alpha 结点有三种类型：事件类型结点、Alpha 结点和左侧输入适配结点。
事件类型结点：保存了事件类型约束信息。例如规则joinConversion1的CE0所指定的事件类型约束EventOne ，该结点保存了事件类型约束信息EventOne 。
Alpha 结点：保存了字面量约束信息。例如规则joinConversion1的CE1所指定的字面量约束(shortAttr 100)，该结点保存了该字面量约束信息。
左侧输入适配结点：其输出指向Beta 结点的左侧输入。该结点是CE0路径的尾结点。该结点不存储事件信息，仅对Beta 结点的左侧输入进行适配。
，该结点保存了复合beta 网络中的结点称为Beta 结点（也称joinNode 和关联结点）
模式，即规定了规则中的事件关联条件。在规则的左部中，如果两个CE 有相互关系，
30
北京航空航天大学硕士学位论文
规则加入到鉴别网络时会生成Beta 结点，例如规则find_unaccessable_host指定的CE0中的变量dest_variable和CE1中的变量dest_variable是同一变量，表明这两个CE 规定的关联关系为“目标IP 相同”。而否定变量source_variable规定CE0与CE1之间的关联关系为“源IP 不相同”。
4.2.2 基本结点图示
为了表述方便，将各个结点的图示做如下规定，如图12所示。
图12 鉴别网络基本结点图示
4.2.3 结点间的关系限定
鉴别网络是一个有向无环图。因为各个结点的作用不同，结点之间的相互关系也不相同，RETE 算法对鉴别网络结点的关系做了如下规定：
(1) 根结点的入度为0，Beta 结点的入度是2，其他结点的入度均为1；
(2) 终结点的出度为0，其他结点的出度均大于0；
(3) 根结点的后继结点类型只能是事件类型结点；
(4) 事件类型结点的后继结点类型可以是左侧输入适配结点、终结点、Beta 结点、
或Alpha 结点；
(5) 左侧输入适配结点的后继结点类型是Beta 结点；
(6) Beta 结点的左侧输入结点类型只能是左侧输入适配结点或Beta 结点；
(7) Beta 结点的右侧输入结点类型只能是事件类型结点或Alpha 结点；
(8) Beta 结点的后继结点类型可以是终结点或Beta 结点；
终结点，Beta 结点或Alpha (9) Alpha 结点的后继结点类型可以是左侧输入适配结点，
结点。
4.2.4 结点与存储区的关系
为了使得部分匹配结果能够用于下次的再次匹配，提高retract 动作的执行效率，结点需要存储区来存储匹配结果，因此凡是具有模式约束的结点都有存储区。存储区分为
31
第四章 鉴别网络的设计
两种类型：alpha 存储区和beta 存储区。存储区和结点的关系如下：
(1) 根结点，左侧输入适配结点和终结点没有存储区，因为这些结点没有模式信息。
(2) 事件类型结点、Alpha 结点有alpha 存储区，前者具有事件类型的约束，后者具
有字面量约束。
一个是左侧存储区，另一个是右侧存储区。前者是beta (3) Beta 结点有两个存储区，
存储区，后者是alpha 存储区。Beta 结点具有复合模式。
4.3 规则加入到鉴别网络的过程
本节给出了一个由规则生成鉴别网络的例子，将规则joinConversion1做为第一条规则，加入到鉴别网络，继续添加规则joinConversion2(见附录) 到鉴别网络，两个规则加入到鉴别网络的过程如图13所示。
EventTwo EventOne
加入:j o
joinConversion1joinConversion2
图13 鉴别网络生成图
最终形成的鉴别网络中，joinConversion1的CE0代表该规则的第0个条件元素(EventOne (intAttr ?intA))，joinConversion1的CE1代表该规则的第1个条件元素(EventTwo(strAttr ?intA)(shortAttr 100))。将规则joinConversion2加入到鉴别网络后，和
32
北京航空航天大学硕士学位论文
规则JoinConversion1共享其中的某些结点产生新的路径：JoinConversion2的CE0代表该规则的第0个条件元素(EventOne (intAttr ?intA))；joinConversion2的CE1代表该规则的第1个条件元素(EventTwo(strAttr ~?intA)(shortAttr 101)。
4.4 规则对象的设计
对象是面向对象编程的术语，是类的实例。生成鉴别网络的前提是CLIPS 语言所指定的规则在词法分析和语法分析之后，形成了和规则对应的规则对象。本节对规则对象及其依赖的数据进行表示，以便于阐述鉴别网络生成算法的设计。
在生成鉴别网络时，一方面生成内存中的对象网络，另一方面将对规则对象的binds 和joins 属性以及condition 的nodes 、hasNotEqual 和hasPredicate 属性进行填充。
4.4.1 规则对象
为了阐述鉴别网络算法的设计，将规则对象中的关键成员变量抽取出来，用五元组表示为Rule=，对规则对象的属性规定如表1所示。
表1 规则对象属性表 name
conditions
binds
joins
actions 规则的名字 规则所包含的所有CE 列表 规则的所有被绑定变量 与该规则对应的所有Beta 结点 规则的右部动作
4.4.2 条件元素
对于规则对象中的每一个CE ，用condition 来表示。CE 有三种类型：ObjectCE 和ExistsCE 和Not CE。对这三种类型的CE 规定如下：
Object CE是一个六元组Object CE=，Exist CE是一个二元组Exist CE=。其中Not CE是negated=true的Object CE。在建立鉴别网络时，只处理Object CE和Exist CE两种情况，对于Not CE做为Object CE的一种特殊情况来处理。对Object CE属性的规定如表2所示。
表2 Object CE的属性表
template 该CE 对应的事件类型约束
33
第四章 鉴别网络的设计
约束信息
constraints
(字面量约束、变量绑定约束、谓词函数约束)
nodes
negated
hasNotEqual
hasPredicate 与该CE 所对应的alpha 结点和beta 结点 该CE 是否是Not CE 该CE 是否具有否定的变量绑定约束 该CE 是否具有谓词函数约束
4.4.3 变量
通过变量可以建立两个CE 间的联系，只有两个CE 存在联系，才能够进行多个事件实例的模式匹配。因此变量是进行事件关联的基础，是Beta 结点binds 列表中的元素。变量用六元组表示如下：bind=。对bind 的属性规定如表3所示。
表3 变量的属性
varName
rowId
leftIndex
rightIndex
negated
isPredJoin 变量绑定或者谓词函数变量的名字 被绑定变量所在的行号 被绑定变量所在的列号 绑定变量所在的列号 是否为否定的变量绑定 是否为谓词函数约束
变量分为绑定变量和被绑定变量。变量的第一次出现称为被绑定变量；变量的第n 次(n>1)出现称为绑定变量。被绑定变量只是对变量的定义，因此无论是肯定变量约束、否定变量约束还是谓词函数约束，被绑定变量的属性negated 和属性isPredJoin 值为空。rightIndex 指定了绑定变量所在列号，因此在被绑定变量中也为空。绑定变量的属性值都不为空。
4.5 alpha 网络生成算法的设计
规则对象加入到鉴别网络之前，首先是对规则所依赖的事件类型进行定义，该定义生成了鉴别网络中的事件类型结点。针对于规则中的每一个CE ，利用alpha 网络生成算法建立相应的alpha 网络，算法总体流程图如图14所示。alpha 网络生成算法总体流程图中，处于核心位置的是“建立alpha 网络”算法，其中包含对规则对象binds 属性的填充。
34
北京航空航天大学硕士学位论文
图14 alpha 网络生成算法总体流程图
Not CE做为Object CE的一种特殊类型，因此不对Not CE单独处理。该算法对于Exist CE到鉴别网络的转换，是取出该CE 中的Object CE，然后建立Object CE对应的alpha 网络。从Object CE建立alpha 网络是从Exist CE建立alpha 网络的子过程。
4.5.1 建立alpha 网络算法的设计
建立alpha 网络算法的流程图如图15所示。该算法主要完成两方面的工作：
建立alpha 结点串（如果鉴别网络中有相同模式的结点，(1) 对于字面量约束的模式，
则共享结点），并加入到condition 的nodes 列表中。
(2) 对于第一次出现的变量绑定约束或谓词函数约束，建立bind 变量并填充到规则
对象的binds 属性。
如果是从空的鉴别网络中加入规则，则不需考虑与已有规则的alpha 结点进行结点共享。如果鉴别网络中存在先前加入的规则，则需要考虑现有规则的加入与先前规则所对应网络中的结点的共享问题。对于alpha 结点的共享算法，在4.5.2节中进行详细阐述。
35
第四章 鉴别网络的设计
图15 建立alpha 网络程序流程图
算法的详细描述如下： 算法名称：建立alpha 网络
输入：条件元素condition ，条件元素位置position ，规则对象rule
输出：无
1) 获得condition 的事件类型约束template 。
2) 建立空的结点串nodesList 。
3) 获得condition 的下一个约束信息constraint 。若constraint 不是字面量约束，则
跳至6步。
4) 建立alpha 结点。
5) 将alpha 结点加入到nodesList 的最后一个位置，跳至7步。
6) 若constraint 是变量绑定约束或谓词函数约束且是第一次出现，则以constraint 、
template 和position 为参数调用“生成被绑定变量”算法得到bind ，将bind 填充
至规则对象的binds 属性。
7) 若存在下一个约束信息constraint ，则跳至3步。
8) 将nodesList 、template 和condition 做为参数，调用“共享alpha 网络”算法。 算法名称：生成被绑定变量
输入：约束信息constraint ，事件类型template 和约束所在CE 位置position
输出：被绑定变量bind
1) 建立bind 。
36
北京航空航天大学硕士学位论文
2) 将constraint 的变量名赋值给bind 的varName 。
3) 将position 赋值给bind 的leftRow 。
4) 通过constraint 对应的属性名，在template 中得到该约束所在的事件类型的插槽
位置并赋值给leftIndex 。
5) 返回该bind 元素。
在算法“建立alpha 网络”中，根据ObjectCE=中不同的constraint ，有着不同的处理：对于字面量约束建立Alpha 结点；而对于变量绑定约束和谓词函数约束的第一次出现只建立bind ，并加入到该ObjectCE 所在的Rule 的binds 属性，而不生成Alpha 结点。
在该规则加入到鉴别网络之前，网络中可能含有与新建立的结点串模式相同的结点，即有相同的字面量约束，因此需要对已存在结点进行共享。这样有利于节省内存，提高模式匹配效率。
4.5.2 alpha 网络中结点的共享
在建立新结点串时，“共享alpha 网络”算法用于和原鉴别网络进行Alpha 结点共享。算法的详细描述如下： 算法名称：共享alpha 网络
输入：已有结点existing ，新结点串alpha ，条件元素condition
输出：无
1) 若alpha 为空串，则结束。
2) 将existing 和alpha 做为参数，调用“获得共享结点”算法，得到共享结点share 。
若share 不为空，则跳至5步。
3) 将alpha 结点串的第一个结点做为existing 的后继结点。
4) 将alpha 结点串中的每一个结点取出，加入到condition 的nodes 列表；结束。 5) 将共享结点share 加入condition 的nodes 属性。
6) 获得alpha 结点串的下一个结点alphaSuc 。将共享结点share 、alphaSuc 和条件
元素condition 做为参数，递归调用“共享alpha 网络”算法。
算法名称：获得共享结点
输入：已存在的结点existing ，新结点串alpha
输出：共享结点share
1) 取出existing 的后继结点share ，若该结点和alpha 的第一个结点具有相同的字
面量约束，返回share 。
2) 如果existing 有其他的后继结点，则转向1步，否则返回空。
例如鉴别网络中已存在的规则有rule1和rule2，如图16所示。
37
第四章 鉴别网络的设计
EventOne e1-attr0=rule1rule2 图16 已有的鉴别网络
若再添加规则(defrule rule3 (EventOne (e1-attr0 "ok") (e1-attr1 200) )=>……)
，则通过该算法，将新建立的
alpha
结点串（如
图
17
所示）和现有的鉴别网络（如
图16）合并，共享现有结点
2，4，生成最终的规则网络，如图18所示。
图17 新规则所形成的alpha
结点路径
图18 新规则加入鉴别网络后，共享结点2，4形成的鉴别网络
下面根据此实例，在加入新规则时和已有的规则共享结点的过程对对“共享alpha 网络”算法进行详细阐述，即由图16转变成图18的过程。
在调用“共享alpha 网络”算法之前，对于Object CE的字面量约束建立了结点串。condition 的template 对应的事件类型结点做为算法的第一个参数existing ，alpha 指向该结点串的第一个结点并做为算法的第二个参数，condition 做为算法的第三个参数，传递到该算法。在调用算法前如图19所示。
38
北京航空航天大学硕士学位论文
图19 共享结点形成鉴别网络，调用算法前
首先获得共享的结点4，然后将序号为4的共享结点加入到该ObjectCE 中的nodes 列表，此时condition 中的nodes 列表中的元素为Node4。在递归调用“共享alpha 网络”算法前，所形成的鉴别网络如图20所示。递归执行该算法，将序号为9的非共享结点加入到该ObjectCE 中的nodes 列表，此时condition 中的nodes 列表中的元素为Node4和Node9。再将Node9加入到鉴别网络中，形成的alpha 网络（此时未形成终结点）如图21所示。到此为止，规则rule3加入鉴别网络，共享现有结点2，4。
图
20 共享结点形成鉴别网络，递归调用算法前
图21 共享结点形成鉴别网络，调用算法后
4.6 beta 网络生成算法的设计
Beta 结点是对多个事件实例进行模式匹配的结点。对于不同的事件关联类型，会产 39
第四章 鉴别网络的设计
生不同的Beta 结点。beta 网络生成算法的核心是建立包含有绑定变量列表的beta 结点并连接起来。绑定变量列表是进行事件关联的依据，指明了需要进行关联的事件实例的属性位置。
beta 网络的生成是根据上节所形成的规则中的binds 属性和conditions 属性来进行的，如果规则包含多个CE ，则对CE0建立左侧输入适配结点，对于其他的CE 建立beta 结点。对于仅有一个CE 的规则建立的是特殊的beta 结点：ExistJoinFirst 结点。本节主要阐述为含有多个CE 的规则建立beta 网络的算法。
算法的总体流程图如图22所示。
图22 beta 网络生成算法总体流程图
算法的详细描述如下： 算法名称：建立beta 网络
输入：规则对象rule
输出：无
1) 获得规则对象的条件元素列表conditions ，若条件元素个数等于1，则跳至7。 2) 建立preCondition 、currCondition 、preJoinNode 和curJoinNode ，并赋值为空。 3) 得到条件元素列表的第0个condition （CE0），建立左侧输入适配结点LIANode ，
40
北京航空航天大学硕士学位论文
4)
5)
6)
7) 将该结点做为condition 的nodes 列表的最后一个结点的后继结点；并将LIANode 加入到该condition 的nodes 列表。将该condition 做为preCondition 。 得到条件元素列表的下一个condition ，做为currCondition 。将currCondition 、条件元素位置position 和规则对象做为参数，调用“获得绑定变量列表”算法，得到绑定变量列表binds 。 将currCondition 和绑定变量列表binds 做为参数，调用“建立beta 结点”算法建立joinNode 做为curJoinNode 。 将preCondition ，currCondition ，preJoinNode 和curJoinNode 做为参数传递给“连接beta 结点”算法。若存在下一个condition ，则跳至4步；否则结束。 建立ExistJoinFirst ，加入该结点到rule 的nodes 列表；结束。
该算法的关键主要是第3、4、5、6步，在本节分四部分对这四步进行了阐述。
4.6.1 建立左侧输入适配结点
左侧输入适配结点是属于alpha 网络中的结点，但该结点是在beta 网络生成算法中建立的。在建立beta 网络时，CE0中不存在被绑定对象，因此有必要将CE0建立左侧输入适配结点和其他CE 建立beta 结点的过程分开。该步骤是建立和CE0对应的左侧输入适配结点，并加入到condition 的nodes 列表中。
4.6.2 获得绑定变量列表
在beta 结点中，绑定变量列表中的元素是bind=，每个元素都指定了CE 中用于事件关联的变量，该变量列表是基于插槽位置的事件实例查找方法和索引生成方法的基础。在建立beta 结点前，首先根据规
然后则中的被绑定变量和CE 中的constraint 元素获得与该CE 所对应的绑定变量列表，
将该列表加入到beta 结点中。对于CE 中的每一个复合模式，获得bind 变量的过程如下：
(1) 获得rule 中的被绑定变量。
对于变量绑定类型的约束，由于变量名是相同的，可以通过constraint 包含的变量名找到rule 中的被绑定变量；对于谓词函数约束的constraint 中，包含有变量名和被绑定的变量名，因此也能够找到rule 中的被绑定变量。
(2) 复制被绑定变量属性到绑定变量，生成绑定变量元素，并对CE 的hasNotEqual
和hasPredicate 属性进行初始化。
算法的详细描述如下：
算法名称：获得绑定变量列表
输入：条件元素condition 、条件元素位置position 和规则对象
输出：绑定变量列表binds
1) 从条件元素中获得非第一次出现的constraints 列表。
2) 建立空的绑定变量列表binds ；
41
第四章 鉴别网络的设计
3) 取出constraints 列表的元素constraint ，若该约束为否定约束，则将condition 的
hasNotEqual 属性设置为True ；若该约束为谓词函数约束，则将condition 的
hasPredicate 属性设置为True 。
4) 通过constraint 的名字，取出rule 中的被绑定变量binded ，建立绑定元素bind ，
复制binded 的varName 、leftRow 和leftIndex 属性到bind ；通过constraint 填充
其他的bind 属性。
5) 加入bind 到binds 列表。
6) 若constraints 含有下一个约束，转向3步，否则返回binds 。
4.6.3 建立beta 结点
为了提高模式匹配的效率，对于不同的CEn(n>0)建立不同的beta 结点，condition 中的hasNotEqual 和hasPredicate 属性指定了该CE 是否拥有否定的变量绑定约束和谓词函数约束，根据这两个属性和binds 列表来建立不同类型的beta 结点。
在模式匹配算法中，用于谓词函数约束的模式匹配方法可以用于变量绑定约束，用于否定的变量绑定约束的模式匹配方法可用于肯定的变量绑定约束。变量约束是存在优先级关系的，即谓词函数约束>否定变量约束>肯定变量约束。为了表述方便，做出规定如表4所示。因此说某个CE 具有某个类型的约束，或者某个beta 结点具有某个类型的约束。
根据所包含的约束类型不同和CE 的类型不同，建立的beta 结点也不相同，如表5所示。beta 结点的类型还有用于单个CE 的ExistJoinFirst ，仅表达CE 间“与”关系的ZJBetaNode 。
最后将由上节获得的binds 变量列表加入到生成的beta 结点中。
表4 具有不同约束的CE
约束定义 hasNotEqual hasPredicate
具有谓词函数约束具有否定的变量绑定约束具有肯定的变量绑定约束表5 beta 结点类型表
CE 类型 具有谓词函数约束 具有否定的变量绑定约束
Object CE
Exist CE
Not CE PredicateBNode ExistPredJoin NotJoin HashedNotEqBJoin ExistNeqJoin HashedNotEqNJoin 具有肯定的变量绑定约束 HashedEqBNode ExistJoin HashedEqNJoin
42
北京航空航天大学硕士学位论文
4.6.4 连接beta 结点
beta 结点是CE 的末尾结点，因此连接beta 结点是对两个CE 的连接。在“alpha 网络生成算法”中建立的condition 的nodes 列表用于CE 之间的连接，主要有两个过程：
(1) 获得前一个CE 对应的condition 的nodes 列表的最后一个结点或者前一个beta
结点，将该结点做为新beta 结点的左侧输入。
(2) 获得当前CE 对应的condition 的nodes 列表的最后一个结点或者condition 对应
的事件类型结点，将该结点做为新beta 结点的右侧输入。
算法的详细描述如下： 算法名称：连接beta 结点
输入：前一个条件元素preCondition ，当前条件元素condition 、前一个beta 结点preJoinNode 和当前beta 结点joinNode 。
输出：无
1) 若preJoinNode 不为空，将preJoinNode 做为joinNode 的前驱结点；否则将
preCondition 的nodes 列表的最后一个结点做为joinNode 的前驱结点。
2) 取出condition 的template ，得到事件类型结点objectTypeNode 。
3) 若condition 的nodes 列表不为空，取出该列表的最后一个结点做为joinNode 的
前驱结点；否则将objectTypeNode 做为joinNode 的前驱结点。
4.7 event-correlation-rule 加入鉴别网络的过程
规则event-correlation-rule 定义如下：
(defrule event-correlation-rule
(EventOne
(e1-attr0 "ok")
(e1-attr1 ?var1)
(e1-attr2 ?var2)
(e1-attr3 ?var3))
(not(EventTwo
(e2-attr0 ?var1)
(e2-attr2 ?var4&:(> ?var4 ?var2))))
(exists (EventThree
(e3-attr0 ~?var1)))
(EventFour
(e4-attr0 ?var5))
43
第四章 鉴别网络的设计
=>(printout t "event-correlation-rule fired " ?var5 ?var3 crlf))
规则event-correlation-rule 所涉及的事件如表6所示，该规则如表7所示。 表6 规则event-correlation-rule 的事件定义表
---------------------------------------
表7 规则event-correlation-rule 描述表 Slot0
False EventOne
True
EventTwo Slot2 ?var2 ?var4&: ?var1
~?var1
?var5无 (> ?var4 ?var2)
EventThree
False
EventFour
无
--------
无 无
------- ?var3 ?var1规则信息通过词法分析和语法分析之后，形成规则对象。此时的规则对象除了binds ，join 为空，其他都根据表7赋予相应的值。在规则对象的conditions 中的每一个condition ，除了nodes 之外，其他都赋予相应的值。因此得到了初始化的规则对象。
在利用deftemplate 进行事件的定义时，已经生成了事件类型结点，如图23所示。下面阐述alpha 网络和beta 网络的生成过程。
图23 加入事件类型后的鉴别网络
4.7.1 alpha 网络的建立
从event-correlation-rule 的CE0建立alpha 网络时，第一个约束为字面量约束，模式为
44
北京航空航天大学硕士学位论文
(e1-attr0 "ok")，建立的Alpha 结点对应为字面量约束”ok”，如图24所示。
图24 建立字面量约束的alpha 结点图
继续获得该CE0的模式，第二、三、四个模式是复合模式，是含有变量定义（第一次出现的变量约束和谓词函数定义的变量）的模式。因此参考表6建立binds ，如表8所示，并加入到规则对象中。 表8 获取CE0中被绑定元素列表
CE
CE0
CE0
CE0leftIndex rightIndex negated 形成binds 属性的过程是这样的：根据表7中所示，CE0定义了三个变量var1、var2、var3，这三个变量均在规则的第0个CE ，则将rowId 设置为0，三个变量所在的插槽分别为Slot1，Slot2，Slot3，因此将leftIndex 设置为1，2，3。
由于该规则不存在Alpha 结点的共享，因此event-correlation-rule 所形成的CE0对应的nodes 列表中的元素为Node6。至此对应于CE0的alpha 网络生成结束。
对于CE1，被绑定变量只有var4，因此仅生成一个bind ，并加入到rule 的binds 属性中。var1做为绑定变量并不生成bind 。
对于CE2，因为没有字面量约束，所以不生成Alpha 结点，而且CE2没有被绑定约束变量，也不生成bind 。
对于CE3，仅生成一个被绑定变量bind ，并加入到rule 的binds 属性中。
最终形成规则对象的binds 属性如表9所示。在alpha 网络生成算法之后，CE0对应的condition 的nodes 列表中的元素为Node6，其他condition 的nodes 列表长度均为0，而对于condition 的hasNotEqual 和hasPredicate 的属性的赋值将在建立beta 网络时进行。
45
第四章 鉴别网络的设计
表9 最终形成的event-correlation-rule 的binds 列表 leftIndex
rightIndex negated
4.7.2 beta 网络的建立
对于规则event-correlation-rule ，建立和CE0对应的左侧输入适配结点后的鉴别网络如图25所示。CE0对应的nodes 列表元素为Node6和Node7。
EventOne 图25 在CE0中加入左侧输入适配结点 对于CE1，找到CE1的第一个约束（变量绑定类型），约束名为var1。用该变量名var1查找表9，拷贝表9中CE0的被绑定变量var1的属性并对其他属性赋值，形成表10的第一行。找到CE1的第二个约束（谓词函数类型），约束名为var4，被绑定变量名为var2。
拷贝表9中CE0的被绑定变量var2的属性并对其他属性赋值，形成表用var2查找表9，
10的第二行。
表10 CE1的绑定变量列表
rightIndex 0 2 negated 在表10中，列varName 、rowId 、leftIndex 是从rule 的binds 属性中拷贝所得，其他列是分析约束信息所得。例如：第一行的rightIndex 指明绑定变量var1的值可以在CE1的第0个插槽位置上得到；negated=false说明该绑定变量是肯定类型的变量绑定约束。第二行指明绑定变量var4绑定了变量var2，该绑定变量var4的值可以在CE1的第2个插槽位置上得到；isPredJoin=true说明该变量为谓词函数约束。
46
北京航空航天大学硕士学位论文
此时CE1所对应的condition 的hasNotEqual 和hasPredicate 都为true 。然后根据condition 的类型和表5建立NotJoin 结点。将表10的绑定变量列表加入到该结点，如图26所示。
图26 第一次调用“连接beta 结点”算法前 在连接beta 结点时，CE0对应的condition 的nodes 列表为Node6、Node7。在Node7后加入Node8，因此Node8
的左侧输入为Node7。而此时CE0的condition 的nodes 列表保持不变，仅将Node8做为Node7的后继结点，如图27所示。
图27 加入Node8之后，CE0的Condition 的nodes 列表图
因为CE1没有建立alpha 结点，连接beta 结点时，CE1的condition 的nodes 列表为空，因此将该condition 对应的事件类型结点，做为Node8的右侧输入。连接Node8到鉴别网络的工作完成，如图28所示。
图28 连接Node8到鉴别网络完毕
由上述获得绑定变量列表、建立beta 结点的过程可知，对于CE2生成了类型为ExistNeqJoin 的Node9，鉴别网络如图29所示。Node8做为Node9的左侧输入连接到Node9。而同连接Node8的右侧输入相同，将Node4做为Node9的右侧输入连接到Node9。
继续连接由CE3生成的结点Node10，最终生成的alpha 网络和beta 网络如图30所示。 47
第四章 鉴别网络的设计
图29 连接Node9到鉴别网络之前
EventOne 图30 event-correlation-rule 形成的alpha 网络和beta 网络 通过前面beta 网络的建立过程的描述，最终生成的对应于每个CE 的condition 如表11所示。其中对于每个CE 建立的Beta 结点在表11的第六列，对于CE0的nodes 列表如图31所示。每个Beta 结点中所包含的绑定元素如表12所示。
表11 event-correlation-rule 中每个CE 的Condition 和Beta 结点 CE 类型列表
有
无
无
无
表12 由event-correlation-rule 生成的beta 结点列表
rowId leftIndex rightIndex hasPredicate hasNotEqual Beta 结点 无
48
北京航空航天大学硕士学位论文
1
无绑定元素
图31
event-correlation-rule
中CE0的condition 的nodes 列表
在形成alpha 网络和beta 网络之后，将规则的右部做为规则激发时的动作加入到终结点，并加入到鉴别网络当中，最终形成了与规则event-correlation-rule 相对应的鉴别网络。如图32所示。
图32 event-correlation-rule 所在的鉴别网络
4.8 本章总结
本章介绍了鉴别网络的基本结构及其基本元素。在介绍鉴别网络的生成前，首先对规则对象进行了设计，然后阐述了alpha 网络和beta 网络的生成算法的设计，最后讲述了event-correlation-rule 加入到鉴别网络的过程。
49
第五章 模式匹配的设计
第五章 模式匹配的设计
在鉴别网络中，alpha 结点（除去左侧输入适配结点）和beta 结点都有相应的存储区，满足结点约束的事件实例都被存储在相应的存储区中。存储区存储事件实例是事件实例匹配的基础。本章先介绍alpha 结点存储区和beta 结点存储区的构成，在此基础上介绍模式匹配。
在alpha 结点的模式匹配是单一模式匹配，在beta 结点中的模式匹配是复合模式匹配，两者都是以鉴别网络为基础。因为模式匹配是规则匹配的最小单位，所以本章重点介绍模式匹配，当一次模式匹配成功后，进行下一次模式匹配时，存在对事件实例的传播，因此本章在最后阐述了事件实例在beta 结点中的传播方式。
本文改进了RETE 算法对beta 结点的右侧存储区的设计，提出了一种基于插槽位置的索引生成方法来存储事件实例。在beta 结点进行左侧匹配时，采用事件实例查找方法找到事件实例集中的事件实例并生成索引，利用索引进行查找匹配的事件实例，提高了对具有变量绑定类型模式的匹配效率。
5.1 alpha 结点的存储区的设计
具有存储区的alpha 结点有两种类型：事件类型结点和Alpha 结点，其存储区结构如图33所示。
图33 Alpha 结点的存储区表示
每个Alpha 结点（除去左侧输入适配结点）都有存储区与之对应，存储区内保存了通过该结点并且匹配成功的事件实例。例如：满足约束e1-attr0(eventOne i ) =" ok " 的事件实例eventOne i 发生时，进入事件类型结点Node2和规定了字面量约束的Alpha 结点
Node6。事件实例eventOne i 被存储在相应的存储区，如图33所示。
50
北京航空航天大学硕士学位论文
5.2 beta 结点的存储区的设计
与beta 结点左侧输入相连的是左侧输入适配结点或beta 结点，这两个结点的输出都是多个事件实例，因此beta 结点的左侧输入是多个事件实例；与beta 结点右侧输入相连的是事件类型结点或者Alpha 结点，这两个结点的输出是单个事件实例，因此beta 结点的右侧输入是单个事件实例。
5.2.1 事件实例集
将beta 结点的左侧输入的多个事件实例称之为事件实例集（简称Index ）。例如：拥其中A 在Index 的0位置上，B 在Index 有事件实例A 和B 的Index 可以记为Index[A,B]，
的1位置上。事件实例集是基于插槽位置的事件查找方法的基础，本小节主要讲述了事件实例集的建立。
Index 是包含有事件实例的数组。当单个事件实例从左侧输入适配结点或者事件实例集从beta 结点向下一个beta 结点传播时，都会建立新的Index ，并将已有的事件实例按照先后顺序加入到该新建的Index 当中，并向下个结点传播。
例如：joinNode1，joinNode2，joinNode3，如图34所示。当事件实例A 通过左侧输入适配结点进入joinNode1时，先建立Index[A]，然后传播Index[A]到joinNode1的左侧输入。当joinNode1的右侧输入的事件实例B 加入到joinNode1时，如果满足传播条件，则以前建立的Index[A]封装事件实例B 形成Index[A,B]，并传播Index[A,B]到joinNode2的左侧输入，然后继续匹配并且填充Index 。
图34 事件实例集的生成图
对于路径CEn 来说，当n=0时，事件实例从左侧输入适配结点进入joinNode ，并添加到Index 的最后一个位置；当n>0时，事件实例从右侧输入进joinNode 时，都会添加到Index 的最后一个位置。
51
第五章 模式匹配的设计
因此得到如下结论：如果事件实例满足CEn ，则会存储在Index 中的位置n 上，即
CE 在规则中的位置等于满足该CE 的事件实例存储在Index 中的位置。 5.2.2 Beta 结点的左侧存储区
为了保存从beta 结点左侧进入的事件实例集，需要设置beta 结点的左侧存储区，对于具有不同约束类型的beta 结点，左侧存储区的类型是不同的，如表13所示。
表13 beta 结点的左侧存储区和存储区索引
约束类型 具有谓词函数约束 具有否定的变量绑定约束具有肯定的变量绑定约束
左侧存储区 匹配存储区 普通存储区 普通存储区
存储区索引Index 无 无
普通存储区和alpha 结点的存储区类似，如图33所示。不同的是前者存储的是事件实例集，而后者存储的是事件实例。
具有谓词函数约束的beta 结点在进行模式匹配时，因为谓词函数约束的匹配不是看两个变量是否相等，而是需要函数的运算，所以不能利用基于插槽位置的索引生成方法来生成索引进行模式匹配。所以将谓词函数约束的右侧存储区设置为普通存储区。
因为Exist CE和Not CE需要对部分匹配事件实例进行计数，来决定是否向下传播。而右侧存储区是普通存储区，不能用来存储匹配的事件实例，所以将左侧存储区设计成匹配存储区。该存储区的索引是从左侧进入的Index ，值是和该Index 相匹配的所有右侧输入进来的事件实例，如图35所示。
图35 beta 结点的左侧存储区
5.2.3 Beta 结点的右侧存储区
为了保存从beta 结点右侧进入的事件实例，需要设置beta 结点的右侧存储区，对于具有不同约束类型的beta 结点，右侧存储区的类型也是不同的，如表14所示。
52
北京航空航天大学硕士学位论文
表14 Beta 结点的右侧存储区和存储区索引 约束类型 具有谓词函数约束 具有否定的变量绑定约束具有肯定的变量绑定约束
右侧存储区普通存储区二级hash 一级hash
存储区索引
无
一级索引：NotEqlHashIndex 二级索引：EqHashIndex
EqHashIndex
普通存储区和alpha 结点的存储区类似，如图33所示，存储事件实例。
对于具有变量绑定约束的beta 结点的alpha 存储区是通过一级hash 存储区和二级
hash 存储区来实现的。当事件实例从右侧进入到具有变量绑定约束的beta 结点时，将该事件实例中的用于参与模式匹配的变量值做成hash 索引，存入存储区。下面从两方面介绍肯定和否定的变量绑定约束的存储区及存储区索引。
5.2.4 具有变量绑定约束的Beta 结点的右侧存储区索引
当事件实例从右侧进入到具有变量绑定约束的beta 结点时，由于采用的存储区不同，存储方式也不同，对于事件实例的存储过程如下：
(1) 取出该joinNode 对应的右侧存储区，如果没有则建立结点的存储区； (2) 根据joinNode 的bind 变量列表，建立与事件实例相对应的索引； (3) 将索引和事件实例加入到该joinNode 的右侧存储区。
具有肯定变量约束的beta 结点和具有否定变量约束的beta 结点对于事件实例的存储过程基本相同，都是建立索引，将索引和事件实例加入到存储区。索引实质上是事件实例某些属性值的hashCode ，joinNode 的bind 变量列表指定了这些属性的插槽位置。而两种结点存储事件实例过程的不同之处在于生成索引的方法，因此下面分两部分设计基于插槽位置的索引生成方法。
1. 具有肯定变量绑定约束的Beta 结点的右侧存储区索引
该索引的形式为EqHashIndex，其中hashCode 是该索引的值，算法详细描述如下：
算法名称：建立EqHashIndex 索引
输入：被绑定变量列表binds ，事件实例event 。 输出：EqHashIndex 索引 1) 创建对象数组。
2) 取出binds 的bind 变量，由bind 的rightIndex 获得事件实例event 在插槽位置
rightIndex 上的属性值，加入对象数组。若binds 中包含其他变量，跳到2步；否则转向3步。
3) 建立EqHashIndex索引。
53
第五章 模式匹配的设计
图36是对于规则event-correlation-rule2(见附录) ，在joinNode 结点右侧存储区存储事件实例eventTwo j 时，根据插槽位置0和2得到的属性值生成的索引eqHashIndex1。
图36 event-correlation-rule2的CE2对应的joinNode 的左右存储区
2. 具有否定变量绑定约束的Beta 结点的右侧存储区索引
该索引的形式为NotEqHashIndex，其中的EqHashIndex 是二级索引。BindValue是由事件实例的属性形成的二元组，value 指定了该属性值，negated 指定了该属性值在bind 变量列表中是否满足否定的变量绑定约束。
算法名称：建立NotEqHashIndex 索引
输入：被绑定变量列表binds ，事件实例event 。 输出：NotEqHashIndex 索引 1) 创建bindValue 数组。
2) 取出binds 的bind 变量，由bind 的rightIndex 获得事件实例event 属性的插槽
位置rightIndex
3) 获得事件实例在该位置上的bindValue值，加入到bindValue 数
组。若binds 中包含其他变量，跳到2步；否则转向4步。
4) 建立二级索引EqHashIndex ，计算否定的bindValue(即negated=true)的值，将所
有获得的属性值的hashCode 相加，做为索引EqHashIndex 的hashCode 。
5) 建立一级索引NotEqHashIndex ，计算肯定的bindValue(即negated=false)的值，
将所获得的属性值的hashCode 相加，做为一级索引NotEqHashIndex 的hashCode ，并将二级索引附着在一级索引上。 6) 返回NotEqHashIndex 索引。
图37是对于规则event-correlation-rule3(见附录) ，在joinNode 结点右侧存储区存储事件实例eventTwo j 时，根据插槽位置0和2得到的bindValue 值生成的一级索引
NotEqHashIndex1和二级索引eqHashIndex1。
54
北京航空航天大学硕士学位论文
图37 event-correlation-rule3的CE3对应的joinNode 的左右存储区
5.3 alpha 结点的模式匹配的设计
alpha 结点的模式匹配过程如下：
来获得事件实例在该插槽位置上的属性值； (1) 根据Alpha 结点中属性插槽位置ID ，
(2) 对Alpha 结点中的属性插槽值和事件实例的在插槽位置上的属性值进行匹配； (3) 若匹配成功，将事件实例存储在结点的存储区，然后直接传播该事件实例到下
一个结点；否则放弃该事件实例。
如图32所示，Node6的插槽ID 是0，插槽值是”ok”。事件实例eventOne i 在经过Node6时，获得事件实例 eventOne i 在插槽位置0上的属性值，如表16所示，即”ok”，然后对两者进行匹配，匹配成功，则传递到结点Node7。
事件类型结点做为特殊的Alpha 结点，在匹配时将插槽位置和插槽值改为类型信息，匹配过程与上述过程相似。
左侧输入适配结点只存在于CE0中。该结点不对事件实例进行匹配，仅对单个事件实例形成Index ，向下个beta 结点传播该Index 。
5.4 Beta 结点的模式匹配的设计
因为beta 结点是用于关联两个CE 的结点，因此进行模式匹配时必须等到两个或者两个以上的事件实例到达该结点，所以在进行模式匹配前，先对事件实例进行存储。然后等待其他事件实例的到来再进行匹配。beta 结点的模式匹配和传播方式程序流程如图38所示。
55
第五章 模式匹配的设计
图38 beta 结点模式匹配和传播方式流程图
为了方便阐述，将定义左侧匹配和右侧匹配的概念。
左侧匹配：事件实例集从左侧进入beta 结点，查找结点的右侧存储区，看是否存在和该事件实例集匹配的事件实例。
右侧匹配：事件实例从右侧进入beta 结点，查找结点的左侧存储区，看是否存在和该事件实例匹配的事件实例集。
无论是左侧匹配还是右侧匹配，从事件实例集中找到需要匹配的事件实例及其属性值是进行模式匹配的前提。本文采用一种基于插槽位置的事件实例查找方法从事件实例集中找到这些参与模式匹配的事件实例。
5.4.1 基于插槽位置的事件实例查找方法
插槽是事件定义中所规定的属性位置。该方法的主要目的就是找到Index 中所包含的用于参与模式匹配的事件实例。例如图32所示的鉴别网络，在eventTwo j 发生后传递到
Node8，查看左侧存储区中的所有事件实例集，从每个事件实例集中找到事件实例eventOne i ；在eventOne i 发生后，传递到Node8后，从左侧输入的事件实例集中找到eventOne i 用于和右侧存储区的eventTwo j 进行匹配。因此从事件实例集中找到eventOne i 就是该方法的应用。
因为CE 在规则中的位置等于满足该CE 的事件实例存储在Index 中的位置，而且
56
北京航空航天大学硕士学位论文
bind 变量列表的rowId 指明了被绑定元素的所在CE 的位置。所以有如下结论：
通过beta 结点bind 变量的rowId 可以找到被绑定元素所在的CE 的位置，而传递到该beta 结点左侧输入的Index 在该位置上的事件实例，就是需要进行模式匹配的事件实例。
为了证实该结论，将部分鉴别网络进行描述，如图39和图40所示。进入第i 个CE 对应的joinNode 的事件实例是eventi ，每一个joinNode 的左侧输入是Index 。本节分析了怎样在第n 个joinNode 中，根据该结点的bind 变量列表在Index 中找到合适的事件实例。
在图40中的第n 个joinNode 的第一个bind 变量rowId=k，即绑定变量在第k 个CE 上。若事件实例eventk 在通过第k 个CE 与第k-1个CE 的joinNode 时成功匹配，则eventk 被封装在了Index 的第k 个位置上。
因此可以在Index 中找到满足第k 个CE 与第k-1个CE 的joinNode 规定的关联条件的事件实例eventk ，也就是找到了在第n 个joinNode 中进行事件关联的事件实例
eventk 。
同理，通过bind 变量列表的第二个元素的rowId ，可以在Index 中找到eventj 。eventk 和eventj 同右侧的输入eventn 进行模式匹配。
模式匹配用来判断事件实例的属性是否满足模式所规定的约束信息，因此在找到参与模式匹配的事件实例后，需要进一步找到事件实例中的属性值。
图39 Beta 网络部分结点图（1）
57
第五章 模式匹配的设计
图40 Beta 网络部分结点图（2）
通过rowId 找到了用于模式匹配的事件实例在Index 中的位置，而leftIndex 和
rightIndex 指明了事件实例的属性插槽的位置，即eventk 的插槽m 上的属性值和eventn 的插槽n 上的属性值相对应，在模式匹配过程中，要判断出这两个值是否满足约束条件。同理，也需要判断eventj 的插槽o 上的属性值和eventn 的插槽p 上的属性值是否满足约束条件。
5.4.2 Beta 结点的模式匹配
在事件实例传播到joinNode 结点时，结点所对应的约束类型决定了模式匹配的实现方式，如表15所示。结点所对应的CE 类型决定了结点的传播方式。
表15 具有不同约束类型的beta 结点的左右匹配方式
约束类型 具有谓词函数约束 具有否定的变量绑定约束 具有肯定的变量绑定约束
左侧匹配 Bind 方式Hash 方式Hash 方式
右侧匹配Bind 方式Bind 方式Bind 方式
beta 结点的模式匹配按事件实例的来源分为左侧匹配和右侧匹配，按实现方式，分为Bind 方式和Hash 方式。这两种方式都是以基于插槽位置的事件实例查找方法为基础。
1. Bind 方式
58
北京航空航天大学硕士学位论文
若Index 从左侧输入，匹配过程如下：
(1) 通过基于插槽位置的事件实例查找方法，找到Index 中的事件实例及其属性值；
(2) 遍历右侧存储区内每一个事件实例，判断该事件实例的属性值是否和(1)的属性
值匹配。
若右侧存储区没有这样的事件实例，则匹配失败，不进行下一个模式匹配；否则进行下一个模式匹配。
若事件实例从右侧输入，匹配过程如下：
(1) 遍历左侧存储区内每一个事件实例集Index ；
(2) 通过基于插槽位置的事件实例查找方法，找到Index 中的事件实例及其属性值；
(3) 判断属性值是否和事件实例的属性值相匹配。
若左侧存储区没有这样的事件实例集，则匹配失败，不进行下一个模式匹配；否则进行下一个模式匹配。
2. Hash 方式
当Index 从左侧进入具有变量绑定约束的beta 结点时，利用该匹配方式来判断右侧存储区内是否存在满足约束的事件实例，匹配过程如下：
(1) 通过基于插槽位置的事件实例查找方法，查找到Index 中的事件实例；
(2) 利用基于插槽位置的索引生成方法，将这些事件实例的属性值转换为索引；
(3) 利用索引查找右侧存储区，看是否有相应的事件实例相匹配。
若查找到有相应的事件实例，则表明查到的事件实例和左侧的Index 模式匹配成功。
5.4.3 事件实例在beta 结点的模式匹配过程
假设鉴别网络是由规则event-correlation-rule 所生成，如图32所示。进入该鉴别网络的事件实例分别是eventOne i 和eventTwo j ，如表16所示。本节阐述了事件实例eventOne i 和eventTwo j 先后到达结点Node8时，在其中的模式匹配过程。
表16 事件实例表 事件实例eventOne i e1-attr0=”ok”e1-attr1=100e1-attr2=0e1-attr3=0
eventTwo j e2-attr0=”100”e2-attr1=300e2-attr2=20-------------
1. eventOne i 从左侧进入joinNode
59
第五章 模式匹配的设计
eventOne i 由CE0路径进入到Node8。由左侧输入进入到Node8之前，先通过左侧输入适配结点Node7进行适配，形成事件实例集Index1[eventOne i ]。
事件实例集Index1从左侧进入Node8后，被存储在Node8的左侧存储区。遍历右侧存储区，发现没有相匹配的事件实例，则等待右侧输入事件实例eventTwo j 的到来。此时Node8的左侧存储区如图35所示。
因为Node8是具有谓词函数约束的joinNode 。由表13可知该结点的左侧存储区是匹配存储区。其中哈希表的值指向了事件匹配列表，该列表中保存了和该事件eventOne i 匹配的事件实例；哈希表的关键字是Index1[eventOne i ]。
2. eventTwo j 从右侧进入joinNode
事件实例eventTwo j 发生后，从CE2路径传播到Node8的右侧输入，存储到Node8的右侧存储区。由表14可知该结点的右侧存储区是普通存储区，物理结构与图33相似。
3. eventOne i 和eventTwo j 在joinNode 的模式匹配
eventTwo j 存储到Node8后，利用Bind 方式进行模式匹配：遍历左侧存储区内的Index ，对每一个Index 用事件实例查找方法，看该Index 是否匹配eventTwo j ，如图41所示。
当遍历到Index1时，基于插槽位置的事件实例查找方法根据bind 变量列表来取出Index1中的将要参与模式匹配的事件实例。
表明被绑定变量在CE0中。同时指定了Index Node8中的两个bind 变量的rowId=0，
中的第0个位置的事件实例就是来自于CE0的事件实例，该事件实例是含有被绑定变量值的事件实例。此时Index 的第0个位置的事件实例是eventOne i 。
60
北京航空航天大学硕士学位论文
图41 joinNode的左右存储区
Node8中的第一个bind 变量leftIndex=1，表明被绑定变量值是事件实例eventOne i 的属性在插槽位置1上的属性值e 1−attr 1(eventOne i ) 。rightIndex=0表明绑定变量值是事件实例eventTwo j 的属性在插槽位置0上的属性值e 2−attr 0(eventTwo j ) 。
Node8的第一个bind 变量指明了该结点包含肯定的变量绑定约束e 1−attr 1(eventOne ) =e 2−attr 0(eventTwo ) ，判断得到的属性值e 1−attr 1(eventOne i ) 和e 2−attr 0(eventTwo j ) 是否相等，即是否满足该变量绑定约束。
但是该结点还含有谓词函数约束e 1−attr 2(eventOne i )
在本例中，由表16可知，事件实例eventOne i 和eventTwo j 满足上述约束。但是Node8是NotJoin 类型的JoinNode ，所以将eventTwo j 保存在左侧存储区的事件匹配列表中，并向下一个结点传播retract 动作，移除后继结点对左侧输入Index 的存储。
5.4.4 joinNode 结点中的事件传播方式
当左侧输入的Index 和右侧输入的事件实例满足事件关联的条件时，将传播Index 。根据不同类型的CE 对应的joinNode ，对事件实例有着不同的传播方式，如表17所示。
61
第五章 模式匹配的设计
表17 鉴别网络中事件实例的传播方式 CE 类型 动作
Assertleft
assert 该Index 。
若右侧存储区中的事件实例数由0个增加到1个且在左侧存储区
AssertRight
Not CE
retractLeft
retractRight
内有和该事件实例匹配的Index ，则向后续结点assert 该Index 。
若右侧存储区中与Index 匹配的事件实例数大于0，向后续结点
Assertleft
assert 该Index 。
若右侧存储区中的事件实例数由0个增加到1个且在左侧存储区
AssertRight
Exist CE
retractLeft
retractRight
内有和该事件实例匹配的Index ，则向后续结点retract 该Index 。
若右侧存储区中有与Index 匹配的事件实例，将该事件实例与该
Assertleft
Index 并形成新Index ，向后续结点assert 新Index 。
若左侧存储区内有和该事件实例匹配的Index ，将该事件实例与
AssertRight
该Index 合并形成新Index ，向后续结点assert 新Index 。
Object CE
若右侧存储区内有和该Index 匹配的事件实例，将该事件实例与
retractLeft
该Index 并成新Index ，向后续结点retract 新Index 。
若左侧存储区内有和该事件实例匹配的Index ，将该事件实例与
retractRight
该Index 并成新Index ，向后续结点retract 新Index 。 内有和该事件实例匹配的Index ，则向后续结点assert 该Index 。 直接向后续结点retract 该Index 。 若右侧存储区中的事件实例数由1个减少到0个且在左侧存储区内有和该事件实例匹配的Index ，则向后续结点retract 该Index 。 直接向后续结点retract 事件实例集。 若右侧存储区中的事件实例数由1个减少到0个且在左侧存储区解释 若右侧存储区中与Index 匹配的事件实例数为0，向后续结点
例如：规则event-correlation-rule 中CE2：(exists (EventThree (e3-attr0 ~?var1)))，如果Index 从左侧进入，查找右侧存储区相匹配的事件实例，若存在满足约束的事件实例则向后继结点传播该Index 。因为exists 不能定义被绑定变量，所以并不把右侧输入的事件实例加入到Index ；若事件实例从右侧进入，此时右侧存储区第一次存在和左侧存储区的某个Index 相匹配的事件实例，则传播该Index ，若在此之前右侧存储区已存在和左侧存储区的某个Index 相匹配的事件实例，则不进行传播，因为在此之前已经传播
62
北京航空航天大学硕士学位论文
了该Index 到下一结点。
retract 动作是将事件实例从存储区中移除的过程。例如Not CE，满足该CE 的事件实例从右侧输入时，该实例第一次进入beta 结点和左侧存储区的某个Index 相匹配，而在此之前，该Index 必定传播到了下一个joinNode ，此时该事件实例发生，意味着不满足该Not CE，需要从后继结点中移除本结点生成的部分匹配，因此传播retract 动作，移除后继结点对左侧输入Index 的存储。
CE 的类型决定了事件实例在模式匹配后的传播方式，表17详细描述了不同类型的CE 在执行模式匹配的assertLeft ，assertRight ，retractLeft 和retractRight 四个动作后，对匹配的事件实例集的传播。
5.5 规则激发和故障定位
当事件实例或者Index 能够传播到终结点时，说明有满足规则的事件实例的发生，因此会激发该规则，执行规则的右部动作，产生故障定位信息。
在产生故障定位信息的同时，满足规则的事件实例或Index 已存在于鉴别网络的存储区中。如果事件实例或Index 不用于今后的事件关联，则可以从鉴别网络中移除，当相同的事件实例再次发生时，重新进行关联，然后产生新的故障定位信息。
5.6 本章总结
本章首先介绍了事件实例集的概念，它是基于插槽位置的事件实例查找方法的基础。然后根据具有不同约束类型的beta 结点介绍了结点的左侧和右侧存储区的设计，对变量绑定类型的右侧存储区进行了详细阐述。
然后以鉴别网络和存储区为基础，介绍了alpha 结点和beta 结点的模式匹配、事件实例的传播和规则激发。
63