外贸平台app,衡水seo排名,企业文化墙设计图效果图,简约风格装修论文作者之一#xff1a;杨炫兴#xff0c;天津大学博士生。链接#xff1a;http://cic.tju.edu.cn/faculty/zhangxiaowang/publication/ASK.pdf动机SPARQL是万维网联盟#xff08;World Wide Web Consortium#xff0c;简记W3C#xff09;推荐的知识图谱标准查询语言杨炫兴天津大学博士生。链接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标准中三类否定构子NegationDIFF_F、DIFF和MINUS结合的子语言共计64个子语言给出了其完整的表达关系哈斯图(Hasse Diagram)。相比SELECT查询表达性ASK查询刻画的是子语言之间更细微的表达差异性。这项工作研究结果将有助于为SELECT查询提供优化理论基础进一步完善SPARQL理论体系是官方提出的为RDF数据定制的查询语言。亮点本文的主要贡献可以概括为以下四点1分析并刻画了所有涉及SPARQL1.0算ANDUNIONOPT_FFILTER的共16个子语言之间的表达关系哈斯图。2分析并刻画了1中的16个子语言在引入MINUS算子后的表达关系哈斯图。3 分析并刻画了1中的16个子语言在引入DIFF算子后的表达关系哈斯图。背景知识SPARQL 算子语义简介SPARQL查询的语义通过映射集合Mapping Set来体现一条三元组模式triple pattern在一个给定的RDF图上的语义为一个包含所有能够“将该三元组模式匹配到该RDF图上某条三元组”的映射mapping的集合。不同算子的语义代表了映射集合之间不同的二元操作我们这里仅做直观的介绍具体的形式化定义请参考论文。1AND 算子代表“连接”的语义(P1 AND P2)返回的是一个包含所有“同时将 P1 和 P2 匹配到图上某个子图”的映射的集合。2UNION 算子代表“联合”的语义(P1 UNION P2)返回一个包含所有“将 P1 或 P2 匹配到图上某个子图”的映射的集合。3DIFF算子代表“减法”的语义(P1 DIFF P2)返回一个包含所有“将P1匹配到图上某个子图且不能扩展为将 P2 匹配到图上某个子图”的映射的集合。4MINUS算子的语义与DIFF相似。区别在于当 P1 和 P2 之间没有共享变量时P1 DIFF P2 返回的是空集此时 P2 非空而因为没有共享变量不会产生冲突任意P1中的映射都可扩展为 P2 中的映射或 P1此时 P2 为空集而(P1 MINUS P2)返回的永远是 P1。5OPT 算子则是 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 patternSELECT查询返回的是一个包含所有将该图模式匹配到图上的映射的集合ASK则返回的该映射集合是否为空的真值True/False。两个查询PQ在SELECT查询中等价当且仅当对于任何查询图P和Q在该图上的SELECT查询返回相同的映射集合。而两个查询PQ在ASK查询中等价当且仅当对于任何查询图P和Q在该图上的ASK查询返回相同的真值。因此两个查询PQ在SELECT查询中等价可以推导出其在ASK查询中也等价反之则不一定成立。ASK查询的表达性问题的定义对于任意两个子语言W1和W2我们称W1可被W2表达当且仅当给定W1中任意的查询PW2中都可找到一个查询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查询中DIFFAND和FILTER算子分别代表了分隔图isolated graph整体连通和查询图同构层面上的形状这三个彼此不相交的性质。这些新发现的性质对于SPARQL的查询的发现新优化方法提供了思路。 OpenKG开放知识图谱简称 OpenKG旨在促进中文知识图谱数据的开放与互联促进知识图谱和语义技术的普及和广泛应用。点击阅读原文进入 OpenKG 博客。
