Le Hachage est particulier au logiciel utilisé, les exercices corrigés suivant explorent les techniques les plus utilisées.
Introduction sur le Hachage
Les articles d’un fichier aléatoire (on parle également de fichier haché) sont répartis dans des paquets composés d’une ou plusieurs pages disque. Une fonction de hachage h associe à une valeur de clé (discriminante ou non) un entier représentant un numéro de paquet. Tous les articles dont la valeur de clé est telle que la fonction h associe un même numéro de paquet sont stockés ensemble dans ce paquet.
Lors d’une recherche sur une clé d’accès, la fonction h détermine de façon unique le paquet contenant tous les articles répondant au critère de recherche. Cette fonction h est rarement injective. Soient c1 et c2 deux clés différentes, on appelle collision le fait que h(c1) = h(c2).
Ce phénomène de collision impose d’une part de vérifier que chaque article accédé satisfait bien le critère de recherche et d’autre part rend difficile l’équi-répartition des articles dans les différents paquets, compliquant la gestion de la mémoire secondaire. De plus, la fonction h conserve rarement l’ordre des clés (c1<c2 =/=> h(c1)<h(c2)), rendant impossibles les recherches avec un critère d’inégalité.
La première section de cette partie est consacrée à l’étude des organisations par hachage statique dans lesquelles le nombre de paquets de hachage est fixé statiquement à la création du fichier. L’inéqui-répartition des articles dans les différents paquets peut entraîner le débordement de certains paquets saturés, dégradant de façon importante les performances des opérations de recherche et d’insertion d’articles dans le fichier.
La seconde section de ce thème présente les organisations par hachage dynamique évitant ce problème au prix d’une plus grande complexité des mécanismes mis en oeuvre.
Exercice Hachage statique
Un fichier organisé par hachage statique est décomposé en N paquets de taille fixe lors de sa création. La fonction de hachage associée détermine pour chaque valeur de clé d’accès un numéro de paquet compris entre 0 et N-1. Le choix de la fonction de hachage est primordial pour assurer une équi-répartition des articles dans les N paquets.
Ce choix doit être guidé par la distribution, rarement uniforme, des clés dans le fichier. Le nombre de collisions (c1 diff c2 et h(c1) = h(c2)) est d’autant plus grand que le nombre de paquets de hachage est petit par rapport au nombre d’articles à insérer dans le fichier. Les collisions vont provoquer une saturation de certains paquets de hachage et entraîner le débordement de ces paquets.
Question 1
Quels sont les critères permettant de choisir la taille d’un paquet de hachage ? Proposer un format de stockage des articles dans un paquet de hachage.
Question 2
Proposer différentes formes de fonctions de hachage produisant des nombres aléatoires compris entre 0 et N-1 à partir d’une clé d’accès.
Question 3
On suppose dans un premier temps que les paquets saturés débordent dans les paquets non encore saturés. Proposer différentes techniques permettant de stocker et de retrouver ultérieurement des articles en débordement. Ces techniques sont-elles adaptées dans le cas de collisions nombreuses ?
Question 4
On considère désormais que le fichier comporte une zone indépendante de débordement dont la taille est fixée à la création du fichier. Les N paquets de hachage initiaux sont appelés zone primaire afin de les distinguer de la zone de débordement.
Proposer de nouvelles techniques de débordement exploitant ce découpage en deux zones indépendantes. Quel est l’apport de ces techniques par rapport à celles introduites dans la question précédente ? Ces techniques résolvent-elles de façon complètement satisfaisante le problème des collisions ? Conclure sur les avantages et inconvénients des organisations statiques.
Question 1
La taille d’un paquet de hachage doit être la plus grande possible afin de limiter les débordements en cas de collision. En revanche, un paquet doit pouvoir être lu en une seule E/S. La taille d’un paquet de hachage est donc limitée par la taille d’une page disque (considérée comme l’unité d’E/S). Les informations de débordement dépendent de la stratégie employée (bit indicateur de débordement ou numéro du premier paquet de débordement (cf. Question 3).
Question 2
De nombreuses fonctions de hachage sont envisageables pour déterminer un numéro de paquet compris entre 0 et N-1 à partir d’une valeur de clé. Les plus courantes sont :
– Division entière: c’est la fonction la plus simple et la plus fréquemment employée. Le résultat de cette fonction, couramment appelée modulo, est le reste de la division entière de la clé par le nombre de paquets de hachage N. Il est recommandé de s’assurer que N est un nombre premier afin de limiter les risques de collisions. A titre d’exemple, soit un fichier haché dans 11 paquets, l’article de clé 35 sera placé dans le paquet numéro 2 (2 = 35 modulo 11). Si la clé d’accès n’est pas numérique, la fonction modulo est appliquée à la représentation binaire de cette clé, considérée comme un entier.
– Extraction du carré: la clé est tout d’abord élevée au carré puis un ensemble de bits (généralement les bits de poids faibles ou de poids moyens) est extrait du nombre obtenu pour former un numéro de paquet. Etant donné que k bits permettent d’adresser 2k paquets, on extraira log_2 N bits pour former un numéro de paquet compris entre 0 et N-1.
– Pliage généralisé: si l’on considère qu’un numéro de paquet est exprimé par p bits (avec p = log2N), on divise la clé par tranches de p bits et on applique une opération binaire « ou exclusif » entre toutes ces tranches afin d’obtenir une nouvelle chaîne de p bits identifiant un paquet. L’opération « ou exclusif » est préférée à l’opération « et » qui privilégie l’apparition de nombreux 0 dans la chaîne de bits résultat et à l’opération « ou » qui privilégie l’apparition de nombreux 1.
Question 3
Si le paquet désigné par la fonction de hachage est saturé, il faut stocker l’article en insertion dans un des N-1 paquets restants et être capable de le retrouver ultérieurement. Plusieurs techniques de débordement sont envisageables :
– Adressage ouvert: supposons que le paquet saturé soit le paquet i, cette technique consiste à rechercher séquentiellement une place libre pour l’article en insertion dans les paquets i+1, i+2, …, i+k, jusqu’à trouver un emplacement de taille suffisante. On mémorise dans le paquet i le numéro du premier paquet dans lequel il a débordé afin d’accélérer les recherches ultérieures des articles en débordement. La recherche de tous les articles appartenant au paquet i s’effectue de la façon suivante.
Les articles stockés dans le paquet i sont tout d’abord lus séquentiellement en vérifiant pour chacun d’eux qu’il appartient bien au paquet i (une comparaison de clé permet d’éliminer les articles d’autres paquets stockés éventuellement en débordement dans le paquet i). Les articles du paquet i stockés en débordement sont ensuite recherchés séquentiellement dans les paquets suivants à partir du premier paquet de débordement.
– Chaînage en débordement: cette technique est identique à l’adressage ouvert mais tous les articles appartenant à un même paquet sont ici chaînés entre eux. Ce chaînage évite le coût d’une recherche séquentielle pour retrouver tous les articles d’un même paquet stockés en débordement. En revanche, outre le coût de stockage supplémentaire lié au chaînage, cette technique peut engendrer de nombreuses E/S si la chaîne des articles est longue et si le chaînage passe fréquemment d’un paquet à l’autre (on peut alors être amené à lire plusieurs fois le même paquet). Dans le pire des cas, le parcours du chaînage peut générer une E/S pour récupérer chaque article (cf. Chapitre 2, question 4).
– Table d’adresse des articles en débordement: cette technique, très similaire à la technique du chaînage en débordement, stocke les adresses de tous les articles en débordement dans une table associée à chaque paquet. Les adresses stockées dans cette table peuvent être maintenues triées afin d’éviter plusieurs lectures d’un même paquet. Cette technique pose cependant le problème de la place occupée et de la taille statique de chacune de ces tables.
– Re-hachage: si le paquet i déborde, on mémorise dans le paquet le fait qu’il a débordé et on applique une nouvelle fonction de hachage aux articles devant être insérés dans ce paquet. Cette seconde fonction génère un numéro de paquet différent de i et compris entre 0 et N-1. La recherche de tous les articles appartenant au paquet i s’effectue de la façon suivante.
Les articles stockés dans le paquet i sont tout d’abord lus séquentiellement en vérifiant pour chacun d’eux qu’il appartient bien au paquet i (afin d’éliminer les articles d’autres paquets stockés éventuellement en débordement dans le paquet i). Les articles du paquet i stockés en débordement sont ensuite recherchés dans le paquet identifié par la seconde fonction de hachage appliquée à la clé d’accès.
Ces techniques offrent une réponse au problème de gestion des articles en débordement mais aucune n’est vraiment satisfaisante si le taux de collisions est élevé. Les performances se dégradent très rapidement lors des recherches d’articles en débordement. Ce phénomène est dû au fait que les articles en débordement d’un paquet i sont stockés en lieu et place des articles d’un paquet j, provoquant rapidement un débordement du paquet j par une réaction en chaîne.
Question 4
Les techniques de débordement présentées question 3 restent applicables, à quelques modifications près, à un fichier possédant une zone de débordement indépendante. Dans le cas de l’adressage ouvert, le premier emplacement libre permettant de stocker un article en débordement n’est plus cherché dans les paquets de hachage primaires suivants mais séquentiellement en zone de débordement. Les techniques de chaînage en débordement et de table d’adresses des articles en débordement restent inchangées mais les liens de chaînage correspondent à des adresses en zone de débordement.
Enfin, la technique de re-hachage nécessite de découper la zone de débordement en P paquets de hachage. Ainsi, lors de l’insertion d’un article dans le fichier, on applique tout d’abord une division entière par N à sa clé afin de déterminer un numéro de paquet primaire. Si ce paquet primaire est saturé, on applique une division entière par P à cette même clé afin de déterminer un numéro de paquet secondaire. Si ce paquet secondaire est saturé à son tour, alors on utilise une des techniques présentées question 3 dans la zone de débordement.
L’avantage de séparer la zone primaire de la zone de débordement est d’éviter le phénomène de réaction en chaîne dû à la saturation de certains paquets générée par le débordement d’autres paquets (cf. question 3). Ici, le débordement d’un paquet primaire n’influe pas sur le taux d’occupation des autres paquets primaires. Cette gestion des débordements est donc plus robuste face à un taux élevé de collisions. Cependant, la recherche des articles en zone de débordement reste une opération coûteuse.
Conclusion : l’avantage majeur des organisations aléatoires statiques est leur simplicité de mise en oeuvre et les excellentes performances qu’elles offrent tant que les débordements de paquets sont peu nombreux. En effet, si aucun paquet n’a débordé, les organisations aléatoires statiques garantissent la recherche de tous les articles ayant une valeur de clé donnée en une seule E/S. En revanche, les débordements provoquent rapidement un effondrement des performances quelle que soit la technique de gestion des débordements employée. Ce problème nécessite une réorganisation périodique des fichiers dès que le taux de débordement dépasse un seuil de tolérance donné.
Exercice Hachage dynamique
L’objectif des organisations par hachage dynamique est de minimiser le coût des collisions en substituant aux techniques de débordement un accroissement dynamique de la taille du fichier. De très nombreuses stratégies de hachage dynamique ont été proposées dans la littérature: hachage extensible [Fagin79], hachage linéaire [Litwin80] et trie-hashing [Litwin81], pour ne citer que les plus connues.
Chacune de ces stratégies constitue une adaptation d’un principe commun : l’exploitation progressive du contenu de la clé d’accès. Supposons une clé d’accès dont le hachage produit une chaîne de k bits. Le hachage d’une telle clé permet d’adresser au plus 2^k paquets. Le fichier haché est créé initialement avec N paquets (N < 2^k) et les articles sont répartis dans ces paquets en exploitant uniquement les p premiers bits issus du hachage de leur clé (N=2^p et p < k).
En cas de saturation, un paquet est éclaté et les articles qu’il contient sont répartis en deux paquets en exploitant la valeur du (p + 1)ème bit issu du hachage de leur clé. Les méthodes de hachage dynamique se différencient suivant la stratégie employée pour choisir le paquet à éclater à chaque saturation.
Question 5
Dans la méthode du hachage extensible [Fagin79], un paquet est éclaté en deux dès l’instant où il devient saturé. On peut représenter l’état d’un fichier à un instant t par un arbre d’éclatement dont les nœuds correspondent aux paquets et dont les arcs matérialisent les éclatements successifs de paquets. La racine de cet arbre possède 2p fils représentant les 2p paquets initiaux.
Chaque nœud correspondant à un paquet éclaté est à son tour père de deux fils représentant les deux paquets issus de l’éclatement. Les feuilles de l’arbre correspondent donc aux paquets réellement occupés par le fichier à un instant t alors que les nœuds internes correspondent à des paquets ayant existé à des instants t-1, …, t-n. Chaque arc de l’arbre d’éclatement est valué par la signature du paquet qu’il référence.
On appelle signature d’un paquet, la valeur de la chaîne de bits partagée par les clés de tous les articles stockés dans ce paquet. Ainsi, les arcs partant de la racine sont valués par des signatures de p bits ayant comme valeur respective: 0…00, 0…01, jusqu’à 1…11. Par récurrence, les arcs correspondant au niveau n de l’arbre sont valués par des signatures de p+n-1 bits.
On considère un fichier haché possédant 8 paquets initiaux numérotés de 0 à 7. Le paquet numéro 6 a éclaté en deux paquets fils, le fils gauche a éclaté à son tour. Représenter l’arbre d’éclatement de ce fichier en précisant les valuations des arcs et les paquets occupés par le fichier.
Question 6
L’arbre d’éclatement doit être mémorisé (sous une forme quelconque) dans une structure de données système appelée catalogue. Le rôle du catalogue est de déterminer rapidement l’adresse du paquet dans lequel doit être inséré un nouvel article ainsi que l’adresse du paquet à lire lors d’une recherche sur clé.
Proposer une organisation du catalogue sous forme de table. Illustrer cette organisation du catalogue par rapport à l’arbre d’éclatement précédent.
En supposant que la fonction de hachage utilisée est le modulo, indiquer le principe de recherche dans le catalogue permettant de retrouver tous les articles du fichier dont la valeur de clé est 54, puis tous ceux dont la valeur de clé est 65.
Question 7
Lorsque le fichier est très grand, le catalogue peut ne plus tenir en mémoire. Proposer une adaptation de la structure précédente qui permette toujours de retrouver l’adresse d’un paquet (lors d’une insertion ou d’une recherche) en une E/S.
Indiquer le principe de mise à jour du catalogue lors des éclatements de paquets. Donner les différentes versions du catalogue, à la création du fichier puis après chacun des deux éclatements considérés dans la question 5. Combien d’entrées référencent le paquet 000 et quelle est leur signature respective ?
Comment retrouve-t-on maintenant les articles de clé 54 et ceux de clé 65 ?
Question 8
Un fichier organisé selon la méthode du hachage dynamique a-t-il une limite de taille ? Si oui, préciser laquelle, si non, préciser pourquoi.
Question 9
La méthode du hachage linéaire [Litwin80] est une méthode de hachage dynamique évitant la gestion d’un catalogue. Plutôt que d’éclater un paquet dès saturation comme dans le hachage extensible, les paquets sont éclatés dans un ordre prédéfini (d’où l’appellation linéaire). Le fichier est composé de N paquets initiaux, numérotés de 0 à N–1. Les articles sont placés dans les paquets initiaux par application de la fonction de hachage h0(clé) = clé modulo N. Lorsqu’un premier paquet déborde (par exemple: le paquet i), un paquet vide de numéro N est ajouté dynamiquement à la fin du fichier et le paquet 0 (et non le paquet i) est éclaté en deux par application de la fonction h1(clé) = clé modulo 2N.
Si la distribution est uniforme, la moitié des articles du paquet 0 seront déplacés dans le paquet N et les autres articles resteront dans le paquet 0. L’article qui a provoqué le débordement du paquet i est chaîné en débordement par une technique classique (ex: adressage ouvert). Lorsqu’un autre paquet j déborde, un nouveau paquet de numéro N+1 est ajouté en fin de fichier et le paquet 1 est éclaté avec la fonction h1. En procédant ainsi linéairement, les paquets i et j seront tôt ou tard éclatés à leur tour. La fonction h1 peut être utilisée jusqu’à ce que le fichier ait doublé de taille (tous les paquets de 0 à N-1 ont alors été éclatés).
A chaque doublement de la taille du fichier, les éclatements recommencent à partir du paquet 0 et la fonction de hachage hk-1 est remplacée par la fonction hk(clé) = clé modulo (2^k N), où k représente le nombre de fois où le fichier a doublé de taille (k est appelé niveau du fichier).
A un instant t, deux fonctions de hachage suffisent pour assurer la gestion du hachage linéaire. Quelle est la règle permettant de déterminer la fonction de hachage à utiliser lors de la recherche ou de l’insertion d’un article dans le fichier ? Quelles informations systèmes doivent être maintenues pour permettre la mise en oeuvre de cette règle ?
Question 10
Donner l’algorithme correspondant à la règle édictée à la question précédente
Question 5
L’arbre d’éclatement correspondant au fichier décrit est représenté sur la figure 5.2. Les paquets grisés correspondent aux paquets occupés par le fichier à l’instant t. On peut noter que la chaîne de bits de la signature est développée de droite à gauche. Ceci permet d’exploiter en priorité les bits de poids faibles (dont la distribution est généralement plus aléatoire) des clés de hachage.
Figure. Arbre d’éclatement valué par les signatures de paquets
Question 6
Le catalogue est matérialisé par une table assurant la correspondance entre signature et adresse de paquet. Cette table contient une entrée pour chaque paquet occupé par le fichier à un instant t, comme illustré figure 5.3.
Figure. Catalogue correspondant à l’arbre d’éclatement de la question 6
Pour effectuer la recherche de tous les articles ayant une clé donnée, il suffit de trouver dans le catalogue l’entrée dont la signature correspond à un préfixe de la chaîne de bits issue du hachage de la clé recherchée. Par exemple, la recherche des articles dont la clé est 54 s’effectue de la façon suivante. Cinq bits au plus étant actuellement exploités dans les signatures de paquet, on applique la fonction de hachage modulo 25 à la clé 54. Le résultat du hachage est donc 22 (54 mod 32).
En binaire, 22 s’écrit 10110. On recherche donc la signature 10110 dans le catalogue afin de trouver l’adresse du paquet correspondant. Il en va de même pour retrouver les articles de clé 65. 65 modulo 25 donne 1, soit en binaire sur 5 bits 00001. L’entrée 001 du catalogue sera sélectionnée car c’est la seule entrée correspondant à un préfixe de 00001.
Question 7
La structure proposée dans la question 7 impose une lecture séquentielle du catalogue. Pour pallier cet inconvénient, on modifie le principe de mise à jour du catalogue. Tant qu’il n’y a pas eu d’éclatement de paquet, le catalogue contient des signatures de p bits adressant les 2p paquets initiaux. Lors du premier éclatement d’un de ces paquets, la taille du catalogue est doublée et on développe un bit supplémentaire de chaque signature de sorte que toutes les entrées du catalogue contiennent des signatures de p+1 bits.
Les deux paquets issus de l’éclatement sont alors référencés chacun par une signature distincte de p+1 bits. Un nouvel éclatement de l’un de ces deux paquets entraînera à nouveau un doublement du catalogue. En revanche, les paquets n’ayant pas éclaté se trouvent référencés par deux signatures de p+1 bits dont les p premiers bits sont identiques. Si l’un de ces paquets éclate à son tour, le doublement du catalogue n’est pas utile puisque l’on dispose déjà de deux signatures de p+1 bits pour adresser les deux paquets issus de l’éclatement.
Dans ce cas, seule l’adresse de paquet associée aux deux signatures doit être mise à jour. La figure 5.4 montre l’évolution du catalogue après l’éclatement du paquet 110 puis du paquet 0110. Sur cette figure, ai représente l’adresse du paquet i.
L’avantage de ce principe est double. D’une part, les doublements du catalogue étant rares, l’éclatement d’un paquet nécessite le plus souvent une simple mise à jour des adresses associées aux signatures. D’autre part, toutes les signatures ont un nombre identique de bits développés. Ainsi, si le catalogue est grand et occupe plusieurs pages, il est possible de déterminer par calcul dans quelle page se trouve la (ou les) signature(s) recherchée(s). Une seule E/S est donc nécessaire pour effectuer la recherche dans le catalogue, quelle que soit sa taille.
Figure . Etapes de l’évolution du catalogue
Le paquet initial 000 est désormais référencé par quatre entrées contenant la même adresse physique mais dont les signatures respectives sont: 00000, 01000, 10000, 11000. On remarque que ces quatre signatures ont le même profil xx000.
La recherche des articles de clé 54 s’effectue comme dans la question 7, à savoir que l’on sélectionne l’entrée du catalogue de signature 10110. La recherche des articles de clé 65 revient à sélectionner l’entrée de signature 00001 qui, dans le cas présent, référence le même paquet que les entrées de signature : 01001, 10001 et 11001. En effet, le paquet initial 001 n’ayant pas éclaté, il est référencé par toutes les entrées dont le profil de signature est 001.
Remarque: l’entrée du catalogue contenant la signature 10110 est l’entrée 22 (10110 en binaire). Par conséquent, il n’est pas utile de stocker les signatures dans ce type de catalogue car cette information est redondante avec le numéro de chaque entrée.
Question 8
Lorsque la signature d’un paquet atteint le nombre de bits total de la chaîne de bits issue du hachage de la clé, ce paquet ne peut plus être éclaté puisque tous les bits des clés des articles qu’il contient ont été exploités. Le fichier est dans ce cas saturé. Il est cependant possible de chaîner un paquet de débordement à chaque paquet saturé afin de permettre leur extension. Dans ce cas, le fichier n’a plus de limite théorique de taille.
Question 9
Afin de déterminer le numéro du paquet dans lequel doit être recherché ou inséré un article, il faut connaître le niveau k du fichier et savoir si le paquet en question a déjà été éclaté ou non, ceci afin de déterminer si l’on doit utiliser la fonction de hachage hk ou hk+1. Pour cela, on mémorise dans le descripteur de fichier : le nombre de fois où le fichier a doublé de taille (niveau k du fichier) et la position du pointeur courant d’éclatement référençant le prochain paquet à éclater.
Par connaissance du niveau k du fichier, on applique la fonction de hachage hk à la clé de l’article à rechercher ou à insérer. Si le numéro de paquet déterminé par cette fonction de hachage est inférieur au pointeur courant d’éclatement, alors le paquet correspondant a déjà été éclaté et l’on re-hache la clé de l’article avec la fonction hk+1. Sinon, le paquet désigné par la fonction hk peut être directement exploité.
Question 10
L’algorithme déterminant la fonction de hachage à utiliser, lors de la recherche ou de l’insertion d’un article dans le fichier, prend en entrée le descripteur du fichier, la clé de l’article et rend en sortie le numéro de paquet dans lequel devrait être recherché ou inséré cet article. La fonction de hachage utilisée dans cet algorithme est h (k, clé) = clé modulo (2k N), où le paramètre k correspond au niveau du fichier.
fonction Calcul_n°paquet (descrip_fich: descripteur, clé:type_clé): entier;
var numpaquet, k: entier;
début
k := descrip_fich.k; // niveau du fichier
numpaquet := h (k, clé);
si (numpaquet < descrip_fich.ptéclat) alors Calcul_n°paquet := h (k+1, clé);
sinon Calcul_n°paquet := numpaquet;
fin
L’algorithme d’insertion d’un nouvel article dans un fichier organisé selon la méthode du hachage linéaire est présenté ci-dessous. La fonction Calcul_n°paquet utilisée dans cet algorithme est celle présentée question 10. La fonction Ecrire(article, numpaquet) écrit l’article « article » dans le paquet numpaquet ou le chaîne en débordement si ce paquet est saturé.
procédure Insérer(descrip_fich: descripteur, clé: type_clé, article: type_art)
var
numpaquet, nvnumpaquet: entier;
k: entier; // niveau du fichier
ptéclat: entier; // pointeur courant d’éclatement
début
k := descrip_fich.k;
ptéclat := descrip_fich.ptéclat; numpaquet := Calcul_n°paquet (descrip_fich, clé);
si (numpaquet est saturé) alors
// éclater le paquet de numéro ptéclat dans les
// paquets ptéclat et (ptéclat + 2k N)
pour chaque articlei Î ptéclat faire
nvnumpaquet := h (k+1, articlei.clé);
Ecrire (article, nvnumpaquet);
fpour
si (numpaquet = ptéclat) alors
// déterminer si le nouvel article doit être inséré
// dans le paquet ptéclat ou (ptéclat + 2k N)
numpaquet := h (k+1, article.clé);
fsi
// incrémenter le pointeur courant d’éclatement
si (ptéclat = (2k N) – 1)
alors // m-à-j du niveau du fichier
k := k + 1;
ptéclat := 0;
sinon ptéclat := ptéclat + 1;
// m-à-j du descripteur de fichier
descrip_fich.k := k;
descrip_fich.ptéclat := ptéclat;
fsi
fsi
// écrire l’article dans le paquet numpaquet
Ecrire (article, numpaquet);
Fin
Exercice Hachage multicritère
Dans le domaine des bases de données, les recherches d’articles se font généralement sur des critères multiples (exemple: rechercher les voitures de puissance supérieure à 10 cv et de marque Citroën). Les organisations de fichier étudiées dans les chapitres 2 et 3 privilégient le traitement du critère de recherche le plus fréquemment employé sur un fichier, en ordonnançant les articles sur disque en fonction de ce critère. Pour traiter efficacement des recherches multi-critères, il est possible d’adapter la majorité des organisations de fichiers afin de faire participer plusieurs attributs à la politique de placement.
Une seconde solution consiste à utiliser une structure de données annexe, appelée index secondaire. Un index secondaire constitue un ré-ordonnancement logique des articles d’un fichier en fonction d’une clé d’accès (discriminante ou non) différente de la clé plaçante sur laquelle est basée l’organisation du fichier. Lors d’une recherche sur clé d’accès, le balayage de l’index secondaire délivre les identifiants de tous les articles satisfaisant le critère de recherche.
Ces articles sont ensuite récupérés un à un via leurs identifiants, à raison d’une E/S par article. La création d’un index secondaire introduit un coût de stockage important. De plus, toute mise à jour du fichier de données entraîne la mise à jour de tous les index secondaires portant sur ce fichier. L’utilisation d’index secondaires doit donc être restreinte à des critères de recherche fréquents.
Question 1
Dans la méthode du hachage statique étudiée précédemment, un numéro de paquet est déterminé par la valeur d’une chaîne de bits issue du hachage de la valeur d’un seul attribut. Pour étendre cette méthode au hachage multi-attributs, la chaîne de bits est obtenue en concaténant respectivement b1, b2, … bn bits issus du hachage des attributs A1, A2, …, An par les fonctions de hachage h1, h2, …, hn.
a) Donner le principe de recherche de tous les articles du fichier satisfaisant la condition Ai = <valeur>.
b) Calculer le nombre d’E/S nécessaire (nombre de paquets accédés) pour effectuer la recherche précédente en supposant qu’il n’y a eu aucun débordement.
c) Une recherche avec la condition (Ai = <valeur1> et Aj= <valeur2>) génère-t-elle plus ou moins d’E/S que la recherche précédente ? Même question avec la condition (Ai = <valeur1> ou Aj= <valeur2>).
Question 2
De nombreuses méthodes de hachage dynamique multi-attributs ont été proposées, parmi lesquelles: grid-file [Nivergelt81], hachage linéaire multi-attributs [Ouksel83] et arbres de prédicats [Gardarin84]. De façon identique au hachage statique multi-attributs, la chaîne de bits servant à déterminer un numéro de paquet est composée des bits issus du hachage des attributs A1, A2, …, An par les fonctions de hachage h1, h2, …, hn.
Cependant, les méthodes de hachage dynamique multi-attributs diffèrent suivant l’ordre des bits issus de chaque fonction de hachage hi(Ai) dans cette chaîne de bits (par exemple, les bits associés à un attribut Ai ne sont pas obligatoirement contigus dans la chaîne). De même que dans le hachage dynamique mono-attribut, cette chaîne de bits est développée bit à bit au fur et à mesure des éclatements de paquets.
Donner le principe de recherche des articles satisfaisant la condition Ai = <valeur>.
Question 3
Supposons un fichier haché dynamiquement sur les attributs A1, A2 et A3. Dans quel ordre doivent être rangés les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans la chaîne de bits déterminant un numéro de paquet afin de privilégier les accès à l’attribut A2, puis à l’attribut A3 puis enfin à l’attribut A1 dans cet ordre de priorité ?
Question 4
La méthode du grid-file permet de traiter de façon équitable chacun des attributs de placement. Supposons un fichier haché sur les attributs A1, A2 et A3. Dans quel ordre doivent être rangés les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans la chaîne de bits déterminant un numéro de paquet afin d’assurer cette équité ?
Question 1
a) Les N paquets d’un fichier haché selon une méthode statique multi-attributs sont identifiés par des chaînes de p bits (où p=log_2 N) construites par concaténation de b1, b2, …, bn bits (où b1+b2+ …+bn = p) associés respectivement aux attributs A1, A2, …, An. La recherche de tous les articles du fichier satisfaisant la condition Ai = <valeur> nécessite la lecture de tous les paquets dont les numéros sont identifiés par une chaîne de p bits dans laquelle les valeurs des bi bits associés à Ai correspondent aux valeurs des bi bits issus du hachage de la valeur recherchée par la fonction hi. O
n sélectionne donc tous les paquets dont les numéros ont la forme présentée en figure 6.1. Ces paquets sont ensuite balayés séquentiellement pour récupérer tous les articles satisfaisant le critère de recherche.
Figure. Signature des paquets sélectionnés
b) S’il n’y a pas eu de débordement, le nombre d’E/S engendrées par une telle recherche correspond au nombre de paquets dont les numéros ont la forme citée précédemment. Puisque le fichier contient 2ppaquets (2p= nombre de combinaisons possibles de p bits), le nombre de paquets sélectionnés (nombre d’E/S) est égal à 2^(p-bi), c’est-à-dire au nombre de combinaisons possibles de p-bi bits puisque bi bits sont fixés par le critère de recherche.
c) En suivant le même raisonnement, le nombre d’E/S générées par une recherche avec la condition (Ai = <valeur1> et Aj= <valeur2>) est égal à 2^(p-bi-bj). Ce coût est donc inférieur au coût calculé en b). Le nombre d’E/S générées par une recherche avec la condition (Ai = <valeur1> ou Aj= <valeur2>) est quant à lui égal à 2^(p-bi) + 2^(p-bj).
Question 2
De façon identique au hachage statique multi-attributs, la recherche de tous les articles du fichier satisfaisant la condition Ai = <valeur> nécessite la lecture de tous les paquets dont les numéros sont identifiés par une chaîne de bits dans laquelle les valeurs des bi bits associés à Ai correspondent aux valeurs des bi bits issus du hachage de la valeur recherchée par la fonction hi. La différence est que les paquets sont ici créés dynamiquement et que les signatures de paquets sont développées au fur et à mesure des éclatements.
On commence donc par construire une chaîne de bits, appelée profil de signature, dans laquelle seules sont renseignées les valeurs des bi bits associés à Ai. Ce profil de signature est ensuite utilisé pour filtrer le catalogue afin de sélectionner toutes les signatures dont les valeurs des bi bits de Ai correspondent à celles du profil de signature, indépendamment des valeurs des autres bits de la signature. Si certains bits du profil de signature correspondent à des bits non encore développés dans une signature, on applique la comparaison uniquement sur les bits développés.
Le hachage de la valeur recherchée 12 par hi donne 3, soit 11 en binaire. Le filtrage du catalogue va donc s’effectuer avec le profil ??1?1 (où ? symbolise une valeur de bit inconnue). Ce filtrage va permettre de sélectionner les 2^(5-2) entrées du catalogue contenant les signatures 00101, 00111, 10101, 10111, 01101, 01111, 11101 et 11111. Le nombre d’E/S résultant est simplement 2 car l’ensemble de ces signatures référencent deux paquets initiaux 101 et 111 qui n’ont jamais éclaté.
Question 3
Dans une méthode de placement statique, l’ordonnancement des bits dans la signature d’un paquet n’a pas d’importance. En revanche, dans une méthode de placement dynamique, l’éclatement des paquets se fait en exploitant les bits de la signature l’un après l’autre. Seuls les bits exploités de la signature participent au placement, les autres bits restant non significatifs lors des recherches. Privilégier l’accès à un attribut revient donc à placer les bits qui lui sont associés en début de signature (c’est à dire à droite) de telle sorte qu’ils deviennent significatifs dès les premiers éclatements.
Soient les fonctions de hachage h1(A1), h2(A2), h3(A3) suivantes:
h1(A1) = i^1 i^2 i^3 … i^n où i^q correspond au qème bit de h1(A1)
h^2(A2) = j^1 j^2 j^3 … j^n où j^q correspond au qème bit de h2(A2)
h3(A3) = k^1 k^2 k^3 … k^n où k^q correspond au qème bit de h3(A3)
Privilégier les accès à l’attribut A2, puis à l’attribut A3 puis enfin à l’attribut A1 dans cet ordre de priorité revient à placer les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans l’ordre suivant: i^1 i^2 i^3 … in k^1 k^2 k^3 … k^n j^1 j^2 j^3 … j^n. Dans cet exemple, le placement sur l’attribut A1 ne deviendra effectif que lorsque le fichier aura atteint une grande taille, après un nombre important d’éclatements de paquet.
Question 4
Afin de traiter de façon équitable chacun des attributs de placement, la méthode du grid–file mélange les bits issus de chaque fonction de hachage dans la chaîne de bits afin d’exploiter un bit d’un attribut différent à chaque éclatement d’un paquet.
Dans l’exemple du fichier haché sur les attributs A1, A2 et A3, la méthode du grid–file va exploiter un bit de h1(A1) lors du premier éclatement d’un paquet, puis un bit de h2(A2) au deuxième éclatement de ce paquet, puis un bit de h3(A3) au troisième éclatement puis à nouveau un bit de h1(A1) au quatrième éclatement et ainsi de suite en tournant cycliquement sur chacun des attributs.
Cette équité est donc obtenue en plaçant les bits issus des fonctions de hachage h1(A1), h2(A2) et h3(A3) dans l’ordre suivant: k^1 j^1 i^1 k^2 j^2 i^2 … k^n j^n i^n, où i^q, j^q, k^q ont même signification que dans la question 5.
