Marcelo Arenas
ABSTRACT
SPARQL -the standard query language for querying RDF- provides only limited navigational functionalities, although these features are of fundamental importance for graph data formats such as RDF. This has led the W3C to include the property path feature in the upcoming version of the standard, SPARQL 1.1.We tested several implementations of SPARQL 1.1 handling property path queries, and we observed that their evaluation methods for this class of queries have a poor performance even in some very simple scenarios. To formally explain this fact, we conduct a theoretical study of the computational complexity of property paths evaluation. Our results imply that the poor performance of the tested implementations is not a problem of these particular systems, but of the specification itself. In fact, we show that any implementation that adheres to the SPARQL 1.1 specification (as of November 2011) is doomed to show the same behavior, the key issue being the need for counting solutions imposed by the current specification. We provide several intractability results, that together with our empirical results, provide strong evidence against the current semantics of SPARQL 1.1 property paths. Finally, we put our results in perspective, and propose a natural alternative semantics with tractable evaluation, that we think may lead to a wide adoption of the language by practitioners, developers and theoreticians.
- F. Alkhateeb, J.-F. Baget, and J. Euzenat. Extending SPARQL with regular expression patterns (forquerying RDF). JWS, 7(2):57--73, 2009. Google Scholar
Digital Library
- C. Àlvarez and B. Jenner. A very hard log-space counting class. Theor. Comput. Sci., 107(1):3--30, 1993. Google ScholarDigital Library
- P. Barceló, C. A. Hurtado, L. Libkin, and P. T. Wood. Expressive languages for path queries over graph-structured data. In PODS, pages 3--14, 2010. Google ScholarDigital Library
- D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. In PODS, pages 194--204, 1999. Google ScholarDigital Library
- J. J. Carroll, I. Dickinson, C. Dollin, D. Reynolds, A. Seaborne, andK. Wilkinson. Jena: implementing the semantic web recommendations. In WWW (Alternate Track Papers & Posters), pages 74--83, 2004. Google ScholarDigital Library
- O. Corby and C. Faron-Zucker. The KGRAM abstract machine for knowledge graph querying. In Web Intelligence, pages 338--341, 2010. Google ScholarDigital Library
- L. Eggan. Transition graphs and the star-height of regular events. The Michigan mathematical journal, 10(4):385--397, 1963.Google Scholar
- J. Gantz et al. The diverse and exploding digital universe: An updated forecast of worldwide information growth through 2011. International Data Corporation, White Paper, 2008.Google Scholar
- G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. TODS, 30(2):444--491, 2005. Google ScholarDigital Library
- S. Harris and A. Seaborne. SPARQL 1.1 query language. W3C Working Draft 12 May 2011, http://www.w3.org/TR/2011/WD-sparql11-query-20110512/.Google Scholar
- O. Hartig, C. Bizer, and J. C. Freytag. Executing SPARQL queries over the Web of Linked Data. In ISWC, pages 293--309, 2009. Google ScholarDigital Library
- M. Marx. Conditional XPath. TODS, 30(4):929--959, 2005. Google ScholarDigital Library
- A. O. Mendelzon and P. T. Wood. Finding regular simple paths in graph databases. SIAM J. Comput., 24(6):1235--1258, 1995. Google ScholarDigital Library
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics of SPARQL. Technical Report, U. de Chile TR/DCC-2006--17, October 2006.Google Scholar
- J. Pérez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL. TODS, 34(3), 2009. Google ScholarDigital Library
- J. Pérez, M. Arenas, and C. Gutierrez. nSPARQL: A navigational language for RDF. JWS, 8(4):255--270, 2010. Google ScholarDigital Library
- E. Prud'hommeaux and A. Seaborne. SPARQL query language for RDF. W3C Recommendation 15 January 2008, http://www.w3.org/TR/rdf-sparql-query/.Google Scholar
- A. L. Selman. A taxonomy of complexity classes of functions. J. Comput. Syst. Sci., 48(2):357--381, 1994. Google ScholarDigital Library
- L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189--201, 1979.Google ScholarCross Ref
- M. Y. Vardi. The complexity of relational query languages (extended abstract). In STOC, pages 137--146, 1982. Google ScholarDigital Library
- K. W. Wagner. More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci., 51:53--80, 1987. Google ScholarDigital Library
- ARQ. http://sourceforge.net/projects/jena/files/ARQ/.Google Scholar
- KGRAM. http://www-sop.inria.fr/edelweiss/software/corese/.Google Scholar
- RDF::Query. http://search.cpan.org/gwilliams/RDF-Query/.Google Scholar
- Sesame. http://sourceforge.net/projects/sesame/.Google Scholar
- Psparql. http://exmo.inrialpes.fr/software/psparql/.Google Scholar
- Gleen. http://sig.biostr.washington.edu/projects/ontviews/gleen/.Google Scholar
- Semantic Web Client Library. http://www4.wiwiss.fu-berlin.de/bizer/ng4j/semwebclient/.Google Scholar
Index Terms
- Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard
Recommendations
Query Planning for Evaluating SPARQL Property Paths
SIGMOD '16: Proceedings of the 2016 International Conference on Management of DataThe extension of SPARQL in version 1.1 with property paths offers a type of regular path query for RDF graph databases. Such queries are difficult to optimize and evaluate efficiently, however. We have embarked on a project, Waveguide, to build a cost-...
SPARQL with property paths on the Web
ESWC 2015 Best PapersLinked Data on the Web represents an immense source of knowledge suitable to be automatically processed and queried. In this respect, there are different approaches for Linked Data querying that differ on the degree of centralization adopted. On one hand,...
Federating queries in SPARQL 1.1: Syntax, semantics and evaluation
Given the sustained growth that we are experiencing in the number of SPARQL endpoints available, the need to be able to send federated SPARQL queries across these has also grown. To address this use case, the W3C SPARQL working group is defining a ...
Comments