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 ...

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/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. 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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

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

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
[CM77]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[C91]: Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
[CV92]: Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
[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
[KA89]: Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989)
[HR92]: ...
[M90]: Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378
[S90]: Yehoshua Sagiv: Is There Anything Better than Magic? NACLP 1990: 235-254
[SY81]: Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980)
[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
[U89]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[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