Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UFR Sciences et Techniques IUP Blois Master SIR – 1° année BD Avancées TRAVAUX

UFR Sciences et Techniques IUP Blois Master SIR – 1° année BD Avancées TRAVAUX DIRIGÉS Enseignant Jean-Yves ANTOINE (Jean-Yves.Antoine AT univ-tours.fr) Bases de Données Avancées Sécurité des données CONTRÔLE DES ACCES CONCURRENTS : EXERCICES THEORIQUES Exercice 1 — Schémas d'exécution sérialisables Dans cet exerice, on considère deux transactions concurrentes qui veulent mettre à jour une donnée O1. Par exemple : T1 : UPDATE Table_prix SET prix = prix + 50 T2 : UPDATE Table_prix SET prix = prix * 2 L'exécution de ces deux transactions revient à lire les données PRIX dans un tampon, faire la mise à jour désirée sur ce tampon puis réécrire la valeur obtenue dans PRIX (validation de la transaction). Problème de concurrence — On suppose qu'il n'existe pas de processus de contrôle des accès concurrents dans notre SGBD. Suivant les circonstances, on peut alors obtenir les deux schémas d'exécution suivants (on ne représente pas les calculs sur les tampons, qui ne concernent pas directement la base de données). Schéma 1 T1 : read(Prix) ; T2 : read(Prix) ; T1 : write(Prix) + COMMIT ; T2 write(Prix) + COMMIT. Schéma 2 T1: read(Prix) ; T2: read(Prix) ; T1: write(Prix)+COMMIT ; T2: read(Prix) ; T2: write(T2) + COMMIT 1. Initialement, PRIX vaut 250. Donnez les valeurs obtenues en fin de schéma dans les deux cas. Quel schéma d'exécution pose problème ? Comment a-t-on qualifié ce problème en cours ? 2. A priori, lesquels des deux schémas sont sériels ? sérialisables ? Ce résultat est-il compatibles avec les observations de la question précédente ? 3. Construisez le graphe de précédence des deux schémas. Là encore, retrouve-t-on nos attentes ? Exercice 2 — Sérialisation par verouilage d'un schéma d'exécution Dans cet exerice, on considère trois transactions concurrentes qui veulent mettre à jour deux données O1 et O2 : T0 UPDATE Table_produit_O1 SET nb = 15 UPDATE Table_produit_O2 SET nb = 20 T1 UPDATE Table_produit_O1 SET nb = nb + 1 UPDATE Table_produit_O2 SET nb = nb – 1 T2 UPDATE Table_produit_O1 SET nb = nb + 3 UPDATE Table_produit_O2 SET nb = nb – 3 T3 SELECT nb FROM Table_produit_O1 SELECT nb FROM Table_produit_O2 Les transactions sont lancées dans l'ordre T0, T1, T2 puis T3. On envisage trois schémas d'exécutions Schéma 1 T0 écriture O1 T0 écriture O2 T1 lecture O1 T1 ecriture O1 T2 lecture O1 T2 ecriture O1 T3 lecture O1 T1 lecture O2 T1 ecriture O2 T2 lecture O2 T2 ecriture O2 T3 lecture O2 © J-Y Antoine — 2 — Bases de Données Avancées Schéma 2 T0 écriture O1 T1 lecture O1 T1 ecriture O1 T0 écriture O2 T2 lecture O1 T2 ecriture O1 T1 lecture O2 T2 lecture O2 T1 ecriture O2 T2 ecriture O2 T3 lecture O1 T3 lecture O2 Schéma 3 T0 écriture O1 T0 écriture O2 T3 lecture O1 T3 lecture O2 T1 lecture O1 T1 ecriture O1 T2 lecture O2 T2 ecriture O2 T1 lecture O2 T1 ecriture O2 T2 lecture O1 T2 ecriture O1 1. Lesquels de ces schémas d'éxécutions sont sériels, sérialisables, sérialisables par permutation ? 2. Donnez les graphes de précédences de ces schémas d'exécution et retrouvez les résultats précédents. 3. Intéressons nous au(x) schéma(s) d'exécution(s) non sérialisable(s). Montrez que ce(s) schéma(s) ne peut être exécuté par une procédure de verrouillage à double phase (2PL) utilisant deux modes : écriture protégée et lecture protégée. 4. On considère toujours ce(s) schéma(s) d'exécution(s). Que se passe-t-il si notre protocole de verrouillage n'est plus 2PL mais utilise des verrous courts. 5. Montrez maintenant qu'un verrouillage 2PL avec verrous en écriture protégée et en lecture protégée n(autorise pas le déroulement de tous les schémas d'exécutions sérialisables. Exercice 3 — Modes de verrouillages On considère le schéma d'exécution suivant : T0 lecture O1 T0 écriture O1 T1 lecture O1 T0 lecture O2 .... Dans le cadre d'un verrouillage 2PL (verrous longs), précisez si la transaction T1 peut démarrer suivant les modes de verrouillage employés ci-dessous. Justifiez vos réponses. 1. Lecture protégée / Ecriture exclusive 2. Lecture protégée / Ecriture protégée 3. Lecture non protégée / Ecriture exclusive 4. Lecture non protégée / Ecriture protégée 5. Lecture exclusive / Ecriture non protégée © J-Y Antoine — 3 — Bases de Données Avancées Optimisation des bases de données INDEXATION : EXERCICES THEORIQUES Exercice 4 — Indexation par arbre B+ de chaînes de caractères Comme nous l'avons vu en cours, l'intérêt des index triés hierarchiques à base d'arbre B est d'accélérer l'accès ordonné aux données ou par plage de valeurs. Ce type de requête concerne bien entendu les attributs numériques, mais aussi les données de type chaîne de caractères pour lesquelles un ordre bien connu est l'ordre lexicographique du dictionnaire. Dans cet exercice, nous allons ainsi suivre la construction d'un index organisant dans un arbre B+ des données de ce type chaînes. 1. Initialisation de l'index — Pour les besoins de l'exercice, on suppose que l'arbre utilisé est un arbre B+ d'ordre 1 (dans la pratique, l'ordre serait bien entendu bien plus élevé). Sachant que l'arbre doit être équilibré, donné les états sucessifs de ce dernier suite aux ajouts de données suivants: 1) branche puis 2) fanal et enfin 3) arbre. 2. Insertion de données dans l'index — Poursuivez, étape par étape, on considérant maintenant les ajours suivants : 1) école puis 2) drap, 3) girafe, 4) draperie, 5) drapeau, et enfin 6) grue. 3. Suppression de données dans l'index — On suppose maintenant que la suppression de tuples dans la base de données entraîne la suppression de certaines valeurs du champ indexé. Donnez les états successifs de l'arbre d'indexation faisant suite aux suppressions suivantes : 1) branche puis 2) fanal et enfin 3) drap. Exercice 5 — Indexation par tables de hachage : comparaisons Un autre mode d'indexation fréquemment utilisé par les SGBD est le hachage. Dans cet exercice, nous allons comparer différentes techniques de hachage pour l'indexation de données purement numériques (nombres entiers). 1. Hachage statique — Nous avons vu en cours que ce type de hachage à espace d'indexation fixe n'est pas adapté à la problématique des bases de données. Nous allons le vérifier par l'exemple. On considère ici une table de hachage comportant 4 pages de capacité maximale d'indexation de 2 éléments par page (là encore, nous sommes dans un cas jouet bien éloigné des valeurs utilisées en pratique. Deux fonctions de hachage seront considérées en parallèle pour indexer les éléments : dans le premier cas, la fonction de hachage indexera les nombres entiers suivant leur vameur modulo 4. Dans l'autre cas, la fonction retournera la somme des digits du nombre, modulo 4 (par exemple, pour le nombre 456, on a comme résultat 13 = 4+5+6 modulo 4). a) donnez l'évolution des deux tables de hachage correspondant aux insertions successives des nombres suivants : 16, 37, 8, 2, 53 et enfin 12. b) combien de valeurs ont-elles pu être indexée avant d'arriver à une saturation de l'index. En comparant ce nombre a la capacité théorique de l'index, pensez-vous qu'une indexation statique aussi simple soit bien équilibrée ? 2. Hachage dynamique extensible — Afin de dépasser les limitations du hachage statique, on s'intéresse cette fois à une indexation de type hachage extensible. Comme dans la question précédente, les pages de la table de hachage ne pourront contenir au maximum que 2 éléments indexés. Comme en cours, l'indexation se fera sur les bits de poids faible des nombres indexés, en commençant initialement par ne considérer que le dernier bit des données. a) donnez l'évolution de la table de hachage ainsi obtenue suite aux insertions successives des nombres suivants : 16, 37, 8, 2, 53 et enfin 12. Cette insertions conduisent-elles à des niveaux de découpage bien équilibrés ? b) montrez maintenant comment évolue la table de hachage suites aux suppressions successives suivantes : 37, 2 et enfin 8. 3. Hachage dynamique linéaire — Pour terminer, nous allons étudier une stratégie de hachage linéaire. Comme dans la question précédente, les pages de la table de hachage ne pourront contenir au maximum que 2 éléments indexés, auxquels on rajoute une page de débordement de 4 éléments. Comme précédemment, l'indexation se fera sur les bits de poids faible des nombres indexés suivant le niveau de découpage atteint par le pointeur dynamique de la table. a) donnez l'évolution de la table de hachage ainsi obtenue suite aux insertions successives des nombres suivants : 16, 37, 8, 2, 53 et enfin 12. Tous les éléments sont-ils bien indexés à la fin de ces différentes insertions. © J-Y Antoine — 4 — Bases de Données Avancées b) on ajoute enfin le nombre 1 dans l'index. Que se passe-t-il pour le nombre présent dans la page de débordement ? Que devient par contre le nombre 1. L'index obtenu est-il plus équilibré que l'index extensible équivalent ? Exercice 6 — Optimisation de bases de données (examen 2004-2005 - 3 points) On considère un attribut d’une table d’une base de données qui prend pour occurrences à un instant donné les valeurs suivantes : {1,2,5,8,9,12,14}. Afin d’optimiser l’accès aux données, on désire indexer uploads/Litterature/ bda-td.pdf