1 4 3 2 sql conjonctif

SQL, langage déclaratif. 2/4 : SQL conjonctif

Supports complémentaires

• Diapositives : SQL conjonctif.
• Vidéo sur la première partie de SQL.

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. Voir également l'atelier SQL proposé en fin de chapitre.

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 pas 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.
• 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 des relations calculées, autrement dit le 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 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, ce qui revient à accepter 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 l'atelier en fin de chapitre.

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 simplifié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

Voyons 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

À 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 relatifs 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.