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)

Paper ID: 1628
Venue: PODS
Year: 2014
Pagerank: 5.093636e-05
Overall Rank: 12,165 | 16.54%
DOI: 10.1145/2594538.2594553

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,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.3921264e-05

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
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
747	Querying Graph Databases	2013	PODS	0.00014400452
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
7,028	Semantic Acyclicity on Graph Databases	2013	PODS	5.7228058e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,753	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS
2	6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
3	9,430	A Theory of Regular Queries	2016	PODS
4	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
5	7,205	Containment of Graph Queries Modulo Schema	2024	PODS
6	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
7	3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
8	7,028	Semantic Acyclicity on Graph Databases	2013	PODS
9	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	1,630	On the Decidability of Query Containment under Constraints	1998	PODS