Année 2016-17

Responsable : Nicolas Lumineau

U.E. BDW1
Bases de Données et programmation WEB

Partie "Algèbre relationnelle"

Fascicule sur l’Algèbre Relationnelle

Rappels : Pourquoi ? Comment ? Page 2
Exercices applicatifs Page 8
Corrigés des exercices applicatifs Page 9
Fascicule : Algèbre relationnelle
Dans ce fascicule, vous trouverez les rappels sur la syntaxe de l’algèbre relationnelle, ainsi que des exercices
corrigés.

Pourquoi ? Comment ?

Pourquoi s’intéresser à l’Algèbre Relationnelle ?

L’Algèbre Relationnelle est le langage qui permet d’exprimer la façon dont une requête va s’exé-
cuter pour obtenir le résultat. Jusqu’à présent vous avez vu le langage SQL qui est un langage déclaratif
qui permet de caractériser le résultat attendu sans pour autant dire comment l’obtenir. L’Algèbre Rela-
tionnelle est un langage procédural qui permet de décrire l’enchainement des opérateurs qui permettront
d’obtenir un résultat.

Pourquoi les SGBD utilise l’Algèbre Relationnelle ?

L’Algèbre Relationnelle est principalement utilisé pour faire de l’optimisation de requête. En effet, pour
une requête SQL, il existe plusieurs requêtes algébriques équivalentes (i.e. plusieurs requêtes en algèbre
relationnelle qui retournent les mêmes tuples en résultat). Ces requêtes algébriques sont alors appelés plans
d’exécution. Autant les tuples retournés sont les mêmes pour tous ces plans d’exécution, autant le temps
nécessaire pour obtenir ces tuples, lui peut être très différent. Tout dépend de la façon dont les opérations
qui composent le plan d’exécution sont organisés.

Comment exprimer une requête en Algèbre Relationnelle ?

Vous trouverez ci-dessous les différents opérateurs de l’Algèbre Relationnelle . Pour illustrer les diffé-
rents opérateurs nous considèrons les schémas de relations suivants R(A,B,C,#D), S(G,H,I,J), U(D, E, F),
V(K,L,M) et W(M) où les clés primaires sont soulignées et la clé étrangère est préfixée par un #.

R S U V W
A B C D E F G H D I J K L M M
1 2 3 4 1 2 3 4 2 3 4 1 2 1 1
2 3 1 4 2 4 1 3 3 1 2 1 2 2 2
3 4 1 2 3 4 1 2 4 2 3 2 1 1 3
4 3 1 2 4 2 1 3 2 1 2
2 1 3
3 2 1

BDW1 - Nicolas Lumineau 2 Partie "Algèbre Relationnelle"

 On distingue les opérateurs de base :
— l’union R ∪ S
— la différence R − S
— le produit cartésien R × S
— la projection ΠA,B (R)
— la sélection σF (R)
— le renommage ρA/A0 ,B/B 0 (R)
et les opérateurs considérés comme des racoucis syntaxiques :
— l’intersection R ∩ S qui peut s’exprimer comme R − (R − S)
— la θ-jointure R BCF S qui peut s’exprimer comme σF (R × S)
— la semi-jointure R B<F S qui peut s’exprimer comme ΠA,B,C,D ( σF (R × S))
— la division V ÷ W qui peut s’exprimer comme ΠK,L (V) - ΠK,L (( ΠK,L (V) × W) - V)

Instance du résultat :
L’UNION : R ∪ S T
A B C D
Condition: R et S doivent être compatibles à l’union 1 2 3 4
(même nombre d’attributs, même type d’attributs). 2 3 1 4
3 4 1 2
Ce qui est retourné: l’ensemble des tuples qui appa- 4 3 1 2
tiennent à R ou qui appartiennent à S. 1 2 3 4
2 4 1 3
Schéma du résultat : T(A,B,C,D) 3 4 1 2
4 2 1 3

La DIFFERENCE : R − S

Condition: R et S doivent être compatibles à l’union Instance du résultat :

(même nombre d’attributs, même type d’attributs). T
A B C D
Ce qui est retourné: l’ensemble des tuples qui appa- 2 3 1 4
tiennent à R mais qui n’appartiennent pas à S. 4 3 1 2

Schéma du résultat : T(A,B,C,D)

La PROJECTION : ΠlisteAttributs (R)

Condition: Les attributs en paramètre de la projection Instance du résultat :

(i.e. listeAttributs) sont bien des attributs présents Si on considère ΠB,C (R) :
dans la relation interrogée (i.e. R). (i.e. listeAttributs : {B,C} )
alors on aura :
Ce qui est retourné: l’ensemble des tuples composés Schéma du résultat : T(B,C)
uniquement des attributs présents en paramètre de T
la projection. Les doublons des tuples sont automati- B C
quement supprimés. 2 3
3 1
Schéma du résultat : T(listeAttributs) 4 1

BDW1 - Nicolas Lumineau 3 Partie "Algèbre Relationnelle"

La SELECTION : σF (R)

Condition: Les attributs intervenant dans la formule Instance du résultat :

logique F sont bien des attributs présents dans la Si on considère :
relation interrogée (R). F=A>2,
alors on aura :
Ce qui est retourné: l’ensemble des tuples de R qui T
rendent vraie la formule logique F. A B C D
3 4 1 2
Schéma du résultat : T(A,B,C,D) 4 3 1 2

Si on considère : Si on considère : Si on considère :

F = B > 3 ∨ C = 3, F = B > 3 ∧ D < 4, F = B > 3 ∧ D != 2,
alors on aura : alors on aura : alors on aura :
T T T
A B C D A B C D A B C D
1 2 3 4 3 4 1 2
3 4 1 2 Le résultat est vide,
mais cela reste une re-
lation.

Le RENOMMAGE : ρmappings (R)

Condition: Les attributs intervenant dans les map- Instance du résultat :

pings sont bien des attributs présents dans la relation Si on considère ρA/A0 ,B/B 0 (R) :
interrogée (R). (i.e. mappings : A/A’,B/B’ )
alors on aura :
Ce qui est retourné: l’ensemble des tuples de R Schéma du résultat :
avec un schéma correspondant aux transformations T(A’,B’,C,D)
définies dans les mappings. T
A’ B’ C D
1 2 3 4
2 3 1 4
3 4 1 2
4 3 1 2

BDW1 - Nicolas Lumineau 4 Partie "Algèbre Relationnelle"

Le PRODUIT CARTESIEN : U × W

Condition: U et W doivent avoir des noms d’attributs Instance du résultat :

différents (si ce n’est pas le cas, un renommage pourra T
être effectué au préalable). D I J M
2 3 4 1
Ce qui est retourné: l’ensemble des tuples composé 2 3 4 2
des attributs réunis des relations U et W et où chaque 2 3 4 3
tuple de U a été associé à chaque tuple de W. 3 1 2 1
3 1 2 2
Schéma du résultat : T(D,I,J,M) 3 1 2 3
4 2 3 1
4 2 3 2
4 2 3 3

L’INTERSECTION : R ∩ S

Condition: R et S doivent être compatibles à l’union Instance du résultat :

(même nombre d’attributs, même type d’attributs). T
A B C D
Ce qui est retourné: l’ensemble des tuples qui appa- 1 2 3 4
tiennent à R et qui appartiennent également à S. 3 4 1 2

Schéma du résultat : T(A,B,C,D)

BDW1 - Nicolas Lumineau 5 Partie "Algèbre Relationnelle"

La θ-JOINTURE : R BCF S

Condition: La formule logique F en paramètre de Instance du résultat :

la jointure ne doit contenir que des comparaisons Si on considère :
(i.e. =, !=, <, >, ≤, ≥) entre des attrituts de R et de S. F:A=E,
alors on aura :
Ce qui est retourné: l’ensemble des tuples composés T
des attributs réunis de R et de S et pour lesquels A B C D F G H
l’association des tuples de R et de S rendent vraie la 1 2 3 4 2 3 4
formule logique F. 2 3 1 4 4 1 3
3 4 1 2 4 1 2
Schéma du résultat : T(A,B,C,D,F,G,H) 4 3 1 2 2 1 3
car dans le cas d’équi-jointure, on ne répète pas l’at-
tribut.

Si on considère : Si on considère :
F : C > F, F : C > F ∧ D != H,
alors on aura : alors on aura :
T T
A B C D E F G H A B C D E F G H
1 2 3 4 1 2 3 4 1 2 3 4 4 2 1 3
1 2 3 4 4 2 1 3

Remarque : On parle d’équi-jointure quand la formule F, ne contient que des égalités.

La SEMI-JOINTURE : R B<F S

Condition: La formule logique F en paramètre de Instance du résultat :

la jointure ne doit contenir que des comparaisons Si on considère :
(i.e. =, !=, <, >, ≤, ≥) entre des attrituts de R et de S. F:A=E,
alors on aura :
Ce qui est retourné: l’ensemble des tuples composés T
uniquement des attributs de R et pour lesquels A B C D
l’association des tuples de R et de S rendent vraie la 1 2 3 4
formule logique F. 2 3 1 4
3 4 1 2
Schéma du résultat : T(A,B,C,D) 4 3 1 2

Si on considère : Si on considère :
F : C > F, F : C > F ∧ D != H,
alors on aura : alors on aura :
T T
A B C D A B C D
1 2 3 4 1 2 3 4

BDW1 - Nicolas Lumineau 6 Partie "Algèbre Relationnelle"

La DIVISION : V ÷ W

Condition: Le schéma de V est une sur-ensemble Instance du résultat :

du schéma de W (i.e. tous les attributs de W sont T
également des attributs de V). Ici, on a bien M qui K L
est l’unique attribut de W et qui appartient bien au 2 1
schéma de V. On remarque que T × W ⊆ U.
On remarque également que si
Ce qui est retourné: l’ensemble des tuples composés on avait considéré le tuple (1,2)
des attributs de V qui ne sont pas dans le schéma dans le résultat, le produit car-
de W et dont le produit cartésien avec W est un tésien nous aurait fait apparaitre
sous-ensemble de tuples de V (i.e. ce produit cartésien le tuple (1,2,3) qui n’est pas dans
ne génèrerait pas de tuples qui ne sont pas dans V). V. De même, si on avait consi-
déré le tuple (3,2) dans le ré-
Schéma du résultat : T(K,L) sultat, le produit cartésien nous
aurait fait apparaitre les tuples
(3,2,2) et (3,2,3) qui ne sont pas
dans V.

Comment représenter une requête en Algèbre Relationnelle ?

Une requête en Algèbre Relationnelle peut se représenter de deux manières différentes :

— Sous forme d’expression algébrique : ΠA,B (R BCA=E σF >1 (S))

— Sous forme d’arbre algébrique :
ΠA,B

BCA=E

R σF >1

BDW1 - Nicolas Lumineau 7 Partie "Algèbre Relationnelle"

Exercices applicatifs

Exercice 1 : Quelques requêtes algébriques

Soient les schémas de la relation JOUEUR et PALMARES suivant :
JOUEUR(Nom, Prenom, AnNaiss, Nation, Taille, Poids)
PALMARES(Nom, Annee, Titre)

On suppose que : AnNaiss représente l’année de naissance d’un joueur, qu’il n’y a pas d’homonymes
dans la base de données, que la taille est exprimée en centimètre et que le poids est exprimé en kilogramme.

Ecrire en algèbre relationnelle, quand cela est possible, les requêtes suivantes :
1. Donner les joueurs nés avant 1987 (inclus) et faisant plus de 78kg (strict).
2. Donner les nationalités présentes dans la table.
3. Donner le nom des joueurs de plus 1m80. Le résultat aura pour nom "NomDesGrands".
4. Donner le nom et le prénom des joueurs ayant eu un palmarès en 2014.
5. Donner le nom des joueurs sans palmarès.
6. Donner le nom des joueurs titré en 2010 et 2014.
7. Donner le nom des joueurs titré tous les ans (i.e. pour toutes les années stockées dans la base)
8. Donner le nom du/des joueurs le(s) plus jeune(s) stocké(s) dans la base.
9. Donner le nombre de titre obtenu par le joueur le plus titré.

Exercice 2 : Trouvez les erreurs

On considère les relations JOUEUR et PALMARES de l’exercice précédent. Expliquer pourquoi les re-
quêtes suivantes ne sont pas correctes ou ne correspondent pas à ce qui est attendu. Pour chaque requête
algébrique, proposer une correction afin que l’énoncé proposé soit en adéquation avec la requête.

1. ΠN om,T itre (JOU EU R) :

retourne les titres obtenus pour chaque joueur.

2. ΠN om (JOU EU R ∪ P ALM ARES) :

retourne l’ensemble des noms de joueurs apparaissant dans JOUEUR et ceux apparaissant dans
PALMARES.

3. σAnN ais>1983 (ΠN om (JOU EU R)) :

retourne le nom des joueurs nés après 1983.

4. ΠN om (σT itre!=0 ChampiondeF rance0 (P ALM ARES)) :

retourne le nom des joueurs n’ayant jamais obtenu le titre de ’Champion de France’.

5. ΠN om,P renom (σN ation=0 F rance0 ∧N ation=0 Argentine0 (JOU EU R)) :

retourne le nom et le prénom des joueurs français et des joueurs argentins.

6. ΠN om (σT itre=0 ChampiondeF rance0 ∧T itre=0 CoupedeF rance0 ∧Annee=0 20140 (P ALM ARES)) :
retourne le nom des joueurs ayant obtenu à la fois le titre de ’Champion de France’ et le titre de
’Coupe de France’ en 2014.

BDW1 - Nicolas Lumineau 8 Partie "Algèbre Relationnelle"

Corrections des exercices applicatifs

Exercice 1 : Quelques requêtes algébriques

1. σAnN aiss<=1987∧P oids>78 (JOU EU R)

2. ΠN ation (JOU EU R)

3. ρN om/N omDesGrands (ΠN om (σT aille>180 (JOU EU R))

4. ΠN om,P renom (JOU EU R BCN om σAnnee=2014 (P ALM ARES))

5. ΠN om (JOU EU R) − ΠN om (P ALM ARES)

6. ΠN om (σAnnee=2010 (P ALM ARES)) ∩ ΠN om (σAnnee=2014 (P ALM ARES))

NB : si cela est proposé par un étudiant, insister sur le fait que l’expression
ΠN om (σAnnee=2010∧Annee=2014 (P ALM ARES)) n’a pas de sens car on ne peut pas avoir deux valeurs
différentes pour un attribut.

7. ΠN om,Annee (P ALM ARES) ÷ ΠAnnee (P ALM ARES)

8. ΠN om,P renom (JOU EU R) − ΠN om,P renom (ρAnN aiss/A1 (JOU EU R) B<A1<A2 ρAnN aiss/A2 (JOU EU R))
car la semi-jointure ne retourne que les joueurs pour lesquels il existe au moins un autre joueur plus
jeune et en faisant la différence, il ne reste plus que les noms et prénoms des joueurs pour lesquels il
n’existe pas d’autre joueurs plus jeune : donc ce sont les plus jeunes !

9. Impossible car pas d’opérateur d’agrégation dans cette version de l’algèbre relationnelle.

Exercice 2 : Trouvez les erreurs !

1. Erreur : Titre n’est pas un attribut de JOUEUR.
ΠN om,T itre (P ALM ARES)

2. Erreur : JOUEUR et PALMARES sont incompatible à l’union.

ΠN om (ΠN om (JOU EU R) ∪ ΠN om (P ALM ARES))

3. Erreur : La projection sur le nom est appliquée avant la sélection qui ne peut pas s’appliquer car
AnNaiss n’existe plus.
ΠN om (σAnN aiss>1983 (JOU EU R))

4. La requête proposée retourne le nom des joueurs ayant obtenu au moins une fois un titre différent de
celui de ’Champion de France’.
ΠN om (JOU EU R) − ΠN om (σT itre=0 Champion de F rance0 (P ALM ARES))

5. La requête proposée ne retourne rien : un attribut ne peut pas avoir deux valeurs différentes en même
temps. Dans le modèle relationnel est les attributs sont mono-valués.
ΠN om,P renom (σN ation=0 F rance0 ∨N ation=0 Argentine0 (JOU EU R))

6. idem, pour les mêmes raisons.

ΠN om (σT itre=0 Champion de F rance0 ∧Annee=0 20140 (P ALM ARES))
∩
ΠN om (σT itre=0 Coupe de F rance0 ∧Annee=0 20140 (P ALM ARES))

BDW1 - Nicolas Lumineau 9 Partie "Algèbre Relationnelle"