Enoncé 32. Indexation pour l'accès multi-critères  Corrigé 32

Problème : Index secondaires dynamiques

Considérons la méthode d'accès suivante permettant d'adresser un fichier à travers un index primaire et éventuellement un ou plusieurs index secondaires :

Méthode d'accès :

Le fichier (F) de données est non ordonné et est un ensemble d'articles à format fixe. Un article possède 4 attributs( Cp, X, Y, Z) o� Cp désigne la clé primaire et les autres les clés secondaires.

Le fichier d'index primaire est un ensemble de triplets(Cp, Effacé, @) o� @ désigne l'adresse de l'article, Cp la clé primaire et Effacé un bit d'effacement. Une adresse est le couple (n�du bloc, position de l'article dans le bloc).

Dans le but de traiter des opérations multi-critères, on a la possibilité de créer dynamiquement en mémoire centrale (à la demande) des indexes secondaires à l'aide de l'opération Indexer("attribut") avec attribut dans {X, Y, Z }. Ces indexes n'ont d'existence que pendant l'exploitation du fichier. Ce sont donc des tables allouées dynamiquement o� chaque élément est le couple (Cs, Cp) avec Cs une clé secondaire et Cp une clé primaire. De plus, les clés secondaires peuvent être dupliquées à l'intérieur de ces tables.

Le fichier d'index primaire est chargé en mémoire centrale à l'ouverture du fichier. De plus, les caractéristiques suivantes sont récupérées :

Nbr_Articles : nombre d'articles du fichier de données

Nbr_Blocs : nombre de blocs du fichier de données

Ax, Ay, Az désignent les variables destinées à recevoir les adresses des indexes sur X, Y et Z respectivement. Elles sont donc initialisées à Nil.

Kx, Ky, Kz désignent les nombres de clés secondaires respectifs. Initialisées à 0.

Structures de données : Décrire le bloc du fichier de données et la table d'index secondaire.

Création automatique d'un index secondaire : Donner l'algorithme correspondant à l'opération "Indexer("attribut")" évoquée ci-dessus. Les clés secondaires sont insérées en ordre croissant au fur et à mesure de leur récupération(lecture)du fichier de données.

Requêtes sur le fichier : Ecrire le module rech("attribut", a, l) qui recherche dichotomiquement le plus petit indice l de la plus petite clé supérieure ou égale à une clé a donnée dans l'index secondaire "attribut".( ex : Pour l'index [5, 10, 13, 13, 18, 25, 25, 25, 30] et a=12 ou a=13 l'indice l est 3).

Donner les algorithmes(sans l'utilisation d'espace mémoire supplémentaire) qui répondent aux requêtes suivantes:

R1(Cs, "attribut") qui donne l'ensemble des articles ayant Cs comme clé secondaire sur "attribut".

R2(a, b, "attribut1", c, d, "attribut2") qui donne l'ensemble des articles ayant des clés secondaires dans l'intervalle [a, b] sur attribut1 et des clés secondaires dans l'intervalle[c,d] sur attribut2.

Interprétation & Calcul

1. Que représente graphiquement les résultats des requêtes R1 et R2 sur l'espace tridimensionnel (X, Y, Z).

2. Avec l'hypothèse que tous les indexes secondaires sont présents en mémoire centrale, quelle est la taille maximale des fichiers de données que l'on peut gérer sachant que l'on dispose d'une mémoire de 200K pour tous les indexes avec les caractéristiques suivantes : Clé(primaire ou secondaire) : 4 octets. Adresse d'un article : 4 octets. Taille maximale d'un index secondaire = 50K.

Indications :

Sur les indexes secondaires on utilisera :

. l'opération Allouer_index(T) qui réserve une table de 50K à l'adresse pointé par T pour l'index secondaire. De plus, si T est une variable qui contient l'adresse d'un index secondaire(table), T^(i) permet l'accès à l'élément i de cette table.

. Adr("attribut") : donne l'adresse de la table d'index secondaire( Ax, Ay ou Az) correspondante à "attribut".

. Long("attribut") : donne le nombre de clés secondaires ( Kx, Ky ou Kz) correspondant à "attribut".

Sur l'index primaire on utilisera :

. le module RD(Cp, i) de recherche dichotomique sur l'index primaire (sans l'écrire). Cp étant la clé à rechercher et i l'indice de Cp.

. le prédicat Effacé(i) égal à vrai si l'entrée i de la table d'index primaire est effacé, faux sinon.

. la fonction Num_bloc(i) qui donne le numéro du bloc de l'entrée i de la table d'index.

. la fonction Dépl(i) qui fournit la position de l'article de l'entrée i de la table d'index.

* * * * *