Quelles sont les options pour stocker des données hiérarchiques dans une base de données relationnelle? [fermé]

Bons aperçus

De manière générale, vous décidez entre des temps de lecture rapides (par exemple, un ensemble imbriqué) ou des temps d'écriture rapides (liste d'adjacence). Habituellement, vous vous retrouvez avec une combinaison des options ci-dessous qui correspondent le mieux à vos besoins. Ce qui suit fournit une lecture approfondie:

• Encore une comparaison des intervalles imbriqués et de la liste d'adjacence : la meilleure comparaison que j'ai trouvée de la liste d'adjacence, du chemin matérialisé, de l'ensemble imbriqué et de l'intervalle imbriqué.
• Modèles de données hiérarchiques : diapositives avec de bonnes explications des compromis et des exemples d'utilisation
• Représenter les hiérarchies dans MySQL : très bon aperçu de l'ensemble imbriqué en particulier
• Données hiérarchiques dans les SGBDR : ensemble de liens le plus complet et le mieux organisé que j'ai vu, mais peu d'explications

Les options

Ceux que je connais et les caractéristiques générales:

1. Liste d'adjacence :
   • Colonnes: ID, ParentID
   • Facile à mettre en œuvre.
   • Déplacements, insertions et suppressions de nœuds bon marché.
   • Cher pour trouver le niveau, l'ascendance et les descendants, le chemin
   • Évitez N + 1 via les expressions de table communes dans les bases de données qui les prennent en charge
2. Ensemble imbriqué (aka Traversée d'arbre de précommande modifiée )
   • Colonnes: gauche, droite
   • Ascendance bon marché, descendants
   • O(n/2)Déplacements, insertions et suppressions très coûteux en raison d'un encodage volatil
3. Bridge Bridge (aka Closure Table / w triggers )
   • Utilise une table de jointure séparée avec: ancêtre, descendant, profondeur (facultatif)
   • Ascendance et descendants bon marché
   • Écrit les coûts O(log n)(taille de la sous-arborescence) pour l'insertion, les mises à jour et les suppressions
   • Encodage normalisé: bon pour les statistiques RDBMS et le planificateur de requêtes dans les jointures
   • Nécessite plusieurs lignes par nœud
4. Colonne de lignage (alias chemin matérialisé , énumération des chemins)
   • Colonne: lignée (par exemple / parent / enfant / petit-enfant / etc ...)
   • Descendants bon marché via une requête de préfixe (par exemple LEFT(lineage, #) = '/enumerated/path')
   • Écrit les coûts O(log n)(taille de la sous-arborescence) pour l'insertion, les mises à jour et les suppressions
   • Non relationnel: repose sur le type de données du tableau ou le format de chaîne sérialisé
5. Intervalles imbriqués
   • Comme un ensemble imbriqué, mais avec un réel / flottant / décimal pour que l'encodage ne soit pas volatile (déplacement / insertion / suppression peu coûteux)
   • A des problèmes de représentation / précision réelle / flottante / décimale
   • La variante d'encodage matriciel ajoute l'encodage ancêtre (chemin matérialisé) pour "gratuit", mais avec une astuce supplémentaire d'algèbre linéaire.
6. Table plate
   • Une liste d'adjacence modifiée qui ajoute une colonne de niveau et de rang (par exemple la commande) à chaque enregistrement.
   • Pas cher pour itérer / paginer sur
   • Déplacement et suppression coûteux
   • Bon usage: discussion filetée - forums / commentaires de blog
7. Plusieurs colonnes de lignée
   • Colonnes: une pour chaque niveau de lignée, fait référence à tous les parents jusqu'à la racine, les niveaux inférieurs au niveau de l'élément sont définis sur NULL
   • Ancêtres, descendants, niveau bon marché
   • Insertion bon marché, suppression, déplacement des feuilles
   • Insertion, suppression, déplacement coûteux des nœuds internes
   • Limite stricte de la profondeur de la hiérarchie

Notes spécifiques à la base de données

MySQL

• Utiliser des variables de session pour la liste d'adjacence

Oracle

• Utilisez CONNECT BY pour parcourir les listes d'adjacence

PostgreSQL

• Type de données ltree pour le chemin matérialisé

serveur SQL

• Résumé général
• 2008 propose que le type de données HierarchyId semble aider l'approche de la colonne de lignage et étendre la profondeur qui peut être représentée.

Ma réponse préférée est celle suggérée par la première phrase de ce fil. Utilisez une liste d'adjacence pour gérer la hiérarchie et utilisez des ensembles imbriqués pour interroger la hiérarchie.

Le problème jusqu'à présent a été que la méthode de conversion d'une liste d'adjacecy en ensembles imbriqués a été terriblement lente, car la plupart des gens utilisent la méthode RBAR extrême connue sous le nom de «push stack» pour effectuer la conversion et a été considérée comme étant trop coûteuse. pour atteindre le Nirvana de la simplicité de maintenance par la liste d'adjacence et les performances impressionnantes des ensembles imbriqués. En conséquence, la plupart des gens doivent se contenter de l'un ou de l'autre, surtout s'il y a plus de 100 000 nœuds, disons. L'utilisation de la méthode push stack peut prendre une journée entière pour effectuer la conversion sur ce que les MLM considéreraient comme une petite hiérarchie d'un million de nœuds.

Je pensais donner un peu de concurrence à Celko en proposant une méthode pour convertir une liste d'adjacence en ensembles imbriqués à des vitesses qui semblent tout simplement impossibles. Voici les performances de la méthode push stack sur mon ordinateur portable i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Et voici la durée de la nouvelle méthode (avec la méthode push stack entre parenthèses).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Oui c'est correct. 1 million de nœuds convertis en moins d'une minute et 100 000 nœuds en moins de 4 secondes.

Vous pouvez en savoir plus sur la nouvelle méthode et obtenir une copie du code à l'URL suivante. http://www.sqlservercentral.com/articles/Hierarchy/94040/

J'ai également développé une hiérarchie "pré-agrégée" en utilisant des méthodes similaires. Les MLM et les personnes faisant des nomenclatures seront particulièrement intéressés par cet article. http://www.sqlservercentral.com/articles/T-SQL/94570/

Si vous vous arrêtez pour jeter un œil à l'un ou l'autre des articles, accédez au lien "Rejoignez la discussion" et faites-moi savoir ce que vous en pensez.

C'est une réponse très partielle à votre question, mais j'espère toujours utile.

Microsoft SQL Server 2008 implémente deux fonctionnalités qui sont extrêmement utiles pour gérer les données hiérarchiques:

• le type de données HierarchyId .
• expressions de table courantes, en utilisant le mot clé with .

Jetez un œil à «Modélisez vos hiérarchies de données avec SQL Server 2008» de Kent Tegels sur MSDN pour commencer. Voir aussi ma propre question: requête récursive de même table dans SQL Server 2008

Cette conception n'était pas encore mentionnée:

Plusieurs colonnes de lignée

Bien qu'il ait des limites, si vous pouvez les supporter, c'est très simple et très efficace. Fonctionnalités:

• Colonnes: une pour chaque niveau de lignée, fait référence à tous les parents jusqu'à la racine, les niveaux inférieurs au niveau des éléments actuels sont définis sur 0 (ou NULL)
• Il y a une limite fixe à la profondeur de la hiérarchie
• Ancêtres, descendants, niveau bon marché
• Insertion bon marché, suppression, déplacement des feuilles
• Insertion, suppression, déplacement coûteux des nœuds internes

Voici un exemple - arbre taxonomique d'oiseaux de sorte que la hiérarchie est Classe / Ordre / Famille / Genre / Espèce - l'espèce est le niveau le plus bas, 1 ligne = 1 taxon (ce qui correspond à l'espèce dans le cas des nœuds foliaires):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

et l'exemple des données:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

C'est formidable car de cette façon, vous accomplissez toutes les opérations nécessaires de manière très simple, tant que les catégories internes ne changent pas leur niveau dans l'arborescence.

Modèle d'adjacence + modèle d'ensembles imbriqués

Je l'ai choisi car je pouvais facilement insérer de nouveaux éléments dans l'arbre (vous avez juste besoin d'un identifiant de branche pour y insérer un nouvel élément) et également l'interroger assez rapidement.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+

• Chaque fois que vous avez besoin de tous les enfants d'un parent, vous interrogez simplement le parent colonne.
• Si vous avez besoin tous les descendants de tous les parents vous interrogez des articles qui ont leur lftentre lftet rgtde parent.
• Si vous aviez besoin de tous les parents d'un nœud jusqu'à la racine de l'arborescence, vous recherchez des éléments dont la taille est lftinférieure à celle du nœud lftet rgtsupérieure à celle du nœud rgtet triez par parent.

Je devais rendre l'accès et l'interrogation de l'arbre plus rapide que les insertions, c'est pourquoi j'ai choisi ceci

Le seul problème est de corriger les colonnes leftet rightlors de l'insertion de nouveaux éléments. eh bien j'ai créé une procédure stockée pour ça et je l'ai appelé à chaque fois que j'insérais un nouvel élément qui était rare dans mon cas mais c'est vraiment rapide. J'ai eu l'idée du livre de Joe Celko, et la procédure stockée et comment je l'ai trouvée est expliquée ici dans DBA SE https://dba.stackexchange.com/q/89051/41481

Si votre base de données prend en charge les tableaux, vous pouvez également implémenter une colonne de lignage ou un chemin matérialisé en tant que tableau d'ID parents.

Plus précisément, avec Postgres, vous pouvez ensuite utiliser les opérateurs d'ensemble pour interroger la hiérarchie et obtenir d'excellentes performances avec les indices GIN. Cela rend la recherche de parents, d'enfants et de profondeur assez simple en une seule requête. Les mises à jour sont également assez gérables.

J'ai une description complète de l'utilisation des tableaux pour les chemins matérialisés si vous êtes curieux.

C'est vraiment une question de cheville carrée, de trou rond.

Si les bases de données relationnelles et SQL sont le seul marteau que vous avez ou êtes prêt à utiliser, les réponses qui ont été publiées jusqu'à présent sont adéquates. Mais pourquoi ne pas utiliser un outil conçu pour gérer des données hiérarchiques? La base de données graphique est idéale pour les données hiérarchiques complexes.

L'inefficacité du modèle relationnel ainsi que la complexité de toute solution de code / requête pour mapper un graphique / modèle hiérarchique sur un modèle relationnel ne valent tout simplement pas l'effort par rapport à la facilité avec laquelle une solution de base de données graphique peut résoudre le même problème.

Considérez une nomenclature comme une structure de données hiérarchique commune.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Chemin le plus court entre deux sous-ensembles : algorithme de traversée de graphe simple. Les chemins acceptables peuvent être qualifiés en fonction de critères.

Similarité : Quel est le degré de similitude entre deux assemblées? Effectuez une traversée sur les deux sous-arbres en calculant l'intersection et l'union des deux sous-arbres. Le pourcentage similaire est l'intersection divisée par l'union.

Fermeture transitive : parcourez le sous-arbre et résumez le (s) champ (s) d'intérêt, par exemple "Combien d'aluminium dans un sous-ensemble?"

Oui, vous pouvez résoudre le problème avec SQL et une base de données relationnelle. Cependant, il existe de bien meilleures approches si vous êtes prêt à utiliser le bon outil pour le travail.

J'utilise PostgreSQL avec des tables de fermeture pour mes hiérarchies. J'ai une procédure stockée universelle pour toute la base de données:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Ensuite, pour chaque table où j'ai une hiérarchie, je crée un déclencheur

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Pour remplir une table de fermeture à partir de la hiérarchie existante, j'utilise cette procédure stockée:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Les tables de fermeture sont définies avec 3 colonnes - ANCESTOR_ID, DESCENDANT_ID, DEPTH. Il est possible (et je conseille même) de stocker des enregistrements avec la même valeur pour ANCESTOR et DESCENDANT, et une valeur de zéro pour DEPTH. Cela simplifiera les requêtes de récupération de la hiérarchie. Et ils sont en effet très simples:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;