Imbrication d'ensembles

En informatique, l'imbrication d'ensembles, nested sets en anglais, est une technique pour représenter des données hiérarchisées dans une base de données relationnelle. En substance, elle consiste à attribuer à chaque nœud deux bornes, dite gauche et droite, qui permettent de statuer sur les liens de parentés entre les différents nœuds. L'implémentation la plus simple utilise des entiers naturels pour définir les bornes. Cette méthode présente entre autres inconvénients la nécessité de modifier une grande partie de l'arbre à chaque ajout d'un enregistrement. Une méthode beaucoup plus efficace utilise des nombres rationnels. Cette deuxième méthode est cependant peu connue, beaucoup plus difficile à appréhender, et comporte des développements assez poussés sur le plan mathématique. Elle comporte notamment des liens avec les fractions continues et un usage possible du calcul matriciel, qui sont autant de fonctionnalités souvent difficiles à implémenter directement en SQL.