Fiche de révision : Algèbre relationnelle

📋 Plan du Cours

1. Fondements de l’algèbre relationnelle
2. Sélection et projections
3. Produit et jointures
4. Renommage des relations
5. Expressions relationnelles complexes
6. Schémas des résultats
7. Algèbre relationnelle sur les bags
8. Élimination et tri
9. Agrégation et groupement

📖 1. Fondements de l’algèbre relationnelle

🔑 Notions clés & Définitions

• Algèbre : Système mathématique composé d’opérandes, qui sont des variables ou valeurs, et d’opérateurs, qui construisent de nouvelles valeurs à partir d’opérandes données.
• Algèbre relationnelle : Algèbre dont les opérandes sont des relations ou des variables représentant des relations, et dont les opérateurs permettent d’interroger les relations d’une base de données.

📝 Points essentiels

• Les opérateurs fondamentaux sont:
  • l’union
  • l’intersection
  • la différence
  • la sélection
  • la projection
  • les produits
  • les jointures
  • le renommage des relations ou des attributs

💡 Astuce mémo

Opérandes = données, opérateurs = transformations

📖 2. Sélection et projections

🔑 Notions clés & Définitions

• Sélection : Conserve dans R1 les tuples de R2 qui satisfont la condition C portant sur les attributs de R2.
• Projection : Extrait de chaque tuple de R2 les attributs de la liste L dans l’ordre indiqué et élimine les tuples dupliqués.

📝 Points essentiels

• La sélection $\sigma_{bar="Joe's"}(Sells)$ produit JoeMenu, contenant les deux tuples de Sells associés au bar Joe’s.

📐 Formule — Une projection étendue peut appliquer une expression arithmétique aux attributs, par exemple $A+B\to C$, et faire apparaître plusieurs fois le même attribut.

💡 Astuce mémo

Sélection = lignes, projection = colonnes

📖 3. Produit et jointures

🔑 Notions clés & Définitions

• Produit cartésien : Associe chaque tuple de R1 à chaque tuple de R2 et concatène les tuples, avec les attributs de R1 puis ceux de R2.
• Theta-jointure : Obtenue en calculant le produit cartésien de R1 et R2, puis en lui appliquant la sélection selon la condition booléenne C.
• Jointure naturelle : Relie deux relations en égalant les attributs de même nom, puis projette une seule copie de chaque paire d’attributs équivalents.
• Jointure externe : Conserve les tuples pendants, c’est-à-dire sans tuple correspondant dans l’autre relation, en complétant leurs attributs par des valeurs NULL.

💡 Astuce mémo

Produit puis condition → theta-jointure

📖 4. Renommage des relations

🔑 Notions clés & Définitions

• Renommage : Donne à R2 le schéma de R1 tout en conservant les mêmes tuples.

📖 5. Expressions relationnelles complexes

★ À maîtriser

• Une expression complexe peut être construite par une suite d’affectations créant des relations temporaires, par une expression unique avec parenthèses ou par un arbre d’expression.

• La priorité des opérateurs relationnels est, de la plus forte à la plus faible, [σ, π, ρ], puis [×, ⋈], puis ∩, puis [∪, −].

Compléments

• Pour trouver les bars situés sur Maple St. ou vendant Bud à moins de 3 dollars, l’arbre combine deux sélections, deux projections, une union et un renommage.

💡 Astuce mémo

Affectations → expression unique → arbre

📖 6. Schémas des résultats

★ À maîtriser

• L’union, l’intersection et la différence utilisent le schéma commun de leurs deux opérandes, qui doivent avoir le même schéma.

• Le schéma d’un produit contient les attributs des deux relations, celui d’une theta-jointure est identique à celui du produit, et celui d’une jointure naturelle est l’union des attributs des deux relations.

Compléments

• Le schéma d’une sélection reste celui de son opérande, celui d’une projection est donné par sa liste d’attributs, et celui d’un renommage est indiqué par l’opérateur.

📖 7. Algèbre relationnelle sur les bags

🔑 Notions clés & Définitions

• Bag : Collection dans laquelle un élément peut apparaître plusieurs fois, contrairement à un ensemble.

★ À maîtriser

• En algèbre relationnelle sur les bags, la sélection conserve l’effet tuple par tuple, la projection ne supprime pas les doublons, et les produits et jointures traitent chaque paire de tuples.

📌 Dans l’union de deux bags, la multiplicité d’un élément est la somme de ses multiplicités dans les deux bags.

Compléments

📌 Dans l’intersection de deux bags, la multiplicité d’un élément est le minimum de ses multiplicités dans les deux bags.

📌 Dans la différence A − B de deux bags, la multiplicité d’un élément est sa multiplicité dans A diminuée de celle dans B, sans jamais devenir négative.

• L’union de bags vérifie $\{1{,}2{,}1\}\cup\{1{,}1{,}2{,}3{,}1\}=\{1{,}1{,}1{,}1{,}1{,}2{,}2{,}3\}$.

💡 Astuce mémo

Ensemble : sans doublons ; bag : doublons conservés

📖 8. Élimination et tri

🔑 Notions clés & Définitions

• Élimination des doublons : Produit une relation contenant une seule copie de chaque tuple apparaissant au moins une fois dans R.
• Tri : Trie les tuples de R selon les attributs de L, d’abord selon le premier attribut, puis selon le suivant, avec des égalités départagées arbitrairement.

📖 9. Agrégation et groupement

🔑 Notions clés & Définitions

• Groupement : Forme un groupe pour chaque combinaison distincte des attributs de groupement de L, calcule les agrégations demandées dans chaque groupe et produit un tuple par groupe.

★ À maîtriser

• Les principaux opérateurs d’agrégation sont:
  • SUM
  • AVG
  • COUNT
  • MIN
  • MAX

Compléments

• Dans une expression de groupement, L peut contenir des attributs individuels ou des expressions AGG(A), éventuellement renommées par une flèche et un nouveau nom d’attribut.

• Pour la relation R(A,B,C), le groupement $\gamma_{A,B,AVG(C)\to X}(R)$ regroupe par A et B, puis calcule la moyenne de C dans chaque groupe, y compris un groupe distinct pour les valeurs NULL de B.

💡 Astuce mémo

Grouper → agréger → produire un tuple par groupe

📊 Tableaux de synthèse

Opérations sur les relations