Master 2, Bases de données avancées, année 2022

Cours 3. Les Bases de données orientées documents

Dans le cours précédant, nous avons vu les key-value store et comment la simplicité de ces derniers leur permet d’être distribué efficacement à moindre coût.

Une des limitations de ces systèmes est l’absence d’indexation du contenus. Ainsi, il est impossible de faire une recherche sur toutes les valeurs de la base de données ayant une certaine propriété.

Au vu de la simplicité du modèle de donnée, cette absence s’explique très bien: la plupart des mécanismes de recherches nécessite une forme d’introspections de la valeur et donc un système de typage et des types plus complexes que simplement des suites d’octets.

Redis est donc un cas intermédiaire, puisque les valeurs sont typées, mais pas indexées.

De nombreuse application offre des API sous forme de clef/valeur où les valeurs sont des documents JSON.

Par exemple, si on prend un Tweet

{
  "created_at": "Thu Apr 06 15:24:15 +0000 2017",
  "id_str": "850006245121695744",
  "text": "1\/ Today we\u2019re sharing our vision for the future of the Twitter API platform!\nhttps:\/\/t.co\/XweGngmxlP",
  "user": {
    "id": 2244994945,
    "name": "Twitter Dev",
    "screen_name": "TwitterDev",
    "location": "Internet",
    "url": "https:\/\/dev.twitter.com\/",
    "description": "Your official source for Twitter Platform news, updates & events. Need technical help? Visit https:\/\/twittercommunity.com\/ \u2328\ufe0f #TapIntoTwitter"
  },
  "place": {
  },
  "entities": {
    "hashtags": [
    ],
    "urls": [
      {
        "url": "https:\/\/t.co\/XweGngmxlP",
        "unwound": {
          "url": "https:\/\/cards.twitter.com\/cards\/18ce53wgo4h\/3xo1c",
          "title": "Building the Future of the Twitter API Platform"
        }
      }
    ],
    "user_mentions": [
    ]
  }
}

Le document contient pleins d’information ainsi des dictionnaires imbriqués (avec des listes) et une profondeur non négligeable.

Pour ce type de document, avec des méta-données, parfois profondes, on ne veut pas stocker tous le document comme un texte car il faut alors retravailler dans le middleware le document pour ne retourner que la valeur souhaitée. Ce travail supplémentaire compliqué l’architecture et diminue fortement les performances.

Les bases de données orientées documents sont donc construites pour permettre de stocker des documents (potentiellement profond), de les interroger et de les indexer. Leur paradigme étend ainsi celui des simples key-value store, principalement par la richesse des requêtes et des indexes que l’on peut exécuter sur les documents.

Documents et Vues sur des collections de documents

Dans une application Web, les documents structurées peuvent avoir deux usages:

Les bases de données classiques peuvent tout à fait retourner un document comme réponse d’une requête, ce qui simplifie grandement la communication avec le middleWare et avec le front-end.

On a vu que les bases de données orientées documents les utilisent également comme unité de donnée stockée. On a donc des collections de documents que l’on souhaite interroger.

Un exemple simple

Le gouvernement fourni un API simple pour interrogé des information géographique. Cette API stock des documents

La commande curl 'https://geo.api.gouv.fr/communes/59350' retourne le document

{
  "nom": "Lille",
  "code": "59350",
  "codeDepartement": "59",
  "codeRegion": "32",
  "codesPostaux": [
    "59800",
    "59000",
    "59260",
    "59777",
    "59160"
  ],
  "population": 232440
}

Ils proposent des mécanismes de recherche de communes selon différents paramètres:

Par exemple, la recherche par nom en triant par population:

curl 'https://geo.api.gouv.fr/communes?nom=Lille&boost=population&limit=2'

[
  {
    "nom": "Lille",
    "code": "59350",
    "codeDepartement": "59",
    "codeRegion": "32",
    "codesPostaux": [
      "59800",
      "59000",
      "59260",
      "59777",
      "59160"
    ],
    "population": 232440,
    "_score": 1.7772017384094794
  },
  {
    "nom": "Lillers",
    "code": "62516",
    "codeDepartement": "62",
    "codeRegion": "32",
    "codesPostaux": [
      "62190"
    ],
    "population": 10058,
    "_score": 0.5923008593838054
  }

Ou de faire une recherche multi-critère:

curl 'https://geo.api.gouv.fr/communes?nom=Lille&boost=population&limit=2'

[
  {
    "nom": "Lille",
    "code": "59350",
    "codeDepartement": "59",
    "codeRegion": "32",
    "codesPostaux": [
      "59800",
      "59000",
      "59260",
      "59777",
      "59160"
    ],
    "population": 232440,
    "_score": 1.7772017384094794
  },
  {
    "nom": "Lillers",
    "code": "62516",
    "codeDepartement": "62",
    "codeRegion": "32",
    "codesPostaux": [
      "62190"
    ],
    "population": 10058,
    "_score": 0.5923008593838054
  }
]

Ou faire une recherche par position géographique (ici le bâtiment M5):

curl 'https://geo.api.gouv.fr/communes?lat=50.63158972205492&lon=3.0752506776080466'

{
  "nom": "Villeneuve-d'Ascq",
  "code": "59009",
  "codeDepartement": "59",
  "codeRegion": "32",
  "codesPostaux": [
    "59650",
    "59491",
    "59493"
  ],
  "population": 62358
}

Une présentation de CouchDB

Les requêtes prennent la forme de vues sur les documents après une application d’une fonction sur chaque document de la collection.

Structure de données pour la recherche

Les tables de hachages sont très efficaces pour des mécanismes de clef-valeurs mais ne permettent pas des mécanismes de recherches plus riches.

Le mécanisme d’indexation principal est l’arbre équilibré et ses variantes. Il permet de répondre à des requêtes plus complexes.

Un peu de lecture.

Recherche dans un tableau ordonnées

On suppose qu’on a une collection d’éléments possiblement infinie \(E\), et un ordre total sur ces éléments, fourni par une fonction extérieur dont on suppose l’évaluation peu couteuse (en \(\mathcal{O}(1)\)).

Un tableau ordonnée permet de retrouver rapidement si un élément est-il présent dans le tableau (dichotomie, \(\mathcal{O}(\log n)\)) et si c’est le cas de retourner son indice ou l’indice de la plus petite valeur plus grande.

Grâce à cette information, et parce que le tableau est ordonné il est possible de récupérer l’information de tous les éléments plus grands qu’une valeur donnée.

En base de donnée, on s’intéresse à retrouver ce type d’information dans un contexte d’ajout et suppression de données. La problématique devient donc: Comment maintenir un tableau ordonné. Pour stocker un tableau, il existe essentiellement de type de mécanismes:

  1. Les listes chainées (et les variantes, doublement chainée, ect)
  2. Une allocation de mémoire contigüe

La première solution permet facilement d’ajouter et supprimer des données, par un jeu de modification de pointeurs simple mais ne permet pas un accès à n’importe quelle cellule en en temps constant. La seconde solution permet un accès à n’importe quelle cellule en temps constant, mais ne permet pas une insertion de donnée en temps constant.

Pour contourner ces problématiques, on présente usuellement les arbres binaires de recherches comme une solution on stock les données dans un arbres de recherches:

La recherche d’information dans un nœud binaire est au pire cas la profondeur de l’arbre. Des stratégies d’auto-équilibrage de l’arbre, pour que sa profondeur soit en \(O(\log n)\) permettent de garantir ainsi une complexité en insertion et en recherche de \(O(\log n)\).

Quelques exemples de stratégies d’équilibrages:

Localité de données

Lorsqu’on réalise un arbre binaire de recherche auto-équilibré, on ajoute de nouveaux éléments par des mécanismes de pointeurs au fur à mesure de leur arrivé. Cela signifie que l’ordre des éléments dans l’arbre et dans la mémoire ne sont pas reliés. On dit que alors que la structure de donnée ne respecte pas la localité des données.

En base de données, si la structure de données est écrite sur disque, la non localité est très problématique.

Les structures de données arborescente vont ainsi être désigné pour tirer partie au maximum de la localité des données et des accès aux disques dure physique sous forme de pages systèmes.

Les \(B\)-tree

Les B-tree sont un type d’arbre de recherche équilibré non binaire. Chaque nœud contient un tableau contigüe. La taille de ce tableau, plus les métas information nécessaires tiennent exactement dans une page système. Ainsi, pour un système classique, il est possible de stocker 64 valeurs de manière contigüe dans une seul page. Article wikipedia sur le sujet.

Les \(B^+\)-tree

Si on ajoute une information de frères sur les feuilles, afin d’accélérer les range query (trouver toutes les valeurs entre deux valeurs).

Les indexes inverses

Pour les bases de données orientées documents, il est primordiale de fournir des mécanismes d’indexation des valeurs. Pour ce faire, on utilise des moteurs d’indexations:

Le terme d’indexes inverse provient des key-value store: un index standard va permettre la recherche d’une clef rapidement, alors qu’un index inverse va permettre une recherche des clefs par des propriétés des valeurs. Il s’agit donc de trouver tout les documents qui ont certaines propriétés. L’application des indexes inverses est typiquement les moteurs de recherches: une grosse collections de documents et on souhaite retrouver les plus pertinents.

L’algorithmique sous-jacente aux indexes inverses est assez naturelle et est souvent utilisées ne serait ce que dans les livres.

The inverted index of the Alice Book

L’intuition est assez évidente: il suffit de stocker dans quel documents apparaissent chaque valeur (ou sous valeur) intéressantes. Ainsi pour indexer des pages web, on peut extraire la liste des mots qui y apparaissent et ajouter chacun de ces mots à l’indexe. De nombreux problème doivent néanmoins être régler pour ce genre d’usage, notamment quand l’indexation porte sur du texte en langue naturelle:

Et être capable de le faire dans toutes les langues possible concernée par l’indexation. Ce travail est très fastidieux et nécessitent beaucoup de temps et d’investissement … ou d’utiliser les bons outils. Les opérations de standardisation des mots dans une langue donnée peut être modéliser de biens des manières, par des grammaires algébriques ou des transducteurs qui modélisent ces règles.

Une fois que la liste des termes indexées est obtenue, il reste un problème algorithmique et une structure de données à construire:

Pour ça on doit donc être capable de réaliser efficacement des opérations booléennes sur les listes de documents. Un algorithmes naïf de l’intersections de deux listes est en \(O(n)\), ce qui serait inutilisable pour de la recherche sur de l’indexation de très nombre documents. Une stratégie raisonnable est de construire un B+-tree qui disposent naturellement d’un support pour l’intersection.


Mastodon