tablas - SQL-¿Cómo almacenar y navegar jerarquías?

tablas jerarquicas

Question

¿De qué maneras se usa para modelar y recuperar información jerárquica en una base de datos?

Answer 1

¿Cuál es la mejor manera de representar una jerarquía en una base de datos SQL? ¿Una técnica genérica y portátil?

Supongamos que la jerarquía se lee principalmente, pero no es completamente estática. Digamos que es un árbol genealógico.

He aquí cómo no hacerlo:

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

E insertando datos como este:

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

En cambio, divide tus nodos y tus relaciones en dos tablas.

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

Los datos se crean así:

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

Ahora puede ejecutar consultas arbitrarias que no impliquen volver a unirse a la tabla, lo que sucedería si tiene la relación de heiraquía en la misma fila que el nodo.

¿Quién tiene abuelos?

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

Todos tus descendientes:

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

¿Quiénes son tíos?

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

Evita todos los problemas de unirse a una tabla a sí mismo a través de subconsultas, una limitación común es 16 subsuqeries.

El problema es que mantener la tabla ancestra es un poco difícil, mejor hecho con un procedimiento almacenado.

Answer 2

FYI: SQL Server 2008 introduce un nuevo tipo de datos HierarchyID para este tipo de situación. Le da control sobre el lugar donde se encuentra el "árbol" en el que se encuentra su hilera, tanto horizontal como verticalmente.

Answer 3

Las piezas definitivas sobre este tema han sido escritas por Joe Celko, y él ha trabajado varias de ellas en un libro llamado Árboles y jerarquías de Joe Celko en SQL for Smarties.

Él favorece una técnica llamada gráficos dirigidos. Una introducción a su trabajo sobre este tema se puede encontrar here

Answer 4

Me gusta el Algoritmo de Travesía de Árboles Preordenados Modificados. Esta técnica hace que sea muy fácil consultar el árbol.

Pero aquí hay una lista de enlaces sobre el tema que copié de la página web de colaboradores de Zend Framework (PHP) publicada por Laurent Melmoux el 5 de junio de 2007 15:52.

Muchos de los enlaces son independientes del idioma:

Hay 2 representaciones principales y algoritmos para representar estructuras jerárquicas con bases de datos:

• conjunto anidado también conocido como algoritmo de recorrido de árbol de preorden modificado
• modelo de lista de adyacencia

Está bien explicado aquí:

• http://www.sitepoint.com/article/hierarchical-data-database
• Gestionar datos jerárquicos en MySQL
• http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

Aquí hay algunos más enlaces que he recopilado:

• http://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

modelo de lista de adyacencia

• http://www.sqlteam.com/item.asp?ItemID=8866

conjunto anidado

• http://www.sqlsummit.com/AdjacencyList.htm
• http://www.edutech.ch/contribution/nstrees/index.php
• http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
• http://www.dbmsmag.com/9604d06.html
• http://en.wikipedia.org/wiki/Tree_traversal
• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html (applet java montrant le fonctionnement)

Graphes

• http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Clases:

Conjuntos anidados Adodb de árbol de base de datos

• http://www.phpclasses.org/browse/package/2547.html

Visitación Modelo ADOdb

• http://www.phpclasses.org/browse/package/2919.html

PEAR :: DB_NestedSet

• http://pear.php.net/package/DB_NestedSet
• utilización: https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html

Arbol de pera

• http://pear.php.net/package/Tree/download/0.3.0/
• http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html

nstrees

• http://www.edutech.ch/contribution/nstrees/index.php

Answer 5

Prefiero una mezcla de las técnicas utilizadas por Josh y Mark Harrison:

Dos tablas, una con los datos de la Persona y otra con la información jerárquica (person_id, parent_id [, mother_id]) si la PK de esta tabla es person_id, tiene un árbol simple con solo uno padre por nodo (lo cual tiene sentido en este caso, pero no en otros casos como cuentas contables)

Esta tabla hiarchy puede ser atravesada por procedimientos recursivos o si su DB lo soporta con oraciones como SELECT ... BY PRIOR (Oracle).

Otra posibilidad es que si conoce la profundidad máxima de la jerarquía, los datos que desea mantener son utilizar una sola tabla con un conjunto de columnas por nivel de jerarquía.

Answer 6

Si está utilizando SQL Server 2005, este enlace explica cómo recuperar datos jerárquicos.

Las expresiones de tabla comunes (CTE) pueden ser tus amigos una vez que te sientas cómodo usándolos.

Answer 7

Tengo que estar en desacuerdo con Josh. ¿Qué sucede si está utilizando una estructura jerárquica enorme como una organización de empresa? Las personas pueden unirse / abandonar la empresa, cambiar las líneas de denuncia, etc. Mantener la "distancia" sería un gran problema y tendrías que mantener dos tablas de datos.

Esta consulta (SQL Server 2005 y superior) le permite ver la línea completa de cualquier persona Y calcula su lugar en la jerarquía y solo requiere una sola tabla de información del usuario. Se puede modificar para encontrar cualquier relación infantil.

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

Answer 8

Tuvimos el mismo problema cuando implementamos un componente de árbol para [fleXive] y utilizamos el enfoque de modelo de árbol conjunto anidado mencionado por tharkun en los documentos de MySQL .

Además de acelerar las cosas (drásticamente), utilizamos un método de propagación que simplemente significa que usamos el valor Máximo largo para los límites de la derecha del nivel superior que nos permite insertar y mover nodos sin volver a calcular todos los valores de la izquierda y la derecha. Los valores para la izquierda y la derecha se calculan dividiendo el rango para un nodo entre 3 y usan el tercero interno como límites para el nuevo nodo.

Un ejemplo de código Java se puede ver here .

Answer 9

Oracle: SELECT ... START WITH ... CONNECT BY

Oracle tiene una extensión para SELECT que permite una recuperación fácil basada en árboles. Quizás SQL Server tiene alguna extensión similar?

Esta consulta atravesará una tabla donde la relación de anidamiento se almacena en columnas primarias y secundarias .

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

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