Hard Problems for Simple Logic Programs.

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

@inproceedings{DBLP:conf/sigmod/Saraiya90,
  author    = {Yatin P. Saraiya},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {Hard Problems for Simple Logic Programs},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {64-73},
  ee        = {http://doi.acm.org/10.1145/93597.93622, db/conf/sigmod/Saraiya90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A number of optimizations have been proposed for Datalog programs involving a single intensional predicate ("single-IDB programs"). Examples include the detection of commutativity and separability ([Naug88],[RSUV89], [Ioan89a]) in linear logic programs, and the detection of ZYT-linearizability ([ZYT88], [RSUV89], [Sara89], [Sara9O]) in nonlinear programs. We show that the natural generalizations of the commutativity and ZYT-linearizability problems (respectively, the sequencability and base-case linearizability problems) are undecidable. Our constructions involve the simulation of context-free grammars using single-IDB programs that have a bounded number of initialisation rules. The constructions may be used to show that containment (or equivalence) is undecidable for such programs, even if the programs are linear, or if each program contains a single recursive rule. These results tighten those of [Shmu87] and [Abit89].

Copyright © 1990 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

BibTeX

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 BibTeX , SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library

References

[Abit89]: Serge Abiteboul: Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule. Inf. Process. Lett. 32(6): 281-287(1989) BibTeX
[BMSU86]: François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[BR87]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[CM77]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[HU79]: John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[Ioan89a]: Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163 BibTeX
[Ioan89b]: Yannis E. Ioannidis, Eugene Wong: Towards an Algebraic Theory of Recursion. J. ACM 38(2): 329-381(1991) BibTeX
[Naug88]: Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX
[RSUB89]: Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181 BibTeX
[SY81]: Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
[Sagi87]: Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[Sara89]: Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189 BibTeX
[Sara90]: Yatin P. Saraiya: Polynomial-Time Program Transformations in Deductive Databases. PODS 1990: 132-144 BibTeX
[Shmu87]: Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Ullm89]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[ZYT88]: 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

Referenced by

Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80
Tomás Feder, Yatin P. Saraiya: Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations. ICDT 1992: 297-311

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]