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

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

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

1 引 言

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

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

RDF模型的基本對(duì)象類型有:資源#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é)點(diǎn)集合)#65380;L(表示文字集合)#65380;P(表示屬性集合)，在RDF層次中包含集合:R= U∪B，rdf∶Property∈U，P∈R，rdf∶type∈P，且U#65380;B#65380;L是兩兩相分離的#65377;

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

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

2.2 RDFS

RDFS通常把類組織為一種分級(jí)結(jié)構(gòu)#65377;一個(gè)類是任何具有rdf∶type特性#65380;并且該特性的值為rdfs∶Class的資源#65377;rdfs∶Class本身也是資源，而且也有一個(gè)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;

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

2.3 完整模型

RDF語(yǔ)義學(xué)定義某一模型M的封閉式RDF和封閉式RDFS的方法是根據(jù)一個(gè)給定的推理法則的集合，在模型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é)果可能會(huì)觸發(fā)其它的法則#65377;然而對(duì)于任何輸入模型M，這些法則將會(huì)終止#65377;

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

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

3 RAL基本運(yùn)算

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

3.1 提取運(yùn)算

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

3.2 循環(huán)運(yùn)算

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

3.3 構(gòu)造運(yùn)算

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

4 RAL等價(jià)規(guī)則

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

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

5 RDF查詢

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

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

然后只要操作數(shù)是可用的，查詢處理模塊就會(huì)處理這棵查詢樹中的一個(gè)節(jié)點(diǎn)#65377;這個(gè)節(jié)點(diǎn)將會(huì)被由處理結(jié)點(diǎn)的相關(guān)表達(dá)式產(chǎn)生的集合所替換#65377;當(dāng)處理根節(jié)點(diǎn)時(shí)，執(zhí)行結(jié)束#65377;最后的查詢結(jié)果是處理根節(jié)點(diǎn)時(shí)所得到的集合#65377;在例子中，在初始查詢樹的執(zhí)行期間，會(huì)產(chǎn)生一個(gè)在所有畫家#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)用最有限制性的選擇，可以對(duì)查詢更進(jìn)一步的優(yōu)化，查詢結(jié)果樹如圖5所示:

6 定量分析

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

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

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

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

上述結(jié)果表明:最有效的查詢執(zhí)行是最后一棵查詢樹，因?yàn)樗牡芽柗e產(chǎn)生的元素的數(shù)目最少#65377;

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

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

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