¿Tiene sentido asignar una estructura de datos de gráficos a una base de datos relacional?

Question

Específicamente un Multigraph.

Un colega sugirió esto y estoy completamente desconcertado.

¿Tiene alguna idea sobre esto?

Answer 1

Es bastante sencillo almacenar un gráfico en una base de datos: tiene una tabla para nodos y una tabla para bordes, que actúa como una tabla de relaciones de muchos a muchos entre la tabla de nodos y ella misma. De esta manera:

create table node (
    id integer primary key 
); 

create table edge (
    start_id integer references node, 
    end_id integer references node, 
    primary key (start_id, end_id) 
); 

Sin embargo, hay un par de puntos pegajosos sobre cómo guardar un gráfico de esta manera.

En primer lugar, los bordes de este esquema se dirigen naturalmente: el inicio y el final son distintos. Si sus bordes no están dirigidos, tendrá que tener cuidado al escribir consultas o almacenar dos entradas en la tabla para cada borde, una en cualquier dirección (¡y luego tenga cuidado al escribir consultas!). Si almacena un único borde, le sugiero que normalice el formulario almacenado, quizás siempre considere el nodo con el ID más bajo como el inicio (y agregue una restricción de verificación a la tabla para aplicar esto). Podrías tener una representación genuinamente desordenada al no tener los bordes referidos a los nodos, sino tener una tabla de unión entre ellos, pero eso no me parece una gran idea.

En segundo lugar, el esquema anterior no tiene forma de representar un multigrafo.Puede extenderlo con la suficiente facilidad para hacerlo; si los bordes entre un par dado de nodos son indistinguibles, lo más simple sería agregar un recuento a cada fila de borde, indicando cuántos bordes hay entre los nodos referidos. Si son distinguibles, tendrá que agregar algo a la tabla de nodos para poder distinguirlos; una ID de borde autogenerada podría ser lo más simple.

Sin embargo, incluso habiendo solucionado el almacenamiento, tiene el problema de trabajar con el gráfico. Si desea hacer todo su procesamiento en objetos en la memoria, y la base de datos es puramente de almacenamiento, entonces no hay problema. Pero si desea realizar consultas en el gráfico de la base de datos, tendrá que descubrir cómo hacerlo en SQL, que no tiene ningún soporte incorporado para gráficos, y cuyas operaciones básicas no se pueden adaptar fácilmente a trabajar con gráficos Se puede hacer, especialmente si tienes una base de datos con soporte recursivo de SQL (PostgreSQL, Firebird, algunas de las bases de datos propietarias), pero se necesita algo de reflexión. Si desea hacer esto, mi sugerencia sería publicar más preguntas sobre las consultas específicas.

Answer 2

Bueno, la información debe almacenarse en alguna parte, una base de datos relacional no es una mala idea.

Sería simplemente una relación de muchos a muchos, una tabla de una lista de nodos y una tabla de una lista de bordes/conexiones.

Answer 3

Considere cómo Facebook podría implementar el gráfico social en su base de datos. Podrían tener una mesa para las personas y otra mesa para las amistades. La tabla de amistades tiene al menos dos columnas, cada una de las cuales es una clave foránea para la tabla de personas.

Dado que la amistad es simétrica (en Facebook), pueden garantizar que la ID de la primera clave externa sea siempre menor que la ID de la segunda clave externa. Twitter tiene un gráfico dirigido para su red social, por lo que no usaría una representación canónica como esa.

Answer 4

Es un enfoque aceptable. Debe considerar cómo se manipulará esa información. Lo más probable es que necesite un idioma separado de su base de datos para realizar los cálculos relacionados con gráficos de clases que este tipo de datos implica. Skiena's Algorithm Design Manual tiene una extensa sección de estructuras de datos de gráficos y su manipulación.

Sin considerar qué tipo de consultas puede ejecutar, comience con dos tablas vertices y edges. Los vértices son simples, un identificador y un nombre. Los bordes son complejos dado el multigrafo. Los bordes deben identificarse de manera única mediante una combinación de dos vértices (es decir, claves externas) y alguna información adicional. La información adicional depende del problema que está resolviendo. Por ejemplo, si la información del vuelo, los horarios de salida y llegada y la línea aérea. Además, deberá decidir si el borde está dirigido (es decir, de una sola dirección) o no, y realizar un seguimiento también de esa información.

Según el cálculo, puede terminar con un problema que se resuelve mejor con algún tipo de inteligencia artificial/algoritmo de aprendizaje automático. Por ejemplo, vuelos óptimos. El libro Programming Collective Intelligence tiene algunos algoritmos útiles para este propósito. Pero donde se guardan los datos no cambia el algoritmo en sí.