Programmation logique et contraintes dans les

bases de données

Cours 2 : Algèbre relationnelle

Dans ce cours ...

●
...nous parlerons de :
●
« Variantes » du modèle relationnel
●
Algèbre Relationnelle (AR)
●
Opérateurs
●
Règles d’équivalence
●
Contraintes d’intégrité exprimées avec l’AR

2 Programmation logique et contraintes dans les bases de données

Ressources et remerciements

●
Ce cours s’inspire des diapos de Wolfgang Gatterbauer, Michel Soto et Pierre Senellart, ainsi que
du livre Database Systems: The Complete Book de Hector Garcia-Molina, Jeff Ullman, et Jennifer
Widom ; je remercie chaleureusement mes collègues pour ce matériel !
●
Les diapos de Wolfgang Gatterbauer correspondant au contenu de ce cours sont disponibles ici :
●
[Link]
●
[Link]
●
[Link]
●
Les diapos de Michel Soto correspondant au contenu de ce cours sont disponibles ici :
[Link]
[Link]
●
Le chapitre 2 du livre Database Systems: The Complete Book, portant sur l’Algèbre Relationnelle,
est disponible ici : [Link]
●
De nombreuses autres ressources sont disponibles en ligne (Wolfgang Gatterbauer en cite sur la
page de son cours [Link] (partie
Litterature list) , ainsi que dans les «grands classiques BDD » comme par exemple
[Link] , que vous pouvez trouver à la BU ! : )

3 Programmation logique et contraintes dans les bases de données

Dans ce cours ...

●
...nous parlerons de :
●
« Variantes » du modèle relationnel
●
Algèbre Relationnelle (AR)
●
Opérateurs
●
Règles d’équivalence
●
Contraintes d’intégrité exprimées avec l’AR

4 Programmation logique et contraintes dans les bases de données

Modèle relationnel : rappels

●
Dans le modèle relationnel, les données sont structurées
en tables
●
Chaque table a un schéma : son nom, l’ensemble de ses
attributs (ou colonnes), ainsi que les types ou domaines de
chacun de ces attributs
●
Ex : Etudiants (NumEtu : string, Moyenne : real, annéeNaissance : int)
●
Il existe certaines variations autour de la définition du
schéma, ainsi qu’autour du contenu « autorisé » dans les
tables
●
Nous en avons déjà mentionné certaines en parlant de SQL...

5 Programmation logique et contraintes dans les bases de données

Modèle relationnel : perspective nommée vs
perspective non-nommée

●
Schéma exemple : Etudiants (NumEtu : string, Moyenne : real, AnnéeNaissance : int)
●
Si nous supposons que chaque attribut a un nom, cela correspond à la perspective
nommée
●
L’ordre des colonnes n’a dans ce cas aucune importance, car chaque colonne est identifiable par son
nom ; nous pouvons décrire un tuple de la table Etudiant en utilisant
(NumEtu= ‘IJ1’, Moyenne=17.3, AnnéeNaissance=2000), mais aussi en utilisant
(AnnéeNaissance=2000, NumEtu= ‘IJ1’, Moyenne=17.3)
●
Nous pouvons également adopter la perspective non-nommée ; dans ce cas, les
colonnes n’ont pas de nom mais sont identifiées sans ambiguïté par leurs indices
●
L’ordre devient donc essentiel pour savoir que telle valeur correspond à telle colonne
●
Nous décrivons le tuple Etudiant par (‘IJ1’, 17.3, 2000) ; la première valeur doit toujours correspondre au
numéro étudiant etc.
●
Cela pourrait vous rappeler le concept de « relation » en maths ; )

6 Programmation logique et contraintes dans les bases de données

Modèle relationnel : sémantique
ensembliste vs multi-ensembliste

●
Nous avons brièvement parlé de l’aspect « sans
doublons » : SQL et les SGBDR permettent les doublons
dans les tables (et les résultats de requêtes),
s’inscrivant ainsi dans la sémantique multi-ensembliste
(multi-set, ou bag)
●
...Mais la majorité de la théorie des bases de données
relationnelles est faite pour la sémantique ensembliste
(set), plus sympathique à manipuler : )
●
Des extensions aux multi-sets existent souvent, pas toujours

7 Programmation logique et contraintes dans les bases de données

Modèle relationnel : attributs non typées

●
Dans les implémentations, les attributs sont toujours
typés
●
Lors des analyses théoriques, on fait souvent
abstraction du type des attributs et on considère qu’ils
ont tous un type/domaine universel D
●
Ce qui nous amène donc à omettre le type des attributs lorsqu’on
décrit un schéma

8 Programmation logique et contraintes dans les bases de données

Dans ce cours ...

●
...nous parlerons de :
●
« Variantes » du modèle relationnel
●
Algèbre Relationnelle (AR)
●
Opérateurs
●
Règles d’équivalence
●
Contraintes d’intégrité exprimées avec l’AR

9 Programmation logique et contraintes dans les bases de données

AR : au commencement …

●
Codd : le père du modèle
relationnel
●
Article à lire:
[Link]
avid/cs848s14/codd-relati
[Link]
●
Ne parle pas de SQL mais
introduit d’autres
langages de requête, dont
l’Algèbre Relationnelle

10 Programmation logique et contraintes dans les bases de données

AR : les bases

●
De manière générale, l’algèbre étudie les structures
algébriques, qui consistent en :
●
Un domaine, ou ensemble d’éléments
●
Un ensemble d’opérateurs
●
Chacun d’arité d, prend « en entrée » d éléments et produit un élément du co-
domaine (qui est souvent le même que le domaine)
●
Un ensemble d’axiomes (ou identités) que ces opérateurs doivent
respecter
●
Par exemple, commutativité : op(x,y) = op(y,x)

11 Programmation logique et contraintes dans les bases de données

AR : les bases

●
Dans l’Algèbre Relationnelle, les éléments sont des
relations
●
Tout opérateur retourne également une relation, on
peut ainsi les composer et toute expression résultante
retournera elle aussi une relation
●
Pour présenter les opérateurs de l’AR, nous allons
adopter par la suite la perspective nommée
●
Mais cela peut s’adapter à la perspective non-nommée

12 Programmation logique et contraintes dans les bases de données

AR : les bases

●
L’Algèbre Relationnelle dans sa version « classique »
adopte la sémantique ensembliste ; de plus, il n’y a
aucun ordre entre les tuples d’une relation, et les
valeurs NULL ne sont pas permises
●
Nous nous focalisons sur cette version dans ce cours
●
Il en existe des version étendues prenant en compte les
multi-sets, proposant du tri, du regroupement et
agrégation etc.
●
Hors du cadre de ce cours

13 Programmation logique et contraintes dans les bases de données

Dans ce cours ...

●
...nous parlerons de :
●
« Variantes » du modèle relationnel
●
Algèbre Relationnelle (AR)
●
Opérateurs
●
Règles d’équivalence
●
Contraintes d’intégrité exprimées avec l’AR

14 Programmation logique et contraintes dans les bases de données

AR : les opérateurs

●
L’AR comporte 5 opérateurs «de base» : sélection,
projection, produit cartésien, union et différence.
●
...A ceux-ci se rajoute un opérateur « à part » qui est le
renommage
●
...Et des opérateurs dérivés : jointure, intersection,
division !

15 Programmation logique et contraintes dans les bases de données

AR : Sélection

●
La sélection (ou restriction) est un opérateur unaire qui
retourne tous les tuples d’une relation qui respectent
une condition
●
Notée σc (R), avec c la condition de sélection ; cette
condition peut être n’importe quelle combinaison
booléenne (avec des ET, OU, NON) de comparaisons (avec
=, <=, >=, >, <, <>) d’attributs entre eux ou avec des
constantes.
●
Le schéma du résultat de la sélection est le même que
celui de la relation fournie en entrée

16 Programmation logique et contraintes dans les bases de données

AR : Sélection
Etudiants
NumEtu Nom MoyenneS1 MoyenneS2

IK20 Toto 15.2 10.7

JP13 Titi 7.2 10.5
AX11 Tata 18 16.4
BT01 Tutu 12 12

σ Nom=’Toto’
Etudiants

NumEtu Nom MoyenneS1 MoyenneS2

IK20 Toto 15.2 10.7

17 Programmation logique et contraintes dans les bases de données

AR : Sélection
Etudiants
NumEtu Nom MoyenneS1 MoyenneS2

IK20 Toto 15.2 10.7

JP13 Titi 7.2 10.5
AX11 Tata 18 16.4
BT01 Tutu 12 12

σ MoyenneS1<MoyenneS2 Etudiants

NumEtu Nom MoyenneS1 MoyenneS2

JP13 Titi 7.2 10.5

18 Programmation logique et contraintes dans les bases de données

AR : Sélection
Etudiants
NumEtu Nom MoyenneS1 MoyenneS2

IK20 Toto 15.2 10.7

JP13 Titi 7.2 10.5
AX11 Tata 18 16.4
BT01 Tutu 12 12

σ MoyenneS1>=10 ^MoyenneS2>=10 Etudiants

NumEtu Nom MoyenneS1 MoyenneS2

IK20 Toto 15.2 10.7

AX11 Tata 18 16.4
BT01 Tutu 12 12

19 Programmation logique et contraintes dans les bases de données

AR : Projection

●
La projection est un opérateur unaire qui enlève
certaines colonnes d’une table et enlève les doublons
du résultat (sémantique ensembliste ! )
●
Le schéma du résultat comprend les colonnes retenues
dans la liste de projection
●
Notation : Π A1,A2,..,AN , avec A1,A2,..,AN l’ensemble
d’attributs retenus

20 Programmation logique et contraintes dans les bases de données

AR : Projection
Produit
NomProduit Categorie Prix Fabricant
Truc Gadgets 20 GadgetKing
SuperTruc Gadgets 40 GadgetKing
SingleTouch AppareilsPhoto 150 Canon
MultiTouch Maison 250 Hitachi

Π NomProduit, Categorie Produit

NomProduit Categorie

Truc Gadgets
SuperTruc Gadgets
SingleTouch AppareilsPhoto
MultiTouch Maison

21 Programmation logique et contraintes dans les bases de données

AR : Projection
Produit
NomProduit Categorie Prix Fabricant
Truc Gadgets 20 GadgetKing
SuperTruc Gadgets 40 GadgetKing
SingleTouch AppareilsPhoto 150 Canon
MultiTouch Maison 250 Hitachi

Π Categorie Produit

Categorie

Gadgets
AppareilsPhoto
Maison

22 Programmation logique et contraintes dans les bases de données

AR : Produit cartésien

●
Le produit cartésien, noté x, est un opérateur binaire
qui correspond tout simplement au produit cartésien
de deux relations
●
Cela veut dire toutes les « combinaisons possible » avec un tuple de
la première relation et un tuple de la deuxième relation
●
C’est une opération rarement utilisée en pratique dans
les SGBD, on lui préfère les jointures (voir suite du
cours : ) )

23 Programmation logique et contraintes dans les bases de données

AR : Produit cartésien

Produit x Entreprise

24 Programmation logique et contraintes dans les bases de données

AR : Union et Difference

●
En AR, l’union et la différence correspondent aux
opérateurs binaires classiques sur les ensembles, dont
on reprend la notation : ∪ respectivement –
●
Pour pouvoir appliquer ces opérateurs à deux
relations, il faut que ces relations aient les mêmes
attributs.

25 Programmation logique et contraintes dans les bases de données

AR : Union et Différence

EffectifsModélisation EffectifsBDDAvancées

NumEtu Nom NumEtu Nom

IK20 Toto IK20 Toto
JP13 Titi JP13 Titi
AX11 Tata BT01 Tutu
EffectifsModélisation U EffectifsBDDAvancées

NumEtu Nom
IK20 Toto
JP13 Titi
AX11 Tata
BT01 Tutu

26 Programmation logique et contraintes dans les bases de données

AR : Union et Différence

EffectifsModélisation EffectifsBDDAvancées

NumEtu Nom NumEtu Nom

IK20 Toto IK20 Toto
JP13 Titi JP13 Titi
AX11 Tata BT01 Tutu
EffectifsModélisation - EffectifsBDDAvancées

NumEtu Nom

AX11 Tata

27 Programmation logique et contraintes dans les bases de données

AR : Renommage

●
Opérateur « spécial », noté ρ ; ne change pas l’instance,
change uniquement les noms de tables ou d’attributs
●
On en a besoin uniquement si on utilise la perspective
nommée
●
Plusieurs conventions / usages :
●
ρS(R) – renomme la relation R en S
●
ρS (A1→ B1, A2→ B2,…,An->Bn) (R) – renomme la relation R en S et les attributs
A1,…,An de R en B1, …, Bn de S
●
ρA1→ B1, A2→ B2,…,An->Bn (R) – renomme uniquement les attributs de R

28 Programmation logique et contraintes dans les bases de données

AR : Renommage

●
Exemple : schéma R(A,B)
●
Produit cartésien RxR – problème car les deux relations
ont les mêmes colonnes ; dans le modèle relationnel,
une relation ne peut pas avoir deux colonnes de même
nom !
●
Solution : RxρR1(R)
...ou alors RxρA->A1, B→B1(R)…

29 Programmation logique et contraintes dans les bases de données

AR : Jointures

●
Les jointures sont des opérateurs dérivés, qui peuvent
donc s’écrire de manière équivalente en utilisant
certains opérateurs « de base »
●
Toutefois, leur intérêt en pratique est énorme et les
algorithmes utilisés par les SGBDR pour calculer le
résultat d’une jointure vont rarement utiliser les
opérateurs de base ; à cause de cela, les jointures
arrivent en pratique « au premier rang » de l’AR ! : )

30 Programmation logique et contraintes dans les bases de données

AR : Théta-jointures (jointures à conditions)

●
La théta-jointure, notée ⋈c, sélectionne dans le produit cartésien de
deux relations R et S les tuples qui respectent la condition c
●
On utilise aussi θ pour la condition, ce qui explique le nom de ces jointures ; )
●
C’est « le cas le plus général de jointure », dont la sémantique peut
s’exprimer très simplement en utilisant la sélection et le produit
cartésien :
R ⋈cS = σc(R x S)
●
Attention, le fait que la sémantique de la théta jointure correspond à ceci ne veut pas du
tout dire qu’en pratique cela sera implémenté en calculant le produit cartésien puis en
opérant une sélection !!!
●
La condition de jointure c correspond donc à une condition de
sélection valide sur le produit cartésien

31 Programmation logique et contraintes dans les bases de données

AR : Equi-jointures

●
Une équi-jointure est une jointure où la condition c
consiste en une conjonction d’égalités
●
Le type de jointure le plus utilisé en pratique !
●
Exemple :
●
Rel1 : Produit (NomProduit, Catégorie, Prix, Fabricant)
●
Rel2 : Entreprise (NomEntreprise, Pays, PrixAction)
●
Pour avoir les produits avec les infos de leur fabricant, équi-jointure :
Produit ⋈Fabricant = NomEntreprise Entreprise

32 Programmation logique et contraintes dans les bases de données

AR : Equi-jointures

Produit ⋈Fabricant = NomEntreprise Entreprise

NomProduit Categorie Prix Fabricant NomEntreprise Pays PrixAction

Truc Gadgets 20 GadgetKing GadgetKing France 25

SuperTruc Gadgets 40 GadgetKing GadgetKing France 25
SingleTouch AppareilsP 150 Canon Canon Japon 65
hoto
MultiTouch Maison 250 Hitachi Hitachi Japon 15

33 Programmation logique et contraintes dans les bases de données

AR : Jointure naturelle

●
La jointure naturelle, notée simplement ⋈ (sans condition
attachée) est une équi-jointure entre deux relations qui
concerne des égalités sur toutes les colonnes de même nom
●
Elle a du sens uniquement dans la perspective nommée
●
Dans le résultat, on garde « un seul exemplaire » de chaque
colonne « doublon »
●
Pas besoin donc de renommage
●
Si R a l’ensemble de colonnes A et S a l’ensemble de colonnes B,
et si on note A⋂B = C, alors la jointure naturelle correspond à :
R ⋈ S = Π A U B (R ⋈ R.C=S.C S)

34 Programmation logique et contraintes dans les bases de données

AR : Jointure naturelle
Etudiants Inscriptions
NumEtu Nom NomCours NumEtu
IK20 Toto BDDAvancées IK20
JP13 Titi ProgAvancée IK20
AX11 Tata BDDAvancées AX11
BT01 Tutu Tricot BT01
BDDAvancées BT01

Etudiants ⋈ Inscriptions

NumEtu Nom NomCours

IK20 Toto BDDAvancées
IK20 Toto ProgAvancée
AX11 Tata BDDAvancées
BT01 Tutu Tricot
BT01 Tutu BDDAvancées

35 Programmation logique et contraintes dans les bases de données

AR : Semi-jointure

●
Une semi-jointure, notée ⋉C , retourne tous les tuples
de la première relation qui ont « au moins un
correspondant » (au sens du respect de la condition c)
dans la deuxième relation
●
Souvent, on appelle la semi-jointure ci-dessus une
semi-jointure gauche et on introduit une semi-jointure
droite, notée ⋊C , qui concerne la deuxième relation.
●
Il existe également le concept de semi-jointure
naturelle (gauche ou droite)

36 Programmation logique et contraintes dans les bases de données

AR : Semi-jointure
Etudiants Inscriptions
NumEtu Nom NomCours NumEtu
IK20 Toto BDDAvancées IK20
JP13 Titi ProgAvancée IK20
AX11 Tata BDDAvancées AX11
BT01 Tutu Tricot BT01
BDDAvancées BT01

Etudiants ⋉ Inscriptions

NumEtu Nom
IK20 Toto
AX11 Tata
BT01 Tutu

37 Programmation logique et contraintes dans les bases de données

AR : Intersection

●
Opérateur ensembliste « classique », comme l’union et la
différence ; même contrainte de compatibilité de schémas
EffectifsModélisation EffectifsBDDAvancées

NumEtu Nom NumEtu Nom

IK20 Toto IK20 Toto
JP13 Titi JP13 Titi
AX11 Tata BT01 Tutu
EffectifsModélisation ∩ EffectifsBDDAvancées

NumEtu Nom
IK20 Toto
JP13 Titi

38 Programmation logique et contraintes dans les bases de données

AR : Division

●
Supposons deux relations R(X,Y) et S(Y), où X et Y sont
des ensembles d’attributs
●
Notez que pour pouvoir appliquer la division, l’ensemble des colonnes de S
doit être inclus dans l’ensemble des colonnes de R !

Soit la table T = ΠXR, donc de schéma T(X)

●
Le résultat de la division R ÷ S est l’ensemble des tuples
de T qui « apparaissent dans R avec tous les tuples de S »
●
Un tuple de T appartient donc au résultat de la division ssi toutes ses
« combinaisons avec des tuples dans S » donnent des tuples qui font
partie de R !

39 Programmation logique et contraintes dans les bases de données

AR : Division

R S T
A B B B
Toto 1 1 1
Toto 2 2 2
Titi 1 3
Titi 2 La valeur ‘Toto’
Titi 3 combinée à la
valeur 3 de S
R÷S ne donne pas de R÷T
ΠAR tuple de R !

A
A A
Toto
Titi Toto
Titi
Titi

40 Programmation logique et contraintes dans les bases de données

AR : Division

●
La division est un opérateur dérivé ; elle peut donc
s’exprimer avec les opérateurs « de base »
●
Comment ? → TD ! : )
●
Intuitivement, alors que la semi-jointure exprime la
quantification existentielle (« il existe un autre tuple tel
que... »), la division exprime la quantification
universelle (« tous les autres tuples » sont concernés)

41 Programmation logique et contraintes dans les bases de données

AR : composition des opérateurs

●
Comme nous avons déjà pu voir, l’AR permet la
composition des opérateurs
●
le résultat d’un opérateur peut être fourni en entrée à un autre
opérateur
●
Nous pouvons ainsi obtenir des expressions très
complexes, qui peuvent également être représentées
sous forme arborescente

42 Programmation logique et contraintes dans les bases de données

AR : composition des opérateurs

●
Schémas
●
Fournisseur (idF, nomF, villeF) ΠnomF
●
Pièce (idP, nomP, taille, couleur)
Achat (idF, idP, quantité, prix)
σ
●

quantité>100
●
Requête : Noms des fournisseurs
auxquels ont a acheté plus de 100
⨝
unités d’une pièce.
●
RA :
Fournisseur Achat
ΠnomF (σ quantité>100 (Fournisseur ⨝ Achat))

43 Programmation logique et contraintes dans les bases de données

AR : composition des opérateurs

●
Schémas
●
Fournisseur (idF, nomF, villeF)
●
Pièce (idP, nomP, taille, couleur)
●
Achat (idF, idP, quantité, prix)
●
Requête : Noms des fournisseurs de pièces de taille >
10 ou de couleur ‘rouge’.
●
RA :
ΠnomF (Fournisseur ⨝ Achat ⨝ (σ taille>10 (Pièce) U σ couleur=’rouge’ (Pièce)))

44 Programmation logique et contraintes dans les bases de données

Dans ce cours ...

●
...nous parlerons de :
●
« Variantes » du modèle relationnel
●
Algèbre Relationnelle (AR)
●
Opérateurs
●
Règles d’équivalence
●
Contraintes d’intégrité exprimées avec l’AR

45 Programmation logique et contraintes dans les bases de données

AR : communtativité, distributivité, règles
d’équivalence

●
Les opérateurs de l’AR possèdent des propriétés de
commutativité et distributivité (comme c’est le cas
pour d’autres structures algébriques!)
●
L’application de ces règles nous permet d’obtenir, à
partir d’une expression AR, des expressions
équivalentes
●
Quel intérêt ?

46 Programmation logique et contraintes dans les bases de données

AR : communtativité, distributivité, règles
d’équivalence

●
Les opérateurs de l’AR possèdent des propriétés de
commutativité et distributivité (comme c’est le cas
pour d’autres structures algébriques!)
●
L’application de ces règles nous permet d’obtenir, à
partir d’une expression AR, des expressions
équivalentes
●
Quel intérêt ?
●
L’optimisation !!! En pratique, un certain ordre d’application des
opérateurs peut se prouver beaucoup plus efficace qu’un autre !!!

47 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 1

●
Une sélection avec une conjonction de conditions peut
être remplacée par une séquence de sélections
“individuelles” :
σc1∧c2 (R) = σc1(σc2(R))
●
Exemple : Fournisseur (idF, nomF, villeF), Pièce (idP, nomP, taille,
couleur), Achat (idF, idP, quantité, prix)
σtaille>10∧couleur= ‘rouge’ (Pièce) = σtaille>10(σcouleur=’rouge’(Pièce))

48 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 2

●
Les sélections sont commutatives:
σc1(σc2(R))= σc2(σc1(R))
●
Exemple : Fournisseur (idF, nomF, villeF), Pièce (idP, nomP, taille,
couleur), Achat (idF, idP, quantité, prix)
σtaille>10(σcouleur=’rouge’(Pièce)) = σcouleur=’rouge’(σtaille>10(Pièce))

49 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 3

●
Il y a besoin uniquement de la dernière projection
d’une séquence de projections (les autres peuvent être
ignorées) :
●
Πt1(Πt2(...ΠtnR))= Πt1(R)
●
Exemple : Fournisseur (idF, nomF, villeF), Pièce (idP, nomP, taille,
couleur), Achat (idF, idP, quantité, prix)
ΠnomF(ΠnomF,villeF(Fournisseur ⨝ Achat)) = ΠnomF(Fournisseur ⨝ Achat)

50 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 4

●
Les sélections peuvent être combinées avec le produit
cartésien et les théta-jointures :
σc(R x S) = R ⨝ cS

σc1(R ⨝ c2S) = R ⨝ c1∧C2S

●
Exemple : Fournisseur (idF, nomF, villeF), Pièce (idP, nomP, taille,
couleur), Achat (idF, idP, quantité, prix)
σquantité>100(Fournisseur x Achat)) = Fournisseur ⨝quantité>100 Achat

σquantité>100(Fournisseur ⨝prix<20 Achat)) =

Fournisseur ⨝quantité>100 ∧ prix<20Achat

51 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 5

●
Les théta-jointures sont commutatives
R ⨝ cS = S ⨝ cR
●
Exemple : Fournisseur (idF, nomF, villeF), Pièce (idP, nomP, taille,
couleur), Achat (idF, idP, quantité, prix)
Fournisseur ⨝prix<20 Achat = Achat ⨝prix<20 Fournisseur
●
Commentaire : n’oubliez pas que nous avons adopté la
perspective nommée (l’ordre des attributs n’a aucune
importance ! )

52 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 6

●
Les théta-jointures sont associatives de la manière suivante:
●
R ⨝c1∧c2(S ⨝c3 T) = (R ⨝c1 S) ⨝ c2∧c3T , si c1 ne concerne que les attributs de R
et de S !
●
Exemple : R(A,B), S(C,D), T(D,E)
R ⨝A=C ∧ B=D (S ⨝ C=ET) = (R ⨝A=C S) ⨝ C=E ∧ B=DT
●
Intuitivement, lorsqu’on applique cette règle, il faut
« remettre les conditions de jointure au bon endroit ! »
●
Corollaire : les jointures naturelles sont associatives :
R ⨝ (S ⨝ T) = (R ⨝ S) ⨝ T

53 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 7

●
Une sélection portant sur une relation impliquée dans
une théta-jointure peut se distribuer sur la jointure:
●
σc1(R ⨝ c2S) = (σc1R) ⨝c2 S , si c1 ne concerne que les attributs de R
●
Exemple : avec Fournisseur (idF, nomF, villeF), Pièce (idP,
nomP, taille, couleur), Achat (idF, idP, quantité, prix)
σvilleF = ‘Paris’(Fournisseur ⨝ Achat) = (σvilleF = ‘Paris’Fournisseur) ⨝ Achat

54 Programmation logique et contraintes dans les bases de données

 AR : Règle d’équivalence 8

●
Une projection ΠX U Y , ou X et Y sont des attributs de R et de S
respectivement, se distribue sur une jointure R ⨝ c1S comme suit :
●
Soit X’ l’ensemble d’attributs de R impliqués dans c1, et Y’ l’ensemble d’attributs de S
impliqués dans c1
●
Alors
ΠX U Y (R ⨝c1 S) = ΠX U Y(ΠX U X’R ⨝c1 ΠY U Y’S)
●
Exemple : avec Fournisseur (idF, nomF, villeF), Pièce (idP, nomP, taille, couleur),
Achat (idF, idP, quantité, prix)
ΠnomP, quantité (Pièce ⨝ Achat) = ΠnomP, quantité (ΠnomP ,idPPièce ⨝ Πquantité, idP Achat)

55 Programmation logique et contraintes dans les bases de données

AR : Règle d’équivalence 9

●
L’union et l’intersection sont commutatives :
●
RUS=SUR
●
R∩ S=S ∩ R
●
Attention : la différence n’est pas commutative !
●
Exemples ?

56 Programmation logique et contraintes dans les bases de données

AR : Règle d’équivalence 10

●
L’union et l’intersection sont associatives:
●
(R U S) U T = R U (S U T)
●
(R ∩ S) ∩ T= R ∩ (S ∩T)
●
Attention : la différence n’est pas associative !
●
Exemples ?

57 Programmation logique et contraintes dans les bases de données

AR : Règle d’équivalence 11

●
La sélection se distribue sur l’union, l’intersection et la
différence comme suit:
●
σC( R ∩S) = σC( R) ∩ σC (S) = σC( R) ∩S
●
σC( R US) = σC( R) U σC (S)
●
σC (R − S) = σC (R) − σC (S) = σC (R) − S
Attention à l’union, la sélection doit toujours être des deux côtés !
Exemple ?

58 Programmation logique et contraintes dans les bases de données

AR : Règle d’équivalence 12

●
La projection se distribue sur l’union
●
ΠA( R US) = (ΠA( R)) U (ΠA(S))
Cela ne marche pas sur l’intersection et la différence ! Exemple ?

59 Programmation logique et contraintes dans les bases de données

AR : Règles d’équivalence et optimisation

●
Les règles d’équivalence que nous avons vu sont essentielles
pour permettre au SGBD d‘optimiser les requêtes
●
Autrement dit, étant donnée la requête fournie par l’utilisateur, de trouver une
requête équivalente qui s’exécute plus vite !
●
Les règles 7 et 8 nous permettent de « pousser les sélections et
projections au plus près des relations » ; ainsi, moins de tuples
et/ou des tuples avec moins d’attributs participent aux jointures
●
Les règles 5 et 6, concernant la commutativité et l’associativité
des jointures, permettent d’effectuer un (re)ordonnancement
des jointures d’une requête, là encore pour effectuer des
jointures moins coûteuses !

60 Programmation logique et contraintes dans les bases de données

Dans ce cours ...

●
...nous parlerons de :
●
« Variantes » du modèle relationnel
●
Algèbre Relationnelle (AR)
●
Opérateurs
●
Règles d’équivalence
●
Contraintes d’intégrité exprimées avec l’AR

61 Programmation logique et contraintes dans les bases de données

L’AR pour exprimer les contraintes
d’intégrité

●
On peut utiliser l’AR pour exprimer des contraintes
d’intégrité sur une BDD (celles que nous avons déjà
vues, et d’autres encore ; ) )
●
Deux manières possibles (chacune plus ou moins
« lisible » suivant le type de contraintes)
●
E = Ø avec E une expression AR ; cela veut dire « il n’y a pas de tuples
dans le résultat de R »
●
E1 ⊆ E2 avec E1 et E2 des expressions AR ; cela veut dire que les
tuples de E1 sont un sous-ensemble des tuples de E2

62 Programmation logique et contraintes dans les bases de données

L’AR pour exprimer les contraintes
d’intégrité

●
Contraintes d’inclusion / intégrité référentielle (la
partie inclusion des clé étrangères)
●
Pour A l’ensemble d’attributs de R dont les valeurs doivent être un
sous-ensemble des valeurs de B dans S :
ΠAR ⊆ ΠBS ou ΠAR – ΠBS = Ø
●
Exemple : Etudiants (NuméroEtudiant,Nom,Prénom), Cours
(IdCours,NomCours), Inscriptions (NuméroEtudiant, IdCours)
ΠNuméroEtudiantInscriptions ⊆ ΠNuméroEtudiantEtudiants

63 Programmation logique et contraintes dans les bases de données

L’AR pour exprimer les contraintes
d’intégrité

●
Clés et dépendances fonctionnelles
●
Pour une dépendance fonctionnelle X→ Y de la relation R, avec X={X1,
X2, …, Xn} et Y={Y1, Y2, … , Yn}
σ(R1.X1 = R2.X1 ∧ … ∧[Link]=[Link]) ∧(R1.Y1 <> R2.Y1 ∨ … [Link] <>[Link]) (ρR1R x ρR2 R) = Ø
●
Autrement dit, il n’existe pas deux tuples avec les mêmes valeurs
sur X et des valeurs différentes sur Y !
●
Exemple : Etu (NumEtu,Nom,Prénom)
σ([Link] = [Link] ∧([Link] <> [Link] ∨[Link] <>[Link]) (ρE1Etu x ρE2 Etu) = Ø

64 Programmation logique et contraintes dans les bases de données