Consulta eficiente de una tabla dirigida/no dirigida de bordes de gráficos en SQL Server

Question

Tengo una tabla de SQL Server en la que cada fila representa una ventaja en una red de gráficos. El FromNodeID y ToNodeID son claves externas a una tabla de nodos, y el esquema es algo como esto:

CREATE TABLE #Edges (
    EdgeID int identity (1,1), 
    FromNodeID int, 
    ToNodeID int 
); 

INSERT INTO #Edges (FromNodeID, ToNodeID) VALUES 
    (1,2), 
    (1,3), 
    (1,4), 
    (2,3), 
    (3,5), 
    (4,5), 
    (5,6); 

Ahora, si considero cada borde que será dirigida (es decir, de una forma), entonces es fácil de resolver todos esos nodos a los que puedo acceder directamente desde cualquier nodo. Yo añadiría un índice para la columna de la FromNodeID, a continuación, ejecutar una consulta como esta:

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3 

Resultado: 5

Pero ¿cuál sería la mejor manera de estructurar mi mesa/consulta si quiero tratar cada borde como unidireccional. es decir, a partir del nodo 3, me gustaría obtener los resultados:

Resultado: 1, 2, 5

La forma más simple que puedo pensar sería la de añadir un índice adicional a la columna y luego ToNodeID ejecutar una consulta como esta:

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3 
UNION SELECT FromNodeID FROM #Edges WHERE ToNodeID = 3; 

Pero esto obviamente implica la combinación de conjuntos de resultados a partir de dos preguntas y no parece muy eficiente - ¿existe una mejor manera de escribir esto en una sola consulta? (Tenga en cuenta que no quiero volver a insertar los bordes invertidos en la tabla; necesito poder tratar los bordes como dirigidos o no dirigidos en el tiempo de ejecución).

¡Gracias por cualquier consejo!

Answer 1

Pero esto obviamente implica combinar conjuntos de resultados de dos consultas y no parece ser muy eficiente. ¿Hay alguna forma mejor de escribir esto en una sola consulta?

Esto es lo suficientemente eficiente.

usted puede hacer esto:

SELECT CASE 3 WHEN FromNodeId THEN ToNodeId ELSE FromNodeId END 
FROM Edges 
WHERE 3 IN (FromNodeId, ToNodeId) 

pero esto será esencialmente los mismos (Will UNION estos índices bajo el capó).

Aquí es un script para la prueba:

CREATE TABLE #Edges 
     (
     EdgeID INT IDENTITY (1,1) PRIMARY KEY, 
     FromNodeID int NOT NULL, 
     ToNodeID int NOT NULL 
     ) 
CREATE INDEX ix_edges_from ON #Edges (FromNodeID, ToNodeId) 
CREATE INDEX ix_edges_to ON #Edges (ToNodeID, FromNodeId) 
; 
WITH q (rn) AS 
     (
     SELECT 1 
     UNION ALL 
     SELECT rn + 1 
     FROM q 
     WHERE rn < 1000 
     ) 
INSERT 
INTO #Edges (FromNodeId, ToNodeId) 
SELECT q1.rn, q2.rn 
FROM q q1 
CROSS JOIN 
     q q2 
WHERE (q1.rn + q2.rn) % 37 = 0 
OPTION (MAXRECURSION 0) 

Para el UNION:

SELECT ToNodeId 
FROM #Edges 
WHERE FromNodeId = 3 
UNION 
SELECT FromNodeId 
FROM #Edges 
WHERE ToNodeId = 3 


    |--Stream Aggregate(GROUP BY:([Union1006])) 
     |--Merge Join(Concatenation) 
      |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD) 
      |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD) 

Para el IN:

|--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN (3)=[tempdb].[dbo].[#Edges].[FromNodeID] THEN [tempdb].[dbo].[#Edges].[ToNodeID] ELSE [tempdb].[dbo].[#Edges].[FromNodeID] END)) 
     |--Sort(DISTINCT ORDER BY:([tempdb].[dbo].[#Edges].[EdgeID] ASC)) 
      |--Concatenation 
       |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD) 
       |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD) 

Como se puede ver, los planes son esencialmente los mismos : ambos toman valores de los índices correspondientes y concatenan el re sults.

La consulta UNION es en realidad un poco más eficiente, ya que utiliza un Merge Join para concatenar los resultados, y los registros han salido de la combinación de mezcla naturalmente ordenada, por lo que el Stream Aggregate no tiene que ordenar.

Answer 2

Hay tres opciones que se me ocurren: hacerlo solo en la tabla, solo en las consultas, o crear un view.Para la tabla, cree triggers que impone el cierre simétrico (por ejemplo, al insertar (a, b), también inserte (b, a); al actualizar (a, b) a (c, d), elimine la antigua conservación de simetría (b, a) par, luego inserte (d, c)). Tenga en cuenta que esto puede no funcionar, ya que algunos RDBMS (no estoy seguro de si SQL Server es uno) no permiten inserciones/actualizaciones en la tabla activada por un activador.

En las consultas,

SELECT CASE FromNodeID WHEN 3 THEN ToNodeId ELSE FromNodeId END 
    FROM #Edges 
    WHERE FromNodeID=3 OR ToNodeID=3 

Para la vista, crear uno que es el cierre simétrica de la tabla original. Creo que aún deberías usar UNION, pero podría simplificar la escritura de consultas.

CREATE VIEW undirected_edges (FirstEdgeID,SecondEdgeId) 
    AS (SELECT FromNodeID, ToNodeID FROM #Edges) 
    UNION DISTINCT 
    (SELECT ToNodeID, FromNodeID FROM #Edges) 

Answer 3

¿Debe procesar el gráfico directamente desde SQL Server? Si realmente le preocupa el rendimiento, debe usar una de las estructuras de datos específicamente para representar y procesar gráficos. La mayor parte del trabajo que he hecho con gráficos (y he hecho mucho) hubiera sido inviable si hubiera utilizado un back-end de base de datos genérico para consultar los gráficos.

Una de las representaciones más eficaces que he utilizado se describe en los apéndices de un compilador que tengo: Engineering a Compiler, por Keith Cooper y Linda Torczon.