Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Doctoral studies

Thesis of

Olivier Gauwin

Monday 28 September 2009
Bâtiment des thèses - Université de Lille1

Flux XML, Requêtes XPath et Automates

Jury :
Joachim Niehren, Directeur de recherche, INRIA Lille, directeur de thèse
Sophie Tison, Professeur, Université de Lille 1, directrice de thèse
Michael Benedikt, Professeur, Oxford University, rapporteur
Helmut Seidl, Professeur, Technische Universität München, rapporteur
Hubert Comon-Lundh, Professeur, ENS Cachan, examinateur
Arnaud Durand, Professeur, Université Denis Diderot (Paris 7), examinateur
Sebastian Maneth, Chargé de recherche, NICTA, examinateur

XML est devenu le format standard pour l'échange de données. L'échange de données en flux (streaming) est fréquemment utilisé lors de l'envoi de données conséquentes par le réseau. Ainsi le transfert par flux est adéquat pour de nombreux traitements XML. Dans cette thèse, nous étudions des algorithmes d'évaluation de requêtes sur des flux XML. Notre objectif est de gérer efficacement la mémoire, afin de pouvoir évaluer des requêtes sur des données volumineuses, tout en utilisant peu de mémoire. Nous étudions les requêtes définies par des automates déterministes ou par des fragments du standard W3C XPath.
Nous introduisons tout d'abord une classe d'automates définissant des requêtes efficacement evaluables en flux. Nous mesurons une telle adéquation d'un langage de requêtes à une évaluation en flux via un nouveau modèle de machines, appelées streaming random access machines, et via une mesure du nombre de candidats simultanément actifs, appelée concurrence. Nous montrons également qu'il peut être décidé en temps polynomial si la concurrence d'une requête définie par un automate de cette classe est bornée.
Concernant le standard W3C XPath, nous montrons que même de petits fragments syntaxiques ne sont pas adaptés à une évaluation en flux. Les difficultés proviennent du non-déterminisme de ce langage, ainsi que du nombre de conjonctions et de disjonctions. Nous définissons des fragments de XPath qui évitent ces problèmes, et prouvons qu'ils sont adaptés à une évaluation en flux.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster