publication . Article . 2003

Linearisability on datalog programs

Name: Linearisability on datalog programs
Keywords: Datalog programs, Program transformation, Program optimisation, Linearisability, Deductive databases, Database queries, Theoretical Computer Science, Computer Science(all), General Computer Science

Manolis Gergatsoulis; Francesca Toni; Foto N. Afrati;

Open Access English

Published: 01 Nov 2003 Journal: Theoretical Computer Science, issue 1-3, pages 199-226 (issn: 03043975,

Publisher: Published by Elsevier B.V.

Summary

Abstract

AbstractLinear 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 techniqu...

doi: 10.1016/s0304-3975(02)00730-2

Subjects

ACM Computing Classification System: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESInformationSystems_DATABASEMANAGEMENTTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS

free text keywords: Datalog programs, Program transformation, Program optimisation, Linearisability, Deductive databases, Database queries, Theoretical Computer Science, Computer Science(all), General Computer Science, Syntax, Linearizability, Piecewise linear function, Linearization, Datalog, computer.programming_language, computer, Program optimization, Computer science, Programming language, computer.software_genre, Deductive database

Related Organizations