Systèmes d’information et Bases de données …prince/VP-enseign/ULIN401/ULIN401...a1 b1 c1 A B C a3 b2 c2 a2 b2 c3 a1 b1 c1 A B C Violaine Prince, [email protected] L’intersection

Systèmes d’information etBases de données (niveau 1)

Cours n° 6

Violaine Prince

Violaine Prince, [email protected]

Le modèle relationnel binaire

L’algèbre relationnelle Opérations algébriques sur les

relations

Opérations algébriques sur lesschémas

Expression algébrique des requêtes


Introduction à l’algèbrerelationnelle

Composée D’opérations algébriques ω endomorphes :ν ∀ r de schéma R, ω(r)= r’.

♣ A pour but d’exprimer des requêtes surles bases de données.

♣ Une requête est un programme/uneprocédure/une fonction, envoyé(e) à unSGBD, qui fournit un résultat sous forme detable ou un message d’erreur/table vide.


Opérations algébriques sur lesrelations

Propriétés Préservent les schémas Modifient les relations (population de n-

uplets)

L’union L’intersection Le complément La sélection



L’union Soient deux relations r et r’ de schéma R.

L’union de ces relations, r U r’ est unerelation de même schéma R, et dont lapopulation est l’union des populations de ret de r’.

Attention, les deux relations doivent êtrede même schéma, ou de schémascompatibles.



On dit que deux schémas de relation sontcompatibles si: Ils ont le même nombre d’attributs Les attributs se « correspondent » dans le même

ordre.

On dit que les attributs se correspondent s’ilsprennent leurs valeurs dans le mêmedomaine (et/ou s’ils ont un format physiqueidentique).


L’union : exemple Soit r de schéma R=(Date, Bataille, vainqueur)

NapoleonAusterlitz1802

SelimConstantinople

1453

François1ER

Marignan1515

vainqueurBatailleDate


L’union : exemple Soit r’ de schéma R=(Date, Bataille, vainqueur)

GouraudLibérationde Paris

1945

PétainVerdun1918

ClémenceauMarne1916



L’union : exemple La relation r U r’ est de schéma R et de population :

NapoleonAusterlitz1802

SelimConstantinople1453

François 1ERMarignan1515

GouraudLibération deParis

1945

PétainVerdun1918

ClémenceauMarne1916




L’intersection Soient deux relations r et r’ de schéma R. La

relation r ∩ r’ est de schéma R et sa populationest composée des n-uplets communs à r et à r’.

Remarque : si r et r’ n’ont aucun n-upletcommun (voir exemple précédent), alorsl’intersection est vide, et la relation r ∩ r’ estla relation vide.

On peut faire une intersection entre relationsde schémas compatibles.


L’intersection : exemple

Soit r de de schémaR=(A,B,C)

Soit r’ de schémaR=(A,B,C)

c2b2a2

c3b2a1

c1b1a1

CBA

c2b2a3

c3b2a2

c1b1a1

CBA


L’intersection : exemple

La relation r∩r’ est de schémaR=(A,B,C) et de population :

c1b1a1

CBA


Les opérations algébriquessur les relations

Le complémentaire Aussi nommé « différence » (représenté

par MINUS ou EXCEPT en SQL) Soient deux relations r et r’ de schéma R.

La relation r-r’ est de schéma R et depopulation :

Si r’ est inclus dans r, alors pop(r-r’) = pop(r)-pop(r’) Si r ∩ r’ est non vide, et r’ non inclus dans r alors

pop(r-r’) = pop (r) -pop(r ∩ r’)

Si r ∩ r’ est vide alors r-r’ est égal à r.


Le complémentaire: exemple

Cas d’inclusion:

c1b2a3

c2b2a1

c1b2a2

c1b1a1

CBA

c1b2a3

c1b1a1

CBA

r1

r2

c2b2a1

c1b2a2

CBA r1-r2


Le complémentaire: exemple

Cas d’intersection non vide sans inclusion

c1b2a3

c2b2a1

c1b2a2

c1b1a1

CBA

c1b2a4

c1b1a1

CBA

r1

r2

r1-r2

c1b2a3

c2b2a1

c1b2a2

CBA



La sélection : Opérateur qui prend en entrée une relation

r de schéma R Et qui rend en sortie une relation r’ de

même schéma R Mais telle que la population de r’ est une

sous-population de r Qui satisfait une (ou plusieurs) condition(s)

indiquée(s).



La sélection : Le format de la sélection est : σcondition(r) La condition est une expression logique atomique

ou composée: Elle utilise les opérateurs logiques et(∧), ou (∨), non(¬),

et les opérateurs de comparaison = , > , <. Elle est évaluée pour chaque n-uplet de la relation. Si elle est vraie pour un n-uplet x, alors x est sélectionné Sinon x n’est pas sélectionné Les n-uplets sélectionnés forment la population de la

relation résultante.


La sélection: exemple

Informations concernant la bataille deMarignan. Relation r :

NapoléonAusterlitz1802

SelimConstantinople

1453

FrançoisIer

Marignan1515

VainqueurBatailleDate


La sélection : exemple

Le résultat doit être le premier n-uplet. On écrit l’opération : σBataille=« Marignan »(r)

Cette sélection produit une relation r’ deschéma R et de population :

FrançoisIer

Marignan1515




On peut avoir des conditions multiplespour la sélection.

Ces conditions concernentobligatoirement des valeurs d’attributs.

Exemple : σX2>1 ∧ X3=‘val’(r)

Avec r ayant la configuration suivante :



val341

rep234

val134

X3X2X1

val341

X3X2X1

r

On obtient la relation suivanteRésultat de la sélection :

σX2>1 ∧ X3=‘val’(r)


Les opérations algébriquessur les schémas

Elles modifient les schémas (nombred’attributs)

Il en existe trois : La projection Le produit cartésien Les jointures

Et une quatrième, peu utilisée: Le quotient ou la division (à voir en niv. II)



Les opérations sur les schémas produisentde nouveaux schémas, mais aussi denouvelles relations, à partir des relations deschéma initial R. si r est de schéma R, l’opération ω (r) produit une

relation r’ de schéma R’ différent de R.

Par convention, quand on ne connaît pas lesrelations, on emploie le schéma commeargument de l’opérateur. A écrire sous la forme ω (R) où R est un schéma.



La projection: Soit une relation r de schéma R. R est un

ensemble d’attributs (A1, A2, …, An) La projection ΠX(r) produit :

Une relation r’, de schéma X

Où X est un sous-ensemble des attributsde R.


La projection : exemple

Soit une relation r de schémaR=(A,B,C,D)

d2c2b2a2

d1c3b2a1

d2c1b1a1

DCBA

On a ΠA (r) = r’

a2

a1

a1

A

R’ = (A)


La projection : exemple

Mais on peut aussi projeter sur 2attributs

d2c2b2a2

d1c3b2a1

d2c1b1a1

DCBA

On a ΠA,C (r) = r’’

a2

a1

a1

A

R’’ = (A,C)

c2

c3

c1

C


La projection

Propriétés : Soit r de schéma R = (A,B,C,D). ΠA,B,C,D (r) = r.

La projection préserve le nombre de n-uplets.

Elle modifie le nombre d’attributs. Par extension, ΠA (R) = R’ / R’= (A).



Le produit cartésien: Soient deux relations r et r’ de schémas

respectifs R et R’.

Soit R et R’ sont disjoints, auquel cas, leproduit cartésien r x r’ est une relation deschéma RUR’ et de population, le produitcartésien des n-uplets respectifs de r et der’.


Le produit cartésien : exemple

Soit r1 de schéma R1= (A,B,C) et r2 deschéma R2 = (D, E) telles que :

c2b2a2

c1b1a1

CBA

e2d2

e1d1

ED

r1 r2


Le produit cartésien : exemple Soit r3 produit cartésien des deux précédentes. C’est

une relation de schéma R1UR2= (A,B,C,D,E) et depopulation :

e2d2c2b2a2

e1d1c2b2a2

e2d2c1b1a1

e1d1c1b1a1

EDCBAr3


Le produit cartésien

Soit les schémas des relationsconsidérées ne sont pas disjoints. Soit X l’attribut commun aux deux schémas

de relation. Le schéma du produit cartésien contient X

deux fois : XR et XR’. Exemple R=(A,B,C,D) et R’ = (C,E).

Le schéma du produit cartésien est de la formeR’’= (A, B,CR, D, CR’, E).


Le produit cartésien

Le cardinal (nombre de n-uplets) de larelation résultant d’un produit cartésien estégal au produit des cardinaux des relationsmises en jeu.

Le produit cartésien touche : Le schéma (contrairement aux opérateurs union,

intersection, complémentaire et sélection) Les n-uplets (idem) Le cardinal (contrairement à la projection)



Les jointures Il existe plusieurs types de jointures

Jointure conditionnelle

Equijointure.

Une jointure est une sélection dans unproduit cartésien.

Soient r1 et r2 de schémas respectifs R1 et R2. r1 r2 , équivalent à σcondition (r1 x r2)

condition


La jointure conditionnelle La forme est : r1 r2

La condition : une comparaions entre valeursd’attributs des relations r1 et r2.

Le schéma de la jointure : R1UR2 La population de la jointure : les n-uplets de

r1 x r2 qui satisfont la condition exprimée Modifie : le schéma, les n-uplets, le cardinal. Par extension, peut s’écrire sur les schémas.

condition


Jointure conditionnelle :exemple

Soient deux relations r1 et r2 de schémasrespectifs R1 = (A,B,C) et R2= (D,E)

084

917

51217

CBA

r1

1813

36

ED

r2 On cherche à définir

La relation r1 r2 B>E



On réalise le produit cartésien r1 x r2

1813084

36084

1813917

36917

181351217

3651217

EDCBAOn choisit les N-uplets où BEst supérieurÀ E



Et on constitue la relation résultante r3

36084

3651217

EDCBA


Autres jointures

Jointure conditionnelle avec attributcommun. La condition ne porte pas sur l’attribut commun

• Se comporte comme toute jointure conditionnellestandard

La condition porte sur l’attribut commun: La condition est celle d’un comparateur de type > , <,

ou ≠ L’attribut commun est dupliqué dans le schéma (avec

schémas de provenance) et le schéma est donc R1UR2. Les n-uplets sélectionnés sont ceux qui vérifient la

condition.


Autres jointures Equijointure

Jointure conditionnelle avec attribut commun La condition porte sur l’égalité de valeurs de l’attribut

commun. Dans le schéma résultant, les colonnes totalement

identiques « fusionnent » ce qui donne un schéma R3 =R1UR2 -{X} (on en supprime un).

La condition est restreinte à la désignation de l’attributcommun.

Soient r1 et r2 de schéma R1 et R2, avec X commeattribut commun.

Équijointure : r1 r2

X


Equijointure : exemple

Soient r1 de schéma R1=(A,B,C) et r2de schéma R2=(C, D). On veut r1 r2

C

976

523

841

CBA

199

175

954

DC

r1r2



On commence par réaliser le produitcartésien r1 x r2.

199976

175976

954976

199523

175523

954523

199841

175841

954841

DC(R2)C(R1)BA

AChoi-sir



On récupère la sélection :

199976

175523

DC(R2)C(R1)BA

On fusionne ensuite les deux colonnes identiques

19976

17523

DCBA


Opérations algébriques

Tous les opérateurs s’écrivent parextension sur les schémas au lieu desrelations.

Cela signifie, par défaut, que sontconsidérées les relations courantes quiexistent avec ces schémas.


Effet des opérationsalgébriques

nonOui:prod. descard.

ouiOui. - siinclusion.

OuiOui :Σdes card.

Effet surlecardinal

ouiouinonnonnonnonEffet surles n-uplets

ouiOui. U

desschémas

nonnonnonnonEffet surleschéma

Projec-tion

Produitcarté-sien

Sélec-tion

Complé-mentaire

Intersection

Union


Effet des opérationsalgébriques

ouiouiEffet sur lecardinal

ouiouiEffet sur les n-uplets

Oui. Union desschémas -élément commun

Oui. Union desschémas

Effet sur lesschémas

EquijointureJointureconditionnelle


Expression algébrique desrequêtes

Question « posée » à la BD dont laréponse est : Une table Une valeur

Les questions dont les réponses sontdes tables peuvent être expriméescomme des compositions d’opérationsalgébriques.


Exemples

Convention : on exprime les requêtes sur lesschémas.

R= (Num-étu, Nom-étu, Prénom-étu, date-naiss, formation, composante)

Question : donner la liste des étudiants du L2info.

Interprétation : récupérer le numéro, le nomet le prénom de l’étudiant.

Expression algébrique : Πnum-étu, nom-étu, prénom-

étu( σformation=‘L2 info’(R))


Exemples

Question : quels sont les étudiants del’UFR qui sont nés avant 1988 ?

Interprétation : listes de noms etprénoms, ainsi que leur date denaissance.

Expression algébrique : Πnom-étu, prénom-étu, date-naiss(σcomposante =‘UFR’ et

date-naiss <1988(R))


Exemples Utilisation des opérateurs ensemblistes tels que le

complémentaire ou l’union. Question : quels sont les étudiants de l’UFR qui ne

sont pas nés en 1988 ? Interprétation : la précédente table obtenue ne traite

que de ceux qui sont nés avant, pas de ceux qui sontnés après.

Deux expressions algébriques possibles : Soit c’est l’union de ceux qui sont nés avant et ceux qui sont

nés après 1988. Soit c’est l’ensemble des étudiants, saufs ceux qui sont nés

en 1988


Exemple Première expression : union des tables.

Πnom-étu, prénom-étu, date-naiss(σcomposante =‘UFR’ et date-

naiss <1988(R)) U Πnom-étu, prénom-étu, date-

naiss(σcomposante =‘UFR’ et date-naiss >1988(R)) Deuxième expression : complémentaire.

Πnom-étu, prénom-étu, date-naiss(σcomposante =‘UFR’(R))-Πnom-étu, prénom-étu, date-naiss(σcomposante =‘UFR’ et date-

naiss =1988(R))Que l’on peut mieux exprimer en factorisant :

Πnom-étu, prénom-étu, date-naiss(σcomposante =‘UFR’(R -σdate-nais =1988(R))


Exemples Prof= (Nom-p, Prénom-p, départ.) Etudiant = (Num-étu, nom-étu, prénom-étu, date-

nais, formation, composante) Matière=(code-mat, nom-mat, discipline) Enseigne-à= (Nom-p, Prénom-p, Num-étu, code-

mat)

Question : quelles sont les matièresenseignées par le professeur Durand?

Interprétation : on veut une liste de noms dematières, ou une liste noms de matière etdiscipline. On choisit le deuxième cas.


Exemples

Expression algébrique : Πnom-mat, discipline(σ nom-p=‘Durand’(Enseigne-

à) Matière)

Les opérations de jointure sontcommutatives et associatives.

Attention : ce n’est pas le cas de lasélection et de la projection.

Code-mat


Optimisation algébrique

Chaque jointure est très « coûteuse ». Limiter au mieux la taille des tables jointes.

Sur la table « Matière » on ne peut enleveraucune colonne.

Sur la table Enseigne-à, on peut enlever« prénom-p », « num-étu »

Πnom-mat, discipline(Π code-mat(σnom-p=‘Durand’( Enseigne-à) )

Matière))) Code-mat

Documents

Systèmes d’information et Bases de données …prince/VP-enseign/ULIN401/ULIN401...a1 b1 c1 A B C a3 b2 c2 a2 b2 c3 a1 b1 c1 A B C Violaine Prince, [email protected] L’intersection