Answer Counting and Guarded TGDs

Answer Counting is simply the problem of counting the number of solutions to a given query. Tuple-Generating Dependencies (TGDs) are a common formalism for formulating database constraints. A TGD states that if certain facts are true, then certain other facts must be true as well. In Ontology-Mediated Querying, TGDs give rise to ontology languages and are used to derive new facts in addition to those that are present in the database. This makes it possible to obtain additional answers if the data is incomplete, or to enrich the vocabulary available for querying. In a more classical setup that can be referred to as Querying under Constraints, TGDs are used as integrity constraints on the database, i.e. a promise that if certain facts are present in the database, then certain other facts are present as well. In this talk, I will show how combining Conjunctive Queries (CQs) with TGDs changes the parameterized complexity of the Answer Count problem for CQs. In particular, I will show the relation between Answer Counting for Ontology-Mediated and Queres for Queries with Constraints and the relation between Answer Counting for Ontology-Mediated and for ``pure'' CQs. The talk is based on a joint work with Cristina Feier and Carsten Lutz.