1 C1 - Base de Données F. KOHLER. 2 Le Modèle relationnel Basé sur le concept de relation...

1

C1 - Base de Données

F. KOHLER

2

Le Modèle relationnel

• Basé sur le concept de relation• Formulé par EF Codd 1970• Chaque phénomène peut être décrit par une relation. Un

phénomène d'un type déterminé est un n-uplet (collection des valeurs qui permet de représenter un fait) de la relation.

• Vue utilisateur : une relation est un tableau. Un n-uplet est une ligne du tableau. Une base de données est un ensemble de tableau

• Les tableaux sont manipulables par des langages non procéduraux

3

Généralités

• Base de données :– Références aux données elles mêmes

– -Système de gestion de base de données : SGBD• Matériel

– Serveur central unique / serveurs répartis

– Clients

• Logiciel– De développement

– Client

4

Modèles de données

• Un modèle de données est un moyen d’expliquer la disposition logique des données et les relations entre les différentes parties de chaque éléments de l’ensemble.

• Représentation d’une entité : un tableau– Chaque colonne correspond à un champs (rubrique)

– Chaque ligne correspond à un individu

Nom Sexe Qualité D. Nais

SIM M Mr 10/02/01

5

Architecture à 3 niveaux

• Interne – Stockage physique des données sur le matériel

• Niveau conceptuel– Définition logique de la base de données : représentation pour la communauté

concernée.– Le DDL (data definition language) permet de décrire les tables et de décrire les

champs de chaque table. Certains y ajoutent les droit d’accès ou de manipulation.– Le DML (data manipulation language) permet de manipuler les données

(remplissage de la base …)

• Le niveau externe – Concerne les utilisateurs en leur donnant des vues différentes (liste, fiche de

saisie…)

• Indépendance des données– Le système doit préserver l’indépendance des données à la fois physiquement

(augmentation de la taille des disques par exemple) et logiquement

6

Modèle entité association

• Les données se rapportant à un même concept sont rassemblées dans une entité.

• Les entités sont reliées entre elles par des associations

• Exemple :– Dans une application de gestion de dossiers patients

on a les entités :• Patient• Médecin• Consultation

Patients

ConsultationReçoit

0n

1

A Médecins1m

k0

Donne

7

Bases de données relationnelles

• SGBDR– Modèle le plus répandu– Repose dur l’algèbre relationnel

• SGBD Objet

• …

8

Relation et schéma de relation

• Domaine : – Ensemble de valeurs que peut prendre une

variable– Exemple

• D1 ensemble des valeurs possible pour le sexe {M,F}

• D2 ensemble des tailles en cm possibles :– Ensemble continu de[30,230]

– Contrainte d’intégrité >30 et < 230

9

Définition d'une relation

• Soit des ensembles D1, D2, ..., Dn– On définit une relation R sur les ensembles D1,

D2, ..., Dn comme une partie du produit cartésien des ensembles D1, D2, ..., Dn

– R (D1, D2, ..., Dn) D1 X D2 X ... X Dn– R est donc un ensemble de n-uplet (tulpe)

<d1,d2,...,dn> tels que d1 D1, d2 D2, dn Dn

10

Relation et schéma de relation

• Nuplet (tulpe) – Est un élément d’une relation, noté (d1,d2,…dn)

– C’est une ligne

– Exemple• Relation Personne (nom, sexe, taille)

• ‘Dupond’, ‘M’, 185 est un N-uplet de la relation Personne

• Attribut– Est un identificateur de domaine

– Surnom donné à une colonne

11

Définitions complémentaires• Degré de la relation

– C'est le nombre de constituants (Nbre de rubrique, Nbre de colonnes...)

• Cardinal de la relation– C'est le nombre de n-uplet de la relation (Nbre de fiches, Nbre

de lignes du tableau)

12

Notion d'identifiant et de clef

• C'est un constituant ou un ensemble de constituant minimal qui détermine de façon univoque un n-uplet de la relation.

• Une relation peut comporter plusieurs identifiants.

• Une clef est un identifiant choisi notamment dans le cadre de son implication dans les associations (liens)

13

Exemple de clé d’une relation

• Relation Médicament (N°AMM, DCI, Forme galénique)

• N°AMM est une clé : deux lignes du tableau ne peuvent pas avoir le même numéro d’AMM

• Médicament(N°AMM, DCI, Forme galénique)

14

Contraintes d’intégrité

• Est une assertion qui doit être vrai durant toute la vie de la base de donnée

• Une base de donnée est dite cohérente si toutes les contraintes d’intégrité sont vérifiées

• Type de contrainte d’intégrité– CI su un attribut, exple : contrainte de domaine– CI intrarelation, exple : prixTTC = (qte*prixunitaire*(1+tva))– CI interrelation, exple CI référentielle

15

Schéma de relation• Définit une classe de relation par :

– n domaines D1, ... , Dn– n attributs A1, ... , An– Un nom de schéma de relation– Des contraintes d'intégrité

• Exemple : Fichier des voitures– Voiture(Imat,Marque,Type,Puis,Couleur)– Domaine(Imat) = Chaine de 8 caractères– Domaine(Marque) = [Renault, Ford, ...] : liste énumérée– Contrainte d'intégrité

• Absolue (0 < Puiss < 1200)• Relative ( Si Renault 3 < Puis < 16

– Le schéma relationnel d'une base de données est l'ensemble des schémas de relation

16

Attention• Qu'est-ce qu'un attribut élémentaire

– Date de Naiss -> Jour N, Mois N, An N– Adresse (Nom, Adresse)– Adresse ( Nom, N° rue, CP, Ville)– Adresse (Nom, N°, Bis_ter, Type voie, Nom

Voie, CP, Cedex, Canton, Arrondissement, Ville, Pays)

• Conséquence => Possibilité des traitements• Le choix est fait en fonction des traitements qui

sont envisagés ou de la disponibilité assurée des constituants : – exemple date de Naissance : si on choisit un type « date » que fait-

on pour les patient dont le jour ou le mois de naissance sont inconnus ?

17

Attention• Une information - Plusieurs représentations

– N° Téléphone 83 59 26 27• Chaîne de caractères• Un réel• Deux entiers• Un entier long• Date (Impossible)• Image

• Choix du type en fonction :– Des contraintes d'intégrité– Des possibilité de calcul– De l'efficacité des recherches– De la place disque

18

Représentation interne• Schéma de relation

– Un fichier ou une table

• Attributs ou constituants– Les rubriques

• Domaines– Type de chaque rubrique

• Contrainte d'intégrité– Filtre de saisie– Procédure de validation

19

Notion de tri

• Soit la table

• Tri selon un ou plusieurs attribut• Tri ascendant/descendant• Tri alphabétique / tri numérique• Résultat : table trié soit en remplacement soit

création d’une autre table

Nom Sexe AgeDupond 1 20Durand 2 30Albert 1 18Dupont 1 45Noémie 2 50Marcel 2 80

Nom Sexe AgeDupond 1 20Albert 1 18Dupont 1 45Durand 2 30Noémie 2 50Marcel 2 80

Tri sur le sexe

20

Notion d'index

• Soit la table

• Possibilité d’index multiples sur une table• A la création de la table on précise les index

N° enr Nom Sexe Age1 Dupond 1 202 Durand 2 303 Albert 1 184 Dupont 1 455 Noémie 2 506 Marcel 2 80

Index sur le Nom

N° enr Nom3 Albert1 Dupond4 Dupont2 Durand6 Marcel5 Noémie

21

Recherche

• Recherche séquentielle

• Recherche sur index

• Notion d'unicité : si un attribut est une clé, le tri sur cette clé permet de vérifier qu’une valeur de cet attribut n’existe qu’une seul fois

22

Structure du langage MySQL

• Nombres– Entier 156– Décimal 250.25– Entier négatif - 258– Décimal négatif -11.5– Notation scientifique 1.77E+12

1770000000000

23

Structure du langage MySQL

Chaînes de caractères« c »

« Paris »

« Il fait beau »

« D\’une apostrophe »

« \ » » et expressions régulières

24

Structure du langage MySQL

Date et heure

Valeurs hexadécimales

Valeur NULL

25

Structure du langage MySQL

Type de colonnesType numérique

TINYINT : 1 octet => -128 à +127 si UNSIGNED 0 à 255

SMALLINT : 2 octets => -32768 à + 32767 si UNSIGNED 0 à 65535

MEDIUMINT : 3 octets

INT : 4 octets

BIGINT : 8 octets

FLOAT : 4 octets

DOUBLE : 8 octets

DECIMAL cf DOUBLE

26

Structure du langage MySQLType de colonnes

Chaînes de caractèresCHAR (M) [BINARY] : contient une chaîne de M (1 à 255) caractères (longueur fixe).

Insensible à la cassse sauf si BINARY est préciséVARCHAR (M) [BINARY] : contient une chaîne de longueur variable plus courte que M

(1 à 255). Insensible à la casse sauf si BINARYTINYBLOB : de 1 à 255 octets, sensible à la casseBLOB : de 1 à 65 535 octets, sensible à la casseMEDIUMBLOB : de 1 à 16 777 215 octets, sensible à la casseLONGBLOB : de 1 à 4 294 967 295 octets, sensible à la casseTINYTEXT : de 1 à 255 octets, insensible à la casseTEXT : de 1 à 65 535 octets, insensible à la casseMEDIUMTEXT : de 1 à 16 777 215 octets, insensible à la casse

LONGTEXT : de 1 à 4 294 967 295 octets, insensible à la casseENUM (« valeur 1», »valeur2 »….) : 1 à 65 535 valeurs, insensible à la casseSET(« valeur1 », »valeur2 »,….) : de 1 à 64 valeurs, insensible à la casse

27

Structure du langage MySQL

Type de colonnesDate et heure

DATE: entre le 1er janvier 1000 et le 31 décembre 9999 (‘9999-12-31’)

DATETIME : date et heure ‘1000-01-01 00:00:00’ à ‘9999-12-31 23:59:59’

TIME : HH:MM:SS de –858:59:59 à 838:59:59

TIMESTAMP : timestamp unix en seconde depuis le 1er janvier 1970 0 heure à 2037

YEAR : Année entre 1901 et 2155

28

Règles d'intégrité• Unicité de clé

– Dans la relation, l'attribut clé est souligné, il identifie de manière unique dans la table le n-uplet.

• Contrainte de référence– Si un même attribut apparaît dans une relation comme clé et

dans une autre comme non-clé, toute valeur de l'attribut non-clé doit exister dans l'attribut clé.

• Malade (NuMal, Nom, Prénom, D_Naiss)

• Consult(NuMal*, NuCons, Date)

• Contrainte d'entité– Les valeurs de tout attribut participant à une clé primaire

doivent être "non nulles" (valeur nulle = @)

29

Vues relationnelles• Ce sont des tables virtuelles créées à partir de

tables réelles permettant d'avoir une vision particulière de la base de donnée. Elles sont entièrement gérées par le système.

• Malade(NuMal, Nom, Prénom, D_Naiss)• Consult(NuMal*, NuCons*, Date)• TTT (NuCons, NuTTT, Nom_Prod)• Créer vue Mal_Cons

– NuMal, Nom,Nom_Prod– Clés utilisées

• NuMal, NuCons

30

Algèbre relationnel• Opérations de base

– Union– Différence– Produit cartésien– Projection– sélection– jointure

• Opérations déduites– Intersection– Division– Jointure naturelle– Jointure externe– Semi-jointure– Complément

31

Union

• Soit 2 relations r(R) et s(S) avec des schémas compatibles l’union de ces 2 relations est l’ensemble de tous les tulpes qui sont actuellement présents dans r ou dans s.

• Il n’y a pas de tulpes doublon. Le schéma de la relation résultant de l’union est celui de la relation r.

• L’union est commutative.

32

Intersection

• Soit 2 relations r(R) et s(S) avec des schémas compatibles l’intersection de ces 2 relations est l’ensemble de tous les tulpes qui sont actuellement présents dans r et dans s.

• L’intersection est commutative

33

1 Dupont2 Albert3 Durant

Malades2 NuMal, Nom1 Dupont4 Albert3 Tartempion

Malade = Différence (Malades1, Malades2)

2 Albert3 Durant

DifférencesMalades1 NuMal, Nom Soit 2 relations r(R) et s(S) avec

des schémas compatibles la différence de ces 2 relations est l’ensemble de tous les tulpes qui sont actuellement présents dans r et ne se trouvent pas dans s.

La différence n’est pas commutative

34

Projection

• Produit une relation réduite aux attributs mentionnés en opérandes (sélection de colonnes de la table, les lignes ayant même valeurs sont dédoublonnées)

• Malade (Nu, Nom)– 1 Dupon– 2 Dupon– 3 Albert

• R2 = Projection(Malade,Nom)– Dupon– Albert

35

Produit cartésien• R1 (Num, Nom)

– 1 A– 2 B– 3 C

• R2 (Dte, Commande)– 10 L– 11 M

• R3 = R1 * R2– Num, Nom, Dte, Commande– 1 A 10 L– 1 A 11 M– 2 B 10 L– 2 B 11 M– 3 C 10 L– 3 C 11 L

36

Sélection ou Restriction

• Produit une relation de même schéma et ayant pour occurrences les n-uplets vérifiant la condition exprimée (sélection de lignes répondant à une condition).

• R2=Select (Malade, Nom = Dupon)– 1 Dupon– 2 Dupon

37

Jointure ou Join• Opération sur deux relations R1 et R2 qui produit une

relation ayant pour schéma la juxtaposition des relations opérandes et pour occurrences l'ensemble des n-uplets obtenus par concaténation des n-uplets de R1 et R2 vérifiant la condition entre les attributs de R1 et R2.

• Join peut être obtenu en combinant le produit cartésien des relations à joindre et d’une sélection utilisant l’expression de jointure comme expression de sélection– R3 = JOIN(R1,R2,Condition)

– R3 = SELECT(PROD(R1,R2),Condition)

38

Equijointure ou jointure naturelle• Opérateur binaire qui associe 2 relations (qui ne sont pas forcément

différentes) sur (tous) leur(s) attribut(s) communs. La jointure est constituées de tous les tulpes résultant de la concaténation des tulpes de la première relation avec ceux de la seconde qui ont des valeurs identiques pour un ensembles communs d’attributs X.

• Exemple :

ID Nom Lieu100 Comptabilité Angers200 Marketing Nantes300 Ventes Angres

DépartementID NOM DEPT TITRE100 Duchemin Ventes Employé200 Portail Marketing Employé300 Hérisson Comptabilité Employé400 Lapelle Comptabilité Chef

Personnel

ID DEP NOM DEP LIEU ID PER NOM PER TITRE100 Comptabilité Angers 300 Hérison Employé100 Comptabilité Angers 400 Lapelle Chef200 Marketing Nantes 200 Portail Employé300 Ventes Angers 100 Duchemin Employé

DEPARTEMENT Equijointure PERSONNEL (NOM,DEP)

39

Opérations déduites

• Division– Opération entre deux

relations ayant des attributs communs qui produit une relation R3 réduite aux attributs Ai appartenant à R1 mais n'appartenant pas à R2 et ayant comme occurrences des n-uplets qui concaténés à ceux de R2 donne un n-uplet de R1

N°LIVRE Genre AuteurL3 poésie HugoL1 poésie VerlaineL4 roman HugoL5 histoire Mallet

R1

R2Genrepoésieroman

N°LIVRE AuteurL3 HugoL4 Hugo

DIV(R1,R2)

40

Opérations déduites• Complément

– Opération sur une relation R1, produit une relation R2 de même schéma ayant un ensemble d'occurrences constitué des n-uplets du produit cartésien entre les domaines des attributs de Ai de R1 n'appartenant pas R1. Les domaines de R1 doivent être finis.

• Jointure externe– Opération entre deux relations qui produit une relation R3 ayant pour

schéma l'union de ceux des relations opérandes et pour occurrences l'ensemble des n-uplets obtenus par jointure de R1 et R2 et ajout des n-uplets de R1 et R2 ne participant pas à la jointure avec des valeurs nulles pour les attributs de l'autre relation.

• Semi jointure– Opération entre deux relations R1 et R2 qui produit une relation de

même schéma que R1 ayant un ensemble d'occurrences formés des n-uplets de R1 participant à la jointure de R1 et R2.

41

Propriétés des opérations relationnelles

• Commutativité des jointures, des unions, des intersections• Associativité des jointures, des unions, des intersections• Regroupement des sélections

– *• R = SELECT (SELECT(R1,Aj="a"), Ak = "b") • R = SELECT (R1,Aj="a" et Ak ="b")

– *• R = UNION (SELECT(R1,Aj="a"), SELECT(R1, Ak = "b"))• R = SELECT (R1,Aj="a" ou Ak ="b")

• Combinaisons des sélections et des projections• Combinaisons des sélections et des jointures• Combinaisons des projections et des jointures• Combinaisons des unions et des projections

42

Exemple

• VIN (Nvin, Cru, Mill, Degré)

• BUV(NBuv, NomBuv, Prebuv, Adrbuv, Typebuv)

• Cons(Nvin*, Nbuv*, Date,Qté)

Quels sont les numéros des vins, les crus ainsi que les millésimes des vins consommés par les buveurs de Lyon dont la quantité est supérieure à 100 ?

R1 = Join(BUV,CONS)R2 = SELECT(R1,Adrbuv = "Lyon" et Qté > 100)R3 = JOIN (VIN, R2)RESULT = PROJECT(R3,Nvin,Cru,Mill)

ou

R1 = SELECT(BUV,Adrbuv = "Lyon")R2 = SELECT (CONS, Qté > 100)R3 = JOIN( R1, R2)R4 = PROJECT (R3, Nvin)R5 = PROJECT (Vin,NVin,CRU,Mill)RESULT = JOIN (R4,R5)

43

Langage SQL

• Langage informatique standard dans les bases de données relationnelles.

• 1ére implémentation 1979• Langage déclaratif non procédural• 2 sous langages

– DDL– DML

• Soit interactif soit intégré : les instructions font alors partie d’un programme écrit dans un langage hôte (C++…)

44

Conventions

• Les noms doivent comporter de 1 à 30 caractères (parfois 64). Les noms de base de données sont souvent limités à 8.

• Les noms doivent commencer par une lettre minuscule ou majuscule et comporter combinaison de lettre et chiffre et signe souligné

45

Structure des instructions SQL

• Toute instruction SQL est une combinaison d’une ou plusieurs clauses.

• Les clauses sont introduites par des mots-clés

• Exemple :– SELECT nom, age, sexe FROM patient

WHERE sexe =‘M’ ORDER BY nom ASC, age DESC

46

Création de table

• CREATE TABLE nom_table

(

Nom_col_1 Type_donnée_1 [contrainte]

Nom_col_2 Type_donnée_2 [contrainte]

…..

Nom_col_n Type_donnée_n [contrainte]

);

47

Implication des contraintes

• A chaque foi qu’une contrainte est définie, on doit lui donner un nom. Elle est soit nommée par l’utilisateur soit nommée en interne par le SGBD (contrainte non nommée).

• Les contraintes non nommées ne doivent pas être précédée de la clause CONSTRAINT

• Conventions de suffixe pour les contraintes nommée :– PK : primary key– FK : foreign key (clé extérieur)– NN : Not NULL– U : unique

• PK implique NN et U

48

Exemple

• CREATE TABLE Carte_etud(NOM VARCHAR2(40), NUM_Carte VARCHAR2(15) PRIMARY KEY,VALEUR_DEP NUMBER(4,2),NUM_PIN CHAR(12) UNIQUE,);

• CREATE TABLE Carte_etud(NOM VARCHAR2(40), NUM_Carte VARCHAR2(15) CONTAINT NUM_CARTE-PK

PRIMARY KEY,VALEUR_DEP NUMBER(4,2),NUM_PIN CHAR(12) UNIQUE,);

49

Insertion d’enregistrements

• INSERT INTO nom_table (col_1, col_2,…., col_n) VALUES (val_1, val_2, ….., val_n);

• COMMIT; est la dernière commande qui permet de rendre permanent les changements dans la table.

50

Suppression, modification d’enregistrement

• DELETE FROM nom-table WHERE condition;

• UPDATE nom_table SET col_1 = nouvelle valeur, col_2 = nouvelle valeur …. WHERE condition;

51

Sélection, projection et jointure• SELECT col_1, col_2,…, col_nFROM table_1,…, table_n[WHERE condition][ORDER BY nom_col [ASC | DESC] [nom_col [ASC |

DESC] ];• Opérations avec SQL

– UNION : select * from tab_1 UNION select * FROM tab_2

– INTERSECT– MINUS

52

Dépendances fonctionnelles

• Dans de nombreuses bases de données, le contrôle de la redondance et la préservation de la cohérence des données sont les plus importants auxquels est confronté le concepteur et l’administrateur.

• La redondance survient quand une information est stockée dans plusieurs endroits. Si ce contenu est modifié, il faut le modifier au niveau de chacune des copies. Si certaines, mais pas toutes les copies, sont modifiées les données sont incohérentes.

• Pour éviter ses écueils, cela passe par l’étude des dépendances fonctionnelles.

53

Dépendances fonctionnelles

• Les contraintes se classent en deux groupes– Les contraintes sémantiques : dépendent de la signification ou de

la compréhension des attributs d’une relation• Dans une relation Personnel(Nom, Age, Salaire) aucun âge ou

salaire ne peut être négatif– Les contraintes d’accord ou de concordance ne dépendent pas

des valeurs particulières d’un attribut d’un tulpe mais du fait que les tulpes qui acceptent certains attributs acceptent ou non les valeurs de certains de leurs autres attributs

• Dans une relation Personnel (employé, âge, salaire, service, chef de service) si un employé ne travaille que dans un service et que chaque service n’a qu’un chef de service alors deux tulpes ayant la même valeur dans la colonne chef de service on doit avoir la même valeur dans service. On a une dépendance fonctionnelles

• Les dépendances fonctionnelles sont les plus importante contraintes de concordance ou d’agrément.

54

Dépendances fonctionnelles

• Définition :– Soit une relation r(R) et deux ensemble des ses attributs A et B.

Les attributs s(A) détermine(nt) fonctionnellement le(s) attribut(s) de B relativement à R si et seulement si pour deux tulpes t1 et t2 de r, à chaque fois que t1(A) = t2(A) alors t1(B) = t2(B)

– On note A->B– A est appelé le déterminant, B est appelé la partie droite de la

dépendance fonctionnelle– A et B ne sont pas nécessaire des attributs uniques mais des

ensembles d’attributs. Si A est composé d’un seul attribut on parle de dépendance fonctionnelle simple

– A -#->B s’emploie pour indiquer que A ne détermine pas fonctionnellement B.

55

Dépendance fonctionnelles (DF)

• Exemple :– La DF Continent->nom

n’est pas satisfaite– La DF Nom->Longueur

est satisfaite

• On ne peut déterminer un DF qu’en fonction du de la signification des attributs. Ils ne faut pas les déduire à partir du contenu courant d’une relation.

56

Normalisation des relations• Ensemble de règles introduites dans le modèle dès son origine ayant pour but de

garantir à la base de données toute sa cohérence lors de manipulation comme l'insertion, la mise à jour, la suppression.

• La normalisation évite les redondances de données.• Six formes normales (FN) (les trois premières sont les plus importantes) numérotées

de 1 à 5 avec une variante pour la troisième.• Processus important dans la phase de conception. La normalisation permet de définir

des relations de telle sortes qu'elles soient l'image d'objets du monde réel en permettant une affectation correcte des attributs dans différentes tables. C'est un outil puissant pour la définition sémantique des relations.

• Le FN ont été sous forme de règles de construction dans la plupart des méthodes de conception comme MERISE, IDA, AXIAL, REMORA.

• Normaliser une relation c'est la représenter sous une forme canonique respectant certains critères assurant la définition sémantique de la structure de la BD et l'intégrité des données. Elles a comme conséquence la décomposition de la relation non normalisée en un certain nombre d'autres relations.

• Les FN sont dépendantes ainsi une relation ne peut être en 2 FN que si elle est en 1 FN. A contrario une relation en 5 FN l'est en 4, 3, 2, 1 FN.

57

Dépendances

• Une dépendance est une contrainte exprimée dans une règle que doivent vérifier les données pour que la base soit dans un état cohérent par rapport à la réalité : une consultation médicale donnée concerne un patient et un seul. Un patient peut avoir plusieurs consultations.

• Dépendances fonctionnelles (DF) : Elles permettent de définir les formes normales de 1 à 3 avec sa variante (Boyce-Codd ou BCNF).

• Dépendances multivaluées (DM) : Elles permettent de définir la 4 FN.

• Dépendances de jointure (DJ) : Elles permettent de définir la 5 FN.

58

Dépendances fonctionnelles (DF)

• Il existe une dépendance fonctionnelle entre deux attributs A et B d'une relation R si à toute valeur de A on ne peut associer à tout instant qu'une et une seule valeur de B.

• Définition formelle– R(X,Y,Z) schéma de relation avec Z éventuellement vide.

• X->Y : X détermine Y ou Y dépend fonctionnellement de X dans R si pour tout tulpe <x,y,z>, <x’,y’,z’) de R , x=x’ => y=y’

• A est l'attribut source et B est l'attribut but : A -> B– NuPatient -> Nom est une DF– Nom ->NuPatient n’est pas une DF

• Si un attribut (ou un groupe d'attributs) détermine par DF tous les autres attributs de la même relation, c'est une clé de la relation.

59

Première forme normale

• Une relation est en première forme normale si :– Elle possède une clé

– Tous ses attributs sont atomiques : c'est à dire n'ayant à un instant donné qu'une seule valeur ou ne regroupant pas un ensemble de valeurs. Un attribut ne doit pas être lui même une relation.

• MALADE (NuMal, Nom, Caractéristiques, DteCons) 1 Dupond Masc,90Kg 10/10;20/10;30/11/93

• Caractéristiques n'est pas un attribut atomique

• DteCons n'est pas atomique car il regroupe plusieurs valeurs.

60

Première forme normale

• R est en première forme normale (1NF) si :– Tout attribut hors clé dépend fonctionnellement de la

clé– Ou si :

• Elle possède une clé et tous ses attributs sont atomique, c’est-à-dire que tous les attributs sont monovalués, ce qui exclut les attributs dont les valeurs seraient des ensembles ou des listes.

– Exemple :• Patient (N°patient,Nom de famille, date de Naissance, sexe)

est 1NF• Patient((N°patient,Nom de famille, date de Naissance, sexe,

date de consultation) n’est pas 1NF

61

Deuxième forme normale• Une relation est en deuxième FN si :

– Elle est en 1FN– Toutes les DF sont élémentaires par rapport à la clé : tout attribut hors clé ne

dépend pas d’une partie de la clé• ou encore si :

– pour toute variable n'appartenant pas à une clé de cette relation, chaque clé est minimale.

• TRAITEMENT (TypTT,NuMal,Salle)– Si salle dépend uniquement du type de traitement (Radiothérapie, Bloc

opératoire) indépendamment du NuMal, il existe une dépendance non élémentaire. La relation TRAITEMENT doit être éclatée en deux relations en 2 FN.

– R1(TypTT,NuMal)– R2(TypTT,Salle)

• Exercice– Mettre en deuxième forme normale

• Patient (N°patient, Date consultation, Nom)• Solution : Nom dépend d’une partie de la clé N°patient->Nom

62

Deuxième forme normale

• Le 2NF permet d’éliminer certaines redondances– Patient (N°patient,Nom)

– Consultation (N°patient*,Date consultation, ordonnance)

• Mais il peut rester des redondances …

Redondance de l’attribut capacité

N°Avion Constructeur Type Capacité PropriétaireAH321 Boeing B747 C1 Ait AlgérieAF564 Airbus A320 C2 Air FranceBA777 Boeing B747 C1 British AW

63

Troisième forme normale• Une relation est en troisième forme normale si :

– Elle est en 2 FN– Tout attribut hors clé est en DF directe par rapport à la clé.

• ou encore si:– R est en 2NF– Pour toutes variables n'appartenant pas à la clé de cette relation, il n'existe

pas un ensemble de variables hors clé qui soit une clé pour la variable considérée.

– TRAITEMENT(TypTT,NuRésa,NuMal,NomMal)• NuMal est une clé pour NomMal• R1(TypTT,NuRésa*)• R2(NuRésa,NuMal*)• R3(NuMal,Nom)

• Dans l’exemple précédant :– Constructeur et capacité ne font pas partie de la clé et dépendent de

l’attribut type on décompose en• Avion (N°avion,Type*,Propriétaire)• Modèle(Type, constructeur, capacité)

64

Troisième forme normale

• La 3NF permet d’éliminer des redondances, dues à des dépendances transitives entre attributs mais elle ne suffit pas parfois à éliminer toutes les redondances :– Codepostal (Code, Ville, Rue)– Les DF sont Code->Ville et Ville,Rue -> Code– Cette relation est en 3NF puisque aucun attribut non clé ne

dépend d’une partie de la clé ou d’un attribut non clé mais il y a des redondances :

Code Ville Rue54505 Vandoeuvre Aiguillette54505 Vandoeuvre Gal Leclerc

65

Forme de Boyce-Codd (BCNF)

• Une relation est en BCNF si :– Elle est en 3 FN– Tout attribut non clé de la relation n'est pas

source de DF vers une partie de la clé.• Ou

– Les seules DF élémentaires qu’elle comporte sont celle où une clé détermine un attribut.

• Dans l’exemple précédant :CodeVille (Code*, Ville)CodeRue (Code, Rue)Sont en BCNF, mais perte de la DF Ville,Rue ->Code

• Toute relation a une décomposition en BCNF sans perte d’information, par contre, une décomposition en BCNF ne préserve pas généralement les DF.

66

Exemple

• Soient 2 représentation équivalentes– R0 (N°Commande, N°Client, Date, Nom, N°Repres, Zone)– Et– R11 (N°Commande, Dte, N°Cli*) en 3NF– R12 (N°Client, Nom, N°Repres*) en 3NF– R13 (N°Repres, Zone) en 3NF

• Si l’on a :– 10 représentants, 100 clients par représentants et 100 commandes par

clients.– La forme R0 conduit à 100*100*6 = 60 000 données– R11 à 100 * 100 * 3 = 30 000– R12 à 100 *10*3 = 3 000– R13 à 10 * 2 = 20– Soit 33 020 données

67

Méthode de normalisation

• Il est souhaitable qu’un schéma relationnel ne comporte que des relations en 3NF ou BCNF.

• Des algorithmes de constructions permettent d’obtenir de tels schémas. Ils sont de eux catégories :– La méthode de décomposition :

• Elle se base sur la décomposition de relations en utilisant les DF entre les données. Cette méthode conduit à des relations en 3NF ou BCNF. Il y a 2 problèmes :

– Identification des DF et leurs exhaustivité– Le résultat dépend de l’ordre d’application des décompositions et peut

ne pas préserver les DF– La méthode synthétique

• Elle se base sur la représentation des DF en terme de graphes (graphe et leur couverture)

68

Méthode synthétique

• Point de départ– L’ensemble de tous les attributs– L’ensemble des DF entre attributs qui sont représentées dans un

graphe avec comme nœud un attribut et comme arc une DF

• Ce qu’il faut faire– Trouver la couverture minimale du graphe c’est-à-dire éliminer

les circuits ainsi que les DF non élémentaires et non directes

• Résultat– Une collection de relation en 3NF. Chaque schéma est obtenu en

prenant comme :• Clé une source de DF• Attributs, les buts des DF correspondant

69

Exemple• Service d’immatriculation de voitures dans une préfecture

– Soient les DF suivantes :• N°Immat -> Couleur, Type, Puissance, Marque• N°INSEE -> Nom, Prénom, Adresse• N°Immat -> N°INSEE• Type -> Marque, Puissance

– On crée le graphe :

N°INSEE N°Immat Type

Nom Prénom Adresse CouleurPuissance

MarqueOn supprime les transitivitésOn obtient :

Personne (N°INSEE, Nom, Prénom, Adresse)Voiture (N°Immat, Couleur, Type*, N°INSEE*)Types (Type, Puissance, Marque)

70

Passage d’un schéma entité/association à un schéma relationnel

• Transformer le schéma E/A en une collection de relations quelconques

• Normaliser les relations soit par la méthode synthétique soit par la méthode de décomposition ou en cherchant la clé minimale parmi les attributs

71

Dépendances multivaluées

• Il existe une dépendance multivaluée entre les attributs A, B et C d'une relation R si toute valeur de A on associe à tout instant plusieurs valeurs de B et C telles que :– Si il existe (a,b1,c1) et (a, b2, c2) alors il

existe (a, b1, c2) et (a, b1, c1)

• Elles mènent aux autres formes normales

72

Exercice

• Dans le cadre de la mise en place du PMSI, vous devez réaliser une base de données permettant pour chaque séjour d'un malade dans une unité médicale de traiter les éléments suivants : DteEnt, MEnt, DteSort,MSort,DP, 0 à n DS, 0 à m Actes, 0 à n Médecins TT)