rdbms - que - La mejor forma de almacenar/acceder a un gráfico dirigido

imagen de mapa de bits de 256 colores

Question

Tengo alrededor de 3500 instalaciones de control de inundaciones que me gustaría representar como una red para determinar las rutas de flujo (esencialmente un gráfico dirigido). Actualmente estoy usando SqlServer y un CTE para examinar recursivamente todos los nodos y sus componentes en sentido ascendente, y esto funciona siempre que la ruta ascendente no se bifurque mucho. Sin embargo, algunas consultas toman exponencialmente más tiempo que otras, incluso cuando no están mucho más lejos físicamente en la ruta (es decir, dos o tres segmentos "en sentido descendente") debido a la complejidad añadida aguas arriba; en algunos casos lo dejé pasar más de diez minutos antes de matar la consulta. Estoy usando una tabla simple de dos columnas, una columna es la instalación en sí misma y la otra es la instalación que está aguas arriba de la lista en la primera columna.

Traté de agregar un índice usando las instalaciones actuales para ayudar a acelerar las cosas, pero eso no hizo ninguna diferencia. Y, en cuanto a las conexiones posibles en el gráfico, cualquier nodo podría tener múltiples conexiones ascendentes y podría conectarse desde múltiples nodos "descendentes".

Ciertamente es posible que haya ciclos en los datos, pero aún no he descubierto una buena forma de verificar esto (salvo cuando la consulta CTE informó un recuento recursivo máximo, que fueron fáciles de corregir).

Entonces, mi pregunta es, ¿estoy almacenando esta información mal? ¿Hay alguna otra forma mejor que un CTE para consultar los puntos de subida?

Answer 1

Creo que su estructura de datos está bien (para SQL Server) pero un CTE puede no ser la solución más eficiente para sus consultas. Puede intentar hacer un procedimiento almacenado que atraviese el gráfico usando una tabla temporal como cola, esto debería ser más eficiente.

la tabla temporal también se puede usar para eliminar ciclos en el gráfico, aunque no debería haber ningún

Answer 2

No sé nada sobre las instalaciones de control de inundaciones. Pero tomaría la primera instalación. Y use una tabla temporal y un ciclo while para generar la ruta.

-- Pseudo Code TempTable (LastNode, CurrentNode, N)

DECLARE @intN INT SET @intN = 1

INSERT INTO TempTable(LastNode, CurrentNode, N) -- Insert first item in list with no up stream items...call this initial condition SELECT LastNode, CurrentNode, @intN FROM your table WHERE node has nothing upstream

WHILE @intN <= 3500 BEGIN SEt @intN = @intN + 1 INSERT INTO TempTable(LastNode, CurrentNode, N) SELECT LastNode, CurrentNode, @intN FROM your table WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)

IF @@ROWCOUNT = 0
BREAK

FIN

Si suponemos que cada nodo apunta a un niño. Entonces esto no debería tomar más de 3500 iteraciones. Si varios nodos tienen el mismo proveedor de origen, tomará menos. Pero más importante aún, esto te permite hacer esto ...

SELECCIONAR LastNode, CurrentNode, N FROM TempTable ORDER BY N

Y eso le permitirá ver si hay algún bucle o algún otro problema con su proveedor. Incidentalmente, 3500 filas no son tan grandes, incluso en el peor caso de que cada proveedor señale a un proveedor ascendente diferente, esto no debería tomar tanto tiempo.

Answer 3

Si quizas). Su conjunto de datos suena relativamente pequeño, puede cargar el gráfico en la memoria como una matriz de adyacencia o una lista de adyacencia y consultar el gráfico directamente, suponiendo que programe.

En cuanto al formato en disco, DOT es bastante portable / popular entre otros. También parece bastante común almacenar una lista de bordes en un formato de archivo plano como:

vertex1 vertex2 {edge_label1}+

Donde la primera línea del archivo contiene el número de vértices en el gráfico, y cada línea después de eso describe los bordes. Si los bordes están dirigidos o no dirigidos depende del implementador. Si quieres bordes dirigidos explícitos, entonces descríbelos usando bordes dirigidos como:

vertex1 vertex2
vertex2 vertex1

Answer 4

Tradicionalmente, los gráficos están representados por una matriz o un vector. La matriz requiere más espacio, pero es más fácil de procesar (3500x3500 entradas en su caso); el vector ocupa menos espacio (3500 entradas, cada una tiene una lista de a quién se conectan).

¿Eso te ayuda?

Answer 5

La mejor forma de almacenar gráficos es, por supuesto, usar un gráfico nativo db :-)

Eche un vistazo a neo4j . Está implementado en Java y tiene enlaces de Python y Ruby también.

Escribí dos páginas wiki con ejemplos simples de modelos de dominio representados como gráficos usando neo4j: ensamblado y roles . Más ejemplos se encuentran en la página de galería de modelado de dominio .

Answer 6

Mis experiencias con el almacenamiento de algo como usted describió en una base de datos de SQL Server:

Estaba almacenando una matriz de distancia, indicando cuánto tiempo toma viajar del punto A al punto B. He hecho la representación ingenua y la he almacenado directamente en una tabla llamada distancias con columnas A, B, distancia, tiempo.

Esto es muy lento en retreival simple. Descubrí que es mucho mejor almacenar toda la matriz como texto. Luego retírelo a la memoria antes de los cálculos, cree una estructura matriz en la memoria y trabaje con ella allí.

Podría proporcionar algún código, pero sería C #.