Skip to content

1 4 4 3 Ex Alg

SQL, langage algébrique ¾ : Expressions algébriques

Supports complémentaires

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.

Note
Les expressions sont seulement données dans la forme concise de l'algèbre. La syntaxe SQL équivalente est à faire à titre d'exercices (et à tester sur notre site).

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 nuplets satisfaisant un critère de sélection, par exemple : "les logements de type 'Hôtel'". Maintenant supposons que l'on veuille retrouver les hôtels dont la capacité est supérieure à 100. On peut exprimer cette requête par une composition :

\[\sigma_{capacité>100}(\sigma_{type='Hôtel'}(Logement))\]

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_{capacité>100 \land type='Hôtel'}(Logement)\]

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 logements qui sont en Corse, ou dont la capacité est supérieure à 100.

\[\sigma_{capacité>100}(Logement) \cup \sigma_{lieu='Corse'}(Logement)\]

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

\[\sigma_{capacité>100\ \lor\ lieu='Corse'}(Logement)\]

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

\[\sigma_{capacité>100}(Logement) - \sigma_{lieu='Corse'}(Logement)\]

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

\[\sigma_{capacité>100 \land lieu \not='Corse'}(Logement)\]

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, l'exemple précédent étant une exception. 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 logements en Corse :

    \(\pi_{nom}(\sigma_{lieu='Corse'}(Logement))\)

  • Code des logements où l'on pratique la voile.

    \(\pi_{codeLogement}(\sigma_{codeActivité='Voile'}(Activité))\)

  • Nom et prénom des clients corses

    \(\pi_{nom,prénom}(\sigma_{région='Corse'}(Voyageur))\)

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 relations. 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 le lieu des logements où l'on pratique la voile". Une analyse très simple suffit pour constater que l'on a besoin des attributs lieu et nom qui apparaîssent dans la relation Logement, et de codeActivité qui apparaît dans Activité.

Donc il faut faire une jointure, de manière à rapprocher les nuplets de Logement 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 Logement et Activité. Elle s'effectue donc par appariement de la clé primaire d'une part (dans Logement), de la clé étrangère d'autre part.

\[\pi_{nom,lieu}(Logement \Join_{code=codeLogement} (\sigma_{codeActivité='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é étrangère 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 un logement et ses activités, ou un logement et ses clients), mais qui ont été réparties dans plusieurs relations au moment de la conception de la base. Voir le chapitre Conception d’une base de données à ce sujet.

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

  • Nom des clients qui sont allés à Tabriz (en supposant connu le code, ta, de cet hôtel) :

    \[\pi_{nom} (\text{Voyageur} \Join_{idVoyageur=idVoyageur} \sigma_{codeLogement='ta'} (\text{Séjour}))\]
  • Quels lieux a visité le client 30 :

    \[\pi_{lieu} (\sigma_{idVoyageur=30} (\text{Séjour}) \Join_{codeLogement=code} (\text{Logement}))\]
  • Nom des clients qui ont eu l'occasion de faire de la voile :

    \[\pi_{nom} (\texttt{Voyageur} \Join_{idVoyageur=idVoyageur} (\texttt{Séjour} \Join_{codeLogement=codeLogement} \sigma_{codeActivité='Voile'}(\texttt{Activité})))\]

Note
Pour simplifier un peu l'expression, on a considéré ci-dessus que l'ambiguité sur l'attribut de jointure idVoyageur était effacée par la projection finale sur nom. En toute rigueur, la relation obtenue par

$$\texttt{Voyageur} \Join_{idVoyageur=idVoyageur} (\texttt{Séjour} \Join_{codeLogement=codeLogement} \sigma_{codeActivité='Voile'}(\texttt{Activité}))$$

comporte des noms d'attributs doublés auxquels il faudrait
appliquer un renommage.

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 lieu de résidence, ainsi que le nom de ce lieu.

Ici on a besoin des informations réparties dans les relations Logement, Séjour et Voyageur. Voici l'expression algébrique :

\[\pi_{nom, lieu} (\text{Voyageur} \Join_{idVoyageur=idVoyageur \land région=lieu} (\text{Séjour} \Join_{codeLogement=code} \text{Logement}))\]

Les jointures avec la relation 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 lieu de Voyageur et de Logement.

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.

Illustration concrète sur la base de données avec la requête suivante : quels sont les codes des logements qui ne proposent pas de voile ?

\[\pi_{code}(\text{Logement}) - \pi_{codeLogement}(\sigma_{codeActivité='Voile'}(\text{Activité}))\]

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 \(O\) qui satisfont \(p\).
  • Finalement, faire \(A - B\).

Les requêtes \(A\) et \(B\) peuvent bien entendu être arbitrairement complexes et mettre en œuvre 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 (et, en théorie, les mêmes noms, mais on peut s'affranchir de cette contrainte).

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

\[\pi_{codeLogement}(\sigma_{codeActivité\ \not=\ 'Voile'}(\text{Activité}))\]

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

Voici quelques exemples complémentaires qui illustrent ce principe.

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

    \[\pi_{région} (\text{Voyageur}) - \pi_{région}(\rho_{lieu \to région} (\text{Logement}))\]
  • Identifiant des logements qui n'ont pas reçu de client tibétain.

    \[\pi_{code}(\text{Logement}) - \pi_{codeLogement} (\text{Séjour} \Join_{idVoyageur=idVoyageur} \sigma_{région='Tibet'} (\text{Voyageur}))\]
  • Id des clients qui ne sont pas allés en Corse.

    \[\pi_{idVoyageur}(\text{Voyageur}) - \pi_{idVoyageur}(\sigma_{lieu='Corse'}(\text{Logement}) \Join_{code=codeLogement} \text{Séjour})\]

La dernière requête construit l'ensemble des idVoyageur pour les clients qui ne sont pas allés en Corse. 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 logements où ils ne sont pas allés. En d'autres termes, parmi toutes les associations Voyageur/Logement 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_{idVoyageur}(\text{Voyageur}) \times \pi_{code}(\text{Logement})) - \pi_{idVoyageur, codeLogement} (\text{Séjour})\]

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 : quels sont les clients dont tous les séjours ont eu lieu en Corse? On l'exprime également par 'quels sont clients pour lesquels il n'existe pas de séjour dans un lieu qui soit différent de la Corse'. Ce qui donne l'expression suivante :

\[\pi_{idVoyageur} (\text{Séjour}) - \pi_{idVoyageur}(\sigma_{lieu \not='Corse'}(\text{Séjour}))\]

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 tous les logements.

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

\[\pi_{idVoyageur}(\text{Voyageur}) - \pi_{idVoyageur} ((\pi_{idVoyageur}(\text{Voyageur}) \times \pi_{code}(\text{Logement})) - \pi_{idVoyageur, idLogement} (\text{Séjour}))\]

Explication: on réutilise l'expression donnant les clients et les logements où ils ne sont pas allés (voir plus haut) :

\[\pi_{idVoyageur}(\text{Voyageur}) \times \pi_{code}(\text{Logement})) - \pi_{idVoyageur, idLogement} (\text{Séjour})\]

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

\[\pi_{idVoyageur}(\text{Voyageur}) - 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.