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

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

2、nt No.2002CB312005 (國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973)作者簡(jiǎn)介: 汪錦嶺(1974),男,安徽廬江人,博士,主要研究領(lǐng)域?yàn)榉植际接?jì)算,中間件技術(shù);金蓓弘(1967),女,博士,副研究員,CCF高級(jí)會(huì)員,主要研究領(lǐng)域?yàn)榉植际接?jì)算,軟件工程技術(shù);李京(1966),男,博士,研究員,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)檐浖w系結(jié)構(gòu),組合軟件技術(shù);邵丹華(1971),男,工程師,主要研究領(lǐng)域?yàn)橹虚g件技術(shù).汪錦嶺1,2+, 金蓓弘1, 李 京1, 邵丹華11(中國(guó)科學(xué)院 軟件研究所 軟件工程技術(shù)中心,北京 100080)2(中國(guó)科學(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ù)事件的語(yǔ)義來(lái)進(jìn)行事件與訂閱的匹配,且不能支持具有復(fù)雜結(jié)構(gòu)(如圖狀結(jié)構(gòu))的事件.將語(yǔ)義Web技術(shù)引入發(fā)布/訂閱系統(tǒng)中,提出一種基于本體的發(fā)布/訂閱系統(tǒng).該系統(tǒng)采用本體來(lái)表示事件的概念模型,采用RDF圖來(lái)表示事件,采用圖模式來(lái)表示訂閱條件.它能較好地解決現(xiàn)有的發(fā)布/訂閱系統(tǒng)的上述問(wèn)題.實(shí)驗(yàn)結(jié)果表明,該系統(tǒng)具有較高的訂閱匹配效率.關(guān)鍵詞:發(fā)布/訂閱;本體;RDF;匹配算法中圖法分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、設(shè)某人的訂閱條件為telephoneNumber=“123456789”,而某個(gè)事件中的數(shù)據(jù)為cellPhoneNumber=“123456789”,那么該事件與該訂閱條件是相匹配的.3. 元語(yǔ)句(meta-statement).我們稱一個(gè)三元組(SubjectClass,property,ObjectClass)為一個(gè)“元語(yǔ)句”.它表示對(duì)于一個(gè)給定的類(SubjectClass),允許有哪些屬性(property),其屬性的值分別屬于哪個(gè)類(ObjectClass).例如,一個(gè)網(wǎng)上拍賣系統(tǒng)可能包括如下一些元語(yǔ)句:(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)的一部分類和屬性不同元語(yǔ)句之間也可以存在層次關(guān)系.對(duì)于兩個(gè)元語(yǔ)句: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.其含義是,如果某語(yǔ)句(statement)滿足ms1的類型約束,那么它也一定滿足ms2的類型約束.3 訂閱語(yǔ)言由于在OPS系統(tǒng)中事件被表示為RDF圖,所以用戶的訂閱條件實(shí)際上就是一種建立在RDF圖語(yǔ)法之上的圖模式,其中規(guī)定了圖的形狀以及對(duì)某些頂點(diǎn)和弧的約束.我們?cè)趨⒖糞quishQL23,RQ

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

27、某語(yǔ)句模式中的meta-statement為(sc,sp,oc),若某語(yǔ)句(s,p,o)能與該語(yǔ)句模式匹配,則如下斷言為真:s rdf:type scp rdfs:subPropertyOf spo rdf:type oc當(dāng)語(yǔ)句模式中object為變量且其類型為文本時(shí),語(yǔ)句模式中可以有一個(gè)過(guò)濾函數(shù)filter_func(object),它是一個(gè)布爾表達(dá)式,用于進(jìn)一步限制賓語(yǔ)變量的取值.過(guò)濾函數(shù)中允許的操作包括>,<,=等關(guān)系運(yùn)算和正則表達(dá)式運(yùn)算等.例如,在上述網(wǎng)上拍賣系統(tǒng)中,如果某人對(duì)所有拍賣計(jì)算機(jī)且價(jià)格小于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)每個(gè)訂閱條件在系統(tǒng)內(nèi)部用一個(gè)圖來(lái)表示,稱為訂閱圖(subscription graph).例如,上述訂閱條件的訂閱圖如圖3所示.Fig. 3 An example of subscription graph圖3 訂閱圖示例在訂閱圖中,每個(gè)頂點(diǎn)上的標(biāo)記為(id

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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