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

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

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

中圖分類號:TP311 文獻(xiàn)標(biāo)識碼:A

1 引 言

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

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

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

2.1 RDF 模型

設(shè)有集合: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來擴(kuò)展數(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特性用于進(jìn)一步描述與應(yīng)用相關(guān)的特性#65377;前者用于表明某個特性的值是給定類的實例或一個類型文字#65377;后者用于表明某個特性應(yīng)用于指定的類#65377;當(dāng)RDFS中這二個特性應(yīng)用于某個RDF特性時，它們也會應(yīng)用于該RDF特性的子特性#65377;RDFS提供了使用預(yù)定義的rdfs∶subPropertyOf特性來描述特性之間的特化關(guān)系的方法#65377;

2.3 完整模型

RDF語義學(xué)定義某一模型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;應(yīng)用這些推理法則的輸出結(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運算的表達(dá)過程中，使用圖1中的RDF數(shù)據(jù)作為運算的輸入#65377;假設(shè)所有的運算都了解定義4所定義的RDF完整模型#65377;各種被提議的運算能使用后綴″^″被定義，后綴″^″將會使運算忽略內(nèi)涵數(shù)據(jù)#65377;定義RDF集合是節(jié)點的集合#65377;所有RAL運算因為集合是封閉的，所以RAL表達(dá)式能容易地被組成#65377;又因RAL集合沒有順序性，故這樣會使一些二進(jìn)制運算能夠交換#65377;與相關(guān)的代數(shù)關(guān)系相比，RAL表達(dá)更有力，其運算形式是:o[f](x1，x2，…xn∶expre-ssion)#65377;這形式表示，對于每一個綁定到輸入集合的一個元組的x， f(x)會被計算#65377;一個元組是通過獲取每個輸入集合x1，x2，…xn被形成的#65377;f可能是一個使用基本屬性或被文中提議的運算之一的函數(shù)#65377;基于運算o的語義，對于每一個綁定x，應(yīng)用于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中被用來控制一個功能或運算的重復(fù)應(yīng)用#65377;它包括映射運算map[f]和級聯(lián)星運算*[f]#65377;

3.3 構(gòu)造運算

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

4 RAL等價規(guī)則

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

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

5 RDF查詢

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

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

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

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

6 定量分析

為了更好地說明圖5的查詢樹是最優(yōu)化的，進(jìn)行如下分析:假設(shè)圖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ù)關(guān)系#65377;它給出的一系列運算符在被正則定義的RDF查詢語言的提取和構(gòu)造部分被使用#65377;與現(xiàn)有的 RDF 查詢語言相比較，它的構(gòu)造階段沒有被疏忽而且是語言規(guī)范的一部份#65377;作者今后的工作是:用有關(guān)的已有RDF查詢語言和RAL的完整性來分析RAL的表達(dá)力，并將它的表達(dá)力與其他代數(shù)關(guān)系的表達(dá)力相比較，從而為RAL 的表達(dá)力提供一些洞察語言的真實力量#65377;另外，作者今后將進(jìn)一步研究查詢優(yōu)化規(guī)則#65377;

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