Tools for Datalog Boundedness

Summary: Develops tools to prove (un)decidability of Datalog boundedness under small-arity or few-rule regimes, pinpointing tight undecidability thresholds. Techniques: mortality reductions for arity-3 (and arity-1 with ≠); a polymorphic single-rule encoding for minimal-rule undecidability; semi-linear-set analysis to decide one-linear-rule plus initializations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 919
Venue: PODS
Year: 1991
Pagerank: 6.6050069e-05
Overall Rank: 4,615 | 68.34%
DOI: 10.1145/113413.113414

Incoming Non-self Citations Over Time

Authors

1. Gerd G. Hillebrand (Brown University)
2. Paris C. Kanellakis (Brown University)
3. Harry G. Mairson (Brandeis University)
4. Moshe Y. Vardi (International Business Machines Almaden Center)

BibTeX Citation

@inproceedings{hillebrand_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Tools for Datalog Boundedness}},
        url = {https://dl.acm.org/doi/10.1145/113413.113414},
        doi = {10.1145/113413.113414},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hillebrand, Gerd G. and Kanellakis, Paris C. and Mairson, Harry G. and Vardi, Moshe Y.},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
7,888	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.5217972e-05
10,640	Circuits and Formulas for Datalog over Semirings	2025	PODS	5.093636e-05
11,639	Deciding Boundedness of Monadic Sirups	2021	PODS	5.093636e-05
13,023	Universal Finiteness and Satisfiability	1994	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
916	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00013224702
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
2	13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS
3	8,128	Decidability and Undecidability Results for the Termination Problem of Active Database Rules	1998	PODS
4	6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS
5	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
6	10,148	Size Bound-Adorned Datalog	2026	PODS
7	13,023	Universal Finiteness and Satisfiability	1994	PODS
8	7,549	Hard problems for simple logic programs	1990	SIGMOD
9	1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS
10	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS