论文浅尝 | SPARQL 语言的 ASK 查询表达性研究进展

2019 年 11 月 20 日 开放知识图谱

论文作者之一：杨炫兴，天津大学博士生。

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

动机

SPARQL是万维网联盟（World Wide Web Consortium，简记W3C）推荐的知识图谱标准查询语言，其包含四类查询：SELECT、CONSTRUCT、ASK和DESCRIBE。与一般SELECT查询返回解不同，ASK查询返回布尔值（真或假）。自从2008年1月15日，万维网联盟W3C 首次发布SPARQL1.0到2013年进一步发布SPARQL1.1，以SELECT为代表的SPARQL基础理论取得较大进展。近年来，牛津大学开始研究CONSTRUCT并取得一些进展。然而，归咎于ASK基础理论刻画SPARQL的复杂问题，目前鲜有ASK基础理论研究工作。这项工作开始尝试研究ASK查询的表达能力（即，布尔表达性），并对SPARQL1.0标准的核心语言（由四个构子AND、OPT_F、UNION、FILTER构成的语言）以及这些子语言与SPARQL1.1标准中三类否定构子（Negation）：DIFF_F、DIFF和MINUS结合的子语言，共计64个子语言，给出了其完整的表达关系哈斯图(Hasse Diagram)。相比SELECT查询表达性，ASK查询刻画的是子语言之间更细微的表达差异性。这项工作研究结果将有助于为SELECT查询提供优化理论基础，进一步完善SPARQL理论体系是官方提出的为RDF数据定制的查询语言。

亮点

本文的主要贡献可以概括为以下四点：

（1）分析并刻画了所有涉及SPARQL1.0算（AND，UNION，OPT_F，FILTER）的共16个子语言之间的表达关系哈斯图。

（2）分析并刻画了（1）中的16个子语言在引入MINUS算子后的表达关系哈斯图。

（3）分析并刻画了（1）中的16个子语言在引入DIFF算子后的表达关系哈斯图。

背景知识

SPARQL 算子语义简介

SPARQL查询的语义通过映射集合（Mapping Set）来体现：一条三元组模式（triple pattern）在一个给定的RDF图上的语义为，一个包含所有能够“将该三元组模式匹配到该RDF图上（某条三元组）”的映射（mapping）的集合。

不同算子的语义代表了映射集合之间不同的二元操作，我们这里仅做直观的介绍，具体的形式化定义请参考论文。

（1）AND 算子代表“连接”的语义：(P₁ AND P₂)返回的是一个包含所有“同时将 P₁ 和 P₂ 匹配到图上（某个子图）”的映射的集合。

（2）UNION 算子代表“联合”的语义，(P₁ UNION P₂)返回一个包含所有“将 P₁ 或 P₂ 匹配到图上（某个子图）”的映射的集合。

（3）DIFF算子代表“减法”的语义，(P₁ DIFF P₂)返回一个包含所有“将P₁匹配到图上（某个子图），且不能扩展为将 P₂ 匹配到图上（某个子图）”的映射的集合。

（4）MINUS算子的语义与DIFF相似。区别在于当 P₁和 P₂ 之间没有共享变量时，P₁ DIFF P₂ 返回的是空集（此时 P₂非空，而因为没有共享变量不会产生冲突，任意P₁中的映射都可扩展为 P₂中的映射）或 P₁（此时 P₂ 为空集）；而(P₁ MINUS P₂)返回的永远是 P₁。

（5）OPT 算子则是 AND 算子和DIFF的复合算子，(P₁ OPT P₂)= ((P₁ AND P₂) UNION (P₁ DIFF P₂))。

注：SPARQL标准支持OPT_F和DIFF_F，即允许FILTER内嵌到OPT和DIFF_F中。为了简洁阐述它们语义，我们还是以OPT和DIFF为例来介绍。

下面我们通过简单例子来展示不同算子的语义：

ASK查询与SELECT查询的区别

对于一个给定的查询（即图模式，graph pattern），SELECT查询返回的是一个包含所有将该图模式匹配到图上的映射的集合，ASK则返回的该映射集合是否为空的真值（True/False）。

两个查询P，Q在SELECT查询中等价当且仅当：对于任何查询图，P和Q在该图上的SELECT查询返回相同的映射集合。而两个查询P，Q在ASK查询中等价当且仅当：对于任何查询图，P和Q在该图上的ASK查询返回相同的真值。因此两个查询P，Q在SELECT查询中等价可以推导出其在ASK查询中也等价，反之则不一定成立。

ASK查询的表达性问题的定义

对于任意两个子语言W₁和W₂，我们称W₁可被W₂表达当且仅当：给定W₁中任意的查询P，W₂中都可找到一个查询Q，使得P和Q在ASK查询中等价。

理论分析

我们通过分析不同算子能够识别的图模式的特征，并以此为依据来判断64个子语言之间的可表达关系是否成立。

1. AND只能被含有OPT的ASK查询表达

在ASK查询中，AND仅能被包含OPT构子的查询表达，这一点与SELECT查询一样。证明利用AND能表达圈性质，即一个图是否含有圈。换言之，非AND非OPT的ASK查询无法表达圈性质。

2. 含有OPT的ASK查询与含有AND的ASK查询之间可表达关系复杂

如果允许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的析取逻辑关系来表达UNION。然而，MINUS相比DIFF太弱不足以表达UNION。

5. DIFF_F只能被含有DIFF和FILTER的ASK查询表达

从DIFF_F的语义构造来看，DIFF_F同时含有DIFF和FILTER的语义特征。在ASK查询，DIFF_F的语义仍然具有重要特性。而且DIFF_F和AND结合能够表达整个本文研究SPARQL 1.1的核心子语言。从这个意义看，DIFF_F具有非常强大的表达性。除了AND，其它构子都能表示。DIFF相比DIFF_F来说，不能表达FILTER语义，因此ASK查询表达能力也降低很多。幸运地是，DIFF具有DIFF_F除了FILTER之外所有的表达能力，因此比MINUS具有较强的ASK查询表达能力。

6. MINUS可以被任何否定ASK查询表达

在ASK查询中，MINUS描述的最弱的否定ASK查询。W3C仍然作为SPARQL1.1标准推荐，笔者觉得考虑工程实际需要。因为MINUS的语义逻辑性有所欠缺。在本项工作中，准确地给出了MINUS和DIFF差异之处（UNION查询）。两者之间差异的发现有助于工程师在实际应用中，能够准确使用。

总结

本文通过分析6个SPARQL算子在ASK查询中的表达性，刻画出了所有包含这六个算子的子语言之间的表达关系哈斯图。在ASK查询中，DIFF，AND和FILTER算子分别代表了分隔图（isolated graph），整体连通和查询图（同构层面上的）形状这三个彼此不相交的性质。这些新发现的性质对于SPARQL的查询的发现新优化方法提供了思路。