Total and partial well-founded datalog coincide

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

doi:10.1007/3-540-62222-5_40

Total and partial well-founded datalog coincide

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that the expressive power of well-founded Datalog does not decrease when restricted to total programs (it is known to decrease from Π ₁ ¹ to Δ ₁ ¹ 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 language	English (US)
Title of host publication	Database Theory - ICDT 1997 - 6th International Conference, Proceedings
Editors	Foto Afrati, Phokion Kolaitis
Publisher	Springer
Pages	113-124
Number of pages	12
ISBN (Print)	9783540622222
DOIs	https://doi.org/10.1007/3-540-62222-5_40
State	Published - 1997
Externally published	Yes
Event	6th International Conference on Database Theory, ICDT 1997 - Delphi, Greece Duration: Jan 8 1997 → Jan 10 1997

Publication series

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

Other

Other	6th International Conference on Database Theory, ICDT 1997
Country/Territory	Greece
City	Delphi
Period	1/8/97 → 1/10/97

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/3-540-62222-5_40

Library availability

Discover UIUC Full Text

Cite this

Flum, J., Kubierschky, M., & Ludäscher, B. (1997). Total and partial well-founded datalog coincide. In F. Afrati, & P. Kolaitis (Eds.), Database Theory - ICDT 1997 - 6th International Conference, Proceedings (pp. 113-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1186). Springer. https://doi.org/10.1007/3-540-62222-5_40

Total and partial well-founded datalog coincide. / Flum, Jörg; Kubierschky, Max; Ludäscher, Bertram.
Database Theory - ICDT 1997 - 6th International Conference, Proceedings. ed. / Foto Afrati; Phokion Kolaitis. Springer, 1997. p. 113-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1186).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Flum, J, Kubierschky, M & Ludäscher, B 1997, Total and partial well-founded datalog coincide. in F Afrati & P Kolaitis (eds), Database Theory - ICDT 1997 - 6th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1186, Springer, pp. 113-124, 6th International Conference on Database Theory, ICDT 1997, Delphi, Greece, 1/8/97. https://doi.org/10.1007/3-540-62222-5_40

Flum J, Kubierschky M, Ludäscher B. Total and partial well-founded datalog coincide. In Afrati F, Kolaitis P, editors, Database Theory - ICDT 1997 - 6th International Conference, Proceedings. Springer. 1997. p. 113-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-62222-5_40

Flum, Jörg ; Kubierschky, Max ; Ludäscher, Bertram. / Total and partial well-founded datalog coincide. Database Theory - ICDT 1997 - 6th International Conference, Proceedings. editor / Foto Afrati ; Phokion Kolaitis. Springer, 1997. pp. 113-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dc4777b4a6c044e3851ba5b23d13855f,

title = "Total and partial well-founded datalog coincide",

abstract = "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.",

author = "J{\"o}rg Flum and Max Kubierschky and Bertram Lud{\"a}scher",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 6th International Conference on Database Theory, ICDT 1997 ; Conference date: 08-01-1997 Through 10-01-1997",

year = "1997",

doi = "10.1007/3-540-62222-5_40",

language = "English (US)",

isbn = "9783540622222",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "113--124",

editor = "Foto Afrati and Phokion Kolaitis",

booktitle = "Database Theory - ICDT 1997 - 6th International Conference, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Total and partial well-founded datalog coincide

AU - Flum, Jörg

AU - Kubierschky, Max

AU - Ludäscher, Bertram

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

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

Y2 - 8 January 1997 through 10 January 1997

ER -

Total and partial well-founded datalog coincide

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this