Database Paper Browser

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
802
Venue
PODS
Year
1987
Pagerank
0.00025830228
Overall Rank
359 | 97.51%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
448 The Magic of Duplicates and Aggregates 1990 VLDB 0.00022922417
910 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00015398775
1,122 Bottom-Up Beats Top-Down For Datalog 1989 PODS 0.00013837099
1,303 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012692678
1,381 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 0.00012271947
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
1,983 Logic Programming as Constructivism: A Formalization and its Application to Databases 1989 PODS 9.8694826e-05
2,048 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.689916e-05
2,179 Spinning Fast Iterative Data Flows 2012 VLDB 9.3632007e-05
2,473 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7048914e-05
2,544 Aggregation and Relevance in Deductive Databases 1991 VLDB 8.5646035e-05
2,679 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3223476e-05
2,777 Quickstep: A Data Platform Based on the Scaling-Up Approach 2018 VLDB 8.1346418e-05
2,809 Extending Relational Query Processing with ML Inference 2020 CIDR 8.0869552e-05
3,007 Benchmarking the Chase 2017 PODS 7.7243073e-05
3,012 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.7129076e-05
3,143 Dynamically Distributed Query Evaluation 2001 PODS 7.4881474e-05
3,284 Magic Conditions 1990 PODS 7.2738706e-05
3,409 End-to-end Optimization of Machine Learning Prediction Queries 2022 SIGMOD 7.1240791e-05
3,531 Efficient Querying of Inconsistent Databases with Binary Integer Programming 2013 VLDB 6.9982256e-05
3,556 Compiling Separable Recursions 1988 SIGMOD 6.9712392e-05
3,589 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9387274e-05
4,179 Argument Reduction by Factoring 1989 VLDB 6.3751001e-05
4,272 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 6.2933353e-05
4,320 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2822407e-05
4,324 Commutativity And Its Role In The Processing Of Linear Recursion 1989 VLDB 6.279813e-05
5,183 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6368566e-05
5,637 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.3978567e-05
6,363 On the Expected Size of Recursive Datalog Queries 1991 PODS 5.0896537e-05
6,412 Optimizing Existential Datalog Queries 1988 PODS 5.0668361e-05
6,513 An alternating fixpoint tailored to magic programs 1993 PODS 5.0273291e-05
6,514 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.0273291e-05
6,567 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.0023017e-05
6,955 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8812945e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8555836e-05
7,069 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.8380576e-05
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
7,603 Polynomial-time program transformations in deductive databases 1990 PODS 4.6959912e-05
7,981 How to Forget the Past Without Repeating It 1990 VLDB 4.6089395e-05
8,012 Compiling Query Constraints 1994 PODS 4.6021663e-05
8,777 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 4.4492064e-05
9,128 Counting Methods for Cyclic Relations 1988 PODS 4.3866751e-05
9,833 Magic Functions : A Technique To Optimize Extended Datalog Recursive Programs 1987 VLDB 4.2710095e-05
10,415 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1905499e-05
10,755 Scaling GPU-Accelerated Databases beyond GPU Memory Size 2025 VLDB 4.1905499e-05
12,805 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.1905499e-05
12,887 A Domain-theoretic Approach to Integrating Functional and Logic Database Languages 1993 VLDB 4.1905499e-05
12,899 Implementing Deductive Databases by Linear Programming 1992 PODS 4.1905499e-05
12,915 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.1905499e-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.00099936325
79 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00056010993
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
910 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00015398775
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,417 Overbound and Right-Linear Queries 1991 PODS 7.116211e-05
1,049 Safety of Recursive Horn Clauses With Infinite Relations 1987 PODS 0.00014426218
5,637 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.3978567e-05
3,284 Magic Conditions 1990 PODS 7.2738706e-05
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
7,069 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.8380576e-05
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
79 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00056010993
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00099936325
2,048 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.689916e-05