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: 1019
Venue: PODS
Year: 1994
Pagerank: 5.8012926e-05
Overall Rank: 6,690 | 54.11%
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,435	Filtering with Approximate Predicates	1998	VLDB	6.7078883e-05
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
12,986	Combinatorial Games in Database Theory	1995	PODS	5.093636e-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
1,957	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	9.4146943e-05
3,800	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	7.1130834e-05

Semantically Similar Papers

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