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: 955
Venue: PODS
Year: 1992
Pagerank: 7.105413e-05
Overall Rank: 3,812 | 73.85%
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
853	Queries Independent of Updates	1993	VLDB	0.00013587101
889	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013398105
1,031	Answering Queries Using Limited External Query Processors	1996	PODS	0.0001253927
1,124	Query Optimization by Predicate Move-Around	1994	VLDB	0.00012087356
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05
2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	8.0012184e-05
3,591	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.279053e-05
5,046	Toward Practical Constraint Databases	1993	VLDB	6.3879316e-05
8,827	Compiling Query Constraints	1994	PODS	5.3615981e-05
12,976	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	5.093636e-05
13,023	Universal Finiteness and Satisfiability	1994	PODS	5.093636e-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
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
3,307	Magic Conditions	1990	PODS	7.5385358e-05
3,360	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS	7.4890377e-05
3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0919497e-05
7,549	Hard problems for simple logic programs	1990	SIGMOD	5.6011655e-05

Semantically Similar Papers

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