Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 1,134

The DOI matches its Crossref record.

Semantics and complexity of SPARQL

Open access
Pérez, Jorge, Arenas, Marcelo, Gutierrez, Claudio·2009·ACM Transactions on Database Systems
DOI 10.1145/1567274.1567278
Open this paper in CoChat — free account

Abstract

SPARQL is the standard language for querying RDF data. In this article, we address systematically the formal study of the database aspects of SPARQL, concentrating in its graph pattern matching facility. We provide a compositional semantics for the core part of SPARQL, and study the complexity of the evaluation of several fragments of the language. Among other complexity results, we show that the evaluation of general SPARQL patterns is PSPACE-complete. We identify a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently. This restriction gives rise to the class of well-designed patterns. We show that the evaluation problem is coNP-complete for well-designed patterns. Moreover, we provide several rewriting rules for well-designed patterns whose application may have a considerable impact in the cost of evaluating SPARQL queries.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/1567274.1567278

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 27

  1. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.
  2. 10.1016/0304-3975(51)90007-2 · DOI · Paper page
  3. 10.1007/978-3-540-88564-1_8 · doi:10.1007/978-3-540-88564-1_8
  4. Arenas , M. , Gutierrez , C. , Parsia , B. , Pérez , J. , Polleres , A. , and Seaborne , A . 2007. SPARQL—Where are we? Current state, theory and practice. Full day tutorial , European Semantic Web Conference. Arenas, M., Gutierrez, C., Parsia, B., Pérez, J., Polleres, A., and Seaborne, A. 2007. SPARQL—Where are we? Current state, theory and practice. Full day tutorial, European Semantic Web Conference.
  5. 10.1145/2402.322389 · DOI · Paper page
  6. 10.1145/223784.223847 · doi:10.1145/223784.223847
  7. 10.1145/800105.803397 · DOI · Paper page
  8. Chen , L. , Gupta , A. , and Kurul , E . 2005. A semantic-aware RDF query algebra . In Proceedings of the International Conference on Management of Data (COMAD). Chen, L., Gupta, A., and Kurul, E. 2005. A semantic-aware RDF query algebra. In Proceedings of the International Conference on Management of Data (COMAD).
  9. de Bruijn , J. , Franconi , E. , and Tessaris , S . 2005. Logical reconstruction of normative RDF . In Proceedings of the OWL—Experiences and Directions Workshop (OWLED). de Bruijn, J., Franconi, E., and Tessaris, S. 2005. Logical reconstruction of normative RDF. In Proceedings of the OWL—Experiences and Directions Workshop (OWLED).
  10. Durst M. and Suignard M. 2005. Rfc 3987 internationalized resource identifiers (IRIS). http://www.ietf.org/rfc/rfc3987.txt. Durst M. and Suignard M. 2005. Rfc 3987 internationalized resource identifiers (IRIS). http://www.ietf.org/rfc/rfc3987.txt. · DOI
  11. 10.1023/B:WWWJ.0000015866.43076.06 · DOI
  12. Furche T. Linse B. Bry F. Plexousakis D. and Gottlob G. 2006. RDF querying: Language constructs and evaluation methods compared. In Reasoning Web 1--52. Furche T. Linse B. Bry F. Plexousakis D. and Gottlob G. 2006. RDF querying: Language constructs and evaluation methods compared. In Reasoning Web 1--52. · DOI
  13. 10.1145/244810.244812 · doi:10.1145/244810.244812
  14. 10.1145/382780.382783 · doi:10.1145/382780.382783
  15. 10.1145/1055558.1055573 · DOI · Paper page
  16. Haase , P. , Broekstra , J. , Eberhart , A. , and Volz , R . 2004. A comparison of RDF query languages . In Proceedings of the International Semantic Web Conference (ISWC), 502--517 . Haase, P., Broekstra, J., Eberhart, A., and Volz, R. 2004. A comparison of RDF query languages. In Proceedings of the International Semantic Web Conference (ISWC), 502--517.
  17. 10.5555/2113364.2113396 · doi:10.5555/2113364.2113396
  18. 10.1145/1634.1886 · DOI · Paper page
  19. 10.1145/511446.511524 · DOI · Paper page
  20. 10.1007/11926078_3 · DOI · Paper page
  21. 10.1145/1242572.1242679 · doi:10.1145/1242572.1242679
  22. 10.1007/978-3-540-31839-2_8 · doi:10.1007/978-3-540-31839-2_8
  23. Schmidt M. Meier M. and Lausen G. 2008. Foundations of SPARQL query optimization. http://arxiv.org/abs/0812.3788. Schmidt M. Meier M. and Lausen G. 2008. Foundations of SPARQL query optimization. http://arxiv.org/abs/0812.3788. · arXiv
  24. 10.1007/11574620_44 · doi:10.1007/11574620_44
  25. 10.1145/800070.802186 · DOI · Paper page
  26. Yannakakis , M. 1981 . Algorithms for acyclic database schemes . In Proceedings of the International Conference on Very Large Data Bases (VLDB), 82--94 . Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the International Conference on Very Large Data Bases (VLDB), 82--94.
  27. 10.1016/0022-0000(84)90080-1 · DOI · Paper page

Cited by

See all 1,134

Metadata

Authors
Pérez, J., Arenas, M., & Gutierrez, C.
Venue
ACM Transactions on Database Systems
Publisher
Association for Computing Machinery (ACM)
Published
2009-08
Volume
34
Issue
3
Pages
1-45
ISSN
  • 0362-5915 (ISSN-L)
  • 1557-4644
DOI
10.1145/1567274.1567278
OpenAlex
W2131785201
Cited by
1,134
References
0
FWCI
67.95
Type
journal article
Language
en
Open access
green
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Funders
Fondo Nacional de Desarrollo Científico y Tecnológico (1.07E+20)

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Semantics and complexity of SPARQL. https://app.cochat.ai/papers/10.1145/1567274.1567278
The paper
Pérez, J., Arenas, M., & Gutierrez, C. (2009). Semantics and complexity of SPARQL. ACM Transactions on Database Systems. https://doi.org/10.1145/1567274.1567278

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.