TY - GEN

T1 - Total and partial well-founded datalog coincide

AU - Flum, Jörg

AU - Kubierschky, Max

AU - Ludäscher, Bertram

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84948950133&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84948950133&partnerID=8YFLogxK

U2 - 10.1007/3-540-62222-5_40

DO - 10.1007/3-540-62222-5_40

M3 - Conference contribution

AN - SCOPUS:84948950133

SN - 9783540622222

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 113

EP - 124

BT - Database Theory - ICDT 1997 - 6th International Conference, Proceedings

A2 - Afrati, Foto

A2 - Kolaitis, Phokion

PB - Springer-Verlag Berlin Heidelberg

T2 - 6th International Conference on Database Theory, ICDT 1997

Y2 - 8 January 1997 through 10 January 1997

ER -