国产卡一卡二卡三无线乱码新区 ,亚洲jiZZjiZZ在线播放

基于SPARQL的RDF數(shù)據(jù)節(jié)點(diǎn)間關(guān)系路徑檢索

來源：微型機(jī)與應(yīng)用2011年第9期

肖竹軍

(武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢 430063)

摘要： 在分析SPARQL標(biāo)準(zhǔn)和基于Jena的開源SPARQL工具ARQ查詢引擎源碼的基礎(chǔ)上，提出了可支持關(guān)聯(lián)查詢的擴(kuò)展SPARQL標(biāo)準(zhǔn)及其設(shè)計(jì)和實(shí)現(xiàn)方案，認(rèn)真分析了已有的試驗(yàn)成果。

關(guān)鍵詞： 無線網(wǎng)絡(luò) SPARQL ARQ Jena RDF 關(guān)系路徑關(guān)系查詢

Abstract：

Key words :

摘要： 在分析ARQL" title="SPARQL">SPARQL標(biāo)準(zhǔn)和基于Jena的開源SPARQL工具ARQ查詢引擎源碼的基礎(chǔ)上，提出了可支持關(guān)聯(lián)查詢的擴(kuò)展SPARQL標(biāo)準(zhǔn)及其設(shè)計(jì)和實(shí)現(xiàn)方案，認(rèn)真分析了已有的試驗(yàn)成果。
關(guān)鍵詞： SPARQL；ARQ；Jena；RDF；關(guān)系路徑；關(guān)系查詢

　資源描述框架RDF(Resource Description Framework)[1]是W3C組織基于可擴(kuò)展標(biāo)記語言(XML)開發(fā)的一種元數(shù)據(jù)描述框架。RDF能夠定義概念以及概念間的關(guān)系，描述易被機(jī)器理解的信息和知識。它提供的語義模型可用于描述Web上的任意資源及其類型，為網(wǎng)上資源描述提供了一種通用表示框架，解決語義異構(gòu)問題，實(shí)現(xiàn)數(shù)據(jù)集成的元數(shù)據(jù)解決方案。同時，RDF可用于數(shù)據(jù)發(fā)現(xiàn)，為搜索引擎提供更強(qiáng)大的搜索功能。RDF通過基于XML語法明確定義的結(jié)構(gòu)化約定來建立語義協(xié)定與語法編碼之間的橋梁，以此促進(jìn)元數(shù)據(jù)的互操作能力。因此，RDF是解決計(jì)算機(jī)知識表示問題的最佳選擇，可以很好地描述元數(shù)據(jù)。
　SPARQL(Simple Protocol and RDF Query Language)是為RDF開發(fā)的一種查詢語言和數(shù)據(jù)獲取協(xié)議，雖然它是為W3C開發(fā)的RDF數(shù)據(jù)模型定義，但是可以用于查詢?nèi)魏慰梢杂肦DF來表示的信息資源。現(xiàn)行SPARQL能夠滿足類似SQL中基本模式匹配、分組、連接、合并等查詢形式，并能夠根據(jù)用戶定義有效地返回映射結(jié)果集，能夠滿足基于RDF數(shù)據(jù)的基本查詢需求。
　RDF數(shù)據(jù)的精髓在于以半結(jié)構(gòu)化數(shù)據(jù)形式來存儲知識以及知識間的基本關(guān)系，比較遺憾的是，目前的SPARQL標(biāo)準(zhǔn)及工具還沒有提供一種有效的途徑來查詢?nèi)我庵付ǖ膬晒?jié)點(diǎn)間可能存在的各種關(guān)系路徑以及任意指定節(jié)點(diǎn)周圍可能散射的各種關(guān)系路徑。為了解決如上問題，本文在原有的SPARQL標(biāo)準(zhǔn)的基礎(chǔ)上引入新關(guān)鍵詞來描述關(guān)聯(lián)查詢語義，并在針對基于Jena[2]的SPARQL開源引擎ARQ基礎(chǔ)上進(jìn)行實(shí)驗(yàn)、支持?jǐn)U展新的標(biāo)準(zhǔn)及功能的方案。
1 SPARQL語法及擴(kuò)展
1.1 SPARQL基本語法
1.1.1 基本術(shù)語
　被“<>”界定的術(shù)語是IRI參考[RFC3987]，它們代表IRIs，直接地或相對于一個基本的IRI。IRIs是URIs[RFC3986]的一般化，而且完全與URIs和URLs兼容。SPARQL為IRIs提供兩種縮寫機(jī)制：namespace前綴和相關(guān)的URIs。查詢術(shù)語可能是文字字符串(用雙引號“”或單引號‘’括起來)，有一個可選擇的語言標(biāo)簽或可選擇的數(shù)據(jù)類型IRI。為方便起見，整數(shù)能被直接地寫，且被解釋成datatype的類型文字xsd：integer；十進(jìn)制數(shù)被解釋為xsd：decimal，含有一個指數(shù)的數(shù)被解釋為xsd：double。類型值xsd：boolean也能被寫為true或false。SPARQL查詢變量有全局范圍，查詢時，同一個名字在各處是相同的變量，變量用“？”指出[3-4]。
1.1.2 三元組模式
　三元組模式被寫作為一列主語、謂語和賓語，用簡單的方法來寫一些通用的三元組模式，用{}將其聚集在一起。
1.1.3 圖模式
　SPARQL查詢語言是基于圖模式匹配的，最簡單的圖模式是三元組模式，如同一個RDF三元組，但在任何主語、謂語或賓語的位置中可能有變量，如{？Book dc：title？title}。復(fù)雜圖模式能由簡單圖模式組合而成，常見的復(fù)雜圖模式是基本圖模式、組合圖模式、可選擇圖模式、聯(lián)合圖模式、RDF數(shù)據(jù)集圖模式、值約束條件六種模式中的一種。
1.1.4 值約束
　SPARQL中的FILTER關(guān)鍵字對綁定變量的值進(jìn)行約束，從而限制查詢的結(jié)果。這些值約束條件是對布爾值進(jìn)行計(jì)算的邏輯表達(dá)式，并且可以與邏輯操作符&&和||組合使用。例如，可以用過濾器把返回名稱列表的查詢修改為只返回和指定正則表達(dá)式匹配的名稱。
1.1.5 查詢類型
　SPARQL支持SELCET、ASK、DESCRIBE和CONSTRUCT四種類型的查詢。典型的SPARQL查詢由SELCET、FROM、WHERE三部分組成。SELCET子句指定查詢應(yīng)當(dāng)返回的內(nèi)容；FROM是一個可選的子句，提供了將要使用的數(shù)據(jù)集的URI，可以指向一個本地文件，也可以指向Web其他地方的某一個圖的URL；WHERE子句由一組三元模式組成，采用基于Turtle的語法表示。這些三元模式共同構(gòu)成了所謂的圖形模式。ASK：應(yīng)用程序可以使用ASK形式來測試查詢模式是否有一個解決方案。如果查詢的圖形模式在數(shù)據(jù)集中有匹配物，那么ASK將返回“yes”；如果沒有匹配物，則返回“no”。DESCRIBE：返回一個圖形，其中包含和圖形模式匹配的節(jié)點(diǎn)的相關(guān)信息。例如，DESCRIBE？person WHERE{？person foaf： name“Jon Foobar”}會返回一個圖，其中包括來自JonFoobar的模型的三元模式。CONSTRUCT：用來為每個查詢結(jié)果輸出一個圖形模式，這樣就可以直接從查詢結(jié)果創(chuàng)建新的RDF圖。

1.2 SPARQL語法擴(kuò)展
　擴(kuò)展的基本原則是不影響原有SPARQL查詢語法及特性，通過引入適當(dāng)?shù)牟樵冴P(guān)鍵字來描述查找指定節(jié)點(diǎn)間的關(guān)鍵關(guān)系。第一個關(guān)鍵詞為SEEK，用來表示路徑查詢類型，其用法類似于SELECT、ASK、DESCRIBE、CONSTRUCT等關(guān)鍵字；第二個關(guān)鍵詞為START，用來描述關(guān)系路徑的起點(diǎn)圖模式；第三個關(guān)鍵詞為END，用來表示關(guān)系路徑的終點(diǎn)圖模式；第四個關(guān)鍵詞為NODE，用來描述關(guān)系路徑節(jié)點(diǎn)的圖模式，以及與起點(diǎn)圖模式和終點(diǎn)圖模式間的連接方式；第五個關(guān)鍵詞為CONSTRAINT，用來描述關(guān)系路徑的約束，作用類似于FILTER關(guān)鍵詞，主要用來限制關(guān)系路徑最短長度、關(guān)系路徑最長長度、與起點(diǎn)和終點(diǎn)的關(guān)系變量前綴、路徑節(jié)點(diǎn)變量前綴等，其中最短路徑為默認(rèn)值為3，最長路徑長度默認(rèn)值為6。遵循以上擴(kuò)展標(biāo)準(zhǔn)的節(jié)點(diǎn)間關(guān)系路徑查詢語法如下。
SEEK ？node，？power，？link
WHERE {
   START{
        ？s1 <http://jena.test/elements/type> “country”；
        ？s1 <http://jena.test/elements/name> “A國”.
   }
   END{
        ？s2 <http://jena.test/elements/type> “country”.
        ？s2 <http://jena.test/elements/name> “B國”.
   }
   NODE{
        ？s1 ？link ？node.
        ？node ？link ？s2.
        ？node<http://jena.test/elements/type>“keypoint”.
        ？node <http://jena.test/elements/power>？power.
        Filter(？power>1)
}
   CONSTRAIT{
        LinkName(“link”)
        NodeName(“node”)
        MinDepth(3)
        MaxDepth(6)
}
}
   當(dāng)只有START描述的起點(diǎn)而沒有END描述的終點(diǎn)時，則用來查找從該起點(diǎn)出發(fā)的符合路徑節(jié)點(diǎn)中描述的關(guān)系路徑，CONSTRAIT依然用來描述路徑的各種約束信息、含義及用法不變，到此便基本完成了對SPARQL標(biāo)準(zhǔn)及語法的擴(kuò)展工作。
2 基于ARQ開源引擎的擴(kuò)展
2.1 創(chuàng)建查詢語法樹
　ARQ[5]目前支持標(biāo)準(zhǔn)SPARQL語法樹的生成，在擴(kuò)展標(biāo)準(zhǔn)之后需要加入新的語法樹創(chuàng)建規(guī)則，以識別擴(kuò)展標(biāo)準(zhǔn)中新加入的關(guān)鍵詞，最終建立正確的語法樹結(jié)構(gòu)[6-7]。新規(guī)則的引入需要保證在SEEK查詢中至少在WHERE子句中出現(xiàn)START關(guān)鍵字來描述關(guān)系路徑起點(diǎn)的模式，而NODE關(guān)鍵字來描述關(guān)系路徑中間各節(jié)點(diǎn)的模式，最后用CONSTRAIT關(guān)鍵字來限制關(guān)系路徑長度等屬性。其中END關(guān)鍵字為可選路徑，如果沒有關(guān)系終點(diǎn)限制，則只需要達(dá)到關(guān)系路徑最大深度后停止關(guān)系查詢即可。若不能滿足上述基本規(guī)則，則查詢語法樹創(chuàng)建失敗，可向客戶端反饋語法錯誤。擴(kuò)展后的語法樹基本邏輯結(jié)構(gòu)如下所示。另外，查詢語法樹對象只是一個中間形式，主要目的是為了生成查詢代數(shù)表達(dá)式服務(wù)。
(project(？node，？link，power)
   (path(
        start(
            bgp(
                   triiple(？s1 <http:
　　　　　　　　//jena.test/elements/type> “country”)
                   triiple(？s1 <http:
　　　　　　　　//jena.test/elements/name> “A國”)
             )
        )
    end(
        bgp(
               triiple(？s2 <http:
　　　　　　　//jena.test/elements/type> “country”)
                triiple(？s2 <http:
　　　　　　　//jena.test/elements/name> “B國”)
           )
)
   node(
        bgp(
            triiple(？s1 ？link ？node)
            triiple(？node ？link ？s2)
             triiple(？node<http:
　　　　　　　//jena.test/elements/type> “keypoint”)
            triiple(？node <http:
　　　　　　　　//jena.test/elements/power> ？power)
           )
        )
))))
2.2 生成查詢代數(shù)表達(dá)式
　ARQ引擎在正確生成查詢語法樹后則通過查詢語法檢查，此時可將語法樹中描述的操作轉(zhuǎn)換為ARQ引擎中與之對應(yīng)的算術(shù)運(yùn)算操作或者算術(shù)運(yùn)算操作組合[8]。在ARQ引擎中，每種算術(shù)運(yùn)算操作都有一個與之對應(yīng)的運(yùn)算操作類型對象，用來封裝和存儲該運(yùn)算的基本信息以及與其他運(yùn)算操作之間的協(xié)作關(guān)系，以達(dá)到最終的查詢目的。
　擴(kuò)展SPARQL標(biāo)準(zhǔn)后，ARQ引擎中并不存在與擴(kuò)展后的關(guān)鍵詞對應(yīng)的算術(shù)運(yùn)算操作類型，即無法將語法樹正確地轉(zhuǎn)換為查詢代數(shù)表達(dá)式。因此，在ARQ引擎中引入新的算術(shù)操作對象類型(PathOp)，該操作類型需要組合起點(diǎn)運(yùn)算和終點(diǎn)運(yùn)算兩個基本模式運(yùn)算對象(BgpOp)以及自身的路徑探索連接運(yùn)算。PathOp的基本設(shè)計(jì)原則是在重用已有運(yùn)算的基礎(chǔ)上加入必要的運(yùn)算操作達(dá)到路徑探索連接的目的，保證原有引擎設(shè)計(jì)結(jié)構(gòu)與實(shí)現(xiàn)方法。
2.3 查詢優(yōu)化與運(yùn)算
　成功生成查詢代數(shù)表達(dá)式后，就可以針對查詢代數(shù)表達(dá)式進(jìn)行優(yōu)化。絕大部分查詢代數(shù)運(yùn)算同樣遵循代數(shù)運(yùn)算中的結(jié)合定律與分配定律，進(jìn)行合理排列組合達(dá)到降低時間和空間復(fù)雜度的目的。新的查詢運(yùn)算建立在原有運(yùn)算基礎(chǔ)之上，可以保持針對原有運(yùn)算的優(yōu)化原則。
　最后是對運(yùn)算表達(dá)式進(jìn)行運(yùn)算，ARQ引擎采用在算術(shù)運(yùn)算部分使用修飾者模式，具體運(yùn)用了結(jié)果流迭代器技術(shù)，為新的擴(kuò)展留下空間，同時也盡量保證運(yùn)算的時空效率。因此在實(shí)現(xiàn)擴(kuò)展運(yùn)算的時候只需繼承或封裝上級結(jié)果流迭代器，在本迭代器中實(shí)現(xiàn)路徑探索連接的運(yùn)算過程。目前采用向后迭代、向前迭代和雙向迭代三種迭代算法。
　(1)向后迭代。首先將起點(diǎn)放入候選隊(duì)列，取出候選隊(duì)列第一項(xiàng)與數(shù)據(jù)集中的其他節(jié)點(diǎn)進(jìn)行迭代匹配，若匹配成功并且匹配深度小于最大深度約束，則將本條匹配加入候選隊(duì)列；若與終點(diǎn)連接成功，則該匹配為一條匹配路徑并返回。重復(fù)上述過程，直到候選隊(duì)列為空。
　(2)向前迭代的過程與向后迭代完全相同，只是將終點(diǎn)放入候選隊(duì)列，然后開始迭代過程。
　(3)雙向迭代。讓向前與向后迭代同時進(jìn)行，每個方向都有一個候選隊(duì)列，每次向前隊(duì)列匹配成功則與向后候選隊(duì)列中的項(xiàng)進(jìn)行匹配連接，若連接成功，則返回該連接匹配，反之亦然。雙方將各自匹配成功的并且小于最大深度約束的匹配項(xiàng)加到各自的候選隊(duì)列，當(dāng)其中任意一方的候選隊(duì)列為空時，迭代結(jié)束。
3 實(shí)驗(yàn)結(jié)果分析
3.1 節(jié)點(diǎn)間關(guān)系路徑
　節(jié)點(diǎn)間關(guān)系路徑實(shí)驗(yàn)在測試數(shù)據(jù)集上進(jìn)行，查詢條件與圖1基本一致。該實(shí)驗(yàn)主要測試查詢節(jié)點(diǎn)間可能存在的關(guān)系路徑，選取的起點(diǎn)為“A國”，終點(diǎn)為“B國”，查詢出來的路徑較多，經(jīng)過power因子過濾和修正之后，主要有3條路徑，圖1給出了這3條關(guān)系路徑的基本邏輯關(guān)系圖。

3.2 單節(jié)點(diǎn)周圍散射關(guān)系路徑
　單節(jié)點(diǎn)周圍散射關(guān)系路徑實(shí)驗(yàn)主要測試在不限定終點(diǎn)的情況下查詢單節(jié)點(diǎn)周圍散射的各種關(guān)系路徑。本實(shí)驗(yàn)僅限制起點(diǎn)“A國”，同樣查出的路徑比較多，經(jīng)過power因子過濾和修正后主要有8條路徑，圖2給出了這8條路徑的基本邏輯關(guān)系圖。

　這兩類實(shí)驗(yàn)測試表明，所做擴(kuò)展基本能達(dá)到預(yù)期的目標(biāo)，但同時也存在一定的問題。在比較復(fù)雜和寬泛的語義環(huán)境下，節(jié)點(diǎn)間的關(guān)系很多而且比較繁雜，如何從如此多的關(guān)系路徑中搜尋到有意義的路徑仍然是一個難題。本實(shí)驗(yàn)嘗試使用一個power因子來描述單個關(guān)系的重要性，在一定程度上可以緩解這個問題，但仍然還有較大的不足之處。
　本文所要解決的問題是在項(xiàng)目實(shí)踐中提出的，目的是為了豐富和完善現(xiàn)有的SPARQL標(biāo)準(zhǔn)及功能，增強(qiáng)RDF數(shù)據(jù)的實(shí)際應(yīng)用能力，滿足語義網(wǎng)應(yīng)用與開發(fā)中對關(guān)系路徑搜索能力的需求。通過閱讀大量的文檔及文獻(xiàn)，提出了比較合理的SPARQL擴(kuò)展標(biāo)準(zhǔn)，并認(rèn)真閱讀開源ARQ查詢引擎源碼，在原有功能的基礎(chǔ)上植入新的關(guān)系路徑搜索功能，相信會進(jìn)一步提升SPARQL及RDF的應(yīng)用前景。下一步的工作計(jì)劃是進(jìn)一步完善和加強(qiáng)SPARQL在關(guān)系搜索領(lǐng)域的能力。例如，引入排序因子等技術(shù)提升查找路徑的關(guān)鍵性與有效性，同時進(jìn)一步提高SPARQL搜索性能。
參考文獻(xiàn)
[1] Resource Description Framework (RDF)[EB/OL]. http：//www.w3.org/2001/sw/wiki/RDF，2011-01-03.
[2] Jena-a semantic Web framework for Java[EB/OL]. http：//openjena.org/index.html，2011-01-03.
[3] Sparql2sql a query engine for SPARQL over jena triple stores[EB/OL]. http：//jena.sourceforge.net/sparql2sql/，2007-11-10.
[4] SPARQL Query Language for RDF[EB/OL]. http：//www.w3.org/TR/rdf-sparql-query/，2008-01-15.
[5] ARQ-SPARQL Processor for Jena[EB/OL]. http：//openjena.org/ARQ/，2011-01-03.
[6] Extensions in ARQ[EB/OL]. http：//openjena.org/ARQ/extension. html，2011-01-03.
[7] ARQ-Extending Query Execution[EB/OL]. http：//openjena.org/ARQ/arq-query-eval.html，2011-01-03.
[8] ARQ-SPARQL Algebra[EB/OL]. http：//openjena.org/ARQ/algebra.html，2011-01-03.

原創(chuàng)聲明：此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。

相關(guān)內(nèi)容