Skip to content

1 4 3 1 calcul

SQL, langage déclaratif ¼ : introduction - Un peu de logique

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 (Caml, 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 a 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 exprime, il faut donc maîtriser l'expression de formules logiques et connaître 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.

Un peu de logique

Supports complémentaires

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 passionnante 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\) \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 truth-values. 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_1) \land F_2\) (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.

Note
Un connecteur très intéressant est l'implication, noté \(\to\). L'implication ne fait pas partie de connecteurs primaires car \(p \to q\) est équivalent à \(\neg p \lor q\). Nous y revenons dans les exercices. Et, oui, l'implication a un lien avec les dépendances fonctionnelles : nous y revenons aussi!

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'atomes, ou de faits). 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 énonçables 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édicats 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 prédicats (dans un contexte arithmétique encore une fois) 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és 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)

Une 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ées \(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, \rm{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. Écrire 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é par 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 :

\[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 auteur = 'Proust'
select nom
from Expert
where exists (select *
             from Manuscrit
             where Expert.id_expert = Manuscrit.id_expert
             and auteur = 'Proust')

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