Skip to content

1 4 4 1 operateurs

SQL, langage algébrique ¼ : Les opérateurs de l'algèbre

Le second langage étudié dans ce cours est l'algèbre relationnelle. Elle consiste en un ensemble d'opérations qui permettent de manipuler des relations, considérées comme des ensembles de nuplets : on peut ainsi faire l'union ou la différence de deux relations, sélectionner une partie des nuplets la relation, effectuer des produits cartésiens ou des projections, etc.

On peut voir l'algèbre relationnelle comme un langage de programmation très simple qui permet d'exprimer des requêtes sur une base de données relationnelle. C'est donc plus une approche d'informaticien que de logicien. Elle correspond moins naturellement à la manière dont on pense une requête. À l'origine, le langage SQL était d'ailleurs entièrement construit sur la logique mathématique, comme nous l'avons vu dans le chapitre chap-calcul, à l'exception de l'union et de l'intersection. L'algèbre n'était utilisée que comme un moyen de décrire les opérations à effectuer pour évaluer une requête. Petit à petit, les évolutions de la norme SQL ont introduit dans le langage les opérateurs de l'algèbre. Il est maintenant possible de les retrouver tous et d'exprimer toutes les requêtes (plus ou moins facilement) avec cette approche. C'est ce que nous étudions dans ce chapitre.

Note
La base utilisée comme exemple dans ce chapitre est celle de nos intrépides voyageurs, présentée dans le chapitre le modèle relationnel..

Les opérateurs de l'algèbre

Supports complémentaires

L'algèbre se compose d'un ensemble d'opérateurs, parmi lesquels 6 sont nécessaires et suffisants et permettent de définir les autres par composition. Une propriété fondamentale de chaque opérateur est qu'il prend une ou deux relations en entrée, et produit une relation en sortie. Cette propriété (dite de clôture) permet de composer des opérateurs : on peut appliquer une sélection au résultat d'un produit cartésien, puis une projection au résultat de la sélection, et ainsi de suite. En fait on peut construire des expressions algébriques arbitrairement complexes qui permettent d'effectuer toutes les requêtes relationnelles à l'aide d'un petit nombre d'opérations de base.

Ces opérations sont donc :

  • La sélection, dénotée \(\sigma\).
  • La projection, dénotée \(\pi\).
  • Le renommage, dénoté \(\rho\).
  • Le produit cartésien, dénoté \(\times\).
  • L'union, \(\cup\).
  • La différence, \(-\).

Les trois premiers sont des opérateurs unaires (ils prennent en entrée une seule relation) et les autres sont des opérateurs binaires. À partir de ces opérateurs il est possible d'en définir d'autres, et notamment la jointure, \(\Join\), qui est la composition d'un produit cartésien et d'une sélection. C'est une opération essentielle, nous lui consacrons la prochaine session.

Ces opérateurs sont maintenant présentés tour à tour.

La projection, \(\pi\)

La projection \(\pi_{A_1, A_2, \ldots,A_k}(R)\) s'applique à une relation \(R\), et construit une relation contenant tous les nuplets de \(R\), dans lesquels seuls les attributs \(A_1, A_2, \ldots A_k\) sont conservés. La requête suivante construit une relation avec le nom des logements et leur lieu.

\[\pi_{nom, lieu}(Logement)\]

On obtient le résultat suivant, après suppression des colonnes id, capacité et type :

nom lieu
Causses Cévennes
Génépi Alpes
U Pinzutu Corse
Tabriz Bretagne

En SQL, le projection s'exprime avec le select suivi de la liste des attributs à projeter.

select nom, lieu
from Logement

C'est un habillage syntaxique direct de la projection.

Si on souhaite conserver tous les attributs, on peut éviter d'en énumérer la liste en la remplaçant par *.

select *
from Logement

Note
En algèbre cette requête est tout simplement l'identité : \(R\)

La sélection, \(\sigma\)

La sélection \(\sigma_F(R)\) s'applique à une relation, \(R\), et extrait de cette relation les nuplets qui satisfont un critère de sélection, \(F\). Ce critère peut être :

  • La comparaison entre un attribut de la relation, \(A\), et une constante \(a\). Cette comparaison s'écrit \(A \Theta a\), où \(\Theta\) appartient à \(\{=, <, >, \leq, \geq\}\).
  • La comparaison entre deux attributs \(A_1\) et \(A_2\), qui s'écrit \(A_1 \Theta A_2\) avec les mêmes opérateurs de comparaison que précédemment.

Premier exemple : exprimer la requête qui donne tous les logements en Corse.

\[\sigma_{lieu='Corse'}(Logement)\]

On obtient donc le résultat :

code nom capacité type lieu
pi U Pinzutu 10 Gîte Corse

La sélection a pour effet de supprimer des nuplets, mais chaque nuplet garde l'ensemble de ses attributs. Il ne peut pas y avoir de problème de doublon (pourquoi ?) et il ne faut donc surtout par appliquer un distinct.

En SQL, les critères de sélection sont exprimés par la clause where.

select * 
from Logement
where lieu = 'Corse'

Les chaînes de caractères doivent impérativement être encadrées par des apostrophes simples, sinon le système ne verrait pas la différence avec un nom d'attribut. Ce n'est pas le cas pour les numériques, car aucun nom d'attribut ne peut commencer par un chiffre.

select * 
from Logement
where capacité = 134

Note
Vous noterez que SQL appelle select la projection, et where la sélection, ce qui est pour le moins infortuné. Dans des langages modernes comme XQuery (pour les modèles basés sur XML) le, select est remplacé par return. En ce qui concerne SQL, la question a donné lieu (il y a longtemps) à des débats mais il était déjà trop tard pour changer.

Le produit cartésien, \(\times\)

Le premier opérateur binaire, et le plus utilisé, est le produit cartésien, \(\times\). Le produit cartésien entre deux relations \(R\) et \(S\) se note \(R \times S\), et permet de créer une nouvelle relation où chaque nuplet de \(R\) est associé à chaque nuplet de \(S\).

Voici deux relations, la première, \(R\), contient

A B
a b
x y

et la seconde, \(S\), contient :

C D
c d
u v
x y

Et voici le résultat de \(R \times S\) :

A B C D
a b c d
a b u v
a b x y
x y c d
x y u v
x y x y

Le nombre de nuplets dans le résultat est exactement \(|R| \times |S|\) (\(|R|\) dénote le nombre de nuplets dans la relation \(R\)).

En lui-même, le produit cartésien ne présente pas un grand intérêt puisqu'il associe aveuglément chaque nuplet de \(R\) à chaque nuplet de \(S\). Il ne prend vraiment son sens qu'associé à l'opération de sélection, ce qui permet d'exprimer des jointures, opération fondamentale qui sera détaillée plus loin.

En SQL, le produit cartésien est un opérateur cross join intégré à la clause from.

select * 
from R cross join S

C'est la première fois que nous rencontrons une expression à l'intérieur du from en lieu et place de la simple énumération par une virgule. Il y a une logique certaine à ce choix : dans la mesure où R cross join S définit une nouvelle relation, la requête SQL peut être vue comme une requête sur cette seule relation, et nous sommes ramenés au cas le plus simple.

Comme illustration de ce principe, voici le résultat du produit cartésien \(Logement \times Activité\) (en supprimant l'attribut description pour gagner de la place).

code nom capacité type lieu codeLogement codeActivité
ca Causses 45 Auberge Cévennes ca Randonnée
ge Génépi 134 Hôtel Alpes ca Randonnée
pi U Pinzutu 10 Gîte Corse ca Randonnée
ta Tabriz 34 Hôtel Bretagne ca Randonnée
ca Causses 45 Auberge Cévennes ge Piscine
ge Génépi 134 Hôtel Alpes ge Piscine
pi U Pinzutu 10 Gîte Corse ge Piscine
ta Tabriz 34 Hôtel Bretagne ge Piscine
ca Causses 45 Auberge Cévennes ge Ski
ge Génépi 134 Hôtel Alpes ge Ski
pi U Pinzutu 10 Gîte Corse ge Ski
ta Tabriz 34 Hôtel Bretagne ge Ski
ca Causses 45 Auberge Cévennes pi Plongée
ge Génépi 134 Hôtel Alpes pi Plongée
pi U Pinzutu 10 Gîte Corse pi Plongée
ta Tabriz 34 Hôtel Bretagne pi Plongée
ca Causses 45 Auberge Cévennes pi Voile
ge Génépi 134 Hôtel Alpes pi Voile
pi U Pinzutu 10 Gîte Corse pi Voile
ta Tabriz 34 Hôtel Bretagne pi Voile

C'est une relation (tout est relation en relationnel) et on peut bien imaginer interroger cette relation comme n'importe quelle autre. C'est exactement ce que fait la requête SQL suivante.

select * 
from Logement cross join Activité

Jusqu'à présent, le from ne contenait que des relations "basées" (c'est-à-dire stockées dans la base). Maintenant, on a placé une relation calculée. Le principe reste le même. Rappelons que l'algèbre est un langage clos : il s'applique à des relations et produit une relation en sortie. Il est donc possible d'appliquer à nouveau des opérateurs à cette relation-résultat. C'est ainsi que l'on construit des expressions, comme nous allons le voir dans la session suivante. Nous retrouverons une autre application de cette propriété extrêmement utile quand nous étudierons les vues (chapitre Schémas relationnels).

Renommage

Quand les schémas des relations \(R\) et \(S\) sont complètement distincts, il n'y a pas d'ambiguïté sur la provenance des colonnes dans le résultat. Par exemple on sait que les valeurs de la colonne \(A\) dans \(R \times S\) viennent de la relation \(R\). Il peut arriver (il arrive de fait très souvent) que les deux relations aient des attributs qui ont le même nom. On doit alors se donner les moyens de distinguer l'origine des colonnes dans la relation résultat en donnant un nom distinct à chaque attribut.

Voici par exemple une relation \(T\) qui a les mêmes noms d'attributs que \(R\).

A B
m n
o p

Le schéma du résultat du produit cartésien \(R \times T\) a pour schéma \((A, B, A, B)\) et présente donc des ambiguïtés, avec les colonnes \(A\) et [B]{.title-ref} en double.

La première solution pour lever l'ambiguïté est d'adopter une convention par laquelle chaque attribut est préfixé par le nom de la relation d'où il provient. Le résultat de \(R \times T\) devient alors :

R.A R.B T.A T.B
a b m n
a b o p
x y m n
x y o p

Cette convention pose quelques problèmes quand on crée des expressions complexes. Il existe une seconde possibilité, plus générale, pour résoudre les conflits de noms : le renommage. Il s'agit d'un opérateur particulier, dénoté \(\rho\), qui permet de renommer un ou plusieurs attributs d'une relation. L'expression \(\rho_{A \to C,B \to D}(T)\) permet ainsi de renommer \(A\) en \(C\) et \(B\) en \(D\) dans la relation \(T\). Le produit cartésien

\[R \times \rho_{A\to C,B \to D}(T)\]

ne présente alors plus d'ambiguïtés. Le renommage est une solution très générale, mais assez lourde à utiliser

Il est tout à fait possible de faire le produit cartésien d'une relation avec elle-même. Dans ce cas le renommage où l'utilisation d'un préfixe distinctif est impératif. Voici par exemple le résultat de \(R \times R\), dans lequel on préfixe par \(R1\) et \(R2\) respectivement les attributs venant de chacune des opérandes.

R1.A R1.B R1.A R2.B
a b a b
a b x y
x y a b
x y x y

En SQL, le renommage est obtenu avec le mot-clé as. Il peut s'appliquer soit à la relation, soit aux attributs (ou bien même aux deux). Le résultat suivant est donc obtenu avec la requête :

select *
from R as R1 cross join R as R2

On obtient une relation de schéma (R1.A, R1.B, R1.A, R2.B), avec des noms d'attribut qui ne sont en principe pas acceptés par la norme SQL. Il reste à spécifier ces noms en ajoutant dans as dans la clause de projection.

select R1.a as premier_a, R1.b as premier_b, R2.a as second_a, R2.b as second_b
from R as R1 cross R as R2

Ce qui donnera donc le résultat :

premier_a premier_b second_a second_b
a b a b
a b x y
x y a b
x y x y

Sur notre schéma, le renommage s'impose par exemple si on effectue le produit cartésien entre Voyageur et Séjour car l'attribut idVoyageur apparaît dans les deux tables. Essayez la requête :

select Voyageur.idVoyageur, Séjour.idVoyageur
from Voyageur cross join Séjour

Elle vous renverra une erreur comme Encountered duplicate field name: 'idVoyageur'. Il faut nommer explicitement les attributs pour lever l'ambiguïté.

select Voyageur.idVoyageur as idV1, Séjour.idVoyageur as idV2
from Voyageur cross join Séjour

L'union, \(\cup\)

Il existe deux autres opérateurs binaires, qui sont à la fois plus simples et moins fréquemment utilisés.

Le premier est l'union. L'expression \(R \cup S\) crée une relation comprenant tous les nuplets existant dans l'une ou l'autre des relations \(R\) et \(S\). Il existe une condition impérative : les deux relations doivent avoir le même schéma, c'est-à-dire même nombre d'attributs, mêmes noms et mêmes types.

L'union des relations \(R(A,B)\) et \(S(C,D)\) données en exemple ci-dessus est donc interdite (on ne saurait pas comment nommer les attributs dans le résultat). En revanche, en posant \(S' = \rho_{C\to A,D\to B}(S)\), il devient possible de calculer \(R \cup S'\), avec le résultat suivant :

A B
a b
x y
c d
u v

Comme pour la projection, il faut penser à éviter les doublons. Donc le nuplet (x,y) qui existe à la fois dans \(R\) et dans \(S'\) ne figure qu'une seule fois dans le résultat.

L'union est un des opérateurs qui existe dans SQL depuis l'origine. La requête suivante effectue l'union des lieux de la table Logement et des régions de la table Voyageur. Pour unifier les schémas, on a projeté sur cet unique attribut, et on a effectué un renommage.

select lieu from Logement
  union
select région as lieu from Voyageur

On obtient le résultat suivant.

lieu
Cévennes
Alpes
Corse
Bretagne
Auvergne
Tibet

Notez que certains noms comme "Corse" apparaîssent deux fois : vous savez maintenant comment éliminer les doublons avec SQL.

La différence, \(-\)

Comme l'union, la différence s'applique à deux relations qui ont le même schéma. L'expression \(R -S\) a alors pour résultat tous les nuplets de \(R\) qui ne sont pas dans \(S\).

Voici la différence de \(R\) et \(S'\), les deux relations étant définies comme précédemment.

A B
a b

En SQL, la différence est obtenue avec except.

select A, B from R
   except 
select C as A, D as B from S

La différence est le seul opérateur algébrique qui permet d'exprimer des requêtes comportant une négation (on veut "rejeter" quelque chose, on "ne veut pas" des nuplets ayant telle propriété). La contrainte d'identité des schémas rend cet opérateur très peu pratique à utiliser, et on lui préfère le plus souvent la construction logique du SQL "déclaratif", not exists.

Note

L'opérateur except n'est même pas proposé par certains systèmes comme MYSQL.