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

On the Expected Size of Recursive Datalog Queries.

S. Seshadri, Jeffrey F. Naughton: On the Expected Size of Recursive Datalog Queries. PODS 1991: 268-279
@inproceedings{DBLP:conf/pods/SeshadriN91,
  author    = {S. Seshadri and
               Jeffrey F. Naughton},
  title     = {On the Expected Size of Recursive Datalog Queries},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {268-279},
  ee        = {http://doi.acm.org/10.1145/113413.113438, db/conf/pods/SeshadriN91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present asymptotically exact expressions for the expected sizes of relations defined by two well-studied Datalog recursions, namely the "same generation" and "canonical factorable recursion". We consider the size of the fixpoints of the recursively defined relations in the above programs, as well as the size of the fixpoints of the relations defined by the rewritten programs generated by the Magic Sets and Factoring rewriting algorithms in response to selection queries. Our results show that even over relatively sparse base relations, the recursively defined relations are within a small constant factor of their worst-case size bounds, and that the Magic Sets rewriting algorithm on the average produces relations within a small constant factor of the corresponding bounds for the recursion without rewriting. The expected size of relations produced by the Factoring algorithm, when it applies, is significantly smaller than the expected size of relations produced by Magic Sets. This lends credence to the belief that reducing the arity of the recursive predicate is probably more important than restricting the recursion to relevant tuples.

Copyright © 1991 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 Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1027 KB]

References

[AKS81]
...
[BKBR87]
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bol85]
...
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BR88]
...
[GKS91]
Sumit Ganguly, Ravi Krishnamurthy, Abraham Silberschatz: An Analysis Technique for Transitive Closure Algorithms: A Statistical Approach. ICDE 1991: 728-735 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HL86]
Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HN88]
Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kar90]
...
[MSPS87]
Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nau88]
...
[NRSU89]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rag86]
Prabhakar Raghavan: Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs. FOCS 1986: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ram88]
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RS62]
...
[SZ87]
Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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