Cours complet pour apprendre les différents types de bases de données et le langage SQL


précédentsommairesuivant

VI. Algèbre relationnelle

VI-A. Objectifs

  • L'algèbre relationnelle fournit les opérateurs de base pour manipuler les extensions des relations (ensembles de n-uplets ou tables) d'une BD relationnelle.
  • On peut faire un parallèle avec l'arithmétique qui fournit les opérations de base pour manipuler les nombres (addition, soustraction, multiplication et division).
  • Tout SGBD relationnel se doit de fournir des implantations efficaces de ces opérateurs.
  • Une requête SQL est traduite, comme on le verra, en un arbre d'opérateurs de l'algèbre relationnelle.

VI-B. Expressions

L'algèbre relationnelle permet de construire des expressions à partir :

  • de noms de relations :

    • relations stockées dans la BD,
    • relations temporaires ;
  • de comparateurs, de connecteurs logiques, d'opérateurs arithmétiques... ;
  • d'opérateurs ensemblistes qui :

    • sélectionnent certaines parties d'une relation,
    • combinent les n-uplets de deux relations.

Une expression de l'algèbre relationnelle a pour valeur une relation :

  • elle exprime une requête à la BD dont la réponse est la valeur de cette expression.

On notera :

  • p, q, r des expressions de l'algèbre relationnelle ;
  • A, B, C des noms d'attributs ;
  • schéma(r) le schéma de la relation valeur de l'expression r ;
  • ext(r) l'extension de la relation valeur de l'expression r ;
  • t.A la valeur de l'attribut A dans le n-uplet t.
  • conc la concaténation de deux n-uplets :

    • (v1, …, vm) conc (w1, …, wn) = (v1, …, vm, w1, …, wn).

Si R est le nom d'une relation, alors R est une expression telle que :

  • schéma(R) = schéma de la relation désignée par R ;
  • extension(R) = extension de la relation désignée par R.

VI-C. Relations temporaires

Il est possible de créer des relations temporaires.

L'instruction :

  • R := e

crée une relation temporaire de nom R dont le schéma et l'extension sont celles de la relation valeur de l'expression e.

VI-D. Principaux opérateurs

Les principaux opérateurs de l'algèbre relationnelle sont les suivants :

  • renommage ;
  • union, intersection et différence ;
  • produit cartésien ;
  • sélection ;
  • projection ;
  • jointure :

    • interne,
    • externe,
    • naturelle ;
  • division.

VI-D-1. Renommage

L'opérateur de renommage (ρ) permet de renommer les attributs d'une relation.

Soit r une expression telle que :

  • schéma(r) = (A1, …, An)

l'opérateur ρ est défini par :

  • kitxmlcodeinlinelatexdvpsch\acute{e}ma\left(\rho _{B_1, \dots, B_n}(r)\right) = (B_1, \dots, B_n)finkitxmlcodeinlinelatexdvp
  • kitxmlcodeinlinelatexdvpext\left(\rho _{B_1, \dots, B_n}(r)\right) = ext(r)finkitxmlcodeinlinelatexdvp
Image non disponible

VI-D-2. Union, intersection et différence

Soit p et q deux expressions telles que :

  • schéma(p) = schéma(q) = (A1: D1, …, An: Dn)

Les opérateurs d'union (∪), d'intersection (⋂) et de différence (—) sont définis par :

  • schéma(p ∪ q) = (A1: D1, …, An: Dn)
  • ext(p ∪ q) = {t | t ∈ ext(p) ∨ t ∈ ext(q)}
  • schéma(p ⋂ q) = (A1: D1, …, An: Dn)
  • ext(p ⋂ q) = {t | t ∈ ext(p) ∧ t ∈ ext(q)}
  • schéma(p — q) = (A1: D1, …, An: Dn)
  • ext(p — q) = {t | t ∈ ext(p) ∧ t ∉ ext(q)}
Image non disponible

VI-D-3. Produit cartésien

Soit p et q deux expressions telles que :

  • schéma(p) = (A1, …, Am)
  • schéma(q) = (B1, …, Bn)
  • {A1, …, Am} ⋂ {B1, …, Bn} = Ø

Le produit cartésien (×) est défini par :

  • schéma(p × q) = (A1, …, Am, B1, …, Bn)
  • ext(p × q) = {u conc v | u ∈ ext(p) ∧ v ∈ ext(q)}
Image non disponible

VI-D-4. Sélection

L'opérateur de sélection (σ) extrait l'ensemble des n-uplets d'une relation qui vérifient une condition donnée.

Une condition est une expression booléenne (c'est-à-dire dont la valeur est vraie ou fausse) :

  • dont les opérandes sont soit des valeurs de domaine, soit des noms d'attributs de la relation à laquelle s'applique la sélection ;
  • les opérateurs sont les comparateurs : <, <=, =, >=, >, != et les connecteurs logiques : ∧, ∨, ¬.

Par exemple :

  • altitude > 8500 ∧ (face = "S" ∨ face = "SO") est une condition applicable aux n-uplets de la relation sommet.

Soit r une expression telle que :

  • schéma(r) = (A1, …, An).

L'opérateur σ est défini par :

  • schéma(σcond) = (A1, …, An) ;
  • ext(σcond) = {t | t ∈ ext(r) ∧ val(cond)}.
Image non disponible

VI-D-5. Projection

L'opérateur de projection (π) extrait l'ensemble des valeurs d'un constituant d'une relation.

Soit r une expression telle que :

  • schéma(r) = (A1: D1, …, An: Dn)

L'opérateur de projection est défini par :

  • schéma(πA1, …, An(r)) = (A1: D1, …, An: Dn) ;
  • ext(πA1, …, An(r)) = {(t.A1, …, t. An) | t ∈ ext(r)}.
Image non disponible

VI-D-6. Jointure

La jointure est l'opération qui permet de concaténer des n-uplets provenant de deux tables et vérifiant une certaine condition.

On distingue trois types de jointure :

  • la jointure interne ;
  • la jointure externe ;
  • la jointure naturelle.

La jointure n'est pas un opérateur primitif :

  • Elle peut être réalisée, selon son type, en combinant les opérateurs de produit cartésien, de sélection, de projection et de renommage.

VI-D-6-a. Jointure interne

L'opérateur de jointure interne (join) fusionne deux relations en produisant toutes les concaténations possibles de leurs n-uplets respectifs qui vérifient une certaine condition.

La jointure interne est équivalente à un produit cartésien suivi d'une sélection :

  • p joincond q ≡ σcond(p × q)
Image non disponible

VI-D-6-b. Jointure externe

L'opérateur de jointure externe permet d'ajouter au résultat d'une jointure interne les n-uplets de l'une, de l'autre ou des deux relations qui ne peuvent pas être joints.

Soit P et Q les relations à joindre, on distingue :

  • la jointure externe totale (ejoin) qui ajoute les n-uplets de P et de Q qui ne peuvent pas être joints ;
  • la jointure externe gauche (lejoin) qui n'ajoute que les n-uplets de P qui ne se joignent pas avec un n-uplet de Q ;
  • la jointure externe droite (rejoin) qui n'ajoute que les n-uplets de Q qui ne se joignent pas avec un n-uplet de P.

Les n-uplets ainsi rajoutés sont complétés par des valeurs nulles pour les attributs qu'ils ne possèdent pas.

Image non disponible

Soit p et q deux expressions telles que :

  • schéma(p) = (A1, …, Am) ;
  • schéma(q) = (B1, …, Bn) ;
  • {A1, …, Am} ⋂ { B1, …, Bn} = Ø.

L'opérateur ejoin est défini par :

  • schéma(p ejoincond q) = (A1, …, Am, B1, …, Bn) ;
  • ext(p ejoincond q) = pext ∪ j ∪ qext.

où :

Image non disponible

VI-D-6-c. Jointure naturelle

Dans une jointure, qu'elle soit interne ou externe, on peut omettre la condition lorsqu'elle se restreint à ce que les attributs de même nom de chacune des relations à joindre doivent avoir la même valeur :

  • on appelle jointure naturelle ce cas particulier de jointure.

La jointure naturelle sera notée en omettant la condition sous l'opérateur de jointure considéré.

Dans la relation produite, les attributs communs aux deux relations n'apparaîtront qu'une seule fois.

Si les deux relations à joindre n'ont pas d'attributs communs, alors la jointure naturelle est équivalente au produit cartésien.

Image non disponible

Soit p et q deux expressions telles que :

  • schéma(p) = (A1, …, Am) ;
  • schéma(q) = (B1, …, Bn) ;
  • {A1, …, Am} ⋂ { B1, …, Bn} = {C1, …, Ck}.

La jointure naturelle est définie par :

  • schéma(p j q) = (A1, …, Am, L)
  • kitxmlcodeinlinelatexdvpp\ j\ q\ =\ \pi_{A_1,\ \dots,\ A_m,\ L} (p\ join_{C_1\ =\ C_1\ \wedge\ \dots\ \wedge\ C_k\ =\ C'_k}\ q') finkitxmlcodeinlinelatexdvp

où :

  • j est l'un des opérateurs join, ejoin, lejoin, rejoin ;
  • L est la liste des attributs de q dans laquelle les attributs C1, …, Ck ont été supprimés ;
  • q' est la relation obtenue à partir de q en renommant respectivement C'1, …, C'k les attributs C1, …, Ck avec
    {A1, …, Am, B1, …, Bn} ⋂ {C'1, …, C'k} = Ø

VI-E. Requêtes en algèbre relationnelle

Nom et altitude des sommets de plus de 8000 m dont la 1re ascension a été réalisée par la face nord ?

  • réponse := πnom, altitudeface = "N"(sommet));

Nom et altitude des sommets de plus de 8000 m dont la 1re ascension a été réalisée par Hermann Buhl ?

  • ahb := σprénom = "Hermann" ∧ nom = "Buhl"(ascension)
  • réponse := πnom, altitude(sommet joinnom = nom_sommet ahb)

Nom des sommets de plus de 8000 m dont l'altitude est supérieure à celle du Makalu ?

  • am := ρaltitude_makalualtitudenom = "Makalu"(sommet)));
  • réponse := πnom(sommet joinaltitude > altitude_makalu am);

Prénom et nom des grimpeurs ayant réalisé la 1re ascension d'un sommet de plus de 8000 m du Népal ?

  • asn := ascension join σpays = "Népal"(localisation);
  • réponse := πprénom_grimpeur, nom_grimpeur(asn);

Nom des sommets de plus de 8000 m qui ne sont pas au Népal (on sélectionne les noms des sommets qui ne joignent pas avec les sommets du Népal) ?

  • nsn := πnom_sommetpays = "Népal"(localisation))
  • réponse := πnomnom_sommet = nul(sommet ejoinnom = nom_sommet nsn));

Nom des sommets de plus de 8500 mètres situés au Népal mais pas sur la frontière chinoise ?

  • ns := ρnom_sommetnomaltitude > 8500(sommet)));
  • nsn := πnom_sommetpays = "Népal"(localisation));
  • nsc := πnom_sommetpays = "Chine"(localisation));
  • réponse := ns ∩ nsn ∩ nsc;

VI-F. Arbre de requête

Une requête de l'algèbre relationnelle peut être représentée par un arbre, appelé arbre de requête, dont les nœuds sont des opérateurs et les arcs des extensions de relations.

On considérera un nom de relation comme l'opérateur qui produit l'extension de la relation ayant ce nom.

Image non disponible
Nom et altitude des sommets dont la 1re ascension a été réalisée par Hermann Buhl ?
Image non disponible
Nom des sommets de plus de 8500 mètres situés au Népal mais pas sur la frontière chinoise ?

précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+