Size Bound–Adorned Datalog Journal: PACMMOD Volume: 4 2 (PODS) 97 5 DOI: 10.1145/3801893 CCS: Theory of computation Database query processing and optimization (theory)
Christian Fattebert, Zhekai Jiang, Christoph Koch, Reinhard Pichler, Qichen Wang · 2026
Read Size Bound–Adorned Datalog Journal: PACMMOD Volume: 4 2 (PODS) 97 5 DOI: 10.1145/3801893 CCS: Theory of computation Database query processing and optimization (theory) by Christian Fattebert, Zhekai Jiang, Christoph Koch, Reinhard Pichler, Qichen Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15425.txt.
Description
Fattebert and co-authors introduce EDB-bounded datalog, a way to bound the size of intermediate results in recursive queries. Given any datalog program, their algorithm rewrites it so each rule carries a conjunctive query that over-covers its output. From those adornments they define a width, based on edge-cover measures. Width yields worst-case size bounds for every derived predicate, polynomial in the input size. The same bounds give output-sensitive complexity limits for the whole program. The approach also yields a semi-decision test for datalog boundedness.
Catalog record
| CREATOR | Christian Fattebert, Zhekai Jiang, Christoph Koch, Reinhard Pichler, Qichen Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 141333 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.15425