The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs
Summary: Pinpoints the tractability frontier: OMQ evaluation under guarded TGDs is FPT iff the UCQ is equivalent to one of bounded treewidth (under standard assumptions). Shows a parallel dichotomy for CQSs (guarded and frontier‑guarded with bounded head size), links OMQ and CQS evaluation, and analyzes the meta-decision problems (bounded arity assumed). (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ó (Pontifical Catholic University of Chile)
- 2. Victor Dalmau (Pompeu Fabra University)
- 3. Cristina Feier (University of Bremen)
- 4. Carsten Lutz (University of Bremen)
- 5. Andreas Pieris (University of Edinburgh)
BibTeX Citation
@inproceedings{barcelo_pods20,
address = {New York, NY, USA},
series = {{PODS} '20},
title = {{The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs}},
url = {https://dl.acm.org/doi/10.1145/3375395.3387653},
doi = {10.1145/3375395.3387653},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Barceló, Pablo and Dalmau, Victor and Feier, Cristina and Lutz, Carsten and Pieris, Andreas},
year = {2020}
}
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,196 | Non-Uniformly Terminating Chase: Size and Complexity | 2022 | PODS | 5.3058708e-05 |
| 9,291 | Efficiently Enumerating Answers to Ontology-Mediated Queries | 2022 | PODS | 5.2910144e-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 |
| 5,347 | Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP | 2013 | PODS | 6.2571376e-05 |
| 9,933 | Semantic Acyclicity Under Constraints | 2016 | PODS | 5.1955087e-05 |
| 11,893 | Containment for Rule-Based Ontology-Mediated Queries | 2018 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS |
| 2 | 3,433 | On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information | 2006 | PODS |
| 3 | 4,393 | Bounded Conjunctive Queries | 2014 | VLDB |
| 4 | 11,630 | Model-theoretic Characterizations of Rule-based Ontologies | 2021 | PODS |
| 5 | 11,893 | Containment for Rule-Based Ontology-Mediated Queries | 2018 | PODS |
| 6 | 9,933 | Semantic Acyclicity Under Constraints | 2016 | PODS |
| 7 | 12,165 | Does Query Evaluation Tractability Help Query Containment? | 2014 | PODS |
| 8 | 7,029 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS |
| 9 | 9,291 | Efficiently Enumerating Answers to Ontology-Mediated Queries | 2022 | PODS |
| 10 | 11,969 | Dichotomies in Ontology-Mediated Querying with the Guarded Fragment | 2017 | PODS |