consulta de base de datos eficiente para antepasados ​​en un grafo acíclico dirigido

Question

Digamos 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 colocar una representación de este gráfico en una base de datos relacional para que sea rápido calcular todos los antepasados ​​de un nodo y todos los descendientes de un nodo. ¿Cómo representarías este gráfico? ¿Cómo consultarías a todos los descendientes? ¿Cómo insertarías y eliminarías nodos y relaciones? ¿Qué suposiciones estás haciendo sobre los datos?

La mejor solución tendrá la mejor gran O para el número de declaraciones select/insert/delete que ejecuta para consultar ancestros y descendientes, con vínculos interrumpidos por best big O para tiempo de ejecución total, con vínculos interrumpidos por requisitos de espacio.

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

edición

clarificada base de datos relacional. Esta pregunta es trivial (y aburrida) si usa bases de datos de gráficos con cierres transitivos incorporados.

Answer 1

Si selects>manipulations, y especialmente selecciona subárbol (todos los antepasados, todos los descendientes) que iría de un enfoque -table Closure. Sí, una explosión de rutas en su tabla de rutas, pero entrega resultados rápidamente (a diferencia del modelo de adyacencia) y mantiene las actualizaciones limitadas a las partes relevantes (a diferencia del 50% de actualización con conjuntos anidados).

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

Answer 2

RDBMS: s no son realmente diseñado para manejar este tipo de datos. La opción obvia es usar un graph database en su lugar, luego no hay necesidad de traducir el gráfico en una representación diferente, utiliza una API de gráficos en todo momento. Hay una buena presentación de Marko Rodríguez explicando el impacto del modelo de datos subyacente cuando se trata de cruces de gráficos, vea The Graph Traversal Programming Pattern si desea profundizar en eso.

escribí un ejemplo sencillo de handling DAGs with the Neo4j graph database hace un tiempo, que puede ser útil para usted.

Answer 3

"¿Cómo representarías este gráfico?"

• VAR NODES RELATION {node: sometype} KEY {node};
• VAR EDGES RELATION {parentNode: tipo de niño childNode: tipo de cosa} KEY {nodo de niño parentNode};
• CONSTRAINT NO_CYCLES IS_EMPTY (TCLOSE (EDGES) WHERE parentNode = childNode);

"¿Cómo consultaría a todos los descendientes?"

TCERRADA (bordes) DONDE parentNode = somevalue;

"¿Cómo insertaría y eliminaría nodos y relaciones?"

• INSERT INTO RELACIÓN BORDES {TUPLE {parentNode somevalue chlidNode somevalue}};
• BORRAR bordes donde deleteCondition;

"¿Qué suposiciones estás haciendo acerca de los datos"

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

Answer 4

En un databa relacional sí me gustaría almacenar para cada nodo:

• padre
• niño
• 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/borrar nodo (sin niños):
  • O (1) para el padre + antepasados ​​
  • O (log n) para encontrar al padre
  • actualización del padre del niño O (| niño de padre |)
• nodo de movimiento (difícil):
  • O (1) para actualizar padre
  • O (log n) para encontrar viejos/nuevos padres del niño
  • actualización del padre dos veces O (| childs del padre |)
  • antepasados ​​actualización de todos descendan ts (reemplazo simple): O (| descendientes | * | árbol de profundidad máxima |) (profundidad max: reemplazar y crear cadena grande de máx de longitud (profundidad-max))

complejidad global se depende de:

• profundidad del árbol
• árbol equilibrado?
• número de hijos? (en mean, max ...)
• complejidad de la operación en una base de datos relacional dado

para ciertos única, eficiente, pero es difícil para las actualizaciones.

En la práctica: trabaje en el árbol de tamaño de RAM (con memchaed por ejemplo, mantenga todo en la RAM) y si no es posible compre más RAM, de "cur" su árbol en árboles más pequeños.

Todos los descendientes costarán mucho de todos modos, con subárboles puede tener descendientes de profundidad máxima D, sin tenerlos todos.

Usted "salta" del subárbol al subárbol: más solicitudes pero más rápidas Y mueva el nodo mucho más rápido (solo necesita actualizar un subárbol).

Answer 5

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

1. recursiva con un cláusula.

2. Transitive closure

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