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
1872
Venue
PODS
Year
2022
Pagerank
5.3058708e-05
Overall Rank
9,196 | 36.91%
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,195 Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study 2023 VLDB 5.3058708e-05
11,129 Chase Termination Beyond Polynomial Time 2024 PODS 5.093636e-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
525 The Chase Revisited 2008 PODS 0.00017118255
1,541 Generalized Schema-Mappings: From Termination To Tractability 2009 PODS 0.00010427058
2,634 Benchmarking the Chase 2017 PODS 8.3210907e-05
4,353 Chase Termination for Guarded Existential Rules 2015 PODS 6.7490677e-05
7,830 When Can We Answer Queries Using Result-Bounded Data Interfaces? 2018 PODS 5.5357919e-05
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
Previous Page 1 / 1 Next

Semantically Similar Papers