Le blog de SpiceGuid

Profil Contributions

On pourrait jouer à kikalapugrosse et pourtant on va jouer à kikalapupetite.

Si vous devez calculer le minimum de deux entiers a et b vous allez écrire quelque chose comme ceci :

if a < b then return a else return b

Cependant la nature étant infinie dans sa diversité, parfois le minimum à calculer n'est pas un entier mais un machin-chose plus compliqué, par exemple un chemin . Alors vous allez écrire quelque chose comme ceci :

if less_than(path1,path2) then return path1 else return path2

Le truc étant que less_than va renvoyer vrai si path1 est plus court que path2 et faux autrement.
Mais plus court. Comment ? En nombre de tours de jeu ? Ou bien en distance kilométrique ?
En nombre de tours de jeu, car il ne serait pas acceptable que le joueur gaspille un tour.
Cependant, à nombre de tours égal, vos soldats déserteront moins s'ils marchent sur moins de distance.
Alors vous allez simplement écrire quelque chose comme ceci :

define less_than(path1,path2) =
  if turns(path1) < turns(path2) then return true
  else if turns(path1) > turns(path2) then return false
  else return length(path1) < length(path2)

Le fil des nouvelles sur l'avancement de mon projet ERic (Entity-Relationship interactive calculator).

La dernière version stable ERic 0.2g :

• Vous pouvez consulter la documentation en ligne
• Vous pouvez récupérer l' archive zip de la dernière version
• Vous pouvez également récupérer la version SVN d'ERic
• Rejoignez le forum des utilisateurs d'ERic

Toutes les extensions prévues ont été implantées. Pour cela il aura fallu, entre autres, concevoir l'ontologie ECO (Eric Companion Ontology) qui n'utilise pas les types conjonctifs.

Eric v0.2a permet d'éditer et de sauvegarder des ontologies et des bases de connaissance sous forme de graphes entités/relations.

Comme Aerie's Guard n'est plus adapté pour discuter des évolutions futures d'Eric, le projet va passer en Open-Source afin de mieux centraliser d'éventuels utilisateurs ainsi que les demandes qu'ils seraient amenés à exprimer. Ceci afin de faire muer Eric en un logiciel compétitif sur son segment de marché. Merci à vous d'avoir suivi la genèse de ce projet motivant.

Eric v0.2a n'est plus capable de charger les fichiers sauvés avec la version 0.1b

Hé bien alors, il répond quand à ma question cette feignasse d'ordinateur ?

Qu'est-ce que la NP-complétude ?

Sans rentrer dans les détails techniques, on dit d'un algorithme ou d'un problème qu'il est NP-complet si le temps de réponse à une petite question peut être arbitrairement grand. Par arbitrairement grand on entend totalement disproportionné par rapport à la simplicité de la question. 

Oui, mais tout ça n'est que de la théorie ?

Rassurez-nous, ça ne peut pas arriver, si ?
D'ailleurs ça ne m'est jamais arrivé.

Hé bien détrompez-vous, ça peut arriver puisqu'on vous le dit.

1. Lancez Eric 0.1b .

2. Copiez-collez la contine de la souris verte dans la console : 

join
  ([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]).

3. Copiez-collez cette requête :

select
  ([*] Then [*])([*] Then [*])([*] Then [*])
  ([*] Then [*])([*] Then [*])([*] Then [*])
  ([*] Then [*])([*] Then [*])([*] Then [*]).

4. Allez faire la sieste. Lissez le cycle de DUNE .

C'est grave docteur ?

C'est impossible à diagnostiquer. L'exemple donné ci-dessus est clairement pathologique puisque le graphe demandé est sacrément non-connexe . Cependant rien ne dit que ça ne pourrait jamais arriver dans des conditions normales d'utilisation. Heureusement on constate (empiriquement) que ça serait l'exception plutôt que la règle.

Appel à témoins

Si jamais vous aviez la chance d'observer un comportement étrange (une réponse sans fin, un temps de réponse anormalement long,...) veuillez me MP l'exemple des données et la question qui ont engendré (de façon reproductible) le comportement pathologique. Ce genre d'information est d'une valeur capitale pour moi.

Merci à vous d'avoir lu cet article.

Un article sur l'évolution du logiciel complexe, exemplifié par le futur Eric 0.2

Oui, je sais, je devrais programmer sinon cette version 0.2 ne verra jamais le jour. D'un autre côté j'ai des choses à dire alors je les dis, tant pis si l'essentiel prend du retard parce que l'essentiel est dit.

Release early, release often

Quel est le cœur du cœur de votre application.
C'est la question clé. Répondez à cette question, réduisez au maximum la voilure, comprimez la spécification jusqu'à ce qu'il ne reste plus que la peau sur les os. Puis implémentez, déboguez, documentez, et appelez ce premier jet version 0.1a

Alors toute la suite de l'histoire n'est plus qu'extensions sur extensions. N'essayez pas d'ajouter des greffons, refactorisez la conception au fur et à mesure de l'implantation de nouvelles fonctionnalités. Visez d'abord les extensions utilitaires. Ce sont celles qui manquaient cruellement à la version 0.1 pour en faire autre chose qu'un jouet.

Utilisez la méthode Quality First .

Comparez avec les logiciels existants. Même si votre programme est très exotique il existe forcément quelques programmes avec des buts similaires ou partiellement équivalents. Sachez distinguer la caractéristique indispensable et le gadget superfétatoire.

Dois-je ajouter une interface graphique.
L'utilisateur final sera sans doute très sensible à la présence d'une interface graphique. Cependant cela représente un travail énorme pour le programmeur. Par conséquent il faut le repousser très en aval de la conception. Pensez d'abord à ajouter les fonctionnalités indispensables. Quand votre programme commence à rivaliser avec les solutions alternatives alors seulement il sera temps d'accoler une interface graphique.

Dois-je ajouter une architecture client-serveur.
Même raisonnement que pour l'interface graphique. C'est une demande de l'utilisateur final. Ne la prenez pas prématurément en compte. Concentrez-vous sur l'essentiel, c'est ce qui fera la véritable valeur ajoutée de votre programme une fois que vous aurez ajouté tout ce que vos utilisateurs réclament.

Google est mon ami

 J'ai déjà dit et répété qu'Eric était sujet à de multiples possibilités d'extension. Foin de promesses, il est grand temps de décider quelle extension fera d'Eric 0.2 un logiciel autrement plus avancé qu'Eric 0.1b

Une recherche rapide dans le domaine de l'ingénierie de la connaissance permet d'isoler les quelques principaux concurrents d'Eric. Ce sont des logiciels matures souvent issus de deux dizaines d'années de recherche universitaire.

Le plus proche (géographiquement) est Cogitant , une charpente pour les graphes conceptuels écrite en C++ et reliée à l'interface CoGui écrite en Java.

Un autre est Loom (maintenant évolué en PowerLoom ) écrit en STELLA (environ 50000 lignes, sans compter l'interface en Java).

Quelle est donc la particularité commune à Cogitant et à Loom qui en fait des bases de connaissances bien plus crédibles qu'Eric 0.1b (environ 600 lignes d'OCaml).

La première réponse c'est sans aucun doute la subsomption . Eric possède bien quelques rudiments de logique de description mais il est incapable d'en tirer pleinement parti car son vocabulaire est plat. Comme Cogitant et Loom l'ont déjà, il lui faudrait une ontologie (un vocabulaire structuré) et un raisonnement par subsomption (un ordre partiel sur l'ensemble des graphes entités-relations).

Bien évidemment l'ontologie d'Eric serait initialement vide au chargement. Il faudrait donc éditer (ou bien charger) une ontologie avant d'éditer un graphe entités-relations, puisqu'autrement on n'aurait aucun vocabulaire pour étiqueter les boîtes-concepts et les boîtes-relations.

Comme je ne vais pas réinventer la roue, autant considérer une création complexe (par exemple Kernherd de Cathaseris ), et utiliser une ontologie appropriée (ici RPGOntology ) pour tenter de la modéliser. Après tout rien de tel que l'épreuve du réel.

Mais pas cette fois-ci

Pas de chance. RPGOntology est introuvable. Ou plutôt si, Google connaît bien RPGOntology , mais il s'agit malheureusement de Radiation Protection Guidelines Ontology
Tant pis, j'aurais bien aimé fournir une ontologie pour le jeu de rôle, et ce même si elle se révélait insuffisante pour modéliser Kernherd.

Exit donc le jeu de rôle. Je me rabats sur des ontologies plus généralistes qui auront le mérite de me permettre les mêmes petits exemples d'introduction accessibles à tous comme dans mon premier article sur le modèle entités-relations. Deux retiennent mon attention. Les autres ont l'air très (trop?) spécialisées dans la description des ressources web ( web sémantique ).

gist: the minimalist upper ontology est une ontologie généraliste écrite en OWL. Elle est également visionnable (uniquement dans Internet Explorer) à l'aide du plugin Visio pour ActiveX .

GUM (Generalized Upper Model) est également une ontologie généraliste, la version 2.0 est sous forme diagrammatique au format pdf tandis que la version 3.0 est écrite en OWL.

Problème: autant gist que GUM , les deux ontologies utilisent les types conjonctifs. Un type conjonctif est un type qui peut avoir 2 super-types ou plus. Or ma conception d'Eric 0.2 est simplissime: elle n'autorise qu'un unique super-type, il n'y aura pas de types conjonctifs. En vocabulaire de POO ( Programmation Orientée Objet ) on dirait qu'Eric 0.2 n'autorise que l'héritage simple alors que gist et GUM utilisent l'héritage multiple.

Solution: des deux ontologies GUM ( pdf ) est la plus petite et (de loin) la plus facile à visionner dans son intégralité. Je choisi GUM ( pdf ) et je décide de la reconcevoir afin d'éliminer les types conjonctifs. C'est assez facile pour les concepts car la majorité des types haut-placés dans la hiérarchie n'ont qu'un unique super-type. Ce sera plus délicat (ou plus dévastateur) pour les relations car elles utilisent intensément les types conjonctifs.

Une autre solution (qui vient en complément) consiste à concevoir ma propre ontologie de haut niveau sur la base de considérations purement sémantiques et/ou computationnelles (GUM est un peu trop philosophico-linguistique).

Une petite mise à jour avant le grand bond en avant.

Au programme de cette mise à jour :

Le développement de Eric va se poursuivre, la version actuelle est 0.1b

Le b de 0.1b ne signifie pas que c'est une version béta, pas plus que la version précédente n'était une version alpha. Pour mon développement en OCaml j'utilise la méthode quality first de Bertrand Meyer (dont la variante la plus simpliste est connue sous le nom de realease early / realease often ). J'incrémente le numéro de version pour les améliorations majeures, j'incrémente la lettre pour des améliorations plus mineures. 

Eric est maintenant fourni avec une coloration lexicale pour Crimson Editor et un fichier Eric.txt qui contient des exemples de code, coloriables avec Crimson Editor, à copier-coller dans la console. Si vous n'aimez pas votre console cmd.exe vous pouvez utiliser la console console2 .

Eric affiche de meilleurs messages d'erreur.

La nouveauté de cette version 0.1b ce sont les variables anonymes.

Quand une variable n'est pas utilisée dans le reste du graphe-motif on peut la laisser anonyme.

Désormais au lieu d'écrire :

select ([*liquid] Boil [*temp]).

Vous pouvez écrire :

select ([*] Boil [*]).

Vous obtenez alors la réponse :

([Liquid Azote] Boil [Celsius -196]).
([Liquid Water] Boil [Celsius 100]).

Au lieu de (avec l'ancienne version 0.1a) :

([Liquid Azote*liquid] Boil [Celsius -196*temp]).
([Liquid Water*liquid] Boil [Celsius 100*temp]).

En effet les variables liquid et temp ne sont jamais utilisées, alors à quoi bon les nommer ?

Zéro bugs découverts, Zéro bugs corrigés, zéro bugs connus. Le quality first au meilleur de sa forme.

À partir de maintenant le développement se poursuit vers la branche 0.2

Un prochain article décrira en détail l'évolution d'Eric vers la version 0.2a et, de façon plus générale, la question de savoir comment aborder sainement l'élaboration et l'évolution des logiciels complexes.

Après avoir présenté le modèle Entités-Relations , on présente deux opérations élémentaires sur ces diagrammes ainsi qu'un programme BDD ( Base De Données ) qui implante ces deux opérations.

Le programme éric

Eric (Entity-Relationship Interactive Calculator) est le petit frère de Georges .

Il est précompilé pour MS-Windows et Linux x86.

 La source est écrite en OCaml .

La jointure

C'est le mécanisme de base d'ajout dans la base de données.

Au lancement du programme la base est totalement vide.

La commande join permet d'ajouter des diagrammes dans la base.

join ([Cat] On [Mat]).

La BDD est irredondante, tout nouveau diagramme est jointuré avec les concepts et les relations nouvelles ou existantes.

Par exemple les deux commandes suivantes :

join ([Woman Sarah] SpouseOf [Man John]).
join ([Woman Sarah] ColleagueOf [Man John]).

Sont équivalentes à cette unique commande :

join ([Woman Sarah*w] SpouseOf [Man John*m]) (w ColleagueOf m).

Car les concepts de départ et d'arrivée des relations sont les mêmes.

La jointure s'effectue également sur les relations, il ne peut pas y avoir deux relations de même nom reliant les deux même concepts de départ aux deux même concepts d'arrivée.

La sélection

C'est le mécanisme de base de la requête dans la base de données.

Seuls les concepts peuvent être variables, on reconnaît une variable-concept à ce qu'elle a un marqueur mais pas d'étiquette. La recherche tente d'associer une étiquette-concept à chaque variable-concept de sorte que le (ou les) graphe résultant soit dans la base de données. Les relations ne sont jamais des variables, ce sont toujours des constantes.

join ([Liquid Water] Boil [Celsius +100]).
join ([Liquid Azote] Boil [Celsius -196]).

select ([*liquid] Boil [*temp]).

Renvoie toutes les températures d’ébullition connues.

select ([*w] ColleagueOf [*m])(w SpouseOf m).

Renvoie toutes les personnes w et m qui sont à la fois collègues et époux.

select
  ([Believe *b] Experiencer [*t])
  (b Theme [Proposition *p])
  (p Statement [Want *w])
  (w Experiencer [*e])
  (w Theme [Situation *s])
  (s Description [Marry *m])
  (m Agent e).

Renvoie toutes les personnes t qui pensent qu'une personne e veut se marier (on ne demande ni avec qui, ni où, ni quand).

Renvoie tous les verbes de la contine de la souris verte :

select
  ([*v0] Then [*v1])
  (v1 Then [*v2])
  (v2 Then [*v3])
  (v3 Then [*v4])
  (v4 Then [*v5])
  (v5 Then [*v6])
  (v6 Then [*v7])
  (v7 Then [*v8])
  (v8 Then [*v9]).

Où l'on voit que le temps de recherche reste raisonnable malgré l'abondance de concepts variables

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

Sauvegarder

La commande save sauvegarde la base de donnée en cours dans le fichier BDD indiqué.

save "database.eric".

Le chemin d'accès doit toujours avoir le caractère / comme séparateur et ce même sous MS-Windows. Par exemple save "F:/Concept graphs/BDD.eric". est une commande valide tandis que save "F:\Concept graphs\BDD.eric". est une commande invalide.

Charger

La commande load efface la base de données en cours et charge le fichier BDD indiqué.

load "database.eric".

Les fichiers BDD sont portables de Windows 32bits vers Linux 32bits et vice-versa. Pour une portabilité 64bits il faudrait recompiler la source.

Quitter

La fonction la plus importante de tout programme

quit.

Le méta-modèle

Le méta-modèle entités/relations c'est le modèle exprimé dans son propre formalisme. Il est extrêmement compact.

join
  ([Definition *def] Of [EntityRelationGraph])
  ([Set V *setV] RequiredBy def)
  ([Set E *setE] RequiredBy def)
  (setV Of [Vertex *v])
  (setE Of [Edge *e])
  (e Origin v)(e Destination v)
  (v LabelledWith [Concept])
  (e LabelledWith [Relation]).

Accessoirement le méta-modèle est aussi un schéma de conception pour l'implantation de Eric.

Conclusion

On a présenté un langage aussi élémentaire que possible pour la modélisation des connaissances ainsi qu'une implantation simple et efficace de ce langage.

De nombreuses extensions et variantes sont possibles pour ajouter de l'expressivité et/ou du raisonnement (assisté ou automatisé) à notre modèle de base.

Le développement d'Eric continue .

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]).

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)

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

Pas forcément une phrase par jour mais forcément un jour par phrase.

Sauf indication contraire l'auteur est le posteur. Deviens toi aussi un free-posteur en postant ta propre phrase du jour.

La construction européenne est une grande entreprise de démolition.

Une page cachée de mon site orange, extraite de ma correspondance avec Zeami .

Un coeur pour t'aimer

Un coquillage pour rêver

Une rose pour te garder

Un mouchoir pour pleurer