模糊RDF數據的一種查詢語言擴展

趙羽晗，胡 磊

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211100)

0 引 言

資源描述框架(RDF)是W3C推廣的標準數據模型，用于表示Web上可用資源的有關信息。RDF遵循互操作性、可擴展性、演進和權力下放的W3C設計原則，應用于生物網絡、社會網絡、大型知識庫等多個領域。因此，大量的RDF存儲庫已經被創建，并且一再被觀察到，數據庫社區面臨著應對RDF細節的新挑戰。然而，一些數據本質上是模糊的或不精確的，因為它們的值在現實應用中是主觀的。需要模糊地表達或描述信息[1]。然而，從機器的角度來看，以這種方式呈現信息并不熟練。因此，研究數據模型和不精確或不確定性的具有不同策略的組合是重要的[2]。因此在文獻[3]中，基于模糊集理論，提出了一項模糊RDF數據模型，用來表達信息中的不確定性?？紤]了RDF圖，其中數據是通過附加到邊或節點的內在加權值來描述的，這個權重可以表示任何漸進的概念。

目前在語義網領域一直致力于RDF數據處理解決方案的開發，如存儲、查詢、維護等等，由于數據量巨大，數據的異質性、模糊性和廣泛的連通性，對這些RDF圖的各種查詢的高效應答是最重要的問題之一[4]。作為RDF查詢語言的官方W3C推薦標準SPARQL[5]，對于RDF數據模型起著與SQL在關系數據模型中相同的作用。它提供了基本的功能，以便通過圖模式查詢RDF數據[6-7]。但是傳統的SPARQL缺乏一些表達性和可用性的功能，這在實際應用中是非常重要的。

在這些情形的驅動下，已經研究出了可以表達信息中豐富模糊性的模糊RDF數據模型[8]，應該定義新的更靈活的查詢語言。目標是擴展SPARQL，以便支持靈活查詢清晰和模糊的RDF圖形數據庫(當數據不精確時)。

該文提出了一種擴展SPARQL的模糊查詢語言。該語言可以更有效地對模糊RDF數據進行查詢，對傳統的SPARQL圖模式進行了模糊擴展，并將模糊量化語句集成到擴展后的模糊查詢中，這使得資源中的模糊性在用戶搜索過程中得到表達，使得結果更滿足用戶的需求。然后采用文獻[9]中Yager基于OWA的解釋來對查詢進行評估，最后討論了該查詢的具體實現方法和流程。

1 模糊RDF模型

介紹了一種模糊RDF數據模型的形式化，這是基于模糊圖[10]在模糊集理論中的特征定義的。

簡而言之，模糊RDF數據模型的基本結構是一個圖表。設V為有限的頂點集，E?Vi×Vj為一組邊緣，L:V∪E→Σ為從頂點和邊緣到稱為標簽的字符串集合Σ的映射。四元組GM=(V,E,Σ,L)是有向標記圖。假設M是由(s,p,o)∈U∪B×U×U∪L∪B表示的一組RDF三元組。從M到GM的轉換函數包括對每個(s,p,o)∈M的以下兩個步驟：

(1)將頂點vs，vo加到V并分配L(vs)=s，L(vo)=o；

(2)向E中添加一個有向邊(vs,vo)并分配L(vs,vo)=p。應該注意的是，圖形結構僅簡要描述了RDF數據模型的結構特征，忽略了RDF數據模型的頂點和邊緣的模糊內容。下面是更詳細的模糊RDF圖形數據模型的正式定義。

定義1(模糊RDF數據圖)：模糊RDF數據圖G由六元組(V,E,Σ,L,μ,ρ)表示。這里

(1)V是一組有限的頂點；

(2)E?Vi×Vj是一組有向邊，其中Vi,Vj?V；

(3)Σ是一組標簽；

(4)L:V∪E→Σ分別為頂點和邊緣分配標簽的函數；

(5)μ:V→[0,1]是V的模糊子集；

(6)ρ:E→[0,1]是模糊子集μ的模糊關系。注意?vi,vj∈V， ρ(vi,vj)≤μ(vi)∧μ(vj)，其中∧代表最小值。

在定義1中，圖G的每個頂點vi∈V具有對應于RDF三元組數據集中的對象或客體的一個標簽L(vi)。此外，vi,vj∈E是從頂點vi到頂點vj的有向邊，邊的標簽L(vi,vj)對應于RDF三元組中的謂詞。頂點的標簽值與模糊度相關聯，指示頂點取標簽的可能性，并且與每個邊緣相關聯的模糊值表示頂點之間對應關系的不一致量。

模糊RDF數據圖可以包含模糊頂點(相應的邊)和清晰頂點(相應的邊)，作為0或1度的模糊頂點(相應的邊)可以被認為是清晰的。同樣的，一般RDF圖是最簡單的模糊RDF數據圖，其中μ:V→{0,1}，對于所有的vi∈V，且ρ:V×V→{0,1}，模糊RDF圖是清晰RDF圖的一般化。

此外，在此模型中，模糊RDF圖的每個頂點和邊緣與一個隸屬度值相關聯，即，三元組的每個元素都存在模糊值，如圖1所示。

圖1 模糊RDF三元組

2 SPARQL擴展

2.1 語義和語法

下面，介紹一種模糊的RDF查詢語言，它使用模糊圖模式擴展SPARQL圖模式。

在語義上，擴展依賴于之前模糊RDF數據模型的相關定義。在語法上，擴展了經典的SPARQL，允許模糊圖模式出現在WHERE子句中，而模糊條件出現在FILTER子句中。如SPARQL 1.1[11]中所定義，模糊正則表達式接近屬性路徑，并且它涉及模糊的結構屬性(例如模糊圖上的距離)。

首先，介紹一些關于模糊量詞的重要概念。由于存在模糊量詞，因此能夠根據自然語言對量詞進行建模。在文獻[12]中，Zadeh將量詞區分為絕對量詞(例如五個以上)和相對量詞(例如很多)。絕對量詞指的是一個數字，而相對量詞指的是一個比例。一個絕對量詞由從整數或實數范圍到[0，1]的μQ函數表示，而相對量詞是從[0，1]到[0，1]的μQ映射。在這兩種情況下，如果恰好X中的j個元素完全滿足條件A，而X中的其他元素完全不滿足A時，則將該值μQ(j)定義為語句“Q X are A”的真值。

現在，考慮在模糊RDF圖數據庫上使用類型為“Q B X are A”的模糊量化語句。其中，量詞Q由模糊集合表達，該模糊集可以表示相對量詞(例如很少)或絕對量詞(例如超過五個)，B是連接到節點x的模糊狀態，X是RDF圖中的一組節點集，A表示模糊條件。這種語法的一個例子是：“很少有演員出生在休斯頓，他們出演的電影收視率高，票房低。”

下面給出模糊SPARQL語言中模糊量化查詢的一般語法形式。

DEFINE ...

SELECT ?var

WHERE {

B(?var, ?X)

GROUP BY ?var

HAVING (Q(?X) ARE ( A(?X) )

}

DEFINE子句用于定義由Q表示的模糊量詞和在模糊條件下的模糊形容詞。SELECT子句確定應在解決方案集中返回哪些變量，以?var表示。B(?var, ?X)和A(?X)是SPARQL模式，使得變量?var和?X連接在B中，并且?X滿足A。

例1：假設有一個查詢旨在檢索所有滿足條件的導演(?person)，他所執導的許多具有較高利潤的電影(?film)都受到高度關注，并且演員Jack極有可能參演了他的電影?？梢允褂媚：齋PARQL表示如下：

DEFINEASC many AS (1,5)

DEFINEASC high gross AS (10,100)

DEFINEASC highly regarded AS (5,20)

DEFINEASC high probability AS (0,1)

SELECT ?person WHERE {

?film directBY ?person.

?film starring Jack.

FILTER (Jack IS high probability)}

GROUP BY ?person

HAVING many(?film) ARE

( ?film audience rating ?r.

?film box office ?b.

FILTER (?r IS highly regarded&& ?b IS high gross) )

其中DEFINEASC子句定義了遞增的隸屬函數(許多、高利潤、高關注度和高概率)。如果存在任何遞減的隸屬函數，也可以使用DEFINEDSC子句。在此查詢中，?person對應于?var，?film對應于?X，WHERE子句中的前三行對應于B，HAVING子句中的內容對應于A。

在定義了模糊SPARQL的量化查詢語法之后，則需要對SPARQL圖模式進行一定的擴展。標準SPARQL的圖模式為若干個三元組組成的圖形化表示，根據以上提出的模糊SPARQL語法，一個模糊SPARQL查詢F(x)可以定義為(N,E,B(x,y),A(y),f(y))。

其中，N為模糊RDF圖的頂點且x,y∈N，x即目標變量，y為查詢中與x有關的節點；E為模糊RDF的有向邊；B(x,y)和A(y)是兩個為與x相關的頂點或邊分配的函數映射，它們可以是常量、變量或者預定義的模糊隸屬函數，一般在FILTER子句中表示；f(y)為模糊量詞函數，附加于與x相關的頂點或邊，在HAVING子句中表示。

由第一節可知，模糊RDF圖模型的表示為GF=(N,E,Σ,L,μ)。聯系模糊定量查詢F(x)的定義，節點x和邊e滿足三元組模式(s,p,o)的對應，隸屬函數B(x,y)的值由μx和μy(y由查詢語句確定)計算得出，函數A(y)的值代入μy計算；f(y)則是對中間結果集的一個篩選，由分組后中間結果集的數量對模糊量詞的滿足程度來決定，按從高到低的結果排序。

2.2 評估策略

當嘗試計算語句“Q X are A”的真實值時，必須確定滿足A的X元素集的基數。如果A是布爾謂詞，則該基數是精確整數k，并且“Q X are A”的真實值是μQ(k)。如果A是一個模糊謂詞，則無法精確地建立基數，因此應該計算去建立一個不精確參數的函數值μQ所對應的量化。

現在從文獻中介紹一種方法來解釋“Q B X are A”形式的量化語句，該方法通過考慮量詞適用的集合是模糊的來概括“Q X are A”的情況。在文獻[9]中，Yager提出通過蘊含值μB(x)→KDμA(x)的OWA聚合來計算類型“Q B X are A”的語句的真實值，其中→KD代表Kleene-Dienes蘊含a→KDb=max(1-a,b)。

可以使用上述公式來解釋模糊SPARQL查詢的模糊量化語句。為了檢索初始查詢的B部分的元素，使之與需要計算最終滿意程度的變量?var和?X匹配，應該將原始查詢派生到下面給出的中間查詢Finter中。對于每對(?var，?X)，檢索計算μB和μA所需的所有信息，即與關系相關的模糊度和在B(?var，?x)和A(?X)中涉及的節點屬性值的組合。分別由UB和UA表示。

SELECT ?var ?XUBUA

WHERE {

B(?var, ?X)

OPTIONAL {A(?X)}

}

通過簡單的后處理步驟，可以根據UB和UA來計算滿意度μB和μA。如果可選部分與給定的答案不匹配，則μA=0。為簡單起見，我們接下來考慮Finter的結果是由與查詢匹配的四元組(?var,?X,μB,μA)構成。

3 實現流程

本章討論與所提出的方法有關的實施問題。必須考慮兩個方面：(1)模糊RDF圖的存儲；(2)模糊SPARQL查詢的評估。

第一點提出的問題比較容易解決，因為可以使用將模糊度附加到三元組的泛化機制。關于模糊SPARQL查詢的評估，可以考慮兩種體系結構。第一個解決方案是在數據管理系統內部實現一個特定的查詢評估引擎。這個方案的優點是直接在查詢引擎中實現的優化技術應該使得系統對查詢處理非常高效。這個方案最大的局限性是，在分布式體系結構中對模糊SPARQL查詢的評估意味著在每個SPARQL端點上都需要有可用的模糊SPARQL查詢評估器，這在具體應用中是不現實的存在。

另一種更現實的架構是在一個標準的SPARQL引擎(端點)上增加一個模糊SPARQL軟件層。這個層主要包含一個查詢編譯器，它產生一個用于檢索適當數據的(清晰的)SPARQL查詢，一個用于計算滿意度的(依賴于查詢的)函數和一個用于排序答案的(依賴于查詢的)函數。

為了處理該查詢，建議在標準的經典SPARQL引擎上使用軟件附加層。該軟件是SURF，在Jena語義網的Java框架內實現，用于創建和處理RDF圖。SURF能夠評估包含模糊量化語句的模糊SPARQL查詢，在前面已經給出了模糊SPARQL的特定語法。它主要由兩個模塊組成。

(1)預處理模塊，即查詢編譯器，它根據Yager基于OWA的方法，生成與查詢相關的函數，通過這些函數能夠計算并針對每個返回的答案。它還可以生成清晰的SPARQL查詢，并將其發送到SPARQL查詢引擎以檢索計算和計算所需的信息。編譯使用文獻[13]中引入的推導原理。

(2)后處理模塊，該模塊首先對元素進行GROUP BY，然后計算，并為每個返回的答案進行排序，如果在初始模糊查詢中已指定閾值，則對它們進行過濾。

這種體系結構如圖2所示。

圖2 SURF體系結構

對于“Q B X are A”類型的量化查詢，原則是首先評估從原始查詢導出的模糊查詢Finter。對于來自Finter的結果的每個元組x，返回與條件A和B相關的滿意度，分別由μB和μA表示?？梢允褂忙藼和μA的值根據定量查詢評估公式計算最終滿足度μ。目前，Yager基于OWA的方法[14]已經實施，并且要使用的解釋的選擇是通過系統的配置工具完成的。最后，得到一組按滿意度降序排列的答案。

4 結束語

現實世界中存在著大量的不確定信息，因此RDF數據模型中模糊信息的表達是如今數據庫方面重要的研究領域，而對這些模糊數據的有效查詢是非常重要的一項工作。該文提出了一項針對SPARQL查詢語言的擴展，這使得查詢之前介紹的模糊RDF數據模型成為可能。通過模糊圖模式擴展了標準SPARQL的圖模式，在查詢中融入模糊量詞，給出了模糊SPARQL查詢語言的語法和語義。還給出了針對模糊量化查詢的一種評估策略，最后討論了該查詢的具體實現的方法和流程。

目前仍然處在對互聯網中不確定信息處理的初級階段。將來的工作有必要更深入地討論模糊查詢的精確性和全面性，以保證用戶檢索到的結果是符合需求的。此外，還要探索用其他方式或者在更復雜的條件下擴展查詢語言，并對其進行更細致的評估，最終找到在實際應用中最有效的模糊信息處理方式。