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.00059023577
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
4,618 Context-Sensitive Program Analysis as Database Queries 2005 PODS 6.4995364e-05
4,735 Translation and Optimization of Logic Queries: The Algebraic Approach 1986 VLDB 6.4452165e-05
4,768 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 6.4255719e-05
4,888 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.3693569e-05
5,050 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD 6.2976106e-05
5,073 A Rule-based Language for Web Data Management 2011 PODS 6.2870136e-05
5,413 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 6.1401229e-05
5,419 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 6.137651e-05
5,784 Maintenance of Stratified Databases Viewed as a Belief Revision System 1987 PODS 5.9961885e-05
6,053 Magic Shapes for SHACL Validation 2022 VLDB 5.9026026e-05
6,144 The BUDS Language for Distributed Bayesian Machine Learning 2017 SIGMOD 5.8717563e-05
6,429 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7884926e-05
6,433 Optimizing Existential Datalog Queries 1988 PODS 5.7868542e-05
6,437 Type Inference for Datalog and its Application to Query Optimisation 2008 PODS 5.7853525e-05
6,741 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.6913065e-05
6,750 On the Power of Alexander Templates (Extended Abstract) 1989 PODS 5.6906839e-05
6,871 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.6597986e-05
6,892 Modelling Non Deterministic Queries and Updates In Deductive Databases 1988 VLDB 5.6541068e-05
7,088 On the Expected Size of Recursive Datalog Queries 1991 PODS 5.6020796e-05
7,139 Optimizing Recursive Queries with Program Synthesis 2022 SIGMOD 5.6006128e-05
7,225 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5810777e-05
7,271 Efficient Identification of Implicit Facts in Incomplete OWL2-EL Knowledge Bases 2014 VLDB 5.5694935e-05
7,311 Query Translation from XPath to SQL in the Presence of Recursive DTDs 2005 VLDB 5.5562115e-05
7,682 Database Updates in Logic Programming 1988 PODS 5.4772833e-05
7,696 Hard problems for simple logic programs 1990 SIGMOD 5.4755041e-05
8,023 Optimizing Iceberg Queries with Complex Joins 2017 SIGMOD 5.4054487e-05
8,053 Polynomial-time program transformations in deductive databases 1990 PODS 5.3986864e-05
8,269 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3648571e-05
8,356 Optimizing Nested Recursive Queries 2024 SIGMOD 5.3481891e-05
8,464 How to Forget the Past Without Repeating It 1990 VLDB 5.3350162e-05
8,481 Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries 1987 VLDB 5.3330859e-05
8,483 Non-deterministic Modelling of Logical Queries in Deductive Databases 1987 SIGMOD 5.3327301e-05
8,641 Making RDBMSs Efficient on Graph Workloads Through Predefined Joins 2022 VLDB 5.2970759e-05
8,995 Compiling Query Constraints 1994 PODS 5.2414297e-05
9,689 Counting Methods for Cyclic Relations 1988 PODS 5.1406988e-05
9,794 Raqlet: Cross-Paradigm Compilation for Recursive Queries 2026 CIDR 5.1257999e-05
9,980 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 5.1013913e-05
10,034 Materializing Knowledge Bases via Trigger Graphs 2021 VLDB 5.0925155e-05
10,159 Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs 1987 VLDB 5.0690887e-05
10,334 Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers 2024 VLDB 5.0254535e-05
10,922 Virtualizing Recursion: Just-In-Time Graph Analytics in a Hyperscale Relational Warehouse 2026 VLDB 4.9793485e-05
11,126 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.9793485e-05
11,511 PLAQUE: Automated Predicate Learning at Query Time 2024 SIGMOD 4.9793485e-05
11,700 Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue 2023 SIGMOD 4.9793485e-05
12,771 Declarative Reconfigurable Trust Management 2009 CIDR 4.9793485e-05
13,100 Soft Stratification for Magic Set Based Query Evaluation in Deductive Databases 2003 PODS 4.9793485e-05
13,229 Binding Propagation in Disjunctive Databases 1998 VLDB 4.9793485e-05
13,339 Query Evaluation under the Well Founded Semantics (Extended Abstract) 1993 PODS 4.9793485e-05
13,355 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.9793485e-05
13,373 Implementing Deductive Databases by Linear Programming 1992 PODS 4.9793485e-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
349 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00020255174
Previous Page 1 / 1 Next

Semantically Similar Papers