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.054172e-05
Overall Rank: 2,830 | 80.32%
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.00014925576
1,302	Query Optimization by Predicate Move-Around	1994	VLDB	0.00012705525
2,103	Deciding Equivalences among Aggregate Queries	1998	PODS	9.5385023e-05
2,877	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9715251e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
5,195	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	5.6366303e-05
5,459	Capturing Missing Tuples and Missing Values	2010	PODS	5.4957751e-05
7,774	Decidability and Undecidability Results for the Termination Problem of Active Database Rules	1998	PODS	4.6543275e-05
8,833	Verification of Relational Transducers for Electronic Commerce	2000	PODS	4.439447e-05
12,782	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.1945683e-05
12,829	Universal Finiteness and Satisfiability	1994	PODS	4.1945683e-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
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
3,317	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2283048e-05
3,857	Constraints and Redundancy in Datalog	1992	PODS	6.6939005e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
12,829	Universal Finiteness and Satisfiability	1994	PODS	4.1945683e-05
4,298	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2885419e-05
3,857	Constraints and Redundancy in Datalog	1992	PODS	6.6939005e-05
3,317	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2283048e-05
200	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00035012858
2,877	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9715251e-05
938	Queries Independent of Updates	1993	VLDB	0.00015197786