Télécom ParisTech

Actualité

Illustration de l'actualité : Soutenance de doctorat d'Antoine Amarilli : Tirer parti de la structure des données incertaines

Soutenance de doctorat d'Antoine Amarilli : Tirer parti de la structure des données incertaines

lundi
14
mars
2016

PhD Comics : I'm defending my thesis, Mom !

Jury

  • Serge Abiteboul, Inria Saclay (examinateur)
  • Michael Benedikt, University of Oxford (examinateur)
  • Pierre Bourhis, CNRS CRIStAL (invité)
  • Martin Grohe, RWTH Aachen University (rapporteur)
  • Marie-Laure Mugnier, Université de Montpellier (examinatrice)
  • Jacques Sakarovitch, CNRS, Télécom ParisTech (examinateur)
  • Pierre Senellart, Télécom ParisTech (examinateur)
  • Cristina Sirangelo, Université Paris Diderot (examinatrice)
  • Dan Suciu, University of Washington (rapporteur)

Résumé

La gestion des données incertaines peut devenir infaisable, dans le cas des bases de données probabilistes, ou même indécidable, dans le cas du raisonnement en monde ouvert sous des contraintes logiques. Cette thèse étudie comment pallier ces problèmes en limitant la structure des données incertaines et des règles.

La première contribution présentée s'intéresse aux conditions qui permettent d'assurer la faisabilité de l'évaluation de requêtes et du calcul de lignage sur les instances relationnelles probabilistes. Nous
montrons que ces tâches sont faisables, pour diverses représentations de la provenance et des probabilités, quand la largeur d'arbre des instances est bornée. Réciproquement, sous des hypothèses faibles, nous pouvons montrer leur infaisabilité pour toute autre condition imposée sur les instances.

La seconde contribution concerne l'évaluation de requêtes sur des données incomplètes et sous des contraintes logiques, sous l'hypothèse de finitude généralement supposée en théorie des bases de données. Nous montrons la décidabilité de cette tâche pour les dépendances d'inclusion unaires et les dépendances fonctionnelles. Ceci constitue le premier résultat positif, sous l'hypothèse de la finitude, pour la réponse aux requêtes en monde ouvert avec un langage d'arité arbitraire qui propose à la fois des contraintes d'intégrité référentielle et des contraintes de cardinalité.