database - Consulta de base de datos eficiente para antepasados en un gráfico dirigido acíclico
algorithm graph (5)
Digamos que tengo un gráfico dirigido acíclico como un "árbol" familiar (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 O grande para la cantidad de declaraciones de select/insert/delete que ejecute para consultar ancestros y descendientes, con vínculos interrumpidos por mejor O grande para el 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.
editar
Base de datos relacional clarificada. Esta pregunta es trivial (y aburrida) si usa bases de datos de gráficos con cierres transitivos incorporados.
"¿Cómo representarías este gráfico?"
- RELACIÓN VAR NODES {node: tipo de cosa} KEY {nodo};
- 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ías a todos los descendientes?"
TCLOSE (EDGES) WHERE parentNode = algún valor;
"¿Cómo insertarías y eliminarías nodos y relaciones?"
- INSERT INTO EDGE RELATION {TUPLE {parentNode algún valor chlidNode algún valor}};
- BORRAR BORDES DONDE deleteCondition;
"¿Qué suposiciones estás haciendo sobre los datos?"
¿Qué tipo de suposiciones hay que hacer? Ha especificado todo lo que hay para especificar diciendo "gráfico acíclico dirigido".
En una base de datos relacional que almacenaría para cada nodo:
- padre
- niños
- antepasados
Con índice en todo y índice completo en antepasados
Solicitud de :
- todos los antepasados
- O (log n) (encuentra el nodo y listo)
- todos los descendientes:
- O (búsqueda de índice completo de antepasados) (depende de la base de datos)
- agregar nuevo nodo / eliminar nodo (sin hijos):
- O (1) para padre + antepasados
- O (log n) para encontrar padre
- actualizar los hijos del padre O (| childs del padre |)
- mover nodo (difícil) :
- O (1) para actualizar al padre
- O (log n) para encontrar padres viejos / nuevos
- actualizar los hijos del padre dos veces O (| childs del padre |)
- actualizar ancestros de todos los descendientes (reemplazo simple): O (| descendientes | * | árbol máximo de profundidad |) (profundidad-máximo: reemplazar y crear una gran cadena de longitud máxima (profundidad-máx))
La complejidad general dependerá de:
- profundidad del árbol
- árbol equilibrado?
- numero de hijos? (en mean, max ...)
- complejidad de operación en una base de datos relacional dada
Solo para SELECT, eficiente, pero difícil de actualizar.
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" árbol en árboles más pequeños.
Todos los descendientes costarán mucho de todos modos, con subárboles puedes 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).
Para los DAG en bases de datos SQL, parecía haber solo dos soluciones:
Cláusula recursiva CON.
No conozco ningún esquema de etiquetado gráfico práctico (como conjuntos anidados, intervalos o ruta materializada)
RDBMS: s realmente no están diseñados para manejar este tipo de datos. La opción obvia es usar una base de datos de gráficos en su lugar, luego no hay necesidad de traducir el gráfico en una representación diferente, se usa una API gráfica en todo momento. Hay una buena presentación de Marko Rodríguez que explica el impacto del modelo de datos subyacente cuando se trata de atravesar gráficos, consulte el patrón de programación de Graph Traversal si desea profundizar en eso.
Escribí un ejemplo simple de manejo de DAG con la base de datos de gráficos Neo4j hace un tiempo, que puede ser útil para usted.
Si selects > manipulations , y especialmente selecciones de subárbol (todos los antepasados, todos los descendientes), elegiría un enfoque de tabla de cierre . 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 una buena presentación en línea sobre los pros y los contras de los diferentes modelos, consulte http://www.slideshare.net/billkarwin/models-for-hierarchical-data (la diapositiva 48 es una descripción general).