Les ensembles en informatique : SQL, codage et tri

La théorie des ensembles sert en informatique partout où l'on regroupe, compare, combine ou code des données : les bases de données relationnelles reposent sur elle, les masques de bits codent des ensembles dans un entier, les sous-réseaux sont des classes d'équivalence, et tout algorithme de tri suppose une relation d'ordre. Ce chapitre rassemble ces usages, avec des exemples que tu peux exécuter. Il sert aussi de révision : chaque notion des chapitres 1 à 6 y réapparaît dans un contexte professionnel.

Le modèle relationnel, une théorie des ensembles appliquée

En 1970, Edgar F. Codd propose de ranger les données dans des relations au sens mathématique, c'est-à-dire des parties d'un produit cartésien de domaines (chapitre 3). Il définit sur ces relations des opérations, l'algèbre relationnelle, dont SQL est la traduction.

Une nuance sépare la théorie de la pratique : une table SQL peut contenir des lignes en double, et un SELECT sans DISTINCT les garde. On parle de multiensemble (un ensemble où un élément peut figurer plusieurs fois). C'est pourquoi SQL a des variantes UNION ALL, INTERSECT ALL et EXCEPT ALL, qui conservent les doublons.

UNION, INTERSECT et EXCEPT

Prenons deux tables d'une seule colonne : acces_vpn(login) contient ana, bilal, chloe, david et emma ; groupe_admin(login) contient bilal, emma et farid. Ce sont deux parties de l'ensemble des comptes.

-- Réunion : les comptes du VPN ou du groupe admin (doublons supprimés)
SELECT login FROM acces_vpn
UNION
SELECT login FROM groupe_admin
ORDER BY login;
-- ana, bilal, chloe, david, emma, farid : 6 lignes

-- Intersection : les administrateurs qui ont accès au VPN
SELECT login FROM acces_vpn
INTERSECT
SELECT login FROM groupe_admin
ORDER BY login;
-- bilal, emma

-- Différence : les comptes VPN qui ne sont pas administrateurs
SELECT login FROM acces_vpn
EXCEPT
SELECT login FROM groupe_admin
ORDER BY login;
-- ana, chloe, david

La formule du cardinal d'une réunion se vérifie : 5 + 3 − 2 = 6. Et UNION ALL, qui garde les doublons, renvoie 5 + 3 = 8 lignes. L'ordre des deux requêtes compte pour EXCEPT comme pour la différence : groupe_admin EXCEPT acces_vpn ne renvoie que farid.

Avant ces opérateurs, on écrivait l'intersection et la différence avec l'appartenance, IN et NOT IN, ou avec EXISTS :

-- Intersection avec IN : x ∈ A et x ∈ B
SELECT login FROM acces_vpn
WHERE login IN (SELECT login FROM groupe_admin);

-- Différence avec NOT EXISTS : x ∈ A et x ∉ B
SELECT v.login FROM acces_vpn v
WHERE NOT EXISTS (SELECT 1 FROM groupe_admin g WHERE g.login = v.login);

Le piège de NOT IN et de NULL

Dans une table employe(id_employe, nom, id_service, id_responsable), la directrice n'a pas de responsable : sa colonne id_responsable vaut NULL. On cherche les employés qui ne sont le responsable de personne, c'est-à-dire la différence « tous les employés privés des responsables » :

SELECT nom FROM employe
WHERE id_employe NOT IN (SELECT id_responsable FROM employe);
-- aucune ligne !

La sous-requête contient un NULL. Pour SQL, 3 NOT IN (1, 2, NULL) signifie « 3 ≠ 1 et 3 ≠ 2 et 3 ≠ NULL », et la comparaison avec NULL ne vaut ni vrai ni faux, mais inconnu : toute la condition devient inconnue, et la ligne est écartée. SQL ne suit pas la logique à deux valeurs des ensembles, mais une logique à trois valeurs. Deux corrections :

-- Retirer NULL de l'ensemble avant la différence
SELECT nom FROM employe
WHERE id_employe NOT IN (SELECT id_responsable FROM employe WHERE id_responsable IS NOT NULL);

-- Ou utiliser NOT EXISTS, qui ne souffre pas du problème
SELECT nom FROM employe e
WHERE NOT EXISTS (SELECT 1 FROM employe x WHERE x.id_responsable = e.id_employe);

Une jointure est une partie du produit cartésien

Avec une table service de 3 lignes et une table employe de 4 lignes, le produit cartésien service CROSS JOIN employe compte 3 × 4 = 12 lignes : chaque employé associé à chaque service. La jointure n'en garde que les couples où l'employé appartient vraiment au service :

SELECT e.nom, s.libelle
FROM employe e
JOIN service s ON s.id_service = e.id_service;

Mathématiquement, c'est la partie {(e ; s) ∈ Employés × Services | e.id_service = s.id_service} : 4 couples sur 12. Une jointure, c'est un produit cartésien suivi d'une sélection. Le SGBD ne calcule pas réellement les 12 lignes (il utilise des index pour aller droit aux bons couples), mais le résultat est le même.

Deux conséquences pratiques :

• une condition de jointure oubliée renvoie tout le produit cartésien : un nombre de lignes égal au produit des tailles des tables est le symptôme ;
• la clé étrangère id_service définit une application des employés vers les services (chapitre 6), et la jointure interne ne garde que les services qui ont un antécédent. Le LEFT JOIN garde aussi ceux qui n'en ont pas, avec des NULL : c'est l'outil pour tester la surjectivité.

Regrouper et trier : équivalence et ordre en SQL

Les masques de bits : un ensemble dans un entier

Au chapitre 1, une partie d'un ensemble de n éléments s'écrivait comme un mot de n bits. Les programmes stockent ainsi des ensembles dans un simple entier, et les opérations ensemblistes deviennent des opérations bit à bit, exécutées en une instruction du processeur.

Exemple : les droits Unix. Avec r = 4 (100), w = 2 (010) et x = 1 (001), les droits {r ; w} valent 6 (110).

• Ajouter x : 6 | 1 = 7, soit {r ; w ; x}.
• Retirer w : 6 & ~2 = 4, soit {r} (sur 3 bits).
• Tester r : 6 & 4 = 4, non nul : r ∈ {r ; w}.

Exemple : les sous-réseaux. L'adresse réseau d'une machine s'obtient par un ET bit à bit entre son adresse et le masque. Avec le masque 255.255.255.192 (/26) :

192.168.10.77 et 192.168.10.100 ont la même image par l'application « adresse ↦ adresse ET masque » : elles sont dans la même classe, le même sous-réseau, et peuvent communiquer sans routeur. Le calcul détaillé des masques est dans le cours Réseaux.

Les ensembles dans les langages de programmation

Python et JavaScript ont un type ensemble natif, qui garantit l'absence de doublons et teste l'appartenance très vite, quelle que soit sa taille (il repose sur une table de hachage, donc sur des classes d'équivalence).

vpn = {"ana", "bilal", "chloe", "david", "emma"}
admin = {"bilal", "emma", "farid"}

print(sorted(vpn | admin))   # réunion : ['ana', 'bilal', 'chloe', 'david', 'emma', 'farid']
print(sorted(vpn & admin))   # intersection : ['bilal', 'emma']
print(sorted(vpn - admin))   # différence : ['ana', 'chloe', 'david']
print(sorted(vpn ^ admin))   # différence symétrique : ['ana', 'chloe', 'david', 'farid']
print(admin <= vpn)          # inclusion : False (farid n'est pas dans vpn)
print("ana" in vpn)          # appartenance : True

En JavaScript, les objets Set ont reçu en 2024 les méthodes ensemblistes, disponibles dans les navigateurs actuels et dans Node.js depuis la version 22 :

const vpn = new Set(["ana", "bilal", "chloe", "david", "emma"]);
const admin = new Set(["bilal", "emma", "farid"]);

vpn.union(admin);               // Set { ana, bilal, chloe, david, emma, farid }
vpn.intersection(admin);        // Set { bilal, emma }
vpn.difference(admin);          // Set { ana, chloe, david }
vpn.symmetricDifference(admin); // Set { ana, chloe, david, farid }
admin.isSubsetOf(vpn);          // false
vpn.has("ana");                 // true

// Supprimer les doublons d'un tableau : passer par un ensemble
const ports = [80, 443, 80, 22, 443];
const uniques = [...new Set(ports)]; // [80, 443, 22]

Trier suppose une relation d'ordre total

Un algorithme de tri range des éléments du plus petit au plus grand : il lui faut une relation qui permette de comparer n'importe quels deux éléments, donc un ordre total (chapitre 5). Avec un ordre partiel (« divise », l'inclusion), il n'y a pas de « plus petit » entre deux éléments incomparables, et un tri n'a pas de sens.

En pratique, la fonction de comparaison qu'on passe à un tri (usort en PHP, sort avec un comparateur en JavaScript, key= en Python) définit cet ordre. Elle doit être cohérente : si a passe avant b et b avant c, a doit passer avant c (transitivité). Un comparateur incohérent donne un tri faux, sans erreur.

Quand on trie selon un seul critère qui ne départage pas tout (trier des employés par service), deux employés du même service sont « à égalité » : la relation « passe avant ou au même rang » est réflexive et transitive, mais pas antisymétrique. Un tri stable garde alors l'ordre d'origine des ex æquo. Les tris de Python, de JavaScript (depuis ES2019) et de PHP (depuis la version 8.0) sont stables. C'est ce qui permet de trier d'abord par prénom, puis par nom, et d'obtenir un résultat rangé par nom puis prénom : l'ordre lexicographique, construit en deux passes.

L'ordre lexicographique est aussi celui des chaînes : c'est pourquoi un tri de noms de fichiers place fichier10.txt avant fichier2.txt. Les explorateurs de fichiers utilisent un « tri naturel », qui compare les suites de chiffres comme des nombres.

Codage, chiffrement, compression : des applications

Le programme du BTS SIO cite le codage, le tri et la compression comme usages de ces notions. Chacun pose la même question : l'application est-elle injective ? bijective ?

Exercices

SELECT email FROM etudiant
EXCEPT
SELECT email FROM inscrit_python
EXCEPT
SELECT email FROM inscrit_reseau;