Conception des bases de données relationnelles

Conception des bases de données relationnelles, tutoriel & guide de travaux pratiques bases de données en pdf.

Présentation du modèle relationnel

Ce chapitre rappel brièvement la structure et les langages du modèle relationnel, sans entrer dans les détails – l’objectif étant principalement de présenter le contexte et les notations. La partie sur les contraintes fera l’objet du chapitre suivant.

Introduction

Le modèle relationnel a été défini en 1970 par Codd. Cette proposition a succédé aux modèles hié-rarchiques et réseaux, avec pour but de définir un modèle simple à comprendre, fondé sur des bases mathématiques solides (logique et théorie des ensembles), et pouvant conduire à une amélioration des performances des outils. L’idée de base est simple : mettre les données “à plat“ dans des tableaux, de façon à ce que chaque valeur apparaissant dans les “cases” du tableau soient atomiques. Cette simplification est la principale explication de la performance du modèle relationnel, car elle évite les traitements récursifs (parcours de graphes et d’arbres complexes).
Après une dizaine d’année de développement de la théorie inhérente aux propositions de Codd, les premiers SGBD commerciaux font leur apparition dans les années 80, avec des outils comme ORACLE principalement. Les contributions techniques se combinent alors aux fondements théoriques et le modèle relationnel s’impose comme un standard. Dès le début des années 90, les progrès technologiques fulgurants sur le matériel (processeurs et mémoire disque) conduisent à des bases de plus en plus grosses, pour atteindre des proportions gigantesques de nos jours. La recherche dans le domaine des bases de données relationnelles est toujours active, placée sans cesse face à des nouveaux défis de taille, d’exigence de rapidité, d’hétérogénéité des données. Même si de nouveaux paradigmes pourraient être en passe de voir le jour dans le traitement des bases de données de production, les fondements théoriques présentés dans ce cours constituent toujours la base des techniques utilisées.

Structure

La structure d’une BD relationnelle est fondée sur la théorie des ensembles. Rappelons qu’un ensemble est une collection non ordonnée d’éléments distincts, à différencier de la séquence (lorsque les éléments sont ordonnés) et du multi-ensemble (lorsqu’on accepte les doublons).
Notations les notations suivantes sont communément admises lorsque le contexte le permet. Un ensemble fA1; A2; :::; Ang sera noté par la concaténation de ses éléments : A1A2:::An. Si X et Y sont deux ensemble, leur union X [ Y sera notée XY . Une séquence d’éléments, est notée < A1; :::; An >. Lorsque le contexte est clair, les séquences et les ensembles seront notés de la même façon.
Exemple 1 L’ensemble fA; B; Cg sera noté ABC dans ce cours. Les notations ABC et BCA sont équivalentes puisque l’ordre n’a pas d’importance : par convention, on notera les ensembles théoriques en respectant l’ordre alphabétique. L’ensemble AABC n’existe pas, puisque l’élément A apparaît deux fois. Soit les ensemble X = ABC et Y = BD, alors leur union X [ Y sera noté XY = ABCD.

Attributs, valeurs et domaines

Soit U un ensemble infini dénombrable de noms d’attributs ou simplement attributs, et D un ensemble infini dénombrable de valeurs. Soit A 2 U un attribut, le domaine de A est un sous-ensemble de D, noté DOM(A).
Hypothèse d’unicité des noms : Soient deux valeurs v1 et v2 des éléments de D. On dit que v1 et v2 sont égales si et seulement si elles sont syntaxiquement identiques, c’est à dire qu’elles ont le même nom. En d’autres termes, lorsque deux attributs ont la même valeur, ils désignent la même chose.

Schémas de relations, schémas de bases de données et première forme normale

Définition 1 (schémas de relations et de bases de données) Un schéma de relation R est un ensemble fini d’attributs (donc R U). Un schéma de base de données R est un ensemble fini de schémas de relation.
Exemple 2
L’exemple suivant sera utilisé tout au long de ce cours. On suppose une application gérant les cours dispensés au sein de l’UFR, regroupant des informations sur les étudiants, les formations, les enseignants, les modules, les UE, les salles de cours et les ressources matérielles (projecteurs, etc…). La modélisation des étudiants pourrait se faire à l’aide du schéma de relation
ET U DIAN T S = fN U M; N OM; P REN OM; AGE; F ORM AT IONg
. Si on représente les autres informations dans d’autres schémas de relations, alors l’union de tous les sché-mas de relation obtenus constituera le schéma de notre base de données, qu’on pourra appeler F ACU LT E.
Hypothèse de schéma de relation universel : Un schéma de base de données R satisfait l’hypo-thèse de schéma de relation universelle si, lorsque deux attributs portent le même nom, ils désignent le même concept.
Définition 2 (Première forme normale) Un schéma de relation R est en première forme normale (notée 1F N) si, pour tout attribut A 2 R, DOM(A) est composé de valeurs atomiques.
La première forme normale est une condition fondamentale du modèle relationnel, garante de sa simplicité et efficacité, et l’hypothèse de schéma de relation universelle est toujours vérifiés, permettant de désigner de façon unique un attribut, sans aucune ambiguïté.
Remarque Ces restrictions sont nécessaires à assurer les fondements théoriques justes du modèle rela-tionnel. En pratique, on trouve plus de souplesse dans les outils :
– Les types complexes sont autorisés dans plusieurs SGBD pour peupler les relations : il s’agit en fait d’extensions de la théorie de base, en utilisant une logique objet. Le modèle utilisé est alors appelé relationnel-objet (Exemple : Oracle). Il permet une modélisation plus intuitive pour les concepteurs, mais le modèle utilisé en fond par le SGBD pour stocker ses données est toujours le relationnel.
– Dans tous les outils existants, on peut nommer deux fois le même attribut pour représenter des concepts différents (au sein d’une relation, un attribut n’apparaît toutefois qu’une seule fois. Par exemple, dans notre base de données on pourrait imaginer un attribut N OM qui désigne le nom d’une salle de cours, et le même attribut qui désigne le nom d’une personne ; ce serait une faute de conception, mais impossible à vérifier par les outils !
Un schéma de relation, ou de bases de données, est donc une boîte vide, avec une structure bien particulière, destinée à contenir des ensembles d’éléments possédant la même structure et donc sémanti-quement équivalents.

Tuples, relations et bases de données

Définition 3 (tuple, Relation et Base de Données) Soit R = A1:::An un schéma de relation. Un tuple sur R est un membre du produit cartésien DOM(A1) : : : DOM(An). Une relation r sur R est un ensemble fini de tuples. Une base de données d sur un schéma de base de données R = fR1; :::; Rng est un ensemble de relations fr1; :::; rng définies sur les schéma de relation de R.
De façon informelle, on peut donc voir un tuple comme une séquence de valeurs, prises par les attributs du schéma de relation. Si t est un tuple défini sur un schéma de relation R, et X un sous-ensemble de R, on peut restreindre t à X en utilisant l’opération de projection, notée t[X].
Exemple 3 Le tableau suivante représente graphiquement une relation etudiants sur le schéma ET U DIAN T .
On suppose que le numéro de formation est une référence vers une autre table qui décrit les formations.
Si on nomme t1 le premier tuple, alors t1[N OM] = Codd, t1[N U M; AGE] = (28; 20). L’ensemble de toutes les relations “peuplées“” par des tuples constitue la base de données.

Langages de requêtes et de mises à jour

Plusieurs langages ont été définis pour l’interrogation et la manipulation des données dans le modèle relationnel. Le résultat d’une requête est toujours une relation : les langages diffèrent sur la façon de définir la relation en sortie. Ils sont de deux sortes :
– les langages procéduraux : cela signifie que, pour obtenir les réponses à sa requête, il faut déterminer où et comment aller rechercher l’information parmi les relations de la base. On définit la procédure devant être exécutée par le programme. Le langage procédural du modèle relationnel est l’algèbre relationnel. Il s’agit d’un ensemble d’opérateurs algébriques unaires et binaires applicables à des relations et retournant des relations : ils peuvent donc être composés pour exprimer le résultat souhaité.
– déclaratif : pour obtenir les réponses à sa requête, il faut caractériser précisément le résultat que l’on veut, sans se soucier de la méthode utilisée par le programme pour accéder aux données. C’est grâce à des expressions logiques qu’on détermine le résultat souhaité : c’est le cas du calcul relationnel de tuple (qui manipule des tuples dans des expressions logiques) ou de domaine (qui manipule des variables parcourant les domaines), ou encore du DATALOG (admettant la récursivité).
Le SQL correspond à l’implantation du calcul relationnel de tuple : c’est donc un langage déclaratif, possédant de nombreuses extensions pour faciliter l’usage et augmenter le pouvoir d’expression.

1 Introduction 
2 Présentation du modèle relationnel 
2.1 Introduction
2.2 Structure
2.2.1 Attributs, valeurs et domaines
2.2.2 Schémas de relations, schémas de bases de données et première forme normale
2.2.3 Tuples, relations et bases de données
2.3 Langages de requêtes et de mises à jour
3 Contraintes d’intégrité dans le modèle relationnel
3.1 Généralités
3.2 Les principales dépendances de données
3.2.1 Dépendances fonctionnelles et clés
3.2.2 Dépendances d’inclusion
3.3 Inférence, fermetures et couvertures de contraintes
3.3.1 Inférence de dépendances fonctionnelles
3.3.2 Inférence de dépendances d’inclusion
3.3.3 Couvertures des DF et des DI
4 Conception de bases de données 
4.1 Anomalies de mise à jour et redondance
4.2 Les pertes d’information
4.2.1 Perte de données
4.2.2 Perte de DF
4.3 Les principales formes normales
4.3.1 Au delà des dépendances fonctionnelles
4.4 Comment normaliser une relation
4.4.1 Algorithmes de synthèse
4.5 Convertir un schéma Entité/Association en schéma relationnel
4.5.1 Rappel : Le modèle Entité-Association
4.5.2 Traduction E/A vers relationnel