publication . Article . 2003

Linearisability on datalog programs

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, Copyright policy)
  • Publisher: Published by Elsevier B.V.
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...
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
Any information missing or wrong?Report an Issue