DBScholar

Back to papers

On the Power of Magic

Summary: Formalizes sideways information passing (SIP) and models recursive evaluation as SIP+control, isolating a strategy class subsuming most DB recursive-evaluation algorithms. Shows any strategy is realizable by program rewrites evaluated bottom-up, generalizing Magic Sets/Counting, with safety and optimality results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
801
Venue
PODS
Year
1987
Pagerank
0.00020659405
Overall Rank
344 | 97.65%
DOI
10.1145/28659.28689

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{beeri_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{On the Power of Magic}},
        url = {https://dl.acm.org/doi/10.1145/28659.28689},
        doi = {10.1145/28659.28689},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Beeri, Catriel and Ramakrishnan, Raghu},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
527 The Magic of Duplicates and Aggregates 1990 VLDB 0.00017108864
1,026 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00012578477
1,124 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012087356
1,410 Magic is Relevant 1990 SIGMOD 0.00010853223
1,538 Bottom-Up Beats Top-Down For Datalog 1989 PODS 0.00010446034
1,653 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.000101081
1,714 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 9.9404301e-05
1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.4809066e-05
2,156 Quickstep: A Data Platform Based on the Scaling-Up Approach 2018 VLDB 9.0635624e-05
2,196 Spinning Fast Iterative Data Flows 2012 VLDB 8.9704984e-05
2,293 Extending Relational Query Processing with ML Inference 2020 CIDR 8.7949378e-05
2,474 Logic Programming as Constructivism: A Formalization and its Application to Databases 1989 PODS 8.5305658e-05
2,511 Aggregation and Relevance in Deductive Databases 1991 VLDB 8.4854377e-05
2,551 Efficient Querying of Inconsistent Databases with Binary Integer Programming 2013 VLDB 8.4290374e-05
2,634 Benchmarking the Chase 2017 PODS 8.3210907e-05
2,865 End-to-end Optimization of Machine Learning Prediction Queries 2022 SIGMOD 8.0180243e-05
2,957 Graph-Theoretic Methods In Database Theory 1990 PODS 7.9200375e-05
3,307 Magic Conditions 1990 PODS 7.5385358e-05
3,355 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.4912272e-05
3,491 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.3658999e-05
3,571 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.2991953e-05
3,629 Compiling Separable Recursions 1988 SIGMOD 7.2392728e-05
3,689 Dynamically Distributed Query Evaluation 2001 PODS 7.2010583e-05
3,767 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 7.1421254e-05
4,099 Argument Reduction by Factoring 1989 VLDB 6.9030568e-05
4,150 Commutativity and Its Role in the Processing of Linear Recursion 1989 VLDB 6.8705682e-05
4,773 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.5149869e-05
5,288 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 6.280882e-05
6,307 Optimizing Existential Datalog Queries 1988 PODS 5.9196585e-05
6,540 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.8471897e-05
6,620 An alternating fixpoint tailored to magic programs 1993 PODS 5.8212982e-05
6,621 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.8212982e-05
6,729 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.789691e-05
6,948 On the Expected Size of Recursive Datalog Queries 1991 PODS 5.7306589e-05
7,079 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.7090732e-05
7,131 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 5.694968e-05
7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.6184826e-05
7,549 Hard problems for simple logic programs 1990 SIGMOD 5.6011655e-05
7,886 Polynomial-time program transformations in deductive databases 1990 PODS 5.5225498e-05
8,296 How to Forget the Past Without Repeating It 1990 VLDB 5.4574671e-05
8,721 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3772617e-05
8,827 Compiling Query Constraints 1994 PODS 5.3615981e-05
9,503 Counting Methods for Cyclic Relations 1988 PODS 5.2586367e-05
9,981 Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs 1987 VLDB 5.1845938e-05
10,690 Dynamic Pruning for Recursive Joins 2025 SIGMOD 5.093636e-05
10,985 Scaling GPU-Accelerated Databases beyond GPU Memory Size 2025 VLDB 5.093636e-05
12,990 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 5.093636e-05
13,071 A Domain-theoretic Approach to Integrating Functional and Logic Database Languages 1993 VLDB 5.093636e-05
13,083 Implementing Deductive Databases by Linear Programming 1992 PODS 5.093636e-05
13,100 Detecting Redundant Tuples During Query Evaluation 1991 PODS 5.093636e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00060089598
63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038782376
429 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018607152
1,026 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00012578477
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,603 Overbound and Right-Linear Queries 1991 PODS
2 1,498 Safety of Recursive Horn Clauses With Infinite Relations 1987 PODS
3 6,729 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB
4 3,307 Magic Conditions 1990 PODS
5 1,410 Magic is Relevant 1990 SIGMOD
6 7,131 Magic-sets Transformation in Nonrecursive Systems 1992 PODS
7 429 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS
8 63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD
9 16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS
10 1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD