La forme mathématique des bases de données

Pourquoi « normaliser son schéma » est un calcul, et non un conseil de bon goût

Dans le cas des bases de données, la situation est plus favorable que pour le code — et cela surprend souvent.

Vérifier un programme demande des annotations, des invariants, du temps. Vérifier la structure d'une base demande de déclarer quelques faits sur le monde, après quoi une bonne partie du travail se calcule. La raison est que le modèle relationnel n'a pas été découvert après coup : il a été conçu comme une théorie mathématique avant d'être un produit.

I. Une table est une relation

Edgar Codd publie en 1970 A Relational Model of Data for Large Shared Data Banks. L'article est court et son idée tient en une phrase : une table est une relation au sens mathématique, c'est-à-dire un ensemble de n-uplets.

La table

est l'ensemble

{ (978-2-07-036002-4, La Nausée, Sartre), (978-2-07-040850-4, L'Étranger, Camus) }

Un ensemble, avec les conséquences que cela entraîne : pas d'ordre — deux tables aux mêmes lignes rangées différemment sont la même table, et c'est pourquoi une requête sans ORDER BY ne garantit aucun ordre ; pas de doublon, en théorie ; et surtout, des opérations mathématiques disponibles.

Ces opérations forment l'algèbre relationnelle : sélectionner des lignes, projeter des colonnes, joindre deux tables, prendre l'union, la différence. Six opérateurs environ, dont tout le reste se déduit.

SQL n'en est que l'habillage. SELECT titre FROM livres WHERE auteur = 'Camus' est une projection composée avec une sélection. Cette correspondance est la raison d'être de SQL : on décrit quel ensemble on veut, jamais comment l'obtenir.

L'optimiseur démontre des théorèmes toute la journée

La conséquence est plus concrète qu'il n'y paraît. Comme les requêtes sont des expressions algébriques, il existe des égalités démontrées entre elles. Par exemple, sélectionner après une jointure donne toujours le même résultat que sélectionner avant, quand le critère ne porte que sur une table. Ce n'est pas une heuristique : c'est un théorème, vrai pour toute donnée.

L'optimiseur de requêtes exploite cette liberté. Il reçoit votre requête, lui applique des réécritures dont l'équivalence est démontrée, et choisit la forme la moins coûteuse. Filtrer avant de joindre peut diviser le travail par mille — et l'optimiseur le fait sans jamais risquer de changer le résultat, parce que les règles qu'il applique préservent l'égalité par construction.

Autrement dit : à chaque requête, une machine transforme votre demande en une autre qu'elle a démontrée équivalente. La vérification mathématique n'est pas ici un outil qu'on ajoute, c'est le fonctionnement ordinaire du moteur.

II. Les dépendances fonctionnelles

Le second pilier est une notion d'une simplicité désarmante.

X → Y : connaître X détermine Y.

Connaître l'ISBN détermine le titre — jamais deux titres différents pour le même ISBN. On écrit isbn → titre. De même adherent → courriel, si chaque adhérent a une adresse.

Ces dépendances ne se déduisent pas des données. Ce sont des affirmations sur le monde. Que la table ne contienne aujourd'hui aucun contre-exemple ne prouve rien : c'est vous qui décidez que deux livres ne peuvent pas partager un ISBN. C'est le seul endroit de cet article où l'humain doit réfléchir — tout ce qui suit est mécanique.

Ce qu'une mauvaise structure coûte

Voici une table plausible, et mauvaise. Un registre de prêts :

Elle souffre de trois maux, qui portent des noms précis.

Anomalie de modification. Marie change d'adresse. Son courriel figure dans autant de lignes qu'elle a emprunté de livres. Si une seule est oubliée, la base affirme deux courriels pour l'adhérent 42 — elle se contredit. Un fait unique y est stocké en plusieurs exemplaires, et rien n'oblige les exemplaires à rester d'accord.

Anomalie d'insertion. La bibliothèque acquiert un livre. Impossible de l'enregistrer : la table n'accepte une ligne qu'avec un adhérent et une date. On ne peut pas dire qu'un livre existe sans inventer un prêt.

Anomalie de suppression. Le prêt de L'Étranger est le seul de ce livre. On le supprime, l'exemplaire étant rendu — et le titre et l'auteur disparaissent avec. Une information sans rapport avec ce prêt a été détruite.

Le diagnostic est le même dans les trois cas : la table mélange trois faits indépendants — ce qu'est un livre, qui est un adhérent, qui a emprunté quoi. Les anomalies sont la sanction de ce mélange, et elles sont prévisibles à partir des seules dépendances.

III. Le calcul

Voici la partie mécanique. Trois règles, un algorithme, et le schéma se déduit.

Les axiomes d'Armstrong

En 1974, William Armstrong donne trois règles qui permettent de dériver toutes les dépendances impliquées par un ensemble donné :

1. Réflexivité — si Y est inclus dans X, alors X → Y. (Connaître le titre et l'auteur, c'est connaître le titre.)
2. Augmentation — si X → Y, alors XZ → YZ. (Si l'ISBN donne le titre, l'ISBN avec la date donne le titre avec la date.)
3. Transitivité — si X → Y et Y → Z, alors X → Z. (L'ISBN donne l'éditeur, l'éditeur donne son pays : l'ISBN donne le pays.)

Chacune est évidente. Ce qui ne l'est pas, c'est le théorème qui les accompagne, et qui est le pivot de tout l'article : ces trois règles sont correctes et complètes.

• Correctes : tout ce qu'on en dérive est vrai.
• Complètes : tout ce qui est vrai peut en être dérivé.

La complétude est l'énoncé fort. Elle signifie qu'il n'existe aucune conséquence cachée : rien ne peut découler de vos dépendances sans que ces trois règles ne l'atteignent. C'est précisément ce qui autorise une machine à travailler. Sans ce théorème, on ne saurait jamais si l'analyse a fait le tour de la question.

La clôture

L'algorithme qui en découle s'appelle le calcul de la clôture de X, notée X⁺ : l'ensemble de tout ce que X détermine.

Partir de X. Tant qu'une dépendance A → B a son A entièrement contenu dans l'ensemble courant, y ajouter B. S'arrêter quand plus rien ne bouge.

Sur le registre de prêts, avec isbn → titre, auteur et adherent → courriel :

• {isbn}⁺ = {isbn, titre, auteur} — l'ISBN ne détermine ni l'adhérent ni la date.
• {adherent}⁺ = {adherent, courriel}
• {isbn, adherent, date}⁺ = toutes les colonnes.

Cette boucle termine toujours — l'ensemble ne fait que croître dans un ensemble fini de colonnes — et elle est rapide. Elle donne immédiatement les deux notions qu'on cherchait :

Une clé est un ensemble de colonnes dont la clôture est la table entière, et qui est minimal. Ici : {isbn, adherent, date}. Ce n'est pas un choix de conception, c'est un résultat de calcul : étant donné vos dépendances, la clé est déterminée.

IV. Les formes normales sont des théorèmes

On peut maintenant énoncer ce qu'est une « bonne » table, sans invoquer le goût.

La forme normale de Boyce-Codd (BCNF) tient en une ligne :

Pour toute dépendance X → Y non triviale de la table, X doit être une clé.

Autrement dit : dans une table, tout doit dépendre de la clé, et de rien d'autre. Une colonne déterminée par autre chose que la clé signale un fait étranger qui s'est invité dans la table — et qui va s'y répéter, d'où les trois anomalies.

Le registre de prêts échoue : isbn → titre est une dépendance dont la source, isbn, n'est pas une clé. Le diagnostic est automatique, et il désigne le coupable.

La réparation l'est aussi. On sépare :

• livres(isbn, titre, auteur) — clé isbn
• adherents(id, courriel) — clé id
• prets(isbn, adherent, date) — clé {isbn, adherent, date}

Chaque fait est désormais stocké une fois. Les trois anomalies ont disparu, non par chance : elles étaient la conséquence de la violation, elles s'en vont avec elle.

Le découpage ne doit rien perdre

Découper une table est risqué : mal fait, on perd de l'information, ou pire, on en invente. Le critère existe, et il est simple (Heath, 1971) :

Couper R en R1 et R2 est sans perte si les colonnes communes aux deux déterminent l'une ou l'autre.

La jointure redonne alors exactement la table de départ — ni plus, ni moins. Si la condition n'est pas remplie, la jointure fabrique des lignes qui n'existaient pas : la base se met à affirmer des choses fausses. Ce critère se vérifie par un calcul de clôture, donc automatiquement.

Le théorème gênant

Voici le résultat qui montre le mieux qu'on est en territoire mathématique, parce qu'il énonce une impossibilité — et qu'une impossibilité ne se contourne pas par un meilleur outil.

On veut trois choses d'un découpage : qu'il soit sans perte, qu'il atteigne la BCNF, et qu'il préserve les dépendances — que chaque contrainte reste vérifiable sur une seule table, sans jointure.

On ne peut pas toujours avoir les trois.

L'exemple canonique est une table d'adresses (ville, rue, code_postal) avec deux faits vrais en France :

• {ville, rue} → code_postal
• code_postal → ville

La seconde viole la BCNF, car code_postal n'est pas une clé. Pour l'atteindre, il faut séparer en (code_postal, ville) et (code_postal, rue). Le découpage est sans perte — mais la dépendance {ville, rue} → code_postal n'est plus contrôlable nulle part : ville et rue ne cohabitent plus dans aucune table. Pour vérifier qu'on n'insère pas deux codes postaux pour la même rue de la même ville, il faudrait joindre à chaque écriture.

D'où l'existence de la troisième forme normale (3NF), légèrement plus permissive, et le théorème qui l'accompagne : un découpage en 3NF, sans perte et préservant les dépendances, existe toujours, et on sait le calculer (algorithme de synthèse de Bernstein, 1976).

Le choix entre 3NF et BCNF n'est donc pas affaire de rigueur mais un arbitrage entre deux garanties incompatibles, et c'est un théorème qui le dit. La table d'adresses ci-dessus reste en 3NF : elle tolère une redondance mesurée pour garder ses contraintes vérifiables localement.

Au-delà

Deux formes supplémentaires existent, pour des situations plus rares où le problème n'est plus qu'une colonne dépende d'une autre, mais que deux listes indépendantes se retrouvent dans la même table et s'y multiplient — un auteur avec ses langues et ses genres littéraires produit toutes les combinaisons des deux. C'est l'objet des dépendances multivaluées et de la 4NF, puis des dépendances de jointure et de la 5NF. La théorie est complète, et le praticien y a rarement recours.

V. Les contraintes : des invariants tenus à l'exécution

Tout ce qui précède concerne la structure, vérifiée avant toute donnée. Il existe un second registre, complémentaire : les contraintes que le moteur fait respecter à chaque écriture.

NOT NULL, UNIQUE, CHECK (montant >= 0) sont exactement des invariants au sens de l'article précédent — des énoncés qu'aucune transaction ne peut violer. La différence est le moment : une preuve statique établit avant exécution qu'aucun cas ne viole la propriété ; une contrainte laisse le moteur refuser, à chaque fois, tout ce qui la violerait. Garantie équivalente, obtenue autrement, et pour un coût de conception nul.

L'intégrité référentielle — « tout adherent cité dans prets existe dans adherents » — appartient au même registre. Elle s'exprime comme une inclusion entre les valeurs de deux colonnes, et peut être tenue soit par le moteur, soit par le code applicatif ; la théorie dit ce qui doit être vrai, pas qui doit le faire respecter.

Un dernier résultat mérite mention, parce qu'il est un exemple achevé de la démarche. Que signifie exécuter mille transactions en parallèle sans que le résultat devienne incohérent ? La réponse formelle est la sérialisabilité : une exécution entrelacée est correcte si elle produit le même état qu'une exécution où les transactions se seraient succédé une à une. Ce critère est vérifiable — on l'exprime par l'absence de cycle dans un graphe de conflits — et les protocoles de verrouillage des moteurs sont accompagnés de la démonstration qu'ils ne produisent que des exécutions sérialisables. Le BEGIN … COMMIT du praticien repose sur un théorème.

Ce que le calcul ne décide pas

Deux réserves, sans lesquelles le tableau serait trompeur.

Les dépendances viennent du monde, pas de la machine. Tout ce qui précède est mécanique à partir des dépendances déclarées. Si vous affirmez qu'un adhérent n'a qu'un courriel et que la bibliothèque en accepte deux, le schéma calculé sera impeccablement dérivé d'une prémisse fausse. La partie qui ne s'automatise pas est la seule qui demande de connaître le métier — et c'est exactement le problème de spécification de l'article suivant, sous un autre costume.

La forme normale n'est pas un impératif. Dénormaliser — recopier volontairement une donnée pour éviter une jointure coûteuse — est une décision d'ingénierie parfaitement défendable. La théorie ne l'interdit pas ; elle dit ce que cela coûte : la redondance introduite devra être tenue cohérente par autre chose que la structure, donc par du code, donc par de la vigilance. Savoir quelle garantie on abandonne, et en échange de quoi, est tout ce qu'on demande à une théorie.