Safety of Datalog Queries over Infinite Databases

Summary: Decomposes Datalog safety under finiteness constraints into weak safety (decidable; guarantees finite intermediate answers) and termination (undecidable; guarantees finite evaluation). Shows safety is PTIME-decidable for monadic programs but undecidable w.r.t. FDs even for monadic. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 862
Venue: PODS
Year: 1989
Pagerank: 6.4127061e-05
Overall Rank: 4,138 | 71.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yehoshua Sagiv
2. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
3,414	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1172834e-05
3,440	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0897313e-05
8,769	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD	4.4520434e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
173	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038731283
612	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.0001915957
1,049	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00014426218
1,167	On Computing Restricted Projections of Representative Instances	1985	PODS	0.0001354084
1,200	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013342243
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05
2,790	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	8.1203289e-05
3,012	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.7129076e-05
3,320	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2212998e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
3,440	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0897313e-05
4,376	Safe Constraint Queries	1998	PODS	6.233754e-05
2,343	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	8.9968717e-05
3,012	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.7129076e-05
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
3,318	Temporal Deductive Databases and Infinite Objects	1988	PODS	7.2227559e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
1,049	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00014426218
12,838	Universal Finiteness and Satisfiability	1994	PODS	4.1905499e-05