Un support de cours magistraux de Bases de données

Introduction

L'algèbre relationnelle est un support mathématique cohérent sur lequel repose la modèle relationnel. L'objet de ce chapitre est d'aborder l'algèbre relationnelle dans le but de décrire quelles sont les opérations qu'il est possible d'appliquer sur des relations. L'approche suivie est donc plus opérationnelle que mathématique.

Les notations ne sont pas standardisées en algèbre relationnelle. Ce cours utilise des notations courantes mais donc pas forcément universelles.

Rappels : Au sein d'une relation, par définition, toutes les occurrences sont distinctes (cf. chapitre 3 Modèle relationnel : concepts). L'ordre des occurrences et des attributs n'est pas significatif.

Sélection

• Opération unaire essentielle
• Signature : relation R × expression logique E → relation
• Rôle : La sélection génère une relation regroupant exclusivement toutes les occurrences de la relation R qui satisfont l'expression logique E.
• En d'autres termes, la sélection permet de choisir des lignes dans le tableau.
• Le résultat de la sélection est une nouvelle relation qui a les mêmes attributs que R.
• Si R est vide (c'est-à-dire ne contient aucune occurrence), la relation qui résulte de la sélection est vide.
• Notation : σER (σ est la lettre grecque sigma.)

Exemple de sélection

Exercices de sélection

1. Considérez la relation Personne donnée ci-dessus et calculez les expressions suivantes. Rappel d'algèbre booléenne : « ∧ » signifie « et », « ∨ » signifie « ou » et « ¬ » signifie « non ».

   1. σnuméro≤13Personne
   2. σnom="Germain"Personne
   3. σprénom="Paul"Personne
   4. σ(numéro<6)∧(prénom≠"Stan")Personne
   5. σ(numéro=12)∨(nom="Germain")Personne
   6. σ¬(numéro<4)Personne
   7. σnuméro<12σnuméro>2Personne
   8. σnom="Germain"σ(prénom="Stan")∨(prénom="Rose-Marie")Personne
   9. σ((prénom≠"Paul")∨(numéro≤6))∧(nom="Germain")Personne
   10. σ((prénom≠"Paul")∧(numéro≤6))∨(nom="Germain")Personne
   11. σ¬((numéro=12)∨(nom="Germain"))Personne
   12. σ¬((numéro<4)∧(nom="Germain"))∧(prénom="Caroline")Personne

2. Soit la relation Employé(numSécu, nom, prénom, salaire). Donnez une expression algébrique quand on souhaite trouver :

   1. tous les employés.
   2. tous les employés qui ont un salaire dépassant 1000 euros.
   3. l'employé dont le numéro de sécurité sociale est 1 63 03 06 081 028 11.
   4. tous les employés qui ont un salaire ne dépassant pas 1000 euros mais qui ont pour nom Durand.
   5. tous les employés qui gagnent entre 1000 et 1500 euros mais aussi ceux qui gagnent exactement 2000 euros et qui ne s'appellent pas Durand.
   6. tous les employés sauf Paul Durand.

Projection

• Opération unaire essentielle
• Signature : relation R × liste d'attributs A → relation
• Rôle : La projection génère une relation regroupant exclusivement toutes les occurrences de la relation R réduites aux attributs de la liste d'attributs A.
• En d'autres termes, la projection permet de choisir des colonnes dans le tableau.
• Le résultat de la projection est une nouvelle relation dont les attributs sont ceux présents dans A.
• Si R est vide, la relation qui résulte de la projection est vide.
• Notation : πAR (π est la lettre grecque pi.)

Exemple de projection

Exercices de projection

1. Considérez la relation Personne donnée ci-dessus et calculez les expressions suivantes.

   1. πnuméro,prénomPersonne
   2. πnomPersonne
   3. πnom,prénomPersonne
   4. πnuméro,nom,prénomPersonne
   5. πnom,prénomσnuméro<4Personne
   6. σ(numéro=12)∨(nom="Germain")πnuméro,nomPersonne
   7. πnomσ(numéro=12)∨(nom="Germain")πnuméro,nomPersonne

2. Soit la relation Ami(nom, prénom, adresse, âge). Donnez une expression algébrique quand on souhaite trouver :

   1. tous les nom et prénom de ses amis.
   2. tous les nom, adresse et âge de ses amis qui ont moins de 25 ans.
   3. l'adresse de son ami Paul Durand.
   4. tous les nom et âge de ses amies prénommées Sophie.
   5. tous les nom, prénom, adresse et âge de ses amis qui ne se prénomment pas Stan et qui ont plus de 55 ans.

Complément

• Opération unaire
• Signature : relation R → relation
• Rôle : Le complément génère une relation regroupant exclusivement toutes les occurrences possibles créées à partir des valeurs d'attributs présentes dans la relation R, à l'exception des occurrences de R.
• En d'autres termes, le complément permet de générer toutes les occurrences qui n'existent pas dans R. Cependant, comme l'ensemble des valeurs possibles pour chaque attribut est généralement inconnu ou infini, seules les valeurs déjà présentes dans un attribut de R sont utilisées, dans cet attribut, pour créer de nouvelles occurrences.
• Le résultat du complément est une nouvelle relation qui a les mêmes attributs que R.
• Si R est vide, la relation qui résulte du complément est vide.
• Notation : -R
• Une propriété remarquable (non exhaustif) :
  • --R est identique à R.

Exemple de complément

Exercices de complément

Considérez la relation Personne donnée ci-dessous et calculez les expressions suivantes.

1. -πnuméro,prénomPersonne
2. -πnomPersonne
3. -σ(numéro<6)∧(prénom="Stan")Personne
4. -πnuméro,prénom-σnuméro<6Personne
5. -σ¬((numéro=12)∨(nom="Germain"))Personne
6. -σ(numéro=12)∨(nom="Germain")πnuméro,prénomPersonne

Union

• Opération binaire ensembliste commutative
• Signature : relation R1 × relation R2 → relation
• Rôle : L'union génère une relation regroupant exclusivement toutes les occurrences de la relation R1 et toutes les occurrences de la relation R2.
• Si une même occurrence existe dans R1 et dans R2, elle n'apparaît qu'une seule fois dans le résultat de l'union.
• Contrainte : R1 et R2 doivent avoir les mêmes attributs.
• Le résultat de l'union est une nouvelle relation qui a les mêmes attributs que R1 et R2.
• Si R1 et R2 sont vides, la relation qui résulte de l'union est vide. Si R1 (respectivement R2) est vide, la relation qui résulte de l'union est identique à R2 (respectivement R1).
• Notation : R1 ∪ R2
• Quelques propriétés remarquables (non exhaustif) :
  • R ∪ R est identique à R.
  • R ∪ -R est la relation regroupant exclusivement toutes les occurrences possibles créées à partir des valeurs d'attributs présentes dans la relation R.

Exemple d'union

Exercices d'union

Considérez les relations Personne1 et Personne2 données ci-dessus et calculez les expressions suivantes.

1. πprénomPersonne1 ∪ πprénomPersonne2
2. πprénomPersonne2 ∪ πprénomPersonne1
3. Personne2 ∪ -Personne2
4. Personne2 ∪ Personne2
5. Personne1 ∪ -Personne2

Intersection

• Opération binaire ensembliste commutative
• Signature : relation R1 × relation R2 → relation
• Rôle : L'intersection génère une relation regroupant exclusivement toutes les occurrences qui existent à la fois dans la relation R1 et dans la relation R2.
• Contrainte : R1 et R2 doivent avoir les mêmes attributs.
• Le résultat de l'intersection est une nouvelle relation qui a les mêmes attributs que R1 et R2.
• Si R1 ou R2 ou les deux sont vides, la relation qui résulte de l'intersection est vide.
• Notation : R1 ∩ R2
• Quelques propriétés remarquables (non exhaustif) :
  • R ∩ R est identique à R.
  • R ∩ -R est vide.
  • R1 ∩ (R1 ∪ R2) est identique à R1.
  • R1 ∪ (R1 ∩ R2) est identique à R1.

Exemple d'intersection

Exercices d'intersection

Considérez les relations Personne1 et Personne2 données ci-dessus et calculez les expressions suivantes.

1. πprénomPersonne1 ∩ πprénomPersonne2
2. Personne2 ∩ -Personne2
3. Personne2 ∩ Personne2
4. Personne2 ∪ (Personne1 ∩ Personne2)
5. Personne2 ∩ (Personne1 ∪ Personne2)
6. Personne1 ∩ -Personne2

Différence

• Opération binaire ensembliste non commutative
• Signature : relation R1 × relation R2 → relation
• Rôle : La différence génère une relation regroupant exclusivement toutes les occurrences de la relation R1 qui n'existent pas dans la relation R2.
• Contrainte : R1 et R2 doivent avoir les mêmes attributs.
• Le résultat de la différence est une nouvelle relation qui a les mêmes attributs que R1 et R2.
• Si R1 est vide, la relation qui résulte de la différence est vide. Si R2 est vide, la relation qui résulte de la différence est identique à R1.
• Notation : R1 - R2
• Quelques propriétés remarquables (non exhaustif) :
  • R - R est vide.
  • R - -R est identique à R.

Exemple de différence

Exercices de différence

Considérez les relations Personne1 et Personne2 données ci-dessus et calculez les expressions suivantes.

1. πprénomPersonne2 - πprénomPersonne1
2. πprénomPersonne1 - πprénomPersonne2
3. Personne2 - -Personne2
4. -Personne2 - Personne2
5. Personne2 - Personne2
6. Personne2 - Personne1
7. -Personne1 - -Personne2
8. -Personne2 - -πprénomPersonne1

Division

• Opération binaire non commutative
• Signature : relation R1 × relation R2 → relation
• Rôle : La division génère une relation regroupant exclusivement toutes les parties d'occurrence de la relation R1 qui sont associées à toutes les occurrences de la relation R2.
• Contraintes : R2 ne peut pas être vide. Tous les attributs de R2 doivent être présents dans R1. R1 doit posséder au moins un attribut de plus que R2.
• Le résultat de la division est une nouvelle relation qui a tous les attributs de R1 sans aucun de ceux de R2.
• Si R1 est vide, la relation qui résulte de la division est vide.
• Notation : R1 ÷ R2

Exemple de division

Exercices de division

Considérez les relations Enseignement et Étudiant données ci-dessus et calculez les expressions suivantes.

1. -Enseignement ÷ Étudiant
2. Enseignement ÷ σnomÉtudiant="Dubois"Étudiant
3. (Enseignement ∪ -Enseignement) ÷ Étudiant
4. (Enseignement - σnomÉtudiant="Durand"Enseignement) ÷ Étudiant

Produit cartésien

• Opération binaire commutative
• Signature : relation R1 × relation R2 → relation
• Rôle : Le produit cartésien génère une relation regroupant exclusivement toutes les possibilités de combinaison des occurrences des relations R1 et R2.
• Contrainte : R1 et R2 ne doivent avoir aucun attribut commun.
• Le résultat du produit cartésien est une nouvelle relation qui a tous les attributs de R1 et tous ceux de R2.
• Si R1 ou R2 ou les deux sont vides, la relation qui résulte du produit cartésien est vide.
• Le nombre d'occurrences de la relation qui résulte du produit cartésien est le nombre d'occurrences de R1 multiplié par le nombre d'occurrences de R2.
• Notation : R1 × R2

Exemple de produit cartésien

Exercices de produit cartésien

Considérez les relations BonneAmie et Cadeau données ci-dessus et calculez les expressions suivantes.

1. -BonneAmie × -Cadeau
2. Cadeau × BonneAmie
3. (BonneAmie ∪ -BonneAmie) × Cadeau
4. Cadeau × πprixCadeau

Thêta-produit

• Opération binaire commutative
• Signature : relation R1 × relation R2 × expression logique E → relation
• Rôle : Le thêta-produit génère une relation regroupant exclusivement toutes les possibilités de combinaison des occurrences des relations R1 et R2 qui satisfont l'expression logique E.
• Contrainte : R1 et R2 ne doivent avoir aucun attribut commun. E doit être une comparaison (=, ≠, <, >, ≤ ou ≥) entre un attribut de R1 et un attribut de R2.
• Le résultat du thêta-produit est une nouvelle relation qui a tous les attributs de R1 et tous ceux de R2.
• Si R1 ou R2 ou les deux sont vides, la relation qui résulte du thêta-produit est vide.
• Notation : R1 θE R2 (θ est la lettre grecque thêta.)
• Une propriété remarquable (non exhaustif) :
  • R1 θE R2 est identique à σE(R1 × R2).

Exemple de thêta-produit

Exercices de thêta-produit

Considérez les relations BonneAmie et CadeauDéjàFait données ci-dessous et calculez les expressions suivantes.

1. BonneAmie θnom=nomAmie CadeauDéjàFait
2. σnom=nomAmie(BonneAmie × CadeauDéjàFait)
3. (BonneAmie ∪ -BonneAmie) θnom=nomAmie CadeauDéjàFait
4. BonneAmie θnom≠nomAmie πnomAmie,prixCadeauDéjàFait

Jointure

• Opération binaire commutative essentielle, également appelée jointure naturelle
• Signature : relation R1 × relation R2 × attribut A → relation ou relation R1 × relation R2 × attribut A1 × attribut A2 → relation
• Rôle : La jointure génère une relation regroupant exclusivement toutes les possibilités de combinaison des occurrences des relations R1 et R2 pour lesquelles il y a égalité entre l'attribut A (ou A1) de la relation R1 et l'attribut A (ou A2) de la relation R2. L'attribut A (ou A2) de la relation R2 est ensuite éliminé.
• Contrainte : R1 et R2 ne peuvent pas avoir plus d'un attribut commun. Si elles en ont un, ce ne peut être que celui sur lequel est réalisée la jointure (A).
• Le résultat de la jointure est une nouvelle relation qui a tous les attributs de R1 et tous ceux de R2 sauf A (ou A2).
• Il est en fait indifférent d'éliminer l'attribut A (ou A1) de la relation R1 ou l'attribut A (ou A2) de la relation R2.
• Si R1 ou R2 ou les deux sont vides, la relation qui résulte de la jointure est vide.
• Notation : R1 ⟩⟨A R2 si A est l'attribut commun ou R1 ⟩⟨A1,A2 R2
• Une propriété remarquable (non exhaustif) :
  • R1 ⟩⟨A1,A2 R2 est identique à R1 θA1=A2 R2 suivi du retrait de A2 par projection.

Exemple de jointure

Exercices de jointure

Considérez les relations BonneAmie et CadeauDéjàFait données ci-dessous et calculez les expressions suivantes.

1. BonneAmie ⟩⟨nom CadeauDéjàFait
2. πprénom,article(BonneAmie ⟩⟨nom CadeauDéjàFait)
3. CadeauDéjàFait ⟩⟨nom CadeauDéjàFait
4. (BonneAmie ∪ -BonneAmie) ⟩⟨nom CadeauDéjàFait
5. (πprénomBonneAmie) ⟩⟨prénom,nom CadeauDéjàFait

Jointure extérieure

• Opération binaire commutative
• Signature : relation R1 × relation R2 × attribut A → relation ou relation R1 × relation R2 × attribut A1 × attribut A2 → relation
• Rôle : La jointure extérieure génère une relation regroupant exclusivement toutes les possibilités de combinaison des occurrences des relations R1 et R2 pour lesquelles il y a égalité entre l'attribut A (ou A1) de la relation R1 et l'attribut A (ou A2) de la relation R2. Les occurrences qui ne peuvent pas être associées sont également ajoutées et complétées par le vide (noté ⊥). L'attribut A (ou A2) de la relation R2 est ensuite éliminé.
• Contrainte : R1 et R2 ne peuvent pas avoir plus d'un attribut commun. Si elles en ont un, ce ne peut être que celui sur lequel est réalisée la jointure extérieure (A).
• Le résultat de la jointure extérieure est une nouvelle relation qui a tous les attributs de R1 et tous ceux de R2 sauf A (ou A2).
• Il est en fait indifférent d'éliminer l'attribut A (ou A1) de la relation R1 ou l'attribut A (ou A2) de la relation R2.
• Si R1 et R2 sont vides, la relation qui résulte de la jointure extérieure est vide.
• Notation : R1 ⟨⟩A R2 si A est l'attribut commun ou R1 ⟨⟩A1,A2 R2

Exemple de jointure extérieure

Exercices de jointure extérieure

Considérez les relations AmieFidèle et CadeauTropCher données ci-dessous et calculez les expressions suivantes.

1. AmieFidèle ⟨⟩nom CadeauTropCher
2. πprénom,article(AmieFidèle ⟨⟩nom CadeauTropCher)
3. CadeauTropCher ⟨⟩nom CadeauTropCher
4. (AmieFidèle ∪ -AmieFidèle) ⟨⟩nom CadeauTropCher
5. (AmieFidèle ⟨⟩nom CadeauTropCher) ∩ (AmieFidèle ⟩⟨nom CadeauTropCher)

Semi-jointure

• Opération binaire non commutative qui peut être gauche ou droite
• Signature : relation R1 × relation R2 × attribut A → relation ou relation R1 × relation R2 × attribut A1 × attribut A2 → relation
• Rôle : La semi-jointure génère une relation regroupant exclusivement toutes les possibilités de combinaison des occurrences des relations R1 et R2 pour lesquelles il y a égalité entre l'attribut A (ou A1) de la relation R1 et l'attribut A (ou A2) de la relation R2. Pour une semi-jointure gauche (respectivement droite), les occurrences de la relation R1 (respectivement R2) qui ne peuvent pas être associées sont également ajoutées et complétées par le vide (noté ⊥). L'attribut A (ou A2) de la relation R2 est ensuite éliminé.
• Contrainte : R1 et R2 ne peuvent pas avoir plus d'un attribut commun. Si elles en ont un, ce ne peut être que celui sur lequel est réalisée la semi-jointure (A).
• Le résultat de la semi-jointure est une nouvelle relation qui a tous les attributs de R1 et tous ceux de R2 sauf A (ou A2).
• Il est en fait indifférent d'éliminer l'attribut A (ou A1) de la relation R1 ou l'attribut A (ou A2) de la relation R2.
• Si R1 et R2 sont vides, la relation qui résulte de la semi-jointure est vide.
• Notation pour la semi-jointure gauche : R1 ⟨A R2 si A est l'attribut commun ou R1 ⟨A1,A2 R2
• Notation pour la semi-jointure droite : R1 ⟩A R2 si A est l'attribut commun ou R1 ⟩A1,A2 R2

Exemple de semi-jointure

Exercices de semi-jointure

Considérez les relations AmieFidèle et CadeauTropCher données ci-dessous et calculez les expressions suivantes.

1. AmieFidèle ⟩nom CadeauTropCher
2. (AmieFidèle ⟩nom CadeauTropCher) ∩ (AmieFidèle ⟨nom CadeauTropCher)
3. (AmieFidèle ⟨nom CadeauTropCher) ∪ (AmieFidèle ⟩nom CadeauTropCher)
4. CadeauTropCher ⟨nom CadeauTropCher