Graphes attribués

Le modèle de données des "graphes à propriétés" ou "graphes attribués" a émergé depuis le début des années 2000 comme un dénominateur commun de différents modèles de bases de données orientées graphes^[1]. Il peut être défini informellement comme suit :

• En termes informatiques, un graphe attribué est une structure de données représentant des entités associées par des relations orientées, où les nœuds et les relations peuvent tous deux avoir plusieurs attributs/propriétés
• En termes de théorie des graphes, un graphe attribué est un multigraphe orienté, dont les sommets/noeuds représentent les entités de la structure de données correspondante
• Les propriétés prennent la forme de paires "clé-valeur", telles qu'utilisées par exemple en JSON. Les clés sont définies par des chaînes de caractères et les valeurs peuvent être numériques, ou également des chaînes de caractères. Ces propriétés entrent dans le cadre de la notion d'attribut usuelle en informatique, c'est pourquoi l'appellation de "graphe attribué" est pertinente. Contrairement aux graphes RDF, les propriétés ne sont pas des arcs du graphe. C'est la raison pour laquelle il est préférable de parler de graphe à propriétés plutôt que de graphes de propriétés pour traduire l'expression correspondante, usuelle (et ambiguë) en anglais :"property graph"^[1].
• Les relations sont des arcs du graphe, qui ont obligatoirement un identifiant, un nœud de départ et un nœud de fin, et facultativement un ou plusieurs attributs/propriétés au sens précédent

Dans une définition courante^[2],[3], un graphe attribué ou graphe à propriétés est défini par un septuplet (N, A, K, V, α, ${\displaystyle \kappa }$, π), où

• N est l'ensemble des nœuds/sommets du graphe
• A est l'ensemble des arcs (arêtes orientées) du graphe
• K est un ensemble dénombrable de clés définissant la nature des attributs/propriétés
• V est un ensemble de valeurs associées à ces clés pour en faire des attributs/propriétés complets
• α est une application (fonction totale) de A vers N×N définissant les arcs, où, pour a ∈ A, α(a)=(n,v) avec u, v ∈ N, signifie que a est l'arc du graphe ayant le nœud u pour origine et le nœud v pour destination
• ${\displaystyle \kappa }$ est une relation de (A∪N) vers K (définie par un sous-ensemble de (A∪N)×K), associant zéro, une ou plusieurs clés à chacun des arcs et nœuds du graphe
• π est une fonction partielle de ${\displaystyle \kappa }$ vers V qui définit des propriétés/attributs complets en associant des valeurs à des clés pour chacun des nœuds et les arcs qui en comportent. Si u ∈ N, a ∈ A et k ∈ K, alors π (u,k) (respectivement π (a,k)) est la valeur associée à la clé d'attribut k pour le nœud u, (respectivement l'arc a), si elle est y est définie.

Une notion très utilisée dans des implémentations courantes de bases de données graphes, et reprise dans certaines définitions formelles des graphes attribués^[3], est celle de label (étiquette), qui peut être associé aux nœuds et aux arcs du graphe, en plus des attributs. Cette notion avait été introduite à l'origine à destination des informaticiens utilisateurs de bases de données graphes, pour faciliter l'importation de jeux de données depuis des bases de données relationnelles, ou leur conversion depuis des modèles entité-relation. Le label permet d'associer un même identifiant (celui de la table relationnelle, ou de l'entité ER) à tous les nœuds de graphe qui correspondraient aux différentes rangées de cette table relationnelle, ou aux instances concrètes d'une même entité/classe générique. De par la définition formelle ci-dessus, il n'est pas nécessaire de les définir séparément puisque ces labels peuvent être vus comme des attributs particuliers, définis seulement par une clé, sans valeur associée (c'est pourquoi π est définie comme fonction partielle et non comme application). La définition de base devient ainsi beaucoup plus claire, plus simple, et satisfait à un principe de parcimonie. Les labels peuvent également être définis par l'intermédiaire de graphes de types.

Les graphes attribués présentent l’intérêt considérable d'apporter une généralisation commune (un concept hyperonyme) pour plusieurs modèles très importants en théorie des graphes, et très utilisés dans l'algorithmique classique des graphes.

• Les graphes étiquetés associent des étiquettes à chaque sommet et/ou arc. Ces étiquettes correspondraient à des attributs constitués seulement d'une clé, sans valeur associé, comme la définition ci-dessus le permet. Cette clé est prise dans un ensemble énumérable (typiquement une chaîne de caractères, ou un entier).
  • Les graphes colorés, tels qu'utilisés dans les problèmes classiques de coloration de graphes, sont des cas particuliers de graphes étiquetés, dont les étiquettes sont définies sur un ensemble fini de couleurs.
• Les graphes pondérés (ou graphes valués) associent une valeur numérique continue à chaque arc/arête, et le cas échéant aux sommets. Ces poids/valuations correspondraient aux différentes valeurs d'attributs associés à la même clé. Par exemple pour un modèle de réseau routier, on peut avoir un ensemble de valuations correspondant aux capacités (débits en nombre de véhicules par unité de temps), et un autre représentant les distances, ces deux valuations étant associées à chaque segment de route représenté par une arête du graphe, et distinguées par deux clés différentes.
  • Les réseaux de flot sont des graphes pondérés dont les poids sont interprétés comme des capacités. Ils sont utilisés dans toutes sortes de modèles très classiques de réseaux de transport, pour des algorithmes comme les calculs de flot maximum.
  • Les problèmes de plus court chemin sont résolus par des algorithmes très classiques (comme l'algorithme de Dijkstra) opérant sur des graphes pondérés pour lesquels les poids correspondent à des distances, réelles ou virtuelles.

Les graphes de connaissance, habituellement représentés sous la forme de graphes RDF, sont en fait des graphes étiquetés hybrides, dont les étiquettes de nœuds correspondent à des identifiants d'instance (IRI) ou des littéraux, et les étiquettes d'arcs définissent des types (de prédicats). Ils ont aujourd'hui acquis une visibilité qui tend à occulter l'acquis bien plus ancien des modèles basés-graphe tels qu'utilisés pour modéliser directement des systèmes de toute nature^[4]. Les graphes attribués sont, par leur adaptabilité et leur généralité, les plus adaptés à ce type de modélisation, où les graphes qu'on peut appeler cyber-physiques ne capturent pas seulement de l'information plus ou moins structurée à propos d'un système physique, comme ce serait le cas avec un graphe de connaissance, mais servent d'abord à représenter directement la structure d'un système physique, qui se trouve plus ou moins reproduite dans la structure de connectivité du graphe. Par contraste, un graphe RDF mélangerait ces relations structurelles avec les propriétés attachées, et les informations sur les catégories/classes avec celles portant sur les instance/individus, noyant la structure L'expressivité des graphes attribués, qui est du niveau de la logique d'ordre supérieur, est également très au dessus de celle des graphes RDF, qui est limitée à la logique du premier ordre. Les propriétés de relations, qui sont au cœur du modèle des graphes attribués, nécessitent ainsi un processus de réification très lourd pour être exprimées en RDF.

Le modèle de données NGSI-LD spécifié par l'ETSI a été la première tentative de normaliser les graphes de propriétés dans le cadre d'un organisme de normalisation de jure. Par rapport au modèle de base défini ici, le méta-modèle NGSI-LD ajoute une définition formelle des catégories de base (entité, relation, propriété) sur la base des standards du web sémantique (OWL, RDFS, RDF), qui permet de convertir en datasets RDF toutes les données représentées en NGSI-LD, par l'intermédiaire d'une sérialisation en JSON-LD. Les entités, relations et propriétés NGSI-LD sont définies par référence à des types qui peuvent eux-mêmes être définis par référence à des ontologies, des thesaurus, des taxonomies ou des vocabulaires de microdonnées connus, aux fins d'assurer l'interopérabilité sémantique des informations correspondantes.

Le groupe de normalisation ISO-IEC JTC1 SC32/ WG3 de l'ISO, qui avait établi le standard SQL, est en cours de spécification d'un nouveau langage de requête adapté aux bases de données orientées graphes, GQL (Graph Query Language). Ce standard inclura la spécification d'un modèle de données de graphes à propriétés, qui devrait inclure le modèle de base décrit ici, en ajoutant probablement des notions de labels, de types, et de schémas.

Les bases de données orientées graphes mettent en avant, par rapport aux bases de données relationnelles, le fait qu'elles ne nécessitent pas la définition préalable d'un schéma pour commencer à peupler (remplir) la base. Ceci est adapté à des environnements où l'on est dans une hypothèse de monde ouvert, comme la description de systèmes complexes et de systèmes de systèmes, à croissance "organique" et/ou non maitrisés par un seul acteur. Cependant, même dans de tels environnements, on peut avoir besoin de contraindre la représentation de certaines informations rentrés dans la base d'un manière qui se rapproche d'un schéma de base de données traditionnelle, tout en gardant l'ouverture pour l'addition de données ou configurations "non-prévues". Par exemple la description d'une ville intelligente relève de l'hypothèse de monde ouvert et sera décrite par le niveau supérieur d'une base de données graphe, sans schéma. Certains sous-systèmes techniques de cette ville restent cependant des systèmes traditionnels gérés par un seul acteur qui peut imposer une structuration plus forte de l'information, telle que représentée par un schéma.

Les notions de "graphe de types" et de schémas de graphes^[2],[5] permettent de répondre à ce besoin, les types jouant un rôle similaire à celui des labels dans les bases de données graphes classiques, mais avec la possibilité de définir des relations entre ces types et de les contraindre par des propriétés. Le graphe de types est lui même un graphe attribué, lié par une relation d'homomorphisme de graphes avec les graphes d'instances qui utilisent les types qu'il définit, en jouant un rôle similaire à celui d'un schéma dans un langage de définition de données.

Les ontologies, thesaurus ou taxonomies utilisées pour référencer les types NGSI-LD, sont également définies par des graphes, mais, contrairement aux graphes de type, ce sont des graphes RDF plutôt que des graphes attribués, et ils adressent en principe des domaines d'utilisation plus larges que ceux d'un schéma de bases de données. L'utilisation complémentaire, possible avec les types NGSI-LD, de graphes de types et de référencements ontologiques, permet de répondre aux besoins de structuration forte des données tout en assurant leur interopérabilité sémantique

• Portail de l'informatique théorique
• Portail des mathématiques