sparql - 如何使用 Python 确定两个 SPARQL 查询是否相同？

Question

当使用 SPARQL 查询 RDF 数据集时，同一个查询可以用多种不同的方式编写。例如，sparql 查询对于其中的某些子句始终是置换不变的。此外，我们可以重命名 sparql 查询中的变量。但是我们如何识别那些相同的 SPARQL 查询呢？理想情况下，应该有一个python包可以将一个sparql查询(即一个字符串对象)解析成一个查询对象，不同的字符串共享相同的底层查询被解析成同一个对象，然后我们可以简单地比较解析后的查询对象确定两个 sparql 查询是否相同。有没有这样的工具(似乎 rdflib 中的 prepareQuery() 不能以这种方式工作)？如果没有，那我该怎么办？

语义相同的查询示例:

SELECT ?x WHERE { ?x foaf:haha ?k .\n ?person foaf:knows ?x .}
SELECT ?s WHERE { ?person foaf:knows ?s .\n ?s foaf:haha ?k .}

Answer 1

论文"Generating SPARQL Query Containment Benchmarksusing the SQCFramework" by Muhammad Seleem et al. , 提到“SPARQL 查询包含求解器”，其中

Query containment is the problem of deciding if the result set of a query Q1 is included in the result set of another query Q2

如果您使用这样的求解器来测试 Q1 的结果集是否是 Q2 的子集，反之亦然，您已经确定它们在语义上是相同的。

至于您的“现成工具”:前一篇论文提到那些在另一篇论文中进行了测试"Evaluating and benchmarking sparql query containment solvers." by M.W. Chekol et al..

关于复杂性和可计算性，后一篇论文提到:

The query containment problem for full SPARQL is undecidable [15, 1]. Hence, it is necessary to reduce SPARQL in order to consider it. A double exponential upper bound has been proven for the containment and equivalence problems of SPARQL queries without OPTIONAL , FILTER and under set semantics [7].

但是，双向查询包含只是确定查询身份的一种方式。我不知道是否有证据证明查询身份比查询包含具有更好的复杂性/可计算性(或相反的证据)。