Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:cm5 [2018/12/13 08:33] – edauce | tc_info:cm5 [2018/12/13 08:51] (Version actuelle) – [5.1 Généralités] edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | |||
+ | |||
+ | ==== CM5 : Indexation / Modèle relationnel ==== | ||
+ | |||
+ | |||
+ | =====5. L' | ||
+ | |||
+ | <note tip> **Rappel ** | ||
+ | |||
+ | Une //donnée informatique// | ||
+ | * Consultable/ | ||
+ | * 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 // | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | ==== 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' | ||
+ | |||
+ | * L' | ||
+ | * On parle également | ||
+ | |||
+ | On peut représenter l' | ||
+ | |||
+ | === Unicité === | ||
+ | |||
+ | <note important> | ||
+ | * soient $d_1$ et $d_2$ deux enregistrements, | ||
+ | * si $k(d_1) = k(d_2)$, alors $d_1=d_2$. | ||
+ | </ | ||
+ | |||
+ | === Efficacité === | ||
+ | |||
+ | L' | ||
+ | |||
+ | La recherche par identifiant repose sur une fonction d' | ||
+ | Ainsi si $k$ est l' | ||
+ | * $i = I(k)$ (lecture de l' | ||
+ | * $d = D[i]$ (lecture des données elles mêmes) | ||
+ | |||
+ | <note tip> | ||
+ | La lecture de l' | ||
+ | $$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' | ||
+ | </ | ||
+ | |||
+ | === Compacité === | ||
+ | |||
+ | L' | ||
+ | * $|k| << |d|$ | ||
+ | pour que : | ||
+ | * $|L| << |D|$ | ||
+ | |||
+ | <note tip> | ||
+ | Un identifiant entier, codé sur 4 octets, permet d' | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 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 // | ||
+ | |||
+ | ** Lier les données ** | ||
+ | |||
+ | Dans le cas des bases de données, l' | ||
+ | |||
+ | __Exemple :__ | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | |||
+ | * Pour chaque album de la table des albums, l' | ||
+ | * Pour chaque piste de la table des pistes, | ||
+ | |||
+ | < | ||
+ | **Exercice** : donner le nom du groupe qui interprète la piste '// | ||
+ | </ | ||
+ | |||
+ | |||
+ | ** Structure d' | ||
+ | |||
+ | L' | ||
+ | |||
+ | Soit $\mathcal{E}$ un // | ||
+ | $$ \mathcal{E} = \{d_1, d_2, ..., d_K\} $$ | ||
+ | On a l' | ||
+ | $$ 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' | ||
+ | |||
+ | === 5.2.1 Adressage des tableaux === | ||
+ | |||
+ | L' | ||
+ | * Soit $D$ un tableau de $n$ lignes | ||
+ | * le numéro $i < n$ est à la fois l' | ||
+ | |||
+ | {{https:// | ||
+ | |||
+ | === 5.2.2 Maintenance centralisée d'un index=== | ||
+ | |||
+ | **Dans le cas général, l' | ||
+ | |||
+ | On sépare donc l' | ||
+ | * $k$ est l' | ||
+ | * $i$ est l' | ||
+ | |||
+ | <note important> | ||
+ | Lors de l' | ||
+ | * l'// | ||
+ | * l' | ||
+ | </ | ||
+ | |||
+ | Il existe différentes méthodes permettant d' | ||
+ | * Le programme maintient une liste triée des identifiants déjà utilisées. Lors de l' | ||
+ | * Coût : | ||
+ | * $O(n)$ en mémoire | ||
+ | * $O(\log n)$ pour l' | ||
+ | * Dans le cas où les identifiants sont des numéros (entiers), il est possible d' | ||
+ | * Coût : | ||
+ | * $O(1)$ en mémoire | ||
+ | * $O(1)$ pour l' | ||
+ | |||
+ | < | ||
+ | **Exemples d' | ||
+ | * numéro INE (étudiants) | ||
+ | * numéro URSSAF (sécurité sociale) | ||
+ | * numéro d' | ||
+ | * numéro de compte en banque | ||
+ | * code barre | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 5.2.3 Indexation pseudo-aléatoire : les fonctions de hachage === | ||
+ | Utilisation d'une //fonction de hachage// : | ||
+ | * qui " | ||
+ | * 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 | ||
+ | * '' | ||
+ | * avantage : les données différentes ont un code entier différent | ||
+ | * mais : |i| = |d| | ||
+ | <code python> | ||
+ | s = ' | ||
+ | d = bytes(s, ' | ||
+ | i = int.from_bytes(d, | ||
+ | print(" | ||
+ | </ | ||
+ | donne : | ||
+ | < | ||
+ | i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058 | ||
+ | </ | ||
+ | * Etape 2 : **réduction** du code | ||
+ | * __Méthode 1__ : le modulo n (reste de la division entière par 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 '' | ||
+ | * ---> il faut prendre n //premier// | ||
+ | |||
+ | * | ||
+ | * | ||
+ | * $n = 2^{32} = 4294967296$ : | ||
+ | * H_code('' | ||
+ | * H_code('' | ||
+ | * $n = 67280421310721$ (premier): | ||
+ | * H_code('' | ||
+ | * H_code('' | ||
+ | |||
+ | * | ||
+ | * __Méthode 2__ : combiner produit et modulo -- soient m et n deux nombres premiers entre eux | ||
+ | * '' | ||
+ | * Avantage : | ||
+ | * $|k| << |d|$ | ||
+ | * deux entiers proches donneront auront des codes très différents : si '' | ||
+ | * Inconvénient : | ||
+ | * deux données différentes peuvent avoir le même code | ||
+ | * le produit '' | ||
+ | |||
+ | * __Méthode 3__ : Hachage cryptographique : | ||
+ | * Le hachage cryptographique est construit de telle sorte qu'il soit très difficile de trouver un entier '' | ||
+ | * Un tel code est appelé une " | ||
+ | * Exemples : | ||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | |||
+ | === Exemple === | ||
+ | |||
+ | Le gestionnaire de bases de données {{https:// | ||
+ | |||
+ | ==== 5.3 Généralisation : multi-indexation ==== | ||
+ | |||
+ | <note tip> | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | ==== 5.4 Structures de données pour l' | ||
+ | |||
+ | === 5.4.1 Liste triée == | ||
+ | <note tip> | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | === 5.4.2 Index bitmap === | ||
+ | <note tip> | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | === 5.4.3 Les B-arbres === | ||
+ | Que faire lorsque l' | ||
+ | * L' | ||
+ | * Les blocs sont organisés sous la forme d'un arbre (B-arbre = "// | ||
+ | |||
+ | 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' | ||
+ | | ||
+ | {{ restricted: | ||
+ | |||
+ | * 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) | ||
+ | |||
+ | < | ||
+ | * 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’ | ||
+ | </ | ||
+ | |||
+ | 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 '' | ||
+ | * 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:// | ||
+ | * http:// | ||
+ | </ | ||
+ | |||
+ | ===== 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> | ||
+ | **// | ||
+ | |||
+ | ** Schémas de données ** | ||
+ | |||
+ | * Un enregistrement est un jeu de valeurs organisé sous forme de **tuple** | ||
+ | * A un tuple on associe | ||
+ | {{public: | ||
+ | |||
+ | * Définir un **schéma** consiste à définir : | ||
+ | * une liste d' | ||
+ | * A chaque **attribut** correspond : | ||
+ | * un // | ||
+ | * un //domaine// de valeurs (type/ | ||
+ | |||
+ | ** 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:// | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | * Soit $R(A_1, ..., A_m)$ un schéma. | ||
+ | * On note $\text{dom}(A_i)$ le domaine associé à l' | ||
+ | * 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. | ||
+ | |||
+ | |||
+ | |||
+ | < | ||
+ | ** Diverses représentations :** | ||
+ | |||
+ | __[[public: | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | __[[public: | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | __[[public: | ||
+ | |||
+ | **Client**(nom, | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | < | ||
+ | ** __Exemples de schémas relationnels__ :** | ||
+ | |||
+ | **Étudiant**(nom, | ||
+ | |||
+ | **Ouvrage**(titre, | ||
+ | |||
+ | **Véhicule**(immatriculation, | ||
+ | </ | ||
+ | |||
+ | === 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' | ||
+ | * Une entité est décrite par une ou plusieurs valeurs caractéristiques, | ||
+ | |||
+ | <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' | ||
+ | * Exemples de noms concrets : // | ||
+ | * prend ses valeurs dans un domaine bien spécifié, | ||
+ | * également appelé le **type** de l' | ||
+ | * Le domaine d'un attribut est noté $\text{dom}(Aj)= Dj$. | ||
+ | * Exemples : | ||
+ | * $\text{dom}(couleur)={rouge, | ||
+ | * $\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 | ||
+ | </ | ||
+ | * Un attribut peut être : | ||
+ | * simple ou composé. | ||
+ | * Exemple : une //adresse// peut être décrite par une simple chaîne de caractères, | ||
+ | * 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' | ||
+ | $$E = \{x_1, | ||
+ | Il regroupe (ou associe) plusieurs entités ayant des caractéristiques communes (descriptibles à l'aide du même ensemble d' | ||
+ | |||
+ | <note tip> | ||
+ | **Exemples** : | ||
+ | * les employés d'une firme, | ||
+ | * les cours de Centrale Marseille, | ||
+ | * une collection de disques, | ||
+ | * etc… | ||
+ | </ | ||
+ | |||
+ | * Les éléments d’un ensemble d’entités sont // | ||
+ | * les attributs $(A_1, | ||
+ | * Le schéma $R$ de l’ensemble $E$ est une // | ||
+ | * Soit : | ||
+ | $$ R : \mathcal{X} \rightarrow D_1 \times ... \times D_m$$ | ||
+ | $$ x_i \mapsto (A_1(x_i), | ||
+ | |||
+ | <note tip> | ||
+ | ** représentation graphique ** : | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | ** Exemples **: | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | === 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:// | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | **Définition** | ||
+ | |||
+ | Soit $R = (A_1, | ||
+ | |||
+ | Une **relation** $r$ obéissant au schéma $R$ est un // | ||
+ | </ | ||
+ | |||
+ | <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' | ||
+ | </ | ||
+ | |||
+ | <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'' | ||
+ | </ | ||
+ | |||
+ | ==== 6.2 Dépendances fonctionnelles ==== | ||
+ | |||
+ | * Au sein d'un schéma $R$, | ||
+ | * Il peut exister un ensemble de contraintes, | ||
+ | * portant sur les attributs (plus précisément sur les valeurs prises par les attributs). | ||
+ | * L' | ||
+ | * On parle de **contraintes d’intégrité**. | ||
+ | * Ces contraintes s’expriment sous la forme de **dépendances fonctionnelles**. | ||
+ | |||
+ | < | ||
+ | **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 important> | ||
+ | **Dépendance fonctionnelle** | ||
+ | |||
+ | * Soit $r$ une relation définie selon $R(A_1, | ||
+ | * Soient $X$ et $Y$ deux sous-ensembles de $R$ | ||
+ | * On dit que la relation $r$ définit une // | ||
+ | * 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 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 tip> | ||
+ | **__Exemple 2__** : | ||
+ | |||
+ | * Soit le schéma : | ||
+ | * **Commande** (num_client, | ||
+ | * et l’ensemble de contraintes | ||
+ | $$ \begin{array}{rl}F &= \{\\ | ||
+ | & \text{num_client, | ||
+ | & \text{num_article, | ||
+ | &\} | ||
+ | \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 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)// | ||
+ | * “// | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Exercice :** | ||
+ | Soit le schéma : | ||
+ | |||
+ | * **Réservation**(code_appareil, | ||
+ | |||
+ | Exprimer la dépendance fonctionnelle : | ||
+ | * « //Un appareil ne peut pas être utilisé dans deux locaux différents au même moment //» | ||
+ | </ | ||
+ | |||
+ | * Il importe donc de bien réfléchir, | ||
+ | * 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!). | ||
+ | |||
+ | < | ||
+ | |||
+ | Soit le schéma relationnel suivant : | ||
+ | |||
+ | **Billet**(num_train, | ||
+ | |||
+ | Définir des dépendances fonctionnelles sur cet ensemble d' | ||
+ | </ | ||
+ | ====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' | ||
+ | * 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$. | ||
+ | </ | ||
+ | < | ||
+ | * **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, | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **__Exemple 1__** : | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | **__Exemple 2__** : | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | *Pour certains schémas, | ||
+ | * il est courant de définir comme clé un entier **identifiant de façon unique** chaque élément de l' | ||
+ | * La clé est alors constituée de cet attribut unique. | ||
+ | {{public: | ||
+ | |||
+ | **Représentation [[public: | ||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | === 6.3.2 Axiomes d' | ||
+ | |||
+ | Soit $K$ une clé candidate. On démontre que $K \rightarrow R$ à l'aide des //axiomes d' | ||
+ | |||
+ | <note tip> **Axiomes d' | ||
+ | |||
+ | - **Réflexivité** : $$Y \subseteq X | ||
+ | - **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$$ | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | |||
+ | Soit le schéma relationnel suivant : | ||
+ | |||
+ | **Billet**(num_train, | ||
+ | |||
+ | Montrer que l' | ||
+ | </ | ||
+ | ====6.4 Normalisation d'un schéma==== | ||
+ | __**Tables mal construites**__ | ||
+ | < | ||
+ | ** Exemple : fournisseurs de composants électroniques: | ||
+ | |||
+ | $$\textbf{Fournisseur}(\underline{\text{nom_f, | ||
+ | |||
+ | * **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, | ||
+ | $$\textbf{Catalogue}(\text{composant, | ||
+ | </ | ||
+ | --> Impossible de retrouver les prix pratiqués par les différents fournisseurs. | ||
+ | |||
+ | |||
+ | * Nouveau Schéma : | ||
+ | <note tip> | ||
+ | $$\textbf{Fournisseurs} (\text{nom_f, | ||
+ | $$\textbf{Catalogue}(\text{nom_f, | ||
+ | </ | ||
+ | --> Il est possible de reconstruire la table initiale en effectuant une jointure entre ces 2 tables sur l’attribut '' | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Exercice** : Les tables suivantes sont-elles bien ou mal construites? | ||
+ | |||
+ | * **Enseignement** (__id_enseignant__, | ||
+ | |||
+ | * **Arrêt** (__num_train__, | ||
+ | |||
+ | * **Facture** (__id_client, | ||
+ | </ | ||
+ | |||
+ | ==== 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 | ||
+ | * Il n’existe aucun sous-ensemble $Y$ ⊆ $X$ tel que $Y \rightarrow A$ | ||
+ | </ | ||
+ | |||
+ | <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 tip> | ||
+ | **Exemple :** | ||
+ | $$\textbf{Fournisseur}(\underline{\text{nom_f}, | ||
+ | $$\text{nom_f} \rightarrow | ||
+ | $$\text{nom_f}, | ||
+ | ⇒ Pas 2FN!! | ||
+ | </ | ||
+ | |||
+ | === 6.5.2 Normalisation 2FN === | ||
+ | * Lorsqu’un schéma relationnel n’est pas en deuxième forme normale, __il doit être **normalisé**__: | ||
+ | |||
+ | < | ||
+ | **Normalisation 2FN** : | ||
+ | * Pour obtenir un schéma 2FN: | ||
+ | * on “// | ||
+ | * La normalisation consiste: | ||
+ | * à créer une nouvelle table pour chaque DFE ainsi trouvée. | ||
+ | |||
+ | * Soit : | ||
+ | $$\mathbf{R} (\underline{A_1, | ||
+ | * avec : | ||
+ | $$\color{red}{A_i} \stackrel{DFE}{\rightarrow} \color{red}{B_j}$$ | ||
+ | $$A_1, | ||
+ | * Alors le schéma de table doit être modifié comme suit : | ||
+ | $$\mathbf{R_1} (\underline{A_1, | ||
+ | $$\mathbf{R_2} (\underline{\color{red}{A_i}}, | ||
+ | |||
+ | <note important> | ||
+ | |||
+ | 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 tip> | ||
+ | **__Exemple__** | ||
+ | * __Avant__: | ||
+ | $$\textbf{Fournisseur}(\underline{\text{nom_f, | ||
+ | $$\text{nom_f} \rightarrow \text{adresse_f}$$ | ||
+ | $$\text{nom_f, | ||
+ | * __Après__: | ||
+ | $$\textbf{Catalogue}(\underline{\text{nom_f, | ||
+ | $$\textbf{Fournisseur}(\underline{\text{nom_f}}, | ||
+ | |||
+ | < | ||
+ | **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: | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | === 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 | ||
+ | </ | ||
+ | |||
+ | <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é. | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Exemple :** | ||
+ | |||
+ | $$\textbf{Commande} (\underline{\text{num_commande}}, | ||
+ | $$\text{num_commande} \rightarrow \text{nom_f, | ||
+ | $$\text{nom_f} \rightarrow \text{adresse_f}$$ | ||
+ | |||
+ | Le schéma n’est pas 3FN!! (dépendance transitive entre num_commande et adresse) | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 6.5.4 Normalisation 3FN === | ||
+ | * Lorsqu’un schéma relationnel n’est pas en troisième forme normale, __il doit être **normalisé**__: | ||
+ | |||
+ | < | ||
+ | **Normalisation 3FN** | ||
+ | * On crée une table pour chaque DFD trouvée au sein des attributs n' | ||
+ | |||
+ | |||
+ | Soit : | ||
+ | $$R (\underline{A_1, | ||
+ | avec : | ||
+ | $$A_1, ..., A_m \stackrel{DFD}{\rightarrow} B_1, ..., | ||
+ | $$\color{red}{B_i} \stackrel{DFD}{\rightarrow} \color{red}{B_j}$$ | ||
+ | Alors : | ||
+ | $$R_1 (\underline{A_1, | ||
+ | $$R_2 (\underline{\color{red}{B_i}}, | ||
+ | |||
+ | <note important> | ||
+ | ** Attention ** | ||
+ | |||
+ | Comme précédemment, | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | |||
+ | __Avant__ : | ||
+ | * **Commande** (__num_commande__, | ||
+ | * avec : | ||
+ | * num_commande → nom_f, composant, quantité | ||
+ | * nom_f → adresse_f | ||
+ | |||
+ | __Après__ : | ||
+ | * **Commande** (__num_commande__, | ||
+ | * **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. | ||
+ | </ | ||
+ | |||