Database Paper Browser

Back to papers

MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)

Summary: Presents magic sets, a rewriting that turns goal-directed logic programs into bottom-up evaluation to prune irrelevant facts and leverage efficient bulk joins. Compares ad-hoc linear-rule implementations and emphasizes the challenge of proving optimal evaluation strategies. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
744
Venue
PODS
Year
1986
Pagerank
0.00099936325
Overall Rank
16 | 99.90%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 107 citing papers.

Rank Citing Paper Year Venue Pagerank
79 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00056010993
209 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00034147258
276 Regular Path Queries with Constraints 1997 PODS 0.00029365217
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
309 Extensible Query Processing in Starburst 1989 SIGMOD 0.00028195213
359 On the Power of Magic 1987 PODS 0.00025830228
364 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025657601
448 The Magic of Duplicates and Aggregates 1990 VLDB 0.00022922417
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022796106
520 LDL: A Logic-Based Data-Language 1986 VLDB 0.00021145923
569 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019912758
652 Logic Programming With Sets 1987 PODS 0.00018643929
725 An Algorithm For Ordering Subgoals In Nail! 1988 PODS 0.00017466684
774 Declarative Networking: Language, Execution and Optimization 2006 SIGMOD 0.00016775162
850 Optimizing the Rule-Data Interface in a KMS 1986 VLDB 0.00015911875
910 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00015398775
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
1,200 Data Independent Recursion in Deductive Databases 1986 PODS 0.00013342243
1,303 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012692678
1,313 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012629432
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
1,552 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011393892
1,611 One-Sided Recursions 1987 PODS 0.00011146101
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
1,740 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00010696383
1,872 Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue! 2005 PODS 0.00010255586
1,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
1,983 Logic Programming as Constructivism: A Formalization and its Application to Databases 1989 PODS 9.8694826e-05
2,038 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.7062591e-05
2,048 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.689916e-05
2,089 Practical Predicate Placement 1994 SIGMOD 9.5689208e-05
2,193 The Complexity Of Ordering Subgoals 1988 PODS 9.328009e-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
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,219 Query Optimization Techniques for Partitioned Tables 2011 SIGMOD 7.3592303e-05
3,284 Magic Conditions 1990 PODS 7.2738706e-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
3,739 Towards a Real Horn Clause Language 1988 VLDB 6.7979486e-05
3,920 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 6.6246708e-05
3,923 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 6.6232068e-05
3,926 Magic Shapes for SHACL Validation 2022 VLDB 6.6210393e-05
3,990 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5536618e-05
4,120 Context-Sensitive Program Analysis as Database Queries 2005 PODS 6.4306149e-05
4,179 Argument Reduction by Factoring 1989 VLDB 6.3751001e-05
4,198 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.361961e-05
4,225 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.3396067e-05
4,320 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2822407e-05
Previous Page 1 / 3 Next

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank Cited Paper Year Venue Pagerank
64 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00063295728
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,198 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.361961e-05
359 On the Power of Magic 1987 PODS 0.00025830228
1,313 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012629432
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
3,284 Magic Conditions 1990 PODS 7.2738706e-05
7,069 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.8380576e-05
448 The Magic of Duplicates and Aggregates 1990 VLDB 0.00022922417
2,048 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.689916e-05
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
5,637 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.3978567e-05