Containment and Equivalence of Well-Designed SPARQL
Summary: Comprehensive complexity classification of query containment and equivalence for well‑designed SPARQL fragments (AND, OPTIONAL) and extensions with UNION and projection. Maps decidable cases (as low as NP‑complete) versus undecidability, pinpointing the boundary for static analysis. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Reinhard Pichler (Vienna University of Technology)
- 2. Sebastian Skritek (Vienna University of Technology)
BibTeX Citation
@inproceedings{pichler_pods14,
address = {New York, NY, USA},
series = {{PODS} '14},
title = {{Containment and Equivalence of Well-Designed SPARQL}},
url = {https://dl.acm.org/doi/10.1145/2594538.2594542},
doi = {10.1145/2594538.2594542},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Pichler, Reinhard and Skritek, Sebastian},
year = {2014}
}
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,463 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 7.3921264e-05 |
| 8,098 | Designing a Query Language for RDF: Marrying Open and Closed Worlds | 2016 | PODS | 5.4874656e-05 |
| 11,852 | An Efficient Index for RDF Query Containment | 2019 | SIGMOD | 5.093636e-05 |
| 11,895 | The Tractability Frontier of Well-designed SPARQL Queries | 2018 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 134 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00030343737 |
| 2,446 | Querying Semantic Web Data with SPARQL | 2011 | PODS | 8.5728114e-05 |
| 3,556 | Static Analysis and Optimization of Semantic Web Queries | 2012 | PODS | 7.3113256e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,971 | Equivalence of Nested Queries with Mixed Semantics | 2009 | PODS |
| 2 | 9,946 | Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. | 2024 | PODS |
| 3 | 12,492 | Equivalence of SQL Queries In Presence of Embedded Dependencies | 2009 | PODS |
| 4 | 11,787 | SPARQL Rewriting: Towards Desired Results | 2020 | SIGMOD |
| 5 | 3,801 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS |
| 6 | 8,098 | Designing a Query Language for RDF: Marrying Open and Closed Worlds | 2016 | PODS |
| 7 | 1,269 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS |
| 8 | 1,777 | Deciding Containment for Queries with Complex Objects (Extended Abstract) | 1997 | PODS |
| 9 | 11,895 | The Tractability Frontier of Well-designed SPARQL Queries | 2018 | PODS |
| 10 | 3,556 | Static Analysis and Optimization of Semantic Web Queries | 2012 | PODS |