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
h1e536adb333d85f4
Venue
PODS
Year
1987
Pagerank
0.0002014941
Overall Rank
353 | 97.64%
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
533 The Magic of Duplicates and Aggregates 1990 VLDB 0.00016794756
1,056 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00012252667
1,122 Query Optimization by Predicate Move-Around 1994 VLDB 0.00011915958
1,443 Magic is Relevant 1990 SIGMOD 0.00010618161
1,571 Bottom-Up Beats Top-Down For Datalog 1989 PODS 0.00010176128
1,688 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8481921e-05
1,758 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 9.6999549e-05
1,986 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.2371562e-05
2,147 Quickstep: A Data Platform Based on the Scaling-Up Approach 2018 VLDB 8.9595129e-05
2,199 Extending Relational Query Processing with ML Inference 2020 CIDR 8.8664379e-05
2,240 Spinning Fast Iterative Data Flows 2012 VLDB 8.7716808e-05
2,535 Logic Programming as Constructivism: A Formalization and its Application to Databases 1989 PODS 8.3090714e-05
2,556 Aggregation and Relevance in Deductive Databases 1991 VLDB 8.2787456e-05
2,607 Efficient Querying of Inconsistent Databases with Binary Integer Programming 2013 VLDB 8.2111488e-05
2,668 Benchmarking the Chase 2017 PODS 8.1323973e-05
2,672 End-to-end Optimization of Machine Learning Prediction Queries 2022 SIGMOD 8.1301225e-05
3,030 Graph-Theoretic Methods In Database Theory 1990 PODS 7.7156987e-05
3,378 Magic Conditions 1990 PODS 7.3454229e-05
3,427 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.2959413e-05
3,567 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.1826291e-05
3,602 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.1572829e-05
3,722 Compiling Separable Recursions 1988 SIGMOD 7.0503269e-05
3,769 Dynamically Distributed Query Evaluation 2001 PODS 7.0154753e-05
3,856 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9565167e-05
4,206 Argument Reduction by Factoring 1989 VLDB 6.722747e-05
4,249 Commutativity and Its Role in the Processing of Linear Recursion 1989 VLDB 6.6912366e-05
4,912 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.345416e-05
5,434 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 6.1169559e-05
6,448 Optimizing Existential Datalog Queries 1988 PODS 5.7650024e-05
6,681 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.6945953e-05
6,774 An alternating fixpoint tailored to magic programs 1993 PODS 5.669182e-05
6,775 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.669182e-05
6,894 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.6384137e-05
7,112 On the Expected Size of Recursive Datalog Queries 1991 PODS 5.5809131e-05
7,246 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5599899e-05
7,300 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 5.5461529e-05
7,599 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4717527e-05
7,716 Hard problems for simple logic programs 1990 SIGMOD 5.4548161e-05
8,007 Scaling GPU-Accelerated Databases beyond GPU Memory Size 2025 VLDB 5.3916546e-05
8,076 Polynomial-time program transformations in deductive databases 1990 PODS 5.378291e-05
8,291 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3445863e-05
8,488 How to Forget the Past Without Repeating It 1990 VLDB 5.3148581e-05
9,022 Compiling Query Constraints 1994 PODS 5.2216313e-05
9,724 Counting Methods for Cyclic Relations 1988 PODS 5.121278e-05
10,198 Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs 1987 VLDB 5.0499354e-05
11,195 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.9605343e-05
13,327 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.9605343e-05
13,408 A Domain-theoretic Approach to Integrating Functional and Logic Database Languages 1993 VLDB 4.9605343e-05
13,420 Implementing Deductive Databases by Linear Programming 1992 PODS 4.9605343e-05
13,437 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.9605343e-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
18 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00058816744
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.0003786983
443 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018161613
1,056 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00012252667
Previous Page 1 / 1 Next

Semantically Similar Papers

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