INFO710 : Compléments de base de données

De Wiki du LAMA (UMR5127)

Ce wiki est un complément de cours pour le cours "info-710 : compléments de bases de données". J'encourage tous les étudiants à y participer en l'augmentant et le corrigeant au fur et à mesure de l'avancement du cours. Pour pouvoir modifier les pages, inscrivez-vous pour obtenir un login et mot de passe. (Please, utilisez votre vrai nom...)

Vous pouvez aller voir ce guide pour vous familiariser avec les wikis.


Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter.





Sommaire

Organisation des séances

Comme vous n'êtes pas nombreux, le cours sera entièrement en mode cours / TD.

  • première séance (08/09/2008) : introduction, entités et attributs.
  • deuxième séance (15/09/2008) : clés, associations et cardinalités ; début du TD1.
  • troisième séance (22/09/2008) : fin du TD1.
  • quatrième séance (29/09/2008) : un peu de SQL.
  • cinquième séance (06/10/2008) : TD2.
  • sixième séance (13/10/2008) : fin du TD2, cours sur l'algèbre relationnelle.
  • septième séance (20/10/2008) : TP1.
  • huitième séance (3/11/2008) : cours (algèbre relationnelle), TD3.
  • neuvième séance (10/11/2008) : TD3.
  • dixième/onzième séance (17/11/2008) : dépendances fonctionnelles, axiomes de Armstrong et recouvrements, TD4.
  • douzième séance (24/11/2008) : fin TD4.
  • treizième séance (24/11/2008) : TP2.
  • quatorzième séance (01/12/2008) : décompositions sans perte d'information, forme normale de Boyce-Codd, début TD 5.
  • quinzième séance (01/12/2008) : TP2.
  • seizième séance (08/12/2008) : TD5 (sans le dernier exercice sur la 3èmes forme normale).
  • dix-septième séance (08/12/2008) : TP2.

Les support de TD et TP


Complément pour le TP 2

Plusieurs d'entre vous semblent avoir des problèmes avec les dates... Voici un tout petit exemple de fichier perl qui interroge une base de données et affiche :

  • toutes les interventions prévues,
  • demande une date à l'utilisateur et affiche toutes les intervention dans un intervalle de 15 jours après la date choisie.

Regardez comment ce script fonctionne pour comprendre comment vous pouvez gérer les dates... Pour les fonctions disponibles sur les données de type date, je vous renvoie à la documentation de PostgreSQL.

#!/usr/bin/perl -w
use DBI;
$dsn   = "dbi:Pg:database=tp2-essai";
$login = "essai";
$mdp   = "essai";

$dbh = DBI->connect($dsn, $login, $mdp) or die "Echec de la connexion\n";


print "\n\n\nListe des interventions\n\n";
$requete = "SELECT date, type FROM interventions ORDER BY date;";
print "\n  ##DEBUG## la requete sera \"$requete\".\n\n";
$sth = $dbh->prepare($requete);
$sth->execute();

$i=0;
while (($date,$type) = $sth -> fetchrow_array) {
  $i++;
  print "Intervention $i :\n";
  if (($annee,$mois,$jour) = ($date =~ /(....)-(..)-(..)/)) {
    print "  Date : $jour/$mois/$annee\n";
    print "  Type : $type\n\n";
  }
}
$sth -> finish;


print "\n\n\nListe des interventions dans un intervalle de 15 jours après une date donnée :\n";
print "  Date : ?  (jj/mm/aaaa)  ";
$d = <STDIN>;
chomp($d);

($jour,$mois,$annee) = ($d =~ /(..)\/(..)\/(....)/) or die "Erreur de saisie...\n";
$jour = $1;
$mois = $2;
$annee = $3;
$datedebut = "date '$annee/$mois/$jour'";
$datefin = "$datedebut + interval '15 days'";
$requete = "SELECT date, type FROM interventions WHERE date > $datedebut AND date < $datefin ORDER BY date;";
print "  ##DEBUG## la requete sera \"$requete\".\n";
$sth = $dbh->prepare($requete);
$sth->execute();

$i=0;
while (($date,$type) = $sth -> fetchrow_array) {
  $i++;
  print "Intervention $i :\n";
  if (($annee,$mois,$jour) = ($date =~ /(....)-(..)-(..)/)) {
    print "  Date : $jour/$mois/$annee\n";
    print "  Type : $type\n\n";
  }
}
$sth -> finish;

$dbh -> disconnect;

Introduction

Présentation, qu'est-ce qu'une base de données

Voici une définition possible de base de données (Richard Grin) :

"une base de données est un ensemble structuré de données enregistrées dans un ordinateur et accessibles de façon sélective par plusieurs utilisateurs."

Donc, il s'agit d'un ensemble de données qui sont :

  • structurées : ça n'est pas mon bureau,
  • enregistrées dans un ordinateur : ça n'est pas la BU,
  • accessibles de façon sélective : ça n'est pas un fichier pdf,
  • par plusieurs utilisateurs : ça n'est pas un fichier dans un tableur.

On pourrait rajouter les choses suivantes :

  • modifiables par plusieurs utilisateurs en même temps (ça n'est donc pas un fichier tableur sur un système de fichiers partagé),
  • accessibles de manière fine (ça n'est pas un catalogue),
  • dont la gestion est possible (tous les utilisateurs ne peuvent pas forcement faire la même chose).


Exercice : cherchez des exemples pour souligner l'importance de chaque point.

Trouvez-vous d'autres aspects à rajouter ?


Historique

Un rapide survol des développements des BD :

  • préhistoire : avant même les ordinateur, le problème de stocker, gérer et utiliser de grandes quantités de données c'est posé. (recensement, bibliothèques, cadastre etc.)
  • années 60 : l'informatique devient accessible pour les entreprises. Deux modèles (modèle hiérarchique et modèle réseau) sont développés pour gérer des banques de données. Un problème est que l'utilisateur doit connaître les détails de l'implantation de ces systèmes pour pouvoir les utiliser.
  • au début des années 70 : E. F. Codd propose un nouveau modèle qui sera à la base de la plupart des SGBD suivants : le modèle relationnel. Ce modèle a l'avantage d'abstraire la couche informatique et permet donc l'étude théorique des problèmes liés à la représentation des données et leur utilisation.
  • 1976 : apparition du modèle "entités / relation" pour faciliter la conception de BD à un niveau plus élevé.
  • milieu des années 80 : le langage SQL (Structured Querry Language) devient un standard.
  • milieu des années 90 : développement de l'internet, demande croissante d'outils pour gérer des BD à distance.
  • fin des années 90 : développement de SGBD ouvert (MySQL, PostgreSQL).
  • actuel : de nouveau problèmes apparaissent à cause de la taille des BD existantes. Une gestion fine et des algorithmes très efficaces sont nécessaires pour pouvoir accéder à certain projets (génome, espace etc.)


Gestion d'une base de données

Le terme "base de données" ("BD" ou "BDD") est généralement réservé aux données, alors que la partie logicielle permettant l'utilisation d'une BDD est appelée "système de gestion de bases de données" (ou "SGBD" pour les intimes). La version anglaise est database management system ("DBMS").

Un SGBD doit permettre :

  • une independance vis à vis de la représentation physique des données
  • un accès logique (sémantique) à toute partie des données
  • de garantir la cohérence des données et d'éviter la redondance
  • un niveau d'abstraction pour permettre à des non-specialistes d'utiliser les données
  • une couche algorithmique transparente pour augmenter l'efficacité sans rendre la manipulation plus complexe
  • une administration fine et centralisée des données et des utilisateurs
  • de garantir la sécurité des données

Voici quelques exemples de SGBD importants :

  • PostgreSQL, entièrement libre et gratuit,
  • MpSQL, un autre logiciel libre populaire,
  • Access, le gestionnaire de bases de données de Microsoft,
  • Oracle,
  • ...


Modèle client/serveur

Sans rentrer dans les détails, on peut faire une distinction entre

  • l'ordinateur serveur (unique)
  • les ordinateurs clients (autant que d'utilisateurs)

Le serveur est une machine (souvent dédiée à une tache unique) qui héberge les bases de données et répond aux requêtes des utilisateurs. Cette machine doit être accessible de l'extérieur (par le réseau) et fonctionne en permanence.

Les clients sont les utilisateurs, qui peuvent interoger le serveur, rajouter ou supprimer des données. Chaque client utilise sa propre machine.

Dans notre cas, le serveur sera la machine appelée eco.univ-savoie.fr accessible uniquement depuis le réseau local de l'université de Savoie. (Si vous êtes chez vous, il faudra utiliser le vpn...)

Premiers exemples

Exercice : donnez quelques exemples détaillés de BD. Quels types de recherches fines pourriez-vous effectuer sur de telle BD ? Quels problèmes peuvent se produire, et quelle solution envisagez-vous ?

Représentation graphique de la structure d'une BDD (modèle conceptuel des données)

Le but de cette représentation est de donner la structure de notre BD indépendemment d'un quelconque SGBD. Comme en programmation, il est important de réfléchir avant de commencer à coder, de peur de faire n'importe quoi...

Img-01.png

un (mauvais) exemple de morceau de BDD

Entités et attributs

Entités

Une entité est une catégorie d'objets de même nature : des étudiants, des livres, des maisons, des crayons etc. Pour chaque type d'objet que l'on veut stocker dans la BD, il faut un attribut correspondant.

Les entités sont représentées par un rectangle :

Img-02.png

L'entité cours

Attributs

Les attributs sont des propriétés "importantes" (pour l'utilisateur de la BD) d'une entité. Les attributs sont listés sous le nom de l'entité comme suit :

Img-03.png

Notions de clé

Chaque objet d'une entité doit pouvoir être désigné de manière unique à partir d'un ou de plusieurs de ces attributs :

  • un cours est désigné par son code (info-710) et son année,
  • un enseignant par son nom et prénom (??)
  • un étudiant par son numéro d'étudiant
  • ...

Un ensemble d'attributs qui permet de désigner un élément d'une entité est appelé un clé candidate. Si cette clé est minimale (on ne peut pas enlever d'attributs sans perdre la propriété d'être une clé), on parle de clé minimale.

Chaque entité doit posséder une clé principale, choisie par le concepteur. Le (ou les) attributs de cette clé sont soulignés :

Img-04.png

Le choix d'une clé peut avoir de graves conséquences sur les performances. Il est de manière générale souhaitable d'avoir des clés comportant un seul attribut de type entier.

Exercice : est-ce qu'une clé principale peut prendre plusieurs fois la même valeur ?

Pour chacune des entités considérées précédemment, donnez les clés candidates et choisissez une clé principale.

Associations

Une association permet de relier deux entités entre elles : elles sont représentées par des rectangles aux coins arrondis. Les entités concernées sont reliées à l'association par un trait plein.

Les associations peuvent avoir des attributs, mais ce n'est pas obligatoire. Par exemple, on pourrait avoir une entité sport d'attributs nom, horaire et lieu, et une association sans attributs appelée pratique entre les entités etudiant et sport.

Fichier:Img-05.png

C'est kiki rajoute un joli dessin ?

Note : les associations n'ont pas de clé.

Cardinalités

La dernière information sur un diagramme de BD est la cardinalité : on indique combien de membres d'une entité peuvent être reliés à un élément d'une autre. On indique le minimum et le maximum, séparés par une virgule. La lettre n permet de préciser un nombre arbitraire. (Tous les n apparaissant dans un diagramme sont indépendants...)

Par exemple, dans le premier diagramme de cette partie,

  • chaque étudiant assiste au moins à un cours ("1,n")
  • chaque cours est suivi par plusieurs étudiants, éventuellement aucun ("0,n")
  • ...

Les cardinalités les plus courantes sont "0,n", "1,n", "0,1" et "1,1".

Exercice : donnez des exemples pour chacune de ces cardinalités.

Associations non binaires

---à faire---

Le langage SQL, première partie

Quoi

Le langage SQL (Structured Query Language) est le langage de bases de données le plus courant. C'est en 1986 que la première version standard de SQL est apparue. On appelle cette version SQL-86. En 1992, une deuxième version de la norme voit le jours (SQL-2), et une troisième version apparaît en 1999 (SQL-3). La version actuelle date de 2003 et est appelée SQL:2003. Tous les aspects du langage sont décrits dans un document officiel (la norme SQL) d'environ 3700 pages ! (Ce document est payant, mais les versions préliminaires sont disponibles gratuitement...)

Il existe de nombreux SGBD se basant sur SQL (MySQL, PostgreSQL, ...), mais aucun de respecte entièrement la norme : chacun rajoute quelques fonctionnalités pour faciliter la vie des utilisateurs. Il faut donc faire attention : certaines requêtes SQL fonctionnant avec MySQL ne sont pas forcement acceptées par PostgreSQL.


Le langage SQL peut se décomposer en plusieurs parties :

  • un langage de requêtes pour la recherche de données dans des bases existantes (ex : l'instruction SELECT);
  • un langage de manipulation pour créer ou modifier des données (ex : l'instruction INSERT)
  • un langage de définition des données (ex : l'instruction CREATE)
  • un langage de contrôle des données (ex : l'instruction REVOKE)
  • ...

Dans ce cours, nous nous intéresserons essentiellement aux trois premiers points.


La plupart des langages de programmation (C, Java, Perl, ...) possèdent également des bibliothèques de fonctions permettant d'accéder à des bases de données en utilisant le langage SQL.


Types de données

Les principaux types de données en SQL sont les suivants :

  • INTEGER : des entiers signés (sur 4 octets),
  • DECIMAL : des nombres décimaux représentés en virgule fixe. Le type DECIMAL(p,q) s'utilise pour les nombres décimaux avec p chiffres avant la virgule et q chiffres après la virgule.
  • REAL : des nombres réels, représentés en virgule flottante,
  • BIT : pour des valeurs booléennes,
  • CHAR(n) : pour les chaînes de caractères de taille fixée (exactement n),
  • VARCHAR(n) : pour les chaînes de caractères de taille variable (au plus n),
  • DATE et TIME : pour les dates ou les heures,
  • NULL est un type vide.


Définition des données

Remarques sur les mots clés et identificateurs

Les mots clés de SQL sont généralement écrits en majuscule (par exemple SELECT ...), même si la casse n'est pas importante. Il est conseillé de choisir une convention (tout en majuscules ou tout en minuscules) et de s'y tenir.

Les identificateurs servant de noms pour les tables, les attributs etc. peuvent comporter des majuscules, mais if faut alors utiliser des guillemets. Par exemples, les tables "Etudiant" et "etudiants" sont considérées comme différentes. Il est bien entendu fortement déconseillé d'avoir plusieurs tables dont les noms ne diffèrent que par la casse de certaines lettres...

On peut utiliser les identificateurs sans guillemets, mais ils sont alors transformés en minuscules. Par exemples, les identificateurs Etudiant, etudiant et "etudiant" désignent le même objet. Si on ne met pas de guillemets, on ne peut utiliser que des lettres dans l'identificateur...


Entités : tables

Les entités sont appelées tables en SQL. Pour déclarer l'entité etudiant dont les attributs sont nom, prenom et no-etu, on utilise la commande SQL suivante :

CREATE TABLE etudiant ( nom VARCHAR(50) , prenom VARCHAR(50) , "no-etu" CHAR(10) ) ;

Il est facile de dire que la clé principale sera le numéro d'étudiant :

CREATE TABLE etudiant (
  nom VARCHAR(50)                      ,
  prenom VARCHAR(50)                   ,
  "no-etu" CHAR(10)        PRIMARY KEY ,
  ) ;


-- autres contraintes : NOT NULL, UNIQ, CHECK...
-- clés étrangères
CREATE TABLE etudiant (
  "no-etu" CHAR(10)    PRIMARY KEY ,
  nom VARCHAR(50)      NOT NULL ,
  prenom VARCHAR(50) ,
  filiere CHAR(10)     REFERENCES "liste-filieres" (code)
) ;

Associations

On transforme les associations binaires en suivants les règles suivantes : on regarde les cardinalités maximales des deux entités autour de l'association,

  • si elles sont "1-n", alors l'association disparaît. On la remplace par une contrainte de clé étrangère en mettant la clé primaire de la table "_,n" dans la table "_,1". Si cette dernière est de type "1,1", la clé étrangère ne doit pas être vide. Les attributs de l'association sont déplacées dans la table "_,1".
  • si elles sont "1-1", on fait comme pour le cas "1-n", mais on rajoute une contrainte d'unicité sur la clé étrangère.
  • si elles sont "n-m", alors l'association devient une table. Comme clé primaire, on prend les deux clés des deux tables reliées par l'association. Ces nouveaux attributs sont également des clés étrangères. Les attributs de l'association deviennent des attributs de cette nouvelle table.


Manipulation des données

 INSERT INTO table( att1, att2, ..., attn)
        VALUES (val1, val2, ..., valn);
 INSERT INTO table( att1, att2, ..., attn)
        SELECT ... ;
 UPDATE TABLE SET att1 = e1 ,
                  att2 = e2 ,
                  ...
                  attn = en ,
   WHERE condition ;
 UPDATE TABLE SET (att1, att2, ..., attn) = (SELECT ...)
   WHERE condition ;
 DELETE FROM table
   WHERE condition ;


Interrogation des données

 SELECT

Modèle théorique : modèle relationnel

Rappels

L'idée du modèle abstrait est de remplacer la notion de table par celle, plus mathématique, de relation.

Définition
le produit cartésien des ensembles A1 et A2 (noté A_1\times A_2) est défini comme A_1\times A_2 = \{ (a_1,a_2)\ |\ a_1\in A_1\ \hbox{et}\ a_2\in A_2\}. Le produit de 3, 4 ou plus ensembles est définie de manière similaire.


Définition
une relation R entre les ensembles A1, ..., An est un sous-ensemble du produit cartésien A_1 \times \cdots \times A_n. Intuitivement, R=\{(a_1,...,a_n)\ |\ a_1, ..., a_n \ \hbox{sont en relation par } R\}.


Modèle relationnel des données

On modélise une table T dont les attributs sont de type A1, ..., An par une relation entre A1, ... et An. Si les attributs ont les noms t1, ... tn, on notera R(t1,...,tn) pour designer une telle relation.


Exemple : on pourra avoir une relation Dep(Code,Nom,Prefecture), ou plus succinctement, une relation D(c,n,p).


Algèbre relationnelle

  • union sur des relations de mêmes attributs : R\cup S
  • différence sur des relations de mêmes attributs : R\setminus S
  • produit cartésien sur des relations quelconques : R\times S
  • projection d'attributs quelconques : \Pi_{t_{i_1},...,t_{i_k}} (R)
  • sélection par une formule simple : σF(R)


Dépendances fonctionnelles

Une des difficultés lors de la création d'une base de donnée est d'éviter une redondance de l'information présente dans la base. Le problème principal lié à la redondance est celui de la cohérence des données : il faut garantir qu'on ne peut pas modifier un seul endroit où l'information est stockée. Par exemple, si un des attribut est l'adresse complète et un autre attribut est le département, il faut garantir que le code postal correspond bien au département. SQL permet de gérer ce genre de contraintes, mais pas forcement de manière simple. Il est donc préférable d'éviter la redondance dés la conception de la base.

Le problème de la taille des données (la redondance implique un besoin en mémoire plus gros) est relativement anecdotique pour la plupart des utilisations d'une base de données.


Les dépendances entre attributs est un des moyens utilisés pour étudier la redondance d'information.

Définition
si R(A,B,...) est un schéma relationnel, et si X et Y sont deux ensembles d'attributs, on dit que Y dépend fonctionnellement de X (et on écrit X \to Y si pour tous les éléments u,v de la table R, on a \Pi_X(u) = \Pi_X(v)  \Rightarrow  \Pi_Y(u)=\Pi_Y(v).


Comme le choix d'une clé, le choix des dépendances à imposer est à faire au moment de la conception, et il s'agit d'une notion sémantique...


Remarque : si X est une clé, alors on a toujours X\to Y pour n'importe quel ensemble Y d'attributs...


Axiomes de Armstrong

Certaines dépendances génèrent d'autres dépendances automatiquement. On aimerait pouvoir calculer toutes les dépendances satisfaites par une table.

Fait
les 3 propriétés suivantes sont appelées axiomes de Armstrong:
  • réflexivité : si Y\subseteq X alors X\to Y est valide,
  • augmentation : si X\to Y est valide, alors X,Z\to Y,Z est aussi valide,
  • transitivité : si X\to Y est valide et si Y\to Z est valide, alors X\to Z est aussi valide.


Ces axiomes permettent de déduire d'autres principes généraux. Par exemple :

  • si X\to Y et X\to Z alors $X\to Y,Z</math>
  • ...


Théorème
les axiomes de Armstrong sont complets. Autrement dit, si \mathcal{F} est un ensemble de dépendances, et si toutes les tables qui satisfont \mathcal{F} satisfont également X\to Y, alors on peut déduire la dépendance X\to Y uniquement à partir de \mathcal{F} et des axiomes de Armstrong.

Remarque : la contraposé de ce théorème garantit qu'une dépendance ne peut pas se déduire d'autres dépendances ssi il y a une table contre-exemple...


Calcul des recouvrements

Si \mathcal{F} est un ensemble de dépendances, l'ensemble de toutes les dépendances générées (appelé \mathcal{F}^+ par \mathcal{F} est potentiellement de taille exponentielle par rapport à la taille de \mathcal{F}. Par exemple, si on prend \mathcal{F} = \{A\to B_1, A\to B_2, \dots, A\to B_n\}...

Par contre, si X est un ensemble d'attributs, le calcul de X + (l'ensemble des attributs A tels que X\to A\ \in\ \mathcal{F}^+ peut se faire en temps linéaire. Comme on a X\to Y \ \in\ \mathcal{F}^+ ssi $Y\subseteq X^+</math>, cet algo remplace avantageusement le calcul de \mathcal{F}^+.

Algorithme : on va calculer une suite X_0, \dots , X_n d'ensembles d'attributs, et le dernier terme de cette suite sera exactement X +  :

  • on initialise X_0 = X\!
  • on calcule X_{i+1} = X_{i} \cup \{ A\ |\ Y\to A,Z \in \mathcal{F}, Y\sub X_i\}.

Le calcul s'arrête lorsque Xi = Xi + 1.


Remarque : il faut quand même transformer ça en véritable algo, et il faut faire attention si on veut effectivement obtenir un algo linéaire.


Définition 
  • si \mathcal{F} et \mathcal{G} sont deux ensembles de dépendances, on dit que \mathcal{F} et \mathcal{G} sont équivalents si \mathcal{F}^+ = \mathcal{G}^+. On dit aussi que $\mathcal{G}</math> est un recouvrement de \mathcal{F}.
  • un ensemble \mathcal{F} de dépendances est minimal si les trois propriétés suivantes sont vérifiées:
    • les dépendances de \mathcal{F} n'ont qu'un seul attribut à droite de la flèche
    • si on enlève une dépendance de \mathcal{F}, l'ensemble obtenu n'est pas équivalent à \mathcal{F}
    • si X\to Y est dans \mathcal{F}, et si A\in X, alors si on remplace X\to Y par X\setminus \{A\}\to Y, l'ensemble obtenu n'est pas équivalent à \mathcal{F}.


Propriété
si \mathcal{F} est un ensemble de dépendances, on peut toujours trouver un ensemble minimal équivalent à \mathcal{F}. Un tels ensemble est appelé recouvrement minimal de \mathcal{F}.

Pour trouver un recouvrement minimal, on se débrouille pour satisfaire les 3 propriétés dans l'ordre...


Remarque : un tels ensemble n'est pas unique ; et son cardinal n'est pas unique non plus:

  • A,B\to C, A\to B et B\to A : pour l'étape 3, on peut supprimer A ou B dans la première dépendance, mais pas les deux à la fois,
  • A\to B, A\to B, B\to A, A\to C, C\to A et B\to C : pour l'étape 2, on peut supprimer B\to C ou bien B\to A et A\to C.

Formes normales

Décompositions sans perte d'information

Décompositions sans perte de dépendances

Forme normale de Boyce-Codd

3ème (et 2ème) forme normale

Le langage SQL, deuxième partie

 --- PAS FAIT ---

Vues

Transactions

Contraintes

Déclencheurs

Intégration avec d'autres outils

Utilisation d'une base de données en Perl avec DBI

cf TP2.

Quelques références

Outils personnels