Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations.

@inproceedings{DBLP:conf/icdt/FederS92,
  author    = {Tom{\'a}s Feder and
               Yatin P. Saraiya},
  editor    = {Joachim Biskup and
               Richard Hull},
  title     = {Decidability and Undecidability of Equivalence for Linear Datalog
               with Applications to Normal-Form Optimizations},
  booktitle = {Database Theory - ICDT'92, 4th International Conference, Berlin,
               Germany, October 14-16, 1992, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {646},
  year      = {1992},
  isbn      = {3-540-56039-4},
  pages     = {297-311},
  ee        = {db/conf/icdt/FederS92.html},
  crossref  = {DBLP:conf/icdt/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

Serge Abiteboul: Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule. Inf. Process. Lett. 32(6): 281-287(1989) BibTeX

[2]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[3]

...

[4]

...

[5]

John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX

[6]

...

[7]

Yannis E. Ioannidis, Eugene Wong: Towards an Algebraic Theory of Recursion. J. ACM 38(2): 329-381(1991) BibTeX

[8]

...

[9]

H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX

[10]

...

[11]

Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX

[12]

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

[13]

Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX

[14]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[15]

Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189 BibTeX

[16]

Yatin P. Saraiya: Polynomial-Time Program Transformations in Deductive Databases. PODS 1990: 132-144 BibTeX

[17]

Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73 BibTeX

[18]

...

[19]

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

[20-1]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[20-2]

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

[21]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. FOCS 1986: 438-454 BibTeX

[22]

Weining Zhang, Clement T. Yu, Daniel Troy: Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases. ACM Trans. Database Syst. 15(3): 459-482(1990) BibTeX