Affiliations: Computer Science Division, Department of Electrical
and Computer Engineering, National Technical University of Athens, 157 73
Zografou, Athens, Greece. E-mail: ppotik@cs.ntua.gr | Department of Informatics & Telecommunications,
University of Athens, Panepistimiopolis, 157 84 Athens, Greece. E-mail:
prondo@di.uoa.gr | Department of Archive and Library Sciences, Ionian
University, Palea Anaktora, Plateia Eleftherias, 49100 Corfu, Greece. E-mail:
manolis@ionio.gr
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 Datalog_{nS}
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
