Total and partial well-founded datalog coincide

Jörg Flum, Max Kubierschky, Bertram Ludäscher

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We show that the expressive power of well-founded Datalog does not decrease when restricted to total programs (it is known to decrease from Π 1 1 to Δ 1 1 on infinite Herbrand structures) thereby affirmatively answering an open question posed by Abiteboul, Hull, and Vianu [AHV95]. In particular, we show that for every well-founded Datalog program there exists an equivalent total program whose only recursive rule is of the form (equation presented) where move is definable by a quantifier-free first-order formula. This yields a nice new normal form for well-founded Datalog and implies that it is sufficient to consider draw-free games in order to evaluate arbitrary Datalog programs under the well-founded semantics.

Original languageEnglish (US)
Title of host publicationDatabase Theory - ICDT 1997 - 6th International Conference, Proceedings
EditorsFoto Afrati, Phokion Kolaitis
Number of pages12
ISBN (Print)9783540622222
StatePublished - 1997
Externally publishedYes
Event6th International Conference on Database Theory, ICDT 1997 - Delphi, Greece
Duration: Jan 8 1997Jan 10 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Conference on Database Theory, ICDT 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Total and partial well-founded datalog coincide'. Together they form a unique fingerprint.

Cite this