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


Bons aperçus

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

Options

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

  1. Liste d'adjacence:
    • Colonnes: ID, ParentID
    • Facile à mettre en œuvre
    • Le nœud bon marché se déplace, insère et supprime.
    • Cher de trouver le niveau, l'ascendance et les descendants, chemin
    • Évitez N + 1 via Expressions de table communes dans les bases de données qui les soutiennent
  2. Ensemble imbriqué (alias Traverse de l'arbre de précommande modifié)
    • Colonnes: Gauche, Droite
    • Ascendance bon marché, descendants
    • Très cher O(n/2) déplace, insère, supprime en raison de l'encodage volatile
  3. Table de pont (alias. Table de fermeture / w déclencheurs)
    • Utilise une table de jointure séparée avec: ancêtre, descendant, profondeur (facultatif)
    • Ascendance bon marché et descendants
    • Écrit les coûts O(log n) (taille de sous-arbre) pour insérer, mettre à jour, supprimer
    • Codage normalisé: bon pour les statistiques RDBMS et le planificateur de requête dans les jointures
    • Nécessite plusieurs lignes par noeud
  4. Colonne de lignage (alias. Chemin matérialisé, Énumération de chemin)
    • Colonne: lignée (par exemple / parent / enfant / petit-enfant / etc ...)
    • Descendants bon marché via une requête de préfixe (par ex. LEFT(lineage, #) = '/enumerated/path')
    • Écrit les coûts O(log n) (taille de sous-arbre) pour insérer, mettre à jour, supprimer
    • Non relationnel: repose sur un type de données Array ou un format de chaîne sérialisé
  5. Intervalles imbriqués
    • Comme ensemble imbriqué, mais avec real / float / decimal pour que l'encodage ne soit pas volatile (move / insert / delete peu coûteux)
    • A des problèmes de représentation / précision / réel / flottant / décimal
    • Variable de codage matriciel ajoute l'encodage ancêtre (chemin matérialisé) pour "libre", 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, une commande) à chaque enregistrement.
    • Bon marché pour itérer / paginer
    • Déplacement coûteux et supprimer
    • Bonne utilisation: discussion filetée - forums / commentaires de blog
  7. Colonnes à plusieurs lignées
    • Colonnes: une pour chaque niveau de lignage, se réfère à tous les parents jusqu'à la racine, les niveaux bas du niveau de l'élément sont définis sur NULL
    • Ancêtres bon marché, descendants, niveau
    • Insert bon marché, supprimer, déplacer des feuilles
    • Insertion coûteuse, suppression, déplacement des noeuds internes
    • Limitation stricte de la profondeur de la hiérarchie

Notes spécifiques aux bases de données

MySQL

Oracle

  • Utilisation CONNECTER PAR pour parcourir les listes d'adjacence

PostgreSQL

serveur SQL

  • Résumé général
  • Offres 2008 HierarchyId Le type de données apparaît pour aider à l'approche Lineage Column et étendre la profondeur qui peut être représentée.

1061
2017-10-29 00:34


origine


Réponses:


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

Jusqu'à présent, le problème était que la méthode de conversion d'une liste d'adjacence en ensembles imbriqués était terriblement lente, car la plupart des gens utilisent la méthode RBAR extrême connue sous le nom de «pile de poussée» pour faire la conversion. pour atteindre le Nirvana de la simplicité de la maintenance par la liste d'adjacence et la performance impressionnante des ensembles imbriqués. En conséquence, la plupart des gens finissent par devoir se contenter de l'un ou l'autre, surtout s'il y a plus de 100 000 noeuds par exemple. 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èrent comme une hiérarchie de petits millions 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 impossibles. Voici la performance 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 lire sur la nouvelle méthode et obtenir une copie du code à l'adresse 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 qui rédigeront 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 regarder l'un ou l'autre article, sautez dans le lien "Rejoindre la discussion" et faites-moi savoir ce que vous en pensez.


30



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

Microsoft SQL Server 2008 implémente deux fonctionnalités extrêmement utiles pour la gestion des données hiérarchiques:

  • la HierarchyId Type de données.
  • expressions de table communes, en utilisant le avec mot-clé.

Jettes un coup d'oeil à "Modéliser vos hiérarchies de données avec SQL Server 2008" par Kent Tegels sur MSDN pour les débuts. Voir aussi ma propre question: Requête récursive de même table dans SQL Server 2008


21



Ce design n'a pas encore été mentionné:

Colonnes à plusieurs lignées

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

  • Colonnes: une pour chaque niveau de lignage, se réfère à tous les parents jusqu'à la racine, les niveaux inférieurs au niveau des éléments actuels sont définis sur NULL
  • Limiter à quelle profondeur la hiérarchie peut être
  • Ancêtres bon marché, descendants, niveau
  • Insert bon marché, supprimer, déplacer des feuilles
  • Insertion coûteuse, suppression, déplacement des noeuds internes

Voici un exemple - arbre taxonomique des oiseaux de sorte que la hiérarchie est de classe / ordre / famille / genre / espèce - l'espèce est le niveau le plus bas, 1 ligne = 1 taxon (qui correspond à l'espèce dans le cas des nœuds feuilles):

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 génial parce que de cette façon, vous accomplissez toutes les opérations nécessaires d'une manière très simple, tant que les catégories internes ne changent pas leur niveau dans l'arbre.


20



Modèle d'adjacence + modèle de jeux imbriqués

Je suis allé pour cela parce que je pouvais facilement insérer de nouveaux éléments dans l'arbre (vous avez juste besoin de l'identifiant d'une branche pour y insérer un nouvel élément) et 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 n'avez qu'à interroger le parent colonne.
  • Si vous avez besoin de tous les descendants d'un parent, vous interrogez les éléments qui ont leur lft entre lft et rgt de parent.
  • Si vous aviez besoin de tous les parents d'un nœud jusqu'à la racine de l'arbre, vous interrogez les éléments ayant lft inférieur à celui du nœud lft et rgt plus grand que le noeud rgt et trier le par parent.

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

Le seul problème est de fixer le left et right colonnes lors de l'insertion de nouveaux éléments. J'ai créé une procédure stockée et je l'ai appelée à chaque fois que j'insérais un nouvel article, ce 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 suis arrivé avec elle est expliqué ici dans DBA SE https://dba.stackexchange.com/q/89051/41481


13



Si votre base de données prend en charge des tableaux, vous pouvez également implémenter une colonne de lignage ou un chemin matérialisé sous la forme d'un tableau d'identifiants parents.

Spécifiquement avec Postgres, vous pouvez ensuite utiliser les opérateurs set 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 triviale dans une seule requête. Les mises à jour sont également gérables.

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


10



Ceci est vraiment une question carrée, trou rond.

Si les bases de données relationnelles et SQL sont le seul outil que vous avez ou êtes prêt à utiliser, alors les réponses qui ont été postées jusqu'à présent sont adéquates. Cependant, pourquoi ne pas utiliser un outil conçu pour gérer les données hiérarchiques? Base de données graphique sont idéales pour les données hiérarchiques complexes.

Les inefficacités du modèle relationnel et la complexité de toute solution de code / requête pour mapper un modèle graphique / hiérarchique sur un modèle relationnel ne valent pas l'effort comparé à 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 {
};

Le plus court chemin entre deux sous-assemblages: Algorithme simple de traversée de graphe. Les chemins acceptables peuvent être qualifiés en fonction de critères.

Similarité: Quel est le degré de similitude entre deux assemblées? Effectuer 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, p. Ex. "Combien d'aluminium est 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 meilleures approches si vous êtes prêt à utiliser le bon outil pour le travail.


7



J'utilise PostgreSQL avec des tables de fermeture pour mes hiérarchies. J'ai une procédure stockée universelle pour l'ensemble de 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 trigger

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 d'une 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 pour la récupération de la hiérarchie. Et ils sont vraiment 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;

4