Un modèle simple avec une sémantique intuitive.
La représentation du langage naturel
d'un côté le mode de communication le plus spontané pour l'humain est sa langue maternelle, comme le français ou l'anglais.
d'un autre côté le mode de fonctionnement de l'ordinateur exige une information symbolique hautement formalisée, ce formalisme est si exigeant qu'il constitue une barrière pour le non-spécialiste et un frein ou une perte de productivité pour le spécialiste.
indépendamment des problèmes d'interface homme/machine, formaliser un projet, une conception, un processus, et même tout type de création complexe, permet souvent de gagner de la clarté, de la cohérence et de la facilité de communication au sein d'une équipe.
Le modèle Entités/Relations tente de répondre à ces 3 problématiques en se voulant être un langage intermédiaire entre le langage parlé ou écrit et le codage pour une machine. Une modélisation entités/relations est une sorte de schéma pré-conceptuel. Il est suffisamment proche du langage écrit pour rester lisible par un humain tout en restant suffisamment structuré pour autoriser le traitement et la validation automatique par une machine.
Les graphes dirigés
Un graphe dirigé (ou digraphe en abrégé) est un diagramme qui comprend :
un ensemble de points (aussi appelés sommets).
un ensemble d'arcs (aussi appelés arêtes) orientés, chacune de ces arêtes orientées relie un sommet de départ à un sommet d'arrivé.
Il n'y pas d'autre contrainte particulière sur les sommets ou les arêtes. En particulier on autorise à ce qu'une (ou plusieurs) suite(s) d'arêtes forme(nt) un chemin cyclique.
Un digraphe étiqueté est un digraphe dont chaque sommet et/ou arête est annoté(e) par une certaine information. Par exemple si chaque sommet est étiqueté par le nom d'une ville alors chaque arête peut être étiquetée par la longueur (ou bien la durée) du trajet reliant une ville d'origine à une ville de destination.
Le modèle Entités/Relations
Le modèle Entités/Relations consiste à représenter l'information à l'aide d'un digraphe étiqueté où :
chaque sommet est étiqueté par une entité (on dit aussi un concept).
chaque arête est étiquetée par une relation (on dit aussi une association).
Avantage: un diagramme entités/relations étant un digraphe, tout résultat algorithme connu pour les digraphes est immédiatement transposable aux diagrammes entités/relations. Or les digraphes font parti des structures étudiées depuis longtemps en informatique, on possède tout un corpus de connaissances à leur sujet. Des connaissances qu'on pourra réutiliser pour étudier les (bonnes ou mauvaises) propriétés du modèle Entités/Relations.
Domaine: dans ce tutoriel on appliquera le modèle au traitement du langage naturel et à la représentation des connaissances. Le modèle peut toutefois s'adapter ou s'étendre pour couvrir à peu près n'importe quel domaine quelque part à la frontière du tout intuitif et du tout formel.
Inconvénient: comme il s'agit plus d'un modèle pré-conceptuel que d'un modèle entièrement formel on sera amené à décrire nos représentations dans plusieurs langages, qu'ils soient naturels ou non. Français/anglais pour les langages naturels. Forme graphique ou textuelle pour les schémas associés. Enfin, pour les lecteurs plus avertis, on utilisera aussi la logique du premier ordre ( First Order Logic ou FOL en abrégé) pour la sémantique formelle ainsi que le langage de programmation OCaml pour l'implantation.
On n'hésitera pas à multiplier les exemples afin que chacun comprenne bien la démarche quelque soit son niveau de connaissance. On insistera particulièrement sur le passage du langage naturel au schéma entités/relations dans sa forme graphique et dans sa forme textuelle.
La forme graphique est la représentation en 2D tandis que la forme textuelle est la représentation linéaire ou 1D.
Les concepts
Textuellement un concept prend l'une des 5 formes suivantes :
[Home] [Liquid: Water] [VIP: #1] [Celsius: +100] [URL: "http://www.aeriesguard.com"]
Un concept est toujours encadré par un crochet ouvrant et un crochet fermant.
Le caractère deux-points est toujours facultatif.
Graphiquement un concept est encadré par une boîte rectangulaire.
Les relations
Une relation est simplement un nom reliant un concept d'origine à un concept de destination.
Textuellement une relation est toujours encadrée par une parenthèse ouvrante et une parenthèse fermante.
Graphiquement une relation est encadrée par une boîte arrondie à gauche et à droite.
Textuellement, un schéma entités/relations est une phrase qui se termine par un point.
Toute relation est binaire: elle relie un seul concept à un seul autre concept. C'est dû au fait qu'une relation est également une arête du digraphe sous-jacent.
A cat is on a mat.
En français: il y a un chat sur un tapis.
([Cat] On [Mat]).
Spoiler (Sélectionnez le texte dans le cadre pointillé pour le faire apparaître)
En FOL ce diagramme est équivalent à l'expression ∃x∃y Cat(x) ⋀ Mat(y) ⋀ On(x,y)
Water boils at 100°C.
En français: l'eau bout à 100°C.
([Liquid Water] Boil [Celsius +100]).
I wash me.
En français: je me lave (la personne qui me lave c'est moi).
([Person:I*me] Wash me).
l'étoile * est suivie d'un nom (un marqueur) qui sert, dans une relation, à désigner la boîte-concept où il a été déclaré.
Il s'agit d'un premier exemple de diagramme contenant un cycle.
John is going to Boston by bus.
En français: John part en bus jusqu'à Boston.
Une relation Agent indique un sujet actif.
([Go *x] Agent [Person:John]) (x Destination [City:Boston]) (x Instrument [Bus]).
Spoiler (Sélectionnez le texte dans le cadre pointillé pour le faire apparaître)
En FOL ce diagramme est équivalent à l'expression ∃x∃y Go(x) ⋀ Person(John) ⋀ City(Boston) ⋀ Bus(y) ⋀ Agent(x,John) ⋀ Destination(x,Boston) ⋀ Instrument(x,y)
Par la suite on ne donnera plus la sémantique en FOL. Ce qu'il faut retenir c'est que chaque diagramme entités/relations possède une sémantique formelle précise (dépourvue d’ambiguïté).
Spoiler (Sélectionnez le texte dans le cadre pointillé pour le faire apparaître)
Un lecteur averti a fait la remarque selon laquelle une autre représentation était possible dans laquelle le verbe Go serait une relation et non un concept.
Le diagramme de gauche est basé sur un digraphe où les arêtes sont étiquetées par les relations. Le diagramme de droite est basé sur un graphe biparti où les arêtes sont étiquetées par des entiers.Textuellement le diagramme de droite s'écrirait ainsi :
(Go [Person:John] [Bus] [City:Boston]).
Un graphe biparti est un diagramme qui comprend :
un premier ensemble de sommets de type E.
un second ensemble de sommets de type R.
un ensemble d'arêtes, chacune de ces arêtes relie un sommet de type E à un sommet de type R.
Dans cet article, pour des raisons que nous ne discuterons pas, on a choisi :
de baser le modèle Entités/Relations sur les digraphes plutôt que sur les graphes biparti
d'accorder (graphiquement) une boîte arrondie à chaque relation même si conceptuellement elle ne restera toujours qu'une simple étiquette sur une arête
Smiling Mary and her brother play with a toy car.
En français: Marie est souriante, elle et son frère jouent avec une voiture.
([Girl:Mary*m] Face [Smile]) (m SisterOf [Boy*b]) (m PlayWith [ToyCar*c]) (b PlayWith c).
Tom believes that Eva wants to marry a sailor.
En français: Tom pense qu'Éva voudrait épouser un marin.
([Believe *b] Experiencer [Person:Tom]) (b Theme [Proposition *p]) (p Statement [Want *w]) (w Experiencer [Person:Eva*e]) (w Theme [Situation *s]) (s Description [Marry *m]) (m Agent e) (m Theme [Sailor]).
Dans ce document on a largement reprit le vocabulaire de John F. Sowa :
Une relation Attribut indique une propriété durable.
Une relation Agent indique un sujet actif.
Une relation Patient indique un sujet passif.
Une relation Theme indique un complément d'objet.
Une relation Location indique un complément de lieu.
Une relation Experiencer indique un sujet dans un certain état.
Les boîtes Proposition/Statement et Situation/Description permettent d'exprimer un concept composite, c'est-à-dire un concept lui-même défini par un diagramme entités/relations. Ces boîtes introduisent la notion de diagramme imbriqué à peu de frais (puisque le diagramme ne reste qu'un simple digraphe étiqueté).
Le marin existe-t-il réellement ? Ou bien peut-il n'exister que dans l'imaginaire de Tom ?
Spoiler (Sélectionnez le texte dans le cadre pointillé pour le faire apparaître)
Le marin existe réellement, et pas seulement dans l'esprit de Tom. Ce qui permet de l'affirmer c'est la sémantique FOL. Une boîte-concept signifie : une entité existe qui représente ce concept. Par exemple, il existe Éva qui est une personne, il existe un liquide qu'on appelle l'eau et qui bout à 100°C, il existe un marin dont on sait que Tom pense qu'Éva voudrait l'épouser...
Spoiler (Sélectionnez le texte dans le cadre pointillé pour le faire apparaître)
Comment s'y prendre si l'on voulait préciser que Tom ne connaît pas le marin et ne sait pas s'il existe mais qu'il le pense. Il faudrait sans doute pouvoir délimiter un cadre en dedans duquel tout est supposition et en dehors duquel tout est certitude. Ce serait une extension du modèle proposé ici. Le modèle de base est inapte à exprimer une telle subtilité.
Une souris verte qui courait dans l'herbe
Une souris verte
Qui courait dans l'herbe,
Je l'attrape par la queue,
Je la montre à ces messieurs,
Ces messieurs me disent :
Trempez-la dans l'huile,
Trempez-la dans l'eau,
Ça fera un escargot
Tout chaud.
Je la mets dans mon chapeau,
Elle me dit qu'il fait trop chaud.
Je la mets dans un tiroir,
Elle me dit qu'il fait trop noir.
Je la mets dans ma culotte,
Elle me fait trois petites crottes.
A green mouse
Was running in the grass,
I catch it by the tail,
I show it to these fellows.
These fellows tell me :
Dip it in the oil,
Dip it in water,
And that will make a snail.
A hot one.
I put it in my hat,
She says to me that it's too hot.
I put it in a drawer,
She says to me that it's too black.
I put it in my trousers,
And she does 3 poos.
À ce stade la réalisation du diagramme (avec MS-Paint 
) devient tellement laborieuse que je m'épargne cet effort pour passer directement à la forme textuelle :
([Mouse*mouse] Attribut [Color:Green]) ([Run*run] Agent mouse) (run Location [Grass]) (run Then [Catch*catch]) (catch Agent [Person:I*i]) (catch Patient mouse) (catch Instrument [Tail*tail]) (tail Of mouse) (catch Then [Show*show]) (show Agent i) (show Experiencer [Fellow Citizen*fellows]) (show Then [Tell*tell]) (tell Agent fellows) (tell Experiencer i) (tell Theme [Proposition*prop]) (prop Statement [Dip#1*dip1]) (dip1 Agent i) (dip1 Patient mouse) (dip1 In [Liquid Oil]) (dip1 Then [Dip#2*dip2]) (dip2 Agent i) (dip2 Patient mouse) (dip2 In [Liquid Water]) (dip2 Then [Make*make]) (make Agent i) (make Theme [Snail*snail]) (snail Attribut [Temperature Hot]) (tell Then [Put#1*put1]) (put1 Agent i) (put1 Patient mouse) (put1 In [Hat*hat]) (i Possess hat) (put1 Then [Say#1*say1]) (say1 Agent mouse) (say1 Experiencer i) (say1 Theme [Temperature*temp]) (temp Attribut [Too High]) (say1 Then [Put#2*put2]) (put2 Agent i) (put2 Patient mouse) (put2 In [Drawer*drawer]) (put2 Then [Say#2*say2]) (say2 Agent mouse) (say2 Experiencer i) (say2 Theme [Light*light]) (light Attribut [Too Low]) (say2 Then [Put#3*put3]) (put3 Agent i) (put3 Patient mouse) (put3 In [Trousers*trousers]) (i Possess trousers) (put3 Then [Poo*poo]) (poo Agent mouse) (poo Repeat [Times 3]).
Conclusion
On a présenté un langage de modélisation à la fois raisonnablement simple et en même temps raisonnablement expressif. Bien entendu des extensions sont possibles, notamment pour effectuer des requêtes avancées et des raisonnements simples comme par exemple des syllogismes.
La forme graphique en 2D peut paraître plus lisible que la forme textuelle.
Toutefois la forme textuelle est incontournable pour au moins deux raisons. D'une part la forme graphique devient de plus en plus difficile à écrire/dessiner à mesure que la connaissance devient compliquée. D'autre part, une fois éditée, la base de connaissance doit pouvoir être sauvegardée pour ne pas être perdue. Or, pour des raisons technologiques, cette sauvegarde ne peut se faire que linéairement, en 1D.
Le modèle Entités/Relations est-il une base solide sur laquelle on pourrait bâtir une ou des formes d'intelligence artificielle arbitrairement évoluées, ou au moins rivalisant avec l'intelligence humaine. La réponse est malheureusement négative. Bien au contraire, le modèle Entités/Relations est une base fragile, toute extension inconsidérément ajoutée pour augmenter l'expressivité du modèle possède un coût en terme de computabilité. En particulier l'ensemble minimum de toutes les extensions désirables pour obtenir un modèle aussi expressif que FOL (First Order Logic) abouti aux mêmes limitations déjà bien connues en FOL: de nombreuses questions deviennent semi-décidables ou carrément indécidables (comprenez: il n'existe aucune façon connue pour l'ordinateur d'aboutir à une réponse positive ou négative).
Le prochain tutoriel abordera les opérations élémentaires sur les schémas entités/relations, c'est-à-dire la jointure et la requête
Tout d'abord merci SpiceGuid pour cet article qui vulgarise pas mal le sujet (l'utilisation de puces graphiques pour séparer les idées aidant beaucoup pour la lecture) néanmoins cela reste quand même assez dur à assimiler dans son ensemble, même pour moi qui le côtoies assez souvent.
Une première chose, lorsque tu définis les arcs je suis assez surpris que tu n’aie pas précisé que lesdits arcs ont un sens ce qui dirige la lecture du schéma et qui fait donc toute la spécificité du graphe dirigé. Ça peut sembler couler de source mais je te confirmes que non.
Dans les formations BDD il est couramment admis que les entités doivent être représentés par des noms et les relations par des verbes. Du coup voir des noms apparaître pour des relations est assez perturbant. Surtout en plus quand des relations spéciales comme agent, patient, etc. apparaissent. Tu devrais approfondir le sujet en particulier sur l'exemple 4 où la relation patient apparait mais n'est expliquée que deux exemples plus loin.
La réflexion sur "si le marin existe" est par contre très intéressante et met bien en lumière les limites du modèle.
Merci pour ton retour d'expérience. Je vais modifier l'article à la marge pour tenter d'améliorer la lisibilité et la cohérence avec la seconde partie à venir.
Ce qui ne va pas changer :
Ce qui va changer :
Edit(1) :
Je n'ai pas répondu à ta question à propos de ce que l'on peut ou doit mettre dans une entité et une relation. En googlant "John is going to Boston by bus" on tombe aussi bien sur ceci que sur cela. Dans un cas le verbe est un concept, dans l'autre le verbe est une relation. J'expliquerai la différence soit dans un futur commentaire soit dans l'article lui-même.
Edit(2) :
Maintenant j'ai complètement répondu à ta question dans une balise anti-spoiler
(Je me permet de solliciter ton avis puisque tu es rédacteur DVP et que je compte bien lever un maximum de difficultés avant la publication de l'article)