dtcSoftware - powerShellDba

SQL Server Graph – Mustererkennung mit MATCH und SHORTEST_PATH

📅 14. Mai 2025 ✍️ Von einem erfahrenen SQL Entwickler & DBA ⏱ 10 Min. Lesezeit

1. Einleitung – Was ist SQL Graph?

Seit SQL Server 2017 bietet Microsoft native Graph-Funktionalitäten direkt in der Datenbank-Engine an. Damit lassen sich Knoten (Node Tables) und Kanten (Edge Tables) erstellen und mit speziellen T-SQL-Erweiterungen abfragen. Die Graph-Features sind vollständig in den SQL Server integriert – Sie nutzen also den gleichen Speicher, die gleichen Indizes und den gleichen Abfrageprozessor wie für relationale Tabellen.

💡 Wann lohnt sich ein Graph? Besonders bei komplexen Many-to-Many-Beziehungen, hierarchischen Daten mit mehreren Eltern oder wenn Sie Beziehungen analysieren möchten, die sich über mehrere Ebenen erstrecken (z. B. Social Networks, Empfehlungssysteme, Netzwerktopologien).

2. Beispiel-Daten: Personen und Freundschaften

Wir legen eine Knotentabelle Person und eine Kantentabelle friendOf an und füllen sie mit 10 Personen und 13 Freundschaftsbeziehungen. Jede Kante hat ein Gewicht (Strength) und ein Datum der Freundschaft.

CREATE TABLE dbo.Person ( 
ID INT PRIMARY KEY, 
Name VARCHAR(50), 
City VARCHAR(50) 
) AS NODE; 
 
CREATE TABLE dbo.friendOf ( 
SinceDate DATE, 
Strength INT 
) AS EDGE; 
 
-- Personen einfügen 
INSERT INTO dbo.Person (ID, Name, City) VALUES 
(1, 'Alice', 'Berlin'), 
(2, 'Bob', 'Hamburg'), 
(3, 'Carol', 'München'), 
(4, 'Dave', 'Köln'), 
(5, 'Eve', 'Frankfurt'), 
(6, 'Frank', 'Stuttgart'), 
(7, 'Grace', 'Düsseldorf'), 
(8, 'Hank', 'Leipzig'), 
(9, 'Ivy', 'Dresden'), 
(10, 'Jack', 'Nürnberg'); 
 
-- Freundschaftskanten (gerichtete Beziehungen) 
INSERT INTO dbo.friendOf ($from_id, $to_id, SinceDate, Strength) 
VALUES 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Alice'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Bob'), '2020-01-15', 8), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Alice'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Carol'), '2021-03-20', 9), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Bob'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Dave'), '2019-11-01', 7), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Bob'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Eve'), '2022-07-12', 6), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Carol'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Frank'), '2020-09-05', 8), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Dave'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Grace'), '2021-11-18', 7), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Eve'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Hank'), '2020-05-22', 9), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Eve'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Ivy'), '2022-02-14', 5), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Frank'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Jack'), '2023-01-10', 4), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Grace'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Ivy'), '2018-12-03', 7), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Hank'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Jack'), '2021-04-09', 6), 
((SELECT $node_id FROM dbo.Person WHERE Name = 'Ivy'), (SELECT $node_id FROM dbo.Person WHERE Name = 'Jack'), '2022-10-30', 8);

Das soziale Netzwerk enthält gerichtete Freundschaften (z. B. Alice → Bob, Bob → Dave, Dave → Grace). So können wir sowohl direkte Beziehungen als auch indirekte Pfade analysieren.

3. Direkte Freunde mit MATCH abfragen

Die MATCH-Klausel erlaubt eine lesbare Pfadnotation. Das folgende Beispiel findet alle direkten Freunde von Alice:

SELECT Person2.Name AS Friend 
FROM dbo.Person AS Person1, dbo.friendOf, dbo.Person AS Person2 
WHERE MATCH(Person1-(friendOf)->Person2) 
AND Person1.Name = 'Alice';

Ausgabe: Bob, Carol

Die Notation Person1-(friendOf)->Person2 bedeutet: Von Person1 ausgehend über die Kante friendOf zu Person2. Die Richtung des Pfeils bestimmt die Navigationsrichtung.

4. Pfade mit zwei Hops (Freunde von Freunden)

Mit zwei Kanten können wir Personen finden, die zwei Schritte entfernt sind. Hier suchen wir alle Freunde zweiten Grades von Alice (ohne die direkten Freunde):

SELECT DISTINCT Person3.Name AS FriendOfFriend 
FROM dbo.Person Person1, 
 dbo.friendOf fo1, 
 dbo.Person Person2, 
 dbo.friendOf fo2, 
 dbo.Person Person3 
WHERE MATCH(Person1-(fo1)->Person2-(fo2)->Person3) 
AND Person1.Name = 'Alice' 
AND Person3.Name NOT IN ('Alice', 'Bob', 'Carol');

Ausgabe: Dave, Eve, Frank
(Bob kennt Dave und Eve, Carol kennt Frank)

💡 Erklärung: Die MATCH-Klausel verkettet die Kanten einfach. Die Länge des Pfades ist durch die Anzahl der Knoten- und Kantenvariablen bestimmt.

5. Rekursive Suche mit SHORTEST_PATH

Für unbekannte oder variable Pfadlängen nutzt man SHORTEST_PATH (SQL Server 2019+). Die folgende Abfrage findet den kürzesten Pfad von Alice zu Jack (bis zu 5 Hops) und zeigt die Pfadlänge sowie die Reihenfolge der besuchten Knoten an.

SELECT 
STRING_AGG(Person2.Name, ' -> ') WITHIN GROUP (GRAPH PATH) AS Path, 
COUNT(fo.$edge_id) WITHIN GROUP (GRAPH PATH) AS Hops 
FROM dbo.Person AS p1, 
 dbo.friendOf FOR PATH AS fo, 
 dbo.Person FOR PATH AS p2 
WHERE MATCH(SHORTEST_PATH(p1(-(fo)->p2){1,5})) 
AND p1.Name = 'Alice' 
AND p2.Name = 'Jack';

Ausgabe:

Path Hops 
Alice -> Bob -> Dave -> Grace -> Ivy -> Jack 5

Die Notation p1(-(fo)->p2){1,5} bedeutet: Von p1 über die Kante fo (von p1 zu p2), wiederholt 1‑ bis 5‑mal. Sie können auch mit {2} eine feste Länge oder mit {2,} eine untere Grenze angeben.

⚠️ Beachte: SHORTEST_PATH liefert nur einen Pfad, selbst wenn mehrere gleich lange existieren. Die Reihenfolge der zurückgegebenen Knoten ist nicht garantiert.

6. Pfade visualisieren und Endknoten extrahieren

Mit LAST_VALUE können wir den letzten Knoten eines Pfades isolieren – nützlich, um z. B. alle Personen zu finden, die von Alice in maximal 3 Schritten erreichbar sind:

SELECT 
LAST_VALUE(p2.Name) WITHIN GROUP (GRAPH PATH) AS ReachablePerson, 
COUNT(fo.$edge_id) WITHIN GROUP (GRAPH PATH) AS Distance 
FROM dbo.Person AS p1, 
 dbo.friendOf FOR PATH AS fo, 
 dbo.Person FOR PATH AS p2 
WHERE MATCH(SHORTEST_PATH(p1(-(fo)->p2){1,3})) 
AND p1.Name = 'Alice' 
GROUP BY LAST_VALUE(p2.Name) WITHIN GROUP (GRAPH PATH), 
 COUNT(fo.$edge_id) WITHIN GROUP (GRAPH PATH);

Ausgabe (gekürzt):

ReachablePerson Distance 
Bob 1 
Carol 1 
Dave 2 
Eve 2 
Frank 2 
Grace 3 
Ivy 3 
Hank 3

So sehen Sie nicht nur die Existenz eines Pfades, sondern auch die genaue Distanz.

7. Indizes für Graph-Abfragen optimieren

Graph-Tabellen profitieren stark von Indizes auf den Pseudospalten. Für SHORTEST_PATH besonders wichtig sind Indizes auf ($from_id, $to_id) (Vorwärtssuche) und ($to_id, $from_id) (Rückwärtssuche).

CREATE INDEX IX_friendOf_from_to ON dbo.friendOf ($from_id, $to_id); 
CREATE INDEX IX_friendOf_to_from ON dbo.friendOf ($to_id, $from_id);

💡 Speicherplatz: Die automatisch erzeugten Indizes auf graph_id können Sie löschen, wenn Sie obige Indizes nachgebaut haben. Dadurch sparen Sie Platz und verbessern die Schreibperformance.

8. Einschränkungen und wann Sie Graph lieber nicht verwenden

Keine mehrfachen Kantentypen im selben Pfad – Sie können nicht innerhalb eines MATCH zwischen verschiedenen Kantentabellen wechseln.
Keine Zyklenvermeidung – SHORTEST_PATH vermeidet keine Zyklen, kann also bei zyklischen Graphen sehr lange laufen (dann mit maximaler Pfadlänge beschränken).
Nur SQL Server 2019+ – SHORTEST_PATH ist erst ab 2019 verfügbar. In älteren Versionen müssen Sie auf rekursive CTEs ausweichen.
Keine gewichteten Pfade – Die Suche nach dem Pfad mit der geringsten Summe von Kantenattributen (z. B. Strength) ist nicht möglich. Dafür bräuchten Sie ein vollwertiges Graphdatenbanksystem.

⚠️ Praxistipp: Für sehr große Graphen mit Millionen von Kanten stoßen Sie mit SHORTEST_PATH an Grenzen. Nutzen Sie dann besser native Graphdatenbanken wie Neo4j oder Azure Cosmos DB Gremlin API.

9. Fazit und weiterführende Tipps

SQL Server Graph bietet eine elegante Möglichkeit, Beziehungsanalysen direkt in T‑SQL durchzuführen, ohne eine separate Datenbank zu betreiben. Die Verwendung von MATCH und SHORTEST_PATH ist nach einer kurzen Einarbeitungszeit sehr intuitiv. Vor allem für soziale Netzwerke, Empfehlungssysteme oder mehrstufige Organisationsstrukturen ist dies ein Gewinn.

Wenn Sie mit dem Artikel arbeiten möchten: Legen Sie die Tabellen an, spielen Sie mit den Daten und variieren Sie die Pfadlängen. Bauen Sie die Indizes, vergleichen Sie die Performance mit und ohne Indizes. So gewinnen Sie ein Gefühl für die Stärken und Grenzen der Graph-Funktionen.