Database Paper Browser

Back to papers

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
1020
Venue
PODS
Year
1994
Pagerank
5.8899094e-05
Overall Rank
6,582 | 54.26%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
4,405 Filtering with Approximate Predicates 1998 VLDB 6.7827066e-05
6,230 Type Inference for Datalog and its Application to Query Optimisation 2008 PODS 6.0088715e-05
12,704 Approximate Query Translation Across Heterogeneous Information Sources 2000 VLDB 5.1725247e-05
12,801 Combinatorial Games in Database Theory 1995 PODS 5.1725247e-05
Previous Page 1 / 1 Next

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,926 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 9.5587587e-05
3,734 On the Expressive Power of Datalog: Tools and a Case Study 1990 PODS 7.2230344e-05
Previous Page 1 / 1 Next

Semantically Similar Papers