發(fā)布時(shí)間：2021-01-20 04:16

　　在SPARQL查詢過程中,含有復(fù)雜結(jié)構(gòu)的資源描述框架（RDF）圖的查詢效率低下。為此,通過分析幾種RDF圖的基本結(jié)構(gòu)與RDF頂點(diǎn)的選擇性,提出RDF三元組模式選擇性（RTPS）——一種基于RDF頂點(diǎn)選擇性的圖結(jié)構(gòu)切分規(guī)則,以提高面向RDF圖的子圖匹配效率。首先,根據(jù)謂詞結(jié)構(gòu)在數(shù)據(jù)圖與查詢圖中的通性建立RDF相鄰謂詞路徑（RAPP）索引,將數(shù)據(jù)圖結(jié)構(gòu)轉(zhuǎn)化為傳入-傳出雙向謂詞路徑結(jié)構(gòu)以確定查詢頂點(diǎn)的搜索空間,并加快頂點(diǎn)的過濾;接著,通過整數(shù)線性規(guī)劃（ILP）問題計(jì)算建模將復(fù)雜RDF查詢圖結(jié)構(gòu)分解為若干結(jié)構(gòu)簡單的查詢子圖,通過分析RDF頂點(diǎn)在查詢圖中的相鄰子圖結(jié)構(gòu)與特征,確立查詢頂點(diǎn)的選擇性以確定最優(yōu)切分方式;然后,通過RDF頂點(diǎn)選擇性與相鄰子圖的結(jié)構(gòu)特征來縮小查詢頂點(diǎn)的搜索空間范圍,并在數(shù)據(jù)圖中找到符合條件的RDF頂點(diǎn);最后,遍歷數(shù)據(jù)圖以找到與查詢子圖結(jié)構(gòu)相匹配的子圖結(jié)構(gòu),將得到的子圖進(jìn)行連接并將其作為查詢結(jié)果輸出。實(shí)驗(yàn)采用控制變量法,比較了RTPS、RDF子圖匹配（RSM）、RDF-3X、Gra SS與R3F的查詢響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果充分表明,與其他4種方法相比,當(dāng)查詢圖復(fù)雜度高于9時(shí),R... 

【文章來源】：計(jì)算機(jī)應(yīng)用. 2019,39(02)北大核心

【文章頁數(shù)】：10 頁

【部分圖文】：

ＲDF數(shù)據(jù)圖示例Fig．3ExampleofＲDFdatagraph從定義1與定義2對(duì)謂詞的

閃教蹺醬事肪?組成了ＲDF頂點(diǎn)的相鄰謂詞結(jié)構(gòu)，根據(jù)ＲAPP索引，對(duì)ＲDF頂點(diǎn)的相鄰謂詞結(jié)構(gòu)定義如下。定義4ＲDF頂點(diǎn)的相鄰謂詞結(jié)構(gòu)。以APS(v)=〈v，p，p'，ppl〉來表示數(shù)據(jù)圖中ＲDF頂點(diǎn)的相鄰謂詞結(jié)構(gòu)。其中:v是當(dāng)前ＲDF頂點(diǎn);p是頂點(diǎn)的傳入謂詞結(jié)構(gòu);p'是頂點(diǎn)的傳出謂詞結(jié)構(gòu);ppl為傳入謂詞路徑與傳出謂詞路徑的最大長度，基于本文的ＲAPS索引的深度為3，ppl的范圍設(shè)置為ppl=∈{1，2}。根據(jù)ＲAPP索引樹中的謂詞路徑結(jié)構(gòu)，將圖3數(shù)據(jù)圖中的ＲDF頂點(diǎn)分類存儲(chǔ)到相應(yīng)的Vlist中，存儲(chǔ)結(jié)果如表1所示。在本文的方法中，ＲAPP索引樹的深度為3(MaxL=2)，即謂詞路徑的最大長度為2，這樣可以避免因謂詞種類關(guān)聯(lián)過多而產(chǎn)生的存儲(chǔ)空間冗余。2．3確定查詢頂點(diǎn)的搜索空間在ＲAPP索引建立后，通過索引在數(shù)據(jù)圖中進(jìn)行ＲDF頂點(diǎn)的遍歷，將頂點(diǎn)根據(jù)與其相連的謂詞結(jié)構(gòu)分類存儲(chǔ)到ＲAPP索引樹中的謂詞節(jié)點(diǎn)上，根據(jù)查詢圖中查詢頂點(diǎn)的相鄰謂詞結(jié)構(gòu)來定義查詢頂點(diǎn)的初始搜索空間。本文引用了gStore［16］中提出的子圖匹配原則定理，引理如下:引理1子圖匹配原則定理。在面向ＲDF的子圖匹配中，一個(gè)查詢頂點(diǎn)的綁定頂點(diǎn)，其標(biāo)簽值、與其相連的謂詞結(jié)第2期關(guān)皓元等:基于資源描述框架圖切分與頂點(diǎn)選擇性的高效子圖匹配方法363


本文編號(hào)：2988352