SQL - Comment stocker et la navigation des hiérarchies?

StackOverflow https://stackoverflow.com/questions/38801

Question

Quels sont les moyens que vous utilisez pour modèle et récupérer hiérarchique des informations dans une base de données?

Était-ce utile?

La solution

L'définitive morceaux sur ce sujet ont été écrit par Joe Celko, et il a travaillé un certain nombre d'entre eux dans un livre qui s'appelle Joe Celko des Arbres et des Hiérarchies dans SQL pour les Smarties.

Il favorise une technique appelée les graphes orientés.Une introduction à son travail sur ce sujet peuvent être trouvées ici

Autres conseils

J'ai comme la modification de l'Aperçu de l'Arbre Transversal de l'Algorithme.Cette technique rend très facile la requête de l'arbre.

Mais voici une liste de liens sur le sujet que j'ai copié à partir du Framework Zend (PHP) contributeurs de la page web (posté par Posté par Laurent Melmoux à Juin 05, 2007 15:52).

La plupart des liens sont en langue agnostique:

Il y a 2 principales représentations et algorithmes pour représenter des structures hiérarchiques avec les bases de données :

  • ensemble imbriqué aussi connu comme modifié précommande l'arbre transversal de l'algorithme
  • la contiguïté de la liste modèle

C'est bien expliqué ici:

Voici quelques liens que j'ai recueillies:

la contiguïté de la liste modèle

ensemble imbriqué

Graphes

Catégories :

Imbriquée Ensembles DB Arbre Adodb

Visite Du Modèle ADOdb

PEAR::DB_NestedSet

PEAR::Arbre

nstrees

Quelle est la meilleure façon de représenter une hiérarchie dans une base de données SQL?Un générique, portable technique?

Supposons la hiérarchie est principalement en lecture, mais n'est pas complètement statique.Disons que c'est un arbre de la famille des.

Voici comment ne pas le faire:

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

Et d'insertion de données comme ceci: 

person_id   name      dob       mother father  
1           Pops      1900/1/1   null   null  
2           Grandma   1903/2/4   null   null  
3           Dad       1925/4/2   2      1  
4           Uncle Kev 1927/3/3   2      1
5           Cuz Dave  1953/7/8   null   4
6           Billy     1954/8/1   null   3

Au lieu de cela, diviser votre nœuds et vos relations dans les deux tables.

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date
);

create table ancestor (
ancestor_id   integer,
descendant_id integer,
distance      integer
);

De données est créée comme ceci:

person_id   name      dob       
1           Pops      1900/1/1  
2           Grandma   1903/2/4   
3           Dad       1925/4/2   
4           Uncle Kev 1927/3/3
5           Cuz Dave  1953/7/8   
6           Billy     1954/8/1   

ancestor_id  descendant_id  distance
1            1              0
2            2              0
3            3              0
4            4              0
5            5              0
6            6              0
1            3              1
2            3              1
1            4              1
2            4              1
1            5              2
2            5              2
4            5              1
1            6              2
2            6              2
3            6              1

vous pouvez maintenant exécuter arbitraire des requêtes qui n'impliquent pas de la jointure de la table en arrière sur lui-même, ce qui pourrait se produire si vous avez le heirachy relation dans la même ligne que le nœud.

Qui a les grands-parents?

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

Tous vos descendants:

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

Qui sont les oncles? 

select decendant_id uncle from ancestor 
    where distance=1 and ancestor_id in 
    (select ancestor_id from ancestor 
        where distance=2 and not exists
        (select ancestor_id from ancestor 
        where distance=1 and ancestor_id=uncle)
    )

Vous évitez tous les problèmes de rejoindre une table à elle-même via les sous-requêtes, une limitation commune est de 16 subsuqeries.

La difficulté réside dans le maintien de l'ancêtre de la table est une sorte de dur - mieux fait avec une procédure stockée.

Je dois être en désaccord avec Josh.Qu'advient-il si vous êtes à l'aide d'une énorme structure hiérarchique comme une organisation de l'entreprise.Les gens peuvent se joindre/quitter l'entreprise, de déclaration de changement de lignes, etc...Le maintien de la "distance" serait un gros problème et vous pouvez avoir à maintenir deux tables de données.

Cette requête (SQL Server 2005 et au-dessus) vous permettrait de voir la gamme complète de toute personne ET calcule leur place dans la hiérarchie et il ne nécessite qu'une seule table de données de l'utilisateur.Il peut être modifié pour trouver toutes les relations avec les enfants.

--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name      varchar(255) not null,
dob       date,
father    integer
);

INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);  
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);

DECLARE @OldestPerson INT; 
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family

WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
   SELECT
      personID
      ,Name
      ,dob
      ,father,
      1 as HierarchyLevel
   FROM #person
   WHERE personID = @OldestPerson

   UNION ALL

   SELECT
    e.personID,
      e.Name,
      e.dob,
      e.father,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM #person e
      INNER JOIN PersonHierarchy eh ON
         e.father = eh.personID
)

SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;

DROP TABLE #person;

FYI:SQL Server 2008 introduit une nouvelle HierarchyID type de données pour ce genre de situation.Vous donne le contrôle sur où dans l'arborescence de votre ligne se trouve, aussi bien horizontalement que verticalement.

Oracle:SÉLECTIONNEZ ...COMMENCER AVEC ...SE CONNECTER PAR

Oracle a une extension pour SÉLECTIONNER qui permet de faciliter l'arbre basé sur la récupération.Peut-être que SQL Server a une certaine extension similaire?

Cette requête va parcourir un tableau où la nidification relation est stocké dans parent et enfant les colonnes.

select * from my_table
    start with parent = :TOP
    connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

Je préfère un mélange de techinques utilisé par Josh et Mark Harrison:

Deux tables, l'une avec les données de la Personne et d'autres avec l'hierarchichal info (person_id, parent_id [, mother_id]) si le PK de ce tableau est person_id, vous avez un simple arbre avec un seul parent par nœud (ce qui est logique dans ce cas, mais pas dans d'autres cas, comme la comptabilité des comptes)

Cette hiarchy table peut être transversed par des procédures récursives ou si votre base de données prend en charge par des phrases comme SELECT...PRÉALABLE (Oracle).

Autre possibilité est de savoir si vous connaissez le max de profondeur de la hiérarchie des données que vous souhaitez mantain est d'utiliser une seule table avec un ensemble de colonnes par niveau de hiérarchie

Nous avons eu le même problème lorsque nous avons mis en place un arbre de composants pour [fleXive] et utilisé l'ensemble imbriqué modèle d'arbre approche évoquée par tharkun de l' MySQL docs.

En plus de la vitesse des choses (spectaculaire) jusqu'nous avons utilisé un diffusée l'approche qui veut dire simplement, nous avons utilisé le maximum de valeur pour le niveau supérieur droit de limites qui nous permet d'ajouter et de déplacer des nœuds sans avoir à recalculer toutes les valeurs gauche et droite.Les valeurs de gauche et de droite sont calculés par la division de la plage par un noeud en 3 und utiliser le intérieure troisième limites pour le nouveau nœud.

Un exemple de code java peut être vu ici.

Si vous utilisez SQL Server 2005, puis ce lien explique comment récupérer des données hiérarchiques.

Les Expressions de Table communes (expressions de table communes) peuvent être vos amis une fois que vous obtenez à l'aise de les utiliser.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top