Evaluation of XPath Queries on XML Streams with Networks of Early Nested Word Automata

Tom Sebastian 1, 2, 3
2 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Résumé : Dans cette thèse, notre défi sera de trouver la réponse à la question : comment répondre à des requêtes XPath sur des flux XML avec une faible latence, une couverture complète, une grande efficacité temporelle et un faible coût mémoire? Dans cette très, nous proposons dans un premier temps une approximation de l’algorithme de réponse au plus-tôt pour les requêtes XPath par une compilation en un automate de mots imbriqués. Nous rapproche ainsi de la latence et d’une empreinte mémoire optimales. Dans un deuxième temps, nous proposons une définition formelle de XPath 3.0. Celle-ci est obtenue en faisant correspondre XPath au nouveau langage λXP que nous introduirons. Nous montrons par la suite comment compiler des requêtes λXP en des réseaux d’automates de mots imbriqués, et développons des algorithmes de streaming pour ces derniers. Dans un troisième temps, nous allons développer un algorithme pour la projection de flux XML en fonction de la requête définie par un automate de mots imbriqués. Ainsi serons- nous en mesure de faire en sorte que notre algorithme soit temporellement très efficace. Nous avons implémenté tous nos algorithmes avec l’objectif visé d’obtenir un outil de streaming applicable dans l’industrie, et les avons testés sur les benchmarks habituels. Notre algorithme surpasse toutes les approches précédemment établies en termes d’efficacité temporelle, de couverture et de latence.
Type de document :
Thèse
Databases [cs.DB]. Universite Lille 1, 2016. English
Liste complète des métadonnées

Littérature citée [60 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01342511
Contributeur : Tom Sebastian <>
Soumis le : mercredi 6 juillet 2016 - 11:30:20
Dernière modification le : mardi 3 juillet 2018 - 11:32:09
Document(s) archivé(s) le : vendredi 7 octobre 2016 - 11:02:30

Identifiants

  • HAL Id : tel-01342511, version 1

Collections

Citation

Tom Sebastian. Evaluation of XPath Queries on XML Streams with Networks of Early Nested Word Automata. Databases [cs.DB]. Universite Lille 1, 2016. English. 〈tel-01342511〉

Partager

Métriques

Consultations de la notice

432

Téléchargements de fichiers

344