Astral – Algèbre

En bref

Contexte : On veut pouvoir poser une requête similaires à SQL sur des flux de données génériques.
Problème
: Les langages sont ambigus et souvant limités en expression.
Contribution
: Définir formellement tout le modèle de gestion de flux (concepts, opérateurs, etc…).
Impact
: Clarification des requêtes, propriétés d’équivalences de requêtes, optimisation structurelle de requête possible, formalisation et médiation de systèmes.

Histoire

La création de l’algèbre remonte à Janvier 2009 lors de mon master de recherche. A l’époque, j’avais fait une première étude sur la gestion de données de capteur, j’avais aussi la thèse de Levent Gürgen sur ce même domaine. J’ai découvert le petit monde des SGFD à ce moment. Le constat est simple : c’est le bazar. Beaucoup de langages, peu de modèles théorique suffisamment expressif. Le challenge que Cyril Labbé et Claudia Roncancio me donnent est celui-ci : être capable d’écrire correctement ces deux requêtes

  • Flux des capteurs du bâtiment A
  • Flux des capteurs actuellement dans le bâtiment A

En gros, si un capteur rentre dans le bâtiment après le début de la requête, dans un cas, il sera intégré au résultat, et pas dans l’autre. Sportif ! A partir de là, j’ai posé la toute première définition de l’opérateur de désignation (sélection de flux en fonction d’identifiants) et la notation permettant de figer une relation à un temps donné. C’était pas beau à voir, et pas clair, même dans ma tête.

A partir de là, j’ai continué à développer les concepts. Qu’est-ce qu’une relation ? Qu’est-ce qu’un timestamp ? Qu’est-ce qu’un flux ? Les réponses sont dures car les impacts sont forts. Un des choix fondamental dont je suis le plus content : le temps est un espace continu. Ainsi, il était impossible de dire « à chaque timestamp » comme certains de l’état de l’art l’avaient fait. Cette contrainte m’a forcé à spécifier proprement les comportements de certains opérateurs. Bref, les définitions s’enchainent et n’en finissent plus.

Le premier draft sera mon rapport de master (M2R – ASTRAL) qui réuni l’ensemble des définitions et propriétés.

Lors de mes travaux de thèse, je raffine encore et toujours les notions car je rencontre d’autres problèmes en pratique. Le premier problème sera découvert lors des expérimentations chez France Telecom. Je remarque qu’il fallait définir absolument la notion de batch car même dans la pratique la différence se voyait. (Pour info, au lieu de dire qu’on découpe le flux par n-uplet, ou par le temps, on le découpe par les envois de la source). C’en est suivi un gros chantier de restauration, car il a fallu refaire les définitions de flux et de relation, ce qui a tout fait sauter. Youpi !

Vu la grande quantité de définitions et de versions conflictuelles que j’ai pu faire au fur et à mesure. J’ai décidé de créer un wiki où toutes les définitions / propriétés / démonstrations sont réunies. N’hésitez pas à le consulter.

Par la suite, d’autres problèmes sont arrivés. Notamment, un autre clash avec différentes interprétations de la définition de fenêtre partitionnés et de produit cartésien. Cela a permit de faire un article à mon sens très utile à ACM SAC sur l’impacts des différents ordres formels dans les SGFD. L’algèbre est maintenant suffisamment mature pour traiter les requêtes sans ambiguïté. Il reste les propriétés. Plusieurs ont étés découvertes au fur et à mesure. Concernant les propriétés, ma fierté reste centrée sur le théorème général de transposition des fenêtres. Sa version linéaire a été publiée avec l’article que j’ai fait à MoBIDE 2010 (workshop ACM SIGMOD).

Mes travaux de thèse confortent le fait que l’algèbre est solide. J’arrive en effet à écrire les requêtes de toutes natures (continue, instantané, hybride), sur différents systèmes, sans ambiguïté.

Contributions majeures

Je vais essayer de détailler les points présents dans l’algèbre qui sont vraiment inédits. D’un point de vue conceptuel voilà les points majeurs.

  • Séquences de fenêtres génériques : il existe beaucoup trop de façon de faire une séquence de fenêtre. Dire « les 5 dernières minutes » a beaucoup trop d’interprétations possibles. Le formalisme standard « Range » « Slide » ne suffit pas (la preuve, il y a eu une tentative de standardisation en 2008 par les acteurs du domaine). J’ai proposé un modèle générique permettant de tout décrire. Le principe est simple : une borne inférieure, une borne supérieure, un motif de mise à jour.
  • Manipulation du dynamisme : le contenu des relations évolue au fur et à mesure du temps. Il faut être capable de maîtriser cette évolution. L’opérateur de manipulation de domaine a été défini pour changer fonctionnellement le temps de consultation de la relation. Ainsi, il est possible de fixer un contenu à un moment précis, ou le mettre à jour régulièrement, ou suivant un motif à donner. La conséquence : écriture possible des requêtes instantanées, continues et hybrides.
  • Équivalence de requête stricte : à la découverte des problèmes d’ordres, et notamment que le produit cartésien n’était plus symétrique (ouais je sais, quel choc), il nous fallait une définition d’égalité de requêtes. Le principe de dire qu’il fallait que les ordres soient égaux, a impliqué plusieurs discussion houleuses notamment lors de mon séminaire à l’INSA de Lyon.
  • Transposition et stabilité de requête : lorsque j’ai constaté que certaines définitions dépendaient du timestamp de départ T0, je me suis demandé ce qui se passerait lorsque T0 bouge. Explosion. Beaucoup de requêtes n’ont plus la même sémantique lorsque ce paramètre est mis à jour (ce que j’ai baptisé transposition). Notamment, j’ai remarqué que les requêtes sont des fois équivalentes, mais seulement à partir d’un certain moment (typiquement, le temps que les premières données arrivent). Ce phénomène s’appelle la stabilité de requête.

En conclusion, Astral c’est bon, mangez-en ! Pour approfondir, je vous laisse aller sur le wiki ou lire les publications que l’on a faite.