基于有序二叉樹(shù)的RDF存儲(chǔ)模型研究

李心科， 秦冬生

（合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

0 引 言

語(yǔ)義網(wǎng)作為第三代Web正越來(lái)越受到業(yè)界的青睞。語(yǔ)義網(wǎng)中的資源以RDF進(jìn)行描述，基于RDF框架描述的語(yǔ)義Web數(shù)據(jù)不僅可以被人理解，而且可以被機(jī)器自動(dòng)地共享和處理，從而實(shí)現(xiàn)了Web信息的自動(dòng)處理，提高了Web數(shù)據(jù)的利用率。語(yǔ)義網(wǎng)的不斷發(fā)展使得語(yǔ)義數(shù)據(jù)大量增加，原始簡(jiǎn)易的存儲(chǔ)模式不可避免地遭遇了性能的瓶頸，從存儲(chǔ)能力到響應(yīng)性能上都已不能滿(mǎn)足用戶(hù)日益增長(zhǎng)的需求。為了解決上述問(wèn)題，不少研究人員關(guān)注語(yǔ)義網(wǎng)與云計(jì)算相結(jié)合的可能性。

近年來(lái)，云計(jì)算領(lǐng)域得到了快速發(fā)展，Google發(fā)表的分布式文件系統(tǒng)GFS、分布式數(shù)據(jù)庫(kù)Big－Table及并行計(jì)算框架MapReduce等成果是當(dāng)前云計(jì)算研究領(lǐng)域的熱點(diǎn)之一。上述技術(shù)在Google的各項(xiàng)應(yīng)用中得到了大量的使用，在開(kāi)源社區(qū)也出現(xiàn)了與之對(duì)應(yīng)的開(kāi)源實(shí)現(xiàn)，Apache Hadoop［1］是其中應(yīng)用最廣泛的項(xiàng)目。這些開(kāi)源分布式項(xiàng)目的涌現(xiàn)以及云計(jì)算本身具有的海量數(shù)據(jù)存儲(chǔ)和處理能力，使得不少研究人員試圖將云計(jì)算與語(yǔ)義Web結(jié)合起來(lái)解決海量語(yǔ)義Web數(shù)據(jù)存儲(chǔ)和查詢(xún)問(wèn)題，該方面的研究尚處于起步階段。

傳統(tǒng)的RDF存儲(chǔ)系統(tǒng)主要依托RDBMS和一些底層的存儲(chǔ)載體，Vertically Partitioned方法［2］、Hexastore方案［3］及Jena系統(tǒng)［4］等均是經(jīng)典的解決方案。

傳統(tǒng)集中式的RDF存儲(chǔ)系統(tǒng)已無(wú)法滿(mǎn)足RDF數(shù)據(jù)爆炸式增長(zhǎng)的趨勢(shì)，研究人員開(kāi)始將目光轉(zhuǎn)向分布式領(lǐng)域。分布式系統(tǒng)所具有的海量數(shù)據(jù)存儲(chǔ)和并行計(jì)算能力被認(rèn)為是解決海量RDF數(shù)據(jù)存儲(chǔ)難題的一個(gè)適宜的解決方案。

對(duì)于現(xiàn)有的分布式存儲(chǔ)方案，研究人員從存儲(chǔ)模型定義、底層存儲(chǔ)系統(tǒng)選擇及查詢(xún)連接處理等不同角度提出了新的解決方案。文獻(xiàn)［5］提出一個(gè)在hadoop上存儲(chǔ)RDF數(shù)據(jù)的方案，在RDF數(shù)據(jù)存儲(chǔ)方面，將RDF文檔數(shù)據(jù)存儲(chǔ)在hdfs中，在查詢(xún)方面，實(shí)現(xiàn)了啟發(fā)式搜索算法。文獻(xiàn)［6］給出一種處理RDF數(shù)據(jù)查詢(xún)的MapReduce多路連接策略，該策略很好地解決了RDF數(shù)據(jù)查詢(xún)中連接操作復(fù)雜問(wèn)題。文獻(xiàn)［7］實(shí)現(xiàn)了hadoop與傳統(tǒng)RDF管理框架sesame相結(jié)合的RDF數(shù)據(jù)存儲(chǔ)系統(tǒng)HadoopRDF。文獻(xiàn)［8］提出了基于HBASE的RDF存儲(chǔ)系統(tǒng)。但現(xiàn)有的分布式解決方案都存在著文件索引結(jié)構(gòu)復(fù)雜、查詢(xún)響應(yīng)策略不能保證查詢(xún)效率等問(wèn)題。

本文提出一種適合于云計(jì)算環(huán)境的RDF數(shù)據(jù)存儲(chǔ)和查詢(xún)方案。為支持海量RDF數(shù)據(jù)的存儲(chǔ)和快速查詢(xún)，提出基于有序二叉樹(shù)結(jié)構(gòu)的語(yǔ)義Web數(shù)據(jù)存儲(chǔ)模型，該模型封裝RDF文本數(shù)據(jù)信息到二叉樹(shù)節(jié)點(diǎn)中，實(shí)現(xiàn)了語(yǔ)義Web數(shù)據(jù)分類(lèi)存儲(chǔ)，此外為了提高數(shù)據(jù)查詢(xún)效率，引入了排序權(quán)值和結(jié)點(diǎn)層次的概念。

1 基于有序二叉樹(shù)的RDF存儲(chǔ)模型

RDF數(shù)據(jù)指以RDF三元組形式組織的語(yǔ)義網(wǎng)數(shù)據(jù)，通常由RDF、RDFS或 OWL語(yǔ)言及RDF圖模型描述。RDF圖以有向圖作為存儲(chǔ)模型，其中主體和客體作為節(jié)點(diǎn)，謂詞充當(dāng)邊，邊的方向由主體指向客體。依據(jù)文獻(xiàn)［9］的方法給出RDF圖的定義。

1.1 RDF圖存儲(chǔ)模型

定義1 設(shè)U、B、L分別表示資源集合、空節(jié)點(diǎn)集合以及文字集合，RDF數(shù)據(jù)用主體、謂詞、客體三元組表示，其中，主體∈（U∪B ），謂詞∈U，客體∈ （U∪B∪L） 。RDF圖為RDF三元組的集合，圖中的每個(gè)三元組表示一個(gè)節(jié)點(diǎn)－邊－節(jié)點(diǎn)的連接。資源集合為Web上以URI標(biāo)識(shí)的事物集合，文字集合包括所有字符串或數(shù)據(jù)類(lèi)型的值，空節(jié)點(diǎn)集合則是所有起連通作用的匿名資源。

實(shí)際的RDF圖如圖1所示。

圖1 RDF圖

圖1 所表述的含義是論文article1的第1作者、第2作者均來(lái)自同一學(xué)校hfut，且第1作者的學(xué)號(hào)為2010001、郵箱地址為ex＠com。其中ex為本文假設(shè)的一個(gè)名稱(chēng)空間前綴；橢圓形節(jié)點(diǎn)表示資源；文字用方節(jié)點(diǎn)表示。圖1中的數(shù)據(jù)用RDF圖模型可表示為7個(gè)RDF三元組，即

ex：article1，ex：author，空節(jié)點(diǎn)3

ex：article1，ex：second－author，空節(jié)點(diǎn)1

空節(jié)點(diǎn)1，ex：school，空節(jié)點(diǎn)2

空節(jié)點(diǎn)3，ex：school，空節(jié)點(diǎn)2

空節(jié)點(diǎn)2，ex：school－name，hfut

空節(jié)點(diǎn)3，ex：sno，2010001

空節(jié)點(diǎn)3，ex：email，383235673＠qq.com

RDF圖模型可以直觀(guān)地表達(dá)RDF數(shù)據(jù)，但存在如下缺點(diǎn)：① 空節(jié)點(diǎn)無(wú)法解析；② 無(wú)法進(jìn)行等價(jià)節(jié)點(diǎn)判定；③ 缺乏合理的RDF數(shù)據(jù)聚合方法。

此外，傳統(tǒng)RDF圖模型忽略了結(jié)點(diǎn)層次關(guān)系的表示方法，導(dǎo)致無(wú)法辨別歧義三元組。如圖1無(wú)法區(qū)分三元組 （空節(jié)點(diǎn)1，ex：school，空節(jié)點(diǎn)2）和（空節(jié)點(diǎn)3，ex：school，空節(jié)點(diǎn)2）。

有序二叉排序樹(shù)既具有數(shù)組的元素搜索便捷特性，也具有鏈表靈活的元素刪除和插入操作的優(yōu)點(diǎn)，且能夠準(zhǔn)確地表述層次關(guān)系，此外還具有較高效率的遍歷算法。有序二叉樹(shù)的這些優(yōu)點(diǎn)恰好能解決傳統(tǒng)RDF圖模型存在的一些問(wèn)題。

合理的RDF數(shù)據(jù)分類(lèi)方法是研究RDF存儲(chǔ)模型的一個(gè)非常重要的問(wèn)題，其中空節(jié)點(diǎn)的識(shí)別是一個(gè)關(guān)鍵點(diǎn)。針對(duì)上述問(wèn)題，文獻(xiàn)［10］提出利用本體的owl：Functional－Property（FP）、owl：InverseFunctionalProperty（IFP）屬性對(duì)空節(jié)點(diǎn)進(jìn)行識(shí)別。本文利用上述基本思想實(shí)現(xiàn)對(duì)RDF三元組的分類(lèi)。

1.2 基于有序二叉樹(shù)模型的三元組分類(lèi)

定義2（函數(shù)型屬性FP） 如果P為函數(shù)屬性，存在P（x，y）與P（x，z），那么蘊(yùn)含y＝z。

定義3（反函數(shù)屬性IFP） 如果P為反函數(shù)屬性，存在P（y，x）與P（z，x），那么蘊(yùn)含y＝z。

根據(jù)上述定義，將RDF節(jié)點(diǎn)（三元組中的主體和客體部分）劃分為以下3類(lèi)：

（1）自然類(lèi)節(jié)點(diǎn)。如果A為自然類(lèi)節(jié)點(diǎn)，那么A?空節(jié)點(diǎn)。

（2）功能類(lèi)節(jié)點(diǎn)。如果A為功能類(lèi)節(jié)點(diǎn)，那么A∈空節(jié)點(diǎn)，且滿(mǎn)足以下任意條件：① ?三元組T（A，P，B），其中P為反函數(shù)屬性，B∈ （自然類(lèi)節(jié)點(diǎn) ∪ 功能類(lèi)節(jié)點(diǎn)）；② ? 三元組T（S，P，A），其中P為函數(shù)屬性，S∈（自然類(lèi)節(jié)點(diǎn)∪功能類(lèi)節(jié)點(diǎn)）；③ ? 節(jié)點(diǎn)B，A?B且B ∈ （自然類(lèi)節(jié)點(diǎn)∪功能類(lèi)節(jié)點(diǎn)）。

（3）其他類(lèi)節(jié)點(diǎn)。如果A為其他類(lèi)節(jié)點(diǎn)，那么A∈空節(jié)點(diǎn)，且A?（自然型節(jié)點(diǎn)∪功能型節(jié)點(diǎn)）。

RDF三元組的節(jié)點(diǎn)類(lèi)型直接決定了三元組含義的顯隱屬性。如果三元組不包含任何空節(jié)點(diǎn)，整個(gè)三元組表現(xiàn)為顯式屬性，不含任何的歧義性；如果包含空節(jié)點(diǎn)，由于空節(jié)點(diǎn)所表達(dá)的是未知對(duì)象，三元組表現(xiàn)出隱式屬性，只能經(jīng)過(guò)復(fù)雜的處理來(lái)消除歧義性。因此，本文依據(jù)三元組中的節(jié)點(diǎn)類(lèi)型將RDF三元組分為：

（1）完全已知三元組。完全已知三元組中只包含自然類(lèi)節(jié)點(diǎn)。

（2）部分已知三元組。部分已知三元組包含自然類(lèi)節(jié)點(diǎn)和至少1個(gè)功能類(lèi)節(jié)點(diǎn)。

（3）未知三元組。未知三元組包含自然類(lèi)節(jié)點(diǎn)和至少1個(gè)其他類(lèi)節(jié)點(diǎn)。

1.3 基于有序二叉樹(shù)存儲(chǔ)模型的結(jié)點(diǎn)描述

針對(duì)傳統(tǒng)RDF圖模型缺少描述節(jié)點(diǎn)關(guān)系的情況，本文將RDF有序二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)定義為一個(gè)六元組O＝（FS，ID，T，I，OP，NB），其中FS為子結(jié)點(diǎn)標(biāo)識(shí)號(hào)；ID為結(jié)點(diǎn)標(biāo)識(shí)號(hào)；T為結(jié)點(diǎn)類(lèi)型；I為結(jié)點(diǎn)排序權(quán)值；OP為結(jié)點(diǎn)選項(xiàng)；NB為兄弟節(jié)點(diǎn)標(biāo)識(shí)號(hào)。

（1）子結(jié)點(diǎn)排序號(hào)。子結(jié)點(diǎn)標(biāo)識(shí)號(hào)是結(jié)點(diǎn)的子孫結(jié)點(diǎn)編號(hào)。

（2）結(jié)點(diǎn)標(biāo)識(shí)號(hào)。結(jié)點(diǎn)標(biāo)識(shí)號(hào)是結(jié)點(diǎn)在整個(gè)存儲(chǔ)結(jié)構(gòu)中的編號(hào)，對(duì)應(yīng)唯一的三元組，由結(jié)點(diǎn)創(chuàng)建時(shí)生成，不能修改。

（3）結(jié)點(diǎn)類(lèi)型?！?－know”表示結(jié)點(diǎn)為“根類(lèi)型”節(jié)點(diǎn)，其子孫結(jié)點(diǎn)為謂詞相同的完全已知三元組；“0－unknow”則表明結(jié)點(diǎn)是“根類(lèi)型”節(jié)點(diǎn)，其子孫結(jié)點(diǎn)謂詞相同且都包含空節(jié)點(diǎn)；“1”表示結(jié)點(diǎn)為“非根類(lèi)型”。

（4）結(jié)點(diǎn)排序權(quán)值。結(jié)點(diǎn)排序權(quán)值表示結(jié)點(diǎn)被查詢(xún)的期望值，權(quán)值越高表明結(jié)點(diǎn)被查詢(xún)的可能性越大。該值僅對(duì)完全已知三元組結(jié)點(diǎn)有效。

（5）結(jié)點(diǎn)選項(xiàng)。結(jié)點(diǎn)選項(xiàng)用于記錄解析空結(jié)點(diǎn)的上下文結(jié)點(diǎn)標(biāo)識(shí)號(hào)，完全已知三元組結(jié)點(diǎn)該項(xiàng)為空。

（6）兄弟結(jié)點(diǎn)標(biāo)識(shí)號(hào)。結(jié)點(diǎn)的兄弟結(jié)點(diǎn)標(biāo)識(shí)號(hào)是結(jié)點(diǎn)的兄弟結(jié)點(diǎn)編號(hào)。

1.4 基于有序二叉樹(shù)存儲(chǔ)模型的結(jié)構(gòu)描述

有序二叉樹(shù)模型中的左子樹(shù)結(jié)點(diǎn)表示孩子結(jié)點(diǎn)，右子樹(shù)結(jié)點(diǎn)表示兄弟結(jié)點(diǎn)，結(jié)點(diǎn)可分為根類(lèi)型結(jié)點(diǎn)和信息類(lèi)型結(jié)點(diǎn)。

與樹(shù)的根結(jié)點(diǎn)含義不同，本文中的根類(lèi)型結(jié)點(diǎn)用于標(biāo)識(shí)結(jié)點(diǎn)的子孫節(jié)點(diǎn)謂詞相同且包含的三元組類(lèi)型亦相同。即根類(lèi)型結(jié)點(diǎn)是某類(lèi)信息類(lèi)型結(jié)點(diǎn)的開(kāi)始標(biāo)記。信息類(lèi)型結(jié)點(diǎn)則是實(shí)際RDF數(shù)據(jù)的索引結(jié)點(diǎn)。

同類(lèi)三元組集合的謂詞信息只記錄在“根類(lèi)型結(jié)點(diǎn)”中，其他結(jié)點(diǎn)無(wú)需記錄，這樣大大減少了存儲(chǔ)空間。

1.5 RDF圖模型到有序二叉樹(shù)存儲(chǔ)模型的轉(zhuǎn)化

將RDF圖轉(zhuǎn)化為有序二叉樹(shù)存儲(chǔ)模型，主要面臨以下幾方面的問(wèn)題。

（1）在樹(shù)形結(jié)構(gòu)中存儲(chǔ)RDF數(shù)據(jù)應(yīng)考慮空節(jié)點(diǎn)的識(shí)別問(wèn)題［11］?？展?jié)點(diǎn)提供多個(gè)三元組間必需的連通作用，與URI引用和文字不同，空節(jié)點(diǎn)標(biāo)識(shí)符并不被認(rèn)為是三元組的一個(gè)實(shí)際組成部分，它所表示的是一個(gè)匿名資源，要準(zhǔn)確解析出空節(jié)點(diǎn)含義，必須結(jié)合語(yǔ)義上下文以及本體。

（2）RDF數(shù)據(jù)存儲(chǔ)必須考慮文件組織形式［12］。不同的數(shù)據(jù)組織形式將直接影響數(shù)據(jù)查詢(xún)方式和效率。

此外，傳統(tǒng)的RDF圖模型并未考慮節(jié)點(diǎn)層次關(guān)系的表示方法。

在空節(jié)點(diǎn)識(shí)別問(wèn)題上，本文處理方法是利用本體的函數(shù)屬性和反函數(shù)屬性，結(jié)合空節(jié)點(diǎn)的上下文，消除空節(jié)點(diǎn)的歧義性，并記錄上下文結(jié)點(diǎn)標(biāo)識(shí)號(hào)。在實(shí)際的RDF查詢(xún)中，如果三元組中擁有匿名的空節(jié)點(diǎn)，可以結(jié)合上下文結(jié)點(diǎn)解析空節(jié)點(diǎn)。本文給出的實(shí)例如下。

上例表示姓名為chin的學(xué)生認(rèn)識(shí)1個(gè)姓名為assemble的計(jì)算機(jī)專(zhuān)業(yè)學(xué)生。考察三元組t1、t2、t3、t4，t1只含有自然類(lèi)節(jié)點(diǎn)，所以屬于完全已知三元組；假設(shè)謂詞ex：major在本體中是反函數(shù)屬性，t2、t3由于含有自然類(lèi)節(jié)點(diǎn)和未知節(jié)點(diǎn)，屬于未知三元組；t4含有自然節(jié)點(diǎn)和功能類(lèi)節(jié)點(diǎn)，屬于部分已知三元組。

因此完全已知節(jié)點(diǎn)有｛t1｝，部分已知節(jié)點(diǎn)有｛t4｝，未知節(jié)點(diǎn)有｛t2｝、｛t3｝。空節(jié)點(diǎn)？x在三元組集｛t2、t4｝、｛t3、t4｝中含義明確，故？x的歧義性可以聯(lián)合三元組t2、t4或t3、t4消除。

本文用二叉樹(shù)的父子關(guān)系［13］描述部分已知三元組和未知三元組的層次關(guān)系。對(duì)于三元組A（S1，P1，O1）和B（S2，P2，O2），其中S1、O1中至少1個(gè)為空節(jié)點(diǎn)，S2、O2中至少有1個(gè)為空節(jié)點(diǎn)。在有序二叉樹(shù)結(jié)構(gòu)中A、B關(guān)系為：

（1）如果S1＝S2，則A、B為兄弟結(jié)點(diǎn)。

（2）如果O1＝S2，則A為B的父親結(jié)點(diǎn)。

（3）如果S1＝O2，則A為B的兒子結(jié)點(diǎn)。

未知三元組節(jié)點(diǎn) （：1，p，：2）、（：2，p，：3）、（：2，p，：4）在有序二叉樹(shù)存儲(chǔ)模型中的表示如圖2所示。

圖2 樹(shù)形存儲(chǔ)中層次關(guān)系的表示

本文給出RDF圖模型轉(zhuǎn)為有序二叉樹(shù)模型的一般步驟如下。

（1）對(duì)RDF圖中所有三元組結(jié)點(diǎn)構(gòu)成n顆二叉樹(shù)集 合 T ＝ ｛T1，T2，…，Tn｝，并標(biāo) 記 結(jié)點(diǎn)類(lèi)型。

（2）對(duì)所有謂詞為p、類(lèi)型為完全已知的二叉樹(shù)Ti，…，Tj，合并Ti，…，Tj為一根新樹(shù)，將合并至T，刪除Ti，…，Tj，。

（3）對(duì)所有謂詞為p且三元組類(lèi)型為部分已知或未知的樹(shù)Tm，…，Tn，根據(jù)結(jié)點(diǎn)層次關(guān)系生成新樹(shù)，刪除Tm，…，Tn。如果謂詞為p且類(lèi)型為完全已知的樹(shù)存在，將插入中；否則合并至T。

（4）借助樹(shù)的孩子－兄弟鏈表表示法，將森林T轉(zhuǎn)化為二叉鏈表結(jié)構(gòu)的二叉樹(shù)。

RDF圖模型轉(zhuǎn)化有序二叉樹(shù)存儲(chǔ)模型的實(shí)例如圖3所示。

圖3 基于有序二叉樹(shù)存儲(chǔ)模型實(shí)例

2 查詢(xún)策略

2.1 排序權(quán)值

有序二叉樹(shù)模型中RDF三元組的查詢(xún)處理實(shí)質(zhì)是查找滿(mǎn)足條件的二叉樹(shù)節(jié)點(diǎn)。為了使符合條件的節(jié)點(diǎn)被更早地查詢(xún)，本文引入排序權(quán)值的概念。

定義4（排序權(quán)值） 設(shè)結(jié)點(diǎn)u被查詢(xún)次數(shù)為SUM（Qu），其中命中條件M次，Bu為同等謂詞結(jié)點(diǎn)集合，L（u）為Bu集合包含元素的數(shù)目，則排序權(quán)值為：

其中，ξ為參照因子，用于平衡結(jié)點(diǎn)命中率與結(jié)點(diǎn)的謂詞被查詢(xún)概率之間的關(guān)系。該計(jì)算方法使得經(jīng)常被查詢(xún)且命中率高的樹(shù)節(jié)點(diǎn)權(quán)值高，被查詢(xún)次數(shù)少且命中率低的樹(shù)節(jié)點(diǎn)權(quán)值低。排序權(quán)值的引入，使得經(jīng)常被查詢(xún)且符合查詢(xún)條件概率高的樹(shù)節(jié)點(diǎn)最早被查詢(xún)，在概率層面上減少了查詢(xún)符合條件節(jié)點(diǎn)所需的查詢(xún)次數(shù)。

在有序二叉樹(shù)存儲(chǔ)模型中，只有完全已知節(jié)點(diǎn)的排序權(quán)值才有意義，其他類(lèi)型結(jié)點(diǎn)由于考慮到空節(jié)點(diǎn)的層次表示問(wèn)題不能使用排序權(quán)值。結(jié)點(diǎn)的排序權(quán)值關(guān)系為：父節(jié)點(diǎn)的排序權(quán)值＞左子樹(shù)的排序權(quán)值＞右子樹(shù)的排序權(quán)值。

2.2 節(jié)點(diǎn)查詢(xún)算法

為了提高樹(shù)節(jié)點(diǎn)的查詢(xún)效率，本文對(duì)實(shí)體三元組進(jìn)行預(yù)處理，主要是建立標(biāo)識(shí)號(hào)索引和謂詞索引。標(biāo)識(shí)號(hào)索引用于快速定位查詢(xún)的三元組，將所有的三元組利用hadoop下的MaPreduce任務(wù)建立統(tǒng)一編號(hào)并存儲(chǔ)于一個(gè)文件中，該文件是所有三元組的實(shí)際存儲(chǔ)文件，有序二叉樹(shù)中存儲(chǔ)的是該節(jié)點(diǎn)的編號(hào)。

建立謂詞索引是有序二叉樹(shù)模型在數(shù)據(jù)查詢(xún)時(shí)將連續(xù)地查找某一謂詞的結(jié)點(diǎn)集合，這就要求能快速定位到謂詞的開(kāi)始標(biāo)記處。

由于RDF數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)為有序二叉樹(shù)，實(shí)際含有三元組信息的結(jié)點(diǎn)始終位于根類(lèi)型節(jié)點(diǎn)的左子樹(shù)中，其次，考慮結(jié)點(diǎn)的排序權(quán)值關(guān)系，這些特性決定了先序遍歷法較適合本文中結(jié)點(diǎn)的查找。結(jié)點(diǎn)的查詢(xún)算法描述如下。

算法1 節(jié)點(diǎn)查詢(xún)方法

輸入：查詢(xún)?nèi)MQ（x py），RDF數(shù)據(jù)集D（T）＝〈T1∪T2∪…∪Tn〉

輸出：確定的查詢(xún)結(jié)果三元組

算法1先取出有序二叉樹(shù)BST，從BST的根節(jié)點(diǎn)開(kāi)始，沿著右子樹(shù)方向查找謂詞為p的根結(jié)點(diǎn)，這時(shí)所查詢(xún)出的根結(jié)點(diǎn)即是謂詞為p的完全已知三元組集合的開(kāi)始標(biāo)記結(jié)點(diǎn)，三元組集合在根結(jié)點(diǎn)的左子樹(shù)上。由于模型中樹(shù)結(jié)點(diǎn)的排序權(quán)值大小關(guān)系為：根結(jié)點(diǎn)＞左孩子結(jié)點(diǎn)＞右孩子結(jié)點(diǎn)，為了盡量用較少的步驟查詢(xún)出符合條件的結(jié)點(diǎn)，算法1用先序遍歷法遍歷左子樹(shù)。如果左子樹(shù)中包含符合條件的結(jié)點(diǎn)，返回查詢(xún)結(jié)果。否則，完全已知三元組集中不包含所查詢(xún)的三元組。如果BST中包含結(jié)點(diǎn)謂詞為p且類(lèi)型為未知的根結(jié)點(diǎn)，則該結(jié)點(diǎn)左子樹(shù)包含所有謂詞為p的未知結(jié)點(diǎn)集，先序遍歷左子樹(shù)。如果查詢(xún)某未知結(jié)點(diǎn)符合條件，這時(shí)結(jié)合選項(xiàng)中的結(jié)點(diǎn)，解析出目標(biāo)結(jié)點(diǎn)，返回結(jié)果，將解析出的結(jié)點(diǎn)加入至BST中。否則，查詢(xún)失敗。

3 實(shí)驗(yàn)分析

本文針對(duì)查詢(xún)響應(yīng)、查詢(xún)預(yù)處理性能進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)以RDF圖模型為基礎(chǔ)，選取存儲(chǔ)結(jié)構(gòu)的Sesame［14］作為對(duì)比系統(tǒng)。

實(shí)驗(yàn)采用4臺(tái)Ubuntu搭建的hadoop集群，以L(fǎng)UBM基準(zhǔn)數(shù)據(jù)集為測(cè)試數(shù)據(jù)集。對(duì)于LUBM數(shù)據(jù)集中16個(gè)標(biāo)準(zhǔn)查詢(xún)分別在不同的數(shù)量級(jí)上進(jìn)行查詢(xún)測(cè)試，結(jié)果如圖4、圖5所示。

由圖4可看出，實(shí)驗(yàn)數(shù)據(jù)在較小數(shù)量級(jí)時(shí)，本文模型與Sesame系統(tǒng)的平均查詢(xún)響應(yīng)時(shí)間幾乎相等；當(dāng)數(shù)據(jù)量較大時(shí)，有序二叉樹(shù)模型能夠大幅度地縮短查詢(xún)響應(yīng)時(shí)間。

由圖5可得出，有序二叉樹(shù)模型在預(yù)處理階段比Sesame系統(tǒng)消耗時(shí)間長(zhǎng)，但與查詢(xún)響應(yīng)時(shí)間相比在很小的數(shù)量級(jí)上，故其產(chǎn)生的影響可忽略不計(jì)。

此外，本文模型為追求更快的查詢(xún)性能，建立了多個(gè)索引，故需要更多的存儲(chǔ)空間。云計(jì)算具有較強(qiáng)的可擴(kuò)展性，可以通過(guò)向集群中添加更多的機(jī)器以獲取更大的存儲(chǔ)能力及更強(qiáng)的運(yùn)算能力，存儲(chǔ)空間和計(jì)算能力不會(huì)成為束縛有序二叉樹(shù)模型的因素 。因此，本文的有序二叉樹(shù)模型更加適合海量RDF數(shù)據(jù)存儲(chǔ)。

圖4 查詢(xún)響應(yīng)性能實(shí)驗(yàn)結(jié)果

圖5 查詢(xún)預(yù)處理性能實(shí)驗(yàn)結(jié)果

4 結(jié)束語(yǔ)

本文提出了基于有序二叉樹(shù)的海量RDF數(shù)據(jù)存儲(chǔ)模型，并實(shí)現(xiàn)了RDF數(shù)據(jù)的查詢(xún)算法，對(duì)比實(shí)驗(yàn)結(jié)果證明了該模型的可行性和有效性。在后續(xù)的工作中，將進(jìn)一步優(yōu)化查詢(xún)響應(yīng)策略，提高RDF數(shù)據(jù)查詢(xún)成功率。

［1］Borthakur D.The hadoop distributed file system：architecture and design［EB／OL］.［2012－08－16］.http：／／hadoop.apache.org.

［2］Abadi D J，Marcus A，Madden S R.SW－Store：a vertically partitioned DBMS for semantic web data management［J］.The VLDB Journal，2009，8（2）：358－406.

［3］Weiss C，Karras P，Bernstein A.Hexastore：sextuple indexing for semantic web data management［J］.The VLDB Endowment，2008，1（1）：108－119.

［4］Owens ASeaborne AGibbins N.Clustered TDBa clustered triple store for jena［EB／OL］.［2009－05－02］.http：／／eprints.soton.ac.uk／266974／.

［5］Husain MF，McGlothlin J，Masud MM.Heuristics－based query processing for large RDF graphs using cloud computing［J］.IEEE Transactions on Data and Knowledge Engineering，2011，23（9）：1312－1327.

［6］Myung J，Yeon J，Lee S G.SPARQL basic graph pattern processing with iterative mapreduce［C］／／Proceedings of the 2010Workshop on Massive Data Analytics on the Cloud，2011：1－6.

［7］Tian Yuan，Wang Haofen，Jin Wei，et al.A pattern－based approach for efficient query processing over RDF data［J］.Transactions on Large－Scale Data－and Knowledge－Centered Systems V Lecture Notes in Computer Science，2012，7（10）：70－90.

［8］Choi H，Son J，Cho Y，et al.SPIDER：a systeMfor scalable，parallel／distributed evaluation of large－scale RDF data［C］／／The Conference on Information and Knowledge Management，2009：2087－2088.

［9］Klyne G，Carroll J J，etal.Resource description framework（RDF）：concepts and abstract syntax［EB／OL］.［2012－01－20］.http：／／www.w3.org／TR／rdf－concepts／.

［10］Lee Berners，Connolly T，Delta D.An ontology for the distribution of differences between RDF graphs［EB／OL］.［2009－8－12］.http：／／www.w3c.org／DesignIssues／Diff.

［11］McGlothlin J P，Khan L.Materializing and persisting inferred and uncertain knowledge in RDF datasets［C］／／Proceedings of the Twenty－Fourth AAAI Conference on Artificial Intelligence，2010，23（9）：1312－1327.

［12］Mcglothlin J P，Khan L T.RDFKB：efficient support for RDF inference queries and knowledge management［C］／／IDEAS’09Proceedings for the 2009International Database Engineering and Application Symposium，2009：259－266.

［13］Arora N，Tamta V K，Kumar S.Modified non－recursive algorithMfor reconstructing a binary tree［J］.International Journal of Computer Applications，2012，43（10）：25－28.

［14］Broekstra J，Kampman A.Sesame：ageneric architecture for storing and querying RDF and RDF schema［C］／／Proceedings of the First International Semantic Web Conference（ISWC2002），2002：54－68.

［15］鄧 青，韓江洪，周 健.基于混合決策樹(shù)的自適應(yīng)數(shù)據(jù)集成方法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（8）：1165－1169.