Bases de données relationnelles

I. Introduction

A. Exemple introductif

On souhaite informatiser notre ludothèque. On peut représenter cela sous la forme d'une table ainsi :

Nom du jeu	Auteur 1	Auteur 2	Éditeur	NbJoueursMin	NbJoueursMax	Nationalité éditeur	Durée en min	Illustrateur	Nationnalité illustrateur	Thèmes
Les chevaliers de la table ronde	Bruno Cathala	S. Laget	Days of wonder	3	7	Française	90	Julien Delval	Française	Moyen-âge, Légende arthurienne
Cargo Noir	Serge Laget		Days of wonder	2	5	Française	60	Miguel Coimbra	Française	Marché Noir, Navigation marchande
Era : medieval age	Matt Leacock		EggertSpiele	1	4	Allemande	50	Chris Quilliams	Canadienne	Médiéval, Construction
Smash up	Paul Peterson		Iello	2	4	Française	45	Bruno Balixa, Dave Alsop, Franciso Rico Torres	Américaine	Fantastique, Monstre, Pirate

Cet exemple servira de fil rouge tout au long de ce court, aussi devez-vous vous y référer chaque fois que cela sera nécessaire.

B. Quelques premières définitions

On appelle une telle table une Relation. Cette table est notamment définie par l'ensemble des noms des colonnes, appelé Schéma de relation, à savoir (Nom du jeu, Auteur 1, Auteur 2, Éditeur, NbJoueursMin, NbJoueursMax, Nationalité éditeur, Durée en min, Illustrateur, Nationnalité illustrateur, Thèmes).

On appelle chaque ligne de la table un Enregistrement ou un Tuple. Les colonnes peuvent être appelées Attribut ou Champ. Les attributs sont caractérisés par un nom et un type (ou ensemble de définition).

C. Premiers constats

Une telle table présente plusieurs inconvénients :

• On a des redondances ; par exemple, la nationnalité de l'éditeur Days of Wonder, est précisée 2 fois ;
• La structure permet de préciser 2 auteurs au plus, mais un seul illustrateur. Du coup, Si on a plus de 2 auteurs ou plus de 2 illustrateurs, on doit triturer la structure de la table (c.f. le cas des illustrateurs pour le jeu Smash Up). Inversement, si on a moins de 2 auteurs, on perd de la place avec des cases vides ;
• Les contenus des cellules sont libres. Ainsi, l'auteur Serge Laget est référencé soit sous son nom complet Serge Laget, soit sous la forme S. Laget, ce qui ne facilite pas les recherches. De même, les jeux portant sur le Moyen-Âge sont référencés soit avec le thème Moyen-âge, soit avec le thème Médiéval ;
• Les valeurs pour le champ Thèmes peuvent contenir plusieurs informations. Ceci ne facilite pas les recherches.

D. Modification de la table

Pour éviter le problème des dépendances multiples (plusieurs auteurs et illustrateurs), on préfère représenter les informations précédentes sous la forme suivante :

Nom du jeu	Auteur	Éditeur	NbJoueursMin	NbJoueursMax	Nationalité éditeur	Durée en min	Illustrateur	Nationnalité illustrateur	Thèmes
Les chevaliers de la table ronde	Bruno Cathala	Days of wonder	3	7	Française	90	Julien Delval	Française	Moyen-âge, Légende arthurienne
Les chevaliers de la table ronde	S. Laget	Days of wonder	3	7	Française	90	Julien Delval	Française	Moyen-âge, Légende arthurienne
Cargo Noir	Serge Laget	Days of wonder	2	5	Française	60	Miguel Coimbra	Française	Marché Noir, Navigation marchande
Era : medieval age	Matt Leacock	EggertSpiele	1	4	Allemande	50	Chris Quilliams	Canadienne	Médiéval, Construction
Smash up	Paul Peterson	Iello	2	4	Française	45	Bruno Balixa	Américaine	Fantastique, Monstre, Pirate
Smash up	Paul Peterson	Iello	2	4	Française	45	Franciso Rico Torres	Américaine	Fantastique, Monstre, Pirate
Smash up	Paul Peterson	Iello	2	4	Française	45	Dave Alsop	Américaine	Fantastique, Monstre, Pirate

Avec une telle représentation, le problème de redondance devient alors criant.

II. Un peu de vocabulaire et de théorie...

A. Notion de dépendance fonctionnelle

1. Définitions

Pour mieux structurer la représentation de notre ludothèque, on introduit la notion de dépendance fonctionnelle entre attributs :

Par ailleurs, on préfère avoir uniquement des champs atomiques :

2. Exercices

3. Couverture minimale

Face à un schéma de relation Ω et un ensemble de dépendances fonctionnelles DF, on essaie en général de déterminer un ensemble minimale de dépendances fonctionnelles non triviales (ni réflexives, ni liées à l'augmentation) dont la fermeture transitive est égale à la fermeture transitive de l'ensemble DF.

Il existe des algorithmes pour calculer la couverture minimale d'un ensemble de dépendances fonctionnelles, mais cela dépasse le cadre de ce cours.

Remarque : Souvent, on omet le schéma de relation dans la définition de la fermeture transitive.

On représente souvent un ensemble de dépendances fonctionnelles sous la forme d'un graphe exempt des df triviales.

B. Notion de clé

C. Formes Normales

Pour éviter un certain nombre de problèmes (redondance par exemple), différentes formes normales ont été définies pour les bases de données. Voici les 3 premières :

Remarque : La 3FN ne garantit pas totalement l'absence de redondance dans tous les cas.

D. Transformer un schéma de relation en 3FN

Il est toujours possible de transformer un schéma de relation en 3FN. Pour cela, Il va falloir créer plusieurs relations afin de se ramener aux règles des différentes formes normales.

1. Rendre tous les attributs atomiques

Cette première phase permet d'obtenir une relation en 1FN. C'est ce qui a été fait dans l'exercice 1.

2. Passer en 2FN

Pour passer en 2FN, on va éclater le schéma de relation initial en plusieurs schémas, de façon à ce que chaque fois qu'on a une dépendance fonctionnelle de la forme (partieClé → attribut), on crée une relation spécifique avec pour clé partieClé et pour attribut non clé attribut. Une fois ceci fait, si plusieurs relations ont même clé, on les fusionne en 1 seule relation ayant tous les attributs des relations de départ. Par ailleurs, on gardera une relation avec l'ensemble des attributs de la clé minimale.

3. Passer en 3FN

Pour passer en 3FN, pour chaque dépendance de la forme AttributNonClé → Attribut, on va créer une table (AttributNonClé, Attribut), et on supprime Attribut de la relation de départ. À la fin du processus, on fusione les tables de même clé.

E. Remarque sur la 3FN et sur le travail fait précédemment

La 3FN permet d'éviter un certain nombre de redondances, mais ne les supprime pas toutes, comme on peut le voir sur l'exemple précédent. On peut bien sûr obtenir mieux, mais avec un schéma qui n'est pas équivalent au schéma initial. Les explications dépassent cependant le cadre de ce cours.

Par ailleurs, procéder comme cela a été fait précédemment ne permet pas de mettre en évidence que les attributs (NomAuteur, PrénomAuteur) correspondent à une même entité, à savoir la notion d'Auteur.