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

CREATORChristian Fattebert, Zhekai Jiang, Christoph Koch, Reinhard Pichler, Qichen Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE141333
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.15425

Browse the full library · About the Tower of Babel