The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs

Ontology-mediated querying and querying in the presence of constraints aretwo key database problems where tuple-generating dependencies (TGDs) play acentral role. In ontology-mediated querying, TGDs can formalize the ontologyand thus derive additional facts from the given data, while in querying in thepresence of constraints, they restrict the set of admissible databases. In thiswork, we study the limits of efficient query evaluation in the context of theabove two problems, focussing on guarded and frontier-guarded TGDs and on UCQsas the actual queries. We show that a class of ontology-mediated queries (OMQs)based on guarded TGDs can be evaluated in FPT iff the OMQs in the class areequivalent to OMQs in which the actual query has bounded treewidth, up to somereasonable assumptions. For querying in the presence of constraints, weconsider classes of constraint-query specifications (CQSs) that bundle a set ofconstraints with an actual query. We show a dichotomy result for CQSs based onguarded TGDs that parallels the one for OMQs except that, additionally, FPTcoincides with PTime combined complexity. The proof is based on a novelconnection between OMQ and CQS evaluation. Using a direct proof, we also show asimilar dichotomy result, again up to some reasonable assumptions, for CQSsbased on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Ourresults on CQSs can be viewed as extensions of Grohe's well-knowncharacterization of the tractable classes of CQs (without constraints). LikeGrohe's characterization, all the above results assume that the arity ofrelation symbols is bounded by a constant. We also study the associated metaproblems, i.e., whether a given OMQ or CQS is equivalent to one in which theactual query has bounded treewidth.