Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TKDE.2008.91 | IEEE transactions on knowledge and data engineering |
Keywords | Field | DocType |
sparql standard,idempotent disjunction,query optimization,graph pattern,algebraic extension,algebraic manipulation,sparql query language,original query,query plan,query evaluation methodology,sparql leftjoin abstract operator,computational complexity,np complete problem,resource description framework,pattern matching,query language,graph theory,query languages,distributed processing,database languages,sparql,algebra,ontology,mathematical model,algorithm design and analysis,rdf | Data mining,Query language,Programming language,Computer science,SPARQL,Theoretical computer science,Artificial intelligence,Query optimization,RDF query language,Query expansion,Sargable,Named graph,Boolean conjunctive query,Machine learning | Journal |
Volume | Issue | ISSN |
21 | 3 | 1041-4347 |
Citations | PageRank | References |
3 | 0.51 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| E. Patrick Shironoshita | 1 | 122 | 6.15 |
| Yves R. Jean-Mary | 2 | 124 | 5.47 |
| Ray M. Bradley | 3 | 6 | 1.60 |
| Mansur R. Kabuka | 4 | 250 | 16.95 |