DBScholar

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
h886a5fed09f0d73d
Venue
PODS
Year
1987
Pagerank
0.00021142713
Overall Rank
319 | 97.87%
DOI
10.1145/28659.28696

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{sagiv_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{OPTIMIZING DATALOG PROGRAMS (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/28659.28696},
        doi = {10.1145/28659.28696},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sagiv, Yehoshua},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank Citing Paper Year Venue Pagerank
179 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00026563438
703 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014638214
862 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013372073
878 Queries Independent of Updates 1993 VLDB 0.0001326705
981 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012688969
1,355 Independence of Logic Database Queries and Updates 1990 PODS 0.00010910619
1,522 Constraint Checking with Partial Information 1994 PODS 0.00010341308
1,688 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8481921e-05
1,827 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.5417632e-05
1,986 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.2371562e-05
2,038 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.1328477e-05
2,075 A Decidable Class of Bounded Recursions 1987 PODS 9.0631365e-05
2,078 One-Sided Recursions 1987 PODS 9.0607099e-05
2,166 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 8.9171951e-05
2,652 Chasing Constrained Tuple-Generating Dependencies 1996 PODS 8.1495688e-05
2,816 Database Theory: Past and Future 1987 PODS 7.9542377e-05
3,326 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.4103766e-05
3,551 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.188942e-05
3,808 Non-Deterministic Languages to Express Deterministic Transformations 1990 PODS 6.9901793e-05
3,898 Constraints and Redundancy in Datalog 1992 PODS 6.9199453e-05
4,206 Argument Reduction by Factoring 1989 VLDB 6.722747e-05
4,443 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.5820613e-05
4,575 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.5132348e-05
4,728 Tools for Datalog Boundedness 1991 PODS 6.4324136e-05
4,790 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 6.4012965e-05
5,434 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 6.1169559e-05
5,875 Tie-Breaking Semantics and Structural Totality (Extended Abstract) 1992 PODS 5.9456544e-05
6,149 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.8557417e-05
7,716 Hard problems for simple logic programs 1990 SIGMOD 5.4548161e-05
12,250 How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)? 2018 PODS 4.9605343e-05
13,327 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 4.9605343e-05
13,437 Detecting Redundant Tuples During Query Evaluation 1991 PODS 4.9605343e-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
18 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00058816744
41 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00045733094
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.0003786983
179 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00026563438
351 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00020181666
443 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018161613
637 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015323882
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,728 Tools for Datalog Boundedness 1991 PODS
2 6,764 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS
3 981 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS
4 878 Queries Independent of Updates 1993 VLDB
5 8,503 Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries 1987 VLDB
6 6,448 Optimizing Existential Datalog Queries 1988 PODS
7 7,701 Database Updates in Logic Programming 1988 PODS
8 2,937 Semantic Query Optimization in Datalog Programs (Extended Abstract) 1995 PODS
9 3,898 Constraints and Redundancy in Datalog 1992 PODS
10 2,727 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS