Quelles sont les options pour stocker des données hiérarchiques dans une firebase database relationnelle?

Bonnes vues d’ensemble

En règle générale, vous prenez une décision entre des temps de lecture rapides (par exemple, un ensemble nested) ou des temps d’écriture rapides (liste d’adjacence). Généralement, vous obtenez une combinaison des options ci-dessous qui correspondent le mieux à vos besoins. Ce qui suit fournit une lecture approfondie:

  • Une autre comparaison entre les intervalles nesteds et les listes d’adjacence : la meilleure comparaison entre la liste d’adjacence, le chemin matérialisé, le jeu nested et l’intervalle nested que j’ai trouvé.
  • Modèles pour les données hiérarchiques : diapositives avec de bonnes explications sur les compromis et les exemples d’utilisation
  • Représenter des hiérarchies dans MySQL : très bon aperçu de Nested Set 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 explicatif

Les options

Je connais des caractéristiques générales:

  1. Liste d’adjacence :
    • Colonnes: ID, ParentID
    • Facile à mettre en œuvre.
    • Un nœud bon marché se déplace, insère et supprime.
    • Cher pour trouver le niveau, l’ascendance et les descendants, chemin
    • Évitez N + 1 via les expressions de table communes dans les bases de données qui les prennent en charge
  2. Set nested (aka Traversal d’arbre de précommande modifié )
    • Colonnes: Gauche, Droite
    • Ascendance pas cher, descendants
    • Très coûteux O(n/2) se déplace, insère, supprime en raison de l’encodage volatile
  3. Table Bridge (aussi appelée table de fermeture / déclencheurs w )
    • 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 du sous-arbre) pour l’insertion, les mises à jour, les suppressions
    • Codage normalisé: bon pour les statistiques de SGBDR et le planificateur de requêtes dans les jointures
    • Nécessite plusieurs lignes par noeud
  4. Colonne de lignage (alias chemin matérialisé , énumération de chemin)
    • Colonne: lignage (par exemple / parent / enfant / petit-fils / etc …)
    • Descendants à bas prix via une requête de préfixe (par exemple LEFT(lineage, #) = '/enumerated/path' )
    • Écrit les coûts O(log n) (taille du sous-arbre) pour l’insertion, les mises à jour, les suppressions
    • Non relationnel: s’appuie sur le type de données Array ou le format de chaîne sérialisé
  5. Intervalles nesteds
    • Comme nested set, mais avec real / float / decimal 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éels / flottants / décimaux
    • La variante d’encodage masortingciel ajoute l’encodage des ancêtres (chemin matérialisé) à “libre”, mais avec une difficulté 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, un ordre) à chaque enregistrement.
    • Pas cher pour itérer / paginer sur
    • Déplacer cher et supprimer
    • Good Use: discussion en ligne – forums / commentaires de blog
  7. Colonnes de lignage multiples
    • Colonnes: une pour chaque niveau de lignage, 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 pas chers, descendants, niveau
    • Insérer, supprimer, déplacer les feuilles à bas prix
    • Insertion, suppression, déplacement coûteux des nœuds internes
    • Limite difficile à quelle profondeur la hiérarchie peut être

Notes spécifiques à la firebase database

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
  • Offres de 2008 Le type de données HierarchyId apparaît pour faciliter l’approche de Lineage Column et étendre la profondeur pouvant être représentée.

Ma réponse préférée est ce que la première phrase de ce fil a suggéré. Utilisez une liste de zones adjacentes pour gérer la hiérarchie et utilisez des ensembles nesteds pour interroger la hiérarchie.

Le problème jusqu’à présent était que la méthode de couverture d’une liste Adjacecy aux ensembles nesteds était terriblement lente, car la plupart des gens utilisent la méthode RBAR extrême appelée “Push Stack” pour effectuer la conversion. pour atteindre le Nirvana de la simplicité de la maintenance par la liste des adjacences et les performances impressionnantes des ensembles nesteds. En conséquence, la plupart des gens finissent par devoir se contenter de l’un ou de l’autre, surtout s’il y a plus de 100 000 noeuds environ. Utiliser la méthode de la stack push peut prendre une journée entière pour effectuer la conversion sur ce que les MLM considèrent comme une hiérarchie de plusieurs 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 nesteds à des vitesses qui semblent tout simplement impossibles. Voici la performance de la méthode de stack push 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” utilisant des méthodes similaires. Les MLM et les personnes qui rédigent 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 coup d’œil à l’un ou l’autre de ces articles, lancez-vous dans le lien «Rejoignez la discussion» et dites-moi ce que vous en pensez.

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

Colonnes de lignage multiples

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, fait référence à 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 pas chers, descendants, niveau
  • Insérer, supprimer, déplacer les feuilles à bas prix
  • Insertion, suppression, déplacement coûteux des nœuds internes

Voici un exemple – arbre taxonomique des oiseaux de sorte que la hiérarchie est Class / Order / Family / Genus / Species – l’espèce est le niveau le plus bas, 1 rang = 1 taxon (ce qui correspond aux espèces 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 génial car 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 de niveau dans l’arborescence.

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 extrêmement utiles pour la gestion des données hiérarchiques:

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

Jetez un coup d’oeil à “Modélisez vos hiérarchies de données avec SQL Server 2008” par Kent Tegels sur MSDN pour les démarrages. Voir aussi ma propre question: Requête récursive de même table dans SQL Server 2008

Modèle d’adjacence + modèle de jeux nesteds

Je suis allé là-bas parce que je pouvais insérer facilement de nouveaux éléments dans l’arborescence (vous avez juste besoin d’un identifiant de twig pour y insérer un nouvel élément) et pour 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 ne faites qu’interroger la colonne parent .
  • Si vous avez besoin de tous les descendants de tout parent, vous interrogez les éléments qui ont leur lft et rgt de parent.
  • Si vous aviez besoin de tous les parents d’un nœud jusqu’à la racine de l’arborescence, vous interrogez les éléments dont lft inférieur à lft et rgt du nœud plus grand que le rgt du nœud et sortingez-le par parent .

J’avais besoin de rendre l’access à l’arborescence plus rapide que les insertions, c’est pourquoi j’ai choisi cette option.

Le seul problème est de corriger les colonnes left et right lors de l’insertion de nouveaux éléments. Eh bien, j’ai créé une procédure stockée pour cela et l’ai appelée chaque fois que j’ai inséré un nouvel élément, 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 l’ai trouvée est expliquée ici dans DBA SE https://dba.stackexchange.com/q/89051/41481

Si votre firebase database prend en charge les tableaux, vous pouvez également implémenter une colonne de lignage ou un chemin matérialisé sous la forme d’un tableau d’identifiants parents.

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

Si vous êtes curieux, j’ai une description complète de l’utilisation de tableaux pour les chemins matérialisés .

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

Si les bases de données relationnelles et SQL sont les seuls éléments que vous avez ou êtes prêt à utiliser, les réponses qui ont été affichées sont adéquates. Cependant, pourquoi ne pas utiliser un outil conçu pour gérer les données hiérarchiques? La firebase database de graphes est idéale pour les données hiérarchiques complexes.

Les inefficacités du modèle relationnel et les complexités de toute solution de code / requête pour mapper un modèle graphique / hiérarchique sur un modèle relationnel ne valent pas la peine par rapport à la facilité avec laquelle une solution de firebase database de graphes 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-assemblages : 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 ou les champs d’intérêt, par exemple “Quelle quantité d’aluminium dans un sous-ensemble?”

Oui, vous pouvez résoudre le problème avec SQL et une firebase database relationnelle. Cependant, il existe de meilleures approches si vous souhaitez 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 firebase database:

 CREATE FUNCTION nomen_tree() RETURNS sortinggger 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 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 même conseillé) de stocker des enregistrements de 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 très simples en effet:

 -- 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;