Answer Counting and Guarded TGDs

Speaker(s)

Marcin Przybyłko

Affiliation

University of Bremen

Date

Dec. 22, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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.

---