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

 

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

链接: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 算子代表“连接”的语义:(P1 AND P2)返回的是一个包含所有“同时将 P1 和 P2 匹配到图上(某个子图)”的映射的集合。

(2)UNION 算子代表“联合”的语义,(P1 UNION P2)返回一个包含所有“将 P1 或 P2 匹配到图上(某个子图)”的映射的集合。

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

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

(5)OPT 算子则是 AND 算子和DIFF的复合算子,(P1 OPT P2)= ((P1 AND P2) UNION (P1 DIFF P2))。

注: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查询的表达性问题的定义

对于任意两个子语言W1和W2,我们称W1可被W2表达当且仅当:给定W1中任意的查询P,W2中都可找到一个查询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的查询的发现新优化方法提供了思路。

 

OpenKG

开放知识图谱(简称 OpenKG)旨在促进中文知识图谱数据的开放与互联,促进知识图谱和语义技术的普及和广泛应用。

发表评论

邮箱地址不会被公开。 必填项已用*标注