A Value-propagating Transformation Technique for Datalog Programs Based on
Non-Deterministic Constructs
Petros Potikas, Panos Rondogiannis, Manolis Gergatsoulis
Abstract: The branching-time transformation is a recent technique for
optimizing Chain Datalog programs. In this paper we propose a significant
extension of the branching-time transformation which we believe opens up a
promising new direction of research in the area of value-propagating Datalog
optimizations. More specifically, the proposed transformation can handle more
general programs that allow multiple consumptive occurrences of variables in the
bodies of clauses. This extension is achieved by using as target language the
temporal logic programming formalism DatalognS enriched with choice
predicates (a non-deterministic construct that was originally introduced in the
area of intensional logic programming). We demonstrate the correctness of the
transformation and propose several optimizations that can be applied to the
target code. Moreover, we define a bottom-up proof procedure that applies to the
target programs and demonstrate that it always terminates (despite the
fact that the Herbrand base of these programs is generally infinite).
Keywords: Logic Programming, Deductive Databases, Program and Query
Transformations, Non-deterministic Constructs.