Can Datalog be approximated?

Summary: Introduces a quantitative error notion and upper/lower-envelope constraints to study approximating recursive Datalog predicates by finite unions of CQs, contrasting absolute vs relative approximation. Proves absolute approximation impossible for unbounded Datalog, rules out constant-relative-error CQ approximations for broad unbounded classes, and gives sharp FO inapproximability for transitive closure and cycle queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1126848994f9aa71
Venue: PODS
Year: 1994
Pagerank: 5.6721201e-05
Overall Rank: 6,820 | 54.15%
DOI: 10.1145/182591.182602

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Hewlett Packard Enterprise)
2. Phokion G. Kolaitis (University of California Santa Cruz)

BibTeX Citation

@inproceedings{chaudhuri_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Can Datalog be approximated?}},
        url = {https://dl.acm.org/doi/10.1145/182591.182602},
        doi = {10.1145/182591.182602},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chaudhuri, Surajit and Kolaitis, Phokion G.},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,481	Filtering with Approximate Predicates	1998	VLDB	6.5807146e-05
6,437	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.7853525e-05
13,178	Approximate Query Translation Across Heterogeneous Information Sources	2000	VLDB	4.9793485e-05
13,276	Combinatorial Games in Database Theory	1995	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,005	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	9.2054933e-05
3,876	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	6.9534856e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,310	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS
2	8,168	Complete Approximations of Incomplete Queries	2013	VLDB
3	6,429	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
4	7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS
5	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
6	658	The Complexity of Query Reliability	1998	PODS
7	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS
8	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
9	8,055	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS
10	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS