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: 861
Venue: PODS
Year: 1989
Pagerank: 5.9850223e-05
Overall Rank: 6,077 | 58.31%
DOI: 10.1145/73721.73738

Incoming Non-self Citations Over Time

Authors

1. Yehoshua Sagiv (Hebrew University)
2. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{sagiv_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Safety of Datalog Queries over Infinite Databases}},
        url = {https://dl.acm.org/doi/10.1145/73721.73738},
        doi = {10.1145/73721.73738},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sagiv, Yehoshua and Vardi, Moshe Y.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0919497e-05
8,942	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD	5.3483178e-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
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
916	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00013224702
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,417	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010839353
1,498	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010567892
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
2,015	A Decidable Class of Bounded Recursions	1987	PODS	9.3047297e-05
3,025	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.8386928e-05
3,355	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.4912272e-05
3,476	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.3807586e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,615	Tools for Datalog Boundedness	1991	PODS
2	3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS
3	4,226	Safe Constraint Queries	1998	PODS
4	2,579	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS
5	3,355	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD
6	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
7	4,439	Temporal Deductive Databases and Infinite Objects	1988	PODS
8	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
9	1,498	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS
10	13,023	Universal Finiteness and Satisfiability	1994	PODS