Etiquetado jerárquico en SQL
mysql database (5)
La respuesta de Ali tiene un enlace a Árboles y jerarquías de Joe Celko en SQL for Smarties , lo que confirma mi sospecha: no existe una estructura de base de datos simple que ofrezca lo mejor de todos los mundos. Lo 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 indización no consecutiva. Esto permite la inserción de O (1) ( una numeración de línea BASIC no estructurada), con reorganización de índice ocasional cuando sea necesario.
Tengo una aplicación web PHP que utiliza una base de datos MySQL para el etiquetado de objetos, en la que he utilizado la estructura de etiquetas aceptada como la respuesta a esta pregunta SO .
Me gustaría implementar una jerarquía de etiquetas, donde cada etiqueta puede tener una etiqueta primaria única. Las búsquedas de una etiqueta padre T coincidirían con todos los descendientes de T (es decir, T, 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. La búsqueda de descendientes, sin embargo, requiere 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 (presumiblemente) más rápida, pero menos normalizada de hacer esto sería tener una tabla que contenga todos los hijos de cada etiqueta, o incluso todos los descendientes de cada etiqueta. Sin embargo, esto corre el riesgo de datos inconsistentes en la base de datos (por ejemplo, una etiqueta que es hija de más de un padre).
¿Existe una buena manera de realizar consultas para encontrar descendientes rápidamente, mientras se mantienen los datos lo más normalizados posible?
Lo implementé usando dos columnas. Aquí lo simplifico un poco, porque tuve que mantener el nombre de la etiqueta en un campo / tabla separada porque tuve que localizarlo para diferentes idiomas:
- etiqueta
- camino
Mire 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.
Usando 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 mueve un nodo en la jerarquía, tiene que cambiar también a todos los niños, 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 utilicé el nombre de la etiqueta para la ruta, sino otro campo para asegurarme de no obtener trayectorias demasiado largas.
Yo usaría algún tipo de arreglo para almacenar las etiquetas de los niños, esto debería ser mucho más rápido que unirme a una mesa en sí mismo (especialmente si tiene una gran cantidad de etiquetas). He echado un vistazo, y no puedo decir si mysql tiene un tipo de datos de matriz nativa, pero puedes emular esto usando 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, hice un poco más de búsqueda y encontré esta presentación en una serie de enfoques para implementar jerarquías en postgres. Puede ser útil con fines explicativos.
Puedes construir lo que Kimball llama una tabla de ayuda jerárquica.
Supongamos que su jerarquía se ve así: A -> B | B -> C | C -> D
insertarías registros en una tabla que se parece a esto
ParentID, ChildID, profundidad, bandera más alta, bandera más baja
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 almacenas tu jerarquía correctamente, solo construyes esta tabla DESDE tu tabla adecuada. ESTA tabla consulta como un Banshee. Digamos que quiere saber qué es todo el primer nivel debajo de B
DONDE parentID = ''B'' y profundidad = 1