Quelles sont les options pour le stockage de données hiérarchiques dans une base de données relationnelle?

Mon préféré réponse est que ce que la première phrase de ce fil suggéré. Utiliser une Liste d'Adjacence pour maintenir la hiérarchie et de l'utilisation Imbriquée Définit à la requête de la hiérarchie.

Le problème jusqu'à maintenant a été que la coversion méthode à partir d'un Adjacecy Liste Imbriquée Ensembles a été horriblement lent, car la plupart des gens utilisent l'extrême RBAR méthode connue sous le nom de "Pousser la Pile des" à faire la conversion et a été considéré comme un moyen de coûteux d'atteindre le Nirvana de la simplicité de maintenance de la Liste d'Adjacence et la performance impressionnante de Imbriquée Ensembles. En conséquence, la plupart des gens finissent par avoir à trancher pour l'un ou l'autre, surtout si il ya plus de, disons, un moche de 100 000 nœuds ou plus. L'utilisation de la commande de la pile méthode peut prendre une journée entière pour faire la conversion sur ce MLM ils considèrent comme un petit million de nœud de hiérarchie.

J'ai pensé donner Celko un peu de la concurrence et à venir avec une méthode pour convertir une Liste d'Adjacence Imbriquées jeux à des vitesses qui semblent tout simplement impossible. Voici la performance de la pile push méthode sur mon i5 ordinateur portable.

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 poussée de la pile de la méthode dans la parenthèse).

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 au sujet de la nouvelle méthode et d'obtenir une copie du code à l'adresse suivante.
http://www.sqlservercentral.com/articles/Hierarchy/94040/

J'ai également développé un "pré-agrégées" hiérarchie à l'aide de méthodes similaires. MLM croyants et les gens qui font des listes de matériaux seront particulièrement intéressés par le présent article.
http://www.sqlservercentral.com/articles/T-SQL/94570/

Si vous ne s'arrêter pour jeter un oeil à l'article, sauter dans le "Join the discussion" et laissez-moi savoir ce que vous en pensez.

Cette conception n'était pas encore mentionné:

Plusieurs colonnes de lignage

Si elle a des limites, si vous pouvez supporter, c'est très simple et très efficace. Caractéristiques:

• Colonnes: une pour chaque lignée niveau, se réfère à tous les parents jusqu'à la racine, les niveaux ci-dessous les éléments en cours de niveau sont mis à 0 (ou NULL)
• Il y a une limite fixe à la profondeur de la hiérarchie peut être
• Pas cher ascendants, descendants, niveau
• Bon marché insérer, supprimer, déplacer des feuilles
• Cher, insérer, supprimer, déplacer des nœuds internes

Voici un exemple - arbre taxonomique des oiseaux de la hiérarchie est donc de Classe/Ordre/Famille/Genre/Espèce espèce est le niveau le plus bas, 1 ligne = 1 taxon (ce qui correspond à des espèces dans le cas de 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 de l'exemple de 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                   |

Ce qui est excellent, car de cette façon vous accomplir toutes les opérations d'une manière très facile, aussi longtemps que les catégories ne change pas de niveau dans l'arborescence.

Si votre base de données prend en charge les tableaux, vous pouvez également mettre en place une lignée de colonne ou de chemin matérialisé comme un tableau de parent id.

Spécifiquement avec Postgres vous pouvez ensuite utiliser l'ensemble des opérateurs de requête de la hiérarchie, et d'obtenir d'excellentes performances avec GIN indices. Cela rend la recherche de parents, d'enfants, et de la profondeur assez trivial dans une seule requête. Les mises à jour sont assez gérable ainsi.

J'ai une écriture complète de l'aide des tableaux pour matérialisée chemins si vous êtes curieux.

Je suis en utilisant PostgreSQL avec la fermeture des tables pour mon hiérarchies.
J'ai un universel de la procédure stockée 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, j'ai créer 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 le remplissage d'une fermeture de la table de hiérarchie existante-je utiliser 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;
$$;

Fermeture tables sont définies avec 3 colonnes - ANCESTOR_ID, DESCENDANT_ID, de la PROFONDEUR. Il est possible (et j'ai même des conseils) pour stocker des enregistrements avec la même valeur pour ANCÊTRE et DESCENDANT, et une valeur de zéro pour la PROFONDEUR. Ceci permettra de simplifier les requêtes pour la récupération de la hiérarchie. Et ils sont en réalité très simple:

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