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

Linearizing Nonlinear Recursions in Polynomial Time.

Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
@inproceedings{DBLP:conf/pods/Saraiya89,
  author    = {Yatin P. Saraiya},
  title     = {Linearizing Nonlinear Recursions in Polynomial Time},
  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     = {182-189},
  ee        = {http://doi.acm.org/10.1145/73721.73740, db/conf/pods/Saraiya89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The replacement of nonlinear recursions with equivalent linear recursions is a potentially useful query optimization strategy, since it permits the use of efficient algorithms for the evaluation of linear logic programs. We show that a member of a certain class of bilinear recursions is linearizable in a strong sense if and only if a specific partial proof tree derived from this recursion is contained in a bounded number of partial proof trees generated by the recursion. Further, while each such test of containment between proof trees involves an exponential number of conjunctive-query containment tests, we present syntactic conditions on the recursion that are necessary and sufficient for the containment and verifiable in polynomial time.

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

[1]
...
[2]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[3]
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
[4]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[5]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[6]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX
[7]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[8]
Yannis E. Ioannidis, Eugene Wong: Transforming Nonlinear Recursion into Linear Recursion. Expert Database Conf. 1988: 401-421 BibTeX
[9]
...
[10]
Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181 BibTeX
[11]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX
[12]
Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 BibTeX
[13]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[14]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[15]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX
[16]
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

  1. Irène Guessarian, Jean-Eric Pin: Linearizing Some Recursive Logic Programs. IEEE Trans. Knowl. Data Eng. 7(1): 137-149(1995)
  2. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  3. Sergio Greco: Optimization of Chain Queries. DASFAA 1993: 261-268
  4. Tomás Feder, Yatin P. Saraiya: Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations. ICDT 1992: 297-311
  5. 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
  6. Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
  7. Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73
  8. Yatin P. Saraiya: Polynomial-Time Program Transformations in Deductive Databases. PODS 1990: 132-144
  9. Thane E. Plambeck: Semigroup Techniques in Recursive Query Optimization. PODS 1990: 145-153
  10. Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181
  11. 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