Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes d'information

Le modèle relationnel : clés, contraintes et algèbre relationnelle

Relations, n-uplets et domaines, existence d'une clé démontrée, contraintes d'intégrité et clés étrangères, sélection, projection et jointure, cardinalité d'une jointure démontrée, de l'algèbre à SQL.

https://www.electronics-engineering.com/fr/modele-relationnel-cles-algebre-relationnelle/

Pas encore de vote : soyez le premier à noter cette page.

En 1970, Edgar Codd, chercheur chez IBM, proposa de représenter les données comme de simples tables et de les interroger avec des opérations mathématiques, au lieu de naviguer entre des pointeurs comme dans les systèmes de l’époque. Le modèle relationnel est encore la base de presque tout système d’information. Dans cette leçon, nous regardons les relations et les clés avec la démonstration que toute relation en a au moins une, les contraintes d’intégrité, l’algèbre relationnelle avec la sélection, la projection et la jointure, la démonstration des bornes sur la taille d’une jointure, et le lien avec SQL.

Relations, n-uplets et attributs

Une relation est une table avec un nom, des colonnes nommées (les attributs) et des lignes (les n-uplets, ou tuples). Mathématiquement, c’est un ensemble de n-uplets : l’ordre des lignes ne compte pas et il n’y a pas deux lignes égales. Chaque attribut prend ses valeurs dans un domaine (entiers, dates, chaînes), et chaque cellule contient une seule valeur atomique. Le schéma de la relation est le nom avec les attributs, Étudiant(numéro, prénom, nom, naissance) ; l’instance est le contenu à un moment donné.

Les clés

Une super-clé est un ensemble d’attributs qui ne prend jamais la même valeur dans deux n-uplets différents. Une clé est une super-clé minimale : en retirant n’importe quel attribut, ce n’est plus une super-clé.

Théorème. Toute relation a au moins une clé.

Démonstration. L’ensemble de tous les attributs est une super-clé : deux n-uplets de valeurs toutes égales seraient le même n-uplet, et une relation est un ensemble, donc sans doublons. Si cette super-clé n’est pas minimale, on retire un attribut qui la laisse super-clé, et l’on recommence. Il y a un nombre fini d’attributs, donc la procédure s’arrête, et l’ensemble atteint est une super-clé dont on ne peut plus rien retirer : une clé. ∎

Parmi les clés, on en choisit une comme clé primaire, sur laquelle les valeurs nulles ne sont pas admises. On utilise souvent un code artificiel (un numéro séquentiel) même quand il existe une clé naturelle, parce qu’il est plus stable et plus compact.

Les contraintes d’intégrité

Le modèle n’accepte pas n’importe quelles données : les contraintes expriment les règles du monde réel et le SGBD les fait respecter.

  • Contraintes de domaine et de n-uplet : la note est entre 18 et 30, la date de fin ne précède pas la date de début.
  • Contrainte de clé : pas de doublons sur la clé primaire, pas de valeurs nulles.
  • Intégrité référentielle : une clé étrangère doit renvoyer à un n-uplet existant. Chaque examen renvoie à un étudiant présent dans la table Étudiant. Quand l’étudiant est supprimé, le SGBD peut refuser la suppression, supprimer aussi ses examens (en cascade) ou mettre la référence à nul, selon la façon dont la contrainte a été déclarée.

L’algèbre relationnelle

Les requêtes se construisent avec des opérateurs qui prennent des relations et renvoient des relations, et qui peuvent donc se composer :

  • la sélection \sigma_{cond}(R) : les n-uplets qui satisfont une condition, c’est-à-dire un sous-ensemble des lignes ;
  • la projection \pi_{A,B}(R) : seulement certaines colonnes, en éliminant les doublons qui en résultent ;
  • l’union, la différence, l’intersection de relations de même schéma ;
  • le renommage d’attributs ;
  • la jointure naturelle R \bowtie S : combine les n-uplets des deux relations qui ont des valeurs égales sur les attributs communs.
Jointure naturelle de deux relations
R et S ont en commun l’attribut B. Le résultat contient un n-uplet pour chaque paire de n-uplets de R et S de même valeur de B : le n-uplet a2 b2 n’a pas de correspondant dans S et disparaît, tandis que chaque n-uplet avec b1 se combine avec les deux n-uplets de S avec b1.

Théorème. La jointure naturelle de R et S a un nombre de n-uplets compris entre 0 et |R|\cdot|S|. Si les attributs communs contiennent une clé de S, le résultat a au plus |R| n-uplets ; si en outre il y a une contrainte d’intégrité référentielle de R vers S sur ces attributs, il en a exactement |R|.

Démonstration. Chaque n-uplet du résultat vient d’une paire de n-uplets, un de R et un de S, et les paires possibles sont au nombre de |R|\cdot|S| : c’est le maximum, atteint quand tous ont la même valeur sur les attributs communs. Le minimum 0 se produit quand aucune valeur ne correspond. Si les attributs communs contiennent une clé de S, pour chaque n-uplet de R il y a au plus un n-uplet de S avec ces valeurs, donc chaque n-uplet de R apporte au plus un n-uplet au résultat. Avec la contrainte référentielle, ce n-uplet de S existe toujours, et l’apport est exactement un. ∎

C’est le cas le plus courant : joindre les examens (avec la clé étrangère) aux étudiants (avec la clé) donne une ligne par examen, enrichie des données de l’étudiant. Le savoir aide à comprendre quand une requête renvoie « trop de lignes » : d’ordinaire la jointure portait sur des attributs qui ne sont pas une clé.

De l’algèbre à SQL

SQL, le langage de tous les SGBD relationnels (leçon sur SQL), est un langage déclaratif construit sur ces opérations : on dit ce que l’on veut, non comment l’obtenir.

SELECT s.surname, e.mark
FROM Student s JOIN Exam e ON s.number = e.number
WHERE e.mark >= 28;

correspond à \pi_{surname,\,mark}(\sigma_{mark \ge 28}(Student \bowtie Exam)). Le SGBD traduit la demande en une expression d’algèbre et l’optimise avec des équivalences algébriques : par exemple, il effectue la sélection avant la jointure, pour joindre moins de n-uplets. Cette indépendance entre la question et la façon d’y répondre, rendue possible par la base mathématique du modèle, est la principale raison de son succès.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x