Différences

Ci-dessous, les différences entre deux révisions de la page.

--- tc_info:cm5 [2018/12/04 10:42] – edauce
+++ tc_info:cm5 [2024/06/28 15:18] (Version actuelle) – modification externe 127.0.0.1
@@ Ligne 1: / Ligne 1: @@
+==== CM5 : Indexation / Modèle relationnel ====
+=====5. L'indexation=====
+<note tip> **Rappel **
+Une //donnée informatique// est un élément d'information ayant subi un encodage numérique
+    * Consultable/manipulable/échangeable par des programmes informatiques
+    * Possibilité de la conserver sur un support de stockage numérique (CD-ROM, disque dur, SSD, ...)
+      * Les informations peuvent être stockés dans un fichier (ex : fichier csv).
+    * Un jeu de valeurs encodé et enregistré est appelé un //enregistrement//
+</note>
+==== 5.1 Généralités ====
+Pour une gestion efficace des données, il est nécessaire de pouvoir identifier chaque enregistrement de façon unique.
+L'indexation des données repose sur un principe simple d'étiquetage consistant à attribuer une étiquette différente à chaque enregistrement. Cette étiquette peut être une suite de caractères arbitraires, un entier, ou un descripteur explicite. On parle en général de **clé** ou d'**identifiant** pour désigner cette étiquette.
+  * L'**indexation** des données consiste  à attribuer à chaque donnée distincte un **identifiant** unique.
+  * On parle également  de //clé// de l'enregistrement:
+On peut représenter l'opération d'indexation sous la forme d'une fonction. Si  $d$  est le jeu de valeurs,  $k(d)$  désigne l'identifiant de ce jeu de valeurs.
+=== Unicité ===
+<note important>
+  * soient  $d_1$  et  $d_2$  deux enregistrements,
+  * si  $k(d_1) = k(d_2)$ , alors  $d_1=d_2$ .
+</note>
+=== Efficacité ===
+L'existence d'un identifiant unique pour chaque jeu de valeurs  $d$  permet la mise en œuvre d'une //recherche par identifiant// (ou recherche par clé).
+La recherche par identifiant repose sur une fonction d'adressage  $I$  qui à tout identifiant  $k$  associe sa position (entrée)  $i$   dans un tableau de données:  $I : k \rightarrow i$ .
+Ainsi si  $k$  est l'identifiant servant à la recherche, l'extraction des informations se fait en 2 étapes:
+  *  $i = I(k)$  (lecture de l'index des données)
+  *  $d = D[i]$  (lecture des données elles mêmes)
+<note tip>
+La lecture de l'index repose sur le parcours d'une liste
+ $L = ((k_1, i_1), (k_2, i_2), ..., (k_N, i_N))$  telle que  $k_1 < k_2 < ... < k_N$ , de telle sorte que la recherche s'effectue en O(log N) (recherche dichotomique).
+</note>
+=== Compacité ===
+L'identifiant doit en pratique tenir sur un nombre d'octets le plus petit possible pour que la liste  $L$  puisse être manipulée en mémoire centrale. Autrement dit, il faut que :
+  *  $|k| << |d|$
+pour que :
+  *  $|L| << |D|$
+<note tip>
+Un identifiant entier, codé sur 4 octets, permet d'indexer jusqu'à  $2^{4 \times 8} \simeq 4\times10^9$  données différentes.
+</note>
+=== Utilisation ===
+** Définir un ordre sur les données **
+La présence d'un identifiant permet de définir un ordre total sur les données :
+  * ordre sur les entiers (identifiant entier)
+  * ordre alphabétique (identifiant texte)
+  * ordre //ASCII//bétique (chaîne de caractères quelconque)
+** Lier les données **
+Dans le cas des bases de données, l'identifiant constitue une //référence// vers les jeux de valeurs des tableaux de données. Une référence permet de //lier// les données d'une table aux données d'une autre table.
+__Exemple :__
+  * {{http://edauce.perso.centrale-marseille.fr/visible/Artists.csv|Artistes}}
+  * {{http://edauce.perso.centrale-marseille.fr/visible/Albums.csv|Albums}}
+  * {{http://edauce.perso.centrale-marseille.fr/visible/Track.csv|Pistes}}
+  * Pour chaque album de la table des albums, l'identifiant d'artiste (ici un numéro) permet de lier l'album avec l'artiste (ou groupe) correspondant.
+  * Pour chaque piste de la table des pistes,  l'identifiant d'album permet de lier la piste à l'album correspondant (et donc à l'artiste correspondant par transitivité)
+<note>
+**Exercice** : donner le nom du groupe qui interprète la piste '//Paradise City//'.
+</note>
+** Structure d'ensemble **
+L'index définit l'//appartenance// d'une donnée à un ensemble.
+Soit  $\mathcal{E}$  un //ensemble// de données indexées :
+ $\mathcal{E} = \{d_1, d_2, ..., d_K\}$
+On a l'équivalence :
+ $d \in \mathcal{E} \Leftrightarrow k(d) \in I$
+Ainsi, il ne peut y avoir de doublon car  $\forall d$  :
+  *  $k(d)$  est unique
+  *  $i = I(k(d))$  est unique ssi  $d \in \mathcal{E}$  et indéfini sinon.
+==== 5.2 Exemples d'indexation des données ====
+=== 5.2.1 Adressage des tableaux ===
+L'exemple le plus simple d'indexation est celui fourni par les **numéros de case** d'un tableau.
+  * Soit  $D$  un tableau de  $n$  lignes
+  * le numéro  $i < n$  est à la fois l'identifiant et l'//entrée// (ou //adresse//) de la ligne  $D[i]$
+{{https://wiki.centrale-marseille.fr/informatique/_media/public:std-3:cm1:aspect_physique:s7_index.png}}
+=== 5.2.2 Maintenance centralisée d'un index===
+**Dans le cas général, l'identifiant n'est pas égal à l'entrée!**
+On sépare donc l'index  $k$  de l'entrée  $i$ :
+  *  $k$  est l'identifiant (ou clé) de la donnée  $d$ . Il s'agit d'une valeur numérique quelconque.
+  *  $i$  est l'entrée de la donnée  $d$ , correspondant à sa position dans le tableau de données.
+<note important>
+Lors de l'ajout de nouvelles données, il est nécessaire de définir une méthode permettant d'assurer:
+  * l'//intégrité// de l'index
+  * l'unicité de l'identifiant
+</note>
+Il existe différentes méthodes permettant d'assurer l'intégrité de l'index:
+  * Le programme maintient une liste triée des identifiants déjà utilisées. Lors de l'ajout d'une nouvelle donnée, il s'assure que l'identifiant n'est pas déjà présente dans la liste.
+    * Coût :
+      *  $O(n)$  en mémoire
+      *  $O(\log n)$  pour l'ajout
+  * Dans le cas où les identifiants sont des numéros (entiers), il est possible d'utiliser un compteur qui s'incrémente à chaque nouvelle insertion.
+    * Coût :
+      *  $O(1)$  en mémoire
+      *  $O(1)$  pour l'ajout
+<note>
+**Exemples d'indexation centralisée** :
+  * numéro INE (étudiants)
+  * numéro URSSAF (sécurité sociale)
+  * numéro d'immatriculation (véhicules)
+  * numéro de compte en banque
+  * code barre
+  * etc.
+</note>
+=== 5.2.3 Indexation pseudo-aléatoire : les fonctions de hachage ===
+Utilisation d'une //fonction de hachage// :
+  * qui "calcule" la valeur de l'identifiant à partir des valeurs du jeu de valeurs à insérer.
+  * La fonction de hachage doit être telle que la probabilité de choisir le même identifiant pour deux données différentes soit extrêmement faible.
+Attribution d'un identifiant arbitraire entre 0 et n-1
+  * Etape 1 : **transcodage** binaire des données
+      * ''i = int.from_bytes(d, byteorder='big')''
+      * avantage : les données différentes ont un code entier différent
+      * mais : |i| = |d|
+<code python>
+s = 'paul.poitevin@centrale-marseille.fr'
+d = bytes(s, 'ascii')
+i = int.from_bytes(d, byteorder='big')
+print("i =", i)
+</code>
+donne :
+<code>
+i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058
+</code>
+  * Etape 2 : **réduction** du code
+    * __Méthode 1__ : le modulo n (reste de la division entière par n)
+      * ''k = H(i) = i mod n''
+      * Avantage :
+        *   $|k| << |d|$
+      * Inconvénient:
+        * deux données différentes peuvent avoir le même code
+        * ce codage revient à sélectionner les bits de poids faible
+        * deux données proches ou très similaires auront un index proche ou similaire : si ''j = i + 1'', ''H(j) = H(i) + 1'' (presque toujours)
+        * ---> il faut prendre n //premier//
+  *
+    *
+      *  $n = 2^{32} = 4294967296$  :
+        * H_code(''paul.poitevin@centrale-marseille.fr'') = ''1697539698''
+        * H_code(''martin.mollo@centrale-marseille.fr'') = ''1697539698''
+      *  $n = 67280421310721$  (premier):
+        * H_code(''paul.poitevin@centrale-marseille.fr'') = ''36148249469507''
+        * H_code(''martin.mollo@centrale-marseille.fr'') = ''65330032132071''
+  *
+    * __Méthode 2__ : combiner produit et modulo -- soient m et n deux nombres premiers entre eux
+      * ''k = H(i) = (i * m) mod n''
+      * Avantage :
+        *  $|k| << |d|$
+        * deux entiers proches donneront auront des codes très différents :  si ''j = i + 1'', ''j * m - i * m = m''
+      * Inconvénient :
+        * deux données différentes peuvent avoir le même code
+          * le produit ''i * m'' peut etre coûteux à calculer
+    * __Méthode 3__ : Hachage cryptographique :
+      * Le hachage cryptographique est construit de telle sorte qu'il soit très difficile de trouver un entier ''j != i'' tel que ''H(i) = H(j)''.
+      * Un tel code est appelé une "signature".
+        * Exemples :
+          * {{https://fr.wikipedia.org/wiki/MD4|MD4}}
+          * {{https://fr.wikipedia.org/wiki/Secure_Hash_Algorithm|SHA}}
+=== Exemple ===
+Le gestionnaire de bases de données {{https://openclassrooms.com/fr/courses/1915371-guide-de-demarrage-pour-utiliser-mongodb|MongoDB}} utilise une indexation des données par clé cryptographique.
+==== 5.3 Généralisation : multi-indexation ====
+<note tip>
+TODO
+</note>
+==== 5.4 Structures de données pour l'indexation ====
+=== 5.4.1 Liste triée ==
+<note tip>
+TODO
+</note>
+=== 5.4.2 Index bitmap ===
+<note tip>
+TODO
+</note>
+=== 5.4.3 Les B-arbres ===
+Que faire lorsque l'index ne tient pas en totalité dans la mémoire centrale ?
+  * L'index est découpé en "blocs"
+  * Les blocs sont organisés sous la forme d'un arbre (B-arbre = "//Balanced Tree//")
+Considérons un index composé de couples (clé, numero de page). On suppose que l’index est également découpé en pages, chaque page d'index contenant au maximum b clés. Si l’index comporte beaucoup de pages, il est intéressant de l’organiser hiérarchiquement en pages et sous-pages, selon une organisation appelée "B-arbre" (//Balanced Tree//):
+{{ restricted:std-3:td1:b-tree.png}}
+  * chaque noeud de l’arbre contient une liste croissante de couples (clé, numéro d’une sous-page)
+  * chaque clé est dupliquée dans sa sous-page :
+        * les clés contenues dans la sous-page sont inférieures ou égales à elle,
+        * les clés contenues dans la sous-page sont strictement supérieures à celles de la sous-page précédente.
+        * les feuilles contiennent des couples (clé, numéro de la page du tableau de données)
+<note> **algo : lecture de l'Index**
+  * paramètre d’entrée : k
+  I ← charger la racine de l’arbre
+  tant que I n’est pas une feuille :
+    k’ ← première clé de I
+    tant que k > k’
+      k’ ← clé suivante
+    I ← charger sous-page de k’
+</note>
+Remarque : Pour que l’accès aux données soit efficace,
+  * il faut que l’arbre soit le moins profond possible : arbre “équilibré”.
+  * Dans ce cas,
+    * chaque noeud a ''b'' fils,
+    * et la profondeur de l’arbre est de l’ordre de logb(N).
+  * Pour charger la page contenant le tuple cherché,
+    * il faut donc logb(N) + 1 lectures sur disque.
+    *
+En pratique, il existe des algos permettant d’assurer que chaque noeud contient entre b/2 et b clés (sauf la racine).
+<note tip>
+Voir :
+  * http://fr.wikipedia.org/wiki/Arbre_B
+  * http://en.wikipedia.org/wiki/B-tree)
+</note>
+===== 6. Le modèle relationnel =====
+On introduit dans ce chapitre le **modèle relationnel** qui sert de fondation à la conception de bases de données.
+Les différents modèles utiles en représentation des connaissances reposent sur des notions de base de la théorie des ensembles :
+    * Ensemble finis
+    * Éléments partiellement (ou totalement) discernables
+==== 6.1 Schéma de données ====
+<note tip>
+**//Rappel// : Organisation des données sous forme de tableaux bidimensionnels **
+** Schémas de données **
+  * Un enregistrement est un jeu de valeurs organisé sous forme de **tuple**
+  * A un tuple on associe  en général  un **schéma de données**.
+{{public:std-3:cm1:s7_schema.png}}
+  * Définir un **schéma** consiste à définir :
+    * une liste d'attributs (labels) associées à chacune des valeurs du tuples.
+  * A chaque **attribut** correspond :
+    * un //intitulé//
+    * un //domaine// de valeurs (type/format des données)
+** Tableau de données **
+Un tableau de données est une liste (finie et ordonnée) de tuples, chaque tuple obéissant à un même schéma  $R$ .
+{{https://wiki.centrale-marseille.fr/informatique/_media/public:std-3:cm1:s7-tableau-data.png}}
+</note>
+  * Soit  $R(A_1, ..., A_m)$  un schéma.
+  * On note  $\text{dom}(A_i)$  le domaine associé à l'attribut  $A_i$ .
+  * On dit d'un tuple  $t$  qu'il //obéit au schéma  $R$ // si les valeurs qu'il contient correspondent aux domaines des attributs du schéma.
+<note>
+** Diverses représentations :**
+__[[public:STD-3:CM1:Aspect logique:2.2.2 Relation:Ensembles d'entités et schémas d'ensembles|Entité/association]]__ :
+{{public:std-3:cm1:s7-schema-merise.png}}
+__[[public:mco-2:paradigme_objet_et_modelisation_uml|UML]]__ :
+{{public:std-3:cm1:s7_schema_uml.png}}
+__[[public:STD-3:CM1:Aspect logique:2.2.2 Relation|Schéma relationnel]]__ :
+**Client**(nom, prénom, adresse, âge)
+</note>
+<note>
+** __Exemples de schémas relationnels__ :**
+**Étudiant**(nom, prénom, adresse, INE)
+**Ouvrage**(titre, auteur, éditeur, prix, date_édition)
+**Véhicule**(immatriculation, marque, modèle, couleur)
+</note>
+=== 6.1.1 Entité et attributs===
+  * Une **entité**  $x$
+    * est une représentation d'un objet du monde réel,
+    * appartenant au système/à l'organisation modélisée.
+  * Une entité est décrite par une ou plusieurs valeurs caractéristiques, appelées **attributs**.
+<note important>
+Les informations conservées au sujet des entités d'un ensemble sont les **attributs**.
+  * Chaque **attribut** :
+    * a un **nom** unique dans le contexte de cet ensemble d'entités :  $A$ ,  $B$ ,  $C$ ,  $A_1$ ,  $A_2$ , ...,  $A_m$ , ...
+      * Exemples de noms concrets : //couleur//, //nom//, //horaire//, //salaire//.
+    * prend ses valeurs dans un domaine bien spécifié,
+      * également appelé le **type** de l'attribut.
+      * Le domaine d'un attribut est noté  $\text{dom}(Aj)= Dj$ .
+        * Exemples :
+          *  $\text{dom}(couleur)={rouge, vert, bleu, jaune}$ ,
+          *  $\text{dom}(nom) =$ ensemble des chaînes de caractères,
+          *  $\text{dom}(salaire) =$  entiers naturels
+          * etc...
+    * Un attribut  $A_j$  est une fonction à valeur sur  $D_j$  :
+ $A_j :  E  \rightarrow D_j$
+ $x \mapsto   A_j(x)$
+</note>
+    * Un attribut peut être :
+      * simple ou composé.
+        * Exemple :  une //adresse// peut être décrite par une simple chaîne de caractères, ou peut être décomposée en //rue// , //no//, //boîte//, //ville//, //code postal//, //pays//.
+      * obligatoire ou facultatif ( $D_j$  peut ou non contenir la valeur ø ).
+      * atomique ou non (Un attribut peut posséder 0, 1 voire plusieurs valeurs...)
+=== 6.1.2 Ensembles d’entités et schéma d’ensemble===
+Un **ensemble d'entités** est un ensemble fini d'éléments :
+ $E = \{x_1,…,x_n\}$
+Il regroupe (ou associe) plusieurs entités ayant des caractéristiques communes (descriptibles à l'aide du même ensemble d'attributs).
+<note tip>
+**Exemples** :
+  * les employés d'une firme,
+  * les cours de Centrale Méditerranée,
+  * une collection de disques,
+  * etc…
+</note>
+  * Les éléments d’un ensemble d’entités sont //partiellement discernables// à travers les valeurs de leurs attributs :
+    * les attributs  $(A_1,...,A_m)$  servent à décrire les éléments de l’ensemble.
+    * Le schéma  $R$  de l’ensemble  $E$  est une //application// de l'ensemble d'entités vers l'ensemble des tuples de schéma  $R$
+      * Soit :
+ $R : \mathcal{X} \rightarrow D_1 \times ... \times D_m$
+ $x_i \mapsto (A_1(x_i),…, A_m(x_i))$
+<note tip>
+** représentation graphique ** :
+{{public:std-3:cm1:s7-entite-0.png}}
+</note>
+<note>
+** Exemples **:
+{{public:std-3:cm1:s7-entite-01.png}}
+</note>
+=== 6.1.3 Relation ===
+La **Relation** est la représentation logique d'un **tableau de données**.
+<note important>
+**Tableau de données**
+Un tableau de données est une liste (finie et ordonnée) de tuples, chaque tuple obéissant à un même schéma  $R$ .
+{{https://wiki.centrale-marseille.fr/informatique/_media/public:std-3:cm1:s7-tableau-data.png}}
+</note>
+<note important>
+**Définition**
+Soit  $R = (A_1,...,A_m)$  un schéma de données
+Une **relation**  $r$  obéissant au schéma  $R$  est un //sous-ensemble du produit cartésien//  $\text{dom}(A_1) \times ... \times \text{dom}(A_m)$
+</note>
+<note tip>
+**Corollaire** : une relation est un **ensemble** de tuples :
+ $r = \{t_1, ..., t_n\} = \{ (a_{11}, ..., a_{1m}), ..., (a_{n1}, ..., a_{nm})\}$
+  * avec :
+    *  $\forall (i,j), a_{ij} \in \text{dom}(A_j),$
+    *  $\forall i, t_i \in \text{dom}(A_1) \times ... \times \text{dom}(A_m)$
+    *  $n$  : nombre de tuples
+    *  $m$  : nombre d'attributs par tuple
+</note>
+<note tip>
+**Remarque :**
+  * Le **schéma**  $R$  représente le niveau abstrait (modélisation)
+  * La **relation**  $r$  représente un cas concret de réalisaton (à un schéma  $R$  peuvent correspondre une infinité de réalisations possibles :  $r$ ,  $r'$ ,  $r''$ , etc. )
+</note>
+==== 6.2 Dépendances fonctionnelles ====
+  * Au sein d'un schéma  $R$ ,
+    * Il peut exister un ensemble de contraintes, noté  $F$ ,
+      * portant sur les attributs (plus précisément sur les valeurs prises par les attributs).
+      * L'ensemble F est indépendant de R.
+    * On parle de **contraintes d’intégrité**.
+      * Ces contraintes s’expriment sous la forme de **dépendances fonctionnelles**.
+<note>
+**Rappels d’algèbre de base:**
+  * **Relation binaire** : une relation binaire  $r$  portant sur deux domaines  $A$  et  $B$ :
+    * est un sous-ensemble du produit cartésien  $A \times B$ .
+    * si  $(a,b) \in r$ , on note parfois  $a r b$  ce qui signifie “a est en relation avec b”.
+  * **Fonction** : une fonction  $f : A \rightarrow B$  est une relation binaire sur  $A \times B$  telle que
+    * pour tout  $a \in A$ ,
+    * il existe un unique  $b$  tel que  $(a,b) \in f$ .
+    * On note  $b=f(a)$  ,
+      * ce qui signifie qu'au sein de la relation  $f$ ,  $b$  est déterminé de façon unique par le choix de  $a$  (autrement dit : “b dépend de a”)
+</note>
+<note important>
+**Dépendance fonctionnelle**
+  * Soit  $r$  une relation définie selon  $R(A_1,...,A_m)$
+  * Soient  $X$  et  $Y$  deux sous-ensembles de  $R$
+  * On dit que la relation  $r$  définit une //dépendance fonctionnelle// de  $X$  vers  $Y$ ,
+    * notée  $X \stackrel{r}{\rightarrow} Y$
+    * si les valeurs de  $r$  permettent de définir une fonction de  $d(X)$  vers  $d(Y)$ .
+</note>
+<note tip>
+**__Exemple 1__** :
+Soit la relation  $r$ :
+^ A ^ B ^ C ^
+| 1 | a | e |
+| 2 | b | f |
+| 2 | c | f |
+| 3 | d | k |
+| 4 | d | k |
+  * On a les dépendances suivantes :
+    *  $A \rightarrow C$
+    *  $B \rightarrow C$
+    * mais pas :  $A \rightarrow B$ ,  $B \rightarrow A$ , ni  $C \rightarrow A$
+  * On a aussi :
+    *  $A,B \rightarrow C$
+    * mais pas :  $B,C \rightarrow A$ , ni  $A,C \rightarrow B$ , etc.
+</note>
+<note tip>
+**__Exemple 2__** :
+  * Soit le schéma :
+    * **Commande** (num_client, quantité, prix, date, num_article)
+  * et l’ensemble de contraintes
+$$ \begin{array}{rl}F &= \{\\
+    & \text{num_client, date} \rightarrow \text{num_article, quantité, prix} \\
+    & \text{num_article, quantité} \rightarrow \text{prix} \\
+    &\}
+    \end{array}
+$$
+  * La première contrainte indique qu'il ne peut y avoir deux factures émises pour un même client à une date donnée.
+  * La seconde contrainte indique que le prix payé dépend de l’article et de la quantité commandée.
+</note>
+<note tip>
+**__Exemple 3__** :
+  * Soit le schéma :
+    * **Ouvrage** (titre, auteur, éditeur, prix, date_edition)
+  * et la contrainte :
+    * {titre, auteur, éditeur →  prix, date_édition}
+La contrainte signifie :
+  * “//pour une oeuvre chez un certain éditeur, une seule édition est possible (pas de réédition à une date ultérieure)//”
+  * “//politique du prix unique//”
+</note>
+<note>
+**Exercice :**
+Soit le schéma :
+  *  **Réservation**(code_appareil, date, heure, salle)
+Exprimer la dépendance fonctionnelle :
+  * « //Un appareil ne peut pas être utilisé dans deux locaux différents au même moment //»
+</note>
+  * Il importe donc de bien réfléchir, au moment de l'étape de conception,
+    * du réalisme et du caractère limitant de certaines dépendances fonctionnelles,
+    * et du caractère éventuellement limitant du choix des attributs.
+  * Ainsi, le schéma décrivant les commandes (exemple 2)
+    * ne permet pas de commander des articles de nature différente au sein d'une même commande
+    * (un client, pour commander deux râteaux et une truelle, doit donc effectuer deux commandes, qui plus est à des dates différentes!).
+<note> ** Exercice **
+Soit le schéma relationnel suivant :
+**Billet**(num_train, type_train, num_voiture, num_place, date, id_passager, nom_passager, prénom_passager, date_naissance, gare_départ , horaire_départ, gare_arrivée, horaire_arrivée, classe, tarif)
+Définir des dépendances fonctionnelles sur cet ensemble d'attributs
+</note>
+====6.3 Clé d'une relation====
+=== 6.3.1 Définitions ===
+  * Soit un schéma  $R(A_1, ..., A_m)$ .
+<note important>
+**Clé**
+  * Une **clé**  $K$  :
+    * est un ensemble **minimal** d'attributs inclus dans R,
+    * tel que toute relation  $r$  de schéma  $R$  définit une dépendance fonctionnelle de  $d(K)$  dans  $d(R)$ ,
+  * cette dépendance est notée  $K \rightarrow R$ .
+</note>
+<note>
+  * **Remarques** :
+    * Si un schéma  $R$  possède une clé  $K$ , alors tous les éléments d’une relation  $r$  de schéma  $R$  sont discernables : la valeur de la clé permet d’identifier de façon unique chaque élément de l’ensemble.
+    * Au sein d'un schéma, il est souvent possible de définir plusieurs clés à partir des attributs. Le concepteur du modèle choisit une clé parmi les clés possibles. Cette clé est appelée **clé primaire**.
+    * Graphiquement, les attributs constituant la clé sont __soulignés__:
+{{public:std-3:cm1:s7-cle-0.png}}
+</note>
+<note>
+**__Exemple 1__** :
+{{public:std-3:cm1:s7-cle-01.png}}
+</note>
+<note>
+**__Exemple 2__** :
+{{public:std-3:cm1:s7-cle-02.png}}
+  *Pour certains schémas,
+    * il est courant de définir comme clé un entier **identifiant de façon unique** chaque élément de l'ensemble (appelé identifiant ou “Id”).
+    * La clé est alors constituée de cet attribut unique.
+{{public:std-3:cm1:s7-cle-03.png}}
+**Représentation [[public:mco-2:paradigme_objet_et_modelisation_uml|UML]] **:
+{{public:std-3:cm1:s7-cle-04.png}}
+</note>
+=== 6.3.2 Axiomes d'Amstrong ===
+Soit  $K$  une clé candidate. On démontre que  $K \rightarrow R$  à l'aide des //axiomes d'Amstrong// à partir d'un ensemble de DF connues:
+<note tip> **Axiomes d'Amstrong **
+  - **Réflexivité** :  $Y \subseteq X   \Rightarrow   X \rightarrow Y$
+  - **Augmentation** :  $X \rightarrow Y \Rightarrow X,Z \rightarrow Y,Z$
+  - **Transitivité** :  $X \rightarrow Y \text{ et } Y \rightarrow Z \Rightarrow X \rightarrow Z$
+  - **Pseudo-transitivité** :  $X \rightarrow Y \text{ et } Y,W \rightarrow Z \Rightarrow X,W \rightarrow Z$
+  - **Union** :  $X \rightarrow Y \text{ et } X \rightarrow Z \Rightarrow X \rightarrow Y,Z$
+  - **Décomposition** :  $X \rightarrow Y, Z \Rightarrow X \rightarrow Y \text{ et } X -> Z$
+</note>
+<note> ** Exercice **
+Soit le schéma relationnel suivant :
+**Billet**(num_train, type_train, num_voiture, num_place, date, id_passager, nom_passager, prénom_passager, date_naissance, gare_départ , horaire_départ, gare_arrivée, horaire_arrivée, classe, tarif)
+Montrer que l'ensemble {num_train, num_voiture, num_place, date, gare_départ} est une clé primaire du schéma?
+</note>
+====6.4 Normalisation d'un schéma====
+__**Tables mal construites**__
+<note>
+** Exemple : fournisseurs de composants électroniques:**
+ $\textbf{Fournisseur}(\underline{\text{nom_f, composant}}, \text{adresse_f, prix})$
+  * **Problèmes :**
+    * **Redondance** : l’adresse des fournisseurs est répétée plusieurs fois
+    * **Inconsistance** : mauvaise mise à jour => adresses différentes pour un même fournisseur.
+    * **Problème Insertion** : on ne peut pas insérer dans la table un fournisseur qui ne fournit rien
+    * **Problème suppression** : si un fournisseur ne fournit plus rien, on perd son adresse
+  * Solution?
+    * Couper la table en 2?
+<note warning>
+ $\textbf{Fournisseurs} (\text{nom_f, adresse_f})$
+ $\textbf{Catalogue}(\text{composant, prix})$
+</note>
+--> Impossible de retrouver les prix pratiqués par les différents fournisseurs.
+  * Nouveau Schéma :
+<note tip>
+ $\textbf{Fournisseurs} (\text{nom_f, adresse_f})$
+ $\textbf{Catalogue}(\text{nom_f, composant, prix})$
+</note>
+--> Il est possible de reconstruire la table initiale en effectuant une jointure entre ces 2 tables sur l’attribut ''nom_f''.
+</note>
+<note>
+**Exercice** : Les tables suivantes sont-elles bien ou mal construites?
+  * **Enseignement** (__id_enseignant__, nom_enseignant, __matière, id_élève__, nom_élève)
+  * **Arrêt** (__num_train__, horaire, __nom_gare__, ville)
+  * **Facture** (__id_client, article__, date, montant)
+</note>
+==== 6.5 Formes Normales =====
+**__Les Formes normales__**
+  * Restreignent les dépendances admises dans un schéma relationnel
+  * Permettent d’éviter la duplication de l’information au sein des relations
+  * Définissent une méthode
+    * de **décomposition** d’un schéma relationnel redondant
+    * en plusieurs schémas //liés entre eux//:
+=== 6.5.1 2ème forme normale (2FN) ===
+<note important>
+**Dépendance fonctionnelle élémentaire (DFE) **
+  * Soit  $R$  un schéma relationnel
+  * Soit  $X$  un ensemble d’attributs ⊆  $R$
+  * Soit  $A$  un attribut de  $R$
+  * Il existe une DFE entre  $X$  et  $A$  ssi :
+    *  $X \rightarrow  A$
+    * Il n’existe aucun sous-ensemble  $Y$  ⊆  $X$  tel que  $Y \rightarrow A$
+</note>
+<note important>
+**2ème forme normale (2FN) **
+  * Un schéma  $R$  est en 2FN :
+    * ssi la clé primaire de  $R$  est en DFE avec tous les autres attributs.
+    * Donc : il n’y a pas d’attributs qui ne dépendent que d’une partie de la clé.
+</note>
+<note tip>
+**Exemple :**
+ $\textbf{Fournisseur}(\underline{\text{nom_f}, \text{composant}}, \text{adresse_f}, \text{prix})$
+ $\text{nom_f} \rightarrow  \text{adresse_f}$
+ $\text{nom_f}, \text{composant} \rightarrow  \text{prix}$
+⇒ Pas 2FN!!
+</note>
+=== 6.5.2 Normalisation 2FN ===
+  * Lorsqu’un schéma relationnel n’est pas en deuxième forme normale, __il doit être **normalisé**__:
+<note>
+**Normalisation 2FN** :
+  * Pour obtenir un schéma 2FN:
+    * on “//découpe//” la table selon les DFE trouvées entre les attributs de la clé et ceux qui ne sont pas dans la clé.
+  * La normalisation consiste:
+    * à créer une nouvelle table pour chaque DFE ainsi trouvée.
+  * Soit :
+ $\mathbf{R} (\underline{A_1,...,\color{red}{A_i},...,A_n},B_1,...,\color{red}{B_j},...,B_m)$
+    * avec :
+ $\color{red}{A_i} \stackrel{DFE}{\rightarrow} \color{red}{B_j}$
+ $A_1,...,\color{red}{A_i},...,A_n \stackrel{DFE}{\rightarrow} B_1,...,B_{j-1},B_{j+1}...,B_m$
+  * Alors le schéma de table doit être modifié comme suit :
+ $\mathbf{R_1} (\underline{A_1,...,\color{red}{A_i},...,A_n},B_1,...,B_{j-1},B_{j+1}...,B_m)$
+ $\mathbf{R_2} (\underline{\color{red}{A_i}},\color{red}{B_j})$
+<note important>**Attention**
+Même si aucun attribut ne dépend plus de la clé primaire initiale, il est important de la conserver dans une table spécifique (elle sert à “lier” les valeurs dispersées dans les différentes tables).
+</note>
+</note>
+<note tip>
+**__Exemple__**
+  * __Avant__:
+ $\textbf{Fournisseur}(\underline{\text{nom_f,composant}}, \text{adresse_f, prix})$
+ $\text{nom_f} \rightarrow \text{adresse_f}$
+ $\text{nom_f, composant} \rightarrow \text{prix}$
+  * __Après__:
+ $\textbf{Catalogue}(\underline{\text{nom_f,composant}}, \text{prix})$
+ $\textbf{Fournisseur}(\underline{\text{nom_f}}, \text{adresse_f})$
+<note>
+**Remarque :** le schéma est maintenant constitué de deux tables.
+  * Les tables ont un attribut commun : //nom_f// (clé primaire de la table Fournisseur).
+  * La clé primaire de la table des Fournisseurs est  dupliquée dans la table des prix (appelée ici **Catalogue**).
+  * On dit que //nom_f// est une **clé étrangère** de la table des prix (l’attribut fait référence à la clé primaire d’une autre table, en l’occurrence la table des fournisseurs - voir [[public:STD-3:CM2:Conception de bases de données:3.1.1]]).
+</note>
+</note>
+=== 6.5.3 3ème forme normale (3FN) ===
+<note important>
+**Dépendance Fonctionnelle Directe (DFD) :**
+La dépendance fonctionnelle entre 2 attributs  $A_i$  et  $A_j$  est //directe// s’il n’existe pas de  $A_k$  tel que :
+ $A_i \rightarrow  A_k \rightarrow A_j$
+</note>
+<note important>
+**3ème Forme Normale (3FN)**
+Un schéma est 3FN :
+  * S’il est 2FN
+  * Si tous les attributs sont en DFD avec la clé.
+</note>
+<note>
+**Exemple :**
+ $\textbf{Commande} (\underline{\text{num_commande}}, \text{nom_f, adresse_f, composant, quantité})$
+ $\text{num_commande} \rightarrow \text{nom_f, composant, quantité}$
+ $\text{nom_f} \rightarrow \text{adresse_f}$
+Le schéma n’est pas 3FN!! (dépendance transitive entre num_commande et adresse)
+</note>
+=== 6.5.4 Normalisation 3FN ===
+* Lorsqu’un schéma relationnel n’est pas en troisième forme normale, __il doit être **normalisé**__:
+<note>
+**Normalisation 3FN**
+  * On crée une table pour chaque DFD trouvée au sein des attributs n'appartenant pas à la clé.
+Soit :
+ $R (\underline{A_1,...,A_m},B_1, ..., \color{red}{B_i},...,\color{red}{B_j},...,B_n)$
+avec :
+ $A_1, ..., A_m \stackrel{DFD}{\rightarrow} B_1, ...,\color{red}{B_i},...,B_{j-1},B_{j+1},...,B_n$
+ $\color{red}{B_i} \stackrel{DFD}{\rightarrow} \color{red}{B_j}$
+Alors :
+ $R_1 (\underline{A_1,...,A_m},B_1,...,\color{red}{B_i},...,B_{j-1},B_{j+1},...,B_n)$
+ $R_2 (\underline{\color{red}{B_i}},\color{red}{B_j})$
+<note important>
+** Attention **
+Comme précédemment, il est important de **conserver** la clé primaire de la table initiale si elle permet d'associer les valeurs dispersées dans les tables.
+</note>
+</note>
+<note>**Exemple :**
+__Avant__ :
+  * **Commande** (__num_commande__, nom_f, adresse_f, composant, quantité)
+  * avec :
+    * num_commande →  nom_f, composant, quantité
+    * nom_f →  adresse_f
+__Après__ :
+  * **Commande** (__num_commande__, nom_f, composant, quantité)
+  * **Client** (__nom_f__, adresse_f)
+L’attribut nom_f est maintenant clé primaire de la table Client et clé étrangère de la table Commande.
+</note>