DBScholar

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
ha405f7107a24aa27
Venue
PODS
Year
1986
Pagerank
0.00058997063
Overall Rank
18 | 99.89%
DOI
10.1145/6012.15399

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bancilhon_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/6012.15399},
        doi = {10.1145/6012.15399},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bancilhon, Francois and Maier, David and Sagiv, Yehoshua and Ullman, Jeffrey D.},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 108 citing papers.

Rank Citing Paper Year Venue Pagerank
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00037991902
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002251422
273 Extensible Query Processing in Starburst 1989 SIGMOD 0.00022498382
305 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00021580917
317 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00021210493
353 On the Power of Magic 1987 PODS 0.00020213935
356 Regular Path Queries with Constraints 1997 PODS 0.0002009439
440 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018219394
531 The Magic of Duplicates and Aggregates 1990 VLDB 0.00016845756
636 LDL: A Logic-Based Data-Language 1986 VLDB 0.00015361511
828 Logic Programming With Sets 1987 PODS 0.00013608891
859 Query Optimization by Simulated Annealing 1987 SIGMOD 0.0001341356
1,000 Declarative Networking: Language, Execution and Optimization 2006 SIGMOD 0.00012601156
1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012396854
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,168 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00011725733
1,201 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011555372
1,287 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011179513
1,333 An Algorithm For Ordering Subgoals In Nail! 1988 PODS 0.00010993243
1,439 Magic is Relevant 1990 SIGMOD 0.000106437
1,682 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8804595e-05
1,868 Optimizing the Rule-Data Interface in a KMS 1986 VLDB 9.4764925e-05
1,981 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.267247e-05
2,026 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.1626332e-05
2,035 Practical Predicate Placement 1994 SIGMOD 9.1519324e-05
2,067 One-Sided Recursions 1987 PODS 9.0898007e-05
2,100 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 9.0473405e-05
2,110 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.0195865e-05
2,474 Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue! 2005 PODS 8.4083096e-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
3,021 Graph-Theoretic Methods In Database Theory 1990 PODS 7.741152e-05
3,075 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.6742518e-05
3,103 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.6456038e-05
3,145 Query Optimization Techniques for Partitioned Tables 2011 SIGMOD 7.594509e-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,642 The Complexity Of Ordering Subgoals 1988 PODS 7.140621e-05
3,707 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 7.0789307e-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,158 Towards a Real Horn Clause Language 1988 VLDB 6.7704058e-05
4,187 Argument Reduction by Factoring 1989 VLDB 6.7450426e-05
4,206 Distributed Processing Of Logic Programs 1988 SIGMOD 6.7322742e-05
4,402 Shared Arrangements: practical inter-query sharing for streaming dataflows 2020 VLDB 6.6120647e-05
4,427 Magic Counting Methods 1987 SIGMOD 6.6008592e-05
4,483 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5780787e-05
4,557 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.5347712e-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
349 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00020245855
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,707 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD
2 353 On the Power of Magic 1987 PODS
3 1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD
4 1,439 Magic is Relevant 1990 SIGMOD
5 3,366 Magic Conditions 1990 PODS
6 7,281 Magic-sets Transformation in Nonrecursive Systems 1992 PODS
7 531 The Magic of Duplicates and Aggregates 1990 VLDB
8 1,981 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD
9 440 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS
10 6,875 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB