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

Magic Counting Methods.

Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59
@inproceedings{DBLP:conf/sigmod/SaccaZ87,
  author    = {Domenico Sacc{\`a} and
               Carlo Zaniolo},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Magic Counting Methods},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {49-59},
  ee        = {http://doi.acm.org/10.1145/38713.38725, db/conf/sigmod/SaccaZ87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The problem considered is that of implementing recursive queries, expressed in a logic-based language, by efficient fixpoint computations. In particular, the situation is studied where the initial bindings in the recursive predicate can be used to restrict the search space and ensure safety of execution. Two key techniques previously proposed to solve this problem are (i) the highly efficient counting method, and (ii) the magic set method which is safe in a wider range of situations than (i). In this paper, we present a family of methods, called the magic counting methods, that combines the advantages of (i) and (ii). This is made possible by the similarity of the strategies used by the counting method and the magic set method for propagating the bindings. This paper introduces these new methods, examines their computational complexity, and illustrates the trade-offs between the family members and their superiority with respect to the old methods.

Copyright © 1987 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Umeshwar Dayal, Irving L. Traiger (Eds.): Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987. ACM Press 1987 BibTeX , SIGMOD Record 16(3)
Contents

Online Edition: ACM Digital Library


References

[Ban]
...
[BaR]
Isaac Balbin, Kotagiri Ramamohanarao: A Generalization of the Differential Approach to Recursive Query Evaluation. J. Log. Program. 4(3): 259-262(1987) BibTeX
[BMSU]
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
[BR]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[HN]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[MK]
...
[MPS]
Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301 BibTeX
[SZ1]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX
[SZ2]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX
[SZ3]
Domenico Saccà, Carlo Zaniolo: Implementation of Recursive Queries for a Data Language Based on Pure Horn Logic. ICLP 1987: 104-135 BibTeX
[Tar]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[TZ]
Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 BibTeX
[UI]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[VK]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

Referenced by

  1. Yangjun Chen: Speeding up the Counting Method by Computing Heritage Functions in Topological Order. ADBIS 1997: 108-116
  2. Johann Eder: View Definitions with Parameters. ADBIS 1995: 170-184
  3. Kotagiri Ramamohanarao, James Harland: An Introduction to Deductive Database Languages and Systems. VLDB J. 3(2): 107-122(1994)
  4. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  5. Philippe De Smedt, Stefano Ceri, Marie-Anne Neimat, Ming-Chien Shan, Rafi Ahmed: Recursive Functions in Iris. ICDE 1993: 145-154
  6. Sergio Greco, Nicola Leone, Pasquale Rullo: COMPLEX: An Object-Oriented Logic Programming System. IEEE Trans. Knowl. Data Eng. 4(4): 344-359(1992)
  7. Sergio Greco, Carlo Zaniolo: Optimization of Linear Logic Programs Using Counting Methods. EDBT 1992: 72-87
  8. S. Seshadri, Jeffrey F. Naughton: On the Expected Size of Recursive Datalog Queries. PODS 1991: 268-279
  9. 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)
  10. David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391
  11. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  12. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  13. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  14. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989)
  15. Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
  16. W. Yan, Nelson Mendonça Mattos: Transitive Closure and the LOGA+-Strategy for its Efficient Evaluation. MFDBS 1989: 415-428
  17. Erik Lambrichts, Peter Nees, Jan Paredaens, Peter Peelman, Letizia Tanca: Integration of Functions in the Fixpoint Semantics of Rule-Based Systems. MFDBS 1989: 301-316
  18. Hussien Aly, Z. Meral Özsoyoglu: Synchronized Counting Method. ICDE 1989: 366-373
  19. Jai Hyoung Rhee, Seog Park: An Extension of Counting Method for Efficient Processing of the Cyclic Data. DASFAA 1989: 320-326
  20. Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
  21. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  22. Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340
  23. Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301
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:39:48 2009