Voir la source de 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  [[Base de données orientée graphe|bases de données orientées graphes]]<ref name=":2" />. Il peut être défini informellement comme suit :
* En termes [[Informatique|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]] [[Graphe orienté|orienté]], dont les [[Sommet (théorie des graphes)|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 (informatique)|attribut]] usuelle en informatique, c'est pourquoi l'appellation de "graphe attribué" est pertinente. Contrairement aux graphes [[Resource Description Framework|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"<ref name=":2">{{Article |langue=en |auteur1=Renzo Angles |titre=A comparison of current graph database models |périodique=IEEE International Conference on Data Engineering |date=2012/4/1 |lire en ligne=https://www.researchgate.net/profile/Renzo-Angles/publication/261076480_A_Comparison_of_Current_Graph_Database_Models/links/54f05b180cf25f74d72609c3/A-Comparison-of-Current-Graph-Database-Models.pdf }}</ref>.
* Les relations sont des arcs<!-- on parle souvent (incorrectement) d'arêtes, mais une arête (edge en anglais) est non-orientée --> 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

== Définition formelle ==
Dans une définition courante<ref name=":1">{{Article |langue=en |auteur1=Angela Bonifati, Peter Furniss, Alastair Green,Russ Harmer, Eugenia Oshurko, Hannes Voigt |titre=Schema Validation and Evolution for Graph Databases |périodique=ER 2019 - 38th International Conference on ConceptualModeling |lieu=Salvador, Brazil |date=November 2019 |doi=10.1007/978-3-030-33223-5_37 |lire en ligne=https://hal.archives-ouvertes.fr/hal-02138771/document |pages=448-456 }}</ref>{{,}}<ref name=":0">{{Article |langue=english |auteur1=Claudio Gutierrez, Jan Hidders, Peter Wood |titre=Graph Data Models |périodique=Encyclopedia of Big data Technologies |date=2018 |lire en ligne=https://doi.org/10.1007/978-3-319-63962-8_81-1 }}</ref>, un graphe attribué ou graphe à propriétés est défini par un [[N-uplet|septuplet]] (N, A, K, V, α, <math>\kappa</math>, π), où

* N est l'ensemble des ''nœuds''/[[Sommet (théorie des graphes)|sommets]] du graphe
* A est l'ensemble des ''arcs'' ([[Arête (théorie des graphes)|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 (mathématiques)|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
*<math>\kappa</math> 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 (mathématiques)|fonction]] ''partielle'' de <math>\kappa</math>  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 [https://neo4j.com/docs/getting-started/current/graphdb-concepts/#graphdb-labels des implémentations courantes de bases de données graphes], et reprise dans certaines définitions formelles des graphes attribués<ref name=":0" />, 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 [[Base de données relationnelle|bases de données relationnelles]], ou leur conversion depuis des modèles [[Modèle entité-association|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 [[Instance (programmation)|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 [[Rasoir d'Ockham|parcimonie]]. Les labels peuvent également être définis par l'intermédiaire de [[#Graphes de types et schémas|graphes de types]].

== Relations avec d'autres modèles ==

=== Théorie des graphes et algorithmique classique des graphes ===
Les graphes attribués présentent l’intérêt considérable d'apporter une généralisation commune (un concept [[hyperonymie|hyperonyme]]) pour plusieurs modèles très importants en [[théorie des graphes]], et très utilisés dans l'[[Liste des algorithmes de la théorie des graphes|algorithmique classique des graphes.]]
* Les [[Lexique de la théorie des graphes#Étiquetage|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 [[Récursivement énumérable|é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 graphe]]s, sont des cas particuliers de graphes étiquetés, dont les étiquettes sont définies sur un ensemble ''fini'' de couleurs.
*Les [[:en:Glossary of graph theory#weighted graph|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éseau de flot|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 [[Problème de flot maximum|flot maximum]].
**Les [[Problème de plus court chemin|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.

=== Graphes de connaissance et graphes RDF ===
Les [[Knowledge graph|graphes de connaissance]], habituellement représentés sous la forme de graphes [[Resource Description Framework|RDF]], sont en fait des graphes étiquetés hybrides, dont les étiquettes de nœuds correspondent à des identifiants d'instance ([[International Resource Identifier|IRI]]) ou des [[Littéral (programmation)|littéraux]], et les étiquettes d'arcs définissent des types (de [[Prédicat (logique mathématique)|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<ref>{{Article |langue=en |auteur1=Gilles Privat |auteur2=Abdullah Abbas |titre=Cyber-Physical Graphs vs.RDF graphs |périodique=W3C Workshop on Web Standardization for Graph Data |lieu=Berlin |date=March 2019 |lire en ligne=https://www.w3.org/Data/events/data-ws-2019/assets/position/Gilles%20Privat.html }}</ref>. 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 [[Système cyber-physique|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'[[:en: Expressive power (computer science)|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.

== Normalisation ==

=== [[NGSI-LD]] ===
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]] ([[Web Ontology Language|OWL]], [[RDF Schema|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 [[Ontologie (informatique)|ontologies]], des [[Thésaurus documentaire|thesaurus]], des [[Taxonomie (homonymie)#Informatique|taxonomies]] ou des vocabulaires de [[microdonnée]]s connus, aux fins d'assurer l'[[Interopérabilité en informatique#L’interopérabilité sémantique|interopérabilité sémantique]] des informations correspondantes.

=== [[:en:Graph Query Language|GQL]] ===
Le groupe de normalisation [[Joint Technical Committee 1|ISO-IEC JTC1]] SC32/ WG3 de l'[[Organisation internationale de normalisation|ISO]], qui avait établi le standard [[Structured Query Language|SQL]], est en cours de spécification d'un nouveau [[langage de requête]] adapté aux bases de données orientées graphes, [[:en:Graph Query Language|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 [[:en:Database schema|schémas]].

== Graphes de types et 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 [[:en:Database schema|schéma]] pour commencer à peupler (remplir) la base. Ceci est adapté à des environnements où l'on est dans une [[Hypothèse du monde ouvert|hypothèse de monde ouvert]], comme la description de [[Système complexe|systèmes complexes]]  et de [[Système de systèmes|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<ref name=":1" />{{,}}<ref>{{Ouvrage|langue=en|auteur1=Ievgeniia Oshurko|titre=Knowledge representation and curation in hierarchies of graphs, PhD Thesis in Artificial Intelligence
Université de Lyon, 2020.|passage=111-117|lieu=Lyon|éditeur=Université de Lyon|date=2020|lire en ligne=https://tel.archives-ouvertes.fr/tel-02917559}}</ref> 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 [[Ontologie (informatique)|ontologies]], [[Thésaurus documentaire|thesaurus]] ou [[Taxonomie (homonymie)|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é en informatique|interopérabilité]] sémantique

== Références ==
{{Références}}
{{portail|informatique théorique|mathématiques}}

[[Catégorie:Concept en théorie des graphes|*]]
[[Catégorie:Théorie des graphes]]