SQL, langage déclaratif

Il est courant en informatique de disposer de plusieurs langages pour résoudre un même problème. Ces langages ont leur propre syntaxe, mais surtout ils peuvent s’appuyer sur des approches de programmation très différentes. Vous avez peut-être rencontré des langages impératifs (le C), orientés-objet (Java, Python) ou fonctionnels (Camel, Erlang).

Certains langages sont plus appropriés à certaines tâches que d’autres. Il est plus facile de vérifier les propriétés d’un programme écrit en langage fonctionnel par exemple que d’un programme C. Si l’on s’en tient aux bases de données (et particulièrement pour les bases relationnelles), deux approches sont possibles: la première est déclarative et la seconde procédurale.

L’approche procédurale est assez familière: on dispose d’un ensemble d’opérations, et on décrit le calcul à effectuer par une séquence de ces opérations. Chaque opération élémentaire peut être très simple, mais la séquence à construire pour régler des problèmes complexes peut être longue et peu claire.

L’approche déclarative est beaucoup plus simple conceptuellement: elle consiste à décrire les propriétés du point d’arrivée (le résultat) en fonction de celles du point de départ (les données de la base, dans notre cas). La description de ces propriétés se fait classiquement par des formules logiques qui indiquent comment l’existence d’un fait \(f_1\) au départ implique l’existence d’un fait \(f_2\) à l’arrivée.

Cela peut paraître abstrait, et de fait ça l’est puisqu’aucun calcul n’est spécifié. On s’appuie simplement sur le fait que l’informatique sait effectuer des calculs spécifiés par des formules logiques (dans le cas particulier des bases de données en tout cas) apparemment indépendantes de tout processus calculatoire. Il se trouve que SQL est un langage déclaratif, et qu’il l’était même exclusivement dans sa version initiale.

Note

Il existe de très bonnes raisons pour privilégier le caractère déclaratif des langages de requêtes, liées à l’indépendance entre le niveau logique et le niveau physique donc nous avons déjà parlé, et à l’opportunité que cette indépendance laisse au SGBD pour déterminer la meilleure manière d’évaluer une requête. Cela n’est possible que si l’expression de cette requête est assez abstraite pour n’imposer aucun choix de calcul à priori.

Avec SQL, on ne dit rien sur la manière dont le résultat doit être calculé: c’est le problème du SGBD, qui sait d’ailleurs trouver la solution bien mieux que nous puisqu’on ne connaît pas l’organisation des données. On se contente avec SQL d’énoncer les propriétés de la relation de sortie en fonction des propriétés de la base en entrée. Pour bien utiliser SQL, et surtout bien comprendre la signification de ce que l’on exprimer, il faut donc maîtriser l’expression de formules logiques et connaitre les mécanismes d’inférences des valeurs de vérité.

On rencontre parfois l’argument que SQL est, à l’inverse d’un langage de programmation, accessible à un non-initié, car il est proche de la manière dont on exprimerait naturellement une recherche. Ce n’est vrai que si on sait formuler cette dernière de manière rigoureuse, et c’est exactement ce que nous allons apprendre dans ce chapitre.

SQL est-il totalement déclaratif?

Au fil des années et des normes successives, SQL s’est étendu pour incorporer un autre langage relationnel, l’algèbre, que nous étudierons dans le prochain chapitre. Est-ce à dire que la forme déclarative n’était pas suffisante? Non: tous ces ajouts sont redondants et auraient pu être omis sans affecter l’expressivité du langage.

On se retrouve à l’heure actuelle avec un langage très riche dans lequel on peut exprimer des requêtes de manière soit déclarative, soit procédurale, soit par un mélange des deux. Cela ne contribue pas forcément à la facilité d’apprentissage, et introduit une certaine confusion sur la portée de telle ou telle formulation, et sa possible équivalence avec une autre.

En présentant successivement les deux approches, et en montrant ensuite comment elles sont parfaitement équivalentes l’une à l’autre, ce cours a choisi de tenter de clarifier la situation.

S1: Un peu de logique

La logique est l’art de raisonner, autrement dit de construire des argumentations rigoureuses permettant d’induire ou déduire de nouveaux faits à partir de faits existants (ou considérés comme tels). La logique mathématique est la partie de la logique qui présente les règles de raisonnement de manière formelle. C’est une branche importante des mathématiques, qui s’est fortement développée au début du XXe siècle, et constitue un fondement majeur de la science informatique.

Commençons par effectuer un rappel des quelques éléments de logique formelle qui sont indispensables pour formuler et interpréter les requêtes SQL. Ce qui suit n’est qu’une très brève (et assez simplifiée) introduction au sujet: il faut recourir à des textes spécialisés si vous voulez aller plus loin. Pour une passionante introduction historico-scientifique, je vous recommande d’ailleurs la bande dessinée (mais oui) Logicomix, parue chez Vuivert en 2009.

Important

Ceux qui pensent maîtriser le sujet peuvent sauter cette session.

La partie la plus simple de la logique formelle est le calcul propositionnel, par lequel nous commençons. SQL est construit sur une forme plus élaborée, impliquant des prédicats, des collections et des quantificateurs, notions brièvement présentées ensuite dans une optique « bases de données ».

Le calcul propositionnel

Une proposition est un énoncé auquel on peut attacher une valeur de vérité: vrai (V) ou faux (F). Des énoncés comme « Ce livre parle d’informatique » ou « Cette musique est de Mozart » sont des propositions. Une question comme « Qui a écrit ce texte? » n’est pas une proposition.

Le calcul propositionnel décrit la manière dont on peut combiner des propositions pour former des formules (propositionnelles) et attacher des valeurs de vérité à ces formules. Les propositions peuvent être combinées grâce à des connecteurs logiques. Il en faut au moins deux, mais on en considère en général trois.

  • la conjonction, notée \(\land\)
  • la disjonction, notée \(\lor\)
  • la négation, notée \(\neg\)

On note classiquement les propositions par des lettres en minuscules, \(p\), \(q\), \(r\). La table ci-dessous donne les valeurs de vérités pour les formules obtenues à l’aide des trois connecteurs logiques, en fonction des valeurs de vérité de \(p\) et \(q\).

Tableau 1 Valeurs de vérité pour les connecteurs logiques
\(p\) \(q\) \(p \land q\) \(p \lor q\) \(\neg p\)
V V V V F
V F F V F
F V F V V
F F F F V

Les formules créées par connecteurs logiques à partir de propositions ont elles-mêmes des valeurs de vérité, et on peut les combiner à leur tour. Généralement, si \(F_1\) et \(F_2\) sont des formules, alors \(F_1 \land F_2\), \(F_1 \lor F_2\) et \(\neg F_1\) sont aussi des formules. On crée ainsi des arbres dont les feuilles sont des propositions et les nœuds internes des connecteurs.

Pour représenter l’arbre dans le codage de la formule, on utilise des parenthèses et on évite ainsi toute ambiguité. La formule \(p \land q\) peut ainsi être combinée à \(r\) selon la syntaxe.

\[(p \land q) \lor r\]

La valeur de vérité de la formule obtenue s’obtient par application récursive des règles du Tableau 1. Si, par exemple, \(p, q, r\) ont respectivement pour valeurs V, V et F, la formule ci-dessus s’interprète ainsi:

  • \((p \land q)\) vaut \((V \land V)\), donc V
  • \((p \land q) \lor r\) vaut \(V \lor r\), qui vaut \(V \lor F\), donc V

Deux formules sont équivalentes si elles ont les mêmes valeurs de vérité quelles que soient les valeurs initiales des propositions. Les équivalences les plus courantes sont très utiles à connaître. En notant \(F, F_1, F_2\) trois formules quelconques, on a:

  • \(\neg (\neg F)\) est équivalente à \(F\)
  • \(F_1 \land F_2\) est équivalente à \(F_2 \land F_1\) (commutativité)
  • \(F_1 \lor F_2\) est équivalente à \(F_2 \lor F_1\) (commutativité)
  • \(F \land (F_1 \land F_2)\) est équivalente à \((F\land F_2) \land F_1\) (associativité)
  • \(F \lor (F_1 \lor F_2)\) est équivalente à \((F\lor F_1) \lor F_2\) (associativité)
  • \(F \lor (F_1 \land F_2)\) est équivalente à \((F\lor F_1) \land (F \lor F_2)\) (distribution)
  • \(F \land (F_1 \lor F_2)\) est équivalente à \((F\land F_1) \lor (F \land F_2)\) (distribution)
  • \(\neg (F_1 \land F_2)\) est équivalente à \((\neg F_1) \lor (\neg F_2)\) (loi DeMorgan)
  • \(\neg (F_1 \lor F_2)\) est équivalente à \((\neg F_1) \land (\neg F_2)\) (loi DeMorgan)

Une tautologie est une formule qui est toujours vraie. La tautologie la plus évidente est

\[F \lor \neg F\]

Une contradiction est une formule qui est toujours fausse. La contradiction la plus évidente est

\[F \land \neg F\]

Vérifiez que ces notions sont claires pour vous: il est bien difficile d’écrire correctement du SQL si on ne les maîtrise pas.

Prédicats

Une faiblesse de la logique propositionnelle est qu’elle ne considère que des énoncés « bruts », non décomposables. Si je considère les énoncés « Mozart a composé Don Giovanni », « Mozart a composé Cosi fan tutte », et « Bach a composé la Messe en si », la logique propositionnelle ne permet pas de distinguer qu’ils déclarent le même type de propriété (le fait de composer une œuvre) liant des entités (Mozart, Bach, leurs œuvres). Il est impossible par exemple en calcul propositionnel d’identifier que deux des propositions parlent de la même entité, Mozart.

Les prédicats sont des extensions des propositions qui énoncent des propriétés liant des objets. Un prédicat est de la forme \(P (X_1, X_2, \cdots, X_n)\), avec \(n\geq 0\), \(P\) étant le nom du prédicat, et les \(X_i\) désignant les entités liés par la propriété. On peut ainsi définir un prédicat \(Compose(X, Y)\) énonçant une relation de type X a composé Y entre l’entité représentée par X et celle représentée par Y.

Avec un prédicat, il est possible de donner un ensemble d’énoncés ayant tous la même structure. Appelons ces énoncés des nuplets pour adopter une terminologie « bases de données » (un logicien parlera plutôt d’atôme, ou de fait). Les trois propositions précédentes deviennent donc les trois nuplets suivants:

Compose (Mozart, Don Giovanni)
Compose (Mozart, Cosi fan tutte)
Compose (Bach, Messe en si)

Cette fois, contrairement au langage propositionnel, on désigne explicitement les entités: compositeurs (dont Mozart, qui apparaît deux fois) et œuvres. On obtient une collection de nuplets qui remplacent avantageusement les propositions grâce à leur structure plus riche.

Il existe virtuellement une infinité de nuplets énoncables avec un prédicat. Certains sont faux, d’autres vrais. Comment les distingue-t-on? Tout dépend du contexte interprétatif.

Dans un contexte arithmétique par exemple, les précicats courants sont l’égalité, l’inégalité (stricte ou large) et leur négation. Le prédicat d’égalité s’applique à deux valeurs numériques et s’écrit \(=(x,y)\). L’interprétation de ces predicats est celle que nous connaissons « naturellement ». On sait par exemple que \(\geq(2, 1)\) est vrai, et que \(\geq(1, 2)\) est faux.

Quand on modélise le monde réel, les nuplets vrais doivent le plus souvent être énoncées explicitement comme, dans l’exemple ci-dessus, les compositeurs et leurs œuvres. Une base de données n’est rien d’autre que l’ensemble des nuplets considérés comme vrais pour des prédicats applicatifs, tous les autres étant considérés comme faux.

Un système pourra nous dire que le nuplet suivant est faux (il n’est pas dans la base):

Compose (Bach, Don Giovanni)

Alors que le nuplet suivant est vrai (il appartient à la base):

Compose (Mozart, Don Giovanni)

Un réponse Vrai/Faux n’est pas forcément très utile. Nous restons pour l’instant dans un système assez restreint où tous les nuplets font référence à des entités connues. De tels nuplets sont dits fermés. Mais on peut également manipuler des nuplets dits ouverts dans lesquels certains objets sont inconnus, et remplacés par des variables habituellement dénotés \(x, y, z\). On obtient un langage beaucoup plus puissant.

Dans le nuplet ouvert suivant, le nom du compositeur est remplacé par une variable.

\[Compose (x, \text{Don Giovanni})\]

Intuitivement, ce nuplet ouvert représente concisément tous les nuplets fermés exprimant qu’un musicien \(x\) a composé une œuvre intitulée Don Giovanni. En affectant à \(x\) toutes les valeurs possibles (une variable est supposée couvrir un domaine de valeurs), on énumère tous les nuplets de ce type. La plupart sont faux (ceux qui ne sont pas dans la base), certains sont vrais.

Interroger une base relationnelle, c’est simplement demander au système les valeurs de \(x\) pour lesquelles \(Compose (x, Don Giovanni)\) est vrai. La réponse est probablement Mozart.

Collections et quantificateurs

L’ensemble des nuplets vrais d’un prédicat constitue une collection. Jusqu’à présent nous avons évalué les valeurs de vérité au niveau de chaque nuplet individuel, mais on peut également le faire sur l’ensemble de la collection grâce aux quantificateurs existentiel et universel.

  • Le quantificateur existentiel. \(\exists x P(x)\) est vrai s’il existe au moins une valeur de \(x\) pour laquelle \(P(x)\) est vraie.
  • Le quantificateur universel. \(\forall x P(x)\) est vrai si \(P(x)\) est vraie pour toutes les valeurs de \(x\).

Note

Le quantificateur existentiel serait suffisant puisqu’il est possible d’exprimer la quantification universelle avec deux négations. Une propriété \(P\) est toujours vraie s’il n’existe pas de cas où est n’est pas vraie. SQL ne connaît d’ailleurs que le exists: voir plus loin.

On peut donc définir la forme complète des formules de la manière suivante:

Définition: Syntaxe des formules

  • Un nuplet (ouvert ou fermé) \(P(a_1, a_2, \cdots, a_n)\) est une formule
  • Si \(F_1\) et \(F_2\) sont deux formules, \(F_1 \land F_2\), \(F_1 \lor F_2\) et \(\neg F_1\) sont des formules.
  • Si \(F\) est une formule et si \(x\) est une variable, alors \(\exists x F\) et \(\forall x F\) sont des formules.

Les notions d“« ouvert » et de « fermé » se généralisent au niveau des formules: une formule est ouverte si elle contient des variables qui ne sont liées par aucun quantificateur. On les appelle les variables libres. Les formules ouvertes sont celles qui nous intéressent en base de données, car elles reviennent à poser la question suivante: quelles sont les valeurs des variables libres qui satisfont (rendent vraie) la formule?

Reprenons l’un des exemples précédents

\[Compose (x, \text{Don Giovanni})\]

Cette formule est ouverte, avec une seule variable libre; \(x\). Les valeurs qui satisfont cette formule sont les noms des compositeurs qui ont écrit Don Giovanni.

Voici une autre formule dans laquelle le second composant est une variable dite « anonyme », notée \(\_\).

\[Compose (x, \_)\]

Variable anonyme

Les variables anonymes sont celles dont la valeur ne nous intéresse pas et auxquelles on ne se donne donc même pas la peine de donner un nom. Ecrire un nuplet \(P(\_, x, \_, \_)\) est donc une facilité d’écriture pour ne pas avoir à nommer trois variables qui ne servent à rien. La notation complète serait de la forme \(P(x_1, x, x_2, x_3)\).

La seule variable libre est \(x\), et les valeurs de \(x\) qui satisfont la formule sont l’ensemble des noms de compositeur. De fait, une formule \(F\) avec des variables libres \(x_1, x_2, \cdots, x_n\) définit un prédicat \(R(x_1, x_2, \cdots, x_n)\). L’ensemble des nuplets vrais de \(R\) est l’ensemble des nuplets qui satisfont \(F\). Pour reprendre notre exemple, on pourrait définir le prédicat Compositeur de la manière suivante:

\[Compositeur(x) \leftarrow Compose (x, \_)\]

Ce qui se lit: « \(x\) est un compositeur s’il existe une valeur de \(y\) telle que \((x, y)\) est un nuplet vrai de Compose.

Un schéma de base de données peut être vu comme la déclaration d’un ensemble de prédicats. Reprenons un exemple déjà rencontré, celui des manuscrits évalués par des experts.

  • Expert (id_expert, nom)
  • Manuscrit (id_manuscrit, auteur, titre, id_expert, commentaire)

Ces prédicats énoncent des propriétés. Le premier nous dit que l’expert nommé nom a pour identifiant id_expert. Le second nous dit que le manuscrit identifié par id_manuscrit s’intitule titre, a été rédigé par auteur et évalué part l’expert identifié par id_expert qui a ajouté un commentaire.

Voici quelques formules sur ces prédicats. La première est vraie pour toutes les valeurs de \(x\) égales à l’identifiant d’un expert nommé Serge.

\[Expert (x, \text{'Serge'})\]

La seconde est vraie pour toutes les valeurs de \(t\) titre du manuscrit d’un auteur nommé Proust.

\[Manuscrit (\_, \text{'Proust'}, t, \_)\]

Enfin, la troisième est vraie pour toutes les valeurs de \(t\) , \(x\) et \(n\) telles que \(t\) est le titre du manuscrit d’un auteur nommé Proust, évalué par un expert identifié par \(x\) et nommé \(n\).

\[Manuscrit (\_, \text{'Proust'}, t, x, \_) \land Expert (x, n)\]

Notez que la variable \(x\) est utilisée à la fois dans Manuscrit et dans Expert. Cela contraint une valeur de \(x\) à être à la fois un identifiant d’un expert dans Expert, et la valeur de la clé étrangère de cet expert dans Manuscrit Autrement dit l’énoncé de cette formule lie un manuscrit à l’expert qui l’a évalué. Ce mécanisme de lien par partage de valeur, nommé jointure est fondamental dans l’interrogation de bases relationnelles; nous aurons l’occasion d’y revenir longuement.

Voici une dernière formule qui illustre l’utilisation des quantificateurs.

\[Expert (x, n) \land \exists Manuscrit (\_, \text{'Proust'}, \_, x, \_)\]

Cette formule s’énonce ainsi: tous les experts \(n\) qui ont évalué au moins un manuscrit d’un auteur nommé Proust. Notez encore une fois la présence de l’identifiant de l’expert dans les deux nuplets libres, sur Expert et Manuscrit.

Logique et bases de données

Ce qui précède peut sembler inutilement conceptuel ou compliqué, surtout au vu de la simplicité des exemples donnés jusqu’à présent. Il faut bien réaliser que ces exemples ne sont qu’une illustration d’une méthode d’interrogation très générale dans laquelle on demande au système de nous fournir, à partir des nuplets de la base (ceux considérés comme vrais), toutes les informations qui satisfont une propriété logique. Cette propriété s’exprime dans le langage de la logique formelle, ce qui offre des avantages décisifs:

  • la signification d’une formule et précise, non ambiguë;
  • il existe des algorithmes efficaces pour évaluer la valeur de vérité d’une formule;
  • le langage est robuste, universellement connu et adopté, ce qui permet d’obtenir un mode d’interrogation normalisé.
  • enfin, ce langage est totalement déclaratif: exprimer une formule ne donne aucune indication sur la manière dont le système doit trouver le résultat.

SQL, dans sa forme déclarative, qui est la forme d’origine, est un langage concret pour écrire des formules logiques que le SGBD se charge d’interpréter et de calculer. Reprenons la formule: .. math:

Compose (x, \text{Don Giovanni})

Voici la requête SQL correspondante.

select compositeur
from Compose
where oeuvre='Don Giovanni'

Et voici la forme SQL des deux dernières formules sur les experts (avec jointure)

select titre, nom
from Expert, Manuscrit
where Expert.id_expert = Manuscrit.id_expert
and titre = 'Proust'
select nom
from Expert
where exists (select *
             from Manuscrit
             where Expert.id_expert = Manuscrit.id_expert
             and titre = 'Proust')

Maîtriser l’expression des formules et, surtout, comprendre leur signification précisément, est donc une condition pour utiliser SQL correctement.

Quiz

Exercices

Exercice Ex-S1-1: un peu de réécriture

Il est possible de mettre toute formule en forme normale conjonctive (FNC) \((F_1) \land (F_2) \land \cdot \land F_n\). Utilisez les règles d’équivalence pour obtenir la FNC des formules suivantes

  • \(((a \land b) \lor (q \land r)) \lor z\)

Application: on vous demande de trouver les films qui satisfont les critères suivants: soit ils ont été tournés en France, soit ils ont été tournés en Espagne après 2010.

  • (pays = “France”) or (pays=”Espagne” et année > 2010)

Réécrivez cette expression en FNC.

Exercice Ex-S2-1: un peu de raisonnement

Un connecteur peu utilisé en base de données est l’implication, noté :math:to`. La table des valeurs de vérité de \(p \to q\) est la même que celle de \(\neg p \lor q\).

Donner cette table de vérité. Quelle est la valeur de vérité de \(p \to q\) si \(p\) et \(q\) sont faux? Et si \(p\) est faux et \(q\) est vrai? Un autre choix serait-il possible?

S2: SQL conjonctif

Cette session présente le langage SQL dans sa version déclarative, chaque requête s’interprétant par une formule logique. La base de données est constituée d’un ensemble de relations vues comme des prédicats. Ces relations contiennent des nuplets (fermés, sans variable).

Note

Prédicats ou relations ?

Un prédicat énonce une propriété liant des objets, et est donc synonyme de relation au sens mathématique du terme. Les deux termes peuvent être utilisés de manière interchangeable.

Pour illustrer les requêtes et leur interprétation, nous prenons la base des voyageurs présentée dans le chapitre Le modèle relationnel. Vous pouvez expérimenter toutes les requêtes présentées (et d’autres) directement sur note site http://deptfod.cnam.fr/bd/tp/tpsql.

Cette session se limite à la partie dite « conjonctive » de SQL, celle où toutes les requêtes peuvent s’exprimer sans négation. La prochaine session complètera le langage.

Requête mono-variable

Dans les requêtes relationnelles, les variables ne désignent par des valeurs individuelles, mais des nuplets libres. Une variable-nuplet \(t\) a donc des composants \(a_1, a_2, \dots a_n\) que l’on désigne par \(t.a_1, t.a_2, \cdots, t.a_n\). Par souci de simplicité, on nomme souvent les variables comme les attributs du schéma, mais ce n’est pas une obligation.

Commençons par étudier les requêtes utilisant une seule variable. Leur forme générale est

select [distinct] t.a1, t.a2, ..., t.an
from T as t
where <condition>

Ce « bloc » SQL comprend trois clauses: le from définit la variable libre et ce que nous appellerons la portée de cette variable, le where exprime les conditions sur la variable libre, enfin le select, accompagné du mot-clé optionnel distinct, construit le nuplet constituant le résultat. Cette requête correspond à la formule :

\[\{ t.a_1, t.a_2, \cdots, t.a_n | T(t) \land F_{cond}(t) \}\]

L’interprétation est la suivante: je veux constituer tous les nuplets fermés \((t.a_1, t.a_2, \cdots, t.a_n)\) dont les valeurs satisfont la formule \(T(t) \land F_{cond}\). Cette formule comprend toujours deux parties:

  • La première, \(T(t)\) indique que la variable \(t\) est un nuplet de la relation \(T\). Autrement dit \(T(t)\) est vraie si \(t \in T\). Nous appelons donc cette partie la portée dans ce qui suit.
  • La seconde, \(F_{cond}(t)\), est une formule logique sur \(t\), que nous appellons la condition.

Important

La portée définit les variables libres de la formule, celles pour lesquelles on va chercher l’affectation qui satisfait la condition \(F_{cond}(t)\), et à partir desquelles on va construire le nuplet-résultat. Reportez-vous à la session précédente pour la notion de variable libre dans une formule et leur rôle dans un système d’interrogation.

À propos du distinct

Une relation ne contient pas de doublon. La présence de doublons (deux unités d’information indistinguables l’une de l’autre) dans un système d’information est une anomalie. Pour prendre quelques exemples applicatifs, on ne veut pas envoyer deux fois le même message, on ne veut pas produire deux fois la même facture, on ne veut pas afficher deux fois le même document, etc. Vous pouvez vérifier que votre moteur de recherche préféré applique ce principe.

Les relations de la base sont en première forme normale, et la présence de doublons est évitée par la présence d’au moins une clé. Qu’en est-il du résultat des requêtes? Supposons que l’on souhaite connaître tous les types de logements. Voici la requête SQL sans distinct:

select type
from Logement

On obtient une relation avec deux nuplets identiques.

type
Gîte
Hôtel
Auberge
Hôtel

Sans distinct, SQL peut produire des relations avec doublons. Du point de vue logique, cela montre simplement que l’on a établi le même fait de deux manières différentes, mais cela ne sert à rien d’afficher ce fait deux fois (ou plus). Si on ajoute distinct

select distinct type
from Logement

on obtient

type
Gîte
Hôtel
Auberge

Pourquoi SQL n’élimine-t-il pas systématiquement les doublons. En premier lieu parce que cette élimination implique un algorithme potentiellement coûteux si la relation en entrée est très grande. Il faut en effet effectuer un tri du résultat suivi d’une élimination des nuplets identiques. Sur des petites relations, la différence en temps d’exécution est indiscernable, mais elle peut devenir significative quand on a des centaines de milliers de nuplets ou plus. Les concepteurs du langage SQL ont fait le choix, par défaut, d’éviter d’appliquer cet algorithme et donc de produire éventuellement des doublons.

Une seconde raison pour ne pas appliquer systématiquement l’algorithme d’élimination de doublons est que certaines requêtes, par construction, produisent un résultat sans doublons. Voici un exemple très simple

select code, type
from Logement

Inutile dans ces cas-là d’utiliser distinct (voyez-vous pourquoi?). En d’autres termes: SQL nous laisse la charge de décider quand une requête risque de produire des doublons, et si nous souhaitons les éliminer. Dans tout ce cours nous utilisons distinct chaque fois que c’est nécessaire pour toujours obtenir un résultat en première forme normale, sans doublon.

Comment savoir si une requête risque de produire des doublons?

C’est une bonne question. L’exemple donné ci-dessus nous donne une piste: il nous faut des dépendances fonctionnelles dans le résultat! Voir les exercices.

Il est par ailleurs très utile, quand on exprime une requête, de réfléchir à la possibilité qu’elle produise ou non des doublons et donc à la nécessité d’utiliser distinct. Si une requête produit potentiellement des doublons, il est sans doute pertinent de se demander quel est le sens du résultat obtenu.

Exemples

Voici une première requête concrète sur notre base. On veut le nom et le type des logements corses.

select t.code, t.nom, t.type
from Logement as t
where t.lieu = 'Corse'

Note

Pour distinguer les chaînes de caractères des noms d’attribut, on les encadre par des apostrophes simples.

Elle correspond à la formule:

\[\{ t.code, t.nom, t.type | Logement(t) \land t.lieu=\text{'Corse'} \}\]

Note

SQL permet, quand c’est possible, quelques légères simplifications syntaxiques. La forme simplfiée de la requête précédente est donnée ci-dessous.

select code, nom, type
from Logement
where lieu = 'Corse'

On peut donc omettre de spécifier le nom de la variable quand il n’y a pas d’ambiguité, notamment l’interprétation du nom des champs.

Elle s’interprète de la manière suivante: on cherche les affectations d’une variable \(t\) parmi les nuplets de la relation Logement, telle que t.lieu ait pour valeur « Corse ».

De cette interprétation, assez évidente pour l’instant, il faut retenir qu’une table mentionnée dans le from de SQL définit en fait une variable dont la portée est la table (ici, Logement). Parmi toutes les affectations possibles de cette variable, on ne conserve que celles qui satisfont la condition exprimée par le reste de la formule.

Le système d’évaluation peut donc considérer que \(t\) est affectée à n’importe lequel des nuplets de la table, et évaluer si cette affectation satisfait la condition. Dans la table ci-dessous, la croix indique à quel nuplet \(t\) est affectée. Ici, la condition n’est clairement pas satisfaite.

t code nom capacité type lieu
  pi U Pinzutu 10 Gîte Corse
  ta Tabriz 34 Hôtel Bretagne
X ca Causses 45 Auberge Cévennes
  ge Génépi 134 Hôtel Alpes

En revanche, quand l’affectation est faite comme indiquée ci-dessous, la condition est satisfaite. L’affectation de la variable \(t\) satisfait alors l’ensemble de la formule et sert à construire le nuplet-résultat.

t code nom capacité type lieu
X pi U Pinzutu 10 Gîte Corse
  ta Tabriz 34 Hôtel Bretagne
  ca Causses 45 Auberge Cévennes
  ge Génépi 134 Hôtel Alpes

À partir de là, il suffit de savoir exprimer une formule pour spécifier correctement une requête SQL.

Voici quelques exemples. Cherchons d’abord quels hôtels sont dans les Alpes. La requête SQL est:

select t.code, t.nom
from Logement as t
where t.type = 'Hôtel' and t.lieu = 'Alpes'

Elle correspond à la requête logique

\[\{ t.code, t.nom | Logement(t) \land t.type=\text{'Hôtel'} \land t.lieu=\text{'Alpes'}\}\]

La condition à satisfaire pour un nuplet de la relation Logement est \(t.type=\text{'Hôtel'} \land t.lieu=\text{'Alpes'}\). C’est seulement le cas pour le dernier nuplet. Cherchons maintenant les hôtels qui, soit sont en Bretagne, soit ont au moins 100 chambres. La version SQL:

select t.code, t.nom
from Logement as t
where t.type = 'Hôtel' and (t.lieu = 'Alpes' or t.capacité >= 100)

Et sa version logique:

\[\{ t.code, t.nom | Logement(t) \land t.type=\text{'Hôtel'} \land (t.lieu=\text{'Alpes'} \lor t.capacité \geq 100)\}\]

Requêtes multi-variables

Voypns maintenant le cas général où on s’autorise à utiliser plusieurs variables. Pour simplifier la notation, nous allons étudier les requêtes avec exactement deux variables. Il est facile ensuite de généraliser.

Leur forme est

\[\{ t_1.a^1_1, \cdots, t_1.a^1_n, t_2.a^2_1, \cdots, t_2.a^2_m | T_1(t_1) \land T_2(t_2) \land F_{cond}(t_1, t_2) \}\]

On retrouve dans la formule les deux parties: la portée indique les relations respectives qui servent de domaine d’affectation pour \(t_1\) et \(t_2\); la condition est une formule avec \(t_1\) et \(t_2\) comme variables libres.

La transcription en SQL est presque littérale.

select [distinct] t1.a1, ..., t1.an, t2.a1, ..., t2.am
from T1 as t1, T2 as t2
where <condition>

L’interprétation est exactement la même que pour les requêtes mono-variables, légèrement généralisée: parmi toutes les affectations possibles des variables, on ne conserve que celles qui satisfont la condition exprimée par le reste de la formule.

Il n’y a rien de plus à comprendre. Il suffit de considérer toutes les affectations possibles de \(t_1\) et \(t_2\) et de ne garder que celles pour lesquelles la formule de condition est satisfaite.

Voici quelques exemples. On veut les noms des logements où on peut pratiquer le ski. Nous avons besoin de deux variables:

  • la première s’affecte aux nuplets de la table Activité; on ne veut que ceux dont le code est Ski.
  • la seconde s’affecte aux nuplets de la table Logement

Enfin, une condition doit lier les deux variables: on veut qu’elles soient relatives au même logement, et donc que le code logement soit identique. Voici la formule, suivie de la requête SQL.

\[\{ l.code, l.nom | Logement(l) \land Activité(a) \land l.code = a.codeLogement \land a.codeActivité=\text{'Ski'} \}\]

Remarquons au passage que le nom que l’on donne aux variables n’a aucune importance. Nous utilisons l pour le logement, a pour l’activité.

select l.code, l.nom
from Logement as l, Activité as a
where l.code = a.codeLogement
and   a.codeActivité = 'Ski'

Les seules affectations de \(l\) et \(a\) satisfaisant la formule sont marquées par des croix dans les tables ci-dessous (les champs concernés ont de plus été mis en gras). Prenez, si nécessaire, le temps de bien comprendre que d’une part la formule de condition est bien satisfaite, et d’autre part qu’il n’y a pas d’autre solution possible.

l code nom capacité type lieu
  pi U Pinzutu 10 Gîte Corse
  ta Tabriz 34 Hôtel Bretagne
  ca Causses 45 Auberge Cévennes
X ge Génépi 134 Hôtel Alpes
a codeLogement codeActivité description
  pi Voile Pratique du dériveur et du catamaran
  pi Plongée Baptèmes et préparation des brevets
  ca Randonnée Sorties d’une journée en groupe
X ge Ski Sur piste uniquement
  ge Piscine Nage loisir non encadrée

A partir de ces deux affectations, on construit le résultat.

code nom
ge Génépi

Pour maîtriser cette partie de SQL (sans doute la plus couramment utilisée), il faut bien comprendre le mécanisme mis en œuvre. Pour construire un nuplet du résultat, nous avons besoin de 1, 2 ou plus nuplets provenant de la base. Il faut identifier ces nuplets, les conditions qu’ils doivent satisfaire, et les valeurs qu’ils partagent. Ici:

  • nous avons besoin d’un nuplet de la relation Activité, tel que le code soit Ski;
  • nous avons besoin d’un nuplet de la relation Logement, puisque nous souhaitons obtenir le nom du logement en sortie;
  • enfin ces nuplets doivent être relatif au même logement, et partager donc la même valeur sur l’attribut qui identifie ce logement, respectivement code dans Logement et codeLogement dans Activité.

Ce raisonnement est très général et permet d’exprimer des requêtes SQL puissantes. Les seules conditions sont de formuler rigoureusement la requête et de comprendre le schéma de la base.

Prenons un autre exemple montrant que l’on peut utiliser la même portée pour des variables différentes. On veut obtenir les paires de logements qui sont du même type. Puisqu’il nous faut deux logements, nous avons besoin de deux variables, ayant chacune pour portée la table Logement. Ces deux variables doivent partager la même valeur pour l’attribut type. Voici la formule:

\[\{ l_1.nom, l_2.nom | Logement(l_1) \land Logement(l_2) \land l_1.type = l_2.type \}\]

Les deux variables ont été nommées respectivement \(l_1\) et \(l_2\). La syntaxe SQL est donnée ci-dessous.

select distinct l1.nom as nom1, l2.nom as nom2
from Logement as l1, Logement as l2
where l1.type = l2.type

Note

Dans la syntaxe SQL, il faut résoudre les ambiguités éventuelles sur les noms d’attributs avec as. Ici, on a nommé le nom du premier logement nom1 et celui du second nom2 pour obtenir en sortie une relation de schéma (nom1, nom2).

Il existe plusieurs affectations de l1 et l2 pour lesquelles la formule est satisfaite. La première est donnée ci-dessous: l1 est affectée à la seconde ligne et l2 à la quatrième.

l1 l2 code nom capacité type lieu
    pi U Pinzutu 10 Gîte Corse
X   ta Tabriz 34 Hôtel Bretagne
    ca Causses 45 Auberge Cévennes
  X ge Génépi 134 Hôtel Alpes

Mais la formule est également satisfaite si on inverse les affectations: l1 est à la quatrième ligne et l2 à la seconde.

l1 l2 code nom capacité type lieu
    pi U Pinzutu 10 Gîte Corse
  X ta Tabriz 34 Hôtel Bretagne
    ca Causses 45 Auberge Cévennes
X   ge Génépi 134 Hôtel Alpes

Et, surprise, elle est également satisfaite si les deux variables sont affectées au même nuplet.

l1 l2 code nom capacité type lieu
X X pi U Pinzutu 10 Gîte Corse
    ta Tabriz 34 Hôtel Bretagne
    ca Causses 45 Auberge Cévennes
    ge Génépi 134 Hôtel Alpes

Pour éviter les inversions et auto-égalités, on peut ajouter une condition:

select distinct l1.nom as nom1, l2.nom as nom2
from Logement as l1, Logement as l2
where l1.type = l2.type
and l1.nom < l2.nom

Le résultat de cette requête est alors:

nom1 nom2
Génépi Tabriz

Interprétation d’une requête SQL

En résumé, quelle que soit sa complexité, l’interprétation d’une requête SQL peut toujours se faire de la manière suivante.

  • Chaque variable du from peut être affectée à tous les nuplets de sa portée.
  • Le where définit une condition sur ces variables: seules les affectations satisfaisant cette condition sont conservées
  • Le nuplet résultat est construit à partir de ces affectations

Remarquez que ce mode d’interrogation n’indique en aucune manière, même de très loin, comment le résultat est calculé. On est (pour insister) dans une approche purement déclarative où le système est totalement libre de déterminer la méthode la plus efficace.

Quiz

Exercices

S3: Quantificateurs et négation

Jusqu’à présent les seules variables que nous utilisons sont des variables libres de la formule, définies dans la clause from de la syntaxe SQL. Nous n’avons pas encore rencontré de variable liée parce que nous n’avons pas utilisé les quantificateurs.

SQL propose uniquement le quantificateur existentiel. Le quantificateur universel peut être obtenu en le combinant avec la négation. Rappelons que les quantificateurs servent à exprimer des conditions sur l’ensemble d’une relation (qui peut être une relation en base, ou une relation calculée). Ils sont particulièrement utiles pour les requêtes qui comportent des négations (« je ne veux pas des objets qui ont telle ou telle propriété dans mon résultat »).

Le quantificateur exists

Reprenons simplement la requête qui demande les logements où l’on peut faire du ski. La formule donnée précédemment est la suivante:

\[\{ l.nom | Logement(l) \land Activité(a) \land l.code = a.codeLogement \land a.codeActivité=\text{'Ski'} \}\]

On remarque que la variable libre \(a\) n’est pas utilisée dans la construction du nuplet-résultat (qui ne contient que `` l.nom``). On pourrait donc affecter le nuplet a à une variable liée, ce qui revient à formuler la requête légèrement différemment: « donnez-moi le nom des logements pour lesquels il existe une activité Ski ».

Ce qui donne la formule suivante:

\[\{ l.nom | Logement(l) \land \exists a (Activité(a) \land l.code = a.codeLogement \land a.codeActivité=\text{'Ski'})\}\]

On a introduit la sous-formule suivante:

\[\exists a (Activité(a) \land l.code = a.codeLogement \land a.codeActivité=\text{'Ski'})\]

Cette sous-formule est satisfaite dès que l’on a trouvé au moins un nuplet qui satisfait les conditions demandées, à savoir un code activité égal à Ski, et le même code logement que celui de la variable \(l\).

Qui dit sous-formule dit logiquement sous-requête en SQL. Voici la syntaxe:

select distinct l.nom
from Logement as l
where exists (select ''
              from Activité as a
              where l.code = a.codeLogement
              and a.codeActivité = 'Ski')

Le résultat est construit à partir du select de premier niveau, qui ne peut accéder qu’à la variable l, et pas à la variable (liée) a.

Note

La clause du select imbriquée ne sert donc absolument à rien d’autre qu’à respecter la syntaxe SQL, et on peut utiliser select '', select * ou n’importe quoi d’autre.

Cet exemple montre qu’il est possible d’exprimer une même requête avec des syntaxes différentes, que ce soit au niveau de la formulation en langage naturel ou de l’expression formelle (logique ou SQL).

Les quantificateurs permettent d’imbriquer des formules dans des formules, sans limitation de profondeur. En SQL, on peut de même avoir des imbrications de requêtes sans limitation. La lisibilité et la compréhension en sont quand même affectées.

Prenons une requête un peu plus complexe: je veux les noms des voyageurs qui sont allés dans les Alpes. Une première formulation, complètement « à plat » est la suivante:

select distinct v.prénom, v.nom
from Voyageur as v, Séjour as s, Logement as l
where v. idVoyageur=s.idVoyageur
and   s.codeLogement = l .code
and   l.lieu = 'Alpes'

Ni la variable s, ni la variable l ne sont utilisées pour construire le nuplet-résultat. On peut donc l’exprimer ainsi: « je veux les noms des voyageurs pour lesquels il existe un séjour dans les Alpes ». Ce qui donne:

select distinct v.prénom, v.nom
from Voyageur as v
where exists (select ''
              from Séjour as s, Logement as l
              where v. idVoyageur=s.idVoyageur
              and   s.codeLogement = l .code
              and   l.lieu = 'Alpes')

On pourrait même aller encore plus loin dans l’imbrication avec la requête suivante:

select distinct v.prénom, v.nom
from Voyageur as v
where exists (select ''
              from Séjour as s
              where v. idVoyageur=s.idVoyageur
              and exists (select ''
                          from  Logement as l
                           where s.codeLogement = l .code
                           and   l.lieu = 'Alpes')
               )

La troisième version correspond à la formulation « Les voyageurs tels qu’il existe un de leurs séjours tels que le logement existe dans les Alpes ». Elle n’est pas très naturelle, et, de plus, probablement la plus difficile à comprendre, ce qui ne plaide pas en sa faveur.

Quantificateurs et négation

Il nous reste à découvrir les requêtes probablement les plus complexes, celle où l’on exprime une négation. Voici un premier exemple:on veut les logements qui ne proposent pas de Ski. En reprenant la requête « positive » étudiée précédemment, il suffit d’ajouter une négation devant le quantificateur existentiel.

\[\{ l.nom | Logement(l) \land \not \exists a (Activité(a) \land l.code = a.codeLogement \land a.codeActivité=\text{'Ski'})\}\]

On a donc formulé la requête en termes logiques: « je veux les logements tels $ qu’il n’existe pas d’activité Ski ». Voici la requête SQL.

select distinct l.nom
from Logement as l
where not exists (select ''
                 from Activité as a
                 where l.code = a.codeLogement
                 and a.codeActivité = 'Ski')

C’est la seule manière de l’exprimer correctement. Elle donne le résultat suivant:

nom
Causses
U Pinzutu
Tabriz

Vous devriez ête convaincus que la requête suivante est très différente (et ne correspond pas à ce que l’on souhaite). L’opérateur != signifie différent de en SQL.

select l.nom
from Logement as l
where  exists (select ''
                 from Activité as a
                 where l.code = a.codeLogement
                 and a.codeActivité != 'Ski')

Dont le résultat est:

nom
Causses
Génépi
U Pinzutu

Réfléchissez au sens de cette requête, trouvez le résultat sur notre petite base. Rappelez-vous que les quantificateurs servent à exprimer une condition sur un ensemble de nuplet, pas sur chaque nuplet en particulier.

Le not exists est la porte d’entrée pour exprimer le quantificateur universel. Supposons que l’on cherche les voyageurs qui sont allés dans tous les logements. On reformule cette requête avec deux négations: on cherche les voyageurs tels qu’il n’existe pas de logement où ils ne sont pas allés.

select distinct v.prénom, v.nom
from Voyageur as v
where  not exists (select ''
                   from Logement as l
                   where not exists  (select ''
                                      from Séjour as s
                                      where l.code = s.codeLogement
                                      and   v.idVoyageur = s.idVoyageur)
                   )

Vous devriez obtenir:

prénom nom
Nicolas Bouvier

Vous savez maintenant tout sur la version déclarative de SQL, qui n’est rien d’autre qu’une syntaxe concrète pour exprimer des formules ouvertes sur une base de données. Tout ce qui peut s’exprimer par une formule logique est exprimable en SQL. Ni plus, ni moins. Inversement}, tout ce qui ne s’exprime pas par une formule (boucles, incrémentations, etc.) ne s’exprime pas en SQL.

Dans le prochain chapitre, nous verrons la version procédurale, mais il est important de préciser qu’elle n’apporte rien en terme de possibilités d’expression. En d’autres termes, vous avez déjà, avec ce que nous venons d’étudier, la capacité d’exprimer toutes les requêtes possibles. La version procédurale n’est qu’une manière alternative de concevoir l’interrogation d’une base relationnelle.

Prenez le temps de bien maîtriser ce qui précède, car la compréhension du sens de ce que l’on exprime avec les formules de logique des prédicats est la condition nécessaire et suffisante pour utiliser correctement SQL.

Quiz

Exercices