- une base de données est une collection de données inter-reliées. C'est une entité cohérente logiquement et véhiculant une certaine sémantique,
- un Système de Gestion de Bases de Données (SGBD) est un ensemble de programmes qui permettent à des utilisateurs de créer et maintenir une base de données. Les activités supportées sont la définition d'une base de données (spécification des types de données à stocker), la construction d'une base de données (stockage des données proprement dites) et la manipulation des données (principalement ajouter, supprimer, retrouver des données). Les SGBD commerciaux les plus connus sont Oracle, Sybase, Ingres, Informix et DB2,
- un SGBD sépare la partie description des données, des données elles mêmes. Cette description est stockée dans un dictionnaire de données (également géré dans le SGBD) et peut être consultée par les utilisateurs,
- un modèle de données est un ensemble de concepts permettant de décrire la structure d'une base de données. La plupart des modèles de données incluent des opérations permettant de mettre à jour et questionner la base. Le modèle de données le plus utilisé est le modèle relationnel,
- un schéma de base de données (ou compréhension ou intension) est la description des données à gérer. Il est conçu dans la phase de spécification et est peu évolutif (pratiquement statique),
- une extension d'une base de données correspond aux données de la base à un instant donné. Par définition cet état est dynamique.
Nous donnons ici les caractéristiques souhaitables des SGBD qui ne sont pas forcément prises en compte par les SGBD commerciaux.
1- Contrôler la redondance d'informations
La redondance d'informations pose différents problèmes (coût en temps, coût en volume et risque d'incohérence entre les différentes copies). Un des objectifs des bases de données est de contrôler cette redondance, voire de la supprimer, en offrant une gestion unifiée des informations complétée par différentes vues pour des classes d'utilisateurs différents.
2- Partage des données
Une base de données doit permettre d'accéder la même information par plusieurs utilisateurs en même temps. Le SGBD doit inclure un mécanisme de contrôle de la concurrence basé sur des techniques de verrouillage des données (pour éviter par exemple qu'on puisse lire une information qu'on est en train de mettre à jour).
Le partage des données se fait également par la notion de vue utilisateur, qui permet de définir pour chaque classe d'utilisateurs la portion de la base de données qui l'intéresse (et dans la forme qui l'intéresse).
3- Gérer les autorisations d'accès
Une base de données étant multi-utilisateurs, se pose le problème de la confidentialité des données. Des droits doivent être gérés sur les données, droits de lecture, mise à jour, création, ... qui permettent d'affiner la notion de vue utilisateur.
4- Offrir des interfaces d'accès multiples
Un SGBD doit offrir plusieurs interfaces d'accès, correspondant aux différents types d'utilisateurs pouvant s'adresser à lui. On trouve des interfaces orientées utilisateur final (langages de requêtes déclaratifs comme SQL avec mise en oeuvre graphique, interface de type formulaire, ...) ou bien orientées programmeurs d'applications (interface avec des langages de programmation classiques comme par exemple l'approche SQL immergé ou "embedded SQL").
5- Représenter des relations complexes entre les données
Un SGBD doit permettre de représenter des données inter-reliées de manière complexe. Cette facilité s'exprime à travers le modèle de données sous-jacent au SGBD. Chaque modèle de données offre ses propres concepts pour représenter les relations. On peut citer les modèles hiérarchique, réseau (première génération de modèles), relationnel (génération actuelle), sémantiques (ou orientés vers la conception tel que Entité-Association, Z, ...) ou orienté-objet (la génération future ?).
6- Vérifier les contraintes d'intégrité
Un schéma de base de données se compose d'une description des données et de leurs relations ainsi que d'un ensemble de contraintes d'intégrité. Une contrainte d'intégrité est une propriété de l'application à modéliser qui renforce la connaissance que l'on en a. On peut classifier les contraintes d'intégrité, en contraintes structurelles (un employé a un chef et un seul par exemple) et contraintes dynamiques (un salaire ne peut diminuer). Les SGBD commerciaux supportent automatiquement un certain nombre de contraintes structurelles, mais ne prennent pas en compte les contraintes dynamiques (elles doivent être codées dans les programmes d'application).
7- Assurer la sécurité et la reprise après panne
Une base de données est souvent vitale dans le fonctionnement d'une organisation, et il n'est pas tolérable qu'une panne puisse remettre en cause son fonctionnement de manière durable. Les SGBD fournissent des mécanismes pour assurer cette sécurité. Le premier mécanisme est celui de transaction qui permet d'assurer un comportement atomique à une séquence d'actions (elle s'effectue complètement avec succès ou elle est annulée). Une transaction est une séquence d'opérations qui fait passer la base de données d'un état cohérent à un nouvel état cohérent. L'exemple typique est celui du débit-crédit pour la gestion d'une carte bancaire. Ce mécanisme permet de s'affranchir des petites pannes (style coupure de courant).
En ce qui concerne les risques liés aux pannes disques, les SGBD s'appuie sur un mécanisme de journalisation qui permet de regénérer une base de données automatiquement à partir d'une version de sauvegarde et du journal des mouvements.
La plupart des SGBD suivent l'architecture standard Ansi/Sparc qui permet d'isoler les différents niveaux d'abstraction nécessaires pour un SGBD.
Elle est définie sur trois niveaux :
- niveau interne ou physique : décrit le modèle de stockage des données et les fonctions d'accès
- modèle conceptuel ou logique : décrit la structure de la base de données globalement à tous les utilisateurs (limite la redondance). Le schéma conceptuel est produit par une analyse de l'application à modéliser et par intégration des différentes vues utilisateurs. Ce schéma décrit la structure de la base indépendament de son implantation
- niveau externe : correspond aux différentes vues des utilisateurs. Chaque schéma externe donne une vue sur le schéma conceptuel à une classe d'utilisateurs.
Le SGBD doit être capable de faire des transformations entre chaque niveau, de manière à transformer une requête exprimée en terme du niveau externe en requête du niveau conceptuel puis du niveau physique.
La plupart des SGBD ne séparent pas complètement ces trois niveaux, mais respectent néanmoins ces principes de séparation.
L'architecture à trois niveaux permet de supporter le concept d'indépendance données - programmes, c'est à dire la capacité de modifier le schéma de la base de données à un niveau donné, sans remettre en cause le schéma aux niveaux supérieurs :
- indépendance logique : on peut changer le niveau conceptuel sans remettre en cause les schémas externes ou les programmes d'application. L'ajout ou le retrait de nouveaux concepts ne doit pas modifier des éléments qui n'y font pas explicitement référence,
- indépendance physique : on peut changer le schéma physique sans remettre en cause le schéma conceptuel (et les schémas externes). On peut modifier l'organisation physique des fichiers, rajouter ou supprimer des méthodes d'accès.
Le modèle relationnel, contrairement à ces prédécesseurs, permet un certain niveau d'indépendance sans aller jusqu'à une indépendance complète.
Le modèle relationnel de données a été défini en 1970 par Codd et les premiers systèmes commerciaux sont apparus au début des années 80. Le modèle relationnel est simple (3 concepts), facile à appréhender, même pour un non spécialiste et repose sur de solides bases théoriques qui permettent notamment de définir de façon formelle les langages de manipulation associés.
Le modèle relationnel représente l'information dans une collection de relations. Intuitivement, on peut voir une relation comme une table à double entrée, voire même comme un fichier. Chaque ligne de la table (appelée nuplet ou tuple) peut être vue comme un fait décrivant une entité du monde. Une colonne de la table est appelée un attribut.
- un domaine D est un ensemble de valeurs atomiques. Le terme atomique signifie que ces valeurs sont considérées comme insécables au niveau du modèle.
- un schéma de relation R, dénoté par R(A1, A2, ..., An), est un ensemble d'attributs R = {A1, A2, ..., An}. A chaque attribut Ai est associé un domaine Di, Ai indiquant le rôle joué par le domaine Di dans la relation R. Un schéma de relation décrit une relation et représente l'intension de celle-ci. Le degré de la relation est le nombre d'attributs de celle-ci.
Exemple :
ETUDIANT(Nom, No-ss, adresse, age, diplôme)
- une relation r sur le schéma de relation R(A1, A2, ..., An) est un ensemble de nuplets r= {t1, t2, ..., tn}. r est souvent appelée extension du schéma R.
On peut également définir une relation à partir du produit cartésien des domaines de son schéma R :
r(R) inclus-ou-egal dom(A1) X dom( A2) X ...X dom(An)
Il est important de noter qu'un schéma de relation est quasi invariant dans le temps, alors que l'extension représente les données présentes à un instant donné dans la base.
- une relation est un ensemble de nuplets, il n'y a donc pas de notion d'ordre sur les nuplets,
- par contre un nuplet est un séquence ordonnée d'attributs,
- une valeur d'attribut est atomique mais peut être éventuellement nulle (valeur particulière qui indique que la valeur est manquante).
Un schéma de base de données est un ensemble de schémas de relation S = {R1, R2, ..., Rn} et un ensemble de contraintes d'intégrité CI. Une contrainte d'intégrité est une propriété du schéma, invariante dans le temps. On peut distinguer plusieurs catégories de contraintes. Les contraintes structurelles, définissent plus précisément la structure des associations entre les données (le modèle de données les supporte en partie) et les contraintes sur les valeurs donnent des relations entre les données (un chef gagne plus que ses subordonnés). La plupart des contraintes ne sont pas supportées pas le modèle de données et doivent donc être codées par les programmeurs dans des programmes d'application.
- contrainte d'intégrité sur les clés :
Par définition, tous les nuplets d'une relation sont distincts deux à deux (puisqu'il s'agit d'un ensemble). Il est également intéressant de définir des sous-ensembles du schéma qui permettent d'identifier de manière unique un nuplet (par exemple dans l'exemple de l'étudiant, l'attribut No-ss permet d'identifier un étudiant). Ces sous-ensembles du schéma s'appellent des clés. Le système doit donc garantir l'unicité des valeurs de clé (un seul nuplet étudiant peut avoir une valeur de No-ss donnée).
Il peut y avoir plusieurs clés pour une même relation (elles sont alors appelées clés candidates) et on choisit le plus souvent une clé particulière dite clé primaire qui servira d'identification privilégiée des nuplets. Cette clé sera indiquée de manière graphique en mettant en gras les attributs la composant.
Par exemple :
ETUDIANT(Nom, No-ss, adresse, age, diplôme)
- contrainte d'intégrité sur les entités : une clé primaire ne peut contenir de valeur nulle.
- contrainte d'intégrité référentielle :
C'est une contrainte exprimée entre deux relations. Intuitivement cela consiste à vérifier que l'information utilisée dans un nuplet pour désigner un autre nuplet est valide, notament si le nuplet désigné existe bien. Par exemple, si on considère une relation EMPLOYE(no-ss, nom, adresse, rôle, no-dept) et une relation DEPARTEMENT(no-dept, nom, no-ss-chef), un nuplet de EMPLOYE référence un nuplet de DEPARTEMENT via l'attribut no-dept (numéro de département) et un nuplet de DEPARTEMENT référence un nuplet de EMPLOYE via l'attribut no-ss-chef (numéro sécurité sociale du chef de département). Il est important de s'assurer que les nuplets référencés existent bien. On peut noter qu'un nuplet peut référencer un autre nuplet de la même relation. Dans ce cas, no-dept et no-ss-chef sont appelés des clés étrangères, puisque se sont des attributs clés d'une autre relation.
Cette contrainte implique un ordre dans la création ou la destruction des entités, puiqu'on ne peut créer un département si le nuplet correspondant au chef n'a pas été créé et on ne peut détruire un chef de département si le département existe toujours (ou bien si on n'a pas mis un autre chef).
Ces contraintes d'intégrité sont exprimées en SQL au niveau du langage de définition.
Des langages de définition et de manipulation sont associés au modèle relationnel. De façon formelle on trouve deux classes de langages. Les langages algébriques et les langages prédicatifs. Ces langages sont strictement équivalents sur le plan de la puissance d'expression (n'importe quelle requête qui peut s'exprimer dans un de ces langages peut s'exprimer dans l'autre). Sur un plan industriel, les langages algébriques ont dérivé SQL (Structured Query Language, défini par IBM et qui s'impose comme la norme supportée par tout SGBD du commerce) et les langages prédicatifs QBE (Query By Example).
L'algèbre relationnelle se compose d'un ensemble d'opérateurs opérant sur des relations et produisant de nouvelles relations. Il est donc possible de construire de nouvelles informations à partir des relations de départ et d'une composition séquentielle d'opérateurs.
De nombreux opérateurs relationnels ont été proposés, on peut cependant présenter ici les plus courants. On peut classifier les opérateurs relationnels en trois catégories :
- les opérateurs unaires : affectation, sélection et projection
- les opérateurs binaires travaillant sur des relations de même schéma : union, intersection, différence
- les opérateurs binaires travaillant sur des relations de schémas différents : jointure, produit cartésien, théta-jointure, division
La présentation des opérateurs est illustrée par un exemple de gestion d'une base d'invitations. Cette base de données décrit les personnes invitées et les plats qui ont été servis. Elle est composée de trois relations :
REPAS(date,invité) donne la liste des invités qui ont été reçus et à quelle date
MENU(date,plat) donne le menu servi à chaque date
PREFERENCE(personne,plat) donne pour chaque personne ses plats préférés
N.B : les attributs "personne" et "invité" ont même domaine et les clés sont en gras.
a) Opérateurs unaires :
- affectation : R(A1, ..., An) <-- expression de sélection
l'affectation permet de sauvegarder le résultat d'une expression de recherche, ou bien de renommer une relation et ses attributs.
Exemple : Q1
- sélection : SELECTION condition-de-sélection (R)
la sélection prend en entrée une relation R définie sur un schéma SR et produit en sortie une nouvelle relation de même schéma SR ayant comme nuplets ceux de R satisfaisant à l'expression de sélection. Une expresion de sélection est une condition booléenne construite à partir des connecteurs logiques et, ou, non et de conditions simples (attribut de R - opérateur de comparaison - constante ou attribut de R - opérateur de comparaison - attribut de R)
- projection : PROJECTION A1, ..., An (R)
la projection prend en entrée une relation R définie sur un schéma SR et produit en sortie une nouvelle relation de schéma A1, ..., An (schéma inclus dans SR) ayant comme nuplets ceux de R restreints au sous-schéma A1, ..., An. Il faut noter que la cardinalité de la nouvelle relation est inférieure ou égale à celle de R, puisque des doublons ont pu être produits par la projection et sont donc supprimés (une relation est toujours un ensemble).
b) Opérateurs binaires de même schéma :
Les trois opérateurs ensemblistes opèrent sur des relations R et S de même schéma SRS.
- union : R UNION S
produit une nouvelle relation de schéma SRS ayant les nuplets de R et ceux de S (les doublons sont supprimés).
- intersection : R INTERSECTION S
produit une nouvelle relation de schéma SRS ayant les nuplets présents dans R et dans S.
- différence : R - S
produit une nouvelle relation de schéma SRS ayant les nuplets de R qui ne sont pas dans S. Attention, la différence n'est pas commutative.
Exemple : Q5
c) Opérateurs binaires de schémas différents :
Soient R et S deux relations définies sur les schémas SR et SS.
- jointure : R * S
Il faut que les schémas SR et SS aient une intersection SRS non vide. La relation produite a un schéma qui est l'union des schémas SR et SS et dont les nuplets sont la concaténation des nuplets de R avec ceux de S s'ils ont même valeur pour tous les attributs communs (c'est à dire ceux de SRS). On parle également de jointure naturelle ou équi-jointure.
Exemple : Q2
- produit cartésien : R X S
Il faut que les deux schémas SR et SS soient disjoints. La relation produite a un schéma qui est l'union des schémas SR et SS et dont les nuplets sont la concaténation des nuplets de R avec ceux de S. Attention le nombre d'éléments du produit cartésien est le produit des cardinalités des relations R et S!
Exemple : Q4
- théta-jointure : R * (condition) S
Cette opération non canonique est équivalente à un produit cartésien suivi d'une opération de sélection.
R * (condition) S = SELECTION condition (R X S)
Exemple : Q3
- division : R / S
R est définie sur un schéma SR composé des ensembles d'attributs X,Y (SR = X UNION Y) et S est définie sur un schéma SS composé de l'ensemble d'attributs Y (SS = Y). La relation produite est définie sur le schéma Sres (Sres = SR - SS = Y) et comprend tous les nuplets dont la concaténation avec tous les nuplets de S appartient à R (résultat X S inclus-ou-egal R).
La division peut se définir à l'aide du produit cartésien, de la différence et de la projection :
R(A1, .., Ap, Ap+1, ..., An)
S(Ap+1, ..., An)
R / S = R1 - R2 avec
R1 = PROJECTION A1, ..., Ap (R)
R2 = PROJECTION A1, ..., Ap ((R1 X S) - R)
Exemple : Q6
Un des grands intérets de l'algebre relationnelle est l'ensemble de propriétés des opérateurs ce qui permet l'optimisation des requetes.
d)Règles de passage de l'algèbre relationnelle vers SQL
Soient R(X) et S(Y) deux relations de schémas distincts, T(V,W), U(W,Z) deux relations ayant un ensemble d'attributs communs, Q1(X), Q2(X) deux relations de même schéma et P(W).
sélection SELECTION condition (R) --> select *
from R
where condition
projection PROJECTION A1, ..., An (R) --> select distinct A1, ..., An
from R
opérateurs Q1 UNION Q2, Q1 --> select * from Q1
ensemblistes Q1 INTERSECTION Q2 union, intersect, minus
Q1 - Q2 select * from Q2
jointure T * U --> select V, W, Z
from T, U
where T.W=U.W (en réalité égalité sur
tous les attributs communs)
produit R X S --> select R.*, S.*
cartésien from R, S
théta-jointure R* (condition) S --> select X, Y
from R, S
where condition
division T / P --> select V
avec P partie de T from T
group by V
having count(distinct W) >=
(select count(distinct W) from P)
Exemple complet de la base des invitations
Deux approches sont possibles pour établir un lien entre la logique du premier ordre et les bases de données :
(1) approche "intelligence artificielle" : BD déductives
Les faits élémentaires (données) et les propriétés générales (schéma ainsi que les règles d'intégrité et d'inférences) sont représentés par des axiomes d'une théorie du premier ordre. Répondre à une question revient donc à démontrer un théorême dans cette théorie.
Avantages : une question est résolue en dehors de toute interprétation et on peut utiliser des règles d'intégrité ou d'inférences (qui permettent de déduire des informations non stockées).
Inconvénients : problème de performances (il faut intégrer un démonstrateur de théorêmes) et représentation de l'information négative. La plupart du temps on utilise l'hypothèse du monde fermé ("Closed World Assumption") avec une méta-règle de négation par l'échec ("negation as failure"). Toute information manquante est considérée comme fausse et une information qu'on ne peut dériver est également considérée comme fausse.
(2) approche "classique" : BD relationnelle
Les propriétés générales (schéma seulement) sont considérées comme les axiomes d'une théorie du premier ordre, alors que les faits élémentaires (données) sont perçus comme une interprétation de cette théorie. Si cette interprétation vérifie tous les axiomes, elle constitue un modèle. Répondre à une question revient à chercher la valeur de vérité d'une formule relativement à l'interprétation. On distingue alors entre question fermée (sans variable libre) pour laquelle la réponse est vrai ou faux, et question ouverte (avec variable libre) pour laquelle la réponse sont les valeurs de l'interprétation pour lesquelles la question est vraie.
Avantages : on retrouve la théorie relationnelle classique
Inconvénients : pas de puissance supplémentaire
Nous présentons dans la suite cette deuxième approche, les BD déductives étant étudiées dans le cadre du cours de 3ème année. On rencontre deux classes de langages prédicatifs, ceux à variable nuplet (le domaine d'interprétation d'une variable est le nuplet) et ceux à variable domaine (le domaine d'interprétation d'une variable est le domaine).
Une expression générale du calcul relationnel à variable nuplet est de la forme :
{t1[A1], t2[A2], ..., tn[An] / COND(t1, t2, ..., tn, tn+1, tn+2, ..., tn+m)}
avec ti (de 1 à n+m) variables nuplets non nécessairement distinctes deux à deux, Ai sont des attributs de relations associées aux ti et COND est une formule du calcul relationnel à variable nuplet. L'expression de la forme ti[Aj] exprime la valeur du nuplet ti suivant l'attribut de nom Aj (terme de projection).
Une formule est construite à partir de prédicats atomiques (atomes) qui sont d'une des formes suivantes :
1) Un atome de la forme R(ti) où R est un nom de relation et ti est une A variable nuplet. Cet atome identifie le domaine de la variable ti comme celui de la relation de nom R.
2) Un atome de la forme ti[A] op tj[B] où op est un opérateur de comparaison classique, ti et tj des variables nuplets, et A, B des attributs des relations associées.
3) Un atome de la forme ti[A] op c ou c op tj[B], où c est une constante.
Une formule est constituée d'atomes connectés par les opérateurs logiques ET, OU, NON et se définit de la manière suivante :
1- Tout atome est une formule,
B 2- Si F1 et F2 sont des formules, alors (F1 et F2), (F1 ou F2), non(F1) sont des formules,
3- Si F est une formule, alors (ILEXISTE t) (F) est une formule avec t variable nuplet,
4- Si F est une formule, alors (QQSOIT t) (F) est une formule avec t variable nuplet.
NB : une variable est dite libre si elle n'est pas quantifiée dans sa portée, liée sinon.
Une expression générale du calcul relationnel à variable domaine est de la forme :
{x1, x2, ..., xn / COND(x1, x2, ..., xn, xn+1, xn+2, ..., xn+m)}
avec xi variables domaines (non nécessairement distinctes) d'attributs et COND est une formule du calcul relationnel à variable domaine.
Une formule est construite à partir d'atomes. Un atome peut être d'une des formes suivantes :
1) Un atome de la forme R(x1, x2, ..., xj) où R est le nom d'une relation de degré j et chaque xi est une variable. <x1, ..., xj> représente un nuplet de la relation R et xi la ième valeur dans le nuplet.
2) Un atome de la forme xi op xj où op est un opérateur de comparaison classique et xi, xj des variables domaines.
3) Un atome de la forme xi op c ou c op xj, où c est une constante.
Une formule est construite à partir des mêmes règles que celles définies pour le calcul relationnel à variable nuplet.
Problème : un mauvais schéma relationnel peut entrainer des anomalies lors des manipulations.
APPROVISIONNEMENT Produit Quantité Couleur Fournisseur Adresseparapluie 110 rouge Labaleine Paris
chapeau 50 vert Lemelon Lyon
sac à main 65 noir Toutcuir Lyon
parasol 15 jaune Labaleine Paris
ombrelle 5 rouge Labaleine Paris
ceinture 25 vert Letour Nantes
sac à main 65 noir Legrand Paris
Solutions :
- étude des dépendances entre données
- décomposition et normalisation des relations
R(X,Y,Z) un schéma de relation
X, Y, Z des ensembles d'attributs, Z pouvant être éventuellement vide
X -> Y : la connaissance d'une valeur de X détermine au plus une valeur de Y
propriété définie sur l'intension du schéma et non son extension (elle est donc invariante dans le temps et ne peut être extraite à partir d'exemples). C'est une propriété qui doit être extraite de la connaissance que l'on a de l'application à modéliser.
DF1 : réflexivité Y inclus-ou-egal X => X -> Y
DF2 : augmentation X -> Y => X,Z -> Y,Z
DF3 : transitivité X -> Y ET Y -> Z => X -> Z
DF4 : pseudo-transitivité X -> Y ET Y,W -> Z => X,W -> Z
DF5 : union X -> Y ET X -> Z => X -> Y,Z
DF6 : décomposition X -> Y ET Y Z => X -> Z
R(X,Y,Z) ET X -> Y => R(X,Y,Z) = R[X,Y] * R[X, Z]
- on peut toujours décomposer une relation suivant une dépendance fonctionnelle
- on ne peut décomposer une relation s'il n'y a pas de dépendance fonctionnelle
- la décomposition suivant une dépendance fonctionnelle ne perd pas d'information
- ce principe de décomposition binaire d'une relation est à la base de l'algorithme de décomposition
R(X,Y,Z) schéma de relation
X, Y, Z ensemble d'attributs avec Z éventuellement vide
A un attribut quelconque
- dépendance fonctionnelle élémentaire (DFE) :
une DF X -> Y avec X ne contenant pas Y est une DFE ssi
il n'existe aucun sous-ensemble de X ayant une DF sur Y
(X est la plus petite quantité d'information donnant Y)
- clé :
X est une clé de R ssi X -> Y,Z DFE
(une relation peut avoir plusieurs clés)
- A est attribut clé s'il appartient à au moins une clé de R
- A est attribut non clé s'il n'appartient pas à une clé de R
- A est transitivement dépendant de X s'il existe Y, Y ne contenant pas A tel que
X -> Y, Y -> A, ~(Y-> X), Y n'est pas inclus dans X
- A est directement dépendant de X s'il n'est pas transitivement dépendant
- A est pleinement dépendant de X si X -> A est une DFE
- A est partiellement dépendant de X si X -> A n'est pas une DFE
- la fermeture transitive F+ d'un ensemble F de dépendances fonctionnelles est l'ensemble des DFE qui peuvent être produites par application des axiomes d'Amstrong sur l'ensemble F.
Objectifs :
- définir une notion de "qualité" de schéma
- pouvoir comparer deux schémas de relation
Les formes normales définissent un ordre partiel sur les schémas de relation. On peut donc voir une forme normale comme une classe d'équivalence (on peut comparer deux schémas dans deux classes d'équivalence différentes mais pas dans la même). Il faut aussi noter que le seul élément qui est pris en compte par les formes normales est la non redondance d'informations d'un schéma. Selon les formes normales un "bon" schéma est un schéma sans redondance (ce qui ne veut pas forcément dire qu'il est efficace par exemple). Un schéma relationnel sans qualité particulière est appelé schéma en 1ère forme normale (on note 1FN) et si on rajoute certaines qualités on obtient les deuxième et troisième formes normales (on note 2FN et 3FN).
On ne présente ici que les formes normales dont la définition utilise exclusivement les dépendances fonctionnelles. Si on prend en compte d'autres dépendances entre données comme les dépendances multivaluées on obtient alors les 4FN et 5FN. La 3FN reste cependant l'objectif de normalisation le plus "classique".
1FN : une relation est en première forme normale ssi tout attribut a une valeur atomique (vrai par définition du modèle relationnel)
2FN : une relation est en deuxième forme normale ssi elle est en 1FN et si tous les attributs non clés sont pleinement dépendants des clés (toutes les dépendance entre une clé et un attribut non clé sont élémentaires)
3FN : une relation est en troisième forme normale ssi elle est en 2FN et si tous les attributs non clés sont directement et pleinement dépendants des clés (si tout attribut non clé ne dépend pas d'un autre attribut non clé)
3FNBCK (Boyce-Codd-Kent) : une relation est en 3FNBCK ssi elle est en 3FN et si les seules DFE sont celles de la forme C -> X avec C clé (seules les clés sont en partie gauche de DF).
Une manière de concevoir un schéma relationnel en troisième forme normale est de partir du schéma complet (ensemble de tous les attributs) et de décomposer cette "grosse" relation (appelée également relation universelle) suivant les dépendances fonctionnelles. Cette approche est appelée approche par décomposition. Le problème est d'ordonner l'ordre des décompositions de manière à obtenir un schéma en 3ème forme normale. En effet, chaque relation produite ne conserve qu'un certain nombre de DF (celles définies sur ses attributs propres) et n'est donc pas forcément en 3ème forme normale. De plus, l'ensemble des DF du schéma complet n'est pas forcément préservé.
Algorithme de décomposition :
entrée : un schéma relationnel (ensemble d'attributs) et un ensemble E de DF entre ses attributs
sortie : une ou plusieurs relations en 3FN dont la jointure redonne la relation initiale (par contre des DF de E ont pu être perdues)
principe : l'algorithme peut se voir comme la construction d'un arbre binaire. La racine de cet arbre est la relation à décomposer. L'arbre se construit récursivement de la manière suivante :
- on choisit une DF dfi dans l'ensemble E des DF
- le fils gauche du noeud racine est une relation composé de tous les attributs de dfi
- dfi est retirée de l'ensemble E
- le fils droit du noeud racine est une relation composée de tous les attibuts de la racine excepté ceux présents en partie droite de dfi
problèmes : la solution dépend du choix des DF selon lesquelles on choisit de décomposer et il ne préserve pas nécessairement les DF.
On sait néanmoins que toute relation admet une décomposition en 3FN qui préserve les DF.
Il existe un algorithme dit de synthèse qui permet d'obtenir une décomposition 3FN qui préserve les DF. Il est basé sur le calcul de la couverture minimale (ou irredondante) d'un ensemble de DF.
Exemple sur les formes normales :
Soit le schéma R = <{P, H, N, Y, T}, {P -> T; P, H -> Y; H, N -> P; H, Y -> N}>
- Ensemble des DFE engendrées :
H, N -> T
P, H -> N
H,N -> Y
H, Y -> P
P, H -> T
H, Y -> T
- on a donc trois clés potentielles (H, N; P, H; H, Y) :
H, N -> P, T, Y
P, H -> T, Y, N
H, Y -> N, P, T
- les attributs clés sont donc : H, N, P, Y
- et les attributs non clés sont : T
- par définition le schéma est en 1ère forme normale. Est il en 2ème forme normale ?
Non, car P, H -> T n'est pas une DFE (on a P -> T)
- R est donc en 1ère forme normale
- application de l'algorithme de décomposition :
ou bien :
On peut décrire l'architecture logicielle d'un SGBD de la manière suivante :
- le moniteur d'exécution a pour rôle de gérer l'interface d'accès du SGBD, les connections à la base, de retourner à l'extérieur les messages d'erreurs ou les résultats obtenus ainsi que d'enchainer les différentes opérations.
- l'analyseur a pour but d'effectuer les vérifications syntaxiques et sémantiques sur les commandes qu'on lui passe ainsi que de produire une représentation interne de ces commandes. Il s'agit la plupart du temps d'un arbre algébrique dont les noeuds feuilles représentent les relations sur lesquelles porte la commande et les noeuds non feuilles représentent les opérateurs algébriques qui s'appliquent sur ces relations) :
- le contrôleur vérifie que les commandes sont licites, c'est à dire que l'utilisateur a les droits requis pour les commandes effectuées, que les contraintes d'intégrité ne sont pas violées.
- l'optimiseur produit à partir de la représentation interne d'une commande, un plan d'exécution (séquence d'opérations de base sur la BD) optimum. L'optimisation utilise les propriétés algébriques des opérateurs ainsi que des fonctions de coût.
- le système d'exécution doit exécuter les plans d'exécution qui lui sont fournis. Cette exécution peut être interprétée (dans la plupart des cas) ou compilée (rarement). L'avantage de la compilation est qu'elle permet de ne pas effectuer les phases d'analyse, de contrôle et d'optimisation à chaque fois. Une commande compilée est cataloguée et peut être ensuite évaluée directement. Peu de SGBD commerciaux permettent une exécution compilée.
L'exécution d'une commande s'appuie sur la machine algébrique qui permet d'exécuter un ensemble d'opérateurs canoniques (sélection, projection, jointure, ...). Le gestionnaire des méthodes d'accès permet d'accéder efficacement aux données sur le disque et le gestionnaire des accès concurrents permet de contrôler l'accès multi-utilisateurs.
- le catalogue joue un rôle central dans le SGBD puisque c'est la structure de données qui centralise toute l'information nécessaire aux différents modules. Il contient notamment la description des relations, vues et contraintes d'intégrité, la description des utilisateurs avec leurs droits d'accès ainsi que la description des structures de stockage utilisées (placement des données sur le disque, index définis, ...). La plupart du temps, le catalogue est défini comme un ensemble de relations qui sont accessibles par les utilisateurs (s'ils en ont le droit) come toute relation.
Les requêtes algébriques sont évaluées à partir d'un ensemble canonique d'opérateurs. Généralement cet ensemble comprend la sélection, la projection, le produit cartésien et le produit (ou jointure). Toute expression algébrique se traduit en une composition de ces opérateurs canoniques. L'optimisation de cette expression consiste à trouver le meilleur ordonnancement possible des opérateurs relativement à un coût. Ce coût s'évalue généralement par trois critères qui sont le nombre d'entrées/sorties, le temps CPU et le nombre de buffers requis. Le résultat de l'optimisation s'appelle un plan d'exécution.
L'optimisation peut se faire en deux passes, une première s'appuyant sur les propriétés algébriques des opérateurs qui permet surtout de limiter la taille des relations manipulées et une seconde basée sur des fonctions de coût qui permet d'affiner l'optimisation en tenant compte des caractéristiques des relations et attributs manipulés (taille des relations, discriminance des attributs, connaissance des clés, existence de chemins d'accès efficaces, ...).
On peut représenter une requête sous forme d'un arbre algébrique dont les feuilles sont des relations et les non-terminaux des opérateurs canoniques. L'optimisation consiste à réorganiser l'arbre en utilisant les propriétés algébriques de façon à produire un arbre équivalent (c'est à dire produisant la même réponse) mais dont l'évaluation sera plus efficace.
L'idée de base est de réduire au maximum la taille des relations intermédiaires produites. Pour cela, il faut utiliser le plus possible les sélections et les projections et les faire le plus tôt possible. Il faut donc faire "descendre" les sélections et projections dans l'arbre et rajouter éventuellement des projections permettant de ne manipuler que les attributs effectivement utilisés dans l'expression.
1- Séquence de sélections :
SELECTION C1 and c2 ... and Cn(R) = SELECTION C1( SELECTION C2(...( SELECTION Cn(R))))
2- Commutativité de la sélection :
SELECTION C1( SELECTION C2(R)) = SELECTION C2( SELECTION C1(R))
3- Séquence de projections :
PROJECTION L1( PROJECTION L2(...( PROJECTION Ln(R)))) = PROJECTION L1(R)
4- Commutation de la sélection et de la projection :
PROJECTION A1, A2, ..., An( SELECTION C(R)) = SELECTION C( PROJECTION A1, A2, ..., An(R))
5- Commutativité de la jointure :
R * S = S * R
6- Commutation de la sélection et de la jointure (ou produit cartésien) :
à condition que C concerne seulement R
SELECTION C(R * S) = ( SELECTION C(R)) * S
à condition que C = C1 and C2 et C1 (C2) concerne seulement R (S)
SELECTION C(R * S) = ( SELECTION C1(R)) * ( SELECTION C2(S))
7- Commutation de la projection et de la jointure (ou produit cartésien) :
- L = {LR,LS} LR = R1, R2, ..., Rn LS = S1, S2, ..., Sm
C porte sur des attributs présents dans L
PROJECTION L(R * S) = PROJECTION LR(R) * PROJECTION LS(S)
- L = R1, ..., Rn, S1, ..., Sm
LRK = R1, ..., Rn, Rn+1, ..., Rn+k
LSP = S1, ..., Sm, Sm+1, ..., Sm+p
C porte sur Rn+1, ..., Rn+k, Sm+1, ..., Sm+p
PROJECTION L(R * S) = PROJECTION L(( PROJECTION LRK(R)) * ( PROJECTION LSP(S)))
8- Commutativité des opérations ensemblistes (union et intersection)
9- Associativité de la jointure, du produit cartésien, de l'union et de l'intersection :
O = { UNION , INTERSECTION , *, X}
(R O S) O T = R O (S O T)
10- Commutation de la sélection avec les opérateurs ensemblistes :
O = { UNION , INTERSECTION , -}
SELECTION C(R O S) = ( SELECTION C(R)) O ( SELECTION C(S))
11- Commutation de la projection avec les opérateurs ensemblistes :
O = { UNION , INTERSECTION , -}
PROJECTION L(R O S) = ( PROJECTION L(R)) O ( PROJECTION L(S))
Les étapes principales de l'algorithme sont les suivantes :
2-1 Séparer les sélections conjonctives en une séquence de sélections (règle 1)
2-2 Descendre les opérations de sélection le plus bas possible dans l'arbre (règles 2, 4, 6 et 10)
2-3 Réarranger les feuilles de l'arbre pour évaluer les sélections les plus restrictives d'abord (règle 9)
2-4 Combiner les produits cartésiens avec des expressions de sélection appropriées pour en faire des jointures
2-5 Faire des projections le plus tôt possible dans l'arbre (le cas échéant en en créant des nouvelles,
non explicites dans la requête) pour manipuler seulement l'information intéressante (règles 3, 4, 7 et 11)
2-6 Identifier les sous arbres qui peuvent être exécutés par un seul algorithme (les sélection - projection - jointure par exemple)
L'idée est d'utiliser des informations supplémentaires (stockées dans les catalogues de la base) pour minimiser certaines opérations. Parmi les différents ordonnancements possibles, on va chercher celui qui minimise la fonction de coût. Il faut noter que le traitement nécessaire à l'optimisation peut être long (notamment si la requête est complexe) et que cette approche est donc plus adaptée dans un environnement de compilation de requêtes.
Les paramètres principaux de la fonction de coût sont :
- le coût d'accès disque (le plus important)
- le coût de stockage des fichiers intermédiaires
- le coût de calcul
- le coût de communication (si les données ne sont pas toutes sur le même site)
Les informations utilisées pour chaque relation sont le plus souvent :
- site de stockage de la relation
- nombre de nuplets stockées (nt)
- nombre de blocs utilisés (nb)
- pour chaque attribut, son nombre de valeurs distinctes (nd)
Cette dernière information permet d'évaluer la sélectivité d'un attribut (nt / nd).
Un SGBD est par définition multi-utilisateurs, par conséquent l'exécution simultanée de plusieurs applications peut poser des problèmes d'accès concurrents (une même information étant manipulée par plusieurs utilisateurs à la fois). L'unité de concurrence est la transaction qui joue également un rôle vis à vis du contrôle de l'intégrité des données. Une base de données doit être cohérente avant et après une transaction. Par contre, la cohérence peut être violée pendant l'exécution d'une transaction.
Une transaction est une séquence d'opérations qui accèdent et modifient le contenu d'une base de données et qui est complètement exécutée ou pas du tout (unité atomique de traitement). Une transaction s'effectue soit complètement et alors les mises à jour qu'elle a effectuées sur la base de données sont validées, soit elle s'effectue incomplètement (annulation ou panne) et alors toutes les mises à jour effectuées depuis le début de la transaction sont invalidées.
Les propriétés d'une transaction sont les suivantes (ACID) :
- Atomicité : tout ou rien
- Cohérence : une transaction prend une base de données dans un état cohérent et la transforme dans une nouvelle base de données qui est dans un état cohérent (préservation de la cohérence)
- Isolation : les mises à jour faites par une transaction ne sont visibles à l'extérieur de celle-ci (pour les autres transactions) qu'après la validation de la transaction.
- Durabilité : après la fin d'une transaction, les mises à jour sont définitives même en cas de futurs problèmes matériels (grace au mécanisme de reprise)
On considère une transaction T1 qui consiste à annuler N réservations sur un vol V1 (X représente le nombre de places réservées sur le vol V1) et à réserver N places sur un vol V2 (Y représente le nombre de places réservées sur le vol V2). La transaction T2 réserve Mplaces sur le vol V1. L'exécution concurrente de T1 et T2 sans contraintes de synchronisation peut produire un certain nombre de problèmes dont les plus importants sont la perte d'opérations et les lectures impropres.
- perte d'opérations :
T1 T2
lire(X)
X := X-N
lire(X)
X := X+M
écrire(X)
lire(Y)
écrire(X) --> écrire(X:=X-N) est perdu par T1
Y := Y+N
écrire(Y)
- lectures impropres :
T1 T2
lire(X)
X := X-N
écrire(X)
lire(X)
X := X+M
lire(Y)
annulation T1
La valeur de X lue par T2 est incohérente car X a été lu après la mise à jour faite par T1 qui a été ensuite invalidée par l'annulation de T1.
Il faut fixer une propriété déterminant une exécution correcte de transactions concurrentes. Cette propriété est la sérialisibilité à savoir une exécution concurrente de transactions est correcte si elle est équivalente (produit le même résultat) à une exécution en série. Il faut noter que cette définition n'est pas constructive, elle ne donne pas de moyens de garantir la propriété.
La sérialisation est une propriété forte qui limite le parallélisme à l'exécution donc les performances. Certains SGBD comme Oracle propose des assouplissements de cette propriété basés sur des protocoles multi-versions.Une transaction peut échouer pour de nombreuses raisons :
- problème système,
- erreur dans la transaction (définie dans le programme) ou interruption volontaire de l'utilisateur,
- arrêt involontaire de la transaction (interblocage du à une demande croisée d'allocation de ressources avec une autre transaction),
- problème matériels (disque, ...).
Cet échec de la transaction peut entrainer une incohérence si une partie seulement des mises à jour ont été effectuées (ne respecte pas la propriété d'atomicité). Par conséquent, il faut restituer l'état antérieur de la base grace à un mécanisme de reprise.
La notion de transaction sert de granule de contrôle de la concurrence et permet également de faire des reprises sur erreurs logicielles (la base se trouve dans un état cohérent à chaque point observable). Ce mécanisme est appelé "reprise à chaud".
La vie d'une transaction dans le système peut se décrire de la manière suivante :
Les pannes matérielles ou logicielles graves ne peuvent se traiter par un simple mécanisme transactionnel. Le principe général est de garder un historique persistant de tout ce qui se passe sur la base de données. A partir de cet historique (appelé journal) et d'états antérieurs (sauvegardes) de la base de données, on peut reconstituer la base de données dans l'état cohérent qui précède la panne. Ce mécanisme est appelé "reprise à froid".
Le journal est donc un support sur disque qui maintient les informations nécessaires pour la reprise :
- début d'une transaction T,
- si écriture sur une donnée X : ancienne valeur, nouvelle valeur
- si lecture sur une donnée X : X
- fin d'une transaction T,
- point de reprise P.
Un point de reprise consiste à écrire sur disque les mises à jour des transactions validées (copie du buffer sur le disque). Ce mécanisme s'effectue périodiquement, toutes les N secondes, toutes les N transactions, ... Le journal est également sauvegardé sur disque à ce moment là.
On peut distinguer 2 grandes techniques pour assurer la sérialisibilité :
- approche pessimiste ou a priori (on fait en sorte que l'on ne puisse pas avoir d'exécution non correcte) : on trouve ici les techniques de verrouillage ou d'estampillage,
- approche optimiste ou a postériori (on laisse s'exécuter les transactions sans contraintes et on moment de la validation on vérifie qu'il n'y a pas de conflits avec les autres transactions).
De manière industrielle, la seule solution implantée est l'appoche par verrouillage.
Un verrou est une variable d'état associée à un objet X de la base et indiquant son état vis à vis des opérations de lecture / écriture.
Un verrou peut être binaire (deux états verrouillé ou libre avec deux opérations verrouiller(X) et libérer(X)) ou ternaire. Un verrou binaire est trop restrictif puisqu'un objet est bloqué pour toute opération que l'on veut effectuer sur lui, ce qui implique qu'on ne peut faire des lectures simultanées.
Un verrou ternaire permet 3 états, en lecture (ou partagé), en écriture, ou libre. Le verrou en écriture n'est alloué que si l'objet est libre, c'est à dire si aucune opération ni de lecture, ni d'écriture ne s'effectue sur cet objet. Le verrou en lecture est alloué si l'objet est libre ou si aucune opération d'écriture ne s'effectue sur lui (par contre des opérations de lecture peuvent se dérouler simultanément, ce qui nécessite de maintenir un compteur pour connaitre le nombre de transactions "lisant" cet objet).
Un protocole de verrouillage sans aucune contrainte sur l'allocation des verrous, ne permet pas de garantir la propriété de sérialisabilité. De nombreux protocoles ont été proposés, le plus classique étant le protocole de verrouillage à deux phases.
Dans ce protocole, toutes les acquisitions de verrous sont faites avant la première libération. On dit qu'il y a une phase d'expansion suivie d'une phase de libération.
Le protocole de verrouillage à 2 phases garantit la propriété de sérialisabilité mais ne permet pas d'éviter les situations d'interblocage. Un interblocage se produit lorsque une transaction est bloquée en attente de ressources provenant d'une autre transaction (et réciproquement). Plus généralement, un interblocage peut se passer entre n transactions. Deux techniques sont possibles, une pessimiste et une optimiste :
- prévention : on donne un ordre total sur les transactions et on vérifie que les attentes entre transactions sont conformes à cet ordre (approche par estampillage),
- détection : on maintient un graphe de dépendances entre les transactions qui permet de détecter les situations d'interblocage (présence d'un cycle dans le graphe). Il faut alors tuer ("assassiner") une des transactions participant à l'interblocage. Le choix se fait de manière heuristique (transaction ayant le moins de mises à jour à défaire, transaction la plus récente, ...). C'est cette technique qui est implantée dans les systèmes commerciaux.
Différentes granularités de contrôle de la concurrence sont possibles :
- valeur d'un attribut de n-uplet,
- un n-uplet,
- une page ou bloc,
- une relation,
- une base.
Plus la granularité est petite, plus le niveau de concurrence augmente. Par contre le niveau de complexité de gestion des verrous augmente et les performances baissent.
A priori le choix est dépendant du type des transactions (nature des informations manipulées). La plupart du temps dans les systèmes commerciaux la granularité est fixe (sauf indiquée explicitement). Certains systèmes font du verrouillage adaptatif en tenant compte de la hiérarchie des objets (plutot que de bloquer tous les attributs d'un n-uplet il vaut mieux bloquer le n-uplet et ainsi de suite). Dans les systèmes actuels le niveau offert est celui du n-uplet.
L'échec d'une transaction (suicide ou assassinat) entraine un état incohérent de la base de données. Il faut donc ramener la base de données dans l'état cohérent précédent le plus proche. Pour cela, un mécanisme de reprise offre deux opérations "défaire" et "refaire". Défaire une opération peut amener en à défaire d'autres. Deux techniques de reprise sont utilisées, mise à jour différée ou mise à jour immédiate.
Reprise basée sur la mise à jour différée :
La mise à jour différée consiste à ne faire les écritures effectives qu'au moment de la validation de la transaction. Les modifications sur la base de données sont enregistrées dans le journal lors de la validation. La procédure de reprise consiste alors à parcourir le journal pour refaire les opérations d'écriture des transactions validées depuis le dernier point de reprise (dans l'ordre d'apparition du journal).
Par contre, il n'y a rien à faire pour les transactions non validées (la base de données n'a pas été mise à jour).
Reprise basée sur la mise à jour immédiate :
Les écritures sont effectuées sur la base de données immédiatement et les anciennes valeurs des informations modifiées sont enregistrées dans le journal. La procédure de reprise consiste alors à :
- refaire les opérations d'écriture des transactions validées depuis le dernier point de reprise (dans l'ordre d'apparition du journal),
- défaire toutes les opérations d'écriture des transactions invalidées depuis le dernier point de reprise (dans l'ordre inverse d'apparition).
C. Date "An introduction to database systems", Addison Wesley, 1986
C. Delobel, M. Adiba "Bases de données et systèmes relationnels", Dunod Informatique, 1982
R. Elmasri, S. Navathe "Fundamentals of database systems", The Benjamin Cummings Publishing Compagny, 1989
G. Gardarin "Bases de données : les systèmes et leurs langages", Eyrolles, 1983
G. Gardarin, P. Valduriez "Bases de données relationnelles : analyse et comparaison des systèmes", Eyrolles, 1989
H. Korth, A. Silberschatz "Database system concepts", Mc Graw Hill, 1986 (existe depuis en français)
J. Ullman "Principles of database systems", Computer Science Press, 1982
