Pour une gestion efficace des données, il est nécessaire de pouvoir identifier chaque enregistrement de façon unique.

L'indexation des données repose sur un principe simple d'étiquetage consistant à attribuer une étiquette différente à chaque enregistrement. Cette étiquette peut être une suite de caractères arbitraires, un entier, ou un descripteur explicite. On parle en général de clé ou d'identifiant pour désigner cette étiquette.

• L'indexation des données consiste à attribuer à chaque donnée distincte un identifiant unique.
• On parle également de clé de l'enregistrement:

On peut représenter l'opération d'indexation sous la forme d'une fonction. Si $d$ est le jeu de valeurs, $k(d)$ désigne l'identifiant de ce jeu de valeurs.

L'existence d'un identifiant unique pour chaque jeu de valeurs $d$ permet la mise en œuvre d'une recherche par identifiant (ou recherche par clé).

La recherche par identifiant repose sur une fonction d'adressage $I$ qui à tout identifiant $k$ associe sa position (entrée) $i$ dans un tableau de données: $I : k \rightarrow i$. Ainsi si $k$ est l'identifiant servant à la recherche, l'extraction des informations se fait en 2 étapes:

• $i = I(k)$ (lecture de l'index des données)
• $d = D[i]$ (lecture des données elles mêmes)

L'identifiant doit en pratique tenir sur un nombre d'octets le plus petit possible pour que la liste $L$ puisse être manipulée en mémoire centrale. Autrement dit, il faut que :

• $|k| << |d|$

pour que :

• $|L| << |D|$

Définir un ordre sur les données

La présence d'un identifiant permet de définir un ordre total sur les données :

• ordre sur les entiers (identifiant entier)
• ordre alphabétique (identifiant texte)
• ordre ASCIIbétique (chaîne de caractères quelconque)

Lier les données

Dans le cas des bases de données, l'identifiant constitue une référence vers les jeux de valeurs des tableaux de données. Une référence permet de lier les données d'une table aux données d'une autre table.

Exemple :

• Artistes
• Albums
• Pistes

• Pour chaque album de la table des albums, l'identifiant d'artiste (ici un numéro) permet de lier l'album avec l'artiste (ou groupe) correspondant.
• Pour chaque piste de la table des pistes, l'identifiant d'album permet de lier la piste à l'album correspondant (et donc à l'artiste correspondant par transitivité)

Structure d'ensemble

L'index définit l'appartenance d'une donnée à un ensemble.

Soit $\mathcal{E}$ un ensemble de données indexées : $$ \mathcal{E} = \{d_1, d_2, ..., d_K\} $$ On a l'équivalence : $$ d \in \mathcal{E} \Leftrightarrow k(d) \in I $$

Ainsi, il ne peut y avoir de doublon car $\forall d$ :

• $k(d)$ est unique
• $i = I(k(d))$ est unique ssi $d \in \mathcal{E}$ et indéfini sinon.

L'exemple le plus simple d'indexation est celui fourni par les numéros de case d'un tableau.

• Soit $D$ un tableau de $n$ lignes
• le numéro $i < n$ est à la fois l'identifiant et l'entrée (ou adresse) de la ligne $D[i]$

Dans le cas général, l'identifiant n'est pas égal à l'entrée!

On sépare donc l'index $k$ de l'entrée $i$:

• $k$ est l'identifiant (ou clé) de la donnée $d$. Il s'agit d'une valeur numérique quelconque.
• $i$ est l'entrée de la donnée $d$, correspondant à sa position dans le tableau de données.

Il existe différentes méthodes permettant d'assurer l'intégrité de l'index:

• Le programme maintient une liste triée des identifiants déjà utilisées. Lors de l'ajout d'une nouvelle donnée, il s'assure que l'identifiant n'est pas déjà présente dans la liste.
  • Coût :
    • $O(n)$ en mémoire
    • $O(\log n)$ pour l'ajout
• Dans le cas où les identifiants sont des numéros (entiers), il est possible d'utiliser un compteur qui s'incrémente à chaque nouvelle insertion.
  • Coût :
    • $O(1)$ en mémoire
    • $O(1)$ pour l'ajout

Utilisation d'une fonction de hachage :

• qui "calcule" la valeur de l'identifiant à partir des valeurs du jeu de valeurs à insérer.
• La fonction de hachage doit être telle que la probabilité de choisir le même identifiant pour deux données différentes soit extrêmement faible.

Attribution d'un identifiant arbitraire entre 0 et n-1

• Etape 1 : transcodage binaire des données
  • i = int.from_bytes(d, byteorder='big')
  • avantage : les données différentes ont un code entier différent
  • mais : |i| = |d|

s = 'paul.poitevin@centrale-marseille.fr'
d = bytes(s, 'ascii')
i = int.from_bytes(d, byteorder='big')
print("i =", i)

donne :

i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058

• Etape 2 : réduction du code
  • Méthode 1 : le modulo n (reste de la division entière par n)
    • k = H(i) = i mod n
    • Avantage :
      • $|k| << |d|$
    • Inconvénient:
      • deux données différentes peuvent avoir le même code
      • ce codage revient à sélectionner les bits de poids faible
      • deux données proches ou très similaires auront un index proche ou similaire : si j = i + 1, H(j) = H(i) + 1 (presque toujours)
      • —> il faut prendre n premier

• • • $n = 2^{32} = 4294967296$ :
      • H_code(paul.poitevin@centrale-marseille.fr) = 1697539698
      • H_code(martin.mollo@centrale-marseille.fr) = 1697539698
    • $n = 67280421310721$ (premier):
      • H_code(paul.poitevin@centrale-marseille.fr) = 36148249469507
      • H_code(martin.mollo@centrale-marseille.fr) = 65330032132071

• • Méthode 2 : combiner produit et modulo – soient m et n deux nombres premiers entre eux
    • k = H(i) = (i * m) mod n
    • Avantage :
      • $|k| << |d|$
      • deux entiers proches donneront auront des codes très différents : si j = i + 1, j * m - i * m = m
    • Inconvénient :
      • deux données différentes peuvent avoir le même code
        • le produit i * m peut etre coûteux à calculer

• Méthode 3 : Hachage cryptographique :
  • Le hachage cryptographique est construit de telle sorte qu'il soit très difficile de trouver un entier j != i tel que H(i) = H(j).
  • Un tel code est appelé une "signature".
    • Exemples :
      • MD4
      • SHA

Le gestionnaire de bases de données MongoDB utilise une indexation des données par clé cryptographique.

Que faire lorsque l'index ne tient pas en totalité dans la mémoire centrale ?

• L'index est découpé en "blocs"
• Les blocs sont organisés sous la forme d'un arbre (B-arbre = "Balanced Tree")

Considérons un index composé de couples (clé, numero de page). On suppose que l’index est également découpé en pages, chaque page d'index contenant au maximum b clés. Si l’index comporte beaucoup de pages, il est intéressant de l’organiser hiérarchiquement en pages et sous-pages, selon une organisation appelée "B-arbre" (Balanced Tree):

• chaque noeud de l’arbre contient une liste croissante de couples (clé, numéro d’une sous-page)
• chaque clé est dupliquée dans sa sous-page :
  • les clés contenues dans la sous-page sont inférieures ou égales à elle,
  • les clés contenues dans la sous-page sont strictement supérieures à celles de la sous-page précédente.
  • les feuilles contiennent des couples (clé, numéro de la page du tableau de données)

I ← charger la racine de l’arbre
tant que I n’est pas une feuille :
  k’ ← première clé de I
  tant que k > k’
    k’ ← clé suivante 
  I ← charger sous-page de k’

Remarque : Pour que l’accès aux données soit efficace,

• il faut que l’arbre soit le moins profond possible : arbre “équilibré”.
• Dans ce cas,
  • chaque noeud a b fils,
  • et la profondeur de l’arbre est de l’ordre de logb(N).
• Pour charger la page contenant le tuple cherché,
  • il faut donc logb(N) + 1 lectures sur disque.

En pratique, il existe des algos permettant d’assurer que chaque noeud contient entre b/2 et b clés (sauf la racine).

On introduit dans ce chapitre le modèle relationnel qui sert de fondation à la conception de bases de données.

Les différents modèles utiles en représentation des connaissances reposent sur des notions de base de la théorie des ensembles :

• Ensemble finis
• Éléments partiellement (ou totalement) discernables

• Soit $R(A_1, ..., A_m)$ un schéma.
• On note $\text{dom}(A_i)$ le domaine associé à l'attribut $A_i$.
• On dit d'un tuple $t$ qu'il obéit au schéma $R$ si les valeurs qu'il contient correspondent aux domaines des attributs du schéma.

• Une entité $x$
  • est une représentation d'un objet du monde réel,
  • appartenant au système/à l'organisation modélisée.
• Une entité est décrite par une ou plusieurs valeurs caractéristiques, appelées attributs.

• Un attribut peut être :
  • simple ou composé.
    • Exemple : une adresse peut être décrite par une simple chaîne de caractères, ou peut être décomposée en rue , no, boîte, ville, code postal, pays.
  • obligatoire ou facultatif ($D_j$ peut ou non contenir la valeur ø ).
  • atomique ou non (Un attribut peut posséder 0, 1 voire plusieurs valeurs…)

Un ensemble d'entités est un ensemble fini d'éléments : $$E = \{x_1,…,x_n\}$$ Il regroupe (ou associe) plusieurs entités ayant des caractéristiques communes (descriptibles à l'aide du même ensemble d'attributs).

• Les éléments d’un ensemble d’entités sont partiellement discernables à travers les valeurs de leurs attributs :
  • les attributs $(A_1,...,A_m)$ servent à décrire les éléments de l’ensemble.
  • Le schéma $R$ de l’ensemble $E$ est une application de l'ensemble d'entités vers l'ensemble des tuples de schéma $R$
    • Soit :

$$ R : \mathcal{X} \rightarrow D_1 \times ... \times D_m$$ $$ x_i \mapsto (A_1(x_i),…, A_m(x_i))$$

La Relation est la représentation logique d'un tableau de données.

• Au sein d'un schéma $R$,
  • Il peut exister un ensemble de contraintes, noté $F$,
    • portant sur les attributs (plus précisément sur les valeurs prises par les attributs).
    • L'ensemble F est indépendant de R.
  • On parle de contraintes d’intégrité.
    • Ces contraintes s’expriment sous la forme de dépendances fonctionnelles.

• Il importe donc de bien réfléchir, au moment de l'étape de conception,
  • du réalisme et du caractère limitant de certaines dépendances fonctionnelles,
  • et du caractère éventuellement limitant du choix des attributs.
• Ainsi, le schéma décrivant les commandes (exemple 2)
  • ne permet pas de commander des articles de nature différente au sein d'une même commande
  • (un client, pour commander deux râteaux et une truelle, doit donc effectuer deux commandes, qui plus est à des dates différentes!).

• Soit un schéma $R(A_1, ..., A_m)$.

Soit $K$ une clé candidate. On démontre que $K \rightarrow R$ à l'aide des axiomes d'Amstrong à partir d'un ensemble de DF connues:

Tables mal construites

Les Formes normales

• Restreignent les dépendances admises dans un schéma relationnel
• Permettent d’éviter la duplication de l’information au sein des relations
• Définissent une méthode
  • de décomposition d’un schéma relationnel redondant
  • en plusieurs schémas liés entre eux:

• Lorsqu’un schéma relationnel n’est pas en deuxième forme normale, il doit être normalisé:

* Lorsqu’un schéma relationnel n’est pas en troisième forme normale, il doit être normalisé: