論文作者之一：楊炫興，天津大學(xué)博士生。

---

鏈接：http://cic.tju.edu.cn/faculty/zhangxiaowang/publication/ASK.pdf

動機

SPARQL是萬維網(wǎng)聯(lián)盟（World Wide Web Consortium，簡記W3C）推薦的知識圖譜標準查詢語言，其包含四類查詢：SELECT、CONSTRUCT、ASK和DESCRIBE。與一般SELECT查詢返回解不同，ASK查詢返回布爾值（真或假）。自從2008年1月15日，萬維網(wǎng)聯(lián)盟W3C 首次發(fā)布SPARQL1.0到2013年進一步發(fā)布SPARQL1.1，以SELECT為代表的SPARQL基礎(chǔ)理論取得較大進展。近年來，牛津大學(xué)開始研究CONSTRUCT并取得一些進展。然而，歸咎于ASK基礎(chǔ)理論刻畫SPARQL的復(fù)雜問題，目前鮮有ASK基礎(chǔ)理論研究工作。這項工作開始嘗試研究ASK查詢的表達能力（即，布爾表達性），并對SPARQL1.0標準的核心語言（由四個構(gòu)子AND、OPT_F、UNION、FILTER構(gòu)成的語言）以及這些子語言與SPARQL1.1標準中三類否定構(gòu)子（Negation）：DIFF_F、DIFF和MINUS結(jié)合的子語言，共計64個子語言，給出了其完整的表達關(guān)系哈斯圖(Hasse Diagram)。相比SELECT查詢表達性，ASK查詢刻畫的是子語言之間更細微的表達差異性。這項工作研究結(jié)果將有助于為SELECT查詢提供優(yōu)化理論基礎(chǔ)，進一步完善SPARQL理論體系是官方提出的為RDF數(shù)據(jù)定制的查詢語言。

亮點

本文的主要貢獻可以概括為以下四點：

（1）分析并刻畫了所有涉及SPARQL1.0算（AND，UNION，OPT_F，FILTER）的共16個子語言之間的表達關(guān)系哈斯圖。

（2）分析并刻畫了（1）中的16個子語言在引入MINUS算子后的表達關(guān)系哈斯圖。

（3）?? 分析并刻畫了（1）中的16個子語言在引入DIFF算子后的表達關(guān)系哈斯圖。

背景知識

• SPARQL 算子語義簡介

SPARQL查詢的語義通過映射集合（Mapping Set）來體現(xiàn)：一條三元組模式（triple pattern）在一個給定的RDF圖上的語義為，一個包含所有能夠“將該三元組模式匹配到該RDF圖上（某條三元組）”的映射（mapping）的集合。

不同算子的語義代表了映射集合之間不同的二元操作，我們這里僅做直觀的介紹，具體的形式化定義請參考論文。

（1）AND 算子代表“連接”的語義：(P₁ AND P₂)返回的是一個包含所有“同時將 P₁ 和 P₂ 匹配到圖上（某個子圖）”的映射的集合。

（2）UNION 算子代表“聯(lián)合”的語義，(P₁ UNION P₂)返回一個包含所有“將 P₁ 或 P₂ 匹配到圖上（某個子圖）”的映射的集合。

（3）DIFF算子代表“減法”的語義，(P₁ DIFF P₂)返回一個包含所有“將P₁匹配到圖上（某個子圖），且不能擴展為將 P₂ 匹配到圖上（某個子圖）”的映射的集合。

（4）MINUS算子的語義與DIFF相似。區(qū)別在于當 P₁ 和 P₂ 之間沒有共享變量時，P₁ DIFF P₂ 返回的是空集（此時 P₂ 非空，而因為沒有共享變量不會產(chǎn)生沖突，任意P₁中的映射都可擴展為 P₂ 中的映射）或 P₁（此時 P₂ 為空集）；而(P₁ MINUS P₂)返回的永遠是 P₁。

（5）OPT 算子則是 AND 算子和DIFF的復(fù)合算子，(P₁ OPT P₂)= ((P₁ AND P₂) UNION (P₁ DIFF P₂))。

注：SPARQL標準支持OPT_F和DIFF_F，即允許FILTER內(nèi)嵌到OPT和DIFF_F中。為了簡潔闡述它們語義，我們還是以O(shè)PT和DIFF為例來介紹。

?

下面我們通過簡單例子來展示不同算子的語義：

• ASK查詢與SELECT查詢的區(qū)別

對于一個給定的查詢（即圖模式，graph pattern），SELECT查詢返回的是一個包含所有將該圖模式匹配到圖上的映射的集合，ASK則返回的該映射集合是否為空的真值（True/False）。

兩個查詢P，Q在SELECT查詢中等價當且僅當：對于任何查詢圖，P和Q在該圖上的SELECT查詢返回相同的映射集合。而兩個查詢P，Q在ASK查詢中等價當且僅當：對于任何查詢圖，P和Q在該圖上的ASK查詢返回相同的真值。因此兩個查詢P，Q在SELECT查詢中等價可以推導(dǎo)出其在ASK查詢中也等價，反之則不一定成立。

• ASK查詢的表達性問題的定義

對于任意兩個子語言W₁和W₂，我們稱W₁可被W₂表達當且僅當：給定W₁中任意的查詢P，W₂中都可找到一個查詢Q，使得P和Q在ASK查詢中等價。

理論分析

我們通過分析不同算子能夠識別的圖模式的特征，并以此為依據(jù)來判斷64個子語言之間的可表達關(guān)系是否成立。

?

1.???? AND只能被含有OPT的ASK查詢表達

在ASK查詢中，AND僅能被包含OPT構(gòu)子的查詢表達，這一點與SELECT查詢一樣。證明利用AND能表達圈性質(zhì)，即一個圖是否含有圈。換言之，非AND非OPT的ASK查詢無法表達圈性質(zhì)。

?

2.???? 含有OPT的ASK查詢與含有AND的ASK查詢之間可表達關(guān)系復(fù)雜

如果允許FILTER，那么含有OPT的ASK查詢能夠表達含有AND的ASK查詢；反之，如果不允許，那么含有AND的ASK查詢能夠表達含有OPT的ASK查詢。意外的是，含有OPT的ASK查詢與含有AND的ASK查詢不總是相互可表達。

3.???? FILTER不可被非DIFF_F或非OPT_F的ASK查詢

FILTER包含對約束條件進行查詢限制性，是不含有DIFF_F或OPT_F的ASK查詢所表達。證明利用了非DIFF_F或非OPT_F的ASK查詢無法識別完整的RDF圖，然而FILTER可以利用不等詞約束條件可以識別。

?

4.???? UNION在非MINUS的ASK查詢中是冗余的

UNION刻畫ASK查詢的非確定性。在ASK查詢下，UNION不確定性能被OPT和FILTER中的弱不確定性表達。證明分別利用了邏輯德·摩根定律思想與DIFF吸收定律和FILTER的析取邏輯關(guān)系來表達UNION。然而，MINUS相比DIFF太弱不足以表達UNION。

5.???? DIFF_F只能被含有DIFF和FILTER的ASK查詢表達

從DIFF_F的語義構(gòu)造來看，DIFF_F同時含有DIFF和FILTER的語義特征。在ASK查詢，DIFF_F的語義仍然具有重要特性。而且DIFF_F和AND結(jié)合能夠表達整個本文研究SPARQL 1.1的核心子語言。從這個意義看，DIFF_F具有非常強大的表達性。除了AND，其它構(gòu)子都能表示。DIFF相比DIFF_F來說，不能表達FILTER語義，因此ASK查詢表達能力也降低很多。幸運地是，DIFF具有DIFF_F除了FILTER之外所有的表達能力，因此比MINUS具有較強的ASK查詢表達能力。

?

6.???? MINUS可以被任何否定ASK查詢表達

在ASK查詢中，MINUS描述的最弱的否定ASK查詢。W3C仍然作為SPARQL1.1標準推薦，筆者覺得考慮工程實際需要。因為MINUS的語義邏輯性有所欠缺。在本項工作中，準確地給出了MINUS和DIFF差異之處（UNION查詢）。兩者之間差異的發(fā)現(xiàn)有助于工程師在實際應(yīng)用中，能夠準確使用。

總結(jié)

本文通過分析6個SPARQL算子在ASK查詢中的表達性，刻畫出了所有包含這六個算子的子語言之間的表達關(guān)系哈斯圖。在ASK查詢中，DIFF，AND和FILTER算子分別代表了分隔圖（isolated graph），整體連通和查詢圖（同構(gòu)層面上的）形狀這三個彼此不相交的性質(zhì)。這些新發(fā)現(xiàn)的性質(zhì)對于SPARQL的查詢的發(fā)現(xiàn)新優(yōu)化方法提供了思路。

---

?

OpenKG

開放知識圖譜（簡稱 OpenKG）旨在促進中文知識圖譜數(shù)據(jù)的開放與互聯(lián)，促進知識圖譜和語義技術(shù)的普及和廣泛應(yīng)用。

點擊閱讀原文，進入 OpenKG 博客。

總結(jié)

以上是生活随笔為你收集整理的论文浅尝 | SPARQL 语言的 ASK 查询表达性研究进展的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。