Shironoshita E Patrick, Jean-Mary Yves R, Bradley Ray M, Kabuka Mansur R
INFOTECH Soft, Inc., 9200 S. Dadeland Blvd., Suite 620, Miami, FL 33156. E-mail:
IEEE Trans Knowl Data Eng. 2009 Mar 1;21(3):401-414. doi: 10.1109/TKDE.2008.91.
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.
SPARQL左连接抽象运算符对并集不具有分配性；这限制了图形模式的代数操作，进而限制了为分布式处理或查询优化创建查询计划的能力。在本文中，我们提出了semQA，这是一种针对RDF的SPARQL查询语言的代数扩展，它通过使用幂等析取运算符Or作为并集的替代来转换图形模式，从而克服了这个问题。这允许应用一组将查询转换为不同形式的等价关系。我们进一步提出了一种算法，从用Or替代了并集的查询的解集推导出原始查询的解集。我们还分析了SPARQL的组合复杂性，证明其为NP完全问题。还表明，一般情况下，SPARQL查询语言不是固定参数可处理的。给出了实验结果，以对照SPARQL标准验证本文提出的查询评估方法，以证实复杂性分析，并说明通过应用semQA可在处理成本降低方面获得的收益。
