On the Power of Magic.

@inproceedings{DBLP:conf/pods/BeeriR87,
  author    = {Catriel Beeri and
               Raghu Ramakrishnan},
  title     = {On the Power of Magic},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {269-284},
  ee        = {http://doi.acm.org/10.1145/28659.28689, db/conf/pods/BeeriR87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

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

• 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

Online Edition: ACM Digital Library

Journal Version

References

[Bancilhon et al. 86]

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

[Bancilhon and Ramakrishnan 86a]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[Bancilhon and Ramakrishnan 86b]

...

[Beeri at al. 87]

Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37 BibTeX

[Henschen and Naqvi 84]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[Kifer and Lozinskii 85]

...

[Kifer and Lozinskii 86]

...

[Lloyd 84]

John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX

[Lozinskii 85]

Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177 BibTeX

[McKay and Shapiro 81]

...

[Rohmer and Lescoeur 85]

...

[Sacca and Zaniolo 86a]

Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX

[Sacca and Zaniolo 86b]

Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX

[Ullman 85]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[Van Gelder 86]

Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165 BibTeX

[Vieille 86]

Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

Referenced by

1. Chen Li, Edward Y. Chang: On Answering Queries in the Presence of Limited Access Patterns. ICDT 2001: 219-233
2. David B. Kemp, Kotagiri Ramamohanarao: Efficient Recursive Aggregation and Negation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 10(5): 727-745(1998)
3. Sergio Greco: Binding Propagation in Disjunctive Databases. VLDB 1998: 287-298
4. Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23
5. Chien-Le Goh, Masahiko Tsukamoto, Shojiro Nishio: Fast Methods with Magic Sampling for Knowledge Discovery in Deductive Databases with Large Deduction Results. ER Workshops 1998: 14-28
6. Nicola Leone, Pasquale Rullo, Antonella Mecchia, Giuseppe Rossi: A Deductive Environment for Dealing with Objects and Nonmonotonic Reasoning. IEEE Trans. Knowl. Data Eng. 9(4): 539-558(1997)
7. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
8. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)
9. Peter T. Wood: Magic Factoring of Closure Programs. PODS 1995: 174-183
10. Abdelkader Hameurlain, Franck Morvan: Scheduling and Mapping for Parallel Execution of Extended SQL Queries. CIKM 1995: 197-204
11. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
12. Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey, Tim S. Leask, James Harland: The Aditi Deductive Database System. VLDB J. 3(2): 245-288(1994)
13. Kotagiri Ramamohanarao, James Harland: An Introduction to Deductive Database Languages and Systems. VLDB J. 3(2): 107-122(1994)
14. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)
15. Werner Kießling, Helmut Schmidt, Werner Strauß, Gerhard Dünzinger: DECLARE and SDS: Early Efforts to Commercialize Deductive Database Technology. VLDB J. 3(2): 211-243(1994)
16. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation. VLDB J. 3(2): 123-160(1994)
17. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. IEEE Trans. Knowl. Data Eng. 6(4): 501-517(1994)
18. Wenyu Lu, Dik Lun Lee, Jiawei Han: A Study on the Structure of Linear Recursion. IEEE Trans. Knowl. Data Eng. 6(5): 723-737(1994)
19. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
20. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
21. Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67
22. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
23. Alexandra Poulovassilis, Carol Small: A Domain-theoretic Approach to Integrating Functional and Logic Database Languages. VLDB 1993: 416-428
24. Shinichi Morishita: An Alternating Fixpoint Tailored to Magic Programs. PODS 1993: 123-134
25. Philippe De Smedt, Stefano Ceri, Marie-Anne Neimat, Ming-Chien Shan, Rafi Ahmed: Recursive Functions in Iris. ICDE 1993: 145-154
26. Jiawei Han, Kangsheng Zeng, Tong Lu: Normalization of Linear Recursions in Deductive Databases. ICDE 1993: 559-567
27. Yangjun Chen: A Bottom-up Query Evaluation Method for Stratified Databases. ICDE 1993: 568-575
28. Sergio Greco, Nicola Leone, Pasquale Rullo: COMPLEX: An Object-Oriented Logic Programming System. IEEE Trans. Knowl. Data Eng. 4(4): 344-359(1992)
29. Ashish Gupta, Inderpal Singh Mumick: Magic-sets Transformation in Nonrecursive Systems. PODS 1992: 354-367
30. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Linear Programming. PODS 1992: 283-292
31. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
32. S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511
33. S. Seshadri, Jeffrey F. Naughton: On the Expected Size of Recursive Datalog Queries. PODS 1991: 268-279
34. Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
35. Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey: Design Overview of the Aditi Deductive Database System. ICDE 1991: 240-247
36. Béatrice Finance, Georges Gardarin: A Rule-Based Query Rewriter in an Extensible DBMS. ICDE 1991: 248-256
37. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
38. Kotagiri Ramamohanarao: The Aditi Deductive Database System (Extented Abstract). DASFAA 1991: 201-208
39. Burkhard Freitag, Heribert Schütz, Günther Specht: LOLA - A Logic Language for Deductive Databases and its Implementation. DASFAA 1991: 216-225
40. 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)
41. Michael Kifer, Eliezer L. Lozinskii: On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering. ACM Trans. Database Syst. 15(3): 385-426(1990)
42. Peter T. Wood: Factoring Augmented Regular Chain Programs. VLDB 1990: 255-263
43. Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. VLDB 1990: 278-289
44. Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277
45. Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries. VLDB 1990: 372-379
46. David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391
47. Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73
48. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
49. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
50. Yatin P. Saraiya: Polynomial-Time Program Transformations in Deductive Databases. PODS 1990: 132-144
51. Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171
52. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330
53. Seppo Sippu, Eljas Soisalon-Soininen: Multiple SIP Strategies and Bottom-Up Adorning in Logic Query Optimization. ICDT 1990: 485-498
54. Hervé Gallaire, Jean-Marie Nicolas: Logic and Databases: An Assessment. ICDT 1990: 177-186
55. Saumya K. Debray, Nai-Wei Lin: Static Estimation of Query Sizes in Horn Programs. ICDT 1990: 514-528
56. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
57. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Abstract Machine for LDL. EDBT 1990: 153-168
58. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989)
59. 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)
60. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989)
61. Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
62. Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163
63. Guy Hulin: Parallel Processing of Recursive Queries in Distributed Architectures. VLDB 1989: 87-96
64. Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242
65. Hirohisa Seki: On the Power of Alexander Templates. PODS 1989: 150-159
66. Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149
67. Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
68. François Bry: Logic Programming as Constructivism: A Formalization and its Application to Databases. PODS 1989: 34-50
69. Nikolaus Steger, Helmut Schmidt, Ulrich Güntzer, Werner Kießling: Semantics and Efficient Compilation for Quantitative Deductive Databases. ICDE 1989: 660-669
70. Jai Hyoung Rhee, Seog Park: An Extension of Counting Method for Efficient Processing of the Cyclic Data. DASFAA 1989: 320-326
71. Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
72. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. DASFAA 1989: 285-292
73. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
74. Eliezer L. Lozinskii: Computing Facts in Non-Horn Deductive Systems. VLDB 1988: 273-279
75. Raja Ramnarayan, Hongjun Lu: A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing. SIGMOD Conference 1988: 387-395
76. Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319
77. Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163
78. Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332
79. Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
80. Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340
81. Michael Kifer, Ai Li: On the Semantics of Rule-Based Expert Systems with Uncertainty. ICDT 1988: 102-117
82. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
83. Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477
84. Georges Gardarin: Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs. VLDB 1987: 21-30
85. Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37
86. Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226