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)
Incoming Non-self Citations Over Time
Authors
- 1. Marco Calautti
- 2. Georg Gottlob
- 3. Andreas Pieris
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,045 | Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study | 2023 | VLDB | 4.3997447e-05 |
| 10,912 | Chase Termination Beyond Polynomial Time | 2024 | PODS | 4.1905499e-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 |
|---|---|---|---|---|
| 695 | The Chase Revisited | 2008 | PODS | 0.00018013323 |
| 1,737 | Generalized Schema-Mappings: From Termination To Tractability | 2009 | PODS | 0.00010711961 |
| 3,007 | Benchmarking the Chase | 2017 | PODS | 7.7243073e-05 |
| 3,913 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.6311557e-05 |
| 11,557 | All-Instances Restricted Chase Termination | 2020 | PODS | 4.1905499e-05 |
| 11,560 | The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs | 2020 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,388 | Rewriting the Infinite Chase | 2022 | VLDB | 4.1905499e-05 |
| 7,508 | Optimizing the Chase: Scalable Data Integration under Constraints | 2014 | VLDB | 4.7135369e-05 |
| 695 | The Chase Revisited | 2008 | PODS | 0.00018013323 |
| 6,459 | Exploiting Equality Generating Dependencies in Checking Chase Termination | 2016 | VLDB | 5.048352e-05 |
| 10,368 | Restricted Chase Termination: You Want More than Fairness | 2025 | PODS | 4.1905499e-05 |
| 11,557 | All-Instances Restricted Chase Termination | 2020 | PODS | 4.1905499e-05 |
| 3,494 | On Chase Termination Beyond Stratification | 2009 | VLDB | 7.0401e-05 |
| 9,045 | Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study | 2023 | VLDB | 4.3997447e-05 |
| 10,912 | Chase Termination Beyond Polynomial Time | 2024 | PODS | 4.1905499e-05 |
| 3,913 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.6311557e-05 |