Esquema de base de datos para grupos jerárquicos

Question

Estoy trabajando en un diseño de base de datos para la jerarquía de grupos utilizada como base de un sistema más grande. Cada grupo puede contener otros grupos, y también 'dispositivos' como objetos de hoja (nada pasa debajo del dispositivo).

La base de datos que se utiliza es MS SQL 2005. (Aunque trabajar en MS SQL 2000 sería una ventaja, una solución que requiere MS SQL 2008 lamentablemente no es posible en este momento).

Existen diferentes tipos de grupos, que deben ser dinámicos y definibles en tiempo de ejecución por los usuarios. Por ejemplo, los tipos de grupo pueden ser "cliente", "cuenta", "ciudad" o "edificio", "piso", y cada tipo va a tener un conjunto diferente de atributos, definibles por el usuario. También se aplicarán reglas comerciales, por ejemplo, un "piso" solo puede estar contenido debajo de un grupo "de construcción", y nuevamente, estos son definibles en tiempo de ejecución.

Gran parte de la funcionalidad de la aplicación proviene de ejecutar informes basados ​​en estos grupos, por lo que debe haber una forma relativamente rápida de obtener una lista de todos los dispositivos contenidos en un determinado grupo (y todos los subgrupos).

El almacenamiento de grupos usando la técnica modified pre-order tree traversal tiene la ventaja de ser rápido, pero la desventaja es que es bastante complejo y frágil: si los usuarios/aplicaciones externos modifican la base de datos, existe la posibilidad de que se rompa por completo. También estamos implementando una capa ORM, y este método parece complicar el uso de las relaciones en la mayoría de las bibliotecas ORM.

El uso de common table expressions y una relación "estándar" de id/parentid groups parecen ser una forma poderosa de evitar ejecutar múltiples consultas recursivas. ¿Hay algún inconveniente en este método?

En cuanto a los atributos, ¿cuál es la mejor manera de almacenarlos? ¿Una mesa larga y estrecha que se relaciona con el grupo? ¿Debería almacenarse un atributo común, como "nombre" en una tabla de grupos, en lugar de la tabla de atributos (muchas veces, el nombre será todo lo que se requiere para mostrar)?

¿Habrá problemas de rendimiento con este método (supongamos un promedio alto de 2000 grupos con un promedio de 6 atributos cada uno y un promedio de 10 usuarios simultáneos en un hardware razonable, por ejemplo, quad-core Xeon 2 Ghz, 4GB ram, descontando cualquier otro proceso)?

Siéntase libre de sugerir un esquema completamente diferente al que he descrito aquí. Solo estaba tratando de ilustrar los problemas que me preocupan.

Answer 1

Recomiendo que realmente construyas la forma más fácil de mantener (la configuración "estándar" para padres/hijos) y ejecutes al menos algunos puntos de referencia básicos sobre ella.

Se sorprenderá de lo que un motor de base de datos puede hacer con la indexación adecuada, especialmente si su conjunto de datos puede caber en la memoria.

Suponiendo 6 atributos por grupo, 2000 grupos y 30 bytes/atributo, estás hablando de 360 ​​KB * elementos esperados/grupo - cifra de 400 KB. Si espera tener 1000 artículos/grupo, solo está buscando 400MB de datos, que encajarán en la memoria sin problemas, y las bases de datos son en uniones cuando todos los datos están en la memoria.

Answer 2

Las expresiones de tablas comunes le permitirán obtener una lista de grupos con las relaciones padre-hijo. Here es un ejemplo de un sproc que usa CTE para una aplicación diferente.Es razonablemente eficiente, pero tenga en cuenta las siguientes advertencias:

1. Si una pieza aparece más de una vez en la jerarquía, se informará en cada ubicación. Es posible que deba postprocesar los resultados.
2. Los CTE son algo obtusos y ofrecen un alcance limitado para filtrar los resultados dentro de la consulta; es posible que el CTE no aparezca más de una vez en la instrucción de selección.

Oracle's CONNECT BY es algo más flexible ya que no impone casi tantas limitaciones en la estructura de consultas como las de CTE, pero si usa SQL Server, esto no será una opción.

Si necesita hacer nada inteligente con los resultados intermedios a continuación, escribir un procedimiento almacenado que utiliza el CTE para obtener una consulta en bruto en una tabla temporal y trabajar en él desde allí. SELECT INTO minimizará el tráfico en el que se incurre. La tabla resultante estará en caché, por lo que las operaciones serán razonablemente rápidas.

Algunas posibles optimizaciones físicas que podrían ayudar:

• índices agrupados en la matriz de modo que salir nodos hijos de un padre utiliza menos de E/S.
• Gran cantidad de RAM y (según el tamaño de la tabla de su lista de materiales) servidores de 64 bits con aún más RAM para que la tabla principal de la lista de materiales pueda almacenarse en el núcleo. En un poco más de 32 O/S el interruptor de arranque/3G es su amigo y no tiene inconveniente real para un servidor de base de datos
• DBCC PINTABLE puede ayudar a forzar el gestor de bases para mantener la tabla en la memoria caché.

Las tablas de codificación de tipo de atributo primario no funcionarán bien con los CTE ya que terminará con una explosión combinatoria en los recuentos de filas si incluye la tabla de atributos. Esto excluiría cualquier lógica de negocio en la consulta que se filtró en los atributos. Sería mucho mejor almacenar los atributos directamente en la entrada de la tabla BOM.

Answer 3

Previo pedido Tree Traversal es muy útil. Puede hacerlo más robusto manteniendo los números de recorrido actualizados con desencadenantes.

Una técnica similar que he utilizado es mantener una tabla separada de (ancestor_id, descendant_id) que enumera todos los ascendientes y descendientes. Esto es casi tan bueno como los números de cruce previos a la orden.

Usando una tabla separada es útil, porque a pesar de que presenta unen a un extra, sí elimina la complejidad en una tabla separada.

Answer 4

El pedido por adelantado modificado es, esencialmente, el método de conjuntos anidados de Joe Celko. Su libro, "Árboles y jerarquías ..." abarca tanto la lista de adyacencia como la NS, con descripciones de las ventajas y desventajas de cada una. Con una indexación adecuada, el CTE de las listas de adyacencia obtiene el rendimiento más equilibrado. Si vas a leer en su mayoría, entonces NS será más rápido.

Lo que parece que está describiendo es un procesador de lista de materiales. Si bien no es M $, Graeme Birchall tiene un libro libre de DB2, con un capítulo sobre procesamiento de jerarquía utilizando CTE (la sintaxis es prácticamente idéntica, IIRC, en la que la sintaxis ANSI adoptó DB2, que M $ adoptó): http://mysite.verizon.net/Graeme_Birchall/cookbook/DB2V95CK.PDF