Algèbre relationnelle

Opérateurs de base

Il existe cinq opérateurs de base pour formuler des requêtes sur une base de données relationnelle :

1. La projection (\(\Pi\))
2. La restriction (\(\sigma\))
3. Le produit cartésien (\(\times\))
4. L’union (\(\cup\))
5. La différence (\(\setminus\))

A partir desquels on pourra construire les opérateurs dérivés :

• d’intersection (\(\cap\))
• de jointure (\(\Join\))
• de division relationnelle (\(\div\))
• …

1. \(\Pi_{(a_1,...,a_n)}(E)\) : projection

   • réduire le nombre d’attributs (\(a_1,...,a_n\)) sur les éléments d’un ensemble (\(E\))

2. \(\sigma_{[p(e)]}(E)\) : restriction

   • récupérer les éléments (\(e\)) d’un ensemble (\(E\)) qui satisfont un critère de restriction (\([p(e)]\))

3. \(\times(E,F)\) : produit cartésien

   • mettre en relation chaque élément de l’ensemble \(E\) avec tous les éléments de l’ensemble \(F\)

4. \(\cup(E,F)\) : union

   • créer l’ensemble contenant les éléments qui sont dans l’ensemble \(E\) et/ou dans l’ensemble \(F\)

5. \(\setminus(E,F)\) : différence

   • créer l’ensemble contenant les éléments de l’ensemble \(E\) qui ne sont pas dans l’ensemble \(F\)

Opérateurs dérivés

1. \(\cap(E,F)\) : intersection

   • créer l’ensemble contenant les éléments de l’ensemble \(E\) qui sont dans l’ensemble \(F\)

2. \(\Join_{[p(e,f)]}(E,F)\) : jointure

   • mettre en relation les éléments \((e,f)\) des ensembles \((E,F)\) s’ils satisfont un critère de jointure (\([p(e,f)]\))

3. \(\div(E,F)\) : division relationnelle

   • récupérer les éléments \((e,f)\) de l’ensemble \(E\) qui sont en relation avec tous les éléments de l’ensemble \(F\)

   où \(attr(F) \subset attr(E)\) :

   • l’ensemble des attributs de l’ensemble \(F\) est un sous-ensemble de l’ensemble des attributs de l’ensemble \(E\) :

les opérateurs dérivés se déduisent des opérateurs de base.

L’intersection peut s’exprimer en fonction des opérateurs de différence (\(\setminus\)) et d’union (\(\cup\)) :

• \(\cap(E,F)=\setminus(E,\setminus(E,F))\)
• \(\cap(E,F)=\setminus(F, \setminus(F,E))\)
• \(\cap(E,F))=\setminus(\cup(E,F)),[(\cup (\setminus(E,F)),\setminus(F,E))])\)

La division relationnelle peut s’exprimer en fonction des opérateurs de projection (\(\Pi\)), de produit cartésien (\(\times\)) et de différence (\(\setminus\)) :

• \(\div(E,F)=\setminus(\Pi_{(X)}(E),\Pi_{(X)}(\setminus(\times(\Pi_{(X)}(E),F),E)))\)

Nous reviendrons sur ces opérateurs dans le chapitre sur l’algèbre relationnelle.

Du calcul à l’algèbre relationnelle

Toute requête sur une base de données peut être exprimée par une formule de logique du premier ordre en calcul relationnel.

Les opérateurs de l’algèbre relationnelle qui seront utilisés pour formuler des requêtes sur une base de données peuvent être formalisés en calcul relationnel :

1. Projection : réduire le nombre d’attributs (\(a_1,...,a_n\)) sur les éléments d’un ensemble (\(E\))

   • \(\Pi_{(a_1,...,a_n)}(E)=\{ (e.a_1,....,e.a_n) \; | \; e \in E \}\)

2. Produit cartésien : mettre en relation chaque élément de l’ensemble \(E\) avec tous les éléments de l’ensemble \(F\)

   • \(\times(E,F)=\{ (e,f) \; | \; e \in E \land f \in F \}\)

3. Restriction : récupérer les éléments (\(e\)) d’un ensemble (\(E\)) qui satisfont un critère de restriction \([p(e)]\)

   • \(\sigma_{[p(e)]}(E)=\{ e \; | \; e \in E \land p(e) \}\)

4. Jointure : mettre en relation les éléments \((e,f)\) des ensembles \((E,F)\) s’ils satisfont un critère de jointure \([p(e,f)]\)

   • \(\Join_{[p(e,f)]}(E,F)=\{ (e,f) \; | \; e \in E \land f \in F \land p(e,f) \}\)

5. Union : créer l’ensemble contenant les éléments qui sont dans l’ensemble \(E\) et dans l’ensemble \(F\)

   • \(\cup(E,F)=\{ r \; | \; r \in \Pi_{(e_1,...,e_n)}(E) \lor r \in \Pi_{(f_1,...,f_n)}(F) \}\)

6. Différence : créer l’ensemble contenant les éléments de l’ensemble \(E\) qui ne sont pas dans l’ensemble \(F\)

   • \(\setminus(E,F)=\{ r \; | \; r \in \Pi_{(e_1,...,e_n)}(E) \land r \notin \Pi_{(f_1,...,f_n)}(F) \}\)

7. Intersection : créer l’ensemble contenant uniquement les éléments de l’ensemble \(E\) qui sont aussi dans l’ensemble \(F\)

   • \(\cap(E,F)=\{ r \; | \; r \in \Pi_{(e_1,...,e_n)}(E) \land r \in \Pi_{(f_1,...,f_n)}(F) \}\)

8. Division relationnelle : récupérer les éléments \((e,f)\) de l’ensemble \(E\) qui sont en relation avec tous les éléments \((f)\) de l’ensemble \(F\)

   • \(\div(E,F)=\{e \; | \; \forall f \in F, (e,f) \in E \}\)

   où \(attr(F) \subset attr(E)\) : l’ensemble des attributs de (\(F\)) est un sous-ensemble de l’ensemble des attributs de (\(E\))

Il existe un autre opérateur de l’algèbre relationnelle qui consiste à renommer les attributs d’une table (relation) que nous définirons de manière très « littéraire » de la manière suivante :

• \(\rho_{A_1:B_1, ..., A_n:B_n}(E)=\{e \; | \forall e \in E\) « renommer \(e.A_1\) en \(e.B_1\) … \(e.A_n\) en \(e.B_n\) » \(\}\)

Autre notation de l’opérateur de renommage :

• \(\rho_{A \rightarrow B}\)
• \(\delta_{A \rightarrow B}\)
• \(\delta_{A:B}\)

L’intérêt de cet opérateur apparaît lorsque que l’on doit faire des opérations sur des colonnes de même nom dans différentes tables.

Ce cas arrive fréquemment, notamment lorsque l’on est amené à faire un produit cartésien entre deux tables ayant 2 colonnes de même nom.