FR 3129745 A1 20230602 FR 2112754 A 20211130 Système et procédé de stockage d’une base de données temporelle orientée graphe L'invention concerne un système de stockage d’une base de données temporelle orientée graphe, comprenant un ensemble de conteneurs associés à des fenêtres temporelles adjacentes, un conteneur contenant une séquence de modifications successives du graphe sur une fenêtre temporelle à laquelle il est associé. Au moins certains des conteneurs, appelés conteneurs de référence, contiennent également une image instantanée du graphe dans la fenêtre temporelle associée au conteneur de référence, appelée image instantanée de référence. Au moins certains autres conteneurs, appelés conteneurs deltas, contiennent une image de différence entre deux images instantanées du graphe associées respectivement au début et à la fin de la fenêtre temporelle associée au conteneur delta. Figure pour l’abrégé : Fig 3 Système et procédé de stockage d’une base de données temporelle orientée graphe Le domaine de l'invention est celui des bases de données orientées graphes. Plus précisément, l'invention concerne le stockage optimisé de telles bases de données, à des fins de réduction de l’espace de stockage et d’optimisation du temps de latence nécessaire à leur interrogation. Art antérieur Une base de données orientée graphe est une base de données orientée objet utilisant la théorie des graphes, donc avec des nœuds et des arcs, permettant de représenter et stocker les données. Les bases de données orientées graphes sont largement utilisées pour modéliser, stocker et interroger des données centrées sur les relations. En effet, elles sont particulièrement appropriées lorsqu'il s'agit d'exploiter les relations entre les données (par exemple des connaissances entre des personnes, la description de l'ensemble des pièces d'une machine industrielle et de la manière dont elles sont liées entre elles). Ces bases de données gèrent les données comme une collection de sommets et d'arêtes, de sorte que chaque arête relie une paire de sommets. Or, les sommets et les arêtes ont une ou plusieurs étiquettes (types) et peuvent avoir une liste de paires clé/valeur appelées propriétés. Les bases de données orientées graphes sont utilisées aujourd'hui dans la modélisation des réseaux sociaux. Elles sont de même utilisées dans le stockage de masse de données ou Big data. Cependant, les bases de données de graphes conventionnelles ne sont pas temporelles, dans le sens où elles n'incluent que le dernier état mis à jour du graphe. Il s'agit, en effet, d'une limitation critique pour les graphes intégrant un comportement dynamique. Prenons l'exemple d'un réseau de dispositifs IoT (pour l’anglais « Internet of Things », en français « internet des objets »). Le comportement dynamique d'un tel réseau découle du fait que les dispositifs IoT établissent des connexions temporaires avec leur environnement. Un tel cas d'utilisation peut naturellement être modélisé sous la forme d'un graphe temporel où chaque arête est associée à un intervalle de temps de validité, i.e. à un intervalle de temps pendant lequel l'arête a existé. Ainsi, le système de gestion de graphes sous-jacent doit être capable de préserver ces connexions ainsi que les métadonnées temporelles qui permettent de reconstruire l'état du graphe à tout moment. Dans ce contexte, un système de gestion de graphes temporels devrait être conçu pour stocker et interroger de tels graphes. C'est-à-dire que la conception du modèle de stockage, du langage d'interrogation, de l'évaluation des requêtes, etc. nécessite un support optimisé de la version temporelle afin de bénéficier de la caractéristique temporelle sans détériorer les performances du système. Le défi du versionnement des données est l'un des problèmes classiques de la gestion des données mais reste peu étudié dans le contexte des bases de données de graphes. L'étude de l'état de l'art sur les systèmes de gestion de graphes temporels met en évidence l'importance de l'optimisation de la technique de stockage. Dans ce contexte, deux techniques de l'état de l'art sont proposées, à savoir les approches Log et Copy. L'approche Log suivie par George, B., Kang, J. M., & Shekhar, S. (2009) dans « Spatio-temporal sensor graphs (stsg): A data model for the discovery of spatio-temporal patterns » ( Intelligent Data Analysis , 13 (3), 457-475) , et par Nowakowski, E., & Breu, R. (2018, June) dans « ChronoGraph: A Versioned TinkerPop Graph Database » ( Data Management Technologies and Applications: 6th International Conference, DATA 2017, Madrid, Spain, July 24–26, 2017, Revised Selected Papers (Vol. 814, p. 237). Springer) , consiste à stocker les mises à jour du graphe sous la forme d'une série de logs (en français, journaux) horodatés de telle sorte que tout état du graphe peut être récupéré en retrouvant tous les logs avec un horodatage relatif avant celui demandé. Une mise à jour du graphe stockée selon cette approche est par exemple du type « ajout de l’arête e i à l’instant t j ». Cette approche est notamment illustrée par . Une limitation de cette approche est que l’évaluation d’une requête à l’instant t nécessite de charger toutes les mises à jour de graphe horodatées à un instant précédent t, ce qui est consommateur de temps de calcul. L'approche de Copy consiste à matérialiser et à conserver des instantanés du graphe. Cette solution permet d'échanger de l'espace contre une récupération plus rapide de l'état du graphe et présente également la limitation de perdre les données dont les taux de changement sont plus rapides que la fréquence des instantanés. Comme discuté par Salzberg, B., & Tsotras, V. J. (1999) dans « Comparison of access methods for time-evolving data » ( ACM Computing Surveys (CSUR) , 31 (2), 158-221) , les méthodes Log et Copy représentent deux extrêmes peu pratiques pour le stockage des graphes temporels. En d'autres termes, les méthodes Log et Copy favorisent l'optimisation de l'utilisation de l'espace au détriment du temps de calcul de la requête ou vice-versa. Pour atténuer ce compromis apparent, la méthode Copy+Log est décrite par Youshan Miao, Wentao Han, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Enhong Chen, and Wenguang Chen (2015) dans « ImmortalGraph: A System for Storage and Analysis of Temporal Graphs » ( ACM Trans. Storage 11, 3, Article 14 (July 2015), 34 pages) et par Han, W., Li, K., Chen, S., & Chen, W. (2018) dans « Auxo: a temporal graph management system » ( Big Data Mining and Analytics , 2 (1), 58-71) . Cette approche est notamment illustrée par . Elle consiste à combiner les méthodes susmentionnées. L'idée principale est de matérialiser et de faire persister les états du graphe qui sont valides à certains instants, tout en conservant les mises à jour du graphe dans des fenêtres temporelles disjointes. Pour clarifier, les fenêtres temporelles sont des conteneurs physiques des mises à jour du graphe qui ont eu lieu entre deux images instantanées du graphe. En effet, cela offre l'avantage de récupérer au maximum toutes les mises à jour du graphe d'une seule fenêtre temporelle afin de répondre à une requête dont l'instant se situe dans les limites de cette fenêtre. Cependant, un inconvénient de cette approche est que le stockage des images instantanées du graphe est gourmand en espace de stockage. En effet, les images instantanées (en anglais « snapshots ») consomment de l'espace parce qu'elles matérialisent l'état de chaque sommet ou arête existant à un seul instant. Or, dans de nombreux cas d'utilisation, certaines parties du graphe sont statiques, en particulier dans les graphes de croissance où les ajouts sont plus probables que les suppressions. Dans ce cas, les sommets et les arêtes ont tendance à survivre pendant de plus longues périodes et sont donc copiés dans plusieurs instantanés. Il existe donc un besoin d'une technique optimisée de stockage de bases de données temporelles orientées graphes qui ne présente pas ces inconvénients de l’art antérieur. Notamment, il existe un besoin d’une telle technique qui permette de surmonter la limitation de l’importante surcharge de stockage induite par le stockage d’instantanés complets de graphes. L'invention répond à ce besoin en proposant un système de stockage d’une base de données temporelle orientée graphe, comprenant un ensemble de conteneurs associés à des fenêtres temporelles adjacentes, un conteneur contenant une séquence de modifications successives du graphe sur une fenêtre temporelle à laquelle il est associé. Selon l’invention, au moins certains des conteneurs, appelés conteneurs de référence, contiennent également une image instantanée du graphe dans la fenêtre temporelle associée au conteneur de référence, appelée image instantanée de référence, et au moins certains autres conteneurs, appelés conteneurs deltas, contiennent une image de différence entre deux images instantanées du graphe associées respectivement au début et à la fin de la fenêtre temporelle associée au conteneur delta. Ainsi, l'invention repose sur une approche tout à fait nouvelle et inventive du stockage de bases de données temporelles orientées graphes. En effet, l'invention propose une approche de stockage que l’on pourrait dénommer Delta-Copy+Log, qui améliore la technique de l'état de l'art Copy+Log et stocke les mises à jour de graphes dans des fenêtres temporelles disjointes. La technique de stockage selon l’invention diffère avantageusement de la technique antérieure Copy+Log, en ce qu’elle stocke des images de différence, ou deltas, représentant la différence entre les images instantanées du graphe, au lieu des images instantanées elles-mêmes. Une image de différence, ou delta, entre deux instantanés S et S', contient le nombre minimum de mises à jour de graphes qui permettent la transformation de S en S'. Autrement dit, un delta élimine les entités redondantes entre deux instantanés successifs, ce qui peut être d'un grand intérêt si l'on suppose que la topologie des graphes tend à évoluer progressivement. Un tel système de stockage contient néanmoins, outre ces deltas, un certain nombre d'instantanés qui peuvent servir de points de départ pour l'évaluation des requêtes. Ainsi, après un certain nombre de conteneurs deltas, le système de stockage mémorise un instantané complet du graphe. Un avantage majeur de cette approche innovante Delta-Copy+Log réside dans la réduction de l'espace de stockage utilisé, par rapport à la technique de pointe antérieure Copy+Log. Selon une première caractéristique de l'invention, ladite image de différence est stockée sous la forme d’un nombre minimal de modifications du graphe entre lesdites deux images instantanées. Selon une autre caractéristique, les fenêtres temporelles peuvent être de durées distinctes mais contiennent un même nombre N de mises à jour successives du graphe. On contrôle ainsi avantageusement l’espace de stockage requis pour le système. Par exemple, les fenêtres temporelles peuvent être dimensionnées pour contenir 10 6 mises à jour successives du graphe. Par mise à jour du graphe, on entend ici, et dans tout le document, une modification élémentaire du graphe, telle qu’un ajout ou une suppression d’arête entre deux nœuds, ou un ajout ou une suppression de nœud. Selon une autre caractéristique, un tel système de stockage comprend un nombre fixe M de fenêtres temporelles entre deux images instantanées de référence successives. Ce nombre M constitue un paramètre flexible du système, permettant de réaliser le compromis optimal entre l’espace de stockage requis et le temps de calcul nécessaire au traitement des requêtes d’interrogation de la base de données. Selon une caractéristique avantageuse, entre deux images instantanées de référence successives, les images de différence des M/2 premières fenêtres temporelles contiennent des modifications du graphe à apporter à une image instantanée du graphe associée au début de la fenêtre temporelle pour la transformer en une image instantanée du graphe associée à la fin de la fenêtre temporelle, et les images de différence des M/2 dernières fenêtres temporelles contiennent des modifications du graphe à apporter à une image instantanée du graphe associée à la fin de la fenêtre temporelle pour la transformer en une image instantanée du graphe associée au début de la fenêtre temporelle. Ainsi, un tel système repose sur une approche innovante de stockage et d'interrogation en avant et en arrière (en anglais « forward » et « backward ») des événements temporels. En d'autres termes, la moitié des deltas et des fenêtres de temps entre deux instantanés sont stockés, et donc interrogés, de manière prospective, tandis que l'autre moitié est gérée de manière rétrospective. Un tel choix permet avantageusement l'accélération du temps d'exécution des requêtes. Par exemple, le résultat d'une requête est calculé en avant ou en arrière selon que l'instant demandé est plus proche de celui d'un instantané précédent ou suivant, respectivement. Ainsi, les images de différence de la première moitié des conteneurs deltas dans une fenêtre temporelle représentent la différence entre un instantané et son prédécesseur alors que les images de différence de la seconde moitié des conteneurs deltas dans cette même fenêtre temporelle représentent la différence entre un instantané et son successeur. Le temps d’exécution des requêtes d’interrogation d’un tel système de stockage est ainsi avantageusement réduit de 50% environ par rapport à une méthode Delta-Copy+Log qui n’utiliserait que des fenêtres « forward ». Selon un autre aspect, une structure probabiliste de type filtre de Bloom est associée à au moins certains desdits conteneurs deltas. Une telle structure probabiliste permet de vérifier l’existence de mises à jour. Ainsi, avant de lire un conteneur delta pour en extraire des données, le filtre de Bloom associé est vérifié, pour confirmer par exemple qu’il contient des mises à jour liées à un nœud d’intérêt. Si le filtre de Bloom indique avec une certaine probabilité la présence d’une mise à jour impactant ce nœud d’intérêt (par exemple, ajout ou suppression d’une arête le liant à un nœud voisin), le conteneur delta est consulté pour en extraire les informations d’intérêt. En revanche, si le filtre de Bloom indique avec certitude l’absence d’une telle mise à jour, ce conteneur delta n’est pas lu, et on gagne en temps de calcul superflu. Cela présente l'avantage d'atténuer la surcharge de latence causée par le stockage des deltas au lieu des instantanés. L'invention concerne également un procédé de stockage d’une base de données temporelle orientée graphe, sous la forme d’un ensemble de conteneurs associés à des fenêtres temporelles adjacentes, un conteneur contenant une séquence de modifications successives du graphe sur une fenêtre temporelle à laquelle il est associé. Un tel procédé de stockage met en œuvre un stockage, dans au moins certains desdits conteneurs, appelés conteneurs de référence, d’une image instantanée du graphe dans la fenêtre temporelle associée au conteneur de référence, appelée image instantanée de référence, et un stockage, dans au moins certains autres conteneurs, appelés conteneurs deltas, d’une image de différence entre deux images instantanées du graphe associées respectivement au début et à la fin de la fenêtre temporelle associée au conteneur delta. Selon un mode de réalisation, un tel procédé de stockage comprend des étapes de stockage en mode prospectif comprenant : (i) stockage d’une image instantanée de référence du graphe ; (ii) stockage de mises à jour du graphe dans une fenêtre temporelle courante jusqu’à atteindre un nombre maximum N de mises à jour ; (iii) fermeture de la fenêtre temporelle courante et création d’une image de différence entre deux images instantanées du graphe associées respectivement au début et à la fin de la fenêtre temporelle fermée ; (iv) ouverture d’une nouvelle fenêtre temporelle courante et répétition des étapes (ii) et (iii), jusqu’au stockage de M/2 fenêtres temporelles, où M désigne un nombre maximum de fenêtres temporelles entre deux images instantanées de référence successives. Un tel procédé de stockage comprend aussi des étapes de stockage en mode rétrospectif comprenant : (i) stockage de mises à jour du graphe dans une première fenêtre temporelle jusqu’à atteindre un nombre maximum N de mises à jour ; (ii) fermeture de la première fenêtre temporelle et ouverture d’une deuxième fenêtre temporelle ; (iii) stockage de mises à jour du graphe dans la deuxième fenêtre temporelle jusqu’à atteindre un nombre maximum N de mises à jour ; (iv) création d’une image de différence entre deux images instantanées du graphe associées respectivement au début et à la fin de la première fenêtre temporelle fermée; (iv) répétition des étapes (ii) à (iv), jusqu’au stockage de M/2 fenêtres temporelles, où M désigne un nombre maximum de fenêtres temporelles entre deux images instantanées de référence successives ; (v) stockage d’une image instantanée de référence du graphe. L’invention concerne également un produit programme d'ordinateur comprenant des instructions de code de programme pour la mise en œuvre d’un procédé tel que décrit précédemment, lorsqu’il est exécuté par un processeur. L’invention vise également un support d’enregistrement lisible par un ordinateur sur lequel est enregistré un programme d’ordinateur comprenant des instructions de code de programme pour l’exécution des étapes du procédé de stockage selon l’invention tel que décrit ci-dessus. Un tel support d'enregistrement peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une clé USB ou un disque dur. D'autre part, un tel support d'enregistrement peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens, de sorte que le programme d’ordinateur qu’il contient est exécutable à distance. Le programme selon l'invention peut être en particulier téléchargé sur un réseau par exemple le réseau Internet. Alternativement, le support d'enregistrement peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé de contrôle d’affichage précité. Le procédé de stockage, le support d’enregistrement et le programme d'ordinateur correspondants précités présentent au moins les mêmes avantages que ceux conférés par le système de stockage selon la présente invention. Présentation des figures D'autres buts, caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante, donnée à titre de simple exemple illustratif, et non limitatif, en relation avec les figures, parmi lesquelles : présente sous forme schématique la technique de l’art antérieur appelée Log ; illustre sous forme schématique la technique de l’art antérieur appelée Copy+Log ; présente un schéma de principe comparatif de la technique antérieure Copy+Log, et de la technique de stockage Delta-Copy+Log selon un mode de réalisation de l’invention ; présente un exemple de base de données temporelle orientée graphe associée à une usine intelligente ; présente un exemple de stockage de la base de données de la selon la technique antérieure Copy+Log ; présente un exemple de stockage de la base de données de la selon la technique de stockage Delta-Copy+Log d’un mode de réalisation de l’invention ; illustre un exemple d’interrogation du système de stockage de la . Description détaillée de modes de réalisation de l'invention Le principe général de l'invention repose sur une nouvelle forme de stockage des bases de données temporelles orientées graphes, qui vient améliorer la technique antérieure dite Copy+Log, en réduisant substantiellement l’espace de stockage nécessaire. En effet, on propose que certaines fenêtres temporelles soient associées à des conteneurs de référence contenant, comme dans la méthode Copy+Log, une image instantanée du graphe représentatif de la base de données ; en revanche, entre deux conteneurs de référence successifs, on propose de prévoir un certain nombre de conteneurs dits deltas, qui ne contiennent que des images de différence entre deux images instantanées successives S et S’, i.e. le nombre minimum de mises à jour du graphe permettant de passer de S à S’. Ce principe général est illustré par le schéma de principe de la , dont la partie supérieure correspond à la technique antérieure Copy+Log, et dont la parte inférieure correspond à la technique de stockage revendiquée, à titre de comparaison. Comme on peut l’observer, l’axe horizontal correspond à l’axe temporel, sur lequel se succèdent M fenêtres temporelles successives et disjointes. Chaque fenêtre temporelle est associée à un conteneur physique des mises à jour du graphe qui ont eu lieu entre deux images instantanées de ce dernier. Selon la méthode Copy+Log, le système de stockage mémorise un ensemble d’images instantanées successives du graphe référencées S 0 à S 6 , ainsi que l’ensemble des N mises à jour successives du graphe permettant de passer de chaque image instantanée S i à l’image instantanée suivante S i+1 . Ainsi, le système de stockage est organisé en une succession de conteneurs physiques successifs, associés chacun à des fenêtres temporelles adjacentes, et contenant chacun une image instantanée du graphe au début de la fenêtre temporelle à laquelle il est associé, et l’ensemble des mises à jour du graphe permettant de passer de cette image instantanée à l’image instantanée du conteneur directement suivant, selon l’axe temporel. Selon un mode de réalisation de l’invention en revanche, à des fins de réduction de la consommation en espace stockage, on s’abstient de stocker une image instantanée du graphe dans chaque conteneur physique correspondant à chacune des fenêtres temporelles successives. Au contraire, certains de ces conteneurs, appelés conteneurs deltas, ne contiennent pas une image instantanée du graphe S i , mais seulement une image de différence , correspondant aux différences entre deux images instantanées du graphe au début et à la fin de la fenêtre temporelle associée au conteneur delta considéré. Ainsi, en référence à la figure 3 , l’image de différence correspond au nombre minimum de mises à jour du graphe permettant de passer de l’image instantanée S 0 à l’image instantanée S 1 , à savoir dans le cas d’espèce l’ajout d’une arête (opération illustrée en trait plein) entre deux nœuds du graphe ; l’image de différence correspond au nombre minimum de mises à jour du graphe permettant de passer de l’image instantanée S 1 à l’image instantanée S 2 , à savoir dans le cas d’espèce la suppression d’une arête (opération illustrée en traits pointillés) entre deux nœuds du graphe. En revanche, les images instantanées S 1 et S 2 n’ont pas besoin d’être mémorisées par le système de stockage. De plus, comme on l’observe sur la , certaines de ces images de différence, ou deltas, sont construites selon une approche prospective, ou « forward » FWD : ainsi, le conteneur delta contient l’ensemble des mises à jour du graphe sur une fenêtre temporelle, et une image delta, qui correspond à l’image de différence entre l’image instantanée du graphe à la fin de la fenêtre temporelle considérée, et l’image instantanée du graphe au début de cette fenêtre temporelle. L’axe des temps est parcouru de la gauche vers la droite, des instants les plus anciens vers les instants les plus récents. A l’inverse, certaines de ces images de différence, ou deltas, sont construites selon une approche rétrospective, ou « backward » BWD ; l’axe des temps est alors parcouru de la droite vers la gauche, i.e. des instants les plus récents vers les instants les plus anciens. Le conteneur delta contient alors l’ensemble des mises à jour du graphe sur une fenêtre temporelle, et une image delta, qui correspond à l’image de différence entre l’image instantanée du graphe à la fin de la fenêtre temporelle considérée, parcourue en sens chronologique inverse, et l’image instantanée du graphe au début de cette fenêtre temporelle. Par exemple, en référence à la figure 3 , l’image de différence correspond au nombre minimum de mises à jour du graphe permettant de passer de l’image instantanée S 6 à son ancêtre direct qui est l’image instantanée S 5 , à savoir dans le cas d’espèce l’ajout d’une arête (opération illustrée en trait plein) entre deux nœuds du graphe ; l’image de différence correspond au nombre minimum de mises à jour du graphe permettant de passer de l’image instantanée S 5 à son ancêtre direct qui est l’image instantanée S 4 , à savoir dans le cas d’espèce la suppression d’une arête (opération illustrée en traits pointillés) entre deux nœuds du graphe. Les images instantanées S 4 et S 5 n’ont pas besoin d’être mémorisées par le système de stockage. La reconstruction des deltas en mode prospectif est établie lorsqu’une fenêtre temporelle en avant est fermée (i.e. le nombre de mises à jour dans la fenêtre est égal à la taille limite N). Ces mises à jour sont chargées et lues par ordre chronologique croissant. Ainsi, une mise à jour qui n’est pas suivie par une autre mise à jour inverse est ajoutée à l’image delta en cours de construction. On comprend par exemple que l’inverse d’une mise à jour correspondant à l’ajout d’une arête est une mise à jour correspondant à la suppression de cette même arête, et vice versa. La reconstruction des deltas en mode rétrospectif est établie avec une stratégie similaire mais retardée jusqu’au moment de la fermeture de la fenêtre temporelle suivante. De plus, les mises à jour sont chargées par ordre chronologique décroissant puis inversées de sorte qu'un ajout en mode prospectif soit considéré comme une suppression en mode rétrospectif, et vice versa. Ainsi, dans l’ordre chronologique direct, l’état du graphe illustré par l’image instantanée S 4 est modifié par ajout d’une arête pour obtenir l’image instantanée directement suivante S 5 . Cependant, l’image de différence , qui correspond aux mises à jour du graphe dans l’ordre chronologique inverse, pour passer de l’image instantanée S 5 à son ancêtre direct S 4 , contient, à l’inverse, une indication de suppression de cette même arête. Dans l’exemple de la figure 3 , on stocke ainsi M=6 fenêtres temporelles sous forme de conteneurs physiques entre les deux images instantanées successives S 0 et S 6 mémorisées par le système de stockage. Les M/2 premiers conteneurs deltas sont stockés et interrogés selon un mode prospectif, ou « forward » ; les M/2 derniers conteneurs deltas sont stockés et interrogés selon un mode rétrospectif, ou « backward ». On notera cependant qu’il n’est pas nécessaire de stocker l’image de différence . En effet, selon la technique revendiquée, les deltas qui sont centrés entre deux images instantanées mémorisées par le système de stockage ne sont pas pertinents pour la reconstruction du résultat d’une requête d’interrogation de la base de données. Ainsi, et sont stockés en mode avant, et et sont stockés en mode arrière. Cette nouvelle méthode de stockage, que l’on peut appeler Delta-Copy+Log, trouve son applicabilité dans les systèmes de gestion de graphes temporels. En effet, elle peut être implémentée par tout système de graphes temporels, comme une technique de stockage backend, qui optimise à la fois l'espace et le temps d'exécution des requêtes. Cette nouvelle technique de stockage trouve par exemple une application avantageuse dans le domaine des chaînes logistiques, qui peuvent être modélisées comme des graphes temporels où les sommets de ce graphe représentent des produits, des usines, des véhicules d'expédition, des détaillants, etc. Des capteurs peuvent être déployés pour suivre les différentes positions des produits. Par exemple, une arête temporaire peut être créée entre le produit et son emplacement, qui n'est valable que pour l'intervalle de temps pendant lequel l'objet a été trouvé à cet endroit. Il est ainsi possible de suivre le déplacement d’un produit le long de la chaîne logistique, et identifier par exemple l’emplacement où il se trouvait au moment de la détection d’une défaillance l’affectant. Cette nouvelle technique de stockage Delta-Copy+Log peut également trouver une application intéressante dans le domaine des réseaux d’objets connectés, ou IoT (pour l’anglais « Internet of Tings »). En effet, de tels réseaux d’IoT peuvent être naturellement modélisés sous forme d’un graphe temporel. Les objets connectés établissent des connexions temporaires avec les dispositifs environnants, comme une voiture intelligente connectée à d'autres voitures, des feux de circulation, des caméras de rue, des radars, etc. La gestion de ce type de graphes permet de mieux analyser la cause des accidents en reconstruisant l'état du graphe juste avant l'accident. Dans un contexte de base de données temporelle orientée graphe comprenant par exemple un ensemble d’objets connectés (caméras, imprimantes, serrures de portes, etc.) et non connectés (bâtiments, pièces, rues, etc.), telle que la plateforme Thing'in en cours de développement par le Demandeur, une telle technique améliorée de stockage permet de mieux analyser et prévoir le comportement des systèmes sous-jacents. Enfin, une telle technique optimisée de stockage Delta-Copy+Log peut également être adoptée dans les stratégies de compression vidéo en remplaçant analogiquement les deltas du graphe par des trames vidéo. Elle peut encore être utilisée dans les bases de données de séries temporelles avec une modification simple du schéma des fenêtres temporelles, des instantanés et des deltas. On présente désormais, en relation avec les figures 4 à 7 , un exemple de cas d’usage dans un contexte d’usine intelligente. Dans ce scénario simplifié, on considère un graphe temporel modélisant les connexions dynamiques entre les composants et les employés d'une usine intelligente (connexions entre les machines, les capteurs, les produits, les sources d'énergie, les employés, etc.). Un tel graphe temporel a pour objectif de garder une trace des différentes positions d'un produit au cours du processus de fabrication. Cela peut être étendu pour révéler les causes des retards de fabrication ou des pertes de produits. Pour répondre à la question de l’identification d’une telle cause de retard de fabrication ou de perte d’un produit, il est nécessaire de conserver, et donc d'interroger, les arêtes temporaires du graphe de modélisation de l’usine intelligente, avec leurs horodatages relatifs. Toutefois, compte tenu de la taille croissante d'un tel graphe temporel, l'une des principales exigences est de pouvoir stocker ces mises à jour à l'aide d'une technique efficace en termes d'espace, sans détériorer le temps de réponse à la requête. On considère l’exemple de graphe illustré en , qui décrit l’ensemble des composants d’une usine intelligente, et leurs interactions. On observe sur ce graphe un ensemble de nœuds, comprenant des machines référencées m 1 à m 4 , un employé référencé e , des produits fabriqués référencés p 1 et p 2 , un ensemble de capteurs référencés s 1 à s 4 , et une source d’énergie référencée p . Une arête du graphe illustre la connexion existant à un instant donné entre deux nœuds du graphe : par exemple, l’arête reliant la source d’énergie p à la machine m 2 illustre le fait que la machine m 2 est alimentée en énergie par la source p , à un instant donné ; l’arête reliant le capteur s 4 à la machine m 4 illustre une connexion entre la machine m 4 et le capteur s 4 , à un instant donné. On considère la séquence suivante de mises à jour à du graphe de la : Mise à jour de graphe Description Ajout d’une arête « Connecté à » : machine m 1 et capteur s 1 Ajout d’une arête « Connecté à » : machine m 2 et capteur s 2 Ajout d’une arête « Est dans » : produit p 1 et machine m 1 Suppression de l’arête p 1 -> m 1 Ajout d’une arête « maintenance » : employé e et machine m 1 Suppression de l’arête e -> m 1 Ajout d’une arête « Alimenté par » : machine m 1 et source d’énergie p Ajout d’une arête « Est dans » : produit p 2 et machine m 2 Suppression de l’arête p 2 -> m 2 Ajout d’une arête « Est dans » : produit p 1 et machine m 2 Ajout d’une arête « Alimenté par » : machine m 2 et source d’énergie p Suppression de l’arête p 1 -> m 2 On notera que désigne une mise à jour du graphe à un instant t i (ajout/suppression d’un(e) arête/nœud). Pour comprendre les avantages de la technique de l’invention, on présente une comparaison de la technique de stockage antérieure Copy+Log en , et de la technique de stockage revendiquée delta-Copy+Log en . Sur la , cinq images instantanées successives du graphe, référencées S 0 à S 4 , sont illustrées. Ces cinq instantanés successifs du graphe sont mémorisés dans le système de stockage implémentant la méthode antérieure Copy+Log. On désigne par ω i la fenêtre temporelle séparant les images instantanées S i-1 et S i . Dans l’exemple de la , chaque fenêtre temporelle ω i est associée à un nombre N=3 de mises à jour du graphe. Ainsi, on part d’une image instantanée initiale S 0 du graphe. Une nouvelle image instantanée S 1 du graphe est mémorisée dans le système de stockage antérieur Copy+Log, quand les trois premières mises à jour à listées dans le Tableau 1 ont été effectuées. Ainsi, l’image instantanée S 1 correspond à l’image instantanée S 0 , après ajout d’une arête symbolisant la connexion de la machine m 1 et du capteur s 1 , ajout d’une arête symbolisant la connexion de la machine m 2 et du capteur s 2 et ajout d’une arête symbolisant la présence du produit p 1 dans la machine m 1 . De même, l’image instantanée S 2 correspond à l’image instantanée du graphe après que les mises à jour à du graphe ont été effectuées dans la fenêtre temporelle ; l’image instantanée S 3 correspond à l’image instantanée du graphe après que les mises à jour à du graphe ont été effectuées dans la fenêtre temporelle ; l’image instantanée S 4 correspond à l’image instantanée du graphe après que les mises à jour à du graphe ont été effectuées dans la fenêtre temporelle . Sur la en revanche, seules deux images instantanées complètes du graphe, S 0 et S 4 , sont illustrées, et donc mémorisées dans le système de stockage Delta-Copy+Log selon un mode de réalisation de l’invention. Ainsi, un premier conteneur de référence contient l’image instantanée S 0 qui donne un descriptif de l’état initial du graphe ; un second conteneur de référence contient l’image instantanée S 4 qui donne un descriptif de l’état final du graphe. Entre ces deux conteneurs de référence, on ne mémorise que des conteneurs deltas, qui ne contiennent pas d’image instantanée complète du graphe, mais seulement une image de différence, correspondant au nombre minimum de mises à jour à effectuer entre les images instantanées successives du graphe au début et à la fin de la fenêtre temporelle à laquelle il est associé. Ainsi, un premier conteneur delta, noté , mémorise la différence, ou delta, entre l’image instantanée initiale S 0 et l’image instantanée du graphe S 1 à la fin de la fenêtre temporelle . On a : = S 1 -S 0 . L’image instantanée du graphe S 1 elle-même n’est plus enregistrée dans le système de stockage, contrairement à l’exemple de la figure 5 . Ce premier conteneur delta, référencé , est donc construit selon une approche « forward », comme l’illustre la flèche orientée de gauche à droite. Un autre conteneur delta, noté , mémorise la différence, ou delta, entre l’image instantanée du graphe S 3 à la fin de la fenêtre temporelle inverse et l’image instantanée finale S 4 : on a = S 3 - S 4 . L’image instantanée du graphe S 3 elle-même n’est plus enregistrée dans le système de stockage, contrairement à l’exemple de la figure 5 . Cet autre conteneur delta, référencé , est donc construit selon une approche « backward », comme l’illustre la flèche orientée de droite à gauche. Entre ces deux images de différence et , deux autres conteneurs correspondant aux fenêtres temporelles et stockent les mises à jour du graphe qui ont eu lieu sur ces intervalles de temps, à savoir les mises à jour à pour la fenêtre temporelle directe et les mises à jour à pour la fenêtre temporelle inverse . Cependant, selon un mode de réalisation, le système de stockage ne mémorise pas l’image de différence , qui correspond : Selon une approche prospective, à l’image de différence entre l’image instantanée du graphe S 2 à la fin de la fenêtre temporelle directe et l’image instantanée du graphe S 1 au début de cette même fenêtre temporelle : = S 2 -S 1 ; Selon une approche rétrospective, à l’image de différence entre l’image instantanée du graphe S 2 à la fin de la fenêtre temporelle inverse et l’image instantanée du graphe S 3 au début de cette même fenêtre temporelle inverse : = S 2 - S 3 . En effet, on note que les images deltas qui sont temporellement centrées entre deux images instantanées ne sont pas pertinentes pour la reconstruction du résultat d’une requête d’interrogation du graphe. En pratique, le graphe de la figure 6 est construit de la façon suivante. Les mises à jour du graphe nouvellement opérées sont dirigées vers une fenêtre temporelle ouverte. Si la taille de cette fenêtre temporelle ouverte courante atteint le seuil N de nombre maximum de mises à jour dans une fenêtre, elle est alors considérée comme une fenêtre temporelle fermée et une image delta « avant » est créée. Le même processus s'applique aux fenêtres temporelles et aux deltas rétroactifs, en mode « backward ». Cependant, la création d'une image delta à la fermeture d'une fenêtre temporelle inverse est retardée jusqu'à la fermeture de la fenêtre temporelle suivante. Par exemple, la création de l’image de différence , en mode chronologique inverse, est retardée jusqu'à ce que la fenêtre temporelle inverse soit fermée (i.e. jusqu’à ce que le nombre de mises à jour de graphe sur cette fenêtre temporelle est atteint le seuil N=3, soit après réalisation des opérations à ). Enfin, si le nombre de fenêtres temporelles et de conteneurs associés créés atteint un multiple de M, une image instantanée du graphe est enregistrée dans le système de stockage. Dans l’exemple de la figure 6 , M=4. Après création et stockage des fenêtre temporelles adjacentes , , et , le système procède donc au stockage de l’image instantanée S 4 du graphe. On notera que les paramètres N et M, qui correspondent respectivement au nombre maximum de mises à jour du graphe dans une fenêtre temporelle, et au nombre de fenêtres temporelles entre deux images instantanées stockées successives, sont des paramètres flexibles qui peuvent être adaptés en fonction des besoins du système, par exemple des ressources du back-end gérant le système de stockage. Dans un exemple, N=10 6 . On présente désormais, en relation avec la , un exemple d’interrogation de la base de données temporelle orienté graphe de la . On considère la requête suivante : dans quelle machine se trouvait le produit p 2 à l’instant t 8 ? Comme indiqué précédemment, la technique selon un mode de réalisation de l’invention est avantageuse en temps d’exécution et de calcul, dans la mesure où la moitié des informations sont stockées en mode « forward », et l’autre moitié en mode « backward ». Ainsi, le résultat d'une requête est calculé en mode avant ou en mode arrière, selon que l'instant demandé est plus proche de celui d'un instantané précédent ou suivant, respectivement. En toutes circonstances, seule la moitié des fenêtres temporelles et des deltas, au maximum, doit être vérifiée afin de répondre à une seule requête. Dans le cas d’espèce, la requête portant sur la position du produit p 2 à l’instant t 8 , on détermine que la réponse sera trouvée dans la seconde moitié du graphe, et donc en mode « backward ». Au cours d’une première étape E1, on consulte donc l’image instantanée finale S 4 . Au cours d’une deuxième étape E2, on interroge le filtre de Bloom associé à l’image de différence . On rappelle qu’un filtre de Bloom est une structure de données probabiliste inventée en 1970. Lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir : avec certitude l'absence d'un élément (il ne peut pas y avoir de faux négatif) ; avec une certaine probabilité la présence d'un élément (il peut y avoir des faux positifs). La taille d'un filtre de Bloom est fixe et indépendante du nombre d'éléments contenus, ce qui en fait une structure très compacte. Il y a cependant d'autant plus de faux positifs qu'il y a d'éléments dans la structure. Le principe du filtre repose sur l’utilisation de fonctions de hachage. Lors de cette étape E2, comme aucune mise à jour associée au produit p 2 n’est détectée dans le filtre de Bloom associé à , on peut sans risque éviter de vérifier l’image de différence , et ainsi réduire le nombre de lectures sur le disque dur contenant le système de stockage. Au cours d’une troisième étape E3, on consulte donc le conteneur associé à la fenêtre temporelle inverse , pour obtenir l’information selon laquelle, à l’instant t 8 , le produit p 2 se trouvait dans la machine m 2 . Les filtres de Bloom sont avantageux en ce qu’ils ont une taille limitée, contrairement aux autres techniques d'indexation qui croissent avec le nombre de données indexées. Les filtres de Bloom représentent une bonne solution pour vérifier l'existence d'une clé dans un ensemble de clés candidates, à condition que la taille de l'ensemble soit connue. Selon la technique de stockage revendiquée, un filtre de Bloom contient au maximum N mises à jour de graphe correspondant chacune à un nœud distinct : on connaît donc a priori le nombre maximum d'éléments de données à insérer dans le filtre de Bloom. Afin de limiter l’utilisation de l’espace de stockage mémoire par les filtres de Bloom, ces derniers sont conservés en mémoire principale et on fixe le seuil d'utilisation de la mémoire comme paramètre de conception pour limiter la création de filtres de Bloom. Autrement dit, lorsque l'espace occupé par les filtres de Bloom atteint le seuil spécifié, une politique FIFO (First In First Out) est mise en œuvre pour expulser les filtres de Bloom les plus anciens (correspondant au delta le plus ancien) du cache. On présente désormais, en relation avec la , la structure matérielle d’un système de stockage selon un mode de réalisation de l’invention. Un tel système de stockage SS comprend une mémoire vive 10 (par exemple une mémoire RAM), une unité de traitement 11 équipée par exemple d'un processeur, et pilotée par un programme d'ordinateur, stocké dans une mémoire morte 12 (par exemple une mémoire ROM ou un disque dur). A l'initialisation, les instructions de code du programme d'ordinateur sont par exemple chargées dans la mémoire vive 10 avant d'être exécutées par le processeur de l'unité de traitement 11. La mémoire vive 10 contient notamment les conteneurs physiques associés aux fenêtres temporelles adjacentes successives, les images instantanées de référence, les images deltas, et les filtres de Bloom associés. Le processeur de l’unité de traitement 11 pilote le stockage des mises à jour du graphe, l’ouverture et la fermeture des fenêtres temporelles, la création des images delta et le stockage des images instantanées de référence du graphe. Le terme unité peut correspondre aussi bien à un composant logiciel qu’à un composant matériel ou un ensemble de composants matériels et logiciels, un composant logiciel correspondant lui-même à un ou plusieurs programmes ou sous-programmes d’ordinateur ou de manière plus générale à tout élément d’un programme apte à mettre en œuvre une fonction ou un ensemble de fonctions. La illustre seulement une manière particulière, parmi plusieurs possibles, de réaliser le système de stockage, afin qu’il effectue les étapes du procédé détaillé ci-dessus, en relation avec les figures 3 à 7 (dans l’un quelconque des différents modes de réalisation, ou dans une combinaison de ces modes de réalisation). En effet, ces étapes peuvent être réalisées indifféremment sur une machine de calcul reprogrammable (un ordinateur PC, un processeur DSP ou un microcontrôleur) exécutant un programme comprenant une séquence d’instructions, ou sur une machine de calcul dédiée (par exemple un ensemble de portes logiques comme un FPGA ou un ASIC, ou tout autre module matériel). Dans le cas où le système de stockage est réalisé avec une machine de calcul reprogrammable, le programme correspondant (c'est-à-dire la séquence d’instructions) pourra être stocké dans un médium de stockage amovible (tel que par exemple une disquette, un CD-ROM ou un DVD-ROM) ou non, ce médium de stockage étant lisible partiellement ou totalement par un ordinateur ou un processeur. Système de stockage d’une base de données temporelle orientée graphe, comprenant un ensemble de conteneurs associés à des fenêtres temporelles ( ) adjacentes, un conteneur contenant une séquence de modifications successives ( ) du graphe sur une fenêtre temporelle à laquelle il est associé, caractérisé en ce que au moins certains desdits conteneurs, appelés conteneurs de référence, contiennent également une image instantanée (S i ) dudit graphe dans la fenêtre temporelle associée audit conteneur de référence, appelée image instantanée de référence, et en ce que au moins certains autres conteneurs, appelés conteneurs deltas, contiennent une image de différence ( ) entre deux images instantanées dudit graphe associées respectivement au début et à la fin de la fenêtre temporelle associée audit conteneur delta. Système de stockage d’une base de données temporelle orientée graphe selon la revendication 1, caractérisé en ce que ladite image de différence est stockée sous la forme d’un nombre minimal de modifications du graphe entre lesdites deux images instantanées. Système de stockage d’une base de données temporelle orientée graphe selon la revendication 1 ou 2, caractérisé en ce que lesdites fenêtres temporelles ( ) peuvent être de durées distinctes mais contiennent un même nombre N de mises à jour successives ( ) du graphe. Système de stockage d’une base de données temporelle orientée graphe selon l'une quelconque des revendications 1 et 2, caractérisé en ce qu’ il comprend un nombre fixe M de fenêtres temporelles ( ) entre deux images instantanées de référence (S i ) successives. Système de stockage d’une base de données temporelle orientée graphe selon la revendication 3, caractérisé en ce que, entre deux images instantanées de référence successives, les images de différence des M/2 premières fenêtres temporelles contiennent des modifications du graphe à apporter à une image instantanée du graphe associée au début de la fenêtre temporelle pour la transformer en une image instantanée du graphe associée à la fin de la fenêtre temporelle, et les images de différence des M/2 dernières fenêtres temporelles contiennent des modifications du graphe à apporter à une image instantanée du graphe associée à la fin de la fenêtre temporelle pour la transformer en une image instantanée du graphe associée au début de la fenêtre temporelle. Système de stockage selon l'une quelconque des revendications 1 à 4, caractérisé en ce qu’ un filtre de Bloom est associé à au moins certains desdits conteneurs deltas. Procédé de stockage d’une base de données temporelle orientée graphe, sous la forme d’un ensemble de conteneurs associés à des fenêtres temporelles adjacentes, un conteneur contenant une séquence de modifications successives du graphe sur une fenêtre temporelle à laquelle il est associé, caractérisé en ce qu’ il met en œuvre un stockage, dans au moins certains desdits conteneurs, appelés conteneurs de référence, d’une image instantanée dudit graphe dans la fenêtre temporelle associée audit conteneur de référence, appelée image instantanée de référence, et en ce qu’ il met en œuvre un stockage, dans au moins certains autres conteneurs, appelés conteneurs deltas, d’une image de différence entre deux images instantanées dudit graphe associées respectivement au début et à la fin de la fenêtre temporelle associée audit conteneur delta. Procédé de stockage d’une base de données temporelle orientée graphe selon la revendication 7, caractérisé en ce qu’ il comprend des étapes de stockage en mode prospectif comprenant : (i) stockage d’une image instantanée de référence dudit graphe ; (ii) stockage de mises à jour dudit graphe dans une fenêtre temporelle courante jusqu’à atteindre un nombre maximum N de mises à jour ; (iii) fermeture de ladite fenêtre temporelle courante et création d’une image de différence entre deux images instantanées dudit graphe associées respectivement au début et à la fin de ladite fenêtre temporelle fermée ; (iv) ouverture d’une nouvelle fenêtre temporelle courante et répétition des étapes (ii) et (iii), jusqu’au stockage de M/2 fenêtres temporelles, où M désigne un nombre maximum de fenêtres temporelles entre deux images instantanées de référence successives. Procédé de stockage d’une base de données temporelle orientée graphe selon la revendication 7 ou 8, caractérisé en ce qu’ il comprend des étapes de stockage en mode rétrospectif comprenant : (i) stockage de mises à jour dudit graphe dans une première fenêtre temporelle jusqu’à atteindre un nombre maximum N de mises à jour ; (ii) fermeture de ladite première fenêtre temporelle et ouverture d’une deuxième fenêtre temporelle ; (iii) stockage de mises à jour dudit graphe dans ladite deuxième fenêtre temporelle jusqu’à atteindre un nombre maximum N de mises à jour ; (iv) création d’une image de différence entre deux images instantanées dudit graphe associées respectivement au début et à la fin de ladite première fenêtre temporelle fermée; (iv) répétition des étapes (ii) à (iv), jusqu’au stockage de M/2 fenêtres temporelles, où M désigne un nombre maximum de fenêtres temporelles entre deux images instantanées de référence successives ; (v) stockage d’une image instantanée de référence dudit graphe. Produit programme d'ordinateur comprenant des instructions de code de programme pour la mise en œuvre d’un procédé selon la revendication 7 à 9, lorsqu’il est exécuté par un processeur. Support d’enregistrement lisible par un ordinateur sur lequel est enregistré un programme d’ordinateur comprenant des instructions de code de programme pour l’exécution des étapes du procédé selon la revendication 7 à 9.