Does Query Evaluation Tractability Help Query Containment?
Summary: Restricting target UCQs/UC2RPQs to tractable classes alone does not lower Datalog⊆UCQ/UC2RPQ containment from 2EXPTIME. However, acyclicity plus bounds on shared variables (UCQs) or connecting edges (UC2RPQs) yields EXPTIME decidability, and these bounds are tight. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Pablo Barceló (University of Chile)
- 2. Miguel Romero (University of Chile)
- 3. Moshe Y. Vardi (Rice University)
BibTeX Citation
@inproceedings{barcelo_pods14,
address = {New York, NY, USA},
series = {{PODS} '14},
title = {{Does Query Evaluation Tractability Help Query Containment?}},
url = {https://dl.acm.org/doi/10.1145/2594538.2594553},
doi = {10.1145/2594538.2594553},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Barceló, Pablo and Romero, Miguel and Vardi, Moshe Y.},
year = {2014}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,531 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 7.2274159e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 130 | A Query Language and Optimization Techniques for Unstructured Data | 1996 | SIGMOD | 0.00030320165 |
| 633 | Parallel Evaluation of Recursive Rule Queries | 1986 | PODS | 0.00015380574 |
| 719 | Querying Graph Databases | 2013 | PODS | 0.00014529156 |
| 3,315 | On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs | 1994 | PODS | 7.4376793e-05 |
| 7,140 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 5.6005794e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 12,056 | The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs | 2020 | PODS |
| 2 | 7,064 | On the Decidability of Containment of Recursive Datalog Queries - Preliminary report | 2004 | PODS |
| 3 | 9,611 | A Theory of Regular Queries | 2016 | PODS |
| 4 | 390 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS |
| 5 | 7,347 | Containment of Graph Queries Modulo Schema | 2024 | PODS |
| 6 | 8,053 | Polynomial-time program transformations in deductive databases | 1990 | PODS |
| 7 | 3,870 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS |
| 8 | 7,140 | Semantic Acyclicity on Graph Databases | 2013 | PODS |
| 9 | 6,741 | Inherent Complexity of Recursive Queries (Extended Abstract) | 1999 | PODS |
| 10 | 1,660 | On the Decidability of Query Containment under Constraints | 1998 | PODS |