Answer Counting under Guarded TGDs

Tuple-generating dependencies (TGDs) are a prominent formalism for formulating database constraints. A TGD states that if certain facts are true, then certain other facts must be true as well. This can be interpreted in different ways. 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. In a more classical setup that we refer to as querying under constraints, TGDs are used as integrity constraints on the database, that is, a TGD expresses the promise that if certain facts are present in the database, then certain other facts are present as well. In this talk, I will discuss the problem of counting answers to ontology-mediated queries (OMQs) in the context of parameterized complexity theory, with the query being the parameter. I will focus on the case where the ontology is given as a set of guarded TGDs while the actual queries are (unions of) conjunctive queries ((U)CQs)and show how to, in this setting, lift a recent classification due to Dell et al. for UCQs without ontologies and constraints to the world of OMQs. This presentation is based on a joint work with Cristina Feier and Carsten Lutz, published at ICDT 2021.

Authors

• Marcin Przybyłko

Keywords

No keywords are indexed for this paper.