Bases de données avancées

Niveau: L3IN

Code: INF326

Dr.-Ing. Paul Dayang

 Objectifs

● Connaître les aspects approfondis des BDR

– Contraintes sur les données (statiques et dynamiques), triggers
SQL Techniques d'optimisation de requêtes
– Notion de transaction, concurrence d'accès (propriétés ACID,
verrouillage en deux phases), reprise après panne
– Techniques d'accès aux fichiers (hash-code, index, arbres)
– Extensions du modèle relationnel
● Connaître les Bases de données réparties, Bases de
données déductives
● Connaître le Modèle Orienté Objet
● Connaître le modèle Objet-Relationnel et SQL3
● Avoir un aperçu sur les NoSQL
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !2
 Notions avancées des Bases de
Données Relationnelles

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !3

 Quelques rappels du langage SQL

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !4

 Définition SQL

● SQL : Structured Query Language

– Langage de requête structurée
● Composants du SQL
– Un langage de définition des données (LDD) : ALTER, CREATE, DROP;

– Un langage de manipulation des données (LMD) : UPDATE, INSERT,

DELETE ;

– Un langage d'interrogation des données (LID) : SELECT ;

– Un langage de contrôle des données et des utilisateurs (LCD) :

GRANT, REVOKE.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !5

 Le Langage de Définition des Données (LDD)

● Ensemble de commandes qui définit une base de données

et les objets qui la composent
● La définition d’un objet (d’une table) inclut

– sa création: CREATE

– sa modification ALTER

– sa suppression DROP

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !6

 Le Langage de Définition des Données (LDD)

CREATE TABLE NomDeTable {(

nomDeColonne typeDeDonnée [NOT NULL] [UNIQUE
[DEFAULT optionPrédéfinie][CHECK
(conditionDeRecherche)][,…]
[PRIMARY KEY (listeDeColonnes),]
{[UNIQUE (listeDeColonnes),] [,…]}
{[FOREIGN KEY (listeDeColonnesDeCléEtrangère)
REFERENCES
NomDeTableParente[(listeDeColonnesDeCléCandidat,)],
[MATCH{PARTIAL | FULL}
[ON UPDATE actionRéférentielle]
[ON DELETE actionRéférentielle]] [,….]}
{[CHECK (conditionDeRecherche)] [,…]}
)}
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !7
 Le langage de Manipulation des Données : LMD

INSERT INTO <nomTable> [(<listeChamp(s)>)]

VALUES (<listeValeurs>);

UPDATE <nomTable> SET <champ> = <expression>

[WHERE <listeCondition(s)>] ;

DELETE FROM <nomTable> [WHERE

<listeCondition(s)>] ;

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !8

 Le Langage d’Interrogation des Données : LID

• SELECT commande qui permet la consultation et la mise

à jour des objets créés par le LDD et LMD

SELECT [DISTINCT | ALL] {* |

[expressionDeColonne [AS nouveauNom]] [,…]
FROM NomDeTable [alias] [, …]
[WHERE condition]
[GROUP BY listeDeColonnes][HAVING condition]
[ORDER BY listeDeColonnes]

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !9

 Le Langage de Contrôle des données : LCD

• GRANT donne des privilèges au utilisateurs

GRANT
priv_type [(column_list)]
[, priv_type [(column_list)]] ...
ON [object_type] priv_level
TO user_specification [, user_specification] ...
[REQUIRE {NONE | tls_option [[AND] tls_option] ...}]
[WITH {GRANT OPTION | resource_option} …]

GRANT SELECT ON db2.invoice TO 'pdayang'@'localhost';

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !10

 Le Langage de Contrôle des données : LCD

• GRANT donne des privilèges au utilisateurs

REVOKE
priv_type [(column_list)]
[, priv_type [(column_list)]] ...
ON [object_type] priv_level
FROM user [, user] ..

REVOKE INSERT ON db2.invoice FROM 'pdayang'@'localhost';

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !11

 Déclencheur (Triggers)

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !12

 Déclencheur (Triggers) : Définition

● Un déclencheur (ou triggers) est une règle, dite active,

de la forme: ”événement-condition-action”.
● Procédure stockée dans la base qui est déclenchée
automatiquement par des événements spécifiés par le
programmeur et ne s’exécutant que lorsqu’une
condition est satisfaite.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !13

 Déclencheur (Triggers) : Rôle et utilité

● La possibilité d’éviter les risques d’incohérence dus à la

présence de redondance.
● L’enregistrement automatique de certains événements.
● La spécification de contraintes liées à l’évolution de
données.
– Exemple : un salaire ne peut qu’augmenter
● De définir toutes règles complexes liées à
l’environnement d’exécution (restrictions sur des
horaires, des clients, . . .).
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !14
 Déclencheur (Triggers) : Principe

● Séquence Evénement-Condition-Action :
– Trigger déclenché par un événement spécifié par le
programmeur
• Insertion, destruction, modification sur une table.

– Test de la condition : si cette dernière n’est pas vérifiée,

alors l’exécution s’arrête.

– Si vérifiée, l’action est réalisée (toutes opérations sur la

base de données).

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !15

 Déclencheur (Triggers) : Caractéristiques

● Un seul déclencheur par événement sur une table.

● Les déclencheurs permettent de rendre une base de
données dynamique.
● Une opération peut en déclencher d’autres, qui elles-
mêmes peuvent entraîner en cascade d’autres
déclencheurs. . .
● Ce mécanisme n’est pas sans danger !
– Risque de boucle infinie.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !16

 Déclencheur (Triggers) : Caractéristiques

● Manipulation simultanée de l’ancienne et de la nouvelle

valeur d’un attribut ( → tests sur l’évolution).
● Un déclencheur peut être exécuté :
– Une fois pour un seul ordre SQL,

– Ou à chaque ligne concernée par cet ordre.

● L’action peut être réalisée avant ou après l’événement.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !17

 Déclencheur (Triggers) : Caractéristiques

● Concernant ”action” :
● SQL n’est pas procédural
– Les SGBD fournissent une extension du langage SQL :
instructions de branchement conditionnel, instructions de
répétition, affectations, . . .

● Langage impératif permettant de créer des véritables

procédures (procédures stockées)
1) PL/SQL pour ORACLE 2) PL/pgSQL pour PostgreSQL

3) T-SQL pour SQL Server 4) MySQL5

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !18

 Création d’un déclencheur

1. Spécifier l’événement qui déclenche l’action en

indiquant le type de la mise à jour (INSERT, UPDATE,
DELETE), le nom de la table et éventuellement le nom
des attributs mis à jour.

2. Indiquer si l’action est réalisée avant ou après.

3. Eventuellement, donner un nom à l’ancien et au

nouveau n-uplet (uniquement le nouveau en cas
d’insertion et uniquement l’ancien en cas de
suppression).
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !19
 Création d’un déclencheur

4. Décrire la condition sous laquelle se déclenche

l’événement sous la forme d’une expression SQL
booléenne, c.-à-d. Une expression pouvant être placée
dans une clause WHERE.

5. Décrire l’action à réaliser sous la forme d’une

procédure.

6. Indiquer si l’action est réalisée pour chaque n-uplet mis

à jour ou une seule fois pour la requête.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !20

 Création et suppression (MYSQL5)

CREATE
[DEFINER = {user | CURRENT_USER}]
TRIGGER trigger_name
trigger_time trigger_event
ON tbl_name FOR EACH ROW trigger_body

trigger_time: {BEFORE | AFTER}

trigger_event: {INSERT | UPDATE | DELETE}

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !21

 Déclencheur (Triggers) : Caractéristiques

• user : si un utilisateur spécifier doit avoir le format

'user_name'@'host_name'

• tbl_name : précise le nom de la table concernée

• FOR EACH ROW : précise si le trigger doit être déclenché

pour chaque ligne mise à jour.

• Deux variables :new et :old qui contiennent resp. le

nouveau et l’ancien contenu de la ligne.

• trigger_time ayant pour valeur BEFORE / AFTER : moment

de déclenchement du trigger (avant ou après)
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !22
 Déclencheur (Triggers) : Caractéristiques

• trigger_event ayant pour valeur DELETE / UPDATE /

INSERT : précise le ou les évènements concernés par le
déclenchement

• trigger_body : actions à exécuter comprises entre BEGIN

…. END (obligatoire)
BEGIN
/* instructions, commandes SQL, structures de
contrôle */
EXCEPTION
/* gestion des erreurs */
END ;
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !23
 Déclencheur (Triggers) : Caractéristiques

• Créer une table avec des valeur

CREATE TABLE account(acct_num INT, amount
DECIMAL(10,2));

• Sauvegarder le nouveau montant dans une variable

CREATE TRIGGER ins_sum BEFORE INSERT ON account

FOR EACH ROW SET @sum = @sum + NEW.amount;

•Supprimer le déclencheur

DROP TRIGGER ins_sum ;

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !24

 Déclencheur : Exemple 1

CREATE TRIGGER upd_check BEFORE UPDATE ON

account
FOR EACH ROW
BEGIN
IF NEW.amount < 0 THEN
SET NEW.amount = 0;
ELSEIF NEW.amount > 100 THEN
SET NEW.amount = 100;
END IF;
END;//

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !25

 Déclencheur : Exemple 2

• Vérification qu’un prix ne peut pas baisser.

CREATE TRIGGER pas_baisse_prix

BEFORE UPDATE OF prixUnitaire ON Article
FOR EACH ROW
BEGIN
IF (OLD.prixUnitaire > NEW.prixUnitaire)
raise_application_error(-20100, ’le prix d’un
article ne peut pas diminuer’) ;
END IF ;
END ;

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !26

 Déclencheur : Exemple 3

•Insérer, supprimer et actualiser des données

delimiter |
CREATE TRIGGER testref BEFORE INSERT ON test1
FOR EACH ROW
BEGIN
INSERT INTO test2 SET a2 = NEW.a1;
DELETE FROM test3 WHERE a3 = NEW.a1;
UPDATE test4 SET b4 = b4 + 1 WHERE a4 = NEW.a1;
END;
|
delimiter ;

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !27

 Transactions, reprise, concurrence d’accès

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !28

 Transaction

• Définition 1 : séquence d’opérations qui accèdent et

modifient le contenu d’une base de données.

• Définition 2 : séquence d'opérations (lecture/ écriture)

qui doit être exécutée dans son intégralité, amenant la
BD d'un état cohérent à un autre état cohérent.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !29

 Transaction

begin transaction
Compte A, Djorwe 50 000 F CFA
Compte B, Djare 10 000 F CFA

Execution de la transaction. La
Transfert de BD peut se trouver dans un etat
25 000 F FCA intermédiaire incoherent

Compte A, Djorwe 25 000 F CFA

Compte B, Djare 35 000 F CFA end transaction

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !30

 Etapes d’une transaction

• Délimitation par des instructions de début et de fin.

Début si :
Connexion à la base de données, ou fin de la
transaction précédente.
Fin si
COMMIT (validation de la transaction), ROLLBACK
(abandon de la transaction), ou fin (normale) de
session.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !31

 Etapes d’une transaction

START
. . .suite d’opérations. . .
COMMIT

START
. . .suite d’opérations. . .
ROLLBACK

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !32

 Transaction : exemple
BEGIN
INSERT INTO Client2 (nomClient) VALUES
(’acheteur’) ;
COMMIT ;
afficher(’Le client a été inséré’) ;
EXCEPTION
WHEN DUP_VAL_ON_INDEX THEN
afficher(’Le client existe déjà’) ;
ROLLBACK ;
WHEN OTHERS
afficher(’Erreur inconnue à
l’insertion’) ;
ROLLBACK ;
END ;

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !33

 Propriétés des transactions (ACID)

• Atomicité
• Toutes les mises-à-jour doivent être effectuées ou aucune.

• En cas d'échec, le système doit annuler toutes les modifications

réalisées.

• Cohérence
• La base de données doit passer d'un état cohérent à un autre
état cohérent.

• En cas d'échec, il faut restaurer l'état initial cohérent.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !34

 Propriétés des transactions (ACID)

• Isolation
• Les résultats d'une transaction ne sont rendus visibles aux autres
transactions qu'une fois celle-ci validée.

• Les accès concurrents peuvent mettre en question l'isolation.

• Durabilité
• Les modifications d'une transaction validée sont persistentes.

• Principal problème survient en cas de panne disque.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !35

 Concurrence d’accès

• SGBD : multi-utilisateurs
• Une même information peut manipulée par plusieurs utilisateurs
à la fois
• Unité de la concurrence = transaction

Cas d’un système de réservation

1. Kobe et Abel travaillent chacun dans une agence de voyage.
2. Kobe (transaction T1) veut annuler N réservations sur un bus B1
et réserver N places sur un bus B2.
3. Abel (transaction T2) veut réserver M places sur le bus B1.
4. L’exécution concurrente de T1 et de T2 sans contraintes de
synchronisation peut produire un certain nombre de problèmes

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !36

 La théorie de la concurrence

● La théorie de la concurrence permet de garantir la

cohérence et l'isolation des transactions
● Elle est basée sur la théorie de la sérialisabilité des
transactions.
● Objectif: rendre invisible aux clients le partage
simultané des données.
● Problèmes potentiels: perte de modifications, non-
reproductibilité des lectures, modification temporaire.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !37

 Problèmes dus à la concurrence

● Perte de modifications
– Lecture de données incohérentes

– Lecture de données non confirmées

● Non-reproductibilité des lectures
● Modification temporaire
● Objets fantômes.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !38

 Perte de mise à jour

2 transactions accèdent au même élément d'une BD et

l'exécution des opérations est décalée.

On devrait avoir A=70 MAIS on a A = 60 : perte de la mise à

jour de T1.
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !39
 Lecture impropre (données incohérentes)

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !40

 Modification temporaire (dirty read)
1 transaction va modifier un élément de la BD et la
transaction échoue. L'élément mise à jour est alors
accédé par une autre transaction avant réparation

T 1 a lu une valeur de A incorrecte : tout doit se passer

comme si T 2 n’avait jamais changé A.
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !41
 Non-reproductibilité des lectures
(Unrepeatable read)
1 transaction réalise une opération d'aggrégation alors
qu'une autre transaction est en train de modifier des
données

T2 (qui ne modifie pas A) devrait obtenir à chaque

lecture la même valeur pour cette donnée.
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !42
 Lecture fantôme (phantom read)

Scénario : 1 transaction ajoute un tuple qui satisfait

la condition d'une autre transaction.

Cas d’un système de gestion de projet

Une transaction T ajoute un employé travaillant sur le projet 3
alors que la transaction T' demande la liste des employés du
projet 3 (pour calculer la somme des heures ou des salaires de
ces derniers). Le problème peut être le suivant, T' ne
comptabilise pas les données du nouvel employé.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !43

 Lecture fantôme (phantom read)

T1 n’a pas vu l’ajout de 4 dans E par T2 , pour T1 4 est

un objet fantôme.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !44

 Reprise

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !45

 Récupération de bases de données (Reprise)

● Pannes d’un SGBD :

– panne d’ordinateur,
– panne de disque.

● La reprise à chaud, après un abandon de transaction ou

u n e p a n n e d ’ o r d i n a t e u r, p e u t ê t r e r é a l i s é e
automatiquement et rapidement, en s’appuyant sur la
tenue d’un journal qui garde en mémoire tous les
événements d’une transaction.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !46

 Récupération de bases de données (Reprise)

● La reprise à froid, après une panne de disque est plus

longue à mettre en oeuvre. Elle nécessite de réaliser des
copies régulières de la BD et un archivage des mises à
jour entre deux copies.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !47

 Atomicité et durabilité

● Le respect de l’atomicité peut impliquer de défaire les

effets d’une transaction lorsque celle-ci a été
abandonnée.
● Le respect de la durabilité implique que le SGBD doit
être capable de remettre la base de données en état
après une panne :
– les mises à jour faites par une transaction non confirmée
avant la panne doivent être défaites.
● C’est le gestionnaire de reprise qui assure cette tâche.
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !48
 Journalisation

● Journal : fichier séquentiel qui contient une suite

d’enregistrements dont chacun décrit un événement
concernant la vie des transactions et les modifications
de la BD.
● Fichier séquentiel enregistré sur une mémoire stable, c.-
à-d. une mémoire qui théoriquement ne peut pas être
détruite.
● Si nécessaire, le journal est sauvegardé régulièrement
sur un disque miroir, bandes magnétiques, . . .
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !49
 Exemple d’événements journalisés

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !50

 Un extrait de journal

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !51

 Point de reprise (check point)

● Point de reprise = marque dans le journal indiquant un

moment
– Aucune transaction n’était en cours.
– Toutes les données écrites par des transactions
antérieures au point de reprise avaient été
transférées sur disque.

● Pour obtenir un point de reprise, il faut donc :

– Interdire le début de nouvelles transactions

– Laisser se terminer les transactions en cours.
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !52
 Propriétés des opérations sur granule

● Opération: Suite d'actions accomplissant une fonction

sur un granule en respectant sa cohérence interne
(contraintes d'intégrité).
● Différentes opérations en fonction du granule:
– Page : lecture et écriture

– Article (tuple) : lire, écrire, modifier, supprimer et

insérer.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !53

 Propriétés des opérations sur granule

● Le résultat d'une opération sur un granule est

l'application de l'opération sur le granule
● On distingue les opérations compatibles et permutables

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !54

 Techniques d'accès aux fichiers
(index, hash-code, arbres)

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !55

 Techniques d'accès aux fichiers (hash-code,
index, arbres)
● Un SGBD inclut en son cœur une gestion de fichiers.

Architecture d’un gestionnaire de fichiers

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !56
 Index

● Pour compléter le schéma d’une table (relation), on

peut créer des index.
● Permet une recherche rapide d’une information.
● Notion d’index : même que pour un livre

Livre Base de données

Mots-clés de l’index Valeurs d’un attribut

Pages Adresses mémoires où

sont stockées ces valeurs

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !57

 Caractéristiques des index

● Objet optionnel associé à une table.

● Mise à jour automatiquement lors de modifications de la
table.
● Possibilité de créer plusieurs index sur une même table.
● Peut concerner plusieurs attributs d’une même table
(index composé).

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !58

 Caractéristiques des index
Cas selection d'un client
SELECT * FROM Client WHERE nom = ’Kaore’;

● Un moyen pour récupérer la ou les lignes répondant à la

clause nom=’Kaore’ est de balayer toute la table.
● Le temps de réponse sera prohibitif dès que la table
dépasse quelques centaines de lignes.
● Afin d’optimiser ce type de requête, on pourra indexer
l’attribut ”nom”.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !59

 Création et suppression d’un index
Création
CREATE INDEX nom_index ON nom_table
(nom_attribut1, . . .) ;

Exemple
CREATE INDEX idxNomClient ON Client (nom) ;

Suppression
DROP INDEX nom_index ;

Pour vérifier l’existence d’index en MySQL

SHOW INDEX FROM Client;

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !60

 Critères d’indexation

● Choisir de créer un index sur

– Les attributs utilisés comme critère de jointure,

– Les attributs servant souvent de critères de sélection,

– une table de gros volume (d’autant plus intéressant si les

requêtes sélectionnent peu de lignes).

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !61

 Critères d’indexation

● L’adjonction d’index accélère la recherche des lignes.

● Mais il ne faut pas créer des index à tort et à travers
– Impact négatif sur les commandes d’insertion et de
suppression

– Coût de la mise à jour de tous les index portant sur la

table.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !62

 Critères d’indexation

● Les valeurs non renseignées ne sont pas stockées dans

l’index (pour minimiser le volume)
● L’index n’est d’aucune utilité pour retrouver les valeurs
non renseignées (lorsque le critère de recherche est IS
NULL ou IS NOT NULL).
● L'index n’est pas mis en oeuvre lors de l’évaluation
d’une requête si l’ (les) attribut(s) correspondant(s) sont
utilisé(s) par l’intermédiaire d’une expression

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !63

 Critères d’indexation

● La table ”Client” bénéficie d’un index sur l’attribut ”nom”,

sur ”numClient” et sur le champs ”montant”

Les index sont utilisés dans les cas suivants

SELECT * FROM Client WHERE numClient = 500;
SELECT * FROM Client WHERE numClient >= 412;
SELECT * FROM Client WHERE numClient BETWEEN 300
AND 500;
SELECT * FROM Client WHERE nom = ’Martin’;
SELECT * FROM Client WHERE nom LIKE ’M%’;

Les index sont inutiles dans les cas suivants

SELECT * FROM Client WHERE nom IS NULL;
SELECT * FROM Client WHERE ca*10 >= 10000;
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !64
 Mécanisme d’accès aux enregistrements d’un
index
● Mécanisme interne au SGBD.
● Organisation arborescente
– Séquentiel-indexé,

– Arbres B+

● Accès par hachage

– Statique

– Dynamique

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !65

 Hachage

● Le hachage repose sur la construction d’une fonction dite de

hachage qui appliquée à la clé d’un enregistrement fournit
l’adresse de cet enregistrement.
● Le hachage est dit statique ou dynamique selon la fonction de
hachage est fixée ou évolue durant la vie de l’index.
● Un index à accès par hachage peut être organisé avec ou sans
répertoire

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !66

 Hachage statique avec répertoire

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !67

 Hachage statique sans répertoire
On peut éviter l’utilisation d’un répertoire en créant un index de N
pages. Le code haché donne alors directement accès à la
page contenant les clés recherchées.

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !68

 Arbres B+

● Les arbres B ont été introduits par Bayer et McCreight en 1972

et ont fait l’objet de nombreux développements par la suite
● Nous décrivons une variante des arbres B : les arbres B+, qui
sont très largement utilisés pour construire des index de BD
● Un arbre B+ d’ordre m (entier impair >= 3) est un arbre
équilibré dont chaque noeud est enregistré dans une page
stockée sur disque

2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !69

 Arbres B+ : organisation

● Une feuille contient une séquence d’enregistrements triée

par ordre croissant de clé
● Une feuille est au moins à moitié remplie sauf si elle est
l’unique noeud de l’index
● Les feuilles sont chaînées entre elles dans l’ordre de leur
première clé à l’aide du pointeur p.
● Un noeud non terminal contient une séquence
d’enregistrements triée par ordre croissant de clé
● Un noeud est au moins à moitié rempli sauf s’il est la racine
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !70
 Arbres B+ : exemple

● Recherche de la clé ”Igor” :

● I > G, alors n1
● I < J, alors f3,
● Igor ∈ f3
2019/2020 Dr.-Ing. P. Dayang, Math & Info, Université de Ngaoundéré !71