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

Proof-Tree Transformation Theorems and Their Applications.

Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181
@inproceedings{DBLP:conf/pods/RamakrishnanSUV89,
  author    = {Raghu Ramakrishnan and
               Yehoshua Sagiv and
               Jeffrey D. Ullman and
               Moshe Y. Vardi},
  title     = {Proof-Tree Transformation Theorems and Their Applications},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {172-181},
  ee        = {http://doi.acm.org/10.1145/73721.73739, db/conf/pods/RamakrishnanSUV89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

For certain sets of logical rules, one can demonstrate that for every proof tree there is another tree proving the same fact and having a special form. One technique for detecting such opportunities is to reduce the question to one of conjunctive-query containment. A more powerful technique is to test whether one conjunctive query is contained in the infinite union of conjunctive queries formed by expanding a set of recursive rules. We discuss two applications of these techniques. First, we give tests for commutativity of linear rules. When linear rules commute, we can reduce the complexity of "counting" methods for query evaluation from exponential to polynomial; commutativity also implies separability in the sense of Naughton. A second application is the discovery of linear rules that are equivalent to given nonlinear rules.

Copyright © 1989 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 ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[Bancilhon et al., 1986]
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
[Chandra, Lewis, Makowsky, 1981]
Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354 BibTeX
[Chandra, Merlin, 1977]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[Cosmadakis, Kanellakis, 1986]
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX
[Gaifman, Mairson, Sagiv, Vardi, 1987]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX
[Ioannidis, Wong, 1988]
Yannis E. Ioannidis, Eugene Wong: Transforming Nonlinear Recursion into Linear Recursion. Expert Database Conf. 1988: 401-421 BibTeX
[Ioannidis, 1988]
Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. J. Log. Program. 14(3&4): 223-252(1992) BibTeX
[Kanellakis, 1988]
...
[Maher, 1985]
...
[Naughton, 1988]
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX
[Sacc�, Zaniolo, 1986]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX
[Sagiv, 1987]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[Saraiya, 1989]
Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189 BibTeX
[Shmueli, 1987]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Ullman, 1988]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Zhang, Yu, Troy, 1988]
...

Referenced by

  1. Vasilis Vassalos, Yannis Papakonstantinou: Describing and Using Query Capabilities of Heterogeneous Sources. VLDB 1997: 256-265
  2. Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116
  3. Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40
  4. Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144
  5. Irène Guessarian, Jean-Eric Pin: Linearizing Some Recursive Logic Programs. IEEE Trans. Knowl. Data Eng. 7(1): 137-149(1995)
  6. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  7. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
  8. Tomás Feder, Yatin P. Saraiya: Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations. ICDT 1992: 297-311
  9. Laks V. S. Lakshmanan, Héctor J. Hernández: Structural Query Optimization - A uniform Framework for Semantic Query Optimization in Deductive Databases. PODS 1991: 102-114
  10. Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
  11. Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73
  12. Yatin P. Saraiya: Polynomial-Time Program Transformations in Deductive Databases. PODS 1990: 132-144
  13. Thane E. Plambeck: Semigroup Techniques in Recursive Query Optimization. PODS 1990: 145-153
  14. Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163
  15. Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
  16. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:57 2009