機(jī)器學(xué)習(xí)論文-基于本體的發(fā)布_訂閱系統(tǒng)的數(shù)據(jù)模型和匹配算法-文庫吧資料
2025-06-14 05:10本頁面
【正文】 2), 則稱 ms2是 ms1的 “祖先 (ancestor)”,記為 ms1 ,如果某語句 (statement)滿足 ms1的類型約束 ,那么它也一定滿足 ms2的類型約束 . C o n t a c t I n f o r m a t i o nT e l e p h o n e n u m b e rP o s t a l A d d r e s sH o m e p h o n e n u m b e rC e l l p h o n e n u m b e rP r o d u c tC o m p u t e r D i g i t a l P r o d u c tD e s k t o p P C N o t e b o o k PCB o o kE B o o k MP 3 D i g i t a l p r o d u c t C o n t a c t i f r ma t i P o st a l a d r e ss (a) The hierarchical structure of classes (a) 類層次關(guān)系 (b) The hierarchical structure of properties (b) 屬性層次關(guān)系 3 訂閱語言 由于在 OPS 系統(tǒng)中事件被表示為 RDF 圖 ,所以用戶的訂閱條件實(shí)際上就是一種建立在RDF 圖語法之上的圖模式 ,其中規(guī)定了圖的形狀以及對某些頂點(diǎn)和弧的約束 .我們在參考SquishQL[23],RQL[24],RDQL[25]等 RDF 查詢語言的基礎(chǔ)上 ,設(shè)計(jì)了一種 OPS 系統(tǒng)的訂閱語言 . 在 OPS 系統(tǒng)中 ,用戶的一個(gè)訂閱條件由若干個(gè) “語句模式 (statement pattern)”的 “與 ”操作組成 .每個(gè)語句模式描述事件圖中的一個(gè)語句 ,其形式如下 : (subject,object,metastatement,[filter_func(object)]). 其中 ,subject和 object規(guī)定了一個(gè)語句中的 subject和 object,它們可以是具體的值 ,也可以是變量 ,變量可以與任何具體的值相匹配 .變量名以 “?”作為前綴 ,如 ?1,?2 等 . 語句模式中的 metastatement 規(guī)定了一個(gè)語句應(yīng)滿足的類型約束 ,即令某語句模式中的metastatement 為 (sc,sp,oc),若某語句 (s,p,o)能與該語句模式匹配 ,則如下斷言為真 : s rdf:type sc p rdfs:subPropertyOf sp o rdf:type oc 當(dāng)語句模式中 object 為變量且其類型為文本時(shí) ,語句模式中可以有一個(gè)過濾函數(shù)filter_func(object),它是一個(gè)布爾表達(dá)式 ,用于進(jìn)一步限制賓語變量的取值 .過濾函數(shù)中允許的操作包括 ,=等關(guān)系運(yùn)算和正則表達(dá)式運(yùn)算等 . 例如 ,在上述網(wǎng)上拍賣系統(tǒng)中 ,如果某人對所有拍賣計(jì)算機(jī)且價(jià)格小于 400 美元的 事件感興趣 ,則相應(yīng)的訂閱條件為 (_:H, ?1, (Selling, target, Computer)) (_:H, ?2, (Selling, price, MoneyValue)) (?2, units:dollar, (MoneyValue, currency, daml:Thing)) (?2, ?3, (MoneyValue, rdf:value, xsd:decimal),?3) 每個(gè)訂閱條件在系統(tǒng)內(nèi)部用一個(gè)圖來表示 ,稱為訂閱圖 (subscription graph).例如 ,上述訂閱條件的訂閱圖如圖 3 所示 . _ : H , S e l l i n g? 2 , M o n e y V a l u eu n i t s : d o l l a r , d a m l : T h i n gp r i c ec u r r e n c y? 3 , x s d : d e c i m a l , ? 3 4 0 0r d f : v a l u e? 1 , C o m p u t e rt a r g e t Fig. 3 An example of subscription graph 圖 3 訂閱圖示例 在訂閱圖中 ,每個(gè)頂點(diǎn)上的標(biāo)記為 (id,type,[filter_func(id)]),它對應(yīng)于事件圖中的一個(gè)頂點(diǎn) .其中 id 為變量名或事件圖中的頂點(diǎn)的標(biāo)記 ,type 為 id 所對應(yīng)的類 .當(dāng)對應(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è) 元語句 .該元語句與弧起點(diǎn)的 id、弧終點(diǎn)的 id 以及filter_func(id)一起 ,構(gòu)成了一個(gè)語句模式 . 我們對用戶的訂閱條件作如下限制 : 1. 在各 語句模式 中 ,至少有一個(gè) pattern的 subject為 “_:H”,即事件的主頂點(diǎn) .我們稱訂閱圖中id=“_:H”的頂點(diǎn)為訂閱圖的 “主頂點(diǎn) ”. 2. 在訂閱圖中 ,從主頂點(diǎn)到任何其他頂點(diǎn)都存在路徑 . 4 匹配算法 Pub/sub 系統(tǒng)的匹配問題的本質(zhì)在于 ,當(dāng)?shù)竭_(dá)一個(gè)事件以后 ,要能快速地找到所有與之匹配的訂閱條件 .從這一點(diǎn)上說 ,pub/sub 系統(tǒng)與數(shù)據(jù)庫系統(tǒng)相比 ,數(shù)據(jù)和查詢 (訂閱 )條件的角色正好顛倒過來了 [26].在數(shù)據(jù)庫系統(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)的匹配算法 . 索引結(jié)構(gòu) 我們在用戶所定義的 元語句 的基礎(chǔ)上 ,根據(jù)類層次結(jié)構(gòu)和屬性層次結(jié)構(gòu) ,求出所有合法的元語句 ,將它們放到一個(gè)數(shù)組中 ,稱為擴(kuò)展 元語句 (extended metastatement,簡稱 EMS)數(shù)組 .該數(shù)組是 OPS 系統(tǒng)的索引結(jié)構(gòu)的基礎(chǔ) ,其中各 元語句 按字典順序排序 ,以便于查找 . 在 EMS 數(shù)組中 ,每一項(xiàng)包括兩個(gè)鏈表 :祖先鏈表 (ancestor list)和待匹配項(xiàng)鏈表(waitingpattern list).祖先鏈表中記錄了此 元語句 的各祖先在數(shù)組中的序號 ,待匹配項(xiàng)鏈表中包括了與之相關(guān)的等待匹配的語句模式 .初始時(shí) ,各待匹配項(xiàng)鏈表中只包括各訂閱條件中主語為“_:H”的語句模式 . 例如 ,假設(shè)某系統(tǒng)中只有一個(gè)如圖 4(a)所示的訂閱條件 ,則初始時(shí) EMS 數(shù)組如 圖 4(b)所示 . 在圖 4(b)中 ,每一項(xiàng)后面的第 1 個(gè)鏈表為祖先鏈表 (用實(shí)線表示 ),第 2 個(gè)鏈表為待匹配項(xiàng)鏈表 (用虛線表示 ),nil 表示空指針 .為了書寫簡便 ,在圖 4 以及后面的例子中 ,我們使用 A,B,C 等表示類名 ,使用 p1,p2,p3等表示用戶定義的屬性名稱 ,使用 EMS(i)表示 EMS 數(shù)組中第 i 項(xiàng)的元語句 . 匹配過程和匹配樹 當(dāng)一個(gè)事件進(jìn)入 OPS 系統(tǒng)以后 ,系統(tǒng)從該事件圖的主頂點(diǎn)開始 ,按照廣度優(yōu)先的順序 ,對圖中的各弧進(jìn)行遍歷 ,以使得圖中所有標(biāo)記不等于 “rdf:type”的弧都被遍歷到 ,且僅被遍歷一次 .對于每個(gè)被遍歷 到的弧 ,系統(tǒng)對其生成一個(gè)或多個(gè)
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1