Abstract
The original SPARQL proposal was often criticized for its inability to navigate through the structure of RDF documents. For this reason property paths were introduced in SPARQL 1.1, but up to date there are no theoretical studies examining how their addition to the language affects main computational tasks such as query evaluation, query containment, and query subsumption. In this paper we tackle all of these problems and show that although the addition of property paths has no impact on query evaluation, they do make the containment and subsumption problems substantially more difficult.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alkhateeb, F.: Querying RDF(S) with regular expressions. Ph.D. thesis, Université Joseph Fourier, Grenoble (2008)
Alkhateeb, F., Baget, J.F., Euzenat, J.: Extending SPARQL with regular expression patterns (for querying RDF). J. Web Sem. 7(2), 57–73 (2009)
Arenas, M., Conca, S., Pérez, J.: Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard. In: WWW 2012, pp. 629–638 (2012)
Barceló Baeza, P.: Querying graph databases. In: PODS 2013, pp. 175–188 (2013)
Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Containment of conjunctive regular path queries with inverse. In: KR 2000, pp. 176–185 (2000)
Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Reasoning on regular path queries. ACM SIGMOD Record 32(4), 83–92 (2003)
Consens, M., Mendelzon, A.: GraphLog: a visual formalism for real life recursion. In: PODS 1990, pp. 404–416 (1990)
Chekol, M.W.: Static Analysis of Semantic Web Queries. Ph.D. thesis, Université de Grenoble (2012)
Chekol, M.W., Euzenat, J., Genevès, P., Layaïda, N.: SPARQL Query Containment under RDFS Entailment Regime. In: IJCAR 2012 (2012)
SPARQL 1.1 Query Language. http://www.w3.org/TR/sparql11-query
Kostylev, E.V., Reutter, J.L., Vrgoč, D.: Containment of Data Graph Queries. In: ICDT 2014, pp. 131–142 (2014)
Letelier, A., Pérez, J., Pichler, R., Skritek, S.: Static analysis and optimization of semantic web queries. ACM TODS 38(4) (2013)
Libkin, L., Reutter, J.L., Vrgoč, D.: Trial for RDF: adapting graph query languages for RDF data. In: PODS 2013, pp. 201–212 (2013)
Losemann, K., Martens, W.: The Complexity of Regular Expressions and Property Paths in SPARQL. ACM TODS 38(4) (2013)
Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM TOCL 5(3), 403–435 (2004)
Pérez, J., Arenas, M., Gutierrez, C.: Semantics and Complexity of SPARQL. In: ISWC 2006, pp. 30–43 (2006)
Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM TODS 34(3) (2009)
Pérez, J., Arenas, M., Gutierrez, C.: nSPARQL: A navigational language for RDF. J. Web Sem. 8(4), 255–270 (2010)
Picalausa, F., Vansummeren, S.: What are real SPARQL queries like? In: SWIM 2011 (2011)
Pichler, R., Skritek, S.: Containment and equivalence of well-designed SPARQL. In: PODS 2014, pp. 39–50 (2014)
Schmidt, M., Meier, M., Lausen, G.: Foundations of SPARQL query optimization. In: ICDT 2010, pp. 4–33 (2010)
Prud’hommeaux, E., Seaborne, A.: SPARQL query language for RDF. W3C Recommendation (January 15, 2008). http://www.w3.org/TR/rdf-sparql-query/
Vardi, M.Y.: The Complexity of Relational Query Languages. In: STOC (1982)
Zhang, X., Van den Bussche, J.: On the Power of SPARQL in Expressing Navigational Queries. The Computer Journal (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kostylev, E.V., Reutter, J.L., Romero, M., Vrgoč, D. (2015). SPARQL with Property Paths. In: Arenas, M., et al. The Semantic Web - ISWC 2015. ISWC 2015. Lecture Notes in Computer Science(), vol 9366. Springer, Cham. https://doi.org/10.1007/978-3-319-25007-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-25007-6_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25006-9
Online ISBN: 978-3-319-25007-6
eBook Packages: Computer ScienceComputer Science (R0)