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.4188795e-05
Overall Rank: 4,136 | 71.23%
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,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
3,435	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0966834e-05
8,772	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD	4.456315e-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
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
617	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00019090876
1,051	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00014440736
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831
1,196	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00013403617
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05
2,786	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	8.1283801e-05
3,010	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.7205569e-05
3,317	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.2283048e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
3,435	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0966834e-05
4,379	Safe Constraint Queries	1998	PODS	6.2397591e-05
2,339	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	9.005745e-05
3,010	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.7205569e-05
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
3,316	Temporal Deductive Databases and Infinite Objects	1988	PODS	7.2298413e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
1,051	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00014440736
12,829	Universal Finiteness and Satisfiability	1994	PODS	4.1945683e-05