Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" focusable="false" width="1em" height="1em" preserveAspectRatio="xMidYMid meet" viewBox="0 0 24 24" class="iconify mr-1" data-icon="mdi:arrow-left" style="vertical-align: -0.125em; transform: rotate(360deg);"><path d="M20 11v2H8l5.5 5.5l-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5L8 11h12z" fill="currentColor"></path></svg> ==== 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>