1.

INTRODUCTION
1.1. Définitions
- 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.

1.2. Fonctionnalités
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.

1.3. Architecture logique d'un SGBD

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.

1.3.1. Architecture Ansi/Sparc

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.

1.3.2. Indépendance données - programmes

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.

2. Le modèle relationnel de données

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.

2.1. Définition formelle

- 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.

2.2. Caractéristiques des relations

- 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).

2.3. Contraintes d'intégrité

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.

3. Les langages relationnels

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).

3.1. L'algèbre relationnelle

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)

Exemples : Q1, Q2
- 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).

Exemples : Q1, Q2, Q3, Q5, Q6

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

3.2. Les langages prédicatifs (nuplet et domaine)

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).

3.2.1. Spécification formelle du calcul relationnel à variable nuplet

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.

3.2.2. Spécification formelle du calcul relationnel à variable domaine

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.

3.2.3. Exemple de la base des invitations

4. Dépendances fonctionnelles et
normalisation
Problème : un mauvais schéma relationnel peut entrainer des anomalies lors des
manipulations.

APPROVISIONNEMENT

Produit Quantité Couleur Fournisseur Adresse

parapluie 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

4.1. Dépendance fonctionnelle sur une relation (DF)

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.

4.2. Propriétés des dépendances fonctionnelles (ou axiomes

d'Amstrong)
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

4.3. Décomposition binaire d'une relation

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

4.4. Définitions :
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.
4.5. Normalisation des relations (formes normales)
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).

4.6. Dépendances fonctionnelles et conception de schémas

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 :
5. Architecture logicielle d'un SGBD
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.

6. Evaluation et Optimisation de requêtes

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, ...).

6.1. Optimisations algébriques

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.

6.1.1. Règles de transformation de l'algèbre relationnelle

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))

6.1.2. Algorithme général d'optimisation heuristique

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)

6.2. Optimisation par une fonction de coût

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).

7. Contrôle des accès concurrents et reprise

7.1. Introduction
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)

7.2. Problèmes liés aux accès concurrents

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.

7.3. Mécanismes pour assurer la concurrence et la reprise

7.3.1. Transactions et journalisation

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à.

7.3.2. Concurrence par verrouillage

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.

7.3.3. Granularité de contrôle de concurrence

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.

7.4. Principes généraux de la reprise

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).