Thesis of Antonio Al Serhali

Evaluation au plus tôt de requêtes régulières avec projection de sous-haies complète

Les requêtes logiques sont au cœur des bases de données graphes, du traitement d’événements complexes et du traitement de flux Xml. L’efficacité des algorithmes de réponse à ces requêtes est cruciale en pratique, malgré la complexité théorique inhérente du problème algorithmique sous-jacent, qui exclut toute solution à la fois pleinement générale et efficace. Nous réexaminons le problème de la réponse au plus tôt aux requêtes régulières sur des séquences d’arbres de données, souvent appelées haies. Ce problème a été étudié pour la première fois par Gauwin et al. en 2011. Leur motivation initiale, qui demeure notre principale application, est de répondre aux requêtes régulières XPath sur des flux XML avec la latence la plus faible possible. Les réponses aux requêtes doivent être produites immédiatement dès qu’elles deviennent certaines, indépendamment de la continuation du flux. Gauwin et al. (2011) ont montré que la réponse au plus tôt aux requêtes pour les automates à mots imbriqués déterministes est en temps polynomial. Mal- heureusement, leur algorithme de réponse n’était pas suffisamment performant en pratique lorsqu’il était appliqué aux requêtes régulières XPath sur des flux XML : les automates obtenus étaient énormes même pour de petites requêtes XPath, le temps de traitement par événement du flux était trop élevé, et aucune projection d’événements non pertinents n’était disponible. Par conséquent, les meilleurs outils actuels pour évaluer les requêtes régulières XPath sur des flux XML – obtenus par Sebastian et al. (2015) – reposent sur une approximation des réponses au plus tôt qui évite la nécessité de déterminiser des automates à mots imbriqués. Dans cette thèse, nous montrons que la réponse au plus tôt aux requêtes régulières XPath est réalisable en pratique. Pour ce faire, nous développons un nouvel algo- rithme pour les automates de haies déterministes pas-à-pas (dShas). Ce modèle d’automate plus récent de Sakho et al. (2021) combine de manière naturelle les automates à états finis déterministes pour les mots et les arbres. Nous renforçons notre algorithme avec une projection complète de sous-haies afin de projeter au maximum des sous-haies non pertinentes. Nous montrons comment obtenir de petits dShas pour des requêtes régulières XPath extraites de programmes XSLT et XQuery pratiques par Lick et Schmitz, par déterminisation guidée par schéma, développons un algorithme de streaming pour des requêtes monadiques définies par dSha avec une meilleure complexité dans le pire des cas, et introduisons les premiers algorithmes complets de projection de sous-haies pour les dShas. Il s’avère que la projection complète de sous-haies rend la réponse au plus tôt avec les dShas compétitive en termes d’efficacité temporelle par rapport aux meilleurs outils de streaming existants pour les requêtes régulières XPath générales, tout en étant plus efficace en mémoire dans les cas où ces outils ne fonctionnent pas au plus tôt. Nous croyons que les progrès algorithmiques réalisés sur l’approche au plus tôt sur les flux de données dans la présente thèse permettront finalement d’avoir cette même approche sur les hyperflux, comme proposé par Sakho et al. (2021).

Jury

M. Joachim NIEHREN Université de Lille Directeur de thèse, Mme Sophie TISON Université de Lille Examinatrice, M. Sebastian MANETH University of Bremen Rapporteur, M. Sylvain SCHMITZ Université Paris Cité Rapporteur.

Thesis of the team LINKS defended on 12/12/2024