tablas - sql hierarchy

¿Cómo representar un árbol de datos en SQL?

Question

Estoy escribiendo una estructura de árbol de datos que se combina desde un árbol y un TreeNode. Tree contendrá la raíz y las acciones de nivel superior en los datos. Estoy usando una biblioteca de IU para presentar el árbol en un formulario de Windows donde puedo vincular el árbol a TreeView.

Tendré que guardar este árbol y los nodos en la base de datos. Cuál será la mejor manera de guardar el árbol y obtener las siguientes características:

1. Implementación intuitiva.
2. Fácil de encuadernar Será fácil pasar del árbol a la estructura de la base de datos y viceversa (si corresponde)

Tenía 2 ideas El primero es serializar los datos en un único trazador de líneas en una tabla. El segundo es guardar en tablas, pero luego, al moverme a las entidades de datos, perderé los estados de las filas en la tabla en los nodos modificados.

¿Algunas ideas?

Answer 1

Algo así como "nodos" de tablas en los que cada fila de nodos contiene una ID principal (además de los datos de nodo ordinarios). Para root, el padre es NULL.

Por supuesto, esto hace que los niños consuman un poco más de tiempo, pero de esta manera la base de datos real será bastante simple.

Answer 2

Depende de cómo va a consultar y actualizar los datos. Si almacena todos los datos en una fila, es básicamente una sola unidad en la que no puede realizar consultas o actualizar parcialmente sin volver a escribir todos los datos.

Si desea almacenar cada elemento como una fila, primero debe leer Gestión de datos jerárquicos en MySQL (MySQL específico, pero el consejo también se aplica a muchas otras bases de datos).

Si solo está accediendo a un árbol completo, el modelo de lista de adyacencia hace que sea difícil recuperar todos los nodos bajo la raíz sin usar una consulta recursiva. Si agrega una columna adicional que enlaza con el encabezado, puede hacer SELECT * WHERE head_id = @id y obtener todo el árbol en una consulta no recursiva, pero desnormaliza la base de datos.

Algunas bases de datos tienen extensiones personalizadas que facilitan el almacenamiento y la recuperación de datos jerárquicos, por ejemplo, Oracle tiene CONNECT BY .

Answer 3

He marcado este slidshare sobre SQL-Antipatterns, que analiza varias alternativas: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

La recomendación de allí es utilizar una tabla de cierre (se explica en las diapositivas).

Aquí está el resumen (diapositiva 77):

                  | Query Child | Query Subtree | Modify Tree | Ref. Integrity
Adjacency List    |    Easy     |     Hard      |    Easy     |      Yes
Path Enumeration  |    Easy     |     Easy      |    Hard     |      No
Nested Sets       |    Hard     |     Easy      |    Hard     |      No
Closure Table     |    Easy     |     Easy      |    Easy     |      Yes

Answer 4

La implementación más fácil es la estructura de la lista de adyacencia :

id  parent_id  data

Sin embargo, algunas bases de datos, particularmente MySQL , tienen algunos problemas al manejar este modelo, ya que requiere la capacidad de ejecutar consultas recursivas que carece de MySQL .

Otro modelo es conjuntos anidados :

id lft rgt data

donde lft y rgt son valores arbitrarios que definen la jerarquía (cualquier lft un niño, rgt debe estar dentro de lft , rgt cualquier padre)

Esto no requiere consultas recursivas, pero es más lento y más difícil de mantener.

Sin embargo, en MySQL esto se puede mejorar usando ablaciones de SPATIAL.

Vea estos artículos en mi blog:

• Lista de adyacencia frente a conjuntos anidados: PostgreSQL
• Lista de adyacencia frente a conjuntos anidados: SQL Server
• Lista de adyacencia vs. conjuntos anidados: Oracle
• Lista de adyacencia frente a conjuntos anidados: MySQL

para explicaciones más detalladas.

Answer 5

La mejor manera, creo que es dar a cada nodo un id y un parent_id, donde el id principal es el id del nodo padre. Esto tiene un par de beneficios

1. Cuando desee actualizar un nodo, solo tendrá que volver a escribir los datos de ese nodo.
2. Cuando desee consultar solo un nodo determinado, puede obtener exactamente la información que desea, por lo tanto, tendrá menos sobrecarga en la conexión de la base de datos.
3. Muchos lenguajes de programación tienen la funcionalidad de transformar los datos de mysql en XML o json, lo que facilitará la apertura de la aplicación mediante una API.

Answer 6

Me sorprende que nadie haya mencionado la solución de ruta materializada , que es probablemente la forma más rápida de trabajar con árboles en SQL estándar.

En este enfoque, cada nodo en el árbol tiene una ruta de columna, donde se almacena la ruta completa desde la raíz hasta el nodo. Esto implica consultas muy simples y rápidas.

Eche un vistazo al nodo de tabla de ejemplo:

+---------+-------+
| node_id | path  |
+---------+-------+
| 0       |       |
| 1       | 1     |
| 2       | 2     |
| 3       | 3     |
| 4       | 1.4   |
| 5       | 2.5   |
| 6       | 2.6   |
| 7       | 2.6.7 |
| 8       | 2.6.8 |
| 9       | 2.6.9 |
+---------+-------+

Para obtener los elementos secundarios del nodo x , puede escribir la siguiente consulta:

SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), ''.%'')

Tenga en cuenta que la ruta de la columna debe estar indexada para poder realizarla rápidamente con la cláusula LIKE .

Answer 7

Si está utilizando PostgreSQL, puede usar ltree , un paquete en la extensión contrib (viene por defecto) que implementa la estructura de datos del árbol.

De los docs :

CREATE TABLE test (path ltree);
INSERT INTO test VALUES (''Top'');
INSERT INTO test VALUES (''Top.Science'');
INSERT INTO test VALUES (''Top.Science.Astronomy'');
INSERT INTO test VALUES (''Top.Science.Astronomy.Astrophysics'');
INSERT INTO test VALUES (''Top.Science.Astronomy.Cosmology'');
INSERT INTO test VALUES (''Top.Hobbies'');
INSERT INTO test VALUES (''Top.Hobbies.Amateurs_Astronomy'');
INSERT INTO test VALUES (''Top.Collections'');
INSERT INTO test VALUES (''Top.Collections.Pictures'');
INSERT INTO test VALUES (''Top.Collections.Pictures.Astronomy'');
INSERT INTO test VALUES (''Top.Collections.Pictures.Astronomy.Stars'');
INSERT INTO test VALUES (''Top.Collections.Pictures.Astronomy.Galaxies'');
INSERT INTO test VALUES (''Top.Collections.Pictures.Astronomy.Astronauts'');
CREATE INDEX path_gist_idx ON test USING GIST (path);
CREATE INDEX path_idx ON test USING BTREE (path);

Puede hacer consultas como:

ltreetest=> SELECT path FROM test WHERE path <@ ''Top.Science'';
                path
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(4 rows)