[發明專利]基于謂詞覆蓋的啟發式事件匹配方法

無效

• 申請號: 200910028109.5
• 申請日: 2009-01-09
• 公開（公告）號: CN101551757A
• 公開（公告）日: 2009-10-07
• 發明（設計）人: 潘金貴;張凱隆;莊艷;徐曉旸
• 申請（專利權）人: 南京大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;H04L12/56;H04L29/08
• 代理公司: 南京天翼專利代理有限責任公司
• 代理人: 湯志武;王鵬翔

1、基于謂詞覆蓋的啟發式事件匹配方法，訂購表達式由多個訂購謂詞組成，事件表達式由多個屬性、即稱之為事件謂詞組成；其特征是包括以下幾個步驟：

訂購預處理：該預處理過程解析訂購式，并提取出不同的訂購謂詞，同時將各個訂購謂詞依據謂詞關系插入到對應的訂購謂詞關系樹中相應位置；預處理過程結束后，將構建出多棵訂購謂詞關系樹；

啟發式謂詞匹配：將接收到的事件表達式進行解析，并將解析出的各個事件謂詞同對應的訂購謂詞關系樹進行謂詞匹配；設事件謂詞為p，待匹配的訂購謂詞關系樹上的訂購謂詞結點s，M_i為與第i棵訂購謂詞關系樹進行成功匹配的謂詞集合；

啟發式謂詞匹配方法將利用啟發式匹配/過濾規則，盡可能減少事件謂詞與訂購謂詞的比較次數，通過遍歷訂購謂詞關系樹，獲得相匹配的訂購謂詞集合。匹配/過濾方法如下：

(1)如果p與s的關系滿足過濾規則2、5，那么p將終止與以訂購謂詞結點s為根結點的子樹中的任何謂詞(結點)進行匹配；

(2)如果p與s的關系滿足過濾規則3、6，那么p將終止與訂購謂詞結點s為根結點的左子樹(覆蓋子樹)中的任何謂詞(結點)進行匹配；

(3)如果p與s的關系滿足匹配規則7、8，那么表明p與s匹配，將s加入集合M₁中，即M_i←M_i∪s；同時p將繼續與其他訂購謂詞結點進行匹配操作；

發布事件匹配：發布事件由若干個事件謂詞組成，故對于每個事件謂詞都將對應著一棵具有相同屬性的訂購謂詞關系樹，在啟發式謂詞匹配過程處理的基礎上，發布事件的匹配將事件表達式的每一事件謂詞同相應的訂購謂詞關系樹進行匹配，并將各訂購謂詞集合進行“交”運算操作獲得與事件相匹配的訂購集合；

對任一訂購S，其每一訂購謂詞s_k，都可以找到某一訂購謂詞集合M_i，使得s_k∈M_i，即∃Mi,sk∈Mi(i=1,2,...n),]]>才認為發布事作E=^k=1npk]]>同訂購S相匹配；

謂詞：令s＝xΘAΘy，其中x，y是屬性A值域空間中的一個合理取值，Θ是比較操作，則稱s為謂詞；若x＝y，則稱s為等值謂詞，否則稱s為非等值謂詞。其中，組成發布事件表達式的謂詞稱為事件謂詞，組成訂購表達式的謂詞稱為訂購謂詞；

取閾值函數：定義取謂詞上下閾值函數ξ(s)：若s＝xΘAΘy且Θ＝“＜”，則ξ(s↓)＝x，ξ(s↑)＝y；

假設有訂購謂詞s₁及s₂，且兩訂購謂詞描述的是同一屬性的不同范圍表示，默認的比較操作符Θ＝“＜”，若無特別說明，所涉及的謂詞皆為非等值謂詞；

謂詞關系：依據謂詞所包含的數值范圍進行謂詞間的關系約定，并將其可能的關系綜合為兩種：覆蓋關系及序關系；其中，覆蓋關系描述了訂購謂詞s₁及s₂存在覆蓋關系，即有ξ(s₁↓)≤ξ(s₂↓)且ξ(s₁↑)≥ξ(s₂↑)，則稱訂購謂詞s₁覆蓋s₂，記為序關系描述了訂購謂詞s₁及s₂存在序關系，即有[ξ(s₁↓)≤ξ(s₂↓)且ξ(s₁↑)≤ξ(s₂↑)]或[ξ(s₁↓)≥ξ(s₂↓)且ξ(s₁↑)≥ξ(s₂↑)]，則稱s₁，s₂存在左序關系或右序關系，記為或

訂購謂詞關系樹：根據訂購謂詞關系構建的二叉關系樹，訂購謂詞將對應訂購謂詞關系樹中的訂購謂詞結點；其中，訂購謂詞結點的左子樹稱為覆蓋子樹，覆蓋子樹中的所有訂購謂詞結點都被其所覆蓋；訂購謂詞結點的右子樹稱為序子樹，序子樹的所有訂購謂詞結點都與其存在(右)序關系；

啟發式匹配/過濾規則：依據訂購謂詞關系樹的特殊結構，并結合非對稱謂詞事件匹配及對稱謂詞(事件)匹配的相關性質，提出了若干條啟發式匹配/過濾規則，這些匹配/過濾規則的運用可以提高事件匹配算法的效率；對于發布事件謂詞p及訂購謂詞s，有

過濾規則1：[p]∉s⇒[p]∉∀s′(↑s′s),]]>其中[p]為等值事件謂詞p相應的值，適用于非對稱事件匹配；

解釋：如果[p]不屬于s，那么[p]一定不屬于被s所覆蓋的任何訂購謂詞；

過濾規則2：其中[p]為等值事件謂詞p相應的值，適用于非對稱事件匹配；

解釋：如果[p]小于訂購謂詞s的下闕值，那么[p]一定不屬于同s存在右序關系的任何訂購謂詞s′，其中

剪枝操作：對以訂購謂詞結點s為根結點的子樹剪枝，終止對該子樹任何訂購謂詞結點的匹配；

過濾規則3：[p]>x(s↑)⇒[p]∉∀s′(↑s′s),]]>其中[p]為等值事件謂詞p相應的值，適用于非對稱事件匹配；

解釋：如果[p]大于訂購謂詞s的上闕值，那么[p]一定不屬于同s存在覆蓋關系的任何訂購謂詞s′，其中

剪枝操作：對以訂購謂詞結點s為根結點的左子樹(覆蓋子樹)進行剪枝，終止對該左子樹任何訂購謂詞結點的匹配；

過濾規則4：適用于對稱事件匹配；

解釋：如果p不被s所覆蓋，那么p與同s存在覆蓋關系的任何訂購謂詞s′之間一定不存在覆蓋關系，其中

過濾規則5：適用于對稱事件匹配；

解釋：如果p與s存在序關系，那么謂詞p同謂詞s′一定不存在覆蓋關系，其中s′與s存在序關系

剪枝操作：對以訂購謂詞結點s為根結點的序子樹剪枝，終止對該子樹任何訂購謂詞結點的匹配；

過濾規則6：適用于對稱事件匹配；

解釋：如果p與s存在序關系，那么p同s′一定不存在覆蓋關系，其中s′與s存在覆蓋關系

剪枝操作：對以訂購謂詞結點s為根結點的左子樹(覆蓋子樹)進行剪枝，終止對該左子樹任何訂購謂詞結點的匹配；

匹配規則7：[p]∈s⇒p⊕s,]]>表明p與s匹配，其中為匹配成功符；適用于非對稱事件匹配；

匹配規則8：↑ps⇒p⊕s,]]>表明p與s匹配，其中為匹配成功符；適用于對稱事件匹配。