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

Pablo Barceló, Victor Dalmau, Cristina Feier, Carsten Lutz, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus derive additional facts from the given data, while in querying in the presence of constraints, they restrict the set of admissible databases. In this work, we study the limits of efficient query evaluation in the context of the above two problems, focussing on guarded and frontier-guarded TGDs and on UCQs as 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 are equivalent to OMQs in which the actual query has bounded treewidth, up to some reasonable assumptions. For querying in the presence of constraints, we consider classes of constraint-query specifications (CQSs) that bundle a set of constraints with an actual query. We show a dichotomy result for CQSs based on guarded TGDs that parallels the one for OMQs except that, additionally, FPT coincides with PTime combined complexity. The proof is based on a novel connection between OMQ and CQS evaluation. Using a direct proof, we also show a similar dichotomy result, again up to some reasonable assumptions, for CQSs based on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Our results on CQSs can be viewed as extensions of Grohe’s well-known characterization of the tractable classes of CQs (without constraints). Like Grohe’s characterization, all the above results assume that the arity of relation symbols is bounded by a constant. We also study the associated meta problems, i.e., whether a given OMQ or CQS is equivalent to one in which the actual query has bounded treewidth.
Original languageEnglish
Title of host publicationProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 20)
PublisherAssociation for Computing Machinery (ACM)
Pages259–270
Number of pages12
ISBN (Electronic)9781450371087
DOIs
Publication statusPublished - 14 Jun 2020
Event2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States
Duration: 14 Jun 202019 Jun 2020
https://sigmod2020.org/

Conference

Conference2020 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD/PODS 2020
Country/TerritoryUnited States
CityPortland
Period14/06/2019/06/20
Internet address

Keywords

  • conjunctive queries
  • tuple-generating dependencies
  • guardedness
  • ontology-mediated queries
  • treewidth
  • query evaluation
  • complexity
  • fixed-parameter tractability

Fingerprint

Dive into the research topics of 'The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs'. Together they form a unique fingerprint.

Cite this