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.00035012858
Overall Rank
200 | 98.62%
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
172 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00038808816
566 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019970535
673 One-Sided Recursions 1987 PODS 0.00018348841
810 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00016428374
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
938 Queries Independent of Updates 1993 VLDB 0.00015197786
1,189 Independence of Logic Database Queries and Updates 1990 PODS 0.00013441514
1,578 Constraint Checking with Partial Information 1994 PODS 0.00011284233
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
1,952 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.9677831e-05
2,036 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.714898e-05
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05
2,206 A Decidable Class of Bounded Recursions 1987 PODS 9.2910236e-05
2,327 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.0276061e-05
2,341 Chasing Constrained Tuple-Generating Dependencies 1996 PODS 9.0034124e-05
2,735 Database Theory: Past and Future 1987 PODS 8.2069893e-05
3,317 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.2283048e-05
3,413 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1240395e-05
3,855 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6953401e-05
3,857 Constraints and Redundancy in Datalog 1992 PODS 6.6939005e-05
4,178 Argument Reduction by Factoring 1989 VLDB 6.3812002e-05
4,222 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.3480169e-05
4,491 Non-Deterministic Languages to Express Deterministic Transformations 1990 PODS 6.1422281e-05
4,631 Tools for Datalog Boundedness 1991 PODS 6.0347472e-05
4,732 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 5.9639609e-05
5,063 Tie-Breaking Semantics and Structural Totality (Extended Abstract) 1992 PODS 5.7267485e-05
5,180 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 5.6422249e-05
6,254 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.1368042e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8602644e-05
12,796 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.1945683e-05
12,905 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.1945683e-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.0010066783
38 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00075110004
63 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00063714145
77 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00057043861
172 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00038808816
296 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00028644922
537 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.0002068591
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,317 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.2283048e-05
6,236 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1436959e-05
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
938 Queries Independent of Updates 1993 VLDB 0.00015197786
7,817 Optimization Of Systems Of Algebraic Equations For Evaluating Datalog Queries 1987 VLDB 4.6435605e-05
6,417 Optimizing Existential Datalog Queries 1988 PODS 5.0717071e-05
6,932 Database Updates in Logic Programming 1988 PODS 4.8925595e-05
2,877 Semantic Query Optimization in Datalog Programs (Extended Abstract) 1995 PODS 7.9715251e-05
3,857 Constraints and Redundancy in Datalog 1992 PODS 6.6939005e-05
2,830 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.054172e-05