Extensions du traitement par flux – EXSTREAM

Notre approche est basée sur les méthodes formelles, en particulier la théorie des langages. Ces méthodes ont permis de nombreux résultats, y compris algorithmiques. Notre objectif est de combiner cette approche avec des contraintes de type «streaming« sur les documents, à savoir : traitement rapide de chaque événement, et faible consommation mémoire. Pour y parvenir, certains résultats de théorie des langages doivent être établis ou étendus.

De nouveau algorithmes ont été établis pour chaque type de traitement considéré. Pour la validation de documents XML, nous avons mis au point un algorithme permettant de décider quels schémas (comme les DTD) sont réparables en streaming. Pour les requêtes sur des documents XML, nous avons proposé un algorithme rapide, répondant presque toujours au plus tôt (minimisant ainsi la mémoire). Pour la transformation de documents, nous avons amélioré des algorithmes décidant si une transformation (définie par un transducteur) pouvait se faire en streaming à mémoire bornée.

Une retombée inattendue du projet est une avancée importante en théorie de langages, dans les liens entre logique et automates. Nous avons proposé un algorithme permettant de décider si un langage régulier (décrit par exemple par un automate) peut être caractérisé par une formule logique du premier ordre avec 3 alternances de quantificateurs.

Nous avons présenté ces résultats dans divers conférences, et publié quelques articles de journaux.

La tendance actuelle dans le domaine des données est de considérer ces données comme éphémères plutôt que stockées, et donc de les traiter à la volée, plutôt qu'à la demande. Ainsi de nombreuses applications récentes produisent des données sous la forme de flux de données continus, et de longueur arbitraire (par exemple, les messages d'information (logs), les messages de discussion, les données en provenance de capteurs, les flux financiers, les données génomiques, etc.). Cette tendance est particulièrement prononcée dans les communautés liées à l'informatique dans les nuages (cloud computing) et à la gestion de grandes masses de données (big data), qui cherchent des solutions innovantes pour faire face au nombre croissant de flux à traiter et à leur taille. Les caractéristiques des problèmes informatiques liés à la gestion des flux sont (i) la forme sérialisée des données, c'est-à-dire leur accès sous la forme d'une suite d'évènements, et (ii) la contrainte forte sur les ressources en temps et en espace (par exemple, obtenir une borne sur la consommation mémoire, et un temps constant par évènement traité).

Dans le but d'obtenir des traitements par flux efficaces, de nouveaux standards, algorithmes et langages sont recherchés, et de nouvelles questions émergent sur le plan théorique. L'objectif de ce projet de recherche et de développer de nouveaux modèles de calcul et des outils mathématiques rigoureux pour compléter l'état de l'art dans ce domaine. Les questions abordées par ce projet concernent ainsi plusieurs domaines de l'informatique, allant des bases de données à la théorie de la complexité, de la logique aux automates, de la combinatoire à l'algèbre. Elles comprennent un certain nombre de problèmes ouverts difficiles.

Plusieurs types de tâches réalisées en flux seront considérés, principalement liées à XML (requêtes XPath, transformations XSL, validation par rapport à des schémas) et à la recherche de motif. Ces tâches sont représentées formellement par des familles de problèmes paramétrées par des requêtes, contraintes, motifs, etc., et reçoivent en entrée des flux d'évènements.

Plus précisément, le programme scientifique s'organise autour de deux tâches principales. La première consiste à développer des algorithmes pour traiter les flux de manière optimale. Ceci inclut des algorithmes pour énumérer efficacement les réponses d'une requêtes posées sur un flux,
des algorithmes pour transformer des flux de données, des procédures de décision sur la réalisabilité à mémoire constante d'une requête ou d'une transformation, la synthèse de validateurs de flux à mémoire bornée, des solutions pour le problème de recherche de motif paramétré sur des flux. La seconde tâche vise à déterminer les paramètres des problèmes concernés par ce projet, permettant un traitement par flux efficace. Une étape intermédiaire est l'étude de formalismes basés sur les automates et des hiérarchies logiques qui permettront la définition formelle de classes de paramètres (par exemple des requêtes XPath). Une attention particulière sera portée à la capacité de traiter les égalités entre attributs provenant d'un domaine infini (test d'égalité sur des données). Nous comparerons ensuite les formalismses en terme d'expressivité et de concision. Enfin nous espérons caractériser de manière effective certains niveaux des hiérarchies que nous définirons.

Les questions abordées dans ce programme de recherche sont ambitieuses par plusieurs aspects. D'une part, elles peuvent être considérées comme
des variantes de problèmes de vérification et de théorie des langages. D'autre part, elles comprennent des contraintes algorithmiques spécifiques
au traitement en flux. La combinaison de ces deux aspects produit des problèmes très complexes, qui requièrent de nouveaux modèles mathématiques pour être résolus.