consulta la base de datos eficiente para antepasados ??en un gráfico dirigido acíclico

Question

Vamos a decir que tengo un grafo dirigido acíclico como una familia "árbol" (no es realmente un árbol ya que un niño tiene 2 padres). Quiero hacer una representación de este gráfico en un relacional base de datos para que sea más rápido para calcular todos los ancestros de un nodo, y todos los descendientes de un nodo. ¿Cómo se representa esta gráfica? ¿Cómo se consulta para todos los descendientes? ¿Cómo insertar y extraer los nodos y las relaciones? ¿Qué suposiciones que se hacen sobre los datos?

La mejor solución tendrá la mejor O grande para el número de instrucciones que se ejecutan a select/insert/delete antepasados ??y descendientes de consulta, con vínculos rotos por mejor gran O de tiempo total de ejecución, con vínculos rotos por las necesidades de espacio.

Mi compañero de trabajo planteó esta pregunta a mí. Tengo una solución, pero es de tamaño exponencial en el peor de los casos, así que quería ver cómo otras personas lo resolvería.

editar

Se ha aclarado la base de datos relacional. Esta pregunta es trivial (y aburrido) si utiliza bases de datos de gráficos con construido en la clausura transitiva.

Answer 1

Si selects> manipulations y selecciona especialmente de subárbol (todos los antepasados, todos los descendientes) me gustaría ir para una cierre enfoque -table. Sí, una explosión de caminos en la ruta de la mesa, pero sí proporcionan resultados rápidos (en contraposición al modelo de adyacencia), y mantiene cambios limitados a las partes relevantes (en contraposición a la actualización del 50% con conjuntos anidados).

Bill Karwin tiene alguna buena presentación en línea sobre pros y contras de diferentes modelos, véase http://www.slideshare.net/billkarwin/models-for-hierarchical-data (diapositiva 48 es una visión general).

Answer 2

Para los DAG en bases de datos SQL que parece haber sólo dos soluciones:

1. Recursive CON cláusula.

2. transitiva cierre

No estoy al tanto de cualquier sistema de etiquetado gráfico práctica (como conjuntos anidados, intervalos o materializada ruta)

Answer 3

"¿Cómo representar esta gráfica?"

• VAR NODES RELACIÓN {nodo: sometype} tecla {nodo};
• Bordes VAR RELACIÓN {parentNode: sometype childNode: sometype} tecla {parentNode childNode};
• CONSTRAINT NO_CYCLES is_empty (TCERRADA (bordes) DONDE parentNode = childNode);

"¿Cómo se consulta para todos los descendientes?"

TCERRADA (bordes) DONDE parentNode = somevalue;

"¿Cómo insertar y quitar nodos y las relaciones?"

• INSERT INTO BORDES RELACIÓN {TUPLE {parentNode somevalue chlidNode somevalue}};
• Bordes borrar según sea deleteCondition;

"¿Qué suposiciones que se hacen sobre los datos?"

¿Qué tipo de suposiciones están ahí para hacer? Ha especificado todo lo que hay que especificar diciendo "grafo dirigido acíclico".

Answer 4

RDBMS: s realmente no están diseñados para manejar este tipo de datos. La elección obvia es utilizar un gráfico de la base de datos lugar, entonces no hay necesidad de traducir el gráfico en una representación diferente, se utiliza una API gráfica de todo el camino. Hay una buena presentación de Marko Rodríguez para explicar el impacto del modelo de datos subyacente cuando se trata de recorridos de gráficos, consulte el Gráfico Transversal programación del patrón si quieres profundizar en eso.

Me escribió un ejemplo sencillo de manejo de los DAG con la base de datos gráfica Neo4j hace un tiempo que puede ser útil para usted.

Answer 5

En una base de datos relacional Me almacenar para cada nodo:

• padre
• childs
• antepasados ??

Con índice en todo y con un índice completo de ancestros

Solicitud de:

• todos los antepasados:
  • O (log n) (Encontrar el nodo entonces se hacen)
• todos los descendientes:
  • O (búsqueda índice completo de los antepasados) (depende de la base de datos)
• añadir nuevo nodo / nodo de borrado (sin niños):
  • O (1) para + antepasados ??padre
  • O (log n) para encontrar el padre
  • niño actualización del padre O (| niño de padre |)
• nodo movimiento (difícil) :
  • O (1) para actualizar padre
  • O (log n) para encontrar padres viejos / nuevos
  • O niño dos veces al día del padre (| niño de padre |)
  • Actualizar antepasados ??de todos los descendientes (reemplace sencilla): O (| descendientes | * | profundidad del árbol max |) (profundidad max: reemplazar y crear cadena grande de máx de longitud (profundidad max))

voluntad general, la complejidad depende de:

• profundidad del árbol
• árbol equilibrado?
• Número de niños? (En promedio, máx ...)
• complejidad de la operación en una base de datos relacional dada

Para SELECT sólo, eficiente, pero es difícil para las actualizaciones.

En la práctica: el trabajo en el árbol de la memoria RAM de tamaño (con memchaed por ejemplo, a mantener todo en la RAM) y si no se compra posssible más memoria RAM, de "cur" que árbol en árboles más pequeños

.

Todo-descendientes va a costar mucho de todos modos, con sub-árboles que puede tener descendientes de máximo profundidad D, sin tener todos ellos.

"salto" forma de sub-árbol a árbol secundario: más rápido petición, pero unos y forma en movimiento más rápido nodo (sólo tenga que actualizar un sub-árbol)

.