A More General Theory of Static Approximations for Conjunctive Queries

Pablo Barceló, Miguel Romero, Thomas Zeume

Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. Approximating a hard CQ by a query from such a fragment can thus al…