基于本體的發(fā)布訂閱系統(tǒng)的數(shù)據(jù)模型和匹配算法

1、基于本體的發(fā)布/訂閱系統(tǒng)的數(shù)據(jù)模型和匹配算法*Supported by the National Natural Science Foundation of China under Grant No.60173023 (國家自然科學(xué)基金); the National High-Tech Research and Development Plan of China under Grant No.2001AA113010 (國家高技術(shù)研究發(fā)展計劃(863); the National Grand Fundamental Research 973 Program of China under Gra

2、nt No.2002CB312005 (國家重點基礎(chǔ)研究發(fā)展規(guī)劃(973)作者簡介: 汪錦嶺(1974),男,安徽廬江人,博士,主要研究領(lǐng)域為分布式計算,中間件技術(shù);金蓓弘(1967),女,博士,副研究員,CCF高級會員,主要研究領(lǐng)域為分布式計算,軟件工程技術(shù);李京(1966),男,博士,研究員,博士生導(dǎo)師,主要研究領(lǐng)域為軟件體系結(jié)構(gòu),組合軟件技術(shù);邵丹華(1971),男,工程師,主要研究領(lǐng)域為中間件技術(shù).汪錦嶺1,2+, 金蓓弘1, 李 京1, 邵丹華11(中國科學(xué)院 軟件研究所 軟件工程技術(shù)中心,北京 100080)2(中國科學(xué)院 研究生院,北京 100049)Data Model and

3、 Matching Algorithm in an Ontology-Based Publish/Subscribe SystemWANG Jin-Ling1,2+, JIN Bei-Hong1, LI Jing1, SHAO Dan-Hua11(Technology Center of Software Engineering, Institute of Software, The Chinese Academy of Sciences, Beijing 100080, China)2(Graduate School, The Chinese Academy of Sciences, Bei

4、jing 100049, China)+ Corresponding author: Phn: +86-10Received 2004-02-24; Accepted 2004-06-10Wang JL, Jin BH, Li J, Shao DH. Data model and matching algorithm in an ontology-based publish/subscribe system. Journal of Software, 2005,16(9):1625-1635. DOI: 10.1360/jos161625Abstract:The existing publis

5、h/subscribe systems cant match events with subscriptions based on the semantic of events, and they cannot support events with complex structure (such as graph structure). The Semantic Web technologies are introduced into the publish/subscribe system and an ontology-based publish/subscribe system is

6、proposed. In this system, the concept model of events is represented as ontologies, the events are represented as RDF graphs, and the subscriptions are represented as graph patterns. The system can overcome the disadvantages of the existing publish/subscribe systems. Experimental results show that i

7、t has high matching efficiency.Key words:publish/subscribe; ontology; RDF; matching algorithm摘 要:現(xiàn)有的發(fā)布/訂閱系統(tǒng)不能根據(jù)事件的語義來進行事件與訂閱的匹配,且不能支持具有復(fù)雜結(jié)構(gòu)(如圖狀結(jié)構(gòu))的事件.將語義Web技術(shù)引入發(fā)布/訂閱系統(tǒng)中,提出一種基于本體的發(fā)布/訂閱系統(tǒng).該系統(tǒng)采用本體來表示事件的概念模型,采用RDF圖來表示事件,采用圖模式來表示訂閱條件.它能較好地解決現(xiàn)有的發(fā)布/訂閱系統(tǒng)的上述問題.實驗結(jié)果表明,該系統(tǒng)具有較高的訂閱匹配效率.關(guān)鍵詞:發(fā)布/訂閱;本體;RDF;匹配算法中圖法分類

8、號:TP393文獻標(biāo)識碼: AInternet的快速普及,極大地改變了分布式系統(tǒng)的規(guī)模.基于Internet的分布式系統(tǒng)可以包含上萬個分布于世界各地的參與者,在系統(tǒng)的整個生命周期中,這些參與者的位置和行為都可能會改變.這就需要有一種更為靈活的通信模型和交互機制,以反映系統(tǒng)的高度動態(tài)和松散耦合的特性.而發(fā)布/訂閱(publish/subscribe,簡稱pub/sub)范型(paradigm)能夠很好地滿足上述需求,因此受到越來越多的關(guān)注.在pub/sub方式下,信息提供者以“事件”的形式,將信息發(fā)布到pub/sub系統(tǒng)中;信息使用者定義一個訂閱條件,表示對系統(tǒng)中的某一特定種類的事件感興趣;而p

9、ub/sub系統(tǒng)保證將所發(fā)布的事件及時、可靠地傳送到所有感興趣的訂閱者.pub/sub交互風(fēng)格的優(yōu)點在于,信息的生產(chǎn)者和消費者在時間、空間和控制流這3個方面都被完全解耦1,因而能夠很好地滿足大規(guī)模、高度動態(tài)的分布式系統(tǒng)的需要.在不同的分布式系統(tǒng)中,各參與者之間所交換的信息的格式和含義往往是不一樣的.為了使pub/sub系統(tǒng)成為一種通用的分布式計算基礎(chǔ)設(shè)施,能夠支持多種應(yīng)用系統(tǒng),它就必須具有很強的表達能力,能夠:· 支持各種具有不同語義和格式的事件;· 提供一個強大的訂閱語言,使得信息的接收者能夠方便地表達它對哪些事件感興趣.雖然在pub/sub系統(tǒng)領(lǐng)域已經(jīng)有了很多研究,但是

10、現(xiàn)有的pub/sub系統(tǒng)在表達能力方面尚存在如下不足:(1) 目前已有的系統(tǒng)基本上都是根據(jù)事件的結(jié)構(gòu)信息來進行事件與訂閱的匹配,而缺乏對事件本身語義的理解.如果pub/sub系統(tǒng)能夠從語義上進行事件與訂閱的匹配,必將會大大提高匹配的準(zhǔn)確度,同時也會使訂閱者能夠更加方便地定義其訂閱條件.(2) 目前已有的系統(tǒng)只能支持關(guān)系數(shù)據(jù)結(jié)構(gòu)(如“屬性=值”對)和樹形數(shù)據(jù)結(jié)構(gòu)(如XML),而某些應(yīng)用場景可能要求事件具有更為復(fù)雜的結(jié)構(gòu),如圖狀數(shù)據(jù)結(jié)構(gòu).此外,不同的發(fā)布者所發(fā)布的事件可能具有不同的結(jié)構(gòu),例如有的為XML,有的為圖狀結(jié)構(gòu).因此,需要有一種統(tǒng)一的機制,能夠同時處理不同格式的事件.為了解決上述問題,我們

11、將語義Web技術(shù)引入pub/sub系統(tǒng)中,提出一種基于本體的pub/sub系統(tǒng)(ontology-based publish/subscribe system,簡稱OPS).該系統(tǒng)將事件中所涉及到的各種概念整合到一起,建立起統(tǒng)一的概念模型,從語義和結(jié)構(gòu)兩個方面來解決訂閱匹配問題.同時,在OPS系統(tǒng)內(nèi)部,每個事件被表示為一個RDF(resource description framework)2圖,它是一種帶標(biāo)記的有向圖(directed labeled graph,簡稱DLG).Tim Berners-Lee指出3,任何格式的數(shù)據(jù)都可以被表示為DLG,進而可以被表示為RDF.因此,本系統(tǒng)可以同

12、時支持各種格式的事件,包括關(guān)系數(shù)據(jù)結(jié)構(gòu)、樹型數(shù)據(jù)結(jié)構(gòu)以及圖狀數(shù)據(jù)結(jié)構(gòu)等,其表達能力大大高于已有的pub/sub系統(tǒng).當(dāng)事件被發(fā)布時,系統(tǒng)首先將其轉(zhuǎn)換成RDF格式,然后再對其進行進一步的處理.而對于事件接收者而言,所有的事件都是RDF格式的.1 相關(guān)工作Pub/sub系統(tǒng)可以分為基于主題和基于內(nèi)容兩大類.在基于主題的系統(tǒng)中(如IBM MQSeries4),事件被劃分為若干個固定的主題,每個事件都只能屬于其中的某一個主題.發(fā)布者在發(fā)布事件時,必須指明該事件屬于哪一個主題;訂閱者則對某一主題下的所有事件進行訂閱.在基于內(nèi)容的系統(tǒng)中,訂閱者根據(jù)事件的內(nèi)部結(jié)構(gòu),設(shè)置一個訂閱條件,所有滿足該條件的事件都將

13、被傳送給該訂閱者.與基于主題的pub/sub系統(tǒng)相比,基于內(nèi)容的pub/sub系統(tǒng)提供了更強的表達能力,使訂閱者能夠以更細的粒度來定義其訂閱條件.目前的基于內(nèi)容的pub/sub系統(tǒng)又可分為兩類,一類是基于Map的,另一類是基于XML的.在基于Map的pub/sub系統(tǒng)中,事件的內(nèi)容為多個“屬性=值”的集合,訂閱條件一般是各個屬性之上的簡單斷言的連接,通常稱為平面模式(flat pattern).較有影響的原型系統(tǒng)包括SIENA5,Gryphon6,JEDI7,Keryx8,Elvin9等.在基于XML的pub/sub系統(tǒng)中,每個事件是一個XML文檔,訂閱語言通常是XPath或其變體,其中既包括

14、對XML文檔結(jié)構(gòu)的約束,又包括對某些元素和屬性的約束,通常人們稱其為樹模式(tree pattern).目前已有的原型系統(tǒng)包括XFilter10,XTrie11,WebFilter12等.與已有的pub/sub系統(tǒng)相比,OPS系統(tǒng)的不同之處在于:1) 已有的系統(tǒng)基本上都不能利用事件的語義信息進行訂閱匹配,而OPS系統(tǒng)通過采用語義Web技術(shù),能夠根據(jù)事件的語義來提供更為準(zhǔn)確的匹配.2) OPS系統(tǒng)中的事件被表示為一個有向圖,從而該系統(tǒng)能夠支持比Map和XML格式更為復(fù)雜的事件.3) 在OPS系統(tǒng)中,訂閱條件是一種圖模式(graph pattern),其表達能力超過了平面模式和樹模式.近年來,也有

15、一些對pub/sub系統(tǒng)事件語義的研究,如S-ToPSS13和CREAM14等.與這些工作相比,OPS系統(tǒng)的不同之處在于,事件被表示為RDF圖,訂閱條件被表示為圖模式,因而具有更強的表達能力.在信息檢索(information retrieval)領(lǐng)域的信息過濾(information filter)系統(tǒng)和選擇性數(shù)據(jù)發(fā)送(selective dissemination of information)系統(tǒng)中,也有很多對訂閱和匹配問題的研究15-17.在這些系統(tǒng)中,事件通常是非結(jié)構(gòu)化的文本,訂閱條件通常為關(guān)鍵詞的集合.與它們相比,OPS系統(tǒng)能夠利用事件的語義信息和結(jié)構(gòu)信息進行匹配,從而能夠比基于關(guān)

16、鍵詞的方法提供更為精確的過濾.同時,信息檢索領(lǐng)域的這些系統(tǒng)的關(guān)注重點通常是匹配的有效性,即如何找到最相關(guān)的信息,而很少關(guān)注匹配的效率.在數(shù)據(jù)庫領(lǐng)域的觸發(fā)器和規(guī)則處理方面,也有一些對訂閱和匹配問題的研究18,19.在這些系統(tǒng)中,訂閱條件一般為平面模式,與基于Map的pub/sub系統(tǒng)類似.在國內(nèi),對分布式系統(tǒng)消息通信機制的研究主要集中于消息隊列(MQ)方式20,而較少有對pub/sub技術(shù)的研究.2 數(shù)據(jù)模型在OPS系統(tǒng)中,我們采用語義Web中的RDF語言和DAML+OIL21語言來描述系統(tǒng)的數(shù)據(jù)模型.OPS系統(tǒng)的數(shù)據(jù)模型包括如下兩個方面:1) 事件模型,它定義了事件內(nèi)部數(shù)據(jù)的組織方式,采用RD

17、F語言來描述;2) 概念模型,它定義了所有事件中涉及到的各種概念及其相互關(guān)系,采用DAML+OIL語言來描述.由于RDF和DAML+OIL主要是用來描述WWW上的信息的,因而它們使用URI作為各個實體的標(biāo)識.而對于一個基于事件的系統(tǒng)而言,其關(guān)注的重點是正在傳輸中的事件,這些事件本身以及事件內(nèi)部的各實體往往沒有具體的URI.因此,當(dāng)我們采用RDF來表示事件的語義時,事件本身以及大多數(shù)事件內(nèi)部實體都被表示為空白結(jié)點(blank node).根據(jù)RDF規(guī)范,可以為空白結(jié)點賦一個以“_:”開始的ID.在下文中,為清晰起見,我們稱圖中的結(jié)點為“頂點”,稱樹中的結(jié)點為“結(jié)點”.2.1 事件模型在OPS系統(tǒng)

18、內(nèi)部,每個事件被表示為一個RDF圖,稱為事件圖(event graph).RDF是一種按照(subject, property,object)三元組來表達事實的方式,每個三元組稱為一個“語句(statement)”,其中subject,property為URI,object可以為URI或文本.RDF數(shù)據(jù)可以用一種有向圖來表示,圖中的頂點表示各語句中出現(xiàn)的subject或object,弧表示property.每個弧的起點、終點以及弧本身構(gòu)成了一個語句,其中弧的起點為語句中的subject,弧的終點為語句中的object.例如,在一個網(wǎng)上拍賣系統(tǒng)中,設(shè)Jinling Wang要拍賣一個IBM公司生

19、產(chǎn)的Desktop PC,價格為450美元,其硬盤大小為40G且也由IBM公司生產(chǎn),則相應(yīng)的事件如圖1所示.為簡化起見,在圖1中,我們省略了“daml:Thing”頂點、“rdf:Literal”頂點以及指向它們的弧.RDF規(guī)范中定義了一個屬性“rdf:type”,其主語為某實體,賓語為該實體所屬的類.在RDF圖中,如果某頂點有一個“rdf:type”屬性,則該頂點稱為“帶類型頂點(typed-vertex)”.為了便于處理,在OPS系統(tǒng)中,我們對事件圖作如下限制:1. 圖中有且僅有一個頂點稱為“主頂點(home vertex)”.它描述整個事件的全局信息,例如事件的類型、發(fā)生時間等.我們規(guī)定

20、該頂點的ID為“_:H”.2. 從主頂點到其他任何頂點都存在路徑.3. 每個頂點都為帶類型頂點.用戶可以為某頂點定義多個類,表示該實體同時屬于多個類型.Fig.1 An example of event graph圖1 事件圖示例2.2 概念模型在OPS系統(tǒng)中,我們采用本體來表示事件的概念模型.一般認(rèn)為,本體是一種對概念化結(jié)果的規(guī)范表示22.它描述了某一領(lǐng)域中的各種概念以及它們之間的關(guān)系和應(yīng)滿足的約束等.在語義Web領(lǐng)域中,目前影響較大的本體描述語言是DAML+OIL.在OPS系統(tǒng)中,我們采用該語言來描述事件的概念模型.事件的概念模型通常應(yīng)由領(lǐng)域?qū)＜遗c計算機人員共同創(chuàng)建.目前,國際上也有一些組

21、織致力于領(lǐng)域概念模型的標(biāo)準(zhǔn)化工作,為某些特定領(lǐng)域提供通用的、統(tǒng)一的概念模型.在OPS系統(tǒng)中,事件的概念模型主要由以下3部分組成:1. 各ClassClass之間可以存在多重繼承,但是不允許出現(xiàn)循環(huán)的繼承關(guān)系.例如,一個網(wǎng)上拍賣系統(tǒng)的一部分類層次關(guān)系如圖2(a)所示.如果訂閱條件中有一個類為A,而事件中某個實體的類為B,且A為B的祖先,那么這兩者可以匹配.例如,假設(shè)某人對所有價格小于400美元的計算機感興趣,那么他可以根據(jù)“Computer”類來定義訂閱條件,此后所有價格小于400美元的拍賣臺式機或筆記本電腦的事件都會發(fā)送給他.而現(xiàn)有的pub/sub系統(tǒng)一般只能支持事件類型的層次結(jié)構(gòu),而不能支持

22、事件內(nèi)部實體的類層次結(jié)構(gòu).在這些系統(tǒng)中,如果某人對所有價格小于400美元的計算機感興趣,那么他就必須針對“Computer”的每個子類分別設(shè)置訂閱條件(即價格小于400美元的臺式機、價格小于400美元的筆記本電腦),而這是非常麻煩的.2. 各Property及其層次關(guān)系描述.各Property之間可以存在多重繼承,但是不允許出現(xiàn)循環(huán)的繼承關(guān)系.一個Class可以擁有多個Property,一個Property也可以服務(wù)于多個Class.例如,一個網(wǎng)上拍賣系統(tǒng)的一部分屬性層次關(guān)系如圖2(b)所示.如果訂閱條件中有一個屬性p1,而事件數(shù)據(jù)中有屬性p2,且p1為p2的祖先,那么這兩者可以匹配.例如,假

23、設(shè)某人的訂閱條件為telephoneNumber=“123456789”,而某個事件中的數(shù)據(jù)為cellPhoneNumber=“123456789”,那么該事件與該訂閱條件是相匹配的.3. 元語句(meta-statement).我們稱一個三元組(SubjectClass,property,ObjectClass)為一個“元語句”.它表示對于一個給定的類(SubjectClass),允許有哪些屬性(property),其屬性的值分別屬于哪個類(ObjectClass).例如,一個網(wǎng)上拍賣系統(tǒng)可能包括如下一些元語句:(Selling, seller, Customer)(Selling, tar

24、get,Product)(Product, manufacture, Company)(Customer, name, xsd:string)(a) The hierarchical structure of classes(a) 類層次關(guān)系(b) The hierarchical structure of properties(b) 屬性層次關(guān)系Fig.2 A part of classes and properties in an online auction system圖2 網(wǎng)上拍賣系統(tǒng)的一部分類和屬性不同元語句之間也可以存在層次關(guān)系.對于兩個元語句:ms1=(sc1,p1,oc1)和

25、ms2=(sc2,p2,oc2),如果以下斷言成立:(sc1 rdfs:subClassOf sc2) Ù (p1 rdfs:subPropertyOf p2) Ù (oc1 rdfs:subClassOf oc2),則稱ms2是ms1的“祖先(ancestor)”,記為ms1ms2.其含義是,如果某語句(statement)滿足ms1的類型約束,那么它也一定滿足ms2的類型約束.3 訂閱語言由于在OPS系統(tǒng)中事件被表示為RDF圖,所以用戶的訂閱條件實際上就是一種建立在RDF圖語法之上的圖模式,其中規(guī)定了圖的形狀以及對某些頂點和弧的約束.我們在參考SquishQL23,RQ

26、L24,RDQL25等RDF查詢語言的基礎(chǔ)上,設(shè)計了一種OPS系統(tǒng)的訂閱語言.在OPS系統(tǒng)中,用戶的一個訂閱條件由若干個“語句模式(statement pattern)”的“與”操作組成.每個語句模式描述事件圖中的一個語句,其形式如下:(subject,object,meta-statement,filter_func(object).其中,subject和object規(guī)定了一個語句中的subject和object,它們可以是具體的值,也可以是變量,變量可以與任何具體的值相匹配.變量名以“?”作為前綴,如?1,?2等.語句模式中的meta-statement規(guī)定了一個語句應(yīng)滿足的類型約束,即令

27、某語句模式中的meta-statement為(sc,sp,oc),若某語句(s,p,o)能與該語句模式匹配,則如下斷言為真:s rdf:type scp rdfs:subPropertyOf spo rdf:type oc當(dāng)語句模式中object為變量且其類型為文本時,語句模式中可以有一個過濾函數(shù)filter_func(object),它是一個布爾表達式,用于進一步限制賓語變量的取值.過濾函數(shù)中允許的操作包括>,<,=等關(guān)系運算和正則表達式運算等.例如,在上述網(wǎng)上拍賣系統(tǒng)中,如果某人對所有拍賣計算機且價格小于400美元的事件感興趣,則相應(yīng)的訂閱條件為(_:H, ?1, (Selli

28、ng, target, Computer)(_:H, ?2, (Selling, price, MoneyValue)(?2, units:dollar, (MoneyValue, currency, daml:Thing)(?2, ?3, (MoneyValue, rdf:value, xsd:decimal),?3<400.00)每個訂閱條件在系統(tǒng)內(nèi)部用一個圖來表示,稱為訂閱圖(subscription graph).例如,上述訂閱條件的訂閱圖如圖3所示.Fig. 3 An example of subscription graph圖3 訂閱圖示例在訂閱圖中,每個頂點上的標(biāo)記為(id

29、,type,filter_func(id),它對應(yīng)于事件圖中的一個頂點.其中id為變量名或事件圖中的頂點的標(biāo)記,type為id所對應(yīng)的類.當(dāng)對應(yīng)的事件圖頂點為文本頂點時,可以有一項filter_func(id),表示id應(yīng)滿足的約束.每個弧上的標(biāo)記為屬性名,它和弧起點的type和弧終點的type一起,構(gòu)成一個元語句.該元語句與弧起點的id、弧終點的id以及filter_func(id)一起,構(gòu)成了一個語句模式.我們對用戶的訂閱條件作如下限制:1. 在各語句模式中,至少有一個pattern的subject為“_:H”,即事件的主頂點.我們稱訂閱圖中id=“_:H”的頂點為訂閱圖的“主頂點”.2.

30、 在訂閱圖中,從主頂點到任何其他頂點都存在路徑.4 匹配算法Pub/sub系統(tǒng)的匹配問題的本質(zhì)在于,當(dāng)?shù)竭_一個事件以后,要能快速地找到所有與之匹配的訂閱條件.從這一點上說,pub/sub系統(tǒng)與數(shù)據(jù)庫系統(tǒng)相比,數(shù)據(jù)和查詢(訂閱)條件的角色正好顛倒過來了26.在數(shù)據(jù)庫系統(tǒng)中,大量的數(shù)據(jù)被保存并建立了索引,以便當(dāng)用戶發(fā)起一個查詢條件時,能夠快速地找到所需要的數(shù)據(jù).而在pub/sub系統(tǒng)中,大量的訂閱條件被保存并建立索引,以便當(dāng)?shù)竭_一個事件(數(shù)據(jù))時,能夠快速地找到與之匹配的訂閱條件.下面我們介紹本系統(tǒng)中采用的索引結(jié)構(gòu)以及相應(yīng)的匹配算法.4.1 索引結(jié)構(gòu)我們在用戶所定義的元語句的基礎(chǔ)上,根據(jù)類層次結(jié)構(gòu)

31、和屬性層次結(jié)構(gòu),求出所有合法的元語句,將它們放到一個數(shù)組中,稱為擴展元語句(extended meta-statement,簡稱EMS)數(shù)組.該數(shù)組是OPS系統(tǒng)的索引結(jié)構(gòu)的基礎(chǔ),其中各元語句按字典順序排序,以便于查找.在EMS數(shù)組中,每一項包括兩個鏈表:祖先鏈表(ancestor list)和待匹配項鏈表(waiting-pattern list).祖先鏈表中記錄了此元語句的各祖先在數(shù)組中的序號,待匹配項鏈表中包括了與之相關(guān)的等待匹配的語句模式.初始時,各待匹配項鏈表中只包括各訂閱條件中主語為“_:H”的語句模式.例如,假設(shè)某系統(tǒng)中只有一個如圖4(a)所示的訂閱條件,則初始時EMS數(shù)組如圖4(

32、b)所示.在圖4(b)中,每一項后面的第1個鏈表為祖先鏈表(用實線表示),第2個鏈表為待匹配項鏈表(用虛線表示),nil表示空指針.為了書寫簡便,在圖4以及后面的例子中,我們使用A,B,C等表示類名,使用p1,p2,p3等表示用戶定義的屬性名稱,使用EMS(i)表示EMS數(shù)組中第i項的元語句.4.2 匹配過程和匹配樹當(dāng)一個事件進入OPS系統(tǒng)以后,系統(tǒng)從該事件圖的主頂點開始,按照廣度優(yōu)先的順序,對圖中的各弧進行遍歷,以使得圖中所有標(biāo)記不等于“rdf:type”的弧都被遍歷到,且僅被遍歷一次.對于每個被遍歷到的弧,系統(tǒng)對其生成一個或多個如下形式的三元組:(subject, object, meta

33、-statement),我們稱其為“帶類型語句(typed-statement)”,其中subject是弧的起點的ID,object是弧的終點的ID,meta-statement是此弧所對應(yīng)的語句的元語句.其生成規(guī)則為:令某語句為(s,p,o),所生成的元語句為(ts,tp,to),則ts為事件圖中所指定的s的類,p=tp,to為事件圖中所指定的o的類.一個語句可能會對應(yīng)多個帶類型語句.(a) A subscription(a) 一個訂閱條件(b) The initial state of the EMS array(b) 初始時的EMS數(shù)組Fig.4 A subscription and t

34、he initial state of the EMS array圖4 一個訂閱條件及初始時的EMS數(shù)組對于遍歷事件內(nèi)容時所生成的每個帶類型語句,OPS系統(tǒng)根據(jù)其中的元語句,找到EMS數(shù)組中的相應(yīng)項,將其與待匹配項鏈表中的各語句模式進行匹配.然后,系統(tǒng)還應(yīng)根據(jù)EMS數(shù)組中該項的祖先鏈表,對它的各祖先元語句中的待匹配項鏈表進行匹配.令函數(shù)isVariable(k)表示斷言“k為變量”.對于一個語句模式sp=(s1,o1,ms1,filter_func1)和一個帶類型語句ts=(s2,o2,ms2),sp能與ts匹配的充要條件為(s1=s2 Ú isVariable(s1)Ù(

35、o1=o2 Ú isVariable(o1) Ù (ms2ms1) Ù filter_func1(o2).sp與ts匹配的結(jié)果,是建立了兩對頂點之間的映射:s1«s2,o1«o2.下面研究單個訂閱圖的匹配過程.匹配過程開始時,訂閱圖中以主頂點為起點的各語句模式已位于EMS數(shù)組中的待匹配項鏈表中.對于事件中的每個帶類型語句,系統(tǒng)在EMS數(shù)組中的相應(yīng)待匹配項鏈表中尋找與之匹配的語句模式.如果找到了,就形成了一個部分映射方案,其中記錄了到目前為止的頂點映射.假設(shè)語句模式sp=(s1,o1,ms1,filter_func1)和帶類型語句ts=(s2,o

36、2,ms2)匹配成功,系統(tǒng)需要分如下兩種情況進行處理:1. 如果o1不在從訂閱圖主頂點到s1的當(dāng)前路徑上,那么系統(tǒng)在訂閱圖中找出以o1為起點的其他各語句模式,將其中的變量代換成已有映射方案中的具體值,形成新的語句模式(稱為派生語句模式),放入待匹配項鏈表中以供匹配.2. 如果o1已經(jīng)存在于從訂閱圖主頂點到s1的當(dāng)前路徑上了,那么就不再產(chǎn)生新的語句模式.一個訂閱圖的匹配狀態(tài)可以用一棵樹表示,稱為匹配樹,如圖5所示.訂閱圖的匹配過程可以表示為匹配樹的創(chuàng)建和檢驗過程.圖5(b)為圖5(a)所示的事件與圖4(a)所示的訂閱條件進行匹配時所形成的匹配樹.樹中的圓圈結(jié)點表示部分映射方案,方框結(jié)點表示語句模

37、式.根結(jié)點為圓圈結(jié)點,其中包含一個頂點對“_:H”«“_:H”(在圖中,用“=”表示“«”).根結(jié)點的孩子為訂閱圖中所有主語為“_:H”的各語句模式.一個圓圈結(jié)點下可以有多個方框結(jié)點,表示此次匹配所派生的各語句模式.只有當(dāng)這些語句模式均匹配成功時,圓圈結(jié)點所代表的部分映射方案才是成功的.一個方框結(jié)點下也可以有多個圓圈結(jié)點,表示本語句模式有多種匹配方案.只要其中任何一個匹配方案成功,則此語句模式就匹配成功.由此可見,圓圈結(jié)點反映的是一種“與”關(guān)系,方框結(jié)點反映的是一種“或”關(guān)系,整個匹配樹就是一棵與或樹.(a) An event graph(a) 事件圖(b) The cor

38、responding matching tree(b) 對應(yīng)的匹配樹Fig.5 An example of matching tree圖5 匹配樹示例4.3 匹配樹的檢驗當(dāng)對事件內(nèi)容遍歷完成之后,系統(tǒng)就生成了各訂閱圖所對應(yīng)的匹配樹.然后,系統(tǒng)需要根據(jù)每個匹配樹來判斷相應(yīng)的訂閱圖是否匹配成功,我們稱這一過程為匹配樹的檢驗(verification).OPS系統(tǒng)采用兩種方法來對匹配樹進行檢驗:基于布爾表達式的檢驗方法(boolean expression based verification,簡稱BEBV)和基于狀態(tài)的部分檢驗方法(state based partial verification,

39、簡稱SBPV).BEBV方法對每個葉子結(jié)點賦一個布爾表達式,然后對整個匹配樹進行表達式求值,以判斷匹配是否成功.其規(guī)則如下:1. 若葉子結(jié)點為圓圈結(jié)點,且其中的頂點映射為v1SG«vx1EG,v2SG«vx2EG,vkSG«vxkEG,則對應(yīng)的表達式為(v1SG«vx1EG)Ù(v2SG«vx2EG)ÙÙ(vkSG«vxkEG).2. 若葉子結(jié)點為方框結(jié)點,則對應(yīng)的表達式為false.3. 每個非葉子圓圈結(jié)點的表達式為其下各孩子結(jié)點的表達式的“與”運算,每個非葉子方框結(jié)點的表達式為其下各孩子結(jié)點的表達式的

40、“或”運算.4. 對于訂閱圖中的任意頂點viSG和事件圖中的兩個頂點vxEG,vyEG,表達式(viSG«vxEG)Ù(viSG«vyEG)Ù (vxEG¹vyEG)的值為false,即訂閱圖中的一個頂點不能同時映射到事件圖中的兩個不同頂點.5. 對于事件圖中的任意頂點viEG和訂閱圖中的兩個頂點vxSG,vySG,表達式(vxSG«viEG)Ù(vySG«viEG)Ù (vxSG¹vySG)的值為false,即事件圖中的一個頂點不能同時映射到訂閱圖中的兩個不同頂點.根據(jù)上述規(guī)則對匹配樹從底向上

41、計算,如果根結(jié)點的值為false,則表示匹配失敗,否則,匹配成功.然而,如果對每個匹配樹都進行上述表達式求值,那么將是非常低效的.因此,我們又設(shè)計了一種匹配樹檢驗方法SBPV方法,它能夠以很低的成本檢查出大部分匹配失敗的匹配樹,但不能最終確定一個訂閱是否匹配成功.只有通過了SBPV檢查后的匹配樹,才利用BEBV方法來判斷其是否匹配成功.SBPV方法對匹配樹中的每個結(jié)點定義兩種狀態(tài):checked和unchecked.checked表示該結(jié)點已通過SBPV檢驗,unchecked表示尚未完成檢驗.初始時,各結(jié)點的狀態(tài)均為unchecked.對于方框結(jié)點,只要它有一個孩子的狀態(tài)變?yōu)閏hecked,

42、其狀態(tài)就變?yōu)閏hecked.對于圓圈結(jié)點,當(dāng)其所有孩子的狀態(tài)都為checked時,其狀態(tài)才變?yōu)閏hecked.每個圓圈結(jié)點中有一個unCheckedChildren字段,表示它所擁有的狀態(tài)為unchecked的孩子總數(shù).在匹配樹的創(chuàng)建過程中,當(dāng)某個圓圈結(jié)點不能派生出新的語句模式時,系統(tǒng)將對匹配樹進行回溯,以調(diào)整其上層結(jié)點的狀態(tài).其步驟如下:1) 將當(dāng)前結(jié)點的狀態(tài)置為checked.2) 如果本結(jié)點為圓圈結(jié)點:a) 若它是根結(jié)點,則回溯過程結(jié)束.b) 若它不是根結(jié)點,檢查父結(jié)點的狀態(tài)是否為checked.若是,回溯過程結(jié)束.若不是,則將父結(jié)點作為當(dāng)前結(jié)點,遞歸調(diào)用本回溯過程.3) 如果本結(jié)點為方

43、框結(jié)點,則將父結(jié)點的unCheckedChildren減1.如果該值變?yōu)?,則置父結(jié)點為當(dāng)前結(jié)點,遞歸調(diào)用本回溯過程,否則回溯過程結(jié)束.當(dāng)SBPV檢查完成以后,如果匹配樹的根結(jié)點的狀態(tài)為unchecked,則表示匹配失敗.由于SBPV檢查可以在匹配樹的創(chuàng)建時同步完成,所以當(dāng)系統(tǒng)對事件內(nèi)容遍歷完成之后,只需對那些根結(jié)點狀態(tài)為checked的匹配樹進行BEBV檢查,從而可以大大提高處理的效率.4.4 算法分析令TS表示平均每個事件中的帶類型語句個數(shù),D表示EMS數(shù)組中平均每個元語句所能推導(dǎo)的元語句個數(shù),W表示平均每個待匹配項鏈表中的結(jié)點數(shù),SP表示各匹配樹中平均每個圓圈結(jié)點下的語句模式個數(shù),則由算

44、法中的循環(huán)層次可知,本算法的時間復(fù)雜度為O(TS´D´W´SP).一般來說,TS,D,SP的值都比較小,且不受訂閱數(shù)量的影響,而W的值則可能會隨著訂閱數(shù)量的增加而增加.設(shè)系統(tǒng)中的訂閱數(shù)量為n,EMS數(shù)組中元語句數(shù)量為m,平均每個匹配樹中的語句模式數(shù)量為sp,則W»(n´sp)¸m.因此,本算法的時間復(fù)雜度與訂閱數(shù)量呈線性關(guān)系.在空間復(fù)雜度方面,本算法的空間占用主要包括以下兩個方面:(1) 各訂閱條件所對應(yīng)的匹配樹.匹配樹中的結(jié)點個數(shù)由訂閱圖和事件圖決定,與訂閱條件數(shù)量無關(guān).(2) EMS數(shù)組(不包括其中的待匹配項鏈表,因為該鏈表中的結(jié)

45、點同時也在匹配樹中).其大小由事件的概念模型決定.設(shè)匹配樹的平均大小為mt,EMS數(shù)組中每一項的空間占用為e(不包括其中的待匹配項鏈表),則本算法的空間復(fù)雜度為O(n´mt+m´e).因此,總的來說,本算法的空間復(fù)雜度與訂閱數(shù)量呈線性關(guān)系.5 實 驗我們對OPS原型系統(tǒng)進行了模擬實驗,以驗證系統(tǒng)的正確性并對其性能進行評價.原型系統(tǒng)采用Java語言開發(fā),實驗所使用的機器是一臺CPU為Intel Pentium IV 1.6GHz,內(nèi)存為512M的普通筆記本電腦,所使用的操作系統(tǒng)為Windows 2000 Server,Java運行環(huán)境為JDK 1.4.1.在模擬實驗中,我們假

46、設(shè)事件概念模型中有10個類和10個屬性,每個類有兩個屬性,類之間和屬性之間都不存在繼承關(guān)系.id為“_:H”,其他頂點的id均為變量.每個頂點的type都是隨機產(chǎn)生的,各頂點中均不含有過濾函數(shù).圖6(a)顯示了本系統(tǒng)在不同訂閱數(shù)量下的匹配時間,其中訂閱數(shù)量從500增加到10 000.在這組實驗中,平均匹配成功率為3%.從圖中我們可以看出,本系統(tǒng)的匹配時間與訂閱數(shù)量基本上呈線性關(guān)系.當(dāng)訂閱數(shù)量為 10 000時,匹配時間僅為1.2s.圖6(b)顯示了本系統(tǒng)在不同訂閱數(shù)量下的空間占用情況,其中Y5個左右,不隨訂閱數(shù)量的變化而變化.所以,本算法的空間復(fù)雜度與訂閱數(shù)量呈線性關(guān)系.(a) Matchin

47、g time(a) 匹配時間(b) Space usage(b) 空間占用情況Fig. 6 The experimental result圖6 實驗結(jié)果6 結(jié) 論我們將語義Web技術(shù)與發(fā)布/訂閱技術(shù)結(jié)合起來,提出了一種新型的發(fā)布/訂閱系統(tǒng).該系統(tǒng)能夠利用事件的語義知識,提供更為準(zhǔn)確的匹配,同時能夠支持具有復(fù)雜數(shù)據(jù)結(jié)構(gòu)(如圖狀結(jié)構(gòu))的事件.在本系統(tǒng)中,事件概念模型是用DAML+OIL語言來描述的.該語言具有較強的描述能力,能夠?qū)︻惡蛯傩赃M行多種語義約束,而本系統(tǒng)只利用了其描述能力的一小部分.我們下一步的工作將是進一步改進本系統(tǒng)的概念模型,使其能夠包含更為豐富的語義知識,以進一步提高訂閱匹配的準(zhǔn)確

48、度和效率.References:1 Eugster PT, Felber PA, Guerraoui R, Kermarrec AM. The many faces of publish/subscribe. ACM Computing Surveys, 2003,35(2): 114-131.2 Lassila O, Swick RR. Resource description framework (RDF) model and syntax specification. 19993 Berners-Lee T. Using XML for data. 20014 IBM. Internet

49、 Application Development with MQSeries and Java. Palos Verdes: Vervante Corporate Publishing, 1997.5 Carzaniga A, Rosenblum DS, Wolf AL. Design and evaluation of a wide-area event notification service. ACM Trans. on Computer Systems, 2001,19(3):332-3836 Aguilera MK, Strom RE, Sturman DC, Astley M, C

50、handra TD. Matching events in a content-based subscription system. In: Proc. of the 18th ACM Symp. on Principles of Distributed Computing. New York: ACM Press, 1999. 53-61.7 Cugola G, Nitto ED, Fuggetta A. The JEDI event-based infrastructure and its application to the development of the OPSS WFMS. I

51、EEE Trans. on Software Engineering, 2001,27(9):827-850.8 Wray M, Hawkes R. Distributed virtual environments and VRML: An event-based architecture. In: Proc. of the 7th Intl World Wide Web Conf. (WWW7). Amsterdam: Elsevier Science Publishers, 1998. 43-51.9 Fitzpatrick G, Kaplan S, Mansfield T, David

52、A, Segall B. Supporting public availability and accessibility with Elvin: Experiences and reflections. Computer Supported Cooperative Work, 2002,11(3):447-474.10 Altinel M, Franklin MJ. Efficient filtering of XML documents for selective dissemination of information. In: Proc. of the 26th Intl Conf.

53、on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2000. 53-64.11 Chan CY, Felber P, Garofalakis M, Rastogi R. Efficient filtering of XML documents with XPath expressions. The VLDB Journal, 2002,11(4):354-379.12 Pereira J, Fabret F, Llirbat F, Jacobsen HA, Shasha D. WebFilter: A hi

54、gh throughput XML-based publish and subscribe system. In: Proc. of the 27th Intl Conf. on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2001. 723-724.13 Petrovic M, Burcea I, Jacobsen HA. S-ToPSS: Semantic toronto publish/subscribe system. In: Proc. of the 29th Intl Conf. on Very

55、 Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2003. 1101-1104.14 Cilia M, Bornhoevd C, Buchmann AP. CREAM: An infrastructure for distributed, heterogeneous event-based applications. In: Proc. of the Intl Conf. on Cooperative Information Systems (CoopIS). London: Springer-Verlag, 2003. 482-502.15 Yan T