Database Paper Browser

Back to papers

OPTIMIZING DATALOG PROGRAMS (Extended Abstract)

Summary: Proves uniform equivalence of Datalog (no function symbols, head vars occur in body) is decidable despite general equivalence being undecidable, and presents an algorithm to minimize programs under uniform equivalence. Also gives redundancy-removal techniques and a constraint-aware test for uniform equivalence. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
809
Venue
PODS
Year
1987
Pagerank
0.00034147258
Overall Rank
209 | 98.55%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
173 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00038731283
569 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019912758
808 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.000164132
907 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015417107
937 Queries Independent of Updates 1993 VLDB 0.00015194231
1,189 Independence of Logic Database Queries and Updates 1990 PODS 0.0001342924
1,579 Constraint Checking with Partial Information 1994 PODS 0.00011273105
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,959 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.958725e-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,212 A Decidable Class of Bounded Recursions 1987 PODS 9.2818302e-05
2,331 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.019917e-05
2,344 Chasing Constrained Tuple-Generating Dependencies 1996 PODS 8.9942907e-05
2,740 Database Theory: Past and Future 1987 PODS 8.1989773e-05
3,320 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.2212998e-05
3,414 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1172834e-05
3,859 Constraints and Redundancy in Datalog 1992 PODS 6.6875648e-05
3,860 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6864693e-05
4,179 Argument Reduction by Factoring 1989 VLDB 6.3751001e-05
4,225 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.3396067e-05
4,479 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 6.1439609e-05
4,494 Non-Deterministic Languages to Express Deterministic Transformations 1990 PODS 6.1363251e-05
4,631 Tools for Datalog Boundedness 1991 PODS 6.0289457e-05
5,058 Tie-Breaking Semantics and Structural Totality (Extended Abstract) 1992 PODS 5.7212391e-05
5,183 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6368566e-05
6,253 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.1318715e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8555836e-05
12,805 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.1905499e-05
12,915 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.00099936325
38 Testing Implications Of Data Dependencies 1979 SIGMOD 0.0007528369
64 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00063295728
79 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00056010993
173 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00038731283
299 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028555103
541 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00020586706
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,320 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.2212998e-05
6,234 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1387584e-05
907 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015417107
937 Queries Independent of Updates 1993 VLDB 0.00015194231
7,823 Optimization Of Systems Of Algebraic Equations For Evaluating Datalog Queries 1987 VLDB 4.6390991e-05
6,412 Optimizing Existential Datalog Queries 1988 PODS 5.0668361e-05
6,934 Database Updates in Logic Programming 1988 PODS 4.8878659e-05
2,887 Semantic Query Optimization in Datalog Programs (Extended Abstract) 1995 PODS 7.9640219e-05
3,859 Constraints and Redundancy in Datalog 1992 PODS 6.6875648e-05
2,836 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.0466188e-05