Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-09-29  07:00-07:00
TitreTitle: Counting Problems over Incomplete Databases 
RésuméIn this presentation I will talk about various counting problems that naturally arise in the context of query evaluation over incomplete databases. Incomplete databases are relational databases that can contain unknown values in the form of labeled nulls. We will assume that the domains of these unknown values are finite and, for a Boolean query $q$, we will consider the following two problems: given as input an incomplete database $D$, (a) return the number of completions of $D$ that satisfy $q$; or (b) return or the number of valuations of the nulls of $D$ yielding a completion that satisfies $q$. We will study the computational complexity of these problems when $q$ is a self-join--free conjunctive query, and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in $D$ (what is called *Codd tables*); and (2) the domain of each null is the same. Roughly speaking, we will see that counting completions is much harder than counting valuations, and that both (1) and (2) can reduce the complexity of our problems. I will also talk about the approximability of these problems and prove that, while counting valuations can efficiently be approximated, in most cases counting completions cannot. On our way, we will encounter the counting complexity classes #P, Span-P and Span-L. The presentation will be based on joint work with Marcelo Arenas and Pablo Barcelo; see https://arxiv.org/abs/1912.11064 
LieuOnline 
OrateurMikael Monet 
Emailmikael.monet@imfd.cl 
UrlMillenium Instititute for Foundational Research on Data 



Aucun document lié à cet événement.

Retour
Retour à l'index