On veut stocker un fichier F avec 120000 enregistrements d’une taille fixe de
100 octets par article.
Questions :
De combien de blocs a-t-on besoin au minimum pour stocker tout
le fichier si la taille d’un bloc est 8192 octets, sachant
que chaque bloc contient un entête de 150 octets
et qu’un enregistrement ne peut pas chevaucher 2 blocs?
Correction
Un bloc contient 8 042 octets utiles. Donc 80 enregistrements
par bloc au maximum. On divise les 120 000 enregistrements par 80
et on obtient 1 500 blocs
On suppose maintenant que F est indexé par un index non dense
sur A et un index dense sur un autre champ B. On peut
stocker 100 entrées dans un bloc d’index et aucune place libre n’est laissée dans les blocs.
Combien d’entrées y a-t-il dans les feuilles de l’index non dense?
dans les feuilles de l’index dense?
Correction
Le fichier F contient 1 500 blocs et et trié sur A.
L’index non dense contient donc 1500 entrées, une par bloc et cet index occupe 15
blocs. L’index dense
contient 120000 entrées, une par enregistrement, et occupe 1200 blocs..
Supposons que l’index non dense a deux niveaux, racine
comprise, et que seule la racine est en mémoire. On se place dans le pire
des cas où il faut une lecture physique pour lire une feuille d’index et une autre pour
lire un bloc du fichier.
On cherche les enregistrements pour lesquels la
valeur de l’attribut A est comprise entre P1A3 et P3G5. On
suppose qu’il y a moins de 100 enregistrements tels que A
commençe par P. Combien de lectures coûte la recherche par l’index dans le pire
des cas?
Correction
La recherche utilise l’index non dense sur A. Celui-ci tient sur 15 blocs.
La traversée de l’index part de la racine et arrive immédiatement à la feuille
d’index dont la
première entrée est inférieure ou égale à P1A3 et dont la dernière entrée est
supérieure ou égale à P1A3. On recherche dans cette feuille l’entrée la plus grande
inférieure ou égale à P1A3. Cette entrée contient l’adresse du bloc du fichier qui
contient l’article de code P1A3. On accède à ce bloc.
Les articles sont triés sur A.
Soit tous les articles de code compris entre P1A3 et P3G5 sont dans ce bloc soit ils sont
à cheval sur deux blocs adjacents (ils ne peuvent pas être sur plus de 2 blocs
adjacents). Dans ce dernier cas, une lecture du bloc
adjacent chaîné est nécessaire. Donc la recherche coûte 2 ou 3 accès bloc.
Même question avec l’index dense, pour une recherche sur l’attribut
B.
Correction
La recherche utilise l’index dense sur B. La différence essentielle
est que le parcours séquentiel s’effectue au niveau des feuilles de l’index.
Il n’est plus possible de le faire sur le fichier car ce dernier n’est plus
trié.
Pour chaque entrée trouvée dans une feuille, il faut effectuer une lecture de bloc
dans le fichier de données. Au pire, il faut lire autant de blocs que
d’enregistrements, soit 100 lectures qui viennent s’ajouter aux deux blocs
lus dans l’index. Le coût prédominant est donc dans ce cas la multiplication
des accès aléatoires au fichier de données, ce qui montre une nouvelle fois
qu’une recherche par intervalle avec un index peut s’avérer contre-performante.
Pour évaluer cette requête, on suppose que le tampon de lecture ne peut
contenir qu’un seul bloc et l” index tient en mémoire. Dans ce cas, est-ce
qu’il est préférable d’utiliser l’index ou de parcourir la table
séquentiellement ? Pourquoi ?
Correction
Une lecture séquentielle est préférable : la sélectivité de l’index
est très basse, et comme il s’agit d’un index dense, on risque de lire la même
bloc plusieurs fois.
On donne ci-dessous une requête SQL et le plan d’exécution fourni par Oracle :
0 SELECT STATEMENT
1 MERGE JOIN
2 SORT JOIN
3 NESTED LOOPS
4 TABLE ACCESS FULL NOTEMAG
5 TABLE ACCESS BY INDEX ROWID PRODUITS
6 INDEX UNIQUE SCAN A34561
7 SORT JOIN
8 TABLE ACCESS FULL PRIXFOUR
Questions:
Existe-t-il un index ? sur quel(s) attribut(s) de quel(s) table(s) ?
Correction
Il existe un index sur l’attribut code de la table Produits.
Algorithme de jointure : Expliquer en détail le plan d’exécution (accès
aux tables, sélections, jointure, projections)
Ajout d’index : On crée un index sur l’attribut note de la table
NoteMag. Expliquez les améliorations en
terme de plan d’exécution apportées par la création de cet index.
Correction
Après création d’index le plan est :
Plan d'execution
----------------
0 SELECT STATEMENT
1 NESTED LOOPS
2 NESTED LOOPS
3 TABLE ACCESS FULL PRIXFOUR
4 TABLE ACCESS BY INDEX ROWID PRODUITS
5 INDEX UNIQUE SCAN PRODUITS_CODE
6 TABLE ACCESS BY INDEX ROWID NOTEMAG
7 INDEX RANGE SCAN NOTE_MAG
L’abonnement est sans engagement: seulement la date de début est nécessaire pour
un abonnement en cours. Le type d’un abonnement peut être:
“free” (financé par la publicité), “normal” et “premium”
(donne le droit de télécharger la musique en local pour une écoute
hors connexion). L’attribut “téléchargé” vaut vrai ou faux.
Un abonné peut avoir écouté une chanson plusieurs fois (à des dates différentes).
Le SGBD crée un index sur les clés primaires, mais pas sur les clés étrangères.
On insère successivement les enregistrements suivants dans la table Artiste, selon cet ordre :
Id
Nom
Prénom
Nationalité
1
Moustaki
Georges
française
2
Modja
Inna
malienne
3
LeForestier
Maxime
française
4
Vian
Boris
française
5
DePalmas
Gérald
française
6
June
Valérie
américaine
7
Higelin
Jacques
française
8
Berger
Michel
française
9
Goldman
Jean-Jacques
française
10
Mitchell
Eddy
française
11
Katerine
Philippe
française
12
Estefan
Gloria
cubaine
13
Marley
Bob
jamaicaine
14
Azrié
Abed
française
On met en place un index sur l’attribut nom de cette table.
Construire l’arbre B d’ordre 2 (4 entrées max par bloc) correspondant à cet ensemble d’enregistrements,
en respectant l’ordre d’insertion. Donner les étapes de construction
intermédiaires importantes (celles qui produisent un changement de la structure de l’arbre).
On considère que cet arbre B est stocké à raison d’un nœud
par bloc sur disque. On recherche les noms des artistes dont
l’initiale du nom se trouve entre “B” et “I” (inclus).
Combien de blocs disque doivent être chargées au minimum pour répondre
à cette requête en utilisant l’arbre B+ ? Justifier.
Correction
Deux graphes simples
Il s’agit ici d’une requête par intervalle, facilement réalisable avec un arbre B.
On commence par faire une recherche du premier enregistrement dont
l’initiale du nom est égale ou immédiatement supérieure à “B”.
On a trouvé le premier enregistrement répondant à la requête
(en parcourant ici 3 feuilles de l’arbre B), il suffit
d’exploiter le chaînage des feuilles pour trouver les autres enregistrements
(en parcourant ici encore 2 feuilles de l’arbre B). On
charge donc 5 blocs d’index. Il faut ensuite récupérer
les données pointées par l’index sur disque. Au mieux, toutes
les données sont stockées dans une même bloc (peu probable mais
possible…). Donc on charge au minimum 6 blocs.
Donnez le plan d’exécution sous la forme de votre choix, en supposant
que les seuls index sont ceux sur les clés primaires
Qu’est-ce qui change si on crée l’index sur le nom des artistes?
Soit maintenant le plan d’exécution suivant:
0 SELECT STATEMENT
1* MERGE JOIN
2 SORT JOIN
3* NESTED LOOPS
4* TABLE ACCESS FULL Ecoute
5 TABLE ACCESS BY ROWID Chanson
6 INDEX RANGE SCAN IDX-Chanson_ID
7 SORT JOIN
8 TABLE ACCESS FULL Album
1 - access(Chanson.id_album=Album.id)
3 - access(Ecoute.id_chanson=Chanson.id)
4 - access(date=29/05/2013)
Questions:
Donnez la requête correspondante
Expliquez ce plan, en indiquant notamment quels index existent, et lesquels
n’existent pas
Correction
L’index sur Ecoute(idAbonne) ne sert à rien dans cette requête. Les deux index suivants
peuvent être utilisés pour la jointure entre Chanson et Ecoute
(donc boucles imbriquées avec index) mais pas tous les deux en même temps,
il faut choisir l’un des deux (les deux options sont acceptées ici).
Ensuite tri-fusion ou boucles-imbriquées acceptés pour la seconde jointure
(dépend de la taille des tables). Ci-dessous, un tri-fusion pour la seconde jointure.
Quels index pouvez-vous ajouter pour optimiser cette requête, et quel est le plan d’exécution
correspondant?
Correction
L’index sur Album(id) est utilisé pour la seconde jointure qui devient donc une jointure
par boucles imbriquées avec index. L’index sur Ecoute(date) n’est pas utilisé pour
la jointure entre Ecoute et Chanson mais pour effectuer une sélection des
enregistrements sur la table directrice Ecoute dans la première jointure.
0 SELECT STATEMENT
1* NESTED LOOPS
2* NESTED LOOPS
3 TABLE ACCESS BY ROWID Ecoute
4* INDEX RANGE SCAN IDX-Ecoute_DATE
5 TABLE ACCESS BY ROWID Chanson
6 INDEX RANGE SCAN IDX-Chanson_IDChanson
7 TABLE ACCESS BY ROWID Album
8 INDEX RANGE SCAN IDX_Album_ID
Si on ne pose que des verrous exclusifs (par exemple avec la clause forupdate),
\(r_3[x]\) (donc \(T_3\)) est bloqué par \(T_2\) qui a effectué \(r_2[x]\).
\(T_3\) doit attendre la fin des deux autres transactions pour reprendre.
On suppose que l’on peut placer 2 enregistrements par bloc.
On veut construire un index non-dense sur le premier attribut.
Que faut-il faire au préalable ? Donnez les différents niveaux de l’index.
Construire un arbre B sur le second attribut,
en supposant 2 enregistrements et trois pointeurs par bloc au maximum.
On dispose des deux index ci-dessus. Quel est le
nombre d’entrées/sorties dans le pire des cas
pour la recherche des animaux dont le nom commence par un “g”,
et pour la recherche des animaux dont l’identifiant est compris
entre 40 et 50 (prendre en compte les accès à l’index et
au fichier).
On veut trier ce fichier (tel qu’il est donné dans l’énoncé)
avec seulement 3 blocs, toujours
en supposant qu’on peut placer deux enregistrements par bloc.
Décrivez le déroulement de l’algorithme de tri-fusion,
et donnez le nombre total d’entrées/sorties, sans compter
l’écriture finale du fichier trié.
Et finalement il reste (anguille,saumon) à la racine, soit 4 niveaux.
Standard.
La première recherche doit ramener trois enregistrements.
Dans le cas de l’index non-dense, le fichier est trié.
On peut donc parcourir séquentiellement à partir du
premier “g”. On lit donc 4 blocs dans l’index pour arriver aux feuilles,
puis 2 blocs en parcours séquentiel.
Les enregistrements ne sont pas ordonnés pour l’arbre B. Il faut donc, après le
parcours d’index, parcourir les feuilles pour les valeurs de clé entre 40 et 50,
avec une lecture de bloc (au pire) pour chacune.
On utilise 2 blocs pour l’entrée, un pour la sortie. Dans
les 2 blocs on place 4 enregistrements. Il y a 20 animaux
donc (1) 5 fragments initiaux de 2 blocs, puis (2)
2 fragments de 4 blocs, et
un fragment de 2 blocs, puis (3) un fragment de 8 blocs et un de deux.
Et on termine par une lecture. Donc coût = \(3 \times 2 \times 10 + 10 = 70\).
Plus subtil: on peut utiliser 3 blocs pour la phase de tri, et diviser la mémoire
en 2+1 seulement pour la phase de fusion.
On considère trois relations
\(R(**{a},b,d)\), \(S(**{c},d,e)\) et \(T(**{e},f)\) dont les clés
primaires sont respectivement \(a\), \(c\) et \(e\).
\(R\) contient 200 000 enregistrements, \(S\) 20 enregistrements et \(T\) 500 enregistrements. Des index
sont créés sur les clés primaires, et on suppose que
pour chaque relation, y compris celles qui sont calculées par une jointure,
on stocke 10 enregistrements par bloc.
On suppose que tous les index sont toujours en mémoire principale
(donc pas d’entrée/sortie pour les accès aux index).
On dispose de 20 blocs en mémoire pour traiter les jointures.
Les jointures se font sur les attributs de même nom.
Quel est le nombre maximal
d’enregistrements dans \(S \Join T\) (indiquez également la condition
pour que ce nombre maximal soit atteint) ? Quelle est la clé de la
relation obtenue ?
Mêmes questions pour \(R \Join S \Join T\).
Décrire le fonctionnement de l’algorithme par boucles
imbriquées pour calculer \(S \Join T\), en exploitant au mieux la
mémoire disponible.
Indiquez le coût en entrées/sorties pour cet algorithme.
Même question l’algorithme par boucles
imbriquées indexées.
Décrire un plan d’exécution
pour calculer \(R \Join S \Join T\)et
évaluer son coût (nombre de blocs lus).
Une application a inséré des enregistrements dans \(S\)
qui en contient maintenant 5 000. Le
SGBD gère un histogramme qui indique que la sélectivité
de l’attribut \(d\) est 5 (autrement dit, une sélection
sur \(R\) ou \(S\) pour une valeur de \(d\) ramène 5% des enregistrements).
Quelle taille peut-on estimer pour \(R \Join S\) ?
Je n’ai toujours que 20 blocs en mémoire.
Décrire l’algorithme de jointure par hachage pour \(R \Join S\)
et évaluer son coût.
Correction
Il y a au plus 20 enregistrements, et il faut pour l’atteindre
que la clé étrangère soit notnull,
et le respect de l’intégrité référentielle de \(S\) vers \(T\). La clé
est \(c\) (il y a dépendance fonctionnelle de \(c\) vers \(e\)).
Dans le pire des cas il y a \(200~000 \times 20\) enregistrements
(s’il y a une seule valeur pour \(d\)).
On met \(S\) en mémoire (donc 2 blocs) et on l’organise
comme une table de hachage sur l’attribut \(S.e\). Puis on lit \(T\) séquentiellement (50 blocs),
en cherchant pour chaque enregistrement \((e_i,f_i)\) de \(T\) le ou les
enregistrements correspondant dans la table de hachage.
Coût: 52 blocs.
On parcourt \(S\) séquentiellement (2 blocs), pour chaque enregistrement
\((c, d,e)\) (il y en a 20), on utilise l’index pour accéder à \(T\). Pour chaque entrée
trouvée dans l’index il faut lire un bloc (au pire) sur le disque.
Coût: 2 + 20 blocs.
On constate qu’il n’existe pas d’index disponible
pour la jointure avec \(R\), car la clé primaire de \(R\) ne se trouve
en tant que clé étrangère ni dans \(S\) ni dans \(T\).
L’algorithme : on évalue \(S \Join T\), comme indiqué précemment.
Il faut ensuite choisir un algorithme de jointure sans index.
Etant donnée la petite taille de \(S \Join T\), on choisit
la jointure par boucles imbriquées. On construit une table de hachage en mémoire sur le résultat de \(S \Join T\)
(2 blocs au maximum, clé de hachage : \(d\)) ; on lit séquentiellement \(R\)
en joignant chaque enregistrement avec la table de hachage.
La lecture de \(R\) est prédominante : 20 000 blocs à lire séquentiellement.
Toutes les autres possibilités sont moins bonnes, à cause de la taille
du résultat de la jointure entre \(R\) et une autre table. Penser par exemple
au coût qui résulterait d’un tri préalable de \(R\) sur l’attribut \(d\) pour
une jointure par tri-fusion.
Pour chaque tuple de \(R\), on trouve \(5000 \times 0,05 = 250\)
enregistrements dans \(S\): 50 M d’enregistrements au final.
Jointure par hachage : je hache \(S\) en 25 fragments de
200 enregistrements chacun (20 blocs en mémoire). Ensuite je hache \(R\) en 25
fragments également (leur taille m’importe peu). Puis je fais la jointure
entre chaque paire de fragmentss. Coût (très approximatif) =
\(3 \times (|S| + |R|) = 3 \times (20 000 + 500) = 61 500\).
On considère le système d’information
d’un institut de sondage, avec les tables relationnelles
suivantes (les attributs ou combinaisons d’attributs qui forment
une clé unique sont en gras).
Personne (numPers, nom, sexe, numCat)
Question (numQ, description)
Avis (numQ, numPers, reponse)
L’exécution suivante est reçue par le système de l’institut de sondage :
Parmi les programmes qui s’exécutent dans le système,
il y a ModifierAvis(nomPers,numQuestion,nouvelle_réponse), qui modifie
la réponse donnée par
la personne nomPers à la question numQuestion
en nouvelle\_réponse
Si les enregistrements de \(H\) sont des nuplets des relations de la base
de données, montrez (en justifiant votre réponse)
quelles transactions de \(H\) pourraient provenir de ModifierAvis.
Vérifiez si \(H\) est sérialisable en identifiant
les conflits et en construisant le graphe de sérialisation.
Montrer qu’il existe des lectures sales,
et expliquez les conséquences possibles.
Quelle est l’exécution obtenue par verrouillage
à deux phases à partir de \(H\)?
(Question bonus, pour 2 points). Quelle est l’exécution obtenue avec
l’algorithme de concurrence par versionnement ?
On suppose que toutes les transactions débutent
au même moment.
Correction
Les transactions sont \(T_1 = r_1[x] w_1[x]\), \(T_2 = r_2[y] r_2[x] r_2[z] w_2[z]\),
\(T_3 = r_3[y] w_3[y] r_3[z] w_3[z]\)
ModifierAvis doit lire un avis et
le modifier. On peut donc considérer qu’il s’agit de \(T_1\). \(T_2\)
est également une possibilité, en supposant qu’on lit d’abord la personne
puis la question.
– Les conflits sont: \(w_1[x] \to r_2[x]\), \(r_2[y] \to w_3[y]\),
\(r_3[y] \to w_2[z]\) et \(w_2[z] \to w_3[z]\). On trouve un cycle
\(T_2\) et \(T_3\) donc \(H\) n’est pa sérialisable.
\(r_2[x]\) est une lecture sale (car précédée de \(w_1[x]\)).
Si \(T_1\) s’interrompt avant le commit, la valeur
lue par \(r_2[x]\) n’existera plus et \(T_2\) risque de
valider un état incohérent.
On suppose que chaque enregistrement a une taille de
250 octets et que chaque bloc a un entête de 150 octets.
Indiquez le nombre de blocs nécessaires si la table
contient 3 millions de livres. La taille d’un bloc est de 4 000 octets.
Correction
Il y a 3 850 octets utiles dans un bloc. On place \(\lfloor 3850/250 \rfloor =15\) enregistrements par bloc.
Il faut \(\lceil \frac{3 000 000}{15} \rceil = 200 000\) blocs.
On décide de trier la table Livre sur la date de publication et de construire
un index non-dense à un niveau. Combien contient-t-il d’entrées,
Sachant qu’une adresse et une date occupent chacun 8 octets, combien d’entrées met-on dans
un bloc et combien de blocs sont nécessaires ?
Correction
Il y a 200 000 entrées de 16 octets chacune.
On place \(4000/16=250\) entrées par bloc. Il faut
\(\lceil \frac{200 000}{250} \rceil = 800\) blocs.
On insère successivement les enregistrements suivants dans la table
Personne, selon cet ordre :
id
nom
prénom
âge
1
Martin
Georges
30
2
Dubois
Inna
20
3
Thomas
Maxime
14
4
Richard
Boris
45
5
Petit
Gérald
32
6
Durand
Valérie
43
7
Leroy
Jacques
34
8
Simon
Michel
22
9
Laurent
Jean-Jacques
63
10
Moreau
Eddie
12
11
Morel
Philippe
15
12
Perrin
Gloria
18
13
Clement
Bob
19
14
Dumont
Claire
67
On met en place un index sur l’attribut âge de cette table.
Construire l’arbre B d’ordre 2 (4 entrées par bloc)
correspondant à cet ensemble d’articles, en respectant l’ordre d’arrivée.
Donner les étapes de construction intermédiaires importantes (celles qui produisent
un changement de la structure de l’arbre).
Correction
Standard
On considère que cet arbre B est stocké à raison d’un nœud par bloc sur disque. On recherche les noms des personnes dont l’âge est entre 20 et 40 ans (inclus).
Combien de blocs disque doivent être chargés au pire des cas pour répondre à cette requête en utilisant l’arbre B ? Justifier.
Correction
Il s’agit ici d’une requête par intervalle: on commence par chercher les enregistrements pour lesquels
l’âge est égal à 20 (lecture de 3 blocs). Il suffit ensuite
d’exploiter le chaînage des feuilles pour trouver les autres enregistrements, en parcourant
ici encore 1 bloc dans l’arbre B. On charge donc 4
blocs d’index. Il faut ensuite récupérer les données
pointées par l’index vers le fichier sur disque. Dans le pire des cas,
il faut lire un bloc pour chaque enregistrement.
Donc on charge au pire 9 blocs.
Donnez le plan d’exécution classique des boucles imbriquées indexées.
Correction
On parcourt séquentiellement la table Livre. Pour chaque livre
obtenu on utilise l’identifiant de l’auteur pour une recherche par index
sur la table Personne (donc, parcours d’index suivi d’un accès direct).
On considère maintenant la requête suivante, avec une jointure entre Livre et Emprunt
Donner de même le plan d’exécution utilisant le plus possible les index
et indiquer où se situe la sélection sur le titre.
Correction
On parcourt Emprunt, on utilise l’index sur la table Livre,
et la sélection se fait au moment de l’accès direct.
Peut-on éviter tout parcours séquentiel en ajoutant un index sur
le titre des livres ? Justifiez votre réponse.
Correction
Pas vraiment, car même en cherchant le livre par l’index, on ne
peut pas échapper à un parcours séquentiel de la table Emprunt
dont l’index (dans l’ordre donné) ne permet pas une recherche basée
sur id_livre.
On suppose qu’il n’y a pas d’index sur la table Livre.
Elle occupe 50 MO, alors que la table Emprunt en occupe 200.
Le système dispose de 100 MO de mémoire RAM pour effectuer la jointure.
Expliquer l’algorithme de jointure qui vous semble le plus efficace.
Combien de MOs seront lus au final ?
Correction
On charge la table Livre en mémoire sous la forme d’une
table de hachage. Puis on parcourt séquentiellement Emprunt
en cherchant le livre à chaque fois dans la table de hachage.
On va lire une seule fois chaque table : 250 MO au total.
