Etiquetado jerárquico en SQL

Question

Tengo una aplicación web PHP que utiliza una base de datos MySQL para etiquetar objetos, en la que he usado la estructura de etiquetas aceptada como respuesta a esta pregunta SO .

Me gustaría implementar una jerarquía de etiquetas, donde cada etiqueta puede tener una etiqueta principal única. Las búsquedas de una etiqueta padre T coincidirían con todos los descendientes de T (es decir, T, las etiquetas cuyo padre es T (hijos de T), nietos de T, etc.).

La forma más fácil de hacer esto parece ser agregar un campo ParentID a la tabla de etiquetas, que contiene el ID de la etiqueta principal de una etiqueta, o algún número mágico si la etiqueta no tiene padre. Sin embargo, la búsqueda de descendientes requiere, entonces, búsquedas completas repetidas de la base de datos para encontrar las etiquetas en cada "generación", lo que me gustaría evitar.

Una forma (probablemente) más rápida, pero menos normalizada de hacer esto sería tener una tabla con todos los elementos secundarios de cada etiqueta, o incluso todos los descendientes de cada etiqueta. Sin embargo, esto conlleva el riesgo de datos inconsistentes en la base de datos (por ejemplo, una etiqueta que es hija de más de un padre).

¿Hay una buena manera de hacer consultas para encontrar descendientes rápidamente, mientras se mantienen los datos lo más normalizados posible?

Answer 1

La respuesta de Ali tiene un enlace a Árboles y jerarquías de Joe Celko en SQL para Smarties , lo que confirma mi sospecha: no existe una estructura de base de datos simple que ofrezca lo mejor de todos los mundos. El mejor para mi propósito parece ser el "Árbol de Inserción Frecuente" detallado en este libro, que es como el " Modelo de conjunto anidado " del enlace de Ali, pero con indexación no consecutiva. Esto permite la inserción de O (1) ( a la numeración de líneas BÁSICA no estructurada), con una reorganización de índice ocasional cuando sea necesario.

Answer 2

Lo implementé utilizando dos columnas. Aquí lo simplifico un poco, porque tuve que mantener el nombre de la etiqueta en un campo / tabla diferente porque tuve que localizarlo para diferentes idiomas:

• etiqueta
• ruta

Mira estas filas por ejemplo:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

etc.

Al utilizar el operador like en el campo de ruta, puede obtener fácilmente todas las filas de etiquetas necesarias:

SELECT * FROM tags WHERE path LIKE 'database/%'

Hay algunos detalles de implementación, como cuando mueves un nodo en la jerarquía, también tienes que cambiar todos los hijos, etc., pero no es difícil.

También asegúrate de que la longitud de tu ruta sea lo suficientemente larga; en mi caso, no usé el nombre de la etiqueta para la ruta, sino otro campo para asegurarte de que no recibo rutas demasiado largas.

Answer 3

Algunas maneras aquí

Answer 4

Puedes construir lo que Kimball llama una tabla de ayuda de jerarquía.

Supongamos que la jerarquía tiene este aspecto: A - > B | B - > C | C - > D

insertaría registros en una tabla que se parece a esto

ParentID, ChildID, Depth, Highest Flag, Lowest Flag
A, A, 0, Y, N
A, B, 1, N, N
A, C, 2, N, N
A, D, 3, N, Y
B, B, 0, N, N
B, C, 1, N, N
B, D, 2, N, Y
C, C, 0, N, N
C, D, 1, N, Y
D, D, 0. N, Y

Creo que tengo eso correcto ... de todos modos. El punto es que aún almacena su jerarquía correctamente, simplemente construye esta tabla DESDE su tabla correcta. ESTA tabla de consultas como un Banshee. Digamos que quieres saber qué son todos los primeros niveles por debajo de B.

WHERE parentID = 'B' and Depth = 1

Answer 5

Usaría algún tipo de matriz para almacenar las etiquetas de los niños, esto debería ser mucho más rápido que unirse a una tabla en sí misma (especialmente si tiene una gran cantidad de etiquetas). Le eché un vistazo y no puedo saber si mysql tiene un tipo de datos de matriz nativa, pero puede emularlo utilizando una columna de texto y almacenando una matriz serializada en ella. Si desea acelerar aún más las cosas, debería poder colocar un índice de búsqueda de texto en esa columna para averiguar qué etiquetas están relacionadas.

[Editar] Después de leer el artículo de Ali, busqué más y encontré esta presentación en un montón de Enfoques para la implementación de jerarquías en postgres. Podría seguir siendo útil para fines explicativos.