On the Equivalence of Recursive and Nonrecursive Datalog Programs.

@inproceedings{DBLP:conf/pods/ChaudhuriV92,
  author    = {Surajit Chaudhuri and
               Moshe Y. Vardi},
  title     = {On the Equivalence of Recursive and Nonrecursive Datalog Programs},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {55-66},
  ee        = {http://doi.acm.org/10.1145/137097.137109, db/conf/pods/ChaudhuriV92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Journal Version

References

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120

[AV89]

Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79

[BR86]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52

[Ch81]

Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62

[CH80]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980)

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982)

[CH85]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985)

[CKS81]

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981)

[CLM81]

Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354

[CGKV88]

Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490

[CK86]

Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293

[Cou90]

Bruno Courcelle: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput. 85(1): 12-75(1990)

[Cou91]

Bruno Courcelle: Recursive Queries and Context-free Graph Grammars. Theor. Comput. Sci. 78(1): 217-244(1991)

[EJ88]

E. Allen Emerson, Charanjit S. Jutla: The Complexity of Tree Automata and Logics of Programs (Extended Abstract). FOCS 1988: 328-337

[GM78]

...

[GMSV87]

Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115

[HKMV91]

Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12

[HKMV92]

Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190(1995)

[Im86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986)

[K90]

...

[KA89]

Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989)

[MS72]

...

[MP91]

Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141

[Mo74]

...

[Na89a]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989)

[Na89b]

Jeffrey F. Naughton: Minimizing function-free recursive inference rules. J. ACM 36(1): 69-91(1989)

[NRSU89]

Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242

[Ra69]

...

[RSUV89]

Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181

[Sa88b]

...

[Se90]

Helmut Seidl: Deciding Equivalence of Finite Tree Automata. SIAM J. Comput. 19(3): 424-437(1990)

[Shm87]

Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249

[TW68]

James W. Thatcher, Jesse B. Wright: Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic. Mathematical Systems Theory 2(1): 57-81(1968)

[Ul89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents

[UV88]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988)

[Va82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146

[Va88]

Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351

[Va92]

...

[VW86]

Moshe Y. Vardi, Pierre Wolper: Automata-Theoretic Techniques for Modal Logics of Programs. J. Comput. Syst. Sci. 32(2): 183-221(1986)

[Zl76]

...