Query Evaluation in Open and Closed Worlds: Testing, Enumeration, and Counting (QTEC).

• Applicant: Professor Dr. Carsten Lutz
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 444619301

In databases, constraints serve many useful purposes. Interpreting them under a closed-world semantics means to constrain the set of admissible databases and querying such constrained databases is referred to as querying under constraints. Interpreting constraintsunder an open-world semantics leads to ontology-mediated querying where a database query is endowed with an ontology that adds domain knowledge and supports delivering more complete answers. Ontologies are often formulated in a description logic or as sets of (suitably restricted) tuple- and equality-generating dependencies. The latter also generalize many constraint languages that are central to querying under constraints.As ontology-mediated querying is intractable in general (in combined complexity, and often also in data complexity), substantial efforts have been invested to map out the complexity landscape in detail and in particular to separate the tractable cases from the intractableones. The same is true for querying under constraints, which is computationally less expensive but where the presence of constraints can make queries tractable that are intractable over unconstrained databases.In these endeavours, however, the focus has mostly been on single answer testing, that is, a concrete answer candidate is given as part of the input and the problem is to decide whether the candidate indeed is an answer. From a practical perspective, this setup is unrealistic because candidate answers tend to be unavailable or too numerous. Instead, the aim often is to compute answers without being given a candidate or to determine their number, the latter e.g. for statistical queries and for query optimization. Motivated by this observation, the QTEC project sets out to study answer enumeration and answer counting in ontology-mediated querying and in querying under constraints, both with and without database updates, and with a particular focus on separating the tractable cases from the intractable ones.These modes of query evaluation have never been studied in ontology-mediated querying and only rarely in querying under constraints. We study the two areas together as preliminary work shows that they are very closely related and significant synergies can be expected. The QTEC project aims to provide fine grained knowledge about classes of queries that admit tractable enumeration and counting, enabling tractable querying in applications in which the queries actually posed are tractable while, in general, the query languages used do not.

• DFG Programme: Research Grants