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: 991
Venue: PODS
Year: 1993
Pagerank: 8.2831426e-05
Overall Rank: 2,662 | 81.74%
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
869	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013503594
1,124	Query Optimization by Predicate Move-Around	1994	VLDB	0.00012087356
2,238	Deciding Equivalences among Aggregate Queries	1998	PODS	8.8882317e-05
2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	8.0012184e-05
4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.7554436e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
5,062	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.3799383e-05
5,616	Capturing Missing Tuples and Missing Values	2010	PODS	6.1493013e-05
8,128	Decidability and Undecidability Results for the Termination Problem of Active Database Rules	1998	PODS	5.4825743e-05
9,178	Verification of Relational Transducers for Electronic Commerce	2000	PODS	5.3077309e-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 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
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
3,476	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.3807586e-05
3,812	Constraints and Redundancy in Datalog	1992	PODS	7.105413e-05

Semantically Similar Papers

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