Interrogazione efficiente di una tabella diretta/non indirizzata di spigoli del grafico in SQL Server

Question

Ho una tabella server SQL in cui ogni riga rappresenta un bordo in una rete di grafici. Il FromNodeID e ToNodeID sono chiavi esterne a una tabella di nodo, e lo schema è qualcosa di simile:

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); 

Ora, se considero ogni bordo che sarà diretto (cioè, solo andata), quindi è facile da lavorare fuori tutti quei nodi che posso ottenere direttamente da qualsiasi nodo. Mi piacerebbe aggiungere un indice alla colonna FromNodeID, e quindi eseguire una query come questa:

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3 

Risultato: 5

Ma quale sarebbe il modo migliore per strutturare la mia tabella/query se voglio tratta ogni spigolo come unidirezionale. cioè a partire dal nodo 3, mi piacerebbe ottenere i risultati:

Risultato: 1, 2, 5

Il modo più semplice che posso pensare sarebbe quello di aggiungere un indice aggiuntivo alla colonna ToNodeID e poi eseguire una query come questa:

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

Ma questo ovviamente comporta set combinando risultato da due query e non sembra molto efficiente - c'è un modo migliore per scrivere questo in una singola query? (Si noti che non voglio inserire nuovamente i bordi invertiti nella tabella - Devo essere in grado di trattare i bordi come diretti o non diretti in fase di esecuzione).

Grazie per qualsiasi consiglio!

Answer 1

Ma questo ovviamente implica la combinazione di set di risultati da due query e non sembra molto efficiente - c'è un modo migliore per scrivere questo in una singola query?

Questo è abbastanza efficiente.

Si potrebbe fare questo:

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

ma questo sarà essenzialmente gli stessi (si UNION questi indici sotto il cofano).

Ecco uno script di prova:

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) 

Per la 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) 

Per la 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) 

Come si può vedere, i piani sono essenzialmente le stesse : entrambi prendono valori dagli indici corrispondenti e concatenano il re sultati.

Il UNION interrogazione è in realtà un po 'più efficiente, in quanto utilizza un Merge Join per concatenare i risultati, e le registrazioni uscire del join unione naturalmente ordinata, in modo che il Stream Aggregate non ha bisogno di ordinare.

Answer 2

Ci sono tre opzioni a cui posso pensare: farlo solo nella tabella, solo nelle query o creare un view.Per la tabella, creare triggers che impone la chiusura simmetrica (ad esempio quando si inserisce (a, b), anche inserire (b, a); quando si aggiorna (a, b) a (c, d), eliminare il vecchio simmetria-conservazione (b, a) coppia, quindi inserire (d, c)). Si noti che questo potrebbe non funzionare, poiché alcuni RDBMS (non sono sicuro se SQL Server è uno solo) non consentono inserimenti/aggiornamenti alla tabella su cui è stato attivato un trigger.

Nelle query,

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

per la vista, creare uno che è la chiusura simmetrica della tabella originale. Penso che dovrai ancora utilizzare UNION, ma potrebbe semplificare la scrittura delle query.

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

Answer 3

È necessario elaborare il grafico direttamente da SQL Server? Se sei davvero preoccupato per le prestazioni, dovresti utilizzare una delle strutture dati specifiche per rappresentare ed elaborare i grafici. Gran parte del lavoro che ho fatto con i grafici (e ne ho fatto un sacco) sarebbe stato impossibile se avessi usato un database generico per consultare i grafici.

Una delle rappresentazioni più efficaci che ho usato è descritta nelle appendici di un libro di compilazione che ho: Engineering a Compiler, di Keith Cooper e Linda Torczon.