Thèse de Momar Sakho

Requêtes logiques sur les hyperflux

Les hyperflux sont des collections de flux de données avec références. Sachant qu’ils permettent la réception de données en parallèle plutôt que de manière purement séquentielle, l’on peut espérer que des données structurées transmises par leur biais puissent être traitées avec une latence moindre qu’avec un flux. Nous proposons ainsi de développer des algorithmes d’évaluation de requêtes logiques sur les hyperflux de données. Pour ce faire, nous nous intéressons à la faisabilité théorique et pratique d’un algorithme de décision du problème de certitude d’une réponse (CQA) sur les hyperflux. Nous étudions la complexité du CQA sur les hyperflux. Nous montrons d’abord que le CQA est intimement lié à des problèmes de correspondance de motifs dans les langages réguliers, et donc aux problèmes d’habitation des transitions d’automates de mots et d’arbres. Cela nous permet d’établir une classification de la complexité du CQA pour des classes d’automates et d’hyperflux variées. Nous obtenons des résultats en temps polynomial pour les hyperflux linéaires sans compression et les requêtes définies par des automates déterministes pour mots imbriqués. Pour le cas général, la complexité atteint ExpTime. Nous développons ensuite un algorithme efficace pour l’approximation du CQA sur les hyperflux. Cet algorithme a une grande couverture, du fait qu’il s’applique à des hyperflux et des classes d’automates arbitraires, et s’exécute en temps polynomial. Cependant, il ne détecte pas toujours les réponses certaines avec une latence minimale. La troisième contribution est un algorithme pour le CQA sur les flux, qui s’exécute en temps polynomial dans le cas de requêtes booléennes. Cet algorithme est aussi efficace en pratique pour le cas monadique, à l’inverse de toutes les précédentes propositions. Nous le montrons expérimentalement en appliquant l’algorithme aux requêtes navigationnelles XPath habituellement prises pour référence, avec lesquelles toutes les approches précédentes de CQA sans approximation ont échoué. L’utilisation d’automates spéciaux pour les forêts a permis la mise en place dudit algorithme.

Jury

M. Joachim NIEHREN Université de Lille Directeur de thèse M. Sebastian MANETH Universität Bremen Rapporteur M. Sylvain SCHMITZ Université de Paris Rapporteur Mme Iovka BONEVA Université de Lille Co-directrice de thèse M. Olivier GAUWIN Université de Bordeaux Examinateur M. Mathieu GIRAUD Université de Lille Examinateur

Thèse de l'équipe LINKS soutenue le 24/07/2020