Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions

Summary: Characterizes decidability for Datalog with stratified negation and dense-order constraints: query-reachability and satisfiability decidable when negation applies only to EDBs or all EDBs are unary; equivalence decidable in the unary-EDB case. Provides algorithms to push constraints to EDBs and proves satisfiability undecidable for unary-IDB programs with stratified negation plus interpreted ≠. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc36b9963d358e31e
Venue: PODS
Year: 1993
Pagerank: 8.1006747e-05
Overall Rank: 2,716 | 81.75%
DOI: 10.1145/153850.153860

Incoming Non-self Citations Over Time

Authors

1. Alon Y. Levy (Stanford University)
2. Inderpal Singh Mumick (AT&T)
3. Yehoshua Sagiv (Hebrew University)
4. Oded Shmueli (Technion)

BibTeX Citation

@inproceedings{levy_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions}},
        url = {https://dl.acm.org/doi/10.1145/153850.153860},
        doi = {10.1145/153850.153860},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Levy, Alon Y. and Mumick, Inderpal Singh and Sagiv, Yehoshua and Shmueli, Oded},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013280642
1,119	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011950395
2,269	Deciding Equivalences among Aggregate Queries	1998	PODS	8.7196256e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.6038751e-05
4,636	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.4931113e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
5,739	Capturing Missing Tuples and Missing Values	2010	PODS	6.011429e-05
8,303	Decidability and Undecidability Results for the Termination Problem of Active Database Rules	1998	PODS	5.359571e-05
9,353	Verification of Relational Transducers for Electronic Commerce	2000	PODS	5.1886678e-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 5 of 5 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
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,908	Automata Theory for Database Theoreticians	1989	PODS	9.3940283e-05
3,541	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2161746e-05
3,886	Constraints and Redundancy in Datalog	1992	PODS	6.9461797e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
2	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS
3	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
4	13,313	Universal Finiteness and Satisfiability	1994	PODS
5	6,350	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS
6	3,886	Constraints and Redundancy in Datalog	1992	PODS
7	3,541	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD
8	317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS
9	2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
10	875	Queries Independent of Updates	1993	VLDB