一種基于ＲＡＬ的ＲＤＦ查詢方案

摘 要:隨著RDF的出現(xiàn)，其相應的查詢語言也應運而生#65377;然而，這些語言都沒有考慮RDF代數(shù)關系(RDF algebra，簡稱RAL)，因此，這樣的RDF查詢語言通常沒有使用APIs來描述它們的語義和優(yōu)化問題，這對于RDF查詢會導致一種低性能行為#65377;為此，為RDF查詢語言和執(zhí)行RDF查詢優(yōu)化提供一種RAL#65377;首先定義RAL的數(shù)據(jù)模型#65380;然后呈現(xiàn)處理數(shù)據(jù)的運算和等價規(guī)則#65380;最后描述應用RAL運算和等價規(guī)則來查詢RDF的優(yōu)化#65377;

關鍵詞:資源描述框架(模式);資源描述框架(模式)查詢語言;資源描述框架代數(shù)關系

中圖分類號:TP311 文獻標識碼:A

1 引 言

近年來，隨著語義web的出現(xiàn)，為了使其機器可理解，對元數(shù)據(jù)的描述和查詢有很強的要求#65377;為此，W3C推出了RDF和RDFS#65377;RDF是一種基于XML的元數(shù)據(jù)描述框架，能定義概念之間的關系，描述易被機器理解的信息#65377;它提供的語義模型可用于描述Web上的任意資源及其類型，解決語義異構(gòu)問題#65377;RDF模型雖網(wǎng)上資源賦予了基本的語義信息#65377;但RDF只定義了有限的基本的建模原語，它既沒有給出定義新的屬性詞匯的機制，也沒有給出定義這些屬性以及資源之間新的關系的機制#65377;RDFS是RDF的擴展語言，它為RDF模型提供了類型系統(tǒng)支持，可以定義不同領域的核心詞匯以及它們之間的關系，為領域知識的表達#65380;交換和共享提供了語義支持#65377;雖然這二種語言為描述web元數(shù)據(jù)提供了一種標準規(guī)范，但查詢RDF元數(shù)據(jù)的標準化語言仍是一個需解決的問題#65377;目前，研究組已研究出多種RDF查詢語言(rdfDB#65380;SeRQL#65380;SPARQL等)，這些語言在功能#65380;形式等方面各具特點，為RDF元數(shù)據(jù)的查詢提供了不同的方法#65377;但這些語言存在一個共同的缺點:沒有考慮RDF代數(shù)關系，導致對RDF查詢的性能較低#65377;為此，文中提出了RAL#65377;

2 數(shù)據(jù)模型

RDF模型的基本對象類型有:資源#65380;屬性和陳述#65377;有向標記圖是RDF的基本數(shù)據(jù)模型#65377;其最基本的單位是陳述#65377;陳述是由主體#65380;謂詞#65380;客體組成#65377;由此可見，現(xiàn)有的RDF數(shù)據(jù)模型缺乏代數(shù)關系的描述#65377;為此，下面使用代數(shù)關系來討論RDF數(shù)據(jù)模型，描述RDF數(shù)據(jù)結(jié)構(gòu)用RAL表示公式是如何被表達的#65377;

2.1 RDF 模型

設有集合:R(表示資源集合)#65380;U(表示URIrefs集合)#65380;B(表示空節(jié)點集合)#65380;L(表示文字集合)#65380;P(表示屬性集合)，在RDF層次中包含集合:R= U∪B，rdf∶Property∈U，P∈R，rdf∶type∈P，且U#65380;B#65380;L是兩兩相分離的#65377;

定義1一個RDF模型M是一個有限的三元組集合(也稱陳述):MR×U×(R∪L)

定義2 一個RDF模型M的屬性集合:P={p|(s，p，o)∈M∨(p，rdf∶type，rdf∶Property)∈M}

2.2 RDFS

RDFS通常把類組織為一種分級結(jié)構(gòu)#65377;一個類是任何具有rdf∶type特性#65380;并且該特性的值為rdfs∶Class的資源#65377;rdfs∶Class本身也是資源，而且也有一個rdf∶type特性，并且該特性的值為rdfs∶Class#65377;用類的集合C來擴展數(shù)據(jù)模型，使在RDFS層次結(jié)構(gòu)中包含:CR，rdfs∶Resource∈C，rdfs∶Property∈C，rdfs∶Class∈C和rdfs∶Literal∈C#65377;

計算技術(shù)與自動化2007年6月第26卷第2期謝桂芳等:一種基于RAL的RDF查詢方案定義3 一個RDF模型M的類集合是:C={c|(c，rdf∶type，rdfs∶Class)∈M}一個類可以是一個或多個類的子類#65377;RDFS規(guī)定:所有類是rdfs∶Resource的子類#65377;用戶除了描述想要描述的類，還需定義刻畫這些類的特性#65377;特性是用RDF類rdf∶Property以及RDFS特性rdfs∶domain#65380;rdfs∶range和rdfs∶subPropertyOf來描述#65377;RDF中的所有特性都被描述為類rdf∶Property的實例#65377;因此一個新特性的描述是通過為它指派一個URIref，并使用一個值為rdf∶Property的rdf∶type特性來完成#65377;RDFS的rdfs∶range和rdfs∶domain特性用于進一步描述與應用相關的特性#65377;前者用于表明某個特性的值是給定類的實例或一個類型文字#65377;后者用于表明某個特性應用于指定的類#65377;當RDFS中這二個特性應用于某個RDF特性時，它們也會應用于該RDF特性的子特性#65377;RDFS提供了使用預定義的rdfs∶subPropertyOf特性來描述特性之間的特化關系的方法#65377;

2.3 完整模型

RDF語義學定義某一模型M的封閉式RDF和封閉式RDFS的方法是根據(jù)一個給定的推理法則的集合，在模型M中增加新的三元組#65377;稱原始模型M為外延數(shù)據(jù)#65380;最近產(chǎn)生的三元組為內(nèi)涵數(shù)據(jù)#65377;封閉式RDF的推理法則為模型中的所有屬性增加了rdf∶type屬性#65377; 封閉式RDFS的推理法則是rdfs∶subClassOf的傳遞性#65380;rdfs∶subPropertyOf的傳遞性等#65377;應用這些推理法則的輸出結(jié)果可能會觸發(fā)其它的法則#65377;然而對于任何輸入模型M，這些法則將會終止#65377;

定義4 如果一個RDF模型M包含封閉式RDF和封閉式RDFS，則它是完整模型#65377;

用完整模型作為文中被提議的數(shù)據(jù)模型，且忽略RDF具體化和rdfs:seeAlso，rdfs:isDefinedBy，rdfs:comment和rdfs:label的屬性#65377;圖1呈現(xiàn)了不同繪畫技術(shù)的RDF模式和實例#65377;圖2是從一定程度上對圖1稍微做了修改后的RDF模式#65377;

3 RAL基本運算

在RAL運算的表達過程中，使用圖1中的RDF數(shù)據(jù)作為運算的輸入#65377;假設所有的運算都了解定義4所定義的RDF完整模型#65377;各種被提議的運算能使用后綴″^″被定義，后綴″^″將會使運算忽略內(nèi)涵數(shù)據(jù)#65377;定義RDF集合是節(jié)點的集合#65377;所有RAL運算因為集合是封閉的，所以RAL表達式能容易地被組成#65377;又因RAL集合沒有順序性，故這樣會使一些二進制運算能夠交換#65377;與相關的代數(shù)關系相比，RAL表達更有力，其運算形式是:o[f](x1，x2，…xn∶expre-ssion)#65377;這形式表示，對于每一個綁定到輸入集合的一個元組的x， f(x)會被計算#65377;一個元組是通過獲取每個輸入集合x1，x2，…xn被形成的#65377;f可能是一個使用基本屬性或被文中提議的運算之一的函數(shù)#65377;基于運算o的語義，對于每一個綁定x，應用于o的局部結(jié)果的f(x)被計算#65377;運算結(jié)果通過組合所有局部結(jié)果被得到#65377;為了易讀的原因，我們使用二元運算中綴符號#65377;RAL運算有以下三種:

3.1 提取運算

提取運算檢索來自輸入結(jié)點集合(RDF模型所需要)的資源/文字#65377;如果運算沒有定義表示文字結(jié)點，則這些節(jié)點完全被忽略#65377;它包括投影運算π#65380;選擇運算σ#65380;笛卡爾積運算×#65380;連接運算∞#65380;并運算∪#65380;差運算-#65380;交運算∩#65377;

3.2 循環(huán)運算

循環(huán)運算在RAL中被用來控制一個功能或運算的重復應用#65377;它包括映射運算map[f]和級聯(lián)星運算*[f]#65377;

3.3 構(gòu)造運算

構(gòu)造運算通過創(chuàng)造節(jié)點/邊和重復使用舊的節(jié)點(盡可能沒有一些邊)及舊的邊來建立一個新模型#65377;它包括創(chuàng)建結(jié)點運算cnode#65380;創(chuàng)建邊運算cedge#65380;刪除結(jié)點運算dnode#65380;刪除邊運算dedge#65377;

4 RAL等價規(guī)則

使用代數(shù)關系表達式查詢的好處是能夠以滿足某種需要的形式來重寫這表達式#65377;例如一個從RQL到RAL的自動翻譯器能使用RAL等價規(guī)則為查詢優(yōu)化意圖來重寫代數(shù)表達式#65377;

RAL的等價規(guī)則是由單值規(guī)則和相關的代數(shù)關系的等價規(guī)則產(chǎn)生的#65377;因篇幅有限，在此只列舉在文中所用到的5條規(guī)則，其它規(guī)則略#65377;

5 RDF查詢

利用RAL運算和等價規(guī)則，可以對RDF查詢進行優(yōu)化#65377;啟發(fā)式查詢優(yōu)化是盡可能地基于推進選擇運算/投影運算和優(yōu)先使用最有限制性的選擇，這樣查詢優(yōu)化就像在相關的代數(shù)關系上下文中被執(zhí)行一樣#65377;為了能較好地說明RAL對RDF查詢的有效性，文中以圖2來描述查詢處理及優(yōu)化過程#65377;假設對圖2要查詢依字母順序返回使用\"Chiaroscuro\"技術(shù)的畫家的國家#65377;則查詢處理及優(yōu)化過程如下:

首先查詢語法分析器產(chǎn)生圖3所示的初始查詢樹#65377;在所有的查詢樹里，a表示在輸入中，在圖2的模式內(nèi)被分類的所有資源的集合#65377;

然后只要操作數(shù)是可用的，查詢處理模塊就會處理這棵查詢樹中的一個節(jié)點#65377;這個節(jié)點將會被由處理結(jié)點的相關表達式產(chǎn)生的集合所替換#65377;當處理根節(jié)點時，執(zhí)行結(jié)束#65377;最后的查詢結(jié)果是處理根節(jié)點時所得到的集合#65377;在例子中，在初始查詢樹的執(zhí)行期間，會產(chǎn)生一個在所有畫家#65380;繪畫和技術(shù)之間的大的笛卡爾積#65377;使用規(guī)則(1)#65380;(2)和(3)來推進選擇，就能得到圖4所示的查詢樹#65377;

最后，應用規(guī)則(1)#65380;(2)#65380;(3)#65380;(4)和(5)，并優(yōu)先應用最有限制性的選擇，可以對查詢更進一步的優(yōu)化，查詢結(jié)果樹如圖5所示:

6 定量分析

為了更好地說明圖5的查詢樹是最優(yōu)化的，進行如下分析:假設圖2中的實例有5種繪畫技術(shù)#65380;100名畫家#65380;1000幅畫#65377;所有的畫中只有100幅是使用“Chiaroscuro\"繪畫技術(shù)#65377;對每一棵查詢樹，計算由笛卡爾積產(chǎn)生的元素的數(shù)目#65377;

第一棵查詢樹為:1001000+51001000=600000

第二棵查詢樹為:1001000+10001=101000

第三棵查詢樹為:11000+100100=11000

上述結(jié)果表明:最有效的查詢執(zhí)行是最后一棵查詢樹，因為它的笛卡爾積產(chǎn)生的元素的數(shù)目最少#65377;

7 結(jié)束語

RAL是一種被定義為用來支持RDF查詢語言的正則規(guī)范的RDF代數(shù)關系#65377;它給出的一系列運算符在被正則定義的RDF查詢語言的提取和構(gòu)造部分被使用#65377;與現(xiàn)有的 RDF 查詢語言相比較，它的構(gòu)造階段沒有被疏忽而且是語言規(guī)范的一部份#65377;作者今后的工作是:用有關的已有RDF查詢語言和RAL的完整性來分析RAL的表達力，并將它的表達力與其他代數(shù)關系的表達力相比較，從而為RAL 的表達力提供一些洞察語言的真實力量#65377;另外，作者今后將進一步研究查詢優(yōu)化規(guī)則#65377;

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。