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.00020213935
Overall Rank
353 | 97.63%
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
531 The Magic of Duplicates and Aggregates 1990 VLDB 0.00016845756
1,049 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00012293092
1,119 Query Optimization by Predicate Move-Around 1994 VLDB 0.00011946162
1,439 Magic is Relevant 1990 SIGMOD 0.000106437
1,566 Bottom-Up Beats Top-Down For Datalog 1989 PODS 0.00010209764
1,682 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8804595e-05
1,746 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 9.7314096e-05
1,981 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.267247e-05
2,139 Quickstep: A Data Platform Based on the Scaling-Up Approach 2018 VLDB 8.9735524e-05
2,184 Extending Relational Query Processing with ML Inference 2020 CIDR 8.8953085e-05
2,228 Spinning Fast Iterative Data Flows 2012 VLDB 8.7996087e-05
2,528 Logic Programming as Constructivism: A Formalization and its Application to Databases 1989 PODS 8.3365843e-05
2,551 Aggregation and Relevance in Deductive Databases 1991 VLDB 8.3057709e-05
2,597 Efficient Querying of Inconsistent Databases with Binary Integer Programming 2013 VLDB 8.2383888e-05
2,661 End-to-end Optimization of Machine Learning Prediction Queries 2022 SIGMOD 8.1568473e-05
2,675 Benchmarking the Chase 2017 PODS 8.1442721e-05
3,021 Graph-Theoretic Methods In Database Theory 1990 PODS 7.741152e-05
3,366 Magic Conditions 1990 PODS 7.3696512e-05
3,415 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.3201296e-05
3,557 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.2052788e-05
3,593 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.1803217e-05
3,715 Compiling Separable Recursions 1988 SIGMOD 7.0736815e-05
3,765 Dynamically Distributed Query Evaluation 2001 PODS 7.0386131e-05
3,849 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9795056e-05
4,187 Argument Reduction by Factoring 1989 VLDB 6.7450426e-05
4,228 Commutativity and Its Role in the Processing of Linear Recursion 1989 VLDB 6.7134031e-05
4,889 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.3663595e-05
5,417 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 6.1372173e-05
6,436 Optimizing Existential Datalog Queries 1988 PODS 5.7841149e-05
6,668 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.7134654e-05
6,754 An alternating fixpoint tailored to magic programs 1993 PODS 5.68799e-05
6,755 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.68799e-05
6,875 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.6571194e-05
7,090 On the Expected Size of Recursive Datalog Queries 1991 PODS 5.5994281e-05
7,227 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5784356e-05
7,281 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 5.5645528e-05
7,583 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4898987e-05
7,702 Hard problems for simple logic programs 1990 SIGMOD 5.4729121e-05
8,059 Polynomial-time program transformations in deductive databases 1990 PODS 5.3961311e-05
8,275 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3623175e-05
8,280 Scaling GPU-Accelerated Databases beyond GPU Memory Size 2025 VLDB 5.3616863e-05
8,473 How to Forget the Past Without Repeating It 1990 VLDB 5.3324907e-05
9,004 Compiling Query Constraints 1994 PODS 5.2389486e-05
9,695 Counting Methods for Cyclic Relations 1988 PODS 5.1382653e-05
10,163 Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs 1987 VLDB 5.066689e-05
11,135 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.9769913e-05
13,286 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.9769913e-05
13,367 A Domain-theoretic Approach to Integrating Functional and Logic Database Languages 1993 VLDB 4.9769913e-05
13,379 Implementing Deductive Databases by Linear Programming 1992 PODS 4.9769913e-05
13,396 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.9769913e-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.00058997063
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00037991902
440 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018219394
1,049 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00012293092
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,677 Overbound and Right-Linear Queries 1991 PODS
2 1,536 Safety of Recursive Horn Clauses With Infinite Relations 1987 PODS
3 6,875 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB
4 3,366 Magic Conditions 1990 PODS
5 1,439 Magic is Relevant 1990 SIGMOD
6 7,281 Magic-sets Transformation in Nonrecursive Systems 1992 PODS
7 440 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,981 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD