大規(guī)模RDF圖數(shù)據(jù)的屬性路徑查詢及推理研究.pdf

1、屬性路徑查詢（Property Paths Query）是RDF圖數(shù)據(jù)管理中的一種基本查詢，由 SPARQL1.1引入，并成為 W3C的官方推薦標(biāo)準(zhǔn)?，F(xiàn)有的屬性路徑查詢方案均基于多重索引，經(jīng)過多次迭代查詢實(shí)現(xiàn)，效率低下，且不具備推理能力。由于開放鏈接數(shù)據(jù)運(yùn)動(dòng)（LOD）的開展，互聯(lián)網(wǎng)上RDF數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，海量RDF三元組數(shù)據(jù)構(gòu)成了一個(gè)巨大的圖。在如此大規(guī)模的圖數(shù)據(jù)上進(jìn)行高效的屬性路徑查詢，是一個(gè)有意義，且很具有挑戰(zhàn)性的工作。

2、　　本文主要做了兩方面工作。首先，針對(duì)Property Paths不支持嵌套語(yǔ)法，無法表達(dá)部分RDFS（RDF Schema）語(yǔ)義的問題，實(shí)現(xiàn)了RDF-Plus原型系統(tǒng)。采用基于自動(dòng)機(jī)的算法，隱式添加推理規(guī)則，將Property Paths轉(zhuǎn)化為嵌套正則表達(dá)式，在不改變?cè)械臅r(shí)間復(fù)雜度的基礎(chǔ)上，實(shí)現(xiàn)了對(duì)RDFS推理的支持，豐富了查詢結(jié)果，提高了準(zhǔn)確率和召回率。其次，針對(duì)隨著數(shù)據(jù)量的爆炸式增長(zhǎng)，單機(jī)的計(jì)算和存儲(chǔ)能力無法滿足計(jì)算需求的問題，

3、結(jié)合Google近年提出的Pregel模型和其開源實(shí)現(xiàn)Giraph，設(shè)計(jì)了一種并行算法，通過一次消息擴(kuò)散和一次回溯求解。算法不僅可以得到符合查詢的所有結(jié)果，且可以把中間結(jié)果作為子圖返回，查詢結(jié)果直觀且表達(dá)力強(qiáng)。
　　綜上所述，本文基于嵌套正則表達(dá)式和自動(dòng)機(jī)理論提出的屬性路徑查詢解決方案，可以結(jié)合RDFS語(yǔ)義進(jìn)行推理，在保持原有的計(jì)算復(fù)雜度的同時(shí)，提供更全面的查詢結(jié)果。基于Pregel模型將單機(jī)算法并行化，有效提高了系統(tǒng)的查詢速度，