SQL: ¿Cómo almacenar y navegar por jerarquías?

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

Pregunta

¿Cuáles son las formas que utiliza para modelar y recuperar información jerárquica en una base de datos?

¿Fue útil?

Solución

Los artículos definitivos sobre este tema han sido escritos por Joe Celko, y ha incluido varios de ellos en un libro llamado Joe Celko's Trees and Hierarchies in SQL for Smarties.

Prefiere una técnica llamada gráficos dirigidos.Se puede encontrar una introducción a su trabajo sobre este tema. aquí

Otros consejos

Me gusta el algoritmo transversal del árbol de pedidos anticipados modificado.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 contribuyentes de Zend Framework (PHP) (publicada allí por Publicado por Laurent Melmoux el 5 de junio de 2007 a las 15:52).

Muchos de los enlaces son independientes del idioma:

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

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

Está bien explicado aquí:

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

modelo de lista de adyacencia

conjunto anidado

Graficos

Clases :

Conjuntos anidados Árbol de base de datos Adodb

Modelo de visitas ADOdb

PERA::DB_NestedSet

Arbol de pera

nstrees

¿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 su lugar, divida sus nodos y sus 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 implican volver a unir la tabla sobre sí misma, lo que sucedería si tiene la relación de jerarquí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 los 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 unir una tabla a sí misma mediante subconsultas; una limitación común son 16 subconsultas.

El problema es que mantener la tabla ancestral es algo difícil; es mejor hacerlo con un procedimiento almacenado.

No estoy de acuerdo con Josh.¿Qué sucede si utiliza una estructura jerárquica enorme, como la organización de una empresa?Las personas pueden unirse o salir de la empresa, cambiar líneas jerárquicas, etc.Mantener la "distancia" sería un gran problema y habría que mantener dos tablas de datos.

Esta consulta (SQL Server 2005 y superior) le permitirá ver la línea completa de cualquier persona Y calcula su lugar en la jerarquía y solo requiere una única 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;

Para su información:SQL Server 2008 presenta una nueva JerarquíaID tipo de datos para este tipo de situación.Le da control sobre en qué parte del "árbol" se ubica su fila, tanto horizontal como verticalmente.

Oráculo:SELECCIONAR ...EMPEZAR CON ...CONECTAR POR

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

Esta consulta recorrerá una tabla donde se almacena la relación de anidamiento. padre y niño columnas.

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

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

Prefiero una combinación 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, tienes un árbol simple con un solo padre por nodo (lo cual tiene sentido en este caso, pero no en otros casos como las cuentas contables)

Esta tabla de jerarquía se puede atravesar mediante procedimientos recursivos o si su base de datos lo admite mediante oraciones como SELECT...POR PREVIO (Oracle).

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

Tuvimos el mismo problema cuando implementamos un componente de árbol para [fleXivo] y utilizó el enfoque del modelo de árbol de conjuntos anidados mencionado por Tharkun del mysql documentos.

Además de acelerar las cosas (dramáticamente), utilizamos un extendido enfoque que simplemente significa que usamos el valor Long máximo para los límites derechos del nivel superior, lo que nos permite insertar y mover nodos sin volver a calcular todos los valores izquierdo y derecho.Los valores para izquierda y derecha se calculan dividiendo el rango de un nodo por 3 y usando el interno tercero como límites para el nuevo nodo.

Se puede ver un ejemplo de código java. aquí.

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

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top