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
No non-self incoming citations found for this paper in this database.
Authors
- 1. Pablo Barceló
- 2. Georg Gottlob
- 3. Andreas Pieris
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,328 | Hypertree Decompositions: Questions and Answers | 2016 | PODS | 0.00012565612 |
| 11,553 | All-Instances Restricted Chase Termination | 2020 | PODS | 4.1945683e-05 |
| 11,556 | The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs | 2020 | PODS | 4.1945683e-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 |
|---|---|---|---|---|
| 38 | Testing Implications Of Data Dependencies | 1979 | SIGMOD | 0.00075110004 |
| 144 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00041462501 |
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 4,058 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 6.4866036e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,275 | Determinacy of Real Conjunctive Queries. The Boolean Case | 2022 | PODS | 5.1319495e-05 |
| 11,762 | Stable Model Semantics for Tuple-Generating Dependencies Revisited | 2017 | PODS | 4.1945683e-05 |
| 1,522 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.0001153051 |
| 3,681 | Queries with Incomplete Answers over Semistructured Data | 1999 | PODS | 6.8492288e-05 |
| 1,490 | On the Decidability of Query Containment under Constraints | 1998 | PODS | 0.00011699154 |
| 10,002 | Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories | 2026 | PODS | 4.1945683e-05 |
| 2,727 | Semantic Query Optimization in the Presence of Types | 2010 | PODS | 8.2216778e-05 |
| 9,791 | Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. | 2024 | PODS | 4.2818172e-05 |
| 2,877 | Semantic Query Optimization in Datalog Programs (Extended Abstract) | 1995 | PODS | 7.9715251e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |