Sommaire
1. ERic version 0.2a
2. Installation
3. La représentation du langage naturel
4. Les graphes dirigés
5. Le modèle Entités/Relations
6. Notation graphique et notation textuelle
7. Les commandes d'ERic
8. Comportement en cas d'erreur
9. ECO (ERic Companion Ontology)
10. A cat is on a mat
11. I wash me
12. John is going to Boston by bus
13. The Red Cross aids the war victim people
14. Sarah is colleague and spouse of John
15. Water boils at 100°C
16. Tom believes that Eva wants to marry a sailor
17. A green mouse was running in the grass
18. Normalisation
19. Méta-modèle
20. Performance
21. Syllogisme
22. Négation
23. Nombres réels
24. Raccordement de graphes
25. Homomorphisme de graphes
26. Subsomption de graphes ER
27. ERic versions 0.2b et 0.2c
1. ERic version 0.2a

ERic (Entity-Relationship interactive calculator) v0.2a est un jeune logiciel libre, en ligne de commande, sous licence EUPL-1.1.
ERic permet d'éditer et de sauvegarder des ontologies et des bases de connaissance sous forme de graphes entités/relations. Ensuite, grâce à son algorithme de subsomption, ERic est capable d'interroger sa base de connaissance de façon remarquablement flexible.

Les fichiers binaires BDD (Base De Données) produits par une plateforme 32 bits sont interopérables avec toute autre plateforme 32 bits. Les fichiers binaires BDD produits par une plateforme 64 bits sont interopérables avec toute autre plateforme 64 bits.

Le fichier exécutable ERic.exe nécessite l'OS Microsoft Windows 98 ou supérieur.

ERic v0.2a est 100% programmé en OCaml 3.12.1.

attention: ERic étant dans sa phase initiale de développement, il est recommandé de conserver une copie de ses données en notation textuelle. La compatibilité ascendante n'est pas garantie pour les fichiers binaires (BDD).

2. Installation

Des exécutables précompilés sont disponibles dans le répertoire /bin. Sinon vous pouvez aussi compiler à partir de la source OCaml.

./make.sh

.\make.bat

Crimson Editor Le répertoire /crimson contient les fichiers de coloration pour Crimson Editor.

PSPad Editor le répertoire /pspad contient le fichier de coloration pour PSPad Editor.

Rejoignez le forum des utilisateurs d'ERic.

3. 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.

Le modèle Entités/Relations est particulièrement prometteur pour la modélisation de bases de connaissances difficilement normalisables. Il offre un formalisme unificateur pour schématiser des données composites et des requêtes complexes à l'aide d'une seule et même notation. Ces bases de connaissances peuvent éventuellement supporter quelques mécanismes primitifs de déduction automatique.

4. 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. On autorise également à ce que l'ensemble des arêtes soit un multi-ensemble, c'est-à-dire que plusieurs arêtes peuvent relier un même sommet de départ à un même sommet d'arrivé. On parle alors de multi-graphe dirigé.

Un digraphe étiqueté est un digraphe dont chaque sommet et chaque 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 durée du trajet reliant une ville d'origine à une ville de destination, en roulant à la vitesse limite autorisée.

5. Le modèle Entités/Relations

Le modèle Entités/Relations consiste à représenter l'information à l'aide de deux hiérarchies et d'un digraphe étiqueté où :

Chaque sommet est étiqueté par une entité. Une entité est formée par un concept éventuellement suivi d'un référent. Le concept est un nom inclus dans la hiérarchie des concepts. Le référent est un identifiant librement choisi. La forme textuelle d'une entité contient éventuellement un marqueur alors que la forme graphique n'en contient jamais. Un marqueur est un nom qui désigne la boîte entité où il apparaît pour la première fois.

Chaque arête est étiquetée par une relation (on dit aussi une association ou un rôle). La relation est un nom inclus dans la hiérarchie des relations.

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. Notation graphique ou textuelle pour les digraphes associés.
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.

6. Notation graphique et notation textuelle

À gauche une boîte-entité graphique, à droite une boîte-entité textuelle.

Seul le Concept est obligatoire.

Le référent est ou bien un nom, ou bien un entier signé, ou bien une chaîne de caractères encadrée par deux caractères ", ou bien un numéro de référence précédé du caractère "#". Les concepts ne sont pas typés, ainsi les 4 dates ci-dessous sont autant d'entités valides.
[Date : Today]
[Date : 2012]
[Date : "6 Juin 1944"]
[Date : #1789]
Les 4 dates ci-dessus sont toutes subsumées par l'entité générique [Date].

Le marqueur dans la notation textuelle (obligatoirement précédé d'une étoile "*") remplace les flèches de la notation graphique.

Graphiquement une Relation est représentée par une boîte arrondie avec une unique flèche entrante et une unique flèche sortante.
attention: même si (graphiquement) les relations sont encadrées dans des boîtes arrondies cela n'en fait pas pour autant des sommets. Une relation est et reste avant tout une annotation (étiquette) sur une arête. Seules les entités (boîtes rectangulaires) sont des sommets du graphe ER.

7. Les commandes d'ERic

quit. quitte ERic et retourne à l'invite de commande.

save "fichier". sauvegarde l'ontologie et la base de données en cours dans le fichier BDD indiqué.

load "fichier". charge l'ontologie et la base de données à partir du fichier BDD indiqué.

attention: les utilisateurs de Microsoft Windows devront prendre garde à toujours séparer les noms de répertoires à l'aide du caractère "/" et non pas à l'aide du caractère "\" comme ils en ont l'habitude. Dans le cas contraire le fichier ne sera pas trouvé même si le chemin est un chemin DOS valide.

attention: tenter de charger un ficher BDD corrompu ou qui n'a pas été créé avec la commande save peut mettre ERic dans n'importe quel état instable.

join graphe. fusionne le graphe à la BDD en cours.

select graphe. recherche et imprime tous les graphes de la BDD en cours qui sont subsumés par graphe.
Nous verrons plus tard quelle est la signification de ce verbe subsumer.

Les graphes imprimés par la commande select ont exactement la même syntaxe que les graphes acceptés par la commande join.

ontology [Entity] (Relation). efface la BDD en cours. efface l'ontologie en cours. la nouvelle entité la plus générale s'appelle Entity. la nouvelle relation la plus générale s'appelle Relation.

attention: la commande ontology est irréversible, toute la BDD en cours est définitivement perdue.

super-type [Entity] Entity1 ... Entityn. ajoute dans l'ontologie les enfants Entity1 à Entityn à l'entité parente Entity.

super-type (Relation) Relation1 ... Relationn. ajoute dans l'ontologie les enfants Relation1 à Relationn à la relation parente Relation.

Les lignes débutant par le double-caractère "//" sont considérées comme des lignes de commentaires et n'ont aucun effet.

8. Comportement en cas d'erreur

En cas d'erreur un message approprié est imprimé et la dernière commande est sans aucun effet, le système reste dans l'état qui précédait la commande fautive.

9. ECO (ERic Companion Ontology)

Au chargement ERic ne contient pas de données.

Au chargement ERic ne contient que l'entité Entity et la relation Relation. Il est clair qu'avec aussi peu de vocabulaire il est impraticable d'entrer quelque information que ce soit.

C'est pourquoi, bien qu'ERic vous permette d'éditer et de sauvegarder vos propres ontologies, une ontologie élémentaire est fournie en standard tant sous forme texte (ECO.txt) que sous forme binaire (ECO.bdd). Cette ontologie est nécessaire à l'exécution des exemples qui vont suivre.

attention: pour exécuter correctement les exemples qui vont suivre vous devez d'abord entrer la commande load "ECO.bdd".

Il est vivement recommandé aux utilisateurs de Microsoft Windows de démarrer console plutôt que l'habituel cmd.exe. Il est également recommandé d'élargir la fenêtre de console autant que la largeur de l'écran le permet.

10. A cat is on a mat

En français : il y a un chat sur un tapis.

La forme graphique n'est là que pour aider le lecteur à visualiser le graphe exprimé sous forme textuelle. ERic n'est capable ni d'accepter ni de générer un graphe visuel à partir de (ou de convertir vers) la forme textuelle.

join ([Cat] Place [Mat]).
Un digraphe entités/relations est constitué d'une liste de triplets entitérelationentité toujours terminée par un point.

Le graphe ci-dessus est le plus simple possible puisqu'il ne contient qu'un seul triplet et ne contient pas de référent ou de marqueur.

Comme un digraphe est dirigé, la relation part de l'entité à sa gauche et la relie à l'entité à sa droite.

Toute relation est une relation binaire: elle relie un seul concept à un seul autre concept. Ceci est dû au fait qu'une relation est également une arête du digraphe sous-jacent.

Une bonne coloration du code facilite grandement la lecture. Ici les commandes sont en rouge, les Concepts sont en marron et les Relations sont en bleu.

Les parenthèses sont toujours optionnelles, le code ci-dessous aurait ajouté exactement le même graphe ER.
join [Cat] Place [Mat].
Et voici notre première requête, on va demander quels animaux sont sur un objet fabriqué par l'homme.
select [Animal] Place [Artifact].
11. I wash me

En français : je me lave (la personne qui me lave c'est moi).

Ici I est un référent pour le concept Person.

Dans ECO la relation Agent indique un sujet actif.

Dans ECO la relation Patient indique un sujet passif.

join [Wash*w] Agent [Person I*i] w Patient i.
Ici w et i sont deux marqueurs pour les entités (respectives) [Wash] et [Person : I].

On peut demander quelles personnes agissent sur quelles personnes.
select [Act*a] Agent [Person] a Patient [Person].
12. John is going to Boston by bus

En français : John part en bus jusqu'à Boston.

L'équivalent en notation textuelle.
join
  [Go*g] Agent [Person:John]
  g Destination [City:Boston]
  g Instrument [Bus].
13. The Red Cross aids the war victim people

En français : la Croix Rouge et le Croissant Rouge aident les personnes victimes de la guerre.

Cette fois on n'a pas utilisé le caractère ":" pour séparer concepts et référents.
join
  [Organization RedCross] Mission [Aid Humanitarian*h]
  [Organization RedCrescent] Mission h
  h Patient [People WarVictims].
On peut demander quelles organizations viennent en aide aux personnes.
select [Organization] Mission [Aid*a] a Patient [People].
14. Sarah is colleague and spouse of John

En français : Sarah est la collègue et l'épouse de John.

join [Woman Sarah] SpouseOf [Man John].
join [Woman Sarah] ColleagueOf [Man John].
On voit ici une application de la règle nommée unique name assumption. Cette règle dit que deux entités avec le même concept et le même référent désignent en fait une seule et même entité.

On peut demander quelles personnes sont connues pour travailler avec quelqu'un de leur famille.
select ([Person*x] ColleagueOf [Person*y])(x FamilyRelated y).
15. Water boils at 100°C

En français : le point d'ébullition de l'eau est 100°C.

Une fois transcrit sous forme de triplets.
join [Liquid Water] Property [Boil Water*b] b Limit [Celsius +100].
join [Liquid Azote] Property [Boil Azote*b] b Limit [Kelvin 77].
On peut demander quels sont tous les points d'ébullition connus.
select [Liquid] Property [Boil*b] b Limit [Temperature].
16. Tom believes that Eva wants to marry a sailor

En français : Tom pense qu'Éva voudrait épouser un marin.

Dans ECO la relation Experiencer indique un sujet dans un certain état.

Dans ECO la relation Theme indique un complément d'objet.

Dans ECO les couples 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é).
join
  [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].
Le marin existe-t-il réellement ? Ou bien peut-il n'exister que dans l'imaginaire de Tom ?
Le marin existe réellement, et pas seulement dans l'esprit de Tom. En effet 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...

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 n'est pas possible avec ERic v0.2a. Nous verrons plus tard d'autres limitations de notre modèle entités/relations.

On peut demander toutes les personnes qui pensent qu'une personne souhaite se marrier.
select
  [Believe *b] Experiencer [Person]
  b Theme [Proposition *p]
  p Statement [Want *w]
  w Experiencer [Person*e]
  w Theme [Situation *s]
  s Description [Marry *m]
  m Agent e.
17. A green mouse was running in the grass
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.
Une fois transcrit sous forme de triplets.
join
  [Mouse*mouse] Attribut [Color:Green]
  [Run*run] Agent mouse
  run Place [Grass]
  run Then [Catch*catch]
  catch Agent [Person:I*i]
  catch Patient mouse
  catch Instrument [Tail*tail]
  tail PartOf 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 [DipIn#1*dip1]
  dip1 Agent i
  dip1 Patient mouse
  dip1 Substance [Liquid Oil]
  dip1 Then [DipIn#2*dip2]
  dip2 Agent i
  dip2 Patient mouse
  dip2 Substance [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 Destination [Hat*hat]
  [Possess *possess] Agent i
  possess Theme hat
  put1 Then [Say#1*say1]
  say1 Agent mouse
  say1 Experiencer i
  say1 Theme [Temperature*temp]
  temp Too [High]
  say1 Then [Put#2*put2]
  put2 Agent i
  put2 Patient mouse
  put2 Destination [Drawer*drawer]
  put2 Then [Say#2*say2]
  say2 Agent mouse
  say2 Experiencer i
  say2 Theme [Light*light]
  light Too [Low]
  say2 Then [Put#3*put3]
  put3 Agent i
  put3 Patient mouse
  put3 Destination [Trousers*trousers]
  possess Theme trousers
  put3 Then [Poo*poo]
  poo Agent mouse
  poo Repeat [Times 3].
18. Normalisation

La BDD est irredondante, elle ne peut pas contenir deux triplets identiques. Quand un triplet entitérelationentité est déjà présent dans la BDD son insertion est ignorée. Il n'est pas inséré une seconde fois.

Pour imprimer tous les triplets de la BDD :
select [Entity] Relation [Entity].
attention: vous ne devez pas utiliser la commande ci-dessus pour effectuer une sauvegarde textuelle de la BDD. Car la BDD contient éventuellement plus d'informations que l'ensemble de ses triplets. Il est recommandé de conserver vos graphes ER dans la notation textuelle utilisée pour la commande join.

19. Méta-modèle

Le méta-modèle reprend graphiquement la définition d'un graphe entités/relations.

Bien sûr, à partir du moment où l'on ne considère que la partie données (les graphes ER) et pas la partie algorithmie (la subsomption) on a forcément une méta-modélisation hémiplégique. Nous prions le lecteur de bien vouloir nous pardonner ce renoncement.

Heureusement, la représentation graphique est tout à fait transcriptible textuellement. Après quelques ajouts mineurs à l'ontologie ECO.
super-type [Artifact] Mathematical.
  super-type [Mathematical] Graph.
    super-type [Graph] DiGraph EntityRelationGraph.
    super-type [Label] Concept Referent Relation.

join
  [Hierarchy] Members [Concept *con]
  [Hierarchy] Members [Relation *rel]
  [Vertex *v] LabelledWith con
  [Edge *e] LabelledWith rel
  e Origin v e Destination v
  v Optional [Referent *r]
  r Case [Name]
  r Case [Integer]
  r Case [String]
  r Case [Reference]
  [Set *sv] Members v
  [MultiSet *se] Members e
  [EntityRelationGraph *g] Characteristic sv
  g Characteristic se.
ERic est tout à fait capable de classifier son méta-modèle. La requête suivante nous permet de confirmer ce que l'on savait d'eux par leur définition, à savoir que les graphes ER sont subsumés par les multi-graphes dirigés.
select
  [Set *sv] Members [Vertex *v]
  [MultiSet *se] Members [Edge *e]
  e Origin v e Destination v
  [Graph *g] Characteristic sv
  g Characteristic se.
20. Performance

Il s'agit ici de la performance de la commande select puisqu'il ne devrait pas y avoir de problème de performance sur aucune autre commande.

La taille de la BDD se mesure en nombre de triplets entitérelationentité.

La performance de select diminue à mesure que la taille de la BDD augmente.

La performance de select augmente avec la taille initiale de l'ontologie. On peut augmenter la taille de l'ontologie (en l'affinant) après l'insertion de nombreux triplets cependant cela n'aura d'impact que sur les futurs triplets ajoutés. Plus la conception de l'ontologie initiale a été judicieusement anticipée et raffinée meilleure sera la tenue de la performance lorsque le nombre de triplets augmentera. La qualité de l'ontologie initiale est donc déterminante, pour la qualité des données stockées et la qualité de leur exploitation, mais aussi pour le maintient d'une bonne performance.

ERic a été conçu pour des ontologies ambitieuses. Si vous n'utilisez majoritairement qu'un petit nombre de Concepts/Relations alors la tenue de la performance de select risque d'être médiocre.

La variété des référents n'a pas d'impact positif sur la performance. Seule compte la variété des Concepts/Relations.

21. Syllogisme

Comment faire un syllogisme tel que :
Tous les hommes sont mortels.
Socrate est un homme.
Donc Socrate est mortel.
ECO contient le concept Human mais pas le concept Mortal.

Ça n'est pas possible à faire directement à partir d'un graphe. Pour le faire il faut obligatoirement insérer le concept de mortalité dans l'ontologie.
ontology [Entity] (Relation).
  super-type [Entity] Mortal City Date.
    super-type [Mortal] Human.
  super-type (Relation) Born Died.
join
  [Human Socrates*s] Born [Date -470]
  s Born [City:Athens]
  s Died [Date -399].
select
  [Mortal*m] Relation [Entity].
Notez bien que ce n'est pas l'affirmation que Socrate est né puis mort qui fait de lui un mortel. Ce qui fait de lui un mortel c'est le fait d'être subsumé par l'entité [Mortal*m]. Bien entendu Socrate ne cesserait pas d'être [Mortal] si vous décidiez de supprimer la ligne "s Died [Date -399]". Car il n'y a pas besoin d'être mort pour être mortel. Une preuve suffisante que Socrate est mortel c'est que sa boîte-entité est systématiquement marquée par *m.
Ce marqueur *m n'est pas indispensable. Toutefois la commande select répond avec des graphes et non pas avec les images recherchées. Par conséquent pour retrouver une image une astuce consiste à marquer son antécédent.

attention: le code ci-dessus a effacé toute l'ontologie ECO.
Avant de poursuivre ce tutoriel vous seriez bien avisé d'exécuter à nouveau la commande load "ECO.bdd". afin de recharger l'ontologie standard.

Raffiner l'ontologie tend à améliorer la performance mais c'est avant tout l'unique moyen de révéler la puissance de la subsomption.

L'outil ne peut être adapté à vos besoins que si vous concevez une ontologie pertinente pour votre spécialité. Ou à défaut récupérez et personnalisez une ontologie déjà existante et proche de vos préoccupations. ECO n'est pas un standard, ça n'est rien de plus qu'un support pour les exemples de ce tutoriel.

22. Négation

ERic n'offre aucune forme de négation. Introduire la négation générale dans le modèle entités/relations serait une aberration car la subsomption deviendrait logiquement inconsistante.

Si votre négation porte seulement sur un mot ajoutez le mot contraire dans l'ontologie. Par exemple "pas raisonnable" n'est pas une expression valide, cependant PasRaisonnable ou Déraisonnable peuvent être ajoutés à l'ontologie.

Un logicien pourrait être tenté d'affirmer "il n'existe pas d'humain non mortel", ce qui signifierait "tous les humains sont mortels". Dans ce cas encore, comme cela a déjà été dit à propos du syllogisme, la seule façon de faire est d'insérer les bons Concepts dans l'ontologie.

23. Nombres réels

Tout le mode sait que la DeLorean équipée du convecteur temporel du Dr. Emmett Brown doit rouler à 88 miles/heure en consommant une puissance de 2,21 Gigawatts. Seulement ERic 0.2a ne sait pas lire les nombres réels. Toutefois ECO offre une panoplie minimale d'unités de mesure. Par conséquent 2210 Mégawatts feront très bien notre affaire pour un voyage temporel.

En notation textuelle.
join
  [Run*r] Experiencer [Teen Marty-McFly]
  r Substance [Time]
  r Instrument [Car DeLorean*d]
  [Mile/Hour 88] RequiredBy d
  d EquippedWith [Time Convector*t]
  t Design [Doctor Emmett-Brown]
  [MegaWatt 2210] RequiredBy t.
Quelle machine m équipée du convecteur temporel permet de voyager dans le temps ? Quelle est la puissance p requise ?
select
  [Run*r] Substance [Time]
  r Instrument [Artifact*m]
  m EquippedWith [Time Convector*t]
  [Power-SI*p] RequiredBy t.
Le marqueur *p n'est pas strictement nécessaire, en fait il n'est même pas utilisé dans le graphe. Par contre il permet de mieux voir quelle est l'image de [Power-SI] par l'homomorphisme de graphe. Son image sera la boîte-entité marquée par *p. Quant à la machine à voyager dans le temps ce sera la boîte-entité marquée par *m.

24. Raccordement de graphes

Les graphes sont-ils condamnés à n'exister que comme des êtres isolés s'ignorant mutuellement ? Les requêtes ne sont-elles que des clés servant à ouvrir telle ou telle porte prédéfinie ?
Les graphes ER ne sont pas isolés les uns des autres, ils sont au contraire inter-connectés. Leur information est partagée et cette information collective est pleinement exploitable par le mécanisme de requête.

Nous avons déjà rencontré une telle situation auparavant.
join [Woman Sarah] SpouseOf [Man John].
join [Woman Sarah] ColleagueOf [Man John].

Il s'agissait bien de 2 graphes ER qui ont été fusionnés en 1 seul de façon à permettre une requête sur l'ensemble de l'information et non sur deux graphes disjoints. On avait alors évoqué la règle dite de unique name assumption. Cette règle dit que deux entités avec le même concept et le même référent désignent en fait une seule et même entité.

En conséquence de la règle de unique name assumption une boîte-entité munie d'un référent est partagée par tous les graphes qui la contiennent.
Autrement dit on peut compléter, ou même inter-connecter, des graphes déjà existants en ajoutant des jonctions à travers des boîtes-entité munies d'un référent.

Soit en notation textuelle.
join
  [Movie "Back To The Future"*m] Release [Date "3 July 1985"]
  m Origin [Country United-States]
  m Duration [Minute 116]
  m Written [Man Robert-Zemeckis*rz]
  m ArtDirector rz
  m ArtProducer [Man Steven-Spielberg]
  m ArtStudio [Company Amblin-Entertainment]
  m ArtDistributor [Corporation Universal-Pictures]
  m Decoration [Award Academy-Awards]
  m Decoration [Award Hugo-BestDramaticPresentation]
  m Decoration [Award Saturn-BestScienceFictionFilm]
  m Cost [Dollar 19000000*d19M]
  m Estimated d19M
  m Revenue [Dollar 381109710*d381M]
  m Exact d381M
  m Starring [Teen Michael-J-Fox*mjf]
  m Starring [Man Christopher-Lloyd*chl]
  mjf Acting [Teen Marty-McFly*mmf]
  mmf Attribut [Age 17]
  chl Acting [Doctor Emmett-Brown*doc]
  doc Attribut [NickName Doc].
Il devient alors possible de répondre à des requêtes mobilisant l'information de deux ou plusieurs graphes ER.
Il peut s'agir d'un film m récompensé aux Academy Awards dans lequel un docteur d joué par un actor et surnommé Doc a conçu un convecteur temporel équippant une voiture c.
select
  [Movie*m] Decoration [Award Academy-Awards]
  m Starring [Man*actor]
  actor Acting [Doctor*d]
  d Attribut [NickName Doc]
  [Time Convector*t] Design d
  [Car*c] EquippedWith t.
25. Homomorphisme de graphes

Soient G un graphe dirigé d'arêtes U et H un graphe dirigé d'arêtes V. Un homomorphisme de G vers H est une application ƒ telle que :

∀ (xy) ∈ U on a (ƒ(x), ƒ(y)) ∈ V.

Plus simplement, ƒ est un homomorphisme de graphes si l'image de toute arête de G est une arête de H.

Autrement dit l'image d'un graphe G dans un graphe H doit respecter les relations d'adjacence présentes dans G.

26. Subsomption de graphes ER

Un concept (respectivement une relation) est subsumé(e) par tout concept (respectivement toute relation) identique, parent(e) ou ancêtre dans l'ontologie.

Un référent ne peut être subsumé que par un référent identique ou par le référent vide.

Une arête d'un graphe ER est subsumée par toute arête dont la boîte-entité de départ (respectivement d'arrivée) subsume sa propre boîte-entité de départ (respectivement d'arrivée) et dont l'étiquette-relation subsume sa propre étiquette-relation.

Soient G un graphe ER d'arêtes U et H un graphe ER d'arêtes V. Le graphe entités/relations G subsume H si il existe une application ƒ telle que

∀ (xry) ∈ U on a :

(ƒ(x), ƒ(r), ƒ(y)) ∈ V.

(xry) subsume (ƒ(x), ƒ(r), ƒ(y)).

La commande select G. recherche et imprime tous les graphes H subsumés par G.
Les flèches rouges et vertes représentent deux applications ƒ telles que le graphe de gauche subsume le graphe de droite. Pour simplifier seules les flèches les plus significatives ont été représentées. Si on avait été exhaustif alors chaque boîte à gauche serait reliée à une boîte à droite.

L'entité [Child] subsume les entités [Girl] et [Boy:Paul]. L'entité [Act] subsume l'entité [Play]. Les entités [Vehicule] et [Truck] subsument l'entité [FireTruck]. De même les deux boîtes (Place) à gauche sont reliées à l'unique boîte (Place) à droite. L'homomorphisme n'est donc pas injectif.

Ne devrait-on pas considérer que dans la requête (le graphe de gauche) on exige la présence d'un véhicule et d'un camion sur le tapis ?
Le véhicule et le camion sont bien sur le même tapis puisqu'il s'agit de la même boîte entité [Mat]. Par contre le véhicule et le camion ne sont pas forcément distincts puisque, d'une part, un camion est un véhicule, et d'autre part ils ne portent pas de référent qui permettraient de les différencier.

La subsomption s'applique tout autant aux relations comme on l'a déjà vu dans l'exemple 14FamilyRelated subsumait SpouseOf.

Et si on avait demandé un véhicule bleu ?
Dans ce cas il n'y aurait pas de subsomption de graphes. Le fait que la flèche [Color:Red][Color:Red] ne soit pas représentée ne signifie pas qu'elle est plus dispensable que les autres.

Vous pouvez vous amuser à tester des variations sur cet exemple.
join
  [Girl*g] SisterOf [Boy:Paul*b]
  [FireTruck*f] Attribut [Color:Red] f Place [Mat]
  [Play*p] Theme f
  p Agent g p Agent b.
select
  [Act*a] Agent [Child]
  a Theme [Vehicule*v] v Attribut [Color:Red]
  v Place [Mat*m] [Truck] Place m.
27. ERic versions 0.2b et 0.2c

ERic version 0.2b reprend les fondamentaux d'ERic v0.2a et lui apporte deux extensions mineures.

Un nouveau type de base : les nombres réels flottants.
Vous pouvez maintenant créer une entité [Watt 2.21e9].
ERic 0.2c apporte une mise à jour d'ECO qui prend en compte les nombres réels flottants tout en incorporant davantage d'unités SI.

Plus deux annotations pour mieux documenter les relations :

La barre verticale symbolise un miroir, elle sépare un couple de relations inversées comme :
super-type (Invertible) ParentOf|ChildOf  SalariedBy|EmployerOf
L'encadrement par un tiret symbolise une relation réciproque (bidirectionnelle) comme :
super-type (Symmetric) -Spouse- -Sibling- -Twin- -Friend- -Associate- -Colleague- -Rival-
Ces annotations n'ont (pour l'instant) que valeur de documentation, elles n'ajoutent pas automatiquement la relation complémentaire à toute relation inversible ou bidirectionnelle.