Constraints and Redundancy in Datalog

Summary: Introduces two redundancy notions for Datalog—reachability (rules/predicates not on any derivation tree for the query) and irrelevance (based on minimal derivation trees)—and provides algorithms that detect them and build redundancy-free rule‑goal trees. Handles constraint literals, tightly pushes constraints to EDB under stated assumptions, and relates redundancy elimination to uniform-equivalence minimization and magic-set/style constraint-pushing. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h98231bcfb65056cc
Venue: PODS
Year: 1992
Pagerank: 6.9461797e-05
Overall Rank: 3,886 | 73.88%
DOI: 10.1145/137097.137111

Incoming Non-self Citations Over Time

Authors

1. Alon Levy (Stanford University)
2. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{levy_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{Constraints and Redundancy in Datalog}},
        url = {https://dl.acm.org/doi/10.1145/137097.137111},
        doi = {10.1145/137097.137111},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Levy, Alon and Sagiv, Yehoshua},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
875	Queries Independent of Updates	1993	VLDB	0.00013316445
914	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013104061
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012275281
1,119	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011950395
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.1006747e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
3,667	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.1163605e-05
5,170	Toward Practical Constraint Databases	1993	VLDB	6.2448851e-05
8,995	Compiling Query Constraints	1994	PODS	5.2414297e-05
13,266	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.9793485e-05
13,313	Universal Finiteness and Satisfiability	1994	PODS	4.9793485e-05

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
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
1,908	Automata Theory for Database Theoreticians	1989	PODS	9.3940283e-05
3,364	Magic Conditions	1990	PODS	7.3731362e-05
3,417	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS	7.3218419e-05
3,904	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	6.9336057e-05
7,696	Hard problems for simple logic programs	1990	SIGMOD	5.4755041e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,704	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB
2	2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
3	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
4	2,551	Aggregation and Relevance in Deductive Databases	1991	VLDB
5	13,390	Detecting Redundant Tuples During Query Evaluation	1991	PODS
6	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
7	13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
8	14,679	The Complexity of Reusing and Modifying Rulebases	1992	PODS
9	2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS
10	317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS