Chapitre 1 : voir poly Chapitre 2 : modle entit-association (modle entitrelation)

I Dfinition (Cardinalit, Type dassociation, Mthode descendante) II Extension du modle Entit/Association 1) Le lien dans gnralisation-spcialisation 2) Agrgation 3) Identifiant

Chapitre 3 : Modle relationnel

I Dfinition II Introduction la conception des Bases de donnes (Cl et DF) III Passage du modle E/A au modle relationnel IV Dpendances fonctionnelles (AUG, TR, Armstrong, couverture rduite) V Forme Normal de Boyce-Codd (FNBC)

Chapitre 4 : Algbre Relationnel

I Les oprations de bases (union, projection, diffrence, slection, produit) II Autres oprations (intersection, jointure, division)

Chapitre 5 : S.Q.L.
I Requtes simples (projection, slection, produit et jointure) II Modification de la BD (insertion, suppression, mise jour) III Dfini un schma de relation en SQL

Chapitre 6 : X.M.L.

Introduction aux bases de donnes

Chapitre I : Chapitre II : I Dfinition
Entit : objet, notion abstrait, objet qui existe, qui peut-tre distingu Ex. : un gne (particulier), un tudiant (particulier), Groupe dentits semblables : ens. dentits Ex. : tous les tudiants de la licence BIBS Classe dentit : reprsente de manire abstraite lens. Ex. : (tre un) gne, tudiant, (une) protine. Cest un concept. Domaine : ens. de valeurs Ex. : les IR, {A, C, G, T} Attribut : proprit des entits de mme classe qui associe chaque entit de lens. dentit une valeur appartenant au domaine de lattribut. Ex. : auteur, date (cf. Medline), squence, Identifiant : mot cls : attribut ou ens. dattributs dont les valeurs identifient de faon unique une entit de lens. Lidentifiant dtermine fonctionnellement les valeurs des autres attributs. Ex. : Transtern (ACC, PCG) = cl Ex. : ETUDIANT (concept) Attribut : Nom, prnom, ntudiant (identifiant), date de naissance, Reprsentation graphique : ETUDIANT
Nom Prnom Nd_tudiant Date_de_naissance

voir poly

Modle entit-association (modle entit-relation)

Association : cest un regroupement dentits qui traduisent un certain domaine quon veut modliser. On regroupe les associations de mme nature en classes dassociation. Schmatiquement : ENTITE_1 Ex. : ETUDIANT EST_INSCRIT COU 2 ASSOCIATION ENTITE_2

Cas particulier : mre PERSONNE Enfant EST_MERE

On introduit la notion de rle qui permet de distinguer les deux liens : tiquette. Remarque : ici la relation nest pas symtrique. Ex. : 1 PERSONNE EST_COPAIN => association 2 symtrique Attribut dune classe dassociation : Cest une proprit qui dpend de toutes les entits intervenant dans lassociation. Ex. : ETUDIANT EST_INSCRIT COURS
Annee_de_la_1er_inscription

Remarque sur la modlisation : 1er travail : identifier les entits. Il ne sagit pas de toutes les recenser, mais de dgager celles qui sont pertinentes par lapplication. Idem pour les associations. Il faut aussi dfinir le contexte dans lequel on se place et la dure dutilisation. Dimension dassociation : nombre dentit qui la composent. On distingue 2 types : - associations binaires (cf. les ex. ci-dessus) - associations n-aires (n>2) : les autres Ex. : association n-aire : Un prof enseigne une matire un groupe dlve (TD) MATIERE
PROF ENSEIGNE TD tertiaire

Proprit : On ne cre dassociation n-aire que si on peut pas crer dassociation (n-1)-aire pour modliser le problme/lapplication.

Cardinalit dun couple entite-association : E : classe dentits (ex. : ETUDIANT) A : classe dassociation (ex. : INSCRIT) On dfinit m (resp. M) le nombre minimum (resp. maximum) dassociation de classe A pouvant exister pour une entit de classe E. (m, M) est la cardinalit du couple (E, A). Tout tudiant est inscrit au moins 1 cours et au plus 5. Tout cours a au moins 3 inscrit et au plus 100 tudiants. Ex.1 : ETUDIANT N_etudiant Nom Prenom 1, 5 EST_INSCRIT 3, 100 COUR Code_cour Intitule

Remarque : 1) m=0 ou m=1 possible m >1 possible aussi, on nest pas oblig de prciser la valeur. On note alors n. 2) M>1 possible et pas toujours prcis (on note alors n) 3) m=M=1 : chaque entit participe exactement 1 association. Ex.2 : 0, n ENSEIGNANT 1, 1 EST_RESP COUR

Un enseignant nest pas toujours responsable dun cours et peut-tre responsable de plusieurs cours. Un cours a un unique responsable. Ex.3 : 0, 1 ENSEIGNANT 1, 1 DIRIGE DEPARTEMENT

Un seul prsident de dpartement. Un enseignant ne peut pas diriger 2 (ou plus) dpartements. EX.4 : Enfant 0, 1 PERSONNE Mre 0, n EST_MERE

Type dassociation (typologie) : Associations binaires E, A, F 1) de type 1-1 : cas o une entit de E peut correspondre par lassociation A au une entit de F et rciproquement ( une entit de F peut correspondre A, au plus une entit de E). En termes de cardinalit : les deux cardinalits maximales M sont gales 1 (Ex.3) 4

2) de type 1-n (ou un plusieurs) : Cest le cas o une entit de E (resp. F) lassociation A fait correspondre plusieurs entits de F (resp. E) mais une entit F (resp. E) lassociation A fait correspondre au plus une entit de E (resp. F). En terme de cardinalit : les deux cardinalits maximales sont gales lune 1 et lautre n, n>1. (Ex.4) 3) de type n-m (ou plusieurs plusieurs) : A une entit de E, A associe plusieurs entits de F et rciproquement, c-a-d les deux cardinalits maximales sont >1. (Ex.1) Ex : PERSONNE parent enfant EST_PARENT DE

Mthodologie de construction des schmas E/A descendante : On part de lunivers du discours, dcrivant le systme tudi. Il y a diffrentes tapes : 1) Constituer un dico des donnes et une liste de rgles de gestion 2) Recenser les entits et les associations 3) Placer les attributs sur les entits et les associations 4) Calculer les cardinalits et les types dassociation 5) Vrifier que le schma est bien conu respecter les rgles du formalisme E/A regarder si la normalisation est bonne

25/02/04 1) Le lien dans gnralisation-spcialisation Cest un lien exprim par une dpendance IS-A (= est_un) entre un ou plusieurs entits spcialises et une entit gnrique. Ex.1 : (gnralisation) ENSEIGNANT IS-A CHARGE_TD Spcialises IS-A RESP_COUR --- entit --------- entit gnrique

II Extensions du modle E/A

La gnralisation consiste runir deux ou plusieurs classes dentits dun certain niveau suprieur -> renforce les similarits entre entits de niveau infrieur. La spcialisation consiste prlever une ou plusieurs sous-classe dune classe dentits dun certain niveau de faon crer une classe (ou plusieurs) classes dentits de niveau suprieur. -> Accentue les diffrences entre classe dentits des niveaux suprieurs et infrieurs, laide dattribut particulier ajout aux entits spcialises. On procde par hritage des attributs des entits du niveau suprieur pour les entits de niveau infrieur. Ex.2 : (spcialisation) ENSEIGNANT IS-A TITULAIRE
Grade Anc_grade

IS-A

Code_ens Nom_ens Adr_ens Tel_ens

VACATAIRE
Date_entree Nom_service Fct

Il ny a pas besoin de nouveau identifiant. Le VACATAIRE dispose de 7 attributs dont 4 par hritage, sa cl est code_ens. Idem pour TITULAIRE (7 -> 6) 2) Agrgation On peut avoir besoin de considrer que certaines association (avec les entits quelles lient) sont des entits de niveau suprieur. On effectue alors un regroupement appel agrgation. Ex.3 : Contexte dun personnel participant un projet et travaillant sur un certain nombre de machines. EMPLOYE PARTICIPE EXPLOITE
Numro

PROJET

MACHINE Cration par agrgation dune entit globale qui regroupe EMPLOYE et PROJET : entit PARTICIPANT.

Lattribut Numro dpend de EMPLOYE, de la MACHINE et du PROJET -> donc on le met au niveau de lassociation EXPLOITE. 3) Identifiants En gnral, lorsquon construit un schma E/A, on sarrange pour qu chaque entit, il y ait un attribut qui puisse tre un identifiant (un attribut ou plusieurs attributs). identifiant multi-composant Ex. : identifiant mono-composant

ETUDIANT
N-etud Note Cour

ENSEIGNANT
Nom Prenom Adresse Tel

Il y a plusieurs cas de figure : a) Lentit possde un seul identifiant : cest lidentifiant de rfrence. b) Lentit possde plusieurs identifiant : le concepteur du schma en privilgie un, quil appelle identifiant de rfrence ; les autres identifiants sont appels identifiants primaires. Dans ces deux cas on a une entit forte (a au moins un identifiant) c) Lentit na pas assez dattribut pour quon puisse trouver un identifiant primaire parmis ses attributs mais lentit est importante car elle intervient dans une association. Il sagit dune entit faible qui est ncessairement relie une entit forte dont elle dpend. Ex.4 : Contexte bancaire Entits : COMPTE attribut : N_cpt et Position TRANSACTION attribut : N_trans, Date et Montant Bien que ces transactions soient toutes individualisables, des transactions sur des comptes diffrents peuvent avoir le mme numro. => pas didentifiant primaire pour lentit TRANSACTION qui est donc faible. On appelle discriminant un ensemble dattributs de lentit faible qui permettent de la distinguer au sein de lensemble des entits faibles auxquelles elle appartient. Ex. : Pour un compte donn, connatre le N_trans suffit dterminer toute la transaction (on connat alors la date et le montant). Il sagit dune identification relative (ici par rapport un compte). On constitue un identifiant primaire pour lentit faible, en prenant un discriminant

primaire pour lentit faible, en prenant un discriminant pour elle et un identifiant primaire de lentit forte dont elle dpend. 1;n 1,n 1,1 entit forte COMPTE RELEVE TRANSACTION entit faible
N-cpt Position * N-cpt * N-trans Date Montant

Chapitre III : I Dfinition

Modle relationnel

Dfinition1 : Un domaine est un ensemble de valeurs Ex : D1 = IN (ensemble des entiers naturels) D2 = [0,1] (intervalle des rels compris entre 0 et 1) D3 = ensemble des chanes de caractres Dfinition2 : Un attribut est une variable qui prend ses valeurs dans un domaine. Ex. : N_cpt du dom D1 ; Nom et Prenom du dom D3 Dfinition3 : Une relation r sur les attributs A1, A2, , An de domaines respectifs D1, D2, , Dn est un sous-ensemble du produit cartsien D1 X D2 X X Dn, c-a-d un ensemble de n-uplet t1, t2, , tn tel que t1 appartient D1, t2 D2, , tn Dn. Ex.1 : Dom = {a, b, c} r1 sur les attributs A1 et A tel que D1=D2=Dom r1 = {(a, b), (a, c), (b, c)} Ex.2 : r2 sur les attributs NoM et VILLE tel que dom (NOM) = D3 et dom (VILLE) = D3 R2 = {(DUPONT, PARIS), (DURAND, PARIS), (TOTO, ORSAY)} Reprsentation dune relation sous forme de table. Chaque n-uplet est crit sur une ligne de la table dont les colonnes ont pour nom les attributs de la relation. Ex.1 : (suite) r1 : A1 A2 a b a c b c Ex.2 : (suite) r2 : NOM DUPONT DURANT TOTO

VILLE PARIS PARIS ORSAY

Dfinition4 : On appelle schma de relation dune relation r la liste des attributs de la relation r, avec pour chaque attribut son domaine. On note sch (r) = (A1 : D1, A2 : D2 ; ;An :Dn) ou encore R On dit que r est de schma R. Remarque : 1) Lordre des lignes na pas dimportance ; 2) Une table ne peut reprsenter une relation que sil ny a pas 2 lignes identiques ; 3) Chaque case de la table contient une seule valeur pour lattribut prise dans son domaine ; 4) Souvent on considre que lordre des colonnes na pas dimportance si les attributs sont nomms explicitement. Dfinition5 : Un schma de Base de Donnes Relationnelles B est un ensemble de schmas de relations R1, R2, , Rp. Dfinition6 : Soit B un schma de BDR : B = {R1, R2, Rp}. Une base de donnes relationnelles b sur B est un ensemble de relation [r1, r2, , rp} tel que sch (r1) = R1, sch (r2) = R2, , sch (rp) = Rp. Attention : Il y a bien sr plusieurs bases de donnes relationnelles sur un mme schma de BDR. Ex. : ex. de transtern 2 (cf. poly) : On a sur ce transparent une base de donnes relationnelle. Transtern = {Termtradseq, Termtradparam} b ={ r1 , r2 } Soit B le schma de la base de donnes TRANSTERN B= {R1, R2} R1 le schma de la relation TermTradseq et R2 celle de TermTradparam R1 = (Acc : D3 ; PCG : D3 ; 5Utr : {A, C, G, T}* ; PostAtg : {A, C, G, T}* ; 3Utr : {A, C, G, T}*) R2 = (Acc : D3 ; PCG : D3 ; Lem : D1 ; GC3 : [0,1] ; ENC : IR ; CAI :[0,1]) Remarque : Une BDR peut-tre vue comme un ensemble de table.

II Introduction la conception des Bases de Donnes

Ce qui est important est llaboration du schma de la base de donnes. Ce qui volue rapidement ce sont les donnes c-a-d les lignes dans les tables mais le nombre de tables et le nombre de colonnes dans les tables sont plus stables.

On part dune application. - On dispose dun univers U dattributs - On a des liens smantiques entre ces attributs ( dpendances de donnes) qui suggrent des regroupements entre ces attributs. La conception procde par dcompositions successives de lunivers pour obtenir un ou plusieurs schmas de bases de donnes. Dcomposition de U : un ensemble S = {R1,, Rq} de schmas de relation sur U. Critre satisfaire : 1) Economie de stockage : viter les redondances 2) Smantique clair : chaque n-uplet (= ligne dans une table) dcrit un fait et un seul 3) Facilit les traitements de mise jour des tables 4) Respecter les contraintes dintgrit qui sont des dpendances entre les donnes, mergeant de lapplication. (ex. : pour mettre jour lge, a ne peut quaugmenter) 05/03/04 Notion de cl : Soit U un univers (ensemble dattributs). Dfinition formelle : Une cl K reprsente une information minimale pour identifier les n-uplet de U qui nous intressent, de manire unique. Si on connat une valeur pour chaque attribut de K, K <= U, on connat le n-uplet de U correspondant. Dpendance fonction (DF) : X -> Y r de schma R vrifie x->Y Si chaque fois que 2 n-uplet ont mme valeur sur les attributs de X alors ils ont mme valeur sur les attributs de Y. Dfinition formelle de cl : Soit U un ensemble dattributs, soit F un ensemble de DF. K, infrieur ou gal U, est une cl de U par rapport F si : (1) K -> U est une DF qui se dduit de F (2) K est minimal pour cette proprit (1) : il nexiste pas K tel que K< K et K -> U est une DF qui se dduit de F. Remarque : Si on a un ensemble dattributs K<=U qui vrifie (1) et (2), on dit que K est une surcl. Proprit : Soit S un ensemble dattributs. S est une surcl si et seulement si S contient une cl.

10

Ex. : BD sur le cinma. U = { nom_salle, titre, horaire, spectateur} 2 schmas de relation : SALLE = {Nom_salle : string ; Horaire : integer ; Titre : string} VU = {} Spectateur : string ; Titre : string} Cl K1 pour SALLE par rapport R1 = (Nom_salle ; Horaire ; Titre) : K1 = {Nom_salle, horaire} Cl de K2 pour VU par rapport R2 = {Spectateur, Titre} : Si on ne prcise pas lhoraire, une personne peut avoir vu plusieurs films. Ici K2 = {Spectateur, Titre} DF : F = {Nom_salle, Horaire -> Titre} Remarque : il peut avoir plusieurs cls possibles. On appelle cl primaire une cl privilgie pour laccs aux donnes (dclare pendant la dfinition du schma de BD) Liens entre DF et identifiants en schma E/A Rappel : Identifiant = attributs ou ensemble dattributs dont les valeurs identifient de manire unique une entit dans un ensemble dentits. Ex.1 : Enseignant Nom-Ens Pre_Ens Fonct_Ens 0,n 1:n Est-Resp 1,1 Cours Code Libell 1,n n :m Inscrit 1,n Etudiant

Annee_1erinscr Num_Etu Nom_Etu Pren_Etu Adresse

Si on considre les attributs de lentit comme un schma de relation chaque identifiant on peut associer des DF : Nom_Ens, prenom_Ens -> fonction Code -> libelle Num_Etu, Pren_Etu, Adresse Ce dernier signifie que Num_Etu -> Nom_Etu ; Num_Etu -> Pren_Etu ; Num_Etu -> Adresse Cas dun couple (E, A) 1,1 : Est_Resp 1,1 Cours

11

On a aussi : Code -> Nom_Ens, Pren_ens (Remarque : on a aussi Code -> Fonction, mais cette DF peut-tre dduite des autres par transitivit). Cas des attributs dune classe dassociation Code, Num_Etu -> Annee_1erinscr

III Passage du modle E/A au modle relationnel

Ex.1 : avec E pour Enseignant ; A pour Est-Resp et E pour Cours Rgle de passage Rgle1 : A chaque classe dentits est associe un schma de relation contenant les attributs de lentit. Etudiant = (Num_Etu, Nom_Etu, Adresse) Cours= (Code, Libelle Enseignant = (Nom_Ens, Pren_Ens, Fonct_Ens) Rgle2 : Pour traduire une classe dassociation binaire entre deux classes dentits E et E tel que la cardinalit maximale du couple (E, A) est 1, on ajoute au schma de relation qui traduit E, (voir schma) un identifiant de la classe dentit E et les attributs de lassociation A. Cours <- Cours (Code, Libelle, Nom_Ens, Pren_Ens) Rgle 3 : Pour traduire une classe dassociation binaire de type n :m ou n_aires avec n>2, on cre un nouveau schma de relation contenant un identifiant de chaque classe dentits quelle relie, et tous les attributs de lassociation. On cre : Inscrit (Num_Etu, Code, Annee_1erInscr) Ex.2 : Client Num_client Nom_Client Commande Quantit Date Libelle_article Num_Article Article Succursale Nom_Suc Adr_Suc

CLIENT (Num_Client, Nom_Client) ARTICLE (Num_Article, Libelle_Article) SUCCURSALE (Nom_Suc, Adr_suc) COMMANDE (Quantit, Date, Num_Client, Num_article, Nom_suc)

12

11/03/04

IV Dpendances fonctionnelles (DF)

Dfinition : Soit U un schma de relation. On appelle DF toute expention : X -> Y Avec : X C= U, Y C= U qui se lit : X implique Y, X dtermine Y, X donne Y. Une relation u sur U satisfait X -> Y, si quels que soient deux n-uplets t et t de u, si t(X) = t(X) alors t (Y) = t(Y). On note u |= X -> Y satisfait t (X) : projection du n-uplet t sur les attributs de X. Ex. : U= {A, B, C, D} U t1 t2 t3 a b c d a b c d a b c d X= ? Y= ?

u |= A -> B u |= A -> D u |= C -> B

u |= D -> A u |= D -> B u |= AD -> B

u |= D -> AB

Remarque gnrale : Pour toute relation u de schma U : U |= X -> Y si Y C= Y (dpendance triviale) Implication smantique. Soit F un ensemble de DF sur un ensemble dattributs U, Soit f une DF sur U, non ncessairement dans F, On dit que F implique smantiquement f not F |= f si : Pour toute relation u sur U tel que u |= F alors u |= f Soit G un autre ensemble de DF, F |= G (F implique smantiquement G), si pour toute DF g de G on a F |= g F _ G ( F et G sont quivalents) si F |= G et G |= F Ex. : U = {A, B, C} F = {A->B, B->C} g = A->C On a bien F |= g

13

Preuve : Soit u une relation quelconque sur U Hyp : u |= A -> B (provient de u |= F) u |= B -> C (idem) Conclusion ??: u |= A -> C ? u|= g La conclusion atteindre est u satisfait A -> C ? A-t-on pour deux nuplets quelconque t et t avec t (A) = t(A) la proprit t (C) = t (C) ? Ou encore : soient t et t 2 n-uplets de u tel que t (A) = t(A). A-t-on t (C) = t(C) ??? On a t (A) = t(A) Or t et t sont 2 n-uplets de la relation y et u |= A -> B Donc t (B) = t(B) Or t et t sont 2 n-uplets de la relation y et u |= B -> C Donc t (C) = t(C), ce qui est la conclusion cherche. Axiomatisation de lensemble des DF (systme dArmstrong) Systme dinfrence : Soit F un ensemble de DF, soit f une DF, on note : F |-- f le fait que F engendre f (ou encore f se dduit de F ), sil existe une suite de DF f1, f2,, fn tel que fn = f et chaque f : (1>= i >= n) vrifie : soit fi appartient F soit fi sobtient partir des DF prcdents, c-a-d f1,..., fi-1 par application des rgles suivantes. a) Axiome : F|-- X -> b) Rgle dinfrence : Modus ponens : Ex. : Socrate est un homme, les hommes sont mortels => Socrate est donc mortel : p p->q q p -> p p ^ q -> p (i) rgle daugmentation (AUG) X -> Y |-- XZ -> YZ (ii) transitivit (TR) X -> Y, Y -> Z |-- X -> Z Ex. : F = { A -> C, B -> D} f= AB -> CD A-t-on : F |-- AB -> CD ??? F engendre-t-il f ?

14

Voici une suite de DF : f1, f2,, fn aboutissant f : f1 : A -> C (f1 appartient F) f2 : AB -> BC ( application de la rgle AUG f1 avec Z = {b} ) f3 : B -> D (f3 appartient F) f4 : BC -> CD (AUG f3) f5 : AB -> CD (application de TR sur f2 et f4) f5 = f (n=5) Conclusion : F |-- f Dautres rgles dinfrence se dduisent du systme dArmstrong et simplifient les dmonstrations : Union : X -> Y, X -> Z |-- X -> YZ Dcomposition : X -> YZ |-- X -> Y, X -> Z Pseudo-transitivit : X -> Y, YZ -> W |-- XZ -> W Inclusion : si Y C= Y alors F |-- X -> Y Thorme fondamental : (Armstrong ) La notion dimplication smantique est quivalente la notion de drivation dans le systme dinfrence. F |= f ssi F |-- f (= rsultat de correction de compltude) Dfinition : On appelle fermeture de F, not F+ lensemble de toutes les DF engendres par F : F+ = {f / F |-- f} Ex1 : F = { A->B, B-> C} U = {A, B, C} F+ = {A->B, B-> C, A -> C, AB ->C, AB->B, AB->A, A->A, AC->B, ABC->C, } Dfinition : Soit X C= U, soit F un ensemble de DF. La fermeture de X par rapport F, quon note X+F, est lensemble maximal Y tel qu : F |-- X -> Y X+F = max { Y tel que F |-- X -> Y} Ex1 (suite) : X = {A} X+F = {B, A, C} F |-- A -> ABC A+F = ABC (AB)+F = ABC (C)+F = C (B)+F = BC Proprit : X C= X+F

15

Input/output

E/S

I/O

Algorithme de construction de X+F : Input : U ensemble dattributs X C= U F ensemble de DF sur U Output : X+F fermeture de X par rapport F, X+F C= U Mthode : var local ferm Dbut Ferm : = X ; // on sait que X C= X+F Rpter pour chaque Y -> Z dans F Si Y C= ferm et Z nappartenant pas ferm Alors ferm := ferm Union Z Jusqu ce que ferm inchang ou ferm = U Renvoyer ferm Fin Remarque : algorithme polynomial Ex. : U = {A, B, C, D, E, F} F = {AB->C, D->E, BC->AD, CF->B} (AB)+F ?? Faire tourner lalgorithme : Ferme := {AB} *1er passage dans la boucle rpter : AB -> C : AB C= ferm ferm := {A, B, C} D -> E : rien BC -> AD : BC C= ferm ferm := {A, B, C, D} CD -> B : rien *Fin du 1er passage Ferm <> U et ferm a chang * 2me passage dans la boucle rpter : AB -> C : dj utilis D -> E : D C= ferm ferm := {A, B, C, D, E} BC -> AD : dj utilis CF -> B : rien Ferm <> U et ferm a chang * 3me passage dans la boucle rpter : AB -> C : dj utiliser D -> E : dj utiliser BC -> AD : dj utiliser CF -> B : rien * ferm non modifi -> on stop * on ressort : {A, B, C, D, E}

16

Conclusion : (AB)+F = ABCDE Thorme : F |-- X -> Y ssi Y C= X+F Remarque : Si Y C= X+F, on sait alors que X -> Y est drivable partir de F mais on ne connat pas la drivation. Algorithme pour savoir F |-- X -> Y 1. Calculer X+F 2. si Y C= X+F alors rpondre oui sinon rpondre non Ex. : sur (AB)+F (suite) (AB)+F : ABCDE on en dduit donc F |-- AB -> D car D appartient (AB)+F 19/03/04 Remarque : K est une surcl si K+ = U K est une cl s'il nexiste pas K C K tel que K+ = U Proprit : Si un attribut A napparat pas en membre droit dune DF, il appartient tout surcl. Ex. G = {A->B, B->C} A+ = {A, B, C} B+ = {B, C} C+ = {C}

Couverture rduite dun ensemble de DF

Soient F et G deux ensemble de DF, on dit que G est une couverture de F si G _ F. (G est quivalent F) On va dfinir la notion de couverture rduite en 3 tapes : 1) rduction droite 2) rduction gauche 3) limination des redondances Soit U un ensemble dattributs. Soit F un ensemble de DF sur U. 1) rduction droite Soit X -> Y appartenant F La DF X -> Y est rduite droite sil nexiste pas y C= y tel que F |-- X -> Y Lensemble F est rduit droite si toutes ses DF sont rduites droite.

17

Mthode : Remplacer chaque DF de la forme X -> A1, , An par : X -> A1 X -> A2 X -> An Ex. : F = { A->BC, D->E} Frd-droite = {A->B, A->C, D->E} 2) Rduction gauche La DF X -> Y est rduite gauche sil nexiste pas X C X tel que F |-- X -> Y. Lensemble est rduit gauche si toutes ses DF sont rduites gauche. Mthode : Pour chaque DF de la forme X -> Y, on regarde sil existe X C X tel que F |-- X -> Y et on remplace alors X -> Y par X -> Y. Attention : plusieurs sous-ensembles X sont possibles. Il y a plusieurs rductions gauche possibles. Ex. : F = {A->B, B->C, AE->C} Frd-gauche = {A->B, B->C, A->C} On pourra le supprimer par redondance F |-- Frd-gauche car F |-- A -> B F |-- B -> C F |-- A -> C Frd-gauche |= A -> B Frd-gauche |= B -> C Frd-gauche |= AE -> C

oui par AUG

3) Elimination des redondances F est redondant sil existe une DF f tel que F {f} |-- f Mthode pour obtenir un ensemble de DF quivalent non redondant : Pour chaque DF f : faire si Fcourant {fi} |-- fi Fcourant := Fcourant {fi} Avec Fcourant initialis F au dpart. Ex. (suite : F = {A->B, B->C, A->C} F sans redondance : 1) A -> B : { B->C, A->C} |-- A->B ?? B appartient A+ ?? -> rponse : NON { B->C, A->C} 18

(Rappel : G |-- X->Y ssi Y appartient X+G) A -> B non redondant NON B+ = {B} ne contient pas C {A->B, A->C} B->C non redondant 2) {A->B, A->C} |-- B->C ??

3) {A->B, B->C} |-- A->C ?? OUI par la rgle de TRANS Donc A->C est redondant F devient {A->B, B->C} Proprit : en appliquant les trois mthodes dans cet ordre un ensemble de DF F, on obtient une couverture rduite G de F (c-a-d G _ F, G rduit droite, G rduit gauche et G non redondant). Attention : Lordre dans lequel on applique les trois tapes de lalgorithme est fondamental. Ex. : F = {AB->C, B->A, C->A} (i) Dans lordre comme il faut : 1) rduction droite : F inchang 2) rduction gauche : a/ F |-- B->C ??
(1) (2) (3)

{AB -> C, B->A, C->A} |-- B->C ?? B+(1), (2), (3) = {B, A(2), C(1) } C appartient B+(1), (2), (3) donc F |-- B -> C On rduit gauche F et on obtient : F = { B->C, B->A, C->A} Inutile dtudier le cas b/ F |-- B->A 3) limination des redondances : F redondant ? F {B->A} |-- B->A F non redondant est {B->C, C->A} avec F _ F (ii) Dans un mauvais ordre

1) Rduction droite Rien ne change 2) limination des redondances 19

{B->A, C->A} |-- AB->C ?? (AB)+{A->B, C->A} = {A, B} Donc AB -> C non redondant {AB->C, C->A} |-- B->A ?? B+{AB->C, C->A} = {B} Donc B -> A non redondant {AB->C, B->A} |-- C->A ?? C+{AB->C, B->A} = {C} Donc C -> A non redondant Donc F est non redondant 3) Rduction gauche On peut remplacer (cf. prcdent) AB -> C par B -> C On obtient alors la fin des trois oprations dans le mauvais ordre F qui est encore redondant. On na pas avec cet ordre-l de couverture minimale.

V Forme Normal de Boyce-Codd (FNBC)

But : Concevoir un schma de BD dans lequel il ny a pas de n-uplets superflus en raison des dpendances fonctionnelles. Dfinition 1 : - soit U un univers (ensemble dattributs) - soit F un ensemble de DF (U, F) est en FNBC si chaque DF non triviale de F (c-a-d X -> Y avec Y non inclut dans X) pour partie gauche une surcl. Rappel : K C= U, K est une surcl sur U si K+ = U pour F K est une cl sur U sil nexiste pas K C K et K surcl. Ex.1 : U = {A, B, C} F1 = {AB->C, BC->A} (U1, F1) FNBC ? (AB)+F1 = ABC = U1 (BC)+F1 = BCA = U1 Oui cest en FNBC Ex.2 : U2 = {V, R, C} F2 = {VR->C, C->V} (U2, F2) FNBC ? VR -> C : (VR)+ = VRC = U2 C -> V : (C)+ = CV <> U2 Donc (U2, F2) nest pas FNBC

20

Dfinition 2 : Soit U = {A1, , An} un univers. On appelle dcomposition de U tout ensemble S = {R1, , Rn} de schmas de relation sur U ( Ri C= U, 1 <= i <= m) avec R1 U R2 U U Rm = U. Ex. : Base de donnes sur des produits et leurs fournisseurs. NOM ADR ITEM PRIX U= {N, A, I, P} Si on rduit les quatre attributs dans un mme schma, plusieurs problmes : COMMERCIALE N A I P Toto Paris PC 1 000 euros 1) redondance Ladresse du fournisseur est rpte autant de fois quil y a de produit vendu par lui. 2) Inconsistance potentielle Si un fournisseur change dadresse il faut modifier cette adresse dans tous les n-uplets. 3) Anomalie dinsertion On ne peut pas enregistrer ladresse dun fournisseur qil ne vend pas au moins un produit (on ne peut sen sortir en mettant des valeurs nulles). 4) Anomalies de suppression Si un fournisseur ne vend plus rien (on supprime tous les produits, ne pas perdre son adresse). Sur lexemple, il existe des DF exploiter pour la dcomposition : F = {N->A, NI->P} Une dcomposition possible pour rsoudre les problmes ci-dessus : S= [R1, R2}, R1 = {N, A}, R2 = {N, I, P} Dfinition3 : Une DF X -> Y sur U est applicable sur un schma de relation R C= U si XY C= U. Ex. : BD fournisseur suite N -> A nest pas applicable sur R2 mais est applicable sur R1. Dfinition 4 : Soit F un ensemble de DF sur U, soit R un schma de relation sur U. On note FR lensemble des DF engendres par F et applicables sur R, dfinie par : FR = {X->Y tel que F |-- X->Y et XY C= R } Ex. : F = {A->B, B->C}

21

U = {A, B, C} R1 = AB R2 = AC FR1 ={A->B} FR2 = {A->C} En effet F+rduit = {A->B, B->C, A->C} Dfinition 5 : Une dcomposition S = {R1,, Rn} de U est en FNBC par rapport F si (Ri, FRi) est en FNBC pour tout i = 1,,n. Ex. : BD des fournisseurs (suite) S = {R1, R2} R1 = NA et R2 = NIP S est-elle en FNBC par rapport F = {N->A, NI->P} ? (R1, FR1) FNBC et (R2, FR2) en FNBC ?? F+ = F (R1, FR1) = (NA, {N->A}) On regarde chaque DF de FR1 N -> A : N+ = {N, A} = R1 N est bien une surcl de R1 relativement FR1 OUI cest en FNBC. (R2, FR2) = (NIP, {NI->P}) On regarde chaque DF de FR2 NI -> P : (NI)+ = {N, I, P} = R2 NI est bien une surcl de R2 relativement FR2 OUI cest en FNBC. Conclusion : La dcomposition s est en FNBC

Proprit : Si (U, F) nest pas FNBC, il existe toujours une dcomposition S de U qui est FNBC par rapport F. Algorithme : 1. Choisir dans F une DF non triviale X -> Y tel que X nest pas une surcl (toujours possible car (U, F) non FNBC). 2. Dcomposer U en R1 = XY et R2 = U - (Y X) Ex. : A -> BC R1 = ABC Ex. : AB -> BC R1 = ABC U = {ABCDE} R2 = ADE U = {ABCDE} R2 = ABDE

22

Couverture rduite de {AB -> BC } {AB->B, AB->C } (rduction droite) {AB->B, AB->C} |-- B->B {B->B, AB->C} (rduction gauche) {AB->C} |-- B->B non rduit F = {AB->C} 3. Pour i = 1, 2 faire Si (Ri, FRi) est FNBC Alors Ri est une feuille Sinon recommencer tape 1 sur (Ri, FRi) 4. Renvoyer tous les schmas de relation obtenus ltape 2. Ex. : U = {A, B, C, D, E} F = {A->C, C->DE, D->C} (U, F) FNBC ? A+ = ACDF <> U A nest pas une surcl. (U, F) non FNBC Application de lalgorithme. D -> C R1 = DC R2 = ABDE
(1) (2) (3)

F+ = {A->C, C ->DE, D->C, A->D, C->D, D->E, A->E, C->E} C+ = CDE D+ = DCE E+ = E (AB)+ = ABCDE (BC)+ = BCDE (BE)+ = BE FR1 = {D->C, C->D} FR2 = {A->D, A->E, D->E, AB->D, AB->E, BD->E, } (R1, FR1) est FNBC -> feuille (R2, FR2) en FNBC ? NON On reprend avec R1 = DE FR1 = {D->E}

D -> E R2 = ABD FR2 = {A->D, AB->D, }

(R2, FR2) non FNBC car A nest pas une surcl (B non atteignable) On prend : A -> D 23

R1 = AD F+R1 = {A -> D} FNBC On obtient la dcomposition FNBC de U. S = { R1, R1, R1, R2 } = { DC, DE, AD, AB }

R2 = AB F+R2 = FNBC

Chapitre IV :

Algbre Relationnel

I Les oprations de bases

1) Union In : deux relations r et s de mme relation R Out : une relation rUs de mme schma R rUs = runion des n-uplets de r et de s Ex. : r A a c e R B b d b s A a g i R B b h j rUs A a c e g i R B b d b h j

2) Projection In : une relation r de schma R X un schma inclus dans R Out : une relation _X(r) de schma X _X(r) : ensemble des restrictions des n-uplets de r X. Ex. : _A(r) : A a c e A b d (on regarde A dans r)

_A(r) :

(on regarde B dans r)

3) Diffrence 24

In : deux relations r et s de mme schma R Out : une relation r-s de schma R r-s : lensemble des n-uplets de r qui ne sont pas dans s. Ex. : A r-s c e B d b

4) Slection In : une relation r de schma R une condition _ (exprimer avec v, ^, >, <, =, ) out : __(r) une relation de schma R __(r) : ensemble des n-uplets de r qui vrifie _. Ex. : _(A=a) ^ (Bd)(r) A B a b

5) Produit In : deux relations r et u de schma R et U respectivement Out : une relation rxu de schma R+U (somme disjointe des attributs de R et de U) rxu : ensemble des n-uplets t1.t2 avec t1 dans r et t2 dans u. U B u b g C f h rxu A R+U B B b g b g b g C f h f h f h

a b a b c d c d e b e b

renommer les attributs communs.

II autres oprations A => B _ _ A v B A ^ B _ _ ( _ A v _ B)

6) Intersection In : r et s deux relations dfinies sur le m^me schma R. Out : r _ s dfinie sur le schma R. r _ s = {n-uplets t tel que t appartient r et s}

25

Proprit : r _ s se dfinit partir des oprateurs primitifs : (i) r _ s = r (r-s) = s (s-r) (ii) r _ s = (r U s) [(r-s) U (s-r)] Ex. : R A a c e B b d b s A a g i B b h j r_s A a B b

7) Jointure Permet de composer deux relations laide dune condition de rapprochement (les n-uplets concatnes doivent avoir mme valeur sur les attributs en commun). In : r de schma R s de schma S out : r s de schma R U S Attention : Dans R U S, on ne rpte pas les attributs en commun. r s = {n-uplets t tel que t(r) appartienne r et t(s) appartienne s) Ex. : R A a c e B b d b B s b g C f h A rs a e B b b C f f

Proprit : r s = _RUS[__ (rxs)] Soient A1,..., An les attributs communs R et S R _ S = {A1, , An}

_ _ t (R.A1) = t (S.A1) ^ ^ t (R.An) = t (S.An)

Ex. : rxs R.A a a c c e e R.B b b d d b b U.B b g b g b g U.C f h f h f h

_: les n-uplets t cherchs doivent concider sur les attributs de R _ S.

26

__ (rxs)= {abbf, ebbf} r s = _RUS[__ (rxs)] un renommage des attributs prs. _{A, B, C}[_t(R.B) = t(U.B) (rxs)] = {abf, ebf} = r s Cas particuliers : (i) Si R _ S =, r s est un produit. (ii) Si R C= S, r s est une slection de n-uplets de S selon r. Ex. : A B A s a a e B b b f C e f g rs A a a B b b C e g

R a b c d

(iii) Ex. :

Si R = S, r s est r _ s. S s A B g h a b e f RUS=R A B rs a b e f

R A B r a b c d e f

8) Division Construire le quotient de la relation r par la relation s comme une relation q dont les n-uplets sont ceux qui, concatns avec nimporte quel n-uplet de s donne un n-uplet de r. Dans les nombres : R s r = (q*s) + reste Reste q (q*s) r Analogie avec la relation : on ne rcupre pas tous les n-uplets de r. In : r une relation dfinie sur le schma R s une relation dfinie sur le schma S tel que S C= R out : r / s une dfinie sur R-S (diffrence ensembliste entre deux ensembles dattributs) r/s = {n-uplets t tel que t appartient _R-S(r) et {t}x s C= r} Ex. : R S

27

A B C a b c a b c a b c a b c a b c a b c R-S A B a b A b A b

D d d d d d d

C c c

D d d

_R-S(r)

r/s

R-S A B a b a b

Ab appartient r/s car abcd appartient r et abcd appartient r Ab nappartient pas r/s car abcd nappartient pas r Il existe un n-uplet t1 de s tel que (ab.t1) nappartienne pas r Exercice : BD sportive PRATIQUE (Personne, Sport) EST_MEMBRE (Personne, Centre) PROPOSE (Centre, Sport) Q1 : Construire lexpression algbrique (requte) dcrivant les sports pratiqus par au moins une personne appartenant au moins un centre. PRATIQUE P S Prat Toto Toto Titi Titi Zo Jean sp1 sp2 sp1 sp3 sp4 sp5 prop PROPOSE C S c1 c1 c2 c3 c4 c4 c1 c1 sp1 sp4 sp3 sp2 sp3 sp5 sp2 sp3 MEMBRE P C mem Toto Titi Zo Zo c1 c2 c3 c1

rponse : {sp1, sp2, sp3, sp4} S PRATIQUE MEMBRE sp1 sp2 sp1 sp3 sp4 sp4 P Toto Toto Titi Titi Zo Zo C c1 c1 c2 c2 c3 c1

28

Q1 : _sport (Prat Mem) Q2 : Trouver les centre sportifs proposant tous les sports pratiqus par au moins une personne appartenant au moins un centre sportif. Q2 se greffe sur Q1. Rponse : {c1} Q2 _ PROPOSE / Q1 Schma (PROPOSE/Q1) = {C, S} schma (Q1) = { C } C Q2 C1 car c1 c1 c1 c1 sp1 sp2 sp3 sp4 appartient appartient appartient appartient Prop Prop Prop Prop

Chapitre V :

S.Q.L

Langage de requtes le plus populaire. Le noyau dur de S.Q.L est quivalent du point de vue expressivit lalgbre relationnelle standard : S.Q.L.2 (92), S.Q.L.3 venir Strucured Query Language

I Requtes simples

1) Forme gnrale des requtes

SELECT FROM . WHERE Tables : TERMTRADPARAM (ACC, PCG, Len, GC3, ENC, CAI) (cf. poly du 1er cours) Une requte scrit sous la forme : SELECT * FROM TERMTRADPARAM WHERE Enc < 500 ; Enc < 500 est une condition FROM clause : indique la ou les tables auxquelles la requte rfre Ici : table TERMTRADPARAM On peut aussi y trouver des variables n-uplets. 29

WHERE clause : condition sur les n-uplets de la table. (Remarque : condition facultative) Correspond en algbre relationnelle lopration de slection. SELECT clause : indique quels sont les attributs (colonnes de la table) des n-uplets rpondant la condition exprime dans le WHERE regarder pour la rponse. Correspond en algbre relationnelle lopration de projection. Ici : Ltoile indique quon garde toutes les colonnes (tous les attributs sont conservs) 08/04/04 2) Projection Voir poly avant dernier page Ex2 : SELECT Acc, Len FROM Termtradparam WHERE ENC < 54.0 AND Len > 2000 Rponse : (AB000223, 2979) Requte correspondante en algbre linaire : _ACC, Len [_(ENC < 54.0) ^ (Len > 2000)(Termtradparam)] On peut vouloir produire une relation avec les noms de colonne diffrents des attributs slectionns. On les renomme laide de AS.

Ex3 : SELECT Acc, AS Identifiant, Len AS longueur, FROM Termtradparam WHERE ENC < 54.0 AND Len > 2000 ; Rponse : Identifiant AB000223 Longueur 2979

On peut aussi utiliser une formule au lieu dun attribut dans la clause SELECT.

EX4 : SELECT Acc AS Identifiant, Len / 3 AS nbcodons FROM Termtradparam WHERE ENC < 54.0 AND Len > 2000

30

On peut mme utiliser une cl dans la clause SELECT.

Ex5 : SELECT Acc, AS Identifiant, Len / 3 AS longueur, codons AS nbcocons, FROM Termtradparam WHERE PCG = YBR182C Rponse : Identifiant AB000223 longueur 293 nbcodons codons

3) Slection Conditions construites laide : - de comparateur boolen : <, >, <>, =, <=, >= - doprateur arithmtique : +, *, - concatnation de chane : || La WHERE clause utilise AND, OR, NOT. Ex6 : SELECT Acc, Len FROM Termtradparam WHERE (Len > 2000 OR GC3 < 0.4) AND ENC < 50.0 ; 4) Produit et jointure SQL liste chaque table dans la FROM clause. Les SELECT et WHERE clauses peuvent rfrer nimporte quel attribut de ces tables. Ex7 : Trouver les Post Atg des descripteurs dont lENC > 50 SELECT Post Atg FROM Termtradparam, Termtradseq WHERE ENC > 50 AND Termtradseq.Acc = Termtradparam.Acc AND Termtradseq.PCG = Termtradparam.PCG ; Jointure en algbre relationnel : _Post atg (Termtradseq _ENC > 50 (Termtradparam)) Copies de relation : il faut dsambiguser les noms des attributs.

Ex8 : Trouver les paires de PCG correspondant au mme numro daccession Au dpart : Acc1 PCG5 Rponse : p1.PCG p2.PCG Acc1 PCG7 PCG5 PCG7 Acc2 PCG8 PCG8 PCG9

31

Acc2 PCG9 On introduit des variables n-uplets p1 et p2 : SELECT p1.PCG, p2.PCG FROM Termtradparam AS p1, Termtradparam AS p2, WHERE p1.Acc = p2.Acc AND P1.PCG < p2.PCG Les AS ne sont ncessaires que pour certain logiciel. Le < permet davoir PCG5 PCG7 mais pas PCG7 PCG5 (pas de redondance). (_Acc, PCG Termtradparam ) X ( _Acc, PCG Termtradparam)

Sous-requtes : imbrication de requtes.

a) La sous-requte retourne une unique valeur (1-uplet) Ex9 : VEND (bar, bire, prix) Trouver les bars qui servent lAdelscott au prix de la Guinness au bar La Cigale. SELECT bar FROM VEND WHERE bire = Adelscott AND Prix = (SELECT Prix FROM VEND WHERE bire = Guinness AND bar = La cigale) ; b) On sait seulement que le n-uplet cherch est dans une relation. Ex10 : BIERE (nom, fabricant) AIME (buveur, bire) Trouver le nom et le fabricant des bires que Jean aime SELECT * FROM BIERE WHERE nom IN ( SELECT BIERE FROM AIME WHERE buveur = Jean) ; On a de mme : NOT IN

32

Oprations assemblistes
UNION ( U ) INTERSECT ( _ ) EXCEPT ( \ ) (diffrence ensembliste) On peut aussi trouver MINUS Ex11 : AIME (buveur, bire) VEND (bar, bire, prix) FREQUENTE (buveur, bar) Trouver les buveurs et les bires tel que le buveur aime la bire et frquente un bar qui la sert. ( SELECT bire, buveur FROM VEND, FREQUENTE WHERE VEND.bar = FREQUENTE.bar) INTERSECT AIME ;

EXISTS R vaut vrai ssi R

Condition sur les relations

Ex12 : BIERE (nom, fabricant) Trouver les noms de bire qui dsignent lunique bire brass par la fabricant Q2 : SELECT nom FROM BIERE AS b1 WHERE NOT EXISTS ( SELECT * FROM BIERE WHERE fabricant = b1.fabricant AND Nom b1.nom) ; B1 est une variable n-uplet. NOT EXISTS (R2) R2 : sous requte corrle qui se rfre au n-uplet b1. R2 reprsente les n-uplets qui ont le mme fabricant que b1 et un nom de bire diffrent de celui de b1. Si R2 est vide, cest que b1 reprsente une bire qui est lunique bire de son fabricant.

relation dont on souhaite quelle soit vide = R2

33

BIERE (nom, fabricant) Nom b1 b2 b3 b4 b5 b6 b7 b6 fabricant f1 f2 f1 f1 f3 f3 f4 f1 rponse Q2 : b2 b7

(b2, f2) -> on construit R2 On regarde les lignes tel que fabricant = f2 et nom b2 il ny en a pas R2 ion peut garder (b2, f2) On aurait pu avoir b3 ?? Par ex. avec (b3, f1) R2 : on regarde les lignes dont le fabricant est f1 et tel que nom bire b3 On obtient 3 lignes. Donc R2 donc on ne peut garder (b3, f1) comme solution. Donc b3 nest pas dans la rponse.

Rptitions (doublons)
Une relation SQL est un multi-ensemble => les rptitions sont possibles un lment peut avoir plusieurs occurrences. Si on veut une seule occurrence dun lment, il faut utiliser DISTINCT Ex14 : SELECT DICTINCT FROM BIERE ; Rponse : f1, f2, f3, f4 On obtient une seule fois le nom de chaque fabricant. Attention : Les oprateurs ensemblistes liminent eux systmatiquement les doublons. Si on veut garder il faut utiliser : INTERSECT ALL, UNION ALL, EXCPET ALL

34

4) Agrgation Opration qui forme une valeur unique parti de la liste des valeurs apparaissant dans la colonne. SUM : somme des valeurs de la colonne, AVG : moyenne des valeurs de la colonne, COUNT : compte le nombre de valeur de la colonne, MIN : donne la plus petite des valeurs de la colonne, MAX : donne la plus grande des valeurs de la colonne. Attention : COUNT compte toutes les valeurs, y compris les doublonscompte le nombre de lignes. Ex15 : SELECT AVG (Len) FROM Termtradparam ; Solution : 3 Calcule la longueur moyenne des descripteurs de la table. Ex16 : On compte le nombre de n-uplets de la table. SELECT COUNT (*) FROM Termtradparam ; Solution : 3 5) Groupement Permet de grouper les n-uplets dune relation selon un certain critre (tel que pas ex. la valeur dune autre colonne) et de faire ensuite des agrgations au sein de chaque groupe. Ex17 : VENTE (bar, bire, prix) Trouver les prix moyens travers les bars de chaque bire SELECT bire, AVG (prix) FROM VENTE GROUP BY bire ; VENTE bar B1 B2 B2 B4 B5 bire bi1 bi2 bi3 bi1 bi2 prix p1 p2 p3 p5 p6

35

Ca forme des groupes BY : B1 B4 B1 B5 B2 bi1 bi1 bi2 bi2 bi3 p1 p5 p2 p6 p3

Do la rponse : Bire prix Bi1 (p1 + p5) / 2 Bi2 (p2 + p6) / 2 Bi3 p3 Remarque : Seuls les attributs qui apparaissent dans le GROUP BY peuvent apparatre dans la clause SELECT comme non agrgs.

6) Restriction de groupe On veut choisir des groupes bass sur une certaine proprit dagrgation du groupe lui-mme. GROUP BY HAVING <proprit> peut utiliser les variables n_uplet ou les relations provenant de la clause FROM et leurs attributs. EX. : BIERE (nom, fabricant) VENTE (bar, bire, prix) Donner le prix moyen des bires qui sont servies dans au moins 3 bars. SELECT bire, AVG (prix) FROM vente GROUP BY bire HAVING COUNT (*) > 3 Remarque : la clause HAVING peut rendre certains groupes vides. Ordre des clauses de SQL : SELECT, FROM, WHERE, GROUP BY, HAVING Sont obligatoires

36

II Modification de la BD

Les trois activits fondamentales : Insrer, supprimer et mettre jour. 1) Insertion = rajouter des n-uplets dans une table. INSERT INTO R (A1, , An) VALUES (v1, , vn) Ajoute le n-uplet (v1, , vn) la table R. 1) Si la liste dattributs A1, , An ne contient pas tous les attributs de R, alors le n-uplet cre dans R contient sur les attributs manquants la valeur NULL. 2) Inversement si le n-uplet ajouter R une valeur pour chaque attribut de R, il nest pas ncessaire de mentionner les noms des attributs. Il faut alors respecter lordre des colonnes, pour donner les valeurs v1, , vn. On peut aussi insrer dans une table des n-uplets dont les valeurs sont obtenues par une requte. Attention : Si le n-uplet est dj prsent, linsertion du n-uplet se fera et on aura une occurrence de plus. 2) Suppression DELETE FROM R WHERE <condition> Tout n-uplet de R vrifiant la condition est supprim de R. Sil y a des doublons, ils sont tous supprims. Attention : Une insertion suivie dune suppression ne redonne pas ncessairement la table initiale. 3) Mise jour UPDATE R SET <formules assignant de nouvelles valeurs certains attributs de la relation> WHERE <condition> Seuls les n-uplets vrifiant la condition voient leurs valeurs changer sur les attributs indiqus dans les formules.

37

Ex. : VENTE (bar, bires, prix) Pas de bire plus de 4 euros UPDATE VENTE SET prix = 4 WHERE prix > 4 ;

III Dfinir un schma de relation en SQL

1) Types de donnes a/ CHAR (n) : chane de caractre de longueur fixe n. VARCHAR (n) : chane de caractre de longueur n.

Implmenter comme un tableau. Ex. : Si chimary est la valeur dun attribut dclar VARCHAR (8), on a en fait : chimary__ b/ BIT (n) : chane de bits de longueur fixe n VARBIT (n) : chane de bits de longueur n c/ INT (ou INTEGER) d/ REAL (ou FLOAT) On peut aussi avoir DOUBLE PRECISION (comme en C): DECIMAL (n, d). e/ DATE TIME 2004-04-29 09 :00 :00

2) Dclaration de tables CREATE TABLE <nom> <liste des noms dattributs et leurs types> Remarque : On peut aussi faire apparatre dans la dclaration de table des dclarations de cls et/ou de contraintes. Ex. : CREATE TABLE VEND (bar CHAR (20), bire VARCHAR (20), prix REAL);

On peut aussi supprimer une table : DROP TABLE VEND ; 3) Modification dun schma de relation ALTER TABLE <nom> ADD < nom colonne et son type > // ajoute une colonne.

38

ALTER TABLE <nom> DROP <nom colonne> //supprime une colonne. 4) Valeur par dfaut Si la valeur dun attribut nest pas spcifie on peut utiliser la valeur NULL (on peut aussi explicitement interdire la valeur NULL). On peut aussi dclarer quun attribut doit avoir une vrai valeur. On peut aussi prciser soi-mme une valeur si aucune autre plus spcifique nest donne. Ex. : ALTER TABLE VEND ADD tlphone VARCHAR (16) DEFAULT unlisted ; 5) Cration dindexes et des primaires Etant donne une table, il peut y avoir plusieurs cls, mais seule une est choisie comme cl primaire. Une cl primaire peut contenir plusieurs attributs : Ex. {bar, bire} est une cl primaire pour la table VEND. Ex. : CREATE TABLE Vend (bar CHAR (20), bire VARCHAR (20), prix REAL, PRIMARY KEY (bar, bire));

Un fournisseur de BD peut associer systmatiquement un indice une cl si elle est dclare primaire, ce qui permettra dacclrer la recherche dans la table et demandera que lutilisateur spcifie quil veut un index pour dautres attributs. Ex. : CREATE INDEX BireIndex ON VEND (bire) ; Une requte spcifiant le nom de la bire retourne immdiatement les nuplets de la table VEND relatifs cette bire. Ex. : CREATE INDEX KeyIndex ON (VEND (bar, bire) Pour supprimer un index: DROP INDEX BireIndex 39

6) Contraintes Un certain nombre de systme commerciaux relationnel permettent dexprimer des contraintes : dclaration de cl primaire dclaration de cl trangre (intgrit rfrentielle) vrification sur les valeurs des attributs et sur les n-uplets (triggers) etc. = garde-fou a/ Cls trangres On peut dfinir un (ou des) attribut(s) dune table comme tant une cl trangre qui rfrence un (ou plusieurs) attribut(s) dune 2me table (ventuellement la mme). Le(s) attribut(s) de la 2me table rfrencs doivent tre dclars comme une cl primaire de la 2me table.

T2

T1

C cls primaire de T2 Cl trangre : A Toute valeur apparaissant pour un attributs de la cl trangre de la 1re table soit apparatre comme valeur dans les attributs correspondants de la cl primaire de la 2me table. Il y a contrainte dintgrit rfrentielle entre les attributs des deux tables.

Ex. : 2me table : CREATE TABLE Bire ( nom CHAR (20) PRIMARY KEY, fabr CHAR (20)); CREATE TABLE Vend ( bar CHAR (20) bire CHAR (20) REFERENCES Bire (nom) prix REAL PRIMARY KEY (bar, bires)) ;

40

Bire Nom

fabr

Vend bar bire

prix

On peut faire aussi des dclaration tel que : FOREIGN KEY < attributs > REFERENCES < table > (< attributs >) Doivent tre un cl primaire de la table Cette instruction est ajouter la fin dune CREATE TABLE. b) Violation de contrainte de cl trangre (i) Insertion ou mise jour dun n-uplet de la table Vend qui ne refaire aucune bire de la table Bire ; lopration est rejete. EX. : On a Bire Nom fabr b1 b2 f1 f2 Vend bire prix b1 b2 b2 p1 p2 p3

bar bar1 bar1 bar2

Insertion rejete: bar2 b3 p4 Mise jour rejete: remplace b2 par b3 (ii) Suppression ou mise jour dun n-uplet de la table Bire : qui a pour lattribut nom une valeur prsent dans certains n-uplets de la table Vend.

Ex. :On veut supprimer de la table Bire le n-uplet (b2, f2). Plusieurs possibilits : A- par dfaut, opration rejete B- politique en cascade : dans la cas dune suppression ds la table Bire, on supprime dans la table Vend les n-uplets rfrenant les noms de bires supprims. dans le cas dune mise jour dans la table bire on peut mettre jour dans la table Vend les n-uplets concerns.

41

Ex. : Dans bire, on remplace (b2, f2) par (b3, f2) ; alors on remplace dans Vend b2 par b3 mais ce nest pas super. C- mise NULL : on change les n-uplets de la table Vend qui rfrencent les n-uplets modifis de la table Bire et on met la valeur NULL dans les composants correspondants. Conditions sur les attributs : Il sagit de condition qui sont vrifies lorsque lattribut change de valeur ( cas dune insertion ou dune mise jour) mais pas une suppression. Ex. : CREATE TABLE vend (bar CHAR (20), bire CHAR (20), prix REAL CHECK (prix <= 6,00)); 06/05/04

Chapitre VI :

X.M.L.

Data on the web From Relational to Semi-Structured Data and XML S.Abitebout, P.Buneman 8-D-Sucin, Morgan Kaufman Publ 2000 Prsentation complte sur le web de Vincent Aguilera (INRIA) XML : eXensible Markup Language Cest le successeur HTML (Hyper Text Markup Language) et hritier de SGML (Standard Generalized Markup Language) Dfinition : XML est un langage de description et dchange de documents structurs. Historique : Rvolution Internet : HTML : + dun milliard de pages en HTML Beaucoup dapplication : banque, administration, fonds documentaires, commerce lectronique et bibliothques en lignes. HTML : le langage de description de pages sur le web. Ce nest pas adapt pour dcrire la structure dun document. - Besoin de prendre en compte des donnes irrgulires : structure irrgulire et volutive => Les BD semi-structures ont vu le jour.

42

Les deux mondes se rejoignent sur le web grce XML. Travail coopratif entre chercheurs et industries -> Consortium W3C (World Wide Web Consortium) Objectif : dfinir un formalisme pour faciliter lchange des donnes sur le web. 1966 : cration dun groupe de travail sur XML au sein du W3C. 1998 : publication de la recommandation pour lutilisation de la version 1.0 du langage. Proprits vises pour XML : 1) XML doit tre directement utilisable par Internet. 2) XML doit pouvoir supporter un grand nombre dapplication. 3) La cration de page doit tre trs facile. 4) XML doit tre compatible avec SGML. 5) XML ne doit pas possder de fonction facultative. 6) Souci de lisibilit 7) Syntaxe concise et formelle 7) 8) Prsentation de XML Proprit fondamentale : tant un document sparer les info de structure des info de prsentation. Voir feuille Ex. de la lettre et du document XML associ. En XML : on a la structure de la lettre mais on na aucune indication sur la mise en page. Il manque les info graphiques et typographiques du source XML. Ces infos sont donnes par la feuille de style . Feuille de style : cest un ens. De rgles qui permettent de spcifier la ralisation concrte dun document sur un mdia particulier. 2 types de langage pour crer des feuilles de style. 1) CSS : Cascading Style Sheet (Initialement conu pour HTML, sapplique bien XML). Permet de passer des supports mdia varis, cran dordinateur, tlphone portable, cran braille, 2) XSL : eXtensible Stylisheet Language. Cest un langage de rgles comme CSS. Permet en plus de modifier la structure du document. XML successeur de HTML : HTML : un ensemble prdfini de balises, qui ont des smantiques varies (les unes donnent des indications structurelles et les autres des indications de mise en page).

43

XML : va rendre indpendant laffichage du document de linterprtation quen fait le navigateur => le point fort : un auteur ou une communaut peuvent inventer librement des balises. Ex. Reprsenter une date (plusieurs faon de faire) 1) <date> 6 Mai 2004 </date> 2) <date> < anne> <mois > <jour > </date> 3) <date format 2004 </anne> 05 </mois> 06 </jour> = ISO-8601> 2004-05-06 </date>

Cette libert de choix dans les structures de donnes facilite lchange des documents. Toutes les donnes peuvent tre vues comme des documents XML : interoprabilit. Proprits de modularit et rutilisabilit Chaque utilisateur est libre de dfinir ses propres structures de document, mais il peut aussi se conformer des structures types appeles DTD (Dfinition de Type de Document). Chaque communaut peut alors proposer ses DTD et a des structures normalises. automatiser les traitements et possibilit de contrler la validit. 9) Avantage des documents structurs en XML Interrogation plus riche que sur des fichiers plats. Ex. : recherche de la protine MERLIN Fichier plat : recherche par mot-cls On obtient toutes les occurrences de chane MERLIN Cf. poly du 1er cour : on peut obtenir une protine qui na rien voit avec MERLIN, mais qui a pour sous-squence dacide amin : M.E.R.L.I.N. Document structur : on retourne les documents dont le <nom> de la <protine> contient MERLIN. <protine> <nom> ;< < </protine> XML 1.0 : description dun document XML Un document se dcompose : 44

1) un prologue (facultatif mais fortement conseill) < ? xml version = 1.0 standalone : yes ?> 2) un arbre dlments obligatoire < document> <salutation> Bonjour ! </salutation> </document> 3) des commentaires et instruction de traitements. Prologue : une dclaration XML facultative - de la forme : < ? xml version = 1.0 encoding = ISO-8859 > - indique au processeur qui va traiter le document : * la version du langage XML utilise * le codage des caractres * lexistence de dclarations extrieures du document. une dclaration de type de document, facultative - de la forme : <!DOC TYPE.exemple SYSTEM exemple.dtd [dclaration]> - indique la structure particulire que doit respecter le document. Arbre dlments : On impose un document XML les contraintes suivantes : Il existe dans le document un unique lment pre qui contient tout les autres : cest la racine du document. Tout lment distinct de la racine est totalement inclus dans son pre. Il ne peut y avoir de recouvrement partiel. Ex.1 :<p> <b> toto </p> titi </b> nest pas un document XML car chevauchement des balises. Ex. 2 : <lettre> <date> <anne> <mois> <jour> </date> <adresse> <rue> <numro> <ville> </adresse> </lettre> arbre :

2004 </anne> mai </mois> 5 </jour> Paris </rue> 15 </numro> Orsay</ville>

45

lettre date annes 2004-05-22 mois Mai jour 5 adresse rue Paris numro 15 ville Orsay

Un lment est de la forme : < nom attr = valeur> contenu

</nom>

< nom> : balise douverture </nom> : balise de fermeture contenu : dcrit le contenu de llment Ca peut-tre vide, du texte ou dautres lments, une imbrication de texte et dlments des instructions de traitement ou des commentaires. Attributs : valeur : reprsente un ensemble ventuellement vide dattributs cest dire de paires (nom, valeur) Un lment ne peut possder quun seul attribut de nom donn. Ex. : < rapport langue=fr dernier_motif=01-05-04> Dfinition : Un document est bien form si son prologue na pas de dclaration de type de document et si le document contient un arbre dlment. Dfinition : Un document est bien valide si son prologue contient une dclaration de type et si son arbre dlment respecte la structure dfinie par la dclaration de type. Ex. prologue : < ? xml version = 1.0 incoding = ISO-8859_1 standalone = yes ?> <!DOC TYPE document [ < ! ELEMENT document (salutation) > dclaration < ! ELEMENT salutation (#PC DATA) > ] > arbre dlments : 46

< document> < salutation > Bonjour ! </salutation> </document> Cest un document valide. Cette dclaration peut faire rfrence, par lintermdiaire dun URL un fichier externe, appel une DTD. Une DTD peut contenir des dclarations dlments de liste dattributs dentits gnrales, dentits paramtres. !ATTLIST : la dclaration dattributs dans un DTD permet de spcifier les attributs qui pourront ou devront tre associs des instances dlments. EMAIL TO FROM CC* BCC* SUBJECT BODY

<!ENTITY SIGNATURE BILL>

47