Computing Publications

Publications Home » Linearisability on Datalog programs

Linearisability on Datalog programs

Foto Afrati, Manolis Gergatsoulis, Francesca Toni

Journal Article
Theoretical Computer Science
Volume 308
Issues 1–3
ISSN 0304-3975

Linear Datalog programs are programs whose clauses have at most one intensional atom in their bodies. We explore syntactic classes of Datalog programs (syntactically non-linear) which turn out to express no more than the queries expressed by linear Datalog programs. In particular, we investigate linearisability of (database queries corresponding to) piecewise linear Datalog programs and chain queries:

a) We prove that piecewise linear Datalog programs can always be transformed into linear Datalog programs, by virtue of a procedure which performs the transformation automatically. The procedure relies upon conventional logic program transformation techniques.

b) We identify a new class of linearisable chain queries, referred to as pseudo-regular, and prove their linearisability constructively, by generating, for any given pseudo-regular chain query, the Datalog program corresponding to it.

PDF of full publication (306 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.