Programme de baccalauréat en informatique

Modèles et langages des bases de données

IFT-19022

Édition janvier 2005

André Gamache, professeur
© Université Laval
Nabil Sahli, chargé de cours

Indexation, cluster, vue et droits d’accès

Module 6

Bureau de la formation à distance

 Objectifs d’apprentissage
Expliquer le principe de l’indexation et ses différents
types
Juger de la pertinence ou non d’un index dans une
requête SQL
Expliquer le principe des clusters et ses différents
types
Juger de l’utilité ou non des clusters dans une base
de données
Décrire les vues et les règles qui lui sont associées
Énumérer les différents droits d’accès possibles et
décrire les conséquences de leur utilisation

03/01/2005
© 2
Bureau de la formation à distance
 Plan
Indexation
Clusters
Vues

03/01/2005
© 3
Bureau de la formation à distance
 Introduction
Indexation: mécanisme d’accès rapide aux
données par le moteur de la BD
Alternative à l’accès séquentiel (balayage)
Plusieurs types d’index (simple, séquentiel,
indexé avec plusieurs niveaux, par hashing,
etc.)
Les index les plus utilisés par les SGBD sont
ceux des B-arbres (B*-arbre)

03/01/2005
© 4
Bureau de la formation à distance
 B*-arbre (cf. 8.2)
Permet une recherche dans in lot de 2
millions de tuples en moins de 5
lectures disque.
Une hiérarchie de cellules
Chaque cellule est un nœud
Les cellules du dernier niveau sont des
feuilles

03/01/2005
© 5
Bureau de la formation à distance
 B*-arbre
Structure du nœud
vi vi+1

Pointeur sur sous-arbre Pointeur sur sous-arbre

dont les clé < vi Pointeur sur sous-arbre dont les clé > vi+1
dont les clé > vi ou =
vi+1

03/01/2005
© 6
Bureau de la formation à distance
 B*-arbre
Facteurs de croissance d’un B*-arbre
z Nombre de tuples dans la table indexée
z Longueur de la clé (ou valeur indexée):
plus l clé est grande, moins il y a d’entrées
dans une cellule ou page
z Sèlectivité de l’attribut: si très sèlectif
comme une clé, alors l’hauteur de l’arbre
est plus grande que si l’attribut est sexe ou
ville.
03/01/2005
© 7
Bureau de la formation à distance
 Recherche avec un
attribut primaire
Select * From Employe Where age=‘24’
z L’indexation de l’âge permet de trouver
rapidement les rid (adresse du tuple) des tuples
des emplyés 24ans, ensuite les lire en utilisant les
rids.
Select * From Employe Where salaire=25000
and ville=‘Quebec’
z Si salaire indexé et ville non indexé, vaut mieux
enlever l’index sur salaire car le SGBD fera de
toute facon un balayage séquentiel pour ville
z Si les deux indexés, alors le SGBD cherche les
rids relatifs à chaque condition et fait l’intersection
03/01/2005
© 8
Bureau de la formation à distance
 Densité de l’index
Index dense: les pointeurs des feuilles
mènent directement à un tuple
z p. ex. Compter le nbre d’ouvrier de 25ans se fait
sans accès aux tuples (le comptage se fait au
niveau des index)
Index non dense: mènent à une page de
tuples
z Exige un balayage séquentiel de la page pour
trouver la valeur recherchée
z Avantage: utilisation optimale de l’espace des
pages d’index quand l’attribut est à faible
sélectivité ©
03/01/2005 9
Bureau de la formation à distance
 Index inversé
Index construit avec les différentes
valeurs de l’attribut dont chacune est
associée à une liste de rids de tuples
Index inversé sur spécialité dans
Ouvrier

03/01/2005
© 10
Bureau de la formation à distance
 Index inversé
Les feuilles du B*-arbre contiennent les
rid qui conduisent aux tuples
Permet d’indexer les attributs peu
importe leur sélectivité
Utile pour les grandes bases de
données

03/01/2005
© 11
Bureau de la formation à distance
 Index bitmap
Les feuilles de l’arbre ne contiennent
pas les rids mais un vecteur de bits
z La longueur du vecteur correspond au nbre
de tuples dans l’extension de la table
z Index bitmap sur spécialité (4 bits: un bit
par spécialité)

03/01/2005
© 12
Bureau de la formation à distance
 Index bitmap
Accélère les requêtes avec comptage
z Pour le nbre de soudeurs, pas besoin
d’accéder aux tuples
z CREATE INDEX BITMAP on Ouvrier(spec)

03/01/2005
© 13
Bureau de la formation à distance
 Création des index
La spécification d’une clé primaire
génère automatiquement un index
interne géré par le système
La clé étrangère peut être indexée par
la création subséquente d’un index
CREATE [unique] index <nom_index >
on <nom_relation> (col1, col2, …)
DROP index <nom_index > //supprimer

03/01/2005
© 14
Bureau de la formation à distance
 Caractéristiques des
index
Un index est stocké sous la forme de tuples
dans une table (une colonne pour l’entrée de
l’index et une colonne pour le rid du tuple
indexé)
Les propriétés d’un index dépendent de la
procédure de sa création
Clé primaire: index du type système (le DBA
ne peut pas le supprimer). Peut être
désactivé temporairement par ALTER TABLE

03/01/2005
© 15
Bureau de la formation à distance
 Caractéristiques des
index
Les tuples index peuvent cohabiter avec les tuples
données dans le même espace de données mais des
pages (segments) différentes
Les entrées sont MAJ automatiquement (peut causer
un ralentissement si MAJ intensive)
Les index sont utilisés implicitement par l’optimiseur
de requêtes sauf s’il y a blocage (formulation
syntaxique particulière des clauses SQL; p. ex. pas
de WHERE)
Les index sont pertinents pour des tables de plus de
1000 tuples

03/01/2005
© 16
Bureau de la formation à distance
 exemple
Pieces(nop*, description, km, ville_p,
proprio)
Si requête: Select * from Pieces Where
description=’porte’ And proprio=‘f1’ est
fréquente alors Création d’un index
unique et composé:
z Create UNIQUE index idx on Pieces
(description, proprio)

03/01/2005
© 17
Bureau de la formation à distance
 Notions d’optimisation
Si un seul index (sur description), pas
de gain car obligation de faire un balaye
séquentiel sur l’autre attribut (proprio)
Cf. Module Optimisation pour plus de
détails

03/01/2005
© 18
Bureau de la formation à distance
 Guide d’utilisation des
index
Faut supprimer les index pour traiter un flux
important de transactions de MAJ ensuite les
recréer au besoin
L’index de clé sert aussi à maintenir la
contrainte de l’unicité
Une accélération de la jointure est possible
par la création des index sur les attributs de
jointure
Il est judicieux de créer un index composé sur
des attributs qui sont fréquemment utilisés
ensemble ©
03/01/2005 19
Bureau de la formation à distance
 Guide d’utilisation des
index
Un suivi approprié de l’exploitation réelle des
données permet au DBA de mettre au point
et d’adapter les accès à la BD par des index
L’indexation doit être revue périodiquement
pour tenir compte des changements sur le
profil d’exploitation des données
Un index n’est pas utile sur un attribut de
sélectivité inférieure à 0.35 (cf. Module
optimisation)

03/01/2005
© 20
Bureau de la formation à distance
 Plan
Indexation
Clusters (cf. 8.12)
Vues

03/01/2005
© 21
Bureau de la formation à distance
 Définition
Normalement les tuples de 2 tables
différentes sont rangés dans deux pages
différentes
Un cluster est un regroupement des tuples
d’une ou plusieurs table
Le clustering est un mécanisme de
placement des tuples partageant une même
valeur: création d’une nouvelle structure de
page

03/01/2005
© 22
Bureau de la formation à distance
 Définition
Le SGBD place physiquement les
tuples utilisés dans le calcul d’une
jointure de préférence dans la même
page (ou au pire proches)

03/01/2005
© 23
Bureau de la formation à distance
 Exemple
Postes Empl

Assignations

03/01/2005
© 24
Bureau de la formation à distance
 Exemple
Pour connaître description du poste d’un
employé, il faut jointure Assignations et
Postes (exemple de cluster indexé)
Les tuples de ces deux tables peuvent être
placés dans la même page en se basant sur
l’attribut en commun (noPost) appelé clé du
regroupement (ou du clustering)
Dans la même page on aura alors:
z (j75, mecano2) // de la table Postes
z (j75, P346, 12-oct-1997, nuit) // de Assignations
z (j75, P450, 27-jan-1994, nuit) // de Assignations
03/01/2005
© 25
Bureau de la formation à distance
 Types de clusters
2 types
z Cluster avec Hashing (une même table)
z Cluster indexé (implique 2 ou plusieurs
tables)

03/01/2005
© 26
Bureau de la formation à distance
 Cluster indexé
Regroupe dans la même page les
tuples ayant la même valeur pour
l’attribut du cluster
Nécessite création du cluster et un
index
Exemple:
z Create CLUSTER
clust_assign(c-no-post varchar2(5));

03/01/2005
© 27
Bureau de la formation à distance
 Exemple
z Create INDEX ind_clust ON CLUSTER
clust_assign
z CREATE TABLE Postes(
noPoste varchar2(5) primary key,
Description varchar2(30))
Cluster clust_assign(noPoste);
z CREATE TABLE Assignation(
…
noPoste varchar2(5) Foreign key References
Postes(noPoste))
Cluster clust_assign(noPoste);
03/01/2005
© 28
Bureau de la formation à distance
 Cluster avec Hashing
Le placement du tuple est calculé par une
fonction de hashing H
Faut spécifier les attributs de clustering et
estimer le nombre de valeurs de H possibles
et le nombre de tuples ayant la même valeur
par H.
Exemple précédent: attribut de
clustering=TauxH qui varie entre 1250 et
1450 donc 200 valeurs possibles
Si H=mod(50)
03/01/2005
© 29
Bureau de la formation à distance
 exemple

Si taille tuple=1k et puisque 4 tuples peuvent avoir la

même valeur par H, alors taille page=4k
Create Cluster Taux_Clu (tauxH )
SIZE 4k
HASHKEYS 50;

03/01/2005
© 30
Bureau de la formation à distance
 exemple
Ensuite il faut créer la table
Create table Empl (
noEmpl char(4) not null,
Nom varchar2(30),
Prenom varchar2(30),
TauxH number(4),
Cluster taux_clu(TauxH));
03/01/2005
© 31
Bureau de la formation à distance
 exemple
Avec Select * from Empl where
tauxH=1250
z Le SGBD calcule H(1250)=0 donc page 0
z L’accès est plus rapide qu’avec un index
car avec un index le SGBD transfere
plusieurs pages avant d’identifier le rid du
tuple

03/01/2005
© 32
Bureau de la formation à distance
 Plan
Indexation
Clusters
Vues (cf. 8.13-8.16)

03/01/2005
© 33
Bureau de la formation à distance
 Généralités
Syntaxe (cf. Module SQL)
Une vue est conservée sous forme de
requête SQL (Ne correspond pas à une table
réelle)
Certains langages implémentent la variable
de table
z G_Transaction=(select article from Ventes)
z Select [Link] From G_Transaction
z Inconvénient: aspect statique de la table (on n’est
pas sûr d’avoir accès aux denières mises à jour
de la BD)
03/01/2005
© 34
Bureau de la formation à distance
 Généralités
Pour créer une vue, l’usager doit avoir
les droits de lecture et de MAJ sur les
tables référencées dans la vue et avoir
le droit de créer des vues dans le
schéma

03/01/2005
© 35
Bureau de la formation à distance
 Droits d’accès
Une vue a des privilèges d’accès, d’insertion,
de suppression et de modification (comme
une table)
John crée:
z Create View VentesRecentes as Select * From
Ventes Where date > to_date(’01-jan-1995’, ‘DD-
MM-YYYY);
John donne l’accès à Paul:
z GRANT Select On VentesRecentesTo Paul;

03/01/2005
© 36
Bureau de la formation à distance
 Droits d’accès
Paul a juste le droits de faire des select
Avec Grant Insert On VentesRecentesTo
Paul; Paul peut insérer
Mais Paul peut insérer des ventes de 1994
car pas de check option
Pour empêcher Paul d’en insérer
z Create View VentesRecentes_ajout as Select *
From Ventes Where date > to_date(’01-jan-1995’,
‘DD-MM-YYYY) with CHECK OPTION;

03/01/2005
© 37
Bureau de la formation à distance
 Droits d’accès
Autre exemple:
z Create View VentesCourantes as Select * From
Ventes Where date = SYSDATE and prix >5.00
with CHECK OPTION; (bloque les transactions de
moins de 5$)
z Create View VentesCourantes as Select * From
Ventes Where date = Slower(To_char(SYSDATE,
‘DAY’))=‘Monday’ and prix >5.00 with CHECK
OPTION; (usage de la vue possible juste le lundi)

03/01/2005
© 38
Bureau de la formation à distance
 Suppression de la vue
DROP VIEW <nom_vue> {RESTRICT
lCASCADE}
z RESTRICT: bloque la suppression qui la
vue subsiste dans la BD
z CASCADE supprime la vue et toute autre
vue ou contrainte la référençant

03/01/2005
© 39
Bureau de la formation à distance
 Suppression des
privilèges

Patricia ne peut pas transmettre ses

privilèges (pas de GRANT option)
Si ‘REVOKE Select From Sylvain’ la
suppression de ce privilège se propage
à Jacques et à Marie-Claude

03/01/2005
© 40
Bureau de la formation à distance
 Opérations sur les vues
Create View Vue1 as Select nas, salaire
From Employe
z Si l’usager fait: ‘update vue1 set
salaire=20K$ Where nas=21;’ le SGBD
exécute un ordre interne:
z Update Employe set salaire=20k$ where
nas=21; (sur une table)
Cf. 8.15 p. 34-36 pour les vues avec
jointure
03/01/2005
© 41
Bureau de la formation à distance
Restrictions sur les vues
Sur une vue, il est interdit de:
z Changer le type des attributs de la relation de
base
z Modifier des droits d’accès aux tables de base
Une MSJ avec SQL est possible sur une vue
ssi
z L’expression de la vue est un Select sans JOIN, UNION,
INTERSECT, EXCEPT
z Pas de DISTINCT
z Pas de jointure ni d’autojointure (sous-requête dans Where
sur la même table)
z Pas de GROUP BY ni de HAVING

03/01/2005
© 42
Bureau de la formation à distance
 Références
[Link]
[Link]

03/01/2005
© 43
Bureau de la formation à distance