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: 992
Venue: PODS
Year: 1993
Pagerank: 8.0466188e-05
Overall Rank: 2,836 | 80.30%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
971	Rewriting Aggregate Queries Using Views	1999	PODS	0.00014915911
1,303	Query Optimization by Predicate Move-Around	1994	VLDB	0.00012692678
2,105	Deciding Equivalences among Aggregate Queries	1998	PODS	9.5309231e-05
2,887	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9640219e-05
4,343	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2665123e-05
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
5,196	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	5.6311982e-05
5,466	Capturing Missing Tuples and Missing Values	2010	PODS	5.4904942e-05
7,774	Decidability and Undecidability Results for the Termination Problem of Active Database Rules	1998	PODS	4.6498948e-05
8,833	Verification of Relational Transducers for Electronic Commerce	2000	PODS	4.4352158e-05
12,791	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.1905499e-05
12,838	Universal Finiteness and Satisfiability	1994	PODS	4.1905499e-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
173	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038731283
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
3,320	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2212998e-05
3,859	Constraints and Redundancy in Datalog	1992	PODS	6.6875648e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,941	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.4229886e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
12,838	Universal Finiteness and Satisfiability	1994	PODS	4.1905499e-05
4,291	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2824978e-05
3,859	Constraints and Redundancy in Datalog	1992	PODS	6.6875648e-05
3,320	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2212998e-05
209	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00034147258
2,887	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9640219e-05
937	Queries Independent of Updates	1993	VLDB	0.00015194231