ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Finding Nonrecursive Envelopes for Datalog Predicates.

Surajit Chaudhuri: Finding Nonrecursive Envelopes for Datalog Predicates. PODS 1993: 135-146
@inproceedings{DBLP:conf/pods/Chaudhuri93,
  author    = {Surajit Chaudhuri},
  title     = {Finding Nonrecursive Envelopes for Datalog Predicates},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {135-146},
  ee        = {http://doi.acm.org/10.1145/153850.153862, db/conf/pods/Chaudhuri93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we study the ability of data-independent conjunctive expressions (envelopes) to approximate fixpoint of Datalog predicates. We show that no effective procedure exists for finding envelopes that best approximate the fix-point (tight envelopes). Moreover, the problem of determining existence of tight envelopes is undecidable. The relationship between tight envelopes and the boundedness property is explored. Although the property of having tight envelopes seems weaker than boundedness, we note that a predicate can have a tight (lower) envelope iff it is bounded. On the other hand, there exist Datalog predicates that are not bounded but have tight (upper) envelopes. We relax our requirement for tight envelopes and settle for connected envelopes. An algorithm to determine connected envelopes for Datalog predicates is presented. We mention several applications of envelopes.

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


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 969 KB]

References

[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[C91]
Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CV92]
Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GMSV87]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HKMV91]
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KA89]
Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HR92]
...
[M90]
Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[S90]
Yehoshua Sagiv: Is There Anything Better than Magic? NACLP 1990: 235-254 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SY81]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[S*79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[U89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Va82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Va88]
Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:57 2010 by Michael Ley (ley@uni-trier.de)