semQA: SPARQL with Idempotent Disjunction.
semQA: SPARQL with Idempotent Disjunction.
复制标题
semQA：具有幂等析取的 SPARQL。
DOI：
10.1109/tkde.2008.91
复制
发表时间：
2009
影响因子：
8.9
通讯作者：
Kabuka,MansurR
中科院分区：
文献类型：
--
作者：
Shironoshita,EPatrick;Jean-Mary,YvesR;Bradley,RayM;Kabuka,MansurR
SPARQL LeftJoin抽象运算符在Union上不是分布式的;这限制了图模式的代数操作，进而限制了为分布式处理或查询优化创建查询计划的能力。在本文中，我们提出了semQA，一个代数扩展的SPARQL查询语言的RDF，它克服了这个问题，通过使用幂等析取算子或作为替代联盟转换图形模式。这允许应用一组等价项，将查询转换为不同的形式。我们进一步提出了一个算法，以获得原始查询的解决方案集从一个查询的解决方案，其中Union已被替换为Or。我们还分析了SPARQL的组合复杂性，证明它是NP完全的。它还表明，SPARQL查询语言是不是，在一般情况下，固定参数听话。实验结果验证了本文提出的查询评估方法对SPARQL标准，以证实复杂性分析，并说明通过应用semQA可以获得的处理成本降低的收益。
The SPARQL LeftJoin abstract operator is not distributive over Union; this limits the algebraic manipulation of graph patterns, which in turn restricts the ability to create query plans for distributed processing or query optimization. In this paper, we present semQA, an algebraic extension for the SPARQL query language for RDF, which overcomes this issue by transforming graph patterns through the use of an idempotent disjunction operator Or as a substitute for Union. This permits the application of a set of equivalences that transform a query into distinct forms. We further present an algorithm to derive the solution set of the original query from the solution set of a query where Union has been substituted by Or. We also analyze the combined complexity of SPARQL, proving it to be NP-complete. It is also shown that the SPARQL query language is not, in the general case, fixed-parameter tractable. Experimental results are presented to validate the query evaluation methodology presented in this paper against the SPARQL standard, to corroborate the complexity analysis, and to illustrate the gains in processing cost reduction that can be obtained through the application of semQA.