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.0010066783
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
4,370 Distributed Processing Of Logic Programs 1988 SIGMOD 6.2486359e-05
4,555 Magic Counting Methods 1987 SIGMOD 6.0891017e-05
4,732 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 5.9639609e-05
4,881 Translation And Optimization Of Logic Queries: The Algebraic Approach 1986 VLDB 5.8567721e-05
4,920 Shared Arrangements: practical inter-query sharing for streaming dataflows 2020 VLDB 5.8241888e-05
4,927 A Rule-based Language for Web Data Management 2011 PODS 5.8225392e-05
5,180 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6422249e-05
5,259 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD 5.5984356e-05
5,515 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 5.4636431e-05
5,534 Maintenance of Stratified Databases Viewed as a Belief Revision System 1987 PODS 5.4541693e-05
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05
5,992 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2415551e-05
6,236 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1436959e-05
6,312 Type Inference for Datalog and its Application to Query Optimisation 2008 PODS 5.1158809e-05
6,322 The BUDS Language for Distributed Bayesian Machine Learning 2017 SIGMOD 5.1124615e-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,518 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.0321577e-05
6,650 Efficient Identification of Implicit Facts in Incomplete OWL2-EL Knowledge Bases 2014 VLDB 4.9763184e-05
6,693 Modelling Non Deterministic Queries and Updates In Deductive Databases 1988 VLDB 4.9598818e-05
6,932 Database Updates in Logic Programming 1988 PODS 4.8925595e-05
6,957 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8859842e-05
6,963 Query Translation from XPath to SQL in the Presence of Recursive DTDs 2005 VLDB 4.8828629e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8602644e-05
7,156 Counting Methods for Cyclic Relations 1988 PODS 4.8145046e-05
7,342 Optimizing Recursive Queries with Program Synthesis 2022 SIGMOD 4.7576316e-05
7,598 Polynomial-time program transformations in deductive databases 1990 PODS 4.7004867e-05
7,817 Optimization Of Systems Of Algebraic Equations For Evaluating Datalog Queries 1987 VLDB 4.6435605e-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,012 Non-deterministic Modelling of Logical Queries in Deductive Databases 1987 SIGMOD 4.6064553e-05
8,066 Optimizing Iceberg Queries with Complex Joins 2017 SIGMOD 4.5937212e-05
8,600 Making RDBMSs Efficient on Graph Workloads Through Predefined Joins 2022 VLDB 4.4876776e-05
8,781 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 4.4534753e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3047774e-05
9,714 Materializing Knowledge Bases via Trigger Graphs 2021 VLDB 4.299267e-05
9,814 Optimizing Nested Recursive Queries 2024 SIGMOD 4.2783272e-05
9,834 Magic Functions : A Technique To Optimize Extended Datalog Recursive Programs 1987 VLDB 4.2751057e-05
9,997 Raqlet: Cross-Paradigm Compilation for Recursive Queries 2026 CIDR 4.1945683e-05
10,404 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1945683e-05
10,950 PLAQUE: Automated Predicate Learning at Query Time 2024 SIGMOD 4.1945683e-05
11,053 Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers 2024 VLDB 4.1945683e-05
11,179 Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue 2023 SIGMOD 4.1945683e-05
12,285 Declarative Reconfigurable Trust Management 2009 CIDR 4.1945683e-05
12,617 Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases 2003 PODS 4.1945683e-05
12,746 Binding Propagation in Disjunctive Databases 1998 VLDB 4.1945683e-05
12,856 Query Evaluation under the Well Founded Semantics (Extended Abstract) 1993 PODS 4.1945683e-05
12,871 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1945683e-05
12,889 Implementing Deductive Databases by Linear Programming 1992 PODS 4.1945683e-05
12,922 Backward chaining evaluation in stratified disjunctive theories 1990 PODS 4.1945683e-05
Previous Page 2 / 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
63 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00063714145
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,199 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.3662839e-05
365 On the Power of Magic 1987 PODS 0.00025585898
1,313 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.0001263831
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
3,283 Magic Conditions 1990 PODS 7.280826e-05
7,075 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.842703e-05
445 The Magic of Duplicates and Aggregates 1990 VLDB 0.0002294367
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05
296 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028644922
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05