Semantic Acyclicity Under Constraints
Summary: Analyzes semantic acyclicity of conjunctive queries under dependencies, proving CQ‑containment decidability is not sufficient and that semantic acyclicity is undecidable for full tgds. Shows decidability (matching CQ‑containment complexity) for guarded, non‑recursive and sticky tgds; NP‑complete for egds with unary/binary keys; and gives tractable evaluation under guarded tgds and functional dependencies. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Pablo Barceló (University of Chile)
- 2. Georg Gottlob (University of Oxford)
- 3. Andreas Pieris (Vienna University of Technology)
BibTeX Citation
@inproceedings{barcelo_pods16,
address = {New York, NY, USA},
series = {{PODS} '16},
title = {{Semantic Acyclicity Under Constraints}},
url = {https://dl.acm.org/doi/10.1145/2902251.2902302},
doi = {10.1145/2902251.2902302},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Barceló, Pablo and Gottlob, Georg and Pieris, Andreas},
year = {2016}
}Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 814 | Hypertree Decompositions: Questions and Answers | 2016 | PODS | 0.00013841737 |
| 11,750 | All-Instances Restricted Chase Termination | 2020 | PODS | 5.093636e-05 |
| 11,753 | The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs | 2020 | PODS | 5.093636e-05 |
| 11,901 | How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)? | 2018 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 40 | Testing Implications Of Data Dependencies | 1979 | SIGMOD | 0.00046918506 |
| 134 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00030343737 |
| 414 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00018893507 |
| 3,463 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 7.3921264e-05 |
| 7,028 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 5.7228058e-05 |
| 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 5.3335287e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,542 | Determinacy of Real Conjunctive Queries. The Boolean Case | 2022 | PODS |
| 2 | 11,968 | Stable Model Semantics for Tuple-Generating Dependencies Revisited | 2017 | PODS |
| 3 | 1,269 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS |
| 4 | 4,495 | Queries with Incomplete Answers over Semistructured Data | 1999 | PODS |
| 5 | 1,630 | On the Decidability of Query Containment under Constraints | 1998 | PODS |
| 6 | 10,175 | Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories | 2026 | PODS |
| 7 | 4,369 | Semantic Query Optimization in the Presence of Types | 2010 | PODS |
| 8 | 9,946 | Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. | 2024 | PODS |
| 9 | 2,883 | Semantic Query Optimization in Datalog Programs (Extended Abstract) | 1995 | PODS |
| 10 | 7,028 | Semantic Acyclicity on Graph Databases | 2013 | PODS |