Finding Nonrecursive Envelopes for Datalog Predicates

Summary: Proves that finding tight nonrecursive conjunctive envelopes for Datalog fixpoints is undecidable; tight lower envelopes iff boundedness, but tight upper envelopes can exist for unbounded predicates. Presents a decidable relaxation—connected envelopes—with an algorithm and applications. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 993
Venue: PODS
Year: 1993
Pagerank: 5.5217972e-05
Overall Rank: 7,888 | 45.89%
DOI: 10.1145/153850.153862

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Hewlett Packard Enterprise)

BibTeX Citation

@inproceedings{chaudhuri_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Finding Nonrecursive Envelopes for Datalog Predicates}},
        url = {https://dl.acm.org/doi/10.1145/153850.153862},
        doi = {10.1145/153850.153862},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chaudhuri, Surajit},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,310	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.9176726e-05
12,888	Approximate Query Translation Across Heterogeneous Information Sources	2000	VLDB	5.093636e-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
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
4,615	Tools for Datalog Boundedness	1991	PODS	6.6050069e-05
13,100	Detecting Redundant Tuples During Query Evaluation	1991	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
2	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
3	10,148	Size Bound-Adorned Datalog	2026	PODS
4	2,600	Convergence of Datalog over (Pre-) Semirings	2022	PODS
5	953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS
6	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
7	13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS
8	6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
9	4,615	Tools for Datalog Boundedness	1991	PODS
10	6,690	Can Datalog be approximated?	1994	PODS