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.00025585898
Overall Rank
365 | 97.47%
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
445 The Magic of Duplicates and Aggregates 1990 VLDB 0.0002294367
912 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00015414126
1,122 Bottom-Up Beats Top-Down For Datalog 1989 PODS 0.0001385042
1,302 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012705525
1,381 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 0.00012283951
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
1,979 Logic Programming as Constructivism: A Formalization and its Application to Databases 1989 PODS 9.8794371e-05
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05
2,172 Spinning Fast Iterative Data Flows 2012 VLDB 9.3706587e-05
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
2,544 Aggregation and Relevance in Deductive Databases 1991 VLDB 8.5730083e-05
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
2,772 Quickstep: A Data Platform Based on the Scaling-Up Approach 2018 VLDB 8.1401661e-05
2,804 Extending Relational Query Processing with ML Inference 2020 CIDR 8.0935487e-05
3,004 Benchmarking the Chase 2017 PODS 7.7314538e-05
3,010 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.7205569e-05
3,135 Dynamically Distributed Query Evaluation 2001 PODS 7.4963337e-05
3,283 Magic Conditions 1990 PODS 7.280826e-05
3,407 End-to-end Optimization of Machine Learning Prediction Queries 2022 SIGMOD 7.1295646e-05
3,524 Efficient Querying of Inconsistent Databases with Binary Integer Programming 2013 VLDB 7.0087032e-05
3,553 Compiling Separable Recursions 1988 SIGMOD 6.9779134e-05
3,585 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 6.9454028e-05
4,178 Argument Reduction by Factoring 1989 VLDB 6.3812002e-05
4,276 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 6.2976602e-05
4,288 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2891396e-05
4,329 Commutativity And Its Role In The Processing Of Linear Recursion 1989 VLDB 6.2858126e-05
5,180 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6422249e-05
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05
6,365 On the Expected Size of Recursive Datalog Queries 1991 PODS 5.0945408e-05
6,417 Optimizing Existential Datalog Queries 1988 PODS 5.0717071e-05
6,517 An alternating fixpoint tailored to magic programs 1993 PODS 5.0321577e-05
6,518 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.0321577e-05
6,567 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.0069599e-05
6,957 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8859842e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8602644e-05
7,075 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.842703e-05
7,156 Counting Methods for Cyclic Relations 1988 PODS 4.8145046e-05
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
7,598 Polynomial-time program transformations in deductive databases 1990 PODS 4.7004867e-05
7,978 How to Forget the Past Without Repeating It 1990 VLDB 4.613363e-05
8,010 Compiling Query Constraints 1994 PODS 4.6065603e-05
8,781 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 4.4534753e-05
9,834 Magic Functions : A Technique To Optimize Extended Datalog Recursive Programs 1987 VLDB 4.2751057e-05
10,404 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1945683e-05
10,749 Scaling GPU-Accelerated Databases beyond GPU Memory Size 2025 VLDB 4.1945683e-05
12,796 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.1945683e-05
12,877 A Domain-theoretic Approach to Integrating Functional and Logic Database Languages 1993 VLDB 4.1945683e-05
12,889 Implementing Deductive Databases by Linear Programming 1992 PODS 4.1945683e-05
12,905 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.1945683e-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.0010066783
77 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00057043861
296 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028644922
912 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00015414126
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,414 Overbound and Right-Linear Queries 1991 PODS 7.1232056e-05
1,051 Safety of Recursive Horn Clauses With Infinite Relations 1987 PODS 0.00014440736
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05
3,283 Magic Conditions 1990 PODS 7.280826e-05
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
7,075 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.842703e-05
296 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028644922
77 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00057043861
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.0010066783
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05