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

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

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