DBScholar

Back to papers

Non-Uniformly Terminating Chase: Size and Complexity

Summary: For guarded TGDs under the semi-oblivious chase, non-uniform termination is decidable in polynomial time in the database and any finite chase result has size linear in the database. Shows simplification and linearization from ontological query answering transfer soundly to chase-termination analysis, yielding these complexity and size bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h3024702790c4184f
Venue
PODS
Year
2022
Pagerank
5.1868213e-05
Overall Rank
9,376 | 36.97%
DOI
10.1145/3517804.3524146

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{calautti_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{Non-Uniformly Terminating Chase: Size and Complexity}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3524146},
        doi = {10.1145/3517804.3524146},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Calautti, Marco and Gottlob, Georg and Pieris, Andreas},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
9,375 Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study 2023 VLDB 5.1868213e-05
11,477 Chase Termination Beyond Polynomial Time 2024 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
539 The Chase Revisited 2008 PODS 0.00016735847
1,575 Generalized Schema-Mappings: From Termination To Tractability 2009 PODS 0.00010194712
2,674 Benchmarking the Chase 2017 PODS 8.1480823e-05
4,445 Chase Termination for Guarded Existential Rules 2015 PODS 6.5976367e-05
7,991 When Can We Answer Queries Using Result-Bounded Data Interfaces? 2018 PODS 5.4115836e-05
12,053 All-Instances Restricted Chase Termination 2020 PODS 4.9793485e-05
12,056 The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs 2020 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers