L’algèbre relationnelle

Le premier 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 de la relation, effectuer des produits cartésiens ou des projections, etc.

Une propriété fondamentale de chaque opération est qu’elle 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érations : 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 des manipulations sur un grand nombre de relations à l’aide d’un petit nombre d’opérations de base.

Une requête est une expression algébrique qui s’applique à un ensemble de relations (la base de données) et produit une relation finale (le résultat de la requête). 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. Les requêtes du langage SQL peuvent se transposer en expressions algébriques, ce qui nous donnera un moyen d’interpréter leur signification d’une part, et de comprendre comment les exécuter d’autre part.

Dans tout ce chapitre on va prendre l’exemple de la (petite) base de données d’un organisme de voyage. Cet organisme propose des séjours (sportifs, culturels, etc) se déroulant dans des stations de vacances. Chaque station propose un ensemble d’activités (ski, voile, tourisme). Enfin on maintient une liste des clients et des séjours auxquels ils ont participé avec leurs semaines de début et de fin.

Voici le schéma de la base. Les clés primaires sont en gras, les clés étrangères en italiques.

  • Station (id, nom, capacité, lieu, région, tarif)
  • Activité (idStation, libellé, prix)
  • Client (id, nom, prénom, ville, région, solde)
  • Séjour (id, idClient, idStation, début, fin, nbPlaces)

La table Station

Voici le contenu de la table Station. La clé est un code synthétisant le nom de la station.

id nom capacité lieu région tarif
va Venusa 350 Guadeloupe Antilles 1200
fa Farniente 200 Seychelles Océan Indien 1500
sa Santalba 150 Martinique Antilles 2000
pa Passac 400 Alpes Europe 1000

La table Activité

Cette table contient les activités proposées par les stations. La clé est la paire consituée de (idStation, libellé).

idStation libellé prix
va Voile 150
va Plongée 120
fa Plongée 130
pa Ski 200
pa Piscine 20

La table des clients

Les clients sont identifiés par un numéro séquentiel incrémenté de 10 en 10.

id nom prénom ville région solde
10 Fogg Phileas Londres Europe 12465
20 Pascal Blaise Paris Europe 6763
30 Kerouac Jack New York Amérique 9812

La table des séjours

Les séjours sont identifiés par un numéro séquentiel incrémenté par unités. Le début et la fin sont des numéros de semaine dans l’année.

id idClient idStation début fin nbPlaces
1 10 Passac 20 20 2
2 30 Santalba 21 21 5
3 20 Santalba 21 22 4
4 30 Passac 2 3 3
5 30 Venusa 19 23 3
6 20 Venusa 23 23 6
7 30 Farniente 22 24 5
8 10 Farniente 23 25 3

Nous allons découvrir comme appliquer des opérations de l’algèbre aux relations de cette base, afin de construire une nouvelle relation. Exprimer une requête, c’est simplement construire une expression combinant plusieurs opérations afin d’obtenir une relation représentant le résultat cherché.

Les opérateurs de l’algèbre

L’algèbre se compose d’un ensemble d’opérateurs, parmi lesquels 5 sont nécessaires et suffisants et permettent de définir les autres par composition. Ce sont :

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

Les deux 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.

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

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 toutes les stations aux Antilles.

\[\sigma_{region='Antilles'}(Station)\]

On obtient donc le résultat :

id nom capacité lieu région tarif
va Venusa 350 Guadeloupe Antilles 1200
sa Santalba 150 Martinique Antilles 2000

La sélection a pour effet de supprimer des lignes, mais chaque ligne garde l’ensemble de ses attributs.

La projection, \(\pi\)

La projection \(\pi_{A_1, A_2, \ldots,A_k}(R)\) s’applique à une relation \(R\), et construit une relation contenant toutes les lignes de \(R\), dans lesquelles seuls les attributs \(A_1, A_2, \ldots A_k\) sont conservés. Donc, contrairement à la sélection, on ne supprime pas des lignes mais des colonnes. Par exemple : on veut le nom des stations, et leur région.

\[\pi_{nom, region}(Station)\]

On obtient le résultat suivant, après suppression des colonnes capacité, lieu et tarif} :

nom région
Venusa Antilles
Farniente Océan Indien
Santalba Antilles
Passac Europe

On pourrait s’attendre à ce que le nombre de lignes dans le résultat soit le même que dans la relation initiale. C’est presque le cas, avec cependant une petite subtilité. Comme le résultat est une relation, il ne peut pas y avoir deux lignes identiques (il n’y a pas deux fois le même élément dans un ensemble). Il peut arriver qu’après une projection, deux lignes qui étaient distinctes initialement se retrouvent identiques, justement parce ce que l’attribut qui permettait de les distinguer a été supprimé. Dans ce cas on ne conserve qu’une seule des deux (ou plus) lignes identiques.

Exemple : on souhaite connaître toutes les régions où il y a des stations. On exprime cette requête par :

\[\pi_{region}(Station)\]

et on obtient :

région
Antilles
Océan Indien
Europe

La ligne ‘Antilles’ était présente deux fois dans la relation Station, et n’apparaît plus qu’en un seul exemplaire dans le résultat.

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 lignes dans le résultat est exactement \(|R| \times |S|\) (\(|R|\) dénote le nombre de lignes 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 ligne de \(R\) à chaque ligne 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.

Renommage

Quand les schémas des relations \(R\) et \(S\) sont complètement distincts, il n’y a pas d’ambiguité 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 table résultat en donnant un nom distinct à chaque attribut.

Voici par exemple une table \(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 ambiguités, avec les colonnes \(A\) et B en double.

La première solution pour lever l’ambiguité est d’adopter une convention par laquelle chaque attribut est préfixé par le nom de la table 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 n p
x y m n
x y n p

Cette convention pose quelques problèmes quand on crée des expressions complexes. Il existe une seconde possibilité, plus rigoureuse, 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’ambiguités. Le renommage est une solution très générale, mais asez 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

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.

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

La différence est le seul opérateur qui permet d’exprimer des requêtes comportant une négation (on veut “rejeter” quelque chose, on “ne veut pas” des lignes ayant telle propriété). Il s’agit d’une fonctionnalité importante et difficile à manier : elle sera détaillée plus loin.

Jointure, \(\Join\)

Toutes les requêtes exprimables avec l’algèbre relationnelle peuvent se construire avec les 5 opérateurs présentés ci-dessus. En principe, on pourrait donc s’en contenter. En pratique, il existe d’autres opérations, très couramment utilisées, qui peuvent se contruire par composition des opérations de base. La plus importante est la jointure.

Afin de comprendre l’intérêt de cet opérateur, regardons le produit cartésien \(\rm{Station} \times \rm{Activité}\).

id nom capacité lieu région tarif idStation libellé prix
va Venusa 350 Guadeloupe Antilles 1200 va Voile 150
va Venusa 350 Guadeloupe Antilles 1200 va Plongée 120
va Venusa 350 Guadeloupe Antilles 1200 fa Plongée 130
va Venusa 350 Guadeloupe Antilles 1200 pa Ski 200
va Venusa 350 Guadeloupe Antilles 1200 pa Piscine 20
fa Farniente 200 Seychelles Océan Indien 1500 va Voile 150
fa Farniente 200 Seychelles Océan Indien 1500 va Plongée 120
fa Farniente 200 Seychelles Océan Indien 1500 fa Plongée 130
fa Farniente 200 Seychelles Océan Indien 1500 pa Ski 200
fa Farniente 200 Seychelles Océan Indien 1500 pa Piscine 20
sa Santalba 150 Martinique Antilles 2000 va Voile 150
sa Santalba 150 Martinique Antilles 2000 va Plongée 120
sa Santalba 150 Martinique Antilles 2000 fa Plongée 130
sa Santalba 150 Martinique Antilles 2000 pa Ski 200
sa Santalba 150 Martinique Antilles 2000 pa Piscine 20
pa Passac 400 Alpes Europe 1000 va Voile 150
pa Passac 400 Alpes Europe 1000 va Plongée 120
pa Passac 400 Alpes Europe 1000 fa Plongée 130
pa Passac 400 Alpes Europe 1000 pa Ski 200
pa Passac 400 Alpes Europe 1000 pa Piscine 20

Le résultat comprend manifestement un grand nombre de lignes qui ne nous intéressent pas. Cela ne présente pas beaucoup de sens de rapprocher des informations sur Santalba, aux Antilles et sur l’activité de ski à Passac.

Si, en revanche, on considère le produit cartésien comme un résultat intermédiaire, on voit qu’il permet de se ramener au cas on on effectue, par une simple sélection, des rapprochements de lignes distinctes. Sur notre exemple, en considérant la table ci-dessus comme une table de la base, on rapproche les informations générales sur une station et la liste des activités de cette station.

La sélection qui effectue une rapprochement pertinent est la suivante :

\[\sigma_{id=idStation}(\rm{Station} \times \rm{Activité})\]

Prenez bien le temps de méditer cette opération de sélection: nous ne voulons conserver que les lignes de \(\rm{Station} \times \rm{Activité}\) pour lesquelles l’identifiant de la station (provenant de Station) est identique à celui provenant de Activité. En regardant le produit cartésien ci-dessous, vous devriez pouvoir vous convaincre que cela revient à conserver les lignes qui ont un sens: chacune contient des informations sur une station et sur une activité dans cette même station. Si vous saisissez cette logique, vous avez fait un grand pas dans la connaissance des bases relationelles: consacrez-y le temps de réflexion nécessaire.

On obtient le résultat ci-dessous.

id nom capacité lieu région tarif idStation libellé prix
va Venusa 350 Guadeloupe Antilles 1200 va Voile 150
va Venusa 350 Guadeloupe Antilles 1200 va Plongée 120
fa Farniente 200 Seychelles Océan Indien 1500 fa Plongée 130
pa Passac 400 Alpes Europe 1000 pa Ski 200
pa Passac 400 Alpes Europe 1000 pa Piscine 20

On a donc effectué une composition de deux opérations (un produit cartésien, une sélection) afin de rapprocher des informations réparties dans plusieurs tables, mais ayant des liens entre elles (toutes les informations dans un nuplet du résultat sont relatives à une seule station). Cette opération est une jointure, que l’on peut directement, et simplement, noter :

\[\rm{Station} \Join_{id=idStation} \rm{Activité}\]

La jointure consiste donc à rapprocher les lignes de deux relations pour lesquelles les valeurs d’un (ou plusieurs) attributs sont identiques. De fait, dans la plupart des cas, ces attributs communs sont (1) la clé primaire de l’une des relations et (2) la clé étrangère dans l’autre relation. Dans l’exemple ci-dessus, c’est le cas pour id (clé primaire de Station) et idStation (clé étrangère dans Activité). La jointure permet alors de reconstruire l’association conceptuelle entre Station et Activité.

Note

La station Santalba, qui ne propose pas d’activité, n’apparaît pas dans le résultat de la jointure. C’est normal et conforme à la définition que nous avons donnée, mais peut parfois apparaître comme une contrainte. Nous verrons que SQL propose une variante, la jointure externe, qui permet de la contourner.

La notation de la jointure, \(R \Join_F S\), est un racourci pour \(\sigma_F(R \times S)\). Le critère de rapprochement, \(F\), peut être n’importe quelle opération de comparaison liant un attribut de \(R\) à un attribut de \(S\). En pratique, on emploie peu les \(\not=\) ou ‘<‘ qui sont difficiles à interpréter, et on effectue des égalités.

Note

Si on n’exprime pas de critère de rapprochement, la jointure est équivalente à un produit cartésien.

Il faut être attentif aux ambiguités dans le nommage des attributs qui peut survenir dans la jointure au même titre que dans le produit cartésien. Les solutions à employer sont les mêmes : on préfixe par le nom de la relation ou par un synonyme clair, ou bien on renomme des attributs avant d’effectuer la jointure.

Expression de requêtes avec l’algèbre

Cette section est consacrée à l’expression de requêtes algébriques complexes impliquant plusieurs opérateurs. On utilise la composition des opérations, rendue possible par le fait que tout opérateur produit en sortie une relation sur laquelle on peut appliquer à nouveau des opérateurs.

Sélection généralisée

Regardons d’abord comment on peut généraliser les critères de sélection de l’opérateur \(\sigma\). Jusqu’à présent on a vu comment sélectionner des lignes satisfaisant un critère de sélection, par exemple : “les stations aux Antilles”. Maintenant supposons que l’on veuille retrouver les stations qui sont aux Antilles et dont la capacité est supérieure à 200. On peut exprimer cette requête par une composition :

\[\sigma_{capacite>200}(\sigma_{region='Antilles'}(Station))\]

Ce qui revient à pouvoir exprimer une sélection avec une conjonction de critères. La requête précédente est donc équivalente à celle ci-dessous, où le \(\land\) dénote le ‘et’.

\[\sigma_{capacite>200 \land region='Antilles'}(Station)\]

La composition de plusieurs sélections revient à exprimer une conjonction de critères de recherche. De même la composition de la sélection et de l’union permet d’exprimer la disjonction. Voici la requête qui recherche les stations qui sont aux Antilles, ou dont la capacité est supérieure à 200.

\[\sigma_{capacite>200}(Station) \cup \sigma_{region='Antilles'}(Station)\]

Ce qui permet de s’autoriser la syntaxe suivante, où le ‘\(\lor\)‘ dénote le ‘ou’.

\[\sigma_{capacite>200\ \lor\ region='Antilles'}(Station)\]

Enfin la différence permet d’exprimer la négation et “d’éliminer” des lignes. Par exemple, voici la requête qui sélectionne les stations dont la capacité est supérieure à 200 mais qui ne sont pas aux Antilles.

\[\sigma_{capacite>200}(Station) - \sigma_{region='Antilles'}(Station)\]

Cette requête est équivalente à une sélection où on s’autorise l’opérateur ‘\(\not=\)‘ :

\[\sigma_{capacite>200 \land region \not='Antilles'}(Station)\]

Important

Attention avec les requêtes comprenant une négation, dont l’interprétation est parfois subtile. D’une manière générale, l’utilisation du ‘\(\not=\)n’est pas équivalente à l’utilisation de la différence. Voir la prochaine section.

En résumé, les opérateurs d’union et de différence permettent de définir une sélection \(\sigma_F\) où le critère \(F\) est une expression booléenne quelconque. Attention cependant : si toute sélection avec un ‘ou’ peut s’exprimer par une union, l’inverse n’est pas vrai (exercice).

Requêtes conjonctives

Les requêtes dites conjonctives constituent l’essentiel des requêtes courantes. Intuitivement, il s’agit de toutes les recherches qui s’expriment avec des ‘et’, par opposition à celles qui impliquent des ‘ou’ ou des ‘not’. Dans l’algèbre, ces requêtes sont toutes celles qui peuvent s’écrire avec seulement trois opérateurs : \(\pi\), \(\sigma\), \(\times\) (et donc, indirectement, \(\Join\)).

Les plus simples sont celles où on n’utilise que \(\pi\) et \(\sigma\). En voici quelques exemples.

  • Nom des stations aux Antilles :

    \(\pi_{nom}(\sigma_{region='Antilles'}(Station))\)

  • Id des stations où l’on pratique la voile.

    \(\pi_{idStation}(\sigma_{libelle='Voile'}(Activite))\)

  • Nom et prénom des clients européens

    \(\pi_{nom,prenom}(\sigma_{region='Europe'}(Client))\)

Des requêtes légèrement plus complexes - et extrêmement utiles - sont celles qui impliquent la jointure. On doit utiliser la jointure dès que les attributs nécessaires pour évaluer une requête sont réparties dans au moins deux tables. Ces “attributs nécessaires” peuvent être :

  • Soit des attributs qui figurent dans le résultat ;
  • Soit des attributs sur lesquels on exprime un critère de sélection.

Considérons par exemple la requête suivante : “Donner le nom et la région des stations où l’on pratique la voile”. Une analyse très simple suffit pour constater que l’on a besoin des attributs région et nom qui apparaîssent dans la relation Station, et de libellé qui apparaît dans Activité.

Donc il faut faire une jointure, de manière à rapprocher les lignes de Station et de Activité. Il reste donc à déterminer le (ou les) attribut(s) sur lesquels se fait ce rapprochement. Ici, comme dans la plupart des cas, la jointure permet de “recalculer” l’association entre les relations Station et Activité. Elle s’effectue donc par appariement de la clé primaire d’une part (dans Station), de la clé étrangère d’autre part.

\[\pi_{nom,region}(Station \Join_{id=idStation} \sigma_{libelle='Voile'}(\text{Activité}))\]

En pratique, la grande majorité des opérations de jointure s’effectue sur des attributs qui sont clé primaire dans une relation, et clé secondaire dans l’autre. Il ne s’agit pas d’une règle absolue, mais elle résulte du fait que la jointure permet le plus souvent de reconstituer le lien entre des informations qui sont naturellement associées (comme une station et ses activités, ou une station et ses clients), mais qui ont été réparties dans plusieurs relations au moment de la modélisation logique de la base. Cette reconstitution s’appuie sur le mécanisme de clé étrangère qui a été étudié dans le chapitre consacré à la conception.

Voici quelques autres exemples qui illustrent cet état de fait :

  • Nom des clients qui sont allés à Passac :

    \(\pi_{nom} (Client \Join_{id=idClient} \sigma_{nom='Passac'} (\text{Séjour}))\)

  • Quelles régions a visité le client 30 :

    \(\pi_{region} (\sigma_{idClient=30} (Sejour) \Join_{idStation=id} (Station))\)

  • Nom des clients qui ont eu l’occasion de faire de la voile :

    \(\pi_{nom} (Client \Join_{id=idClient} (Sejour \Join_{idStation=idStation} \sigma_{libelle='Voile'}(Activite)))\)

La dernière requête comprend deux jointures, portant à chaque fois sur des clés primaires et/ou étrangères. Encore une fois ce sont les clés qui définissent les liens entre les relations, et elle servent donc naturellement de support à l’expression des requêtes.

Voici maintenant un exemple qui montre que cette règle n’est pas systématique. On veut exprimer la requête qui recherche les noms des clients qui sont partis en vacances dans leur région, ainsi que le nom de cette région.

Ici on a besoin des informations réparties dans les relations Station, Séjour et Client. Voici l’expression algébrique :

\[\pi_{nom, client.region} (Client \Join_{id=idClient \land region=region} (Sejour \Join_{idStation=id} Station))\]

Les jointures avec la table Séjour se font sur les couples (clé primaire, clé étrangère), mais on a en plus un critère de rapprochement relatif à l’attribut région de Client et de Station.

Note

Dans la projection finale, on utilise la notation client.region pour éviter toute ambiguité.

Requêtes avec \(\cup\) et \(-\)

Pour finir, voici quelques exemples de requêtes impliquant les deux opérateurs \(\cup\) et \(-\). Leur utilisation est moins fréquente, mais elle peut s’avérer absolument nécessaire puisque ni l’un ni l’autre ne peuvent s’exprimer à l’aide des trois opérateurs “conjonctifs” étudiés précédemment. En particulier, la différence permet d’exprimer toutes les requêtes où figure une négation : on veut sélectionner des données qui ne satisfont pas telle propriété, ou tous les “untels” sauf les ‘x’ et les ‘y’, etc.

Illlustration concrète sur la base de données avec la requête suivante : quelles sont les identifiants des stations qui ne proposent pas de voile ?

\[\pi_{id}(Station) - \pi_{idStation}(\sigma_{libelle='Voile'}(Activite))\]

Comme le suggère cet exemple, la démarche générale pour construire une requête du type “Tous les \(O\) qui ne satisfont pas la propriété \(p\)” est la suivante :

  • Construire une première requête \(A\) qui sélectionne tous les \(O\).
  • Construire une deuxième requête \(B `qui sélectionne tous les :math:`O\) qui satisfont :math:`p`.
  • Finalement, faire \(A - B\).

Les requêtes \(A\) et \(B\) peuvent bien entendu être arbitrairement complexes et mettre en oeuvre des jointures, des sélections, etc. La seule contrainte est que le résultat de \(A\) et de \(B\) comprenne le même nombre d’attributs.

Important

Attention à ne pas considérer que l’utilisation du comparateur \(\not=\) est équivalent à la différence. La requête suivante par exemple ne donne pas les stations qui ne proposent pas de voile

\[\pi_{idStation}(\sigma_{libelle\ \not=\ 'Voile'}(Activite))\]

Pas convaincu(e)? Réfléchissez un peu plus, faites le calcul concret. C’est l’un de pièges à éviter.

Voici quelques exemples complémentaires qui illustrent ce principe.

  • Régions où il y a des clients, mais pas de station.

    \[\pi_{region} (Client) - \pi_{region}(Station)\]
  • Identifiant des stations qui n’ont pas reçu de client américain.

    \[\pi_{id}(Station) - \pi_{idStation} (Sejour \Join_{idClient=id} \sigma_{region='Amerique'} (Client))\]
  • Id des clients qui ne sont pas allés aux Antilles.

    \[\pi_{idClient}(Client) - \pi_{idClient}(\sigma_{region='Antilles'}(Station) \Join_{id=idStation} Sejour)\]

La dernière requête construit l’ensemble des idClient pour les clients qui ne sont pas allés aux Antilles. Pour obtenir le nom de ces clients, il suffit d’ajouter une jointure (exercice).

Complément d’un ensemble

La différence peut être employée pour calculer le complément d’un ensemble. Prenons l’exemple suivant : on veut les ids des clients et les stations où ils ne sont pas allés. En d’autres termes, parmi toutes les associations Client/Station possibles, on veut justement celles qui ne sont pas représentées dans la base !

C’est un des rares cas où le produit cartésien seul est utile : il permet justement de constituer “toutes les associations possibles”. Il reste ensuite à en soustraire celles qui sont dans la base avec l’opérateur \(-\).

\[(\pi_{id}(Client) \times \pi_{id}(Station)) - \pi_{idClient, idStation} (Sejour)\]

Quantification universelle

Enfin la différence est nécessaire pour les requêtes qui font appel à la quantification universelle : celles où l’on demande par exemple qu’une propriété soit toujours vraie. A priori, on ne voit pas pourquoi la différence peut être utile dans de tels cas. Cela résulte simplement de l’équivalence suivante : une propriété est vraie pour tous les éléments d’un ensemble si et seulement si il n’existe pas un élément de cet ensemble pour lequel la propriété est fausse. La quantification universelle s’exprime par une double négation.

En pratique, on se ramène toujours à la seconde forme pour exprimer des requêtes. Prenons un exemple : quelles sont les stations dont toutes les activités ont un prix supérieur à 100 ? On l’exprime également par ‘quelles sont stations pour lesquelles il n’existe pas d’activité avec un prix inférieur à 100’. Ce qui donne l’expression suivante :

\[\pi_{id} (Station) - \pi_{idStation}(\sigma_{prix<100}(Activite))\]

Pour finir, voici une des requêtes les plus complexes, la division. L’énoncé (en français) est simple, mais l’expression algébrique ne l’est pas du tout. L’exemple est le suivant : on veut les ids des clients qui sont allés dans toutes les stations.

Traduit avec (double) négation, cela donne : les ids des clients tels qu’il n’existe pas de station où ils ne soient pas allés. Ce qui donne l’expression algébrique suivante :

\[\pi_{id}(Client) - \pi_{id} ((\pi_{id}(Client) \times \pi_{id}(Station)) - \pi_{idClient, idStation} (Sejour))\]

On réutilise l’expression donnant les clients et les stations où ils ne sont pas allés (voir plus haut) :

\[\pi_{id}(Client) \times \pi_{id}(Station)) - \pi_{idClient, idStation} (Sejour)\]

On obtient un ensemble \(B\). Il reste à prendre tous les clients, sauf ceux qui sont dans \(B\).

\[\pi_{id}(Client) - B\]

Ce type de requête est rare (heureusement) mais illustre la capacité de l’algèbre à exprimer par de simples manipulations ensemblistes des opérations complexes.