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 traitementd'événements complexes et du traitement de flux Xml. L'efficacité des algorithmesde réponse à ces requêtes est cruciale en pratique, malgré la complexité théoriqueinhérente du problème algorithmique sous-jacent, qui exclut toute solution à la foispleinement générale et efficace.Nous réexaminons le problème de la réponse au plus tôt aux requêtes régulièressur 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èresXPath sur des flux XML avec la latence la plus faible possible. Les réponses auxrequê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 pourles automates à mots imbriqués déterministes est en temps polynomial. Mal-heureusement, leur algorithme de réponse n'était pas suffisament performant enpratique 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, letemps de traitement par événement du flux était trop élevé, et aucune projectiond'événements non pertinents n'était disponible. Par conséquent, les meilleurs outilsactuels pour évaluer les requêtes régulières XPath sur des flux XML - obtenus parSebastian et al. (2015) - reposent sur une approximation des réponses au plus tôtqui é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èresXPath 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èled'automate plus récent de Sakho et al. (2021) combine de manière naturelle lesautomates à états finis déterministes pour les mots et les arbres. Nous renforçonsnotre algorithme avec une projection complète de sous-haies afin de projeter aumaximum des sous-haies non pertinentes. Nous montrons comment obtenir depetits dShas pour des requêtes régulières XPath extraites de programmes XSLTet 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éfiniespar dSha avec une meilleure complexité dans le pire des cas, et introduisons lespremiers 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 avecles dShas compétitive en termes d'efficacité temporelle par rapport aux meilleursoutils 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 plustôt. Nous croyons que les progrès algorithmiques réalisés sur l'approche au plus tôtsur les flux de données dans la présente thèse permettront finalement d'avoir cettemême approche sur les hyperflux, comme proposé par Sakho et al. (2021).