Bases de données
Pr. Yahya Benkaouz
[Link]@[Link]
FSR, Université Mohammed V de Rabat
Plan du cours
• Introduction aux bases de données
• Analyse du monde réel : Modèle Entité/Association (ER)
• Concepts fondamentaux : entités, relations, attributs,…
• Étapes de la modélisation ER
• Normalisation de modèles ER
• Approche relationnelle
• Modèle relationnel
• Algèbre relationnelle
• Langage SQL
2
Algèbre relationnelle
• L’algèbre relationnelle est un support mathématique cohérent sur lequel repose
le modèle relationnel.
• L’objectif de cette section est de décrire les opérations qu’il est possible
d’appliquer sur des relations pour produire de nouvelles relations.
• Les notations ne sont pas standardisées en algèbre relationnelle. On va utiliser
des notations courantes mais donc pas forcément universelles.
3
Algèbre relationnelle
• On peut distinguer trois familles d’opérateurs relationnels :
• Les opérateurs unaires (Sélection, Projection) : ce sont les opérateurs les plus
simples, ils permettent de produire une nouvelle table à partir d’une autre
table.
• Les opérateurs binaires ensemblistes (Union, Intersection, Différence) : ces
opérateurs permettent de produire une nouvelle relation à partir de deux
relations de même degré et de même domaine.
• Les opérateurs binaires ou n-aires (Produit cartésien, Jointure, Division) : ils
permettent de produire une nouvelle table à partir de deux ou plusieurs
autres tables. 4
Les opérations unaires
• Sélection:
• La sélection (parfois appelée restriction) génère une relation regroupant
exclusivement toutes les occurrences de la relation R qui satisfont l’expression
logique E.
• On la note 𝝈(𝑬) 𝑹.
• Exemple: Soit la relation personne
𝝈(𝑵𝒖𝒎é𝒓𝒐≥𝟓) 𝑷𝒆𝒓𝒔𝒐𝒏𝒏𝒆
5
Les opérations unaires
• Projection:
• La projection consiste à supprimer les attributs autres que 𝑨𝟏, … , 𝑨𝒏 d’une
relation et à éliminer les n-uplets en double apparaissant dans la nouvelle
relation.
• On la note 𝚷(𝑨𝟏,…,𝑨𝒏) 𝑹.
• Exemple: Soit la relation personne
𝚷(𝑵𝒐𝒎) 𝑷𝒆𝒓𝒔𝒐𝒏𝒏𝒆
6
Les opérations binaires ensemblistes
• Union:
• L’union est une opération portant sur deux relations R1 et R2 ayant le même
schéma et construisant une troisième relation constituée des n-uplets
appartenant à chacune des deux relations R1 et R2 sans doublon.
• On la note 𝑹𝟏 ∪ 𝑹𝟐 .
• Exemple:
𝑹 = 𝑹𝟏 ∪ 𝑹𝟐
7
Les opérations binaires ensemblistes
• Intersection:
• L’intersection est une opération portant sur deux relations R1 et R2 ayant le
même schéma et construisant une troisième relation dont les n-uplets sont
constitués de ceux appartenant aux deux relations.
• On la note 𝑹𝟏 ∩ 𝑹𝟐 .
• Exemple:
𝑹 = 𝑹𝟏 ∩ 𝑹𝟐
8
Les opérations binaires ensemblistes
• Différence:
• La différence est une opération portant sur deux relations R1 et R2 ayant le
même schéma et construisant une troisième relation dont les n-uplets sont
constitués de ceux ne se trouvant que dans la relation R1.
• On la note 𝑹𝟏 − 𝑹𝟐 .
• Exemple:
𝑹 = 𝑹 𝟏 − 𝑹𝟐
9
Les opérateurs binaires ou n-aires
• Produit cartésien:
• Le produit cartésien est une opération portant sur deux relations R1 et R2 et
qui construit une troisième relation regroupant exclusivement toutes les
possibilités de combinaison des occurrences des relations R1 et R2.
• On la note 𝑹𝟏 × 𝑹𝟐 .
• Exemple:
𝑹 = 𝑹𝟏 × 𝑹 𝟐
10
Les opérateurs binaires ou n-aires
• Jointure:
• La jointure est une opération portant sur deux relations R1 et R2 qui construit
une troisième relation regroupant exclusivement toutes les possibilités de
combinaison des occurrences des relations R1 et R2 qui satisfont
l’expression logique E.
• On la note 𝑹𝟏 ⋈𝑬 𝑹𝟐 . 𝑹𝟏 ⋈𝑬 𝑹𝟐 = 𝝈𝑬 (𝑹𝟏
× 𝑹𝟐 )
• Exemple:
R= Famille ⋈((𝑨𝒈𝒆𝑪>𝑨𝒈𝒆)∧(𝑷𝒓𝒊𝒙<𝟓𝟎)) Cadeau 11
Les opérateurs binaires ou n-aires
• Équi-jointure:
• Une équi-jointure est un type de jointure entre deux tables qui sélectionne
uniquement les lignes ayant des valeurs égales dans les colonnes comparées
des deux tables.
• La seule condition utilisée est l’égalité (=)
• Théta-jointure:
• Une thêta-jointure est une jointure entre deux tables basée sur n’importe
quelle condition de comparaison entre les attributs des deux tables, en
utilisant des opérateurs relationnels tels que =, <, >, <=, >=, ou <>.
12
Les opérateurs binaires ou n-aires
• Jointure naturelle:
• Une jointure naturelle est une equi-jointure dans laquelle les attributs des
relations R1 et R2 portent le même nom A.
• Parfois noté sans condition: 𝑹𝟏 ⋈ 𝑹𝟐
𝑹 = 𝑭𝒂𝒎𝒊𝒍𝒍𝒆 ⋈ 𝑪𝒂𝒅𝒆𝒂𝒖
13
Les opérateurs binaires ou n-aires
• Division:
• La division est une opération portant sur deux relations R1 et R2, telles que le
schéma de R2 est strictement inclus dans celui de R1, qui génère une
troisième relation regroupant toutes les parties d’occurrences de la relation
R1 qui sont associées à toutes les occurrences de la relation R2.
• On la note: 𝑹𝟏 ÷ 𝑹𝟐
R = Enseignant ÷ Etudiant
14
Equivalence opérateur algèbrique en langage
SQL
Algèbre Relationnelle Description SQL Équivalent
SELECT * FROM table WHERE
σ (sélection) Filtrer les lignes (conditions)
condition
SELECT colonne1, colonne2 FROM
π (projection) Choisir certaines colonnes
table
SELECT ... FROM table1 UNION SELECT
∪ (union) Union de deux relations
...
SELECT ... FROM table1 EXCEPT SELECT
− (différence) Différence de deux relations
...
SELECT ... FROM table1 INTERSECT
∩ (intersection) Intersection de deux relations
SELECT ...
× (produit cartésien) Combinaison de toutes les paires SELECT * FROM table1, table2
15
Equivalence opérateur algèbrique en langage
SQL
Tables :
• Inscription(étudiant_id, cours_id)
• CoursObligatoires(cours_id)
• Quels étudiants sont inscrits à tous les cours obligatoires ?
SELECT i.étudiant_id
FROM Inscription i
GROUP BY i.étudiant_id
HAVING COUNT(DISTINCT i.cours_id) = (
SELECT COUNT(*) FROM CoursObligatoires
);
16
Equivalence opérateur algèbrique en langage
SQL
Tables : SELECT e.étudiant_id
FROM Étudiants e
• Inscription(étudiant_id, cours_id)
WHERE NOT EXISTS (
• CoursObligatoires(cours_id)
SELECT *
FROM CoursObligatoires c
• Quels étudiants sont inscrits WHERE NOT EXISTS (
à tous les cours obligatoires ? SELECT *
FROM Inscription i
WHERE i.étudiant_id = e.étudiant_id
AND i.cours_id = c.cours_id
)
);
17
Exemple
- Soit le schéma relationnel suivant :
• Individu(Num-Ind, Nom, Prénom)
• Jouer(Num-Ind, Num-Film*, Rôle)
• Film(Num-Film, Num-Ind*, Titre, Genre, Année)
• Projection(Num-Ciné, Num-Film*, Date)
• Cinéma(Num-Ciné, Nom, Adresse)
18
Exemple
Quel est le résultat des requêtes suivantes?
• Individu(Num-Ind, Nom, Prénom)
- • Jouer(Num-Ind, Num-Film*, Rôle)
• Film(Num-Film, Num-Ind*, Titre, Genre,
Année)
• Projection(Num-Ciné, Num-Film*, Date)
• Cinéma(Num-Ciné, Nom, Adresse)
19
Exemple
Quel est le résultat des requêtes suivantes?
• Individu(Num-Ind, Nom, Prénom)
• Jouer(Num-Ind, Num-Film*, Rôle)
• Film(Num-Film, Num-Ind*, Titre, Genre,
Année)
• Projection(Num-Ciné, Num-Film*, Date)
• Cinéma(Num-Ciné, Nom, Adresse)
20
Evaluation et optimisation
Requête
• Validation de la syntaxe de la
Analyse requête
Résultat
• Transformation de la requête en
Compilation arbre algèbrique
• Recherche de l’arbre
Optimisation
optimal
• Exécution du programme
Exécution correspondant à l’arbre
retenu
21
Evaluation et optimisation
22
[Link]
Lois algébriques
1- Commutativité des jointures:
𝑹 ⋈𝑬 𝑺 = 𝑺 ⋈𝑬 𝑹
23
Lois algébriques
2- Associativité des jointures:
𝑹 ⋈𝑬 𝑺 ⋈𝑭 𝑻 = 𝑹 ⋈𝑬 (𝑺 ⋈𝑭 𝑻)
24
Lois algébriques
3- Groupabilité des restrictions :
𝝈𝑪𝟐 𝝈𝑪𝟏 𝑹 = 𝝈𝑪𝟏^𝑪𝟐 (𝑹)
25
Lois algébriques
4- Semi-commutatitivité des restrictions et des projections:
𝚷𝑨𝟏 ,…,𝑨𝑷 (𝝈𝑨𝒊 =𝒂 𝑹 ) = 𝚷𝑨𝟏 ,…,𝑨𝑷 (𝝈𝑨𝒊 =𝒂 𝚷𝑨𝒊 ,𝑨𝟏 ,…,𝑨𝑷 (𝑹) )
26
Lois algébriques
5- Distributivité des restrictions sur les jointures:
𝝈𝑨𝒊 =𝒂 𝑹 ⋈𝑬 𝑺 = 𝝈𝑨𝒊 =𝒂(𝑹) ⋈𝑬 𝑺 Ou 𝝈𝑨𝒊 =𝒂 𝑹 ⋈𝑬 𝑺 = 𝑹 ⋈𝑬 𝝈𝑨𝒊 =𝒂(𝑺)
27
Lois algébriques
6- Distributivité des projections sur les jointures:
𝚷𝒓𝟏 ,…,𝒓𝑷 ,𝒔𝟏 ,…,𝒔𝒏 R ⋈𝑨=𝑩 S =
𝚷𝒓𝟏 ,…,𝒓𝑷 ,𝒔𝟏 ,…,𝒔𝒏 𝚷𝑨,𝒓𝟏 ,…,𝒓𝑷 (𝑅) ⋈𝑨=𝑩 𝚷𝑩,𝒔𝟏 ,…,𝒔𝑷 (S)
28
Lois algébriques
7- Distributivité des restrictions sur l’union:
𝝈𝑨𝒊 =𝒂 R ∪ S = 𝝈𝑨𝒊 =𝒂(R) ∪ 𝝈𝑨𝒊 =𝒂(S)
𝝈𝑨𝒊 =𝒂 R − S = 𝝈𝑨𝒊 =𝒂 R − 𝝈𝑨𝒊 =𝒂(S)
29
Lois algébriques
8- Distributivité des projections sur l’union:
𝚷𝑨𝟏 ,…,𝑨𝒑 R ∪ S = 𝚷𝑨𝟏 ,…,𝑨𝒑 (𝑅) ∪ 𝚷𝑨𝟏 ,…,𝑨𝒑 (S)
30
Algorithme général d'optimisation heuristique
• Les étapes principales de l'algorithme sont les suivantes :
1. Décomposer les restrictions en restrictions unaires
2. Rapprocher les restrictions aux feuilles
3. Grouper les restrictions aux feuilles
4. Rapprocher les projections des feuilles
5. Ordonner les jointures afin de minimizer le temps
31
Exemple
• Soit la requete suivante:
SELECT nomEmp, nomDept
FROM employes e JOIN departements d ON [Link] = [Link]
WHERE [Link] > 5000 AND [Link] = Maroc';
• L’expression algébrique correspondante:
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕 (𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎 ^ 𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄” 𝒆𝒎𝒑𝒍𝒐𝒚𝒆𝒔 ⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔 )
32
Exemple
• L’expression algébrique correspondante:
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕 (𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎 ^ 𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄” 𝑬𝒎𝒑𝒍𝒐𝒚𝒆𝒔 ⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔 )
• L’arbre algébrique correspondant:
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕
𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎 ^ 𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅
E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔
33
1. Décomposer les restrictions en restrictions unaires
2. Rapprocher les restrictions aux feuilles
Exemple 3.
4.
Grouper les restrictions aux feuilles
Rapprocher les projections des feuilles
5. Ordonner les jointures afin de minimizer le temps
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕
𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎
𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎 ^ 𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
𝝈𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅
E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔
E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔
34
1. Décomposer les restrictions en restrictions unaires
2. Rapprocher les restrictions aux feuilles
Exemple 3.
4.
Grouper les restrictions aux feuilles
Rapprocher les projections des feuilles
5. Ordonner les jointures afin de minimizer le temps
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕
𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅
𝝈𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
𝝈𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅 𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎
E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔
E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔
35
1. Décomposer les restrictions en restrictions unaires
2. Rapprocher les restrictions aux feuilles
Exemple 3.
4.
Grouper les restrictions aux feuilles
Rapprocher les projections des feuilles
5. Ordonner les jointures afin de minimizer le temps
𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕 𝚷𝒏𝒐𝒎𝑬𝒎𝒑,𝒏𝒐𝒎𝑫𝒆𝒑𝒕
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅
⋈𝒅𝒆𝒑𝒕𝑰𝒅=𝑰𝒅
𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎 𝝈𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
𝝈𝒗𝒊𝒍𝒍𝒆=“𝒎𝒂𝒓𝒐𝒄”
𝝈𝒔𝒂𝒍𝒂𝒊𝒓𝒆>𝟓𝟎𝟎𝟎
𝚷𝒏𝒐𝒎𝑬𝒎𝒑, 𝒔𝒂𝒍𝒂𝒊𝒓𝒆,𝒅𝒆𝒑𝒕𝑰𝒅 𝚷𝒏𝒐𝒎𝑫𝒆𝒑𝒕,𝒗𝒊𝒍𝒍𝒆,𝑰𝒅
E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔 E𝒎𝒑𝒍𝒐𝒚𝒆𝒔 𝑫𝒆𝒑𝒂𝒓𝒕𝒆𝒎𝒆𝒏𝒕𝒔
PLAN D’EXECUTION LOGIQUE OPTIMISÉ
36
