tipos tablas permisos jerarquicas datos arboles sql sql-server oracle database-design hierarchy

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



tablas jerarquicas (9)

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

¿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.

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.

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

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í:

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

modelo de lista de adyacencia

conjunto anidado

Graphes

Clases:

Conjuntos anidados Adodb de árbol de base de datos

Visitación Modelo ADOdb

PEAR :: DB_NestedSet

Arbol de pera

nstrees

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.

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.

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;

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 .

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