12. Annales des examens

Examen blanc du 20 janvier 2020 (sans concurrence)

Stockage et indexation

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?

• 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?

• 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?

• Même question avec l’index dense, pour une recherche sur l’attribut B.

Index et optimisation

Soit les tables relationnelles suivantes (les attributs qui forment une clé sont en gras):

• Produits (code, marque, desig, descr). NB: code : identifiant du produit, marque : marque du produit, desig : désignation du produit, descr : description.

• PrixFour (code, nom, prix). NB: code : code du produit, nom : nom du fournisseur.

• NoteMag (code, titre, note). NB: code : code du produit, titre : titre du magazine, note : note entre 1 et 10 du produit dans le magazine)

Voici une instance de la table NoteMag.

Code	Titre	Note
“A345”	“HIFI”	8
“P123”	“Audio Expert”	6
“X254”	“HIFI”	7
“K783”	“Son & Audio”	3
“P345”	“HIFI”	6
“P512”	“Audio Expert”	8
“L830”	“Audio Expert”	8
“M240”	“”HIFI””	6

La table occupe plusieurs blocs dont chacun peut contenir au maximum 3 n-uplets.

• Construire un arbre B+ sur l’attribut code, avec 4 entrées par bloc au maximum.

• Est-il utile d’indexer l’attribut titre? Pourquoi?

• Soit la requête suivante :

  select *
  from NoteMag
  where code between 'A000' and 'X000';
  

  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 ?

On donne ci-dessous une requête SQL et le plan d’exécution fourni par Oracle :

select desig, marque, prix
from Produits, PrixFour, NoteMag
where Produits.code=PrixFour.code
and Produits.code=NoteMag.code
and note > 8;

Plan d’exécution :

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

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

Examen blanc juin 2020

On prend pour exemple une base de données qui sert à la gestion d’un site web de diffusion de la musique en streaming:

• Abonné (id, nom, prénom, typeAbonnement, dateDébut)

• Artiste (id, nom, prénom, nationalité)

• Album (id, nom, idArtiste, annéeSortie)

• Chanson (id, nom, idAlbum)

• Ecoute (idAbonné, idChanson, date, téléchargé)

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.

Questions sur le schéma (3 points)

• Pour la table Ecoute, identifiez les clés primaires et étrangères.

• Donnez la commande SQL pour créer la table Ecoute.

• Une recherche par index est-elle possible si on interroge la table Ecoute sur l’id d’une chanson (justifier)?

• Une recherche par index est-elle possible si on interroge la table Ecoute sur l’id d’un abonné (justifier)?

Stockage et indexation (4 points)

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.

Optimisation (7 points)

Soit la requête suivante:

select Album.nom
from Artiste, Album
where Artiste.id=Album.idArtiste
and Artiste.nom='Moustaki'

Questions:

• 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

• Quels index pouvez-vous ajouter pour optimiser cette requête, et quel est le plan d’exécution correspondant?

Concurrence (6 points)

Soit l’exécution concurrente suivante :

\[H = r_2[x] r_3[x] w_1[y] r_3[y] w_3[y] r_1[z] w_2[y] c_1 w_3[z] w_2[z] c_3 c_2\]

Questions

• Donner la liste des conflits de H

• Donner le graphe de sérialisation de H. Que pouvez-vous déduire de ce graphe ?

• Donner l’exécution finale obtenue par application de l’algorithme de verrouillage à deux phases. Donner le détail du déroulement de l’algorithme.

• Que se passerait-il si on ne posait que des verrous exclusifs?

Examen juin 2022

Stockage et indexation (6 points)

Voici le contenu d’un fichier animaux:

(jaguar, 17), (chameau, 22), (gnou, 1), (girafe, 13), (chat, 3),
(lion, 8), (dauphin, 40), (zèbre, 11), (hamster, 6), (hyène,9),
(licorne, 2), (babouin, 12), (piranha,55), (saumon, 82), (bar,44),
(anguille, 43), (gorille,98), (tigre,76), (requin, 56), (escargot,45).

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

Jointures et optimisation (9 points)

On considère trois relations \(R(\textbf{a},b,d)\), \(S(\textbf{c},d,e)\) et \(T(\textbf{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.

Concurrence (6 points)

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 :

\[H : r_1[x] r_2[y] w_1[x] r_3[y] r_2[x] w_3[y] r_2[z] C_1 r_3[z] w_2[z] C_2 w_3[z] C_3\]

Répondez aux questions suivantes sur \(H\).

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