Modélisation des données Un langage pour décrire INVARIANT, PRE-CONDITION, EXPRESSION Concepts...

Modélisation des données

Un langage pour décrire INVARIANT, PRE-CONDITION, EXPRESSION

Concepts et notations utilisés Logique Ensembles Relations binaires et fonctions Arithmétique Suites Arbres

Logique : connecteurs

ET (ASCII : &) OU (ASCII : or)  NON (ASCII : not) SI-ALORS (ASCII : =>)  EQUIV. (ASCII : <=>)

Logique : quantificateurs

Universel listeDeVariables . (P Q) (ASCII : !) x,y . (x NAT y NAT

x=quantite(y) x≥0) Existentiel

listeDeVariables . (P) (ASCII : #) x . (x NAT x=0)

Logique : prédicat = et couple

Égalité = ≠ (/= en ASCII).

Couple (a,b) (en B symbole maplet |-> : a|->b)

Ensemble : désignation

Extension E={1,3,5,7,9}

Compréhension E={x | x Z x>0 x<10 x mod 2 =1}

L’ensemble vide {}

Ensemble : les prédéfinis

N les entiers naturels (NATURAL en ASCII) N* les entiers naturels non nuls (NATURAL1 en ASCII) Z les entiers relatifs (INTEGER en ASCII) I..J les intervalles d’entier, l’ensemble des valeurs

comprises entre I et J (bornes incluses) INT les entiers relatifs implantables : MININT..MAXINT NAT les entiers naturels implantables : 0..MAXINT NAT1 les entiers naturels non nuls implantables :

1..MAXINT BOOL les booléens = {FALSE,TRUE}

bool(P) retourne le booléen résultat d’une formule FOL STRING l’ensemble des chaînes de caractères.

Ensemble : les prédicats

x E  (: en ASCII) E1 E2 (<: en ASCII, notée <<:) E1 x E2 (* en ASCII)

Produit cartésien non commutatif a|->b ≠ b|->a

P(E)  (POW en ASCII) Négation des prédicats par le symbole /

devient /: en ASCII

Ensembles : les opérateurs

l’union E1 E2 (\/ en ASCII) l’ensemble des éléments appartenant à E1 ou E2

l’intersection E1 E2 (/\ en ASCII) l’ensemble des éléments appartenant aux deux

ensembles E1 et E2 la différence E1 - E2

l’ensemble des éléments appartenant à E1 mais pas à E2 choice(E)

un élément indéterminé de l’ensemble E

Relations binaires: vocabulaire

r est un sous-ensemble du produit cartésien D x A de deux ensembles D : ensemble de départ A : ensemble d’arrivée

Soit un couple d|->a d’une relation r a est une image de d par r d est un antécédent de a par r

Relations binaires : déclaration

r D x A ou r P(D x A) ou

r D↔A r est une relation de D dans A D↔A désigne l’ensemble de toutes les

relations de D vers A D↔A = P(D x A)

noté <-> en ASCII

Relations binaires : les opérateurs

Soit r D↔A Le domaine : dom(r)

l’ensemble des éléments de D qui ont une image par r

{d | dD a.(aA (d,a)r)} Le co-domaine (« range ») : ran(r)

l’ensemble des éléments de A qui ont un antécédent par r

{a | aA d.(dD (d,a)r)}

Relations binaires : les opérateurs

Soit r D↔A et q A↔C l’inverse : r-1 (r~ en ASCII)

la relation de A↔D définie par {(a,d) | (a,d)AxD (d,a) r}

la composition : r;q la relation de D↔C définie par {(d,c) | (d,c)DxC a.(a A (d,a) r (a,c) q)} l’ensemble d’arrivée de r doit être identique à celui de

départ de q la relation identité sur un ensemble : id(D)

la relation de D↔D définie par {(d,a) | (d,a)DxD d=a}

Relations binaires : les opérateurs

Soit r D↔A et ED et BA la restriction de domaine : Er (<| en ASCII)

la relation incluse dans r définie par {(d,a) | (d,a)r d E} ;

la co-restriction : rB (|> en ASCII) la relation incluse dans r définie par {(d,a) | (d,a)r a B} ;

l’anti-restriction : Er (<<| en ASCII) la relation incluse dans r définie par {(d,a) | (d,a)r dE}

l’anti-co-restriction : rB (|>> en ASCII) la relation incluse dans r définie par {(d,a) | (d,a)r aB}

Relations binaires : les opérateurs

Soit rD↔A et pD↔A L’image relationnelle : r[E]

l’ensemble des images des éléments de E par r {a | aA d.(dE (d,a)r)}

La surcharge : r<+p l’écrasement de la relation par la relation p {(d,a) | (d,a)DxA ((d,a)p

(ddom(p) (d,a)r))}

Relations binaires : les opérateurs

Soit rD↔A et sD↔F et qA↔C Le produit direct : rs (>< en ASCII)

la relation définie par {(d,(a,f)) | (d,(a,f))Dx(AxF) (d,a)r (d,f)s}

La première projection : prj1(D,A) la relation qui envoie chaque couple du produit cartésien de

deux ensembles sur le premier élément du couple {((d,a),j) | ((d,a),j)(DxA)xD j=d}

La deuxième projection: prj2(D,A) la relation qui envoie chaque couple du produit cartésien de

deux ensembles sur le deuxième élément du couple {((d,a),j) | ((d,a),j)(DxA)xA j=a}

Le produit parallèle : s||q la relation définie par {((d,a),(f,c)) | ((d,a),(f,c))(DxA)x(FxC) (d,f)s (a,c)q}.

Relations binaires

5 opérateurs suffisent à construire tous les autres dom -1 ; id

Exemples : ran(r) = Er = r[E] = r<+p =

Fonctions : 4 caractéristiques

la fonctionnalité (->) tout élément de l’ensemble de départ a au plus une image

la totalité (non totalité +-) tout élément de l’ensemble de départ a au moins une image

l’injectivité (>-) tout élément de l’ensemble d’arrivée a au plus un antécédent

la surjectivité (->>) tout élément de l’ensemble d’arrivée a au moins un antécédent

Fonctions : 8 catégories

les fonctions partielles (quelconques) D+->A les fonctions totales D-->A les injections partielles D>+>A les injections totales D>->A les surjections partielles D+>>A les surjections totales D-->>A les bijections partielles D>+>>A les bijections totales D>->>A

Inclusion des ensembles de relations et fonctions

D↔A

D-->A

D+->A

D>+>A D+>>A

D-->>A

D>+>>A

D>->>A

D>->A

Relations et fonctions

La relation est la notion la plus générale. La fonction est un cas particulier

En général une fonction est partielle Une fonction totale est un cas particulier

En général une fonction a pour inverse une relation

une injection a pour inverse une fonction

Toujours essayer de mettre le « côté » le plus contraint à « gauche »

Fonctions : nouveaux opérateurs

l’image fonctionnelle d’un élément : f(x) f doit être une fonction x doit appartenir à son domaine

fonctions abstraites (lambda expressions) : x.(xD | e) D est le domaine de définition de la fonction e une expression paramétrée par x définissant

l’image pour tout x de D ( noté % en ASCII)

Arithmétique des entiers

Les comparateurs <, >, , (<= et >= en ASCII)

Les opérateurs binaires +, -, *, / (la division entière) mod (le modulo) xy (x**y en ASCII)

Les opérateurs unaires succ, pred

Arithmétique des ensembles

L’opérateur card(E) Le nombre d’éléments d’un ensemble

Les opérateurs max(E) et min(E) Prennent un ensemble d’entiers non vide en paramètre Retourne l’entier le plus grand (resp. le plus petit) de

l’ensemble Les opérateurs et (SIGMA et PI en ASCII)

Calculent la somme (le produit) d’expressions arithmétiques (x,y…).(P | E)

P est une formule de la logique des prédicats et E une expression arithmétique (P et E dépendant des variables x,y…)

Somme pour toutes valeurs de variables x,y… satisfaisant P des expressions E correspondants aux valeurs des variables

Application à la modélisation

Description de parenté entre personnes 1. Personne ne peut être en même temps un homme

et une femme.2. Cependant on est un homme ou on est une femme.3. Seules les femmes ont des époux, qui sont des

hommes.4. Les femmes n’ont qu’un seul époux.5. Une épouse d’un homme est une femme dont cet

homme est l’époux.6. Les hommes n’ont qu’une seule épouse.7. Les mères sont des femmes mariées.8. Par définition, le père est l’époux de la mère.

Formalisation

Soit un ensemble abstrait PERSONNE On introduit les concepts homme, femme,

époux, mère

homme PERSONNE

femme = PERSONNE – homme

aPourEpoux femme +-> homme

aPourMère PERSONNE +->dom(aPourEpoux)

Formalisation

Modéliser les concepts aPourEpouse aPourConjoint personneMariée mère aPourPère, père aPourParent, parent aPourEnfant, enfant, aPourFille aPourFrereOuSoeur, aPourFrere aPourBeauFrereOuBelleSoeur aPourNeveuOuNiece aPourOncleOuTante aPourCousin …