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
808
Venue
PODS
Year
1987
Pagerank
0.0002168869
Overall Rank
313 | 97.86%
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
174 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00027231487
686 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014948634
839 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013692785
853 Queries Independent of Updates 1993 VLDB 0.00013587101
953 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012997935
1,314 Independence of Logic Database Queries and Updates 1990 PODS 0.00011182427
1,489 Constraint Checking with Partial Information 1994 PODS 0.00010612225
1,653 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.000101081
1,777 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.7849758e-05
1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.4809066e-05
1,970 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.3746238e-05
2,015 A Decidable Class of Bounded Recursions 1987 PODS 9.3047297e-05
2,033 One-Sided Recursions 1987 PODS 9.2819369e-05
2,117 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.1434045e-05
2,617 Chasing Constrained Tuple-Generating Dependencies 1996 PODS 8.3391085e-05
2,754 Database Theory: Past and Future 1987 PODS 8.164514e-05
3,245 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.60327e-05
3,476 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.3807586e-05
3,712 Non-Deterministic Languages to Express Deterministic Transformations 1990 PODS 7.1777407e-05
3,812 Constraints and Redundancy in Datalog 1992 PODS 7.105413e-05
4,099 Argument Reduction by Factoring 1989 VLDB 6.9030568e-05
4,343 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.7529086e-05
4,464 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.6860087e-05
4,615 Tools for Datalog Boundedness 1991 PODS 6.6050069e-05
4,673 Handling Redundancy in the Processing of Recursive Database Queries 1987 SIGMOD 6.573022e-05
5,288 Linearizing nonlinear recursions in polynomial time (Extended Abstract) 1989 PODS 6.280882e-05
5,735 Tie-Breaking Semantics and Structural Totality (Extended Abstract) 1992 PODS 6.105189e-05
6,008 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 6.0114207e-05
7,549 Hard problems for simple logic programs 1990 SIGMOD 5.6011655e-05
11,901 How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)? 2018 PODS 5.093636e-05
12,990 Magic Factoring of Closure Programs (Extended Abstract) 1995 PODS 5.093636e-05
13,100 Detecting Redundant Tuples During Query Evaluation 1991 PODS 5.093636e-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.00060089598
40 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00046918506
63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038782376
174 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00027231487
343 A Message Passing Framework for Logical Query Evaluation 1986 SIGMOD 0.00020669253
429 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018607152
616 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015712636
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,476 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD
2 6,613 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS
3 953 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS
4 853 Queries Independent of Updates 1993 VLDB
5 8,314 Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries 1987 VLDB
6 6,307 Optimizing Existential Datalog Queries 1988 PODS
7 7,536 Database Updates in Logic Programming 1988 PODS
8 2,883 Semantic Query Optimization in Datalog Programs (Extended Abstract) 1995 PODS
9 3,812 Constraints and Redundancy in Datalog 1992 PODS
10 2,662 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS