Size Bound-Adorned Datalog
This work addresses efficiency and predictability issues in datalog query evaluation for database and logic programming researchers, offering incremental improvements in bounding techniques.
The paper tackles the problem of deriving upper bounds on intermediate result sizes and asymptotic complexity for recursive queries in datalog, introducing EDB-bounded datalog with an algorithm that constructs adorned programs and obtains polynomial worst-case size bounds and fixed-parameter tractable complexity bounds.
We introduce EDB-bounded datalog, a framework for deriving upper bounds on intermediate result sizes and the asymptotic complexity of recursive queries in datalog. We present an algorithm that, given an arbitrary datalog program, constructs an EDB-bounded datalog program in which every rule is adorned with a (non-recursive) conjunctive query that subsumes the result of the rule, thus acting as an upper bound. From such adornments, we define a notion of width based on (integral or fractional) edge-cover widths. Through the adornments and the width measure, we obtain, for every IDB predicate, worst-case upper bounds on their sizes, which are polynomial in the input data size, given a fixed program structure. Furthermore, with these size bounds, we also derive fixed-parameter tractable, output-sensitive asymptotic complexity bounds for evaluating the entire program. Additionally, by adapting our framework, we obtain a semi-decision procedure for datalog boundedness that efficiently rewrites most practical bounded programs into non-recursive equivalent programs.