בשני פוסטים קודמים הצגתי פתרונות לבעייה הבאה: כמה משולשים יש בציור הזה:
והפעם - פתרון המבוסס על GraphDB: יכולת שמאפשרת לטפל באמצעות SQL בגראפים, רשתות, עצים וכו'
הפוסט הזה אינו אמור להיות מבוא ל-GraphDB, אז ניגש למלאכה, ומתוך הדוגמאות ניתן יהיה להבין איך זה עובד באופן מעשי.
גראף הוא אובייקט הכולל קודקודים וקשתות המחברות אותם; כשיש לו כל מיני וריאציות: עץ הוא סוג של גראף העונה על תנאים מסויימים, יש גראפים בהם הקשתות מכוונות (כלומר - יש חשיבות לכיוון של הקשת, היא יוצאת מקודקוד אחד ומגיעה לאחר ולא להיפך), קשרי "חברות" בין חברי רשת חברתית הם רשת (לא מכוונת!), מבנה היררכי של ארגון הוא גם רשת מכוונת וגם עץ, וכו'.
מידול הבעייה
גם הציור הנ"ל הוא גראף עם קודקודים וקשתות, וכל אחד מ-91 המשולשים (ספרנו בפוסטים הקודמים..) בנוי משלושה קודקודים ושלוש קשתות שכל אחת מחברת שני קודקודים.
כמו בכל דוגמה של גראף, צריך להתאים את המציאות (הציור הנ"ל) למודל של הגראף, ולכן: די ברור שיש קשת המחברת את קודקוד 1 לקודקוד 2, וקשת המחברת את קודקוד 2 לקודקוד 3; אך מכיוון ששתיהן על קו ישר אחד - אזי יש גם קשת המחברת את קודקוד 1 לקודקוד 3.
הרבה קשתות? אל דאגה: אנחנו נשמור רק את המידע לגבי הקשתות "הישירות" שאינן עוברות דרך קודקודי ביניים, אבל נציין את הקו הכללי עליו הן מונחות, וכך המערכת תוכל לשחזר את הקשתות החסרות. כלומר - לגבי קשת 1-2 וקשת 2-3 נציין שהן על הקו 1-4 (שנקרא לו 0104), ומכיוון שהן על אותו הקו ויש להן קודקוד משותף (2) אזי הן יוצרות את קשת 1-3.
ב-GraphDB הקשתות תמיד מכוונות (בציור לא!) ולכן כל קשת תהיה מהקטן לגדול, וכל משולש ייוצג על ידי שלושה קודקודים מהקטן לגדול.
הטבלאות
ב-SQL Server יש טבלה מסוג Node עבור הקודקודים,
וטבלה מסוג Edge עבור הקשתות המקשרות את הקודקודים הנ"ל; ולטבלאות כאלו יש מבנה מיוחד והרחבות של שפת SQL כדי שאפשר יהיה לתחקר אותן.
נתחיל בקודקודים - ניצור טבלה מסוג Node ונאכלס אותה ב-20 הקודקודים שבציור:
CREATE TABLE dbo.Nodes
(Node Int,
Constraint PK_Nodes Primary Key Clustered(Node)) AS NODE;
Insert
Into Nodes(Node)
Values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20);
Select * From Nodes;
כפי שאפשר לראות, העמודה הימנית כוללת את שמות העמודות כפי שאני הכנסתי,
אך המערכת יצרה באופן אוטומטי עמודה בשם node_id$ (הקוד ההקסדצימלי שאחרי השם אינו חשוב), שכוללת פרטים על הסכימה, הטבלה, ומספר השורה; במבנה של JSON.
מה עם הקשתות? יש יותר וגם ההכנסה שלהן יותר מורכבת כי עליה לכלול את ה-node_id של כל אחד משני קודקודיה מתוך טבלת הקודקודים;
אבל קודם כל הטבלה, כולל עמודה למספר הקו אליו שייכת כל קשת, ורק לאחר מכן פקודות ה-Insert:
CREATE TABLE Lines
(Line int) AS EDGE;
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=1),
(SELECT $node_id FROM Nodes WHERE Node=2),
0104);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=1),
(SELECT $node_id FROM Nodes WHERE Node=5),
0108);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=1),
(SELECT $node_id FROM Nodes WHERE Node=9),
0112);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=1),
(SELECT $node_id FROM Nodes WHERE Node=13),
0117);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=1),
(SELECT $node_id FROM Nodes WHERE Node=18),
0120);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=2),
(SELECT $node_id FROM Nodes WHERE Node=5),
0217);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=2),
(SELECT $node_id FROM Nodes WHERE Node=3),
0104);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=3),
(SELECT $node_id FROM Nodes WHERE Node=5),
0309);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=3),
(SELECT $node_id FROM Nodes WHERE Node=6),
0319);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=3),
(SELECT $node_id FROM Nodes WHERE Node=7),
0312);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=3),
(SELECT $node_id FROM Nodes WHERE Node=4),
0104);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=4),
(SELECT $node_id FROM Nodes WHERE Node=8),
0420);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=5),
(SELECT $node_id FROM Nodes WHERE Node=9),
0309);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=5),
(SELECT $node_id FROM Nodes WHERE Node=10),
0217);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=5),
(SELECT $node_id FROM Nodes WHERE Node=6),
0108);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=6),
(SELECT $node_id FROM Nodes WHERE Node=10),
0319);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=6),
(SELECT $node_id FROM Nodes WHERE Node=7),
0108);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=7),
(SELECT $node_id FROM Nodes WHERE Node=11),
0312);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=7),
(SELECT $node_id FROM Nodes WHERE Node=8),
0108);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=8),
(SELECT $node_id FROM Nodes WHERE Node=11),
0818);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=8),
(SELECT $node_id FROM Nodes WHERE Node=12),
0420);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=9),
(SELECT $node_id FROM Nodes WHERE Node=13),
0919);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=9),
(SELECT $node_id FROM Nodes WHERE Node=10),
0112);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=10),
(SELECT $node_id FROM Nodes WHERE Node=11),
0818);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=10),
(SELECT $node_id FROM Nodes WHERE Node=12),
0112);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=10),
(SELECT $node_id FROM Nodes WHERE Node=13),
0818);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=10),
(SELECT $node_id FROM Nodes WHERE Node=14),
0319);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=10),
(SELECT $node_id FROM Nodes WHERE Node=15),
0217);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=11),
(SELECT $node_id FROM Nodes WHERE Node=12),
0312);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=12),
(SELECT $node_id FROM Nodes WHERE Node=15),
1219);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=12),
(SELECT $node_id FROM Nodes WHERE Node=17),
0420);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=13),
(SELECT $node_id FROM Nodes WHERE Node=14),
0117);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=13),
(SELECT $node_id FROM Nodes WHERE Node=18),
0818);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=13),
(SELECT $node_id FROM Nodes WHERE Node=19),
0919);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=14),
(SELECT $node_id FROM Nodes WHERE Node=19),
0319);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=14),
(SELECT $node_id FROM Nodes WHERE Node=16),
0117);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=15),
(SELECT $node_id FROM Nodes WHERE Node=16),
1219);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=15),
(SELECT $node_id FROM Nodes WHERE Node=17),
0217);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=16),
(SELECT $node_id FROM Nodes WHERE Node=17),
0117);
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=16),
(SELECT $node_id FROM Nodes WHERE Node=19),
1219);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=17),
(SELECT $node_id FROM Nodes WHERE Node=20),
0420);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=18),
(SELECT $node_id FROM Nodes WHERE Node=19),
0120);
---------------------------------------------------
INSERT
INTO Lines
VALUES ((SELECT $node_id FROM Nodes WHERE Node=19),
(SELECT $node_id FROM Nodes WHERE Node=20),
0120);
---------------------------------------------------
במקרה זה עמודה edge_id$ היא המפתח של הקשת, שיוצאת מקודקוד from_id$ ומגיעה לקודקוד to_id$, ושיכת לקו Line (זו העמודה היחידה שהגדרתי - שלוש האחרות מוגדרות אוטומטית בכל טבלת Edge).
שליפת הנתונים
ל-SQL Server יש הרחבה עבור טבלאות Node & Edge במקום Join רגיל המתבקש במקרה זה:
SELECT N1.Node,
N2.Node,
L.Line
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)
Order By N1.Node,
N2.Node;
אפשר לראות שהאופרטור Match מהווה Join כפול המתאם בין שלוש טבלאות (ל-Nodes יש שני מופעים - עבור from_id ועבור to_id).
אם רוצים לתאם (Match) בין שתי קשתות החולקות קודקוד משותף על אותו קו אזי:
SELECT N1.Node,
N2.Node,
N3.Node,
L1.Line,
L2.Line
FROM Nodes N1, Nodes N2, Nodes N3, Lines L1, Lines L2
WHERE MATCH(N1-(L1)->N2-(L2)->N3)
And L1.Line=L2.Line
Order By N1.Node,
N2.Node,
N3.Node;
וכך הלאה אם רוצים 3 קשתות או 4 קשתות או... רגע: איך נדע כמה קשתות יש? מה עושים כשיש הרבה? או אז משתמשים ב-CTE רקורסיבי כך:
With T As
(SELECT N1.Node Node1,
N1.$node_id node_id1,
N2.Node Node2,
N2.$node_id node_id2,
L.Line,
1 Lvl,
Cast(Concat(N1.Node,',',N2.Node) As Varchar(Max)) Nodes
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)
Union All
SELECT T.Node1,
T.node_id1,
Iif(T.node_id2=T1.node_id1,T1.Node2,T1.Node1),
Iif(T.node_id2=T1.node_id1,T1.node_id2,T1.node_id1),
T.Line,
T.Lvl+1,
Concat(T.Nodes,',',Iif(T.node_id2=T1.node_id1,T1.Node2,T1.Node1))
From T
Inner Join (SELECT N1.Node Node1,
N1.$node_id node_id1,
N2.Node Node2,
N2.$node_id node_id2,
L.Line
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)) T1
On T.Line=T1.Line
And ((T.node_id2=T1.node_id1 And Concat(',',T.Nodes,',') Not Like Concat('%,',T1.Node2,',%')) Or (T.node_id2=T1.node_id2 And Concat(',',T.Nodes,',') Not Like Concat('%,',T1.Node1,',%'))))
Select *
From T
Order By Node1,
Node2;
למה כל כך מסובך? זה תמיד ככה? לא, אבל קודם כל נירגע, ונבין מה אנחנו רואים בפלט: אלו הן כל הקשתות, הישירות והעקיפות, ואת המסלול אנחנו רואים בעמודה הימנית Nodes שצברה את כל המסלול ועזרה לנו למנוע כפילויות. למשל בשורה 3 רואים את הקשת 1-4 שעוברת בדרך את הקודקודים (לפי הסדר) 1,2,3,4.
למה כל כך מסובך? ראשית כל - האופרטור Match אינו תומך ב-CTE (גם לא רקורסיבי): לא ניתן לכלול בו סט שנוצר על ידי CTE. ככה החליטו החכמים ממיקרוסופט! לפיכך ל-T הרקורסיבי אני נאלץ ליצור Join בשיטה הישנה והטובה במקום להשתמש ב-Match (אם כי נתנחם בכך שה-Join יהיה עם שאילתת משנה שנוצרה בעזרת Match כשר למהדרין לחסידי GraphDB). זה יקרה בכל CTE רקורסיבי! חוץ מזה, יש את כל הקשיים שהמודל הזה יוצר: בדרך כלל השירשור הולך מהגדול לקטן (למשל 1-2-3 בו משרשרים לזנב של האחד את הראש של השני), אבל לא תמיד: 8-11-10 (עיינו בגרף) בו צריך לשרשר לזנב של 8-11 את הזנב 11 של 10-11 ולא את הראש 10.
במקרה זה יש לוודא שהרקורסיה לא תנסה לשרשר לזנב 10 של 8-11-10 בחזרה את הראש 10 של 10-11
ולשם כך התווספה עמודת השירשור Line ובדיקת התנאי בעזרת Iif ב-Select שבחלק הרקורסיבי).
הפתרון
נו טוב, אבל מה עם המשולשים לכבודם התכנסנו? על בסיס השליפה הרקורסיבית הנ"ל שיוצרת את כל הקשתות, נחפש שלשות שסוגרות משולש, מהקטן לגדול (כלומר שהמשולש 1-2-5 לא יופיע שוב בתור 2-1-5 או 1-5-2 וכו'); ושהן לא יהיו על אותו הקו ונקבל משולשים "שטוחים" שלא נחשבים במקרה זה:
With T As
(SELECT N1.Node Node1,
N1.$node_id node_id1,
N2.Node Node2,
N2.$node_id node_id2,
L.Line,
1 Lvl,
Cast(Concat(N1.Node,',',N2.Node) As Varchar(Max)) Nodes
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)
Union All
SELECT T.Node1,
T.node_id1,
Iif(T.node_id2=T1.node_id1,T1.Node2,T1.Node1),
Iif(T.node_id2=T1.node_id1,T1.node_id2,T1.node_id1),
T.Line,
T.Lvl+1,
Concat(T.Nodes,',',Iif(T.node_id2=T1.node_id1,T1.Node2,T1.Node1))
From T
Inner Join (SELECT N1.Node Node1,
N1.$node_id node_id1,
N2.Node Node2,
N2.$node_id node_id2,
L.Line
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)) T1
On T.Line=T1.Line
And ((T.node_id2=T1.node_id1 And Concat(',',T.Nodes,',') Not Like Concat('%,',T1.Node2,',%')) Or (T.node_id2=T1.node_id2 And Concat(',',T.Nodes,',') Not Like Concat('%,',T1.Node1,',%'))))
Select T1.Node1,
T1.Line,
T2.Node1 Node2,
T2.Line,
T3.Node2 Node3,
T3.Line
From T T1
Inner Join T T2
ON T1.node_id2=T2.node_id1
And T1.Line<>T2.Line
Inner Join T T3
ON T2.node_id2=T3.node_id2
And T1.node_id1=T3.node_id1
And T1.Line<>T3.Line
And T2.Line<>T3.Line
Where T1.Node1<T2.Node1 And T2.Node1<T3.Node2
Order By T1.Node1,
T2.Node1,
T3.Node2;
בסה"כ 91 משולשים, טבין ותקילין, כמו בשני הפוסטים הקודמים.
השלמות
הקורא המקצועי ראוי שישאל את עצמו מדוע הפתרון (החלק שלאחר ה-CTE הרקוסיבי) מתבצע באמצעות Join-ים "רגילים". מדוע לא נשלוף מתוך ה-CTE סט במבנה של טבלת Edge ונתאים לו בעזרת Match את הקודקודים, וכך באמצעות שלושה מופעים של הסט ושלושה מופעים של טבלת Nodes ניצור משולשים;
אלא שכזכור האופרטור Match אינו תומך בסטים שנשלפו מ-CTE...
לא נאמר נואש, ובמקום זאת ניצור טבלת Edge חדשה שלתוכה "נשפוך" את כל הקשתות שנוצרו בעזרת ה-CTE הרקורסיבי, ובעזרתה נמצא שוב את המשולשים:
CREATE TABLE Lines2
(Line int) AS EDGE;
With T As
(SELECT N1.Node Node1,
N1.$node_id node_id1,
N2.Node Node2,
N2.$node_id node_id2,
L.Line,
1 Lvl,
Cast(Concat(N1.Node,',',N2.Node) As Varchar(Max)) Nodes
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)
Union All
SELECT T.Node1,
T.node_id1,
Iif(T.node_id2=T1.node_id1,T1.Node2,T1.Node1),
Iif(T.node_id2=T1.node_id1,T1.node_id2,T1.node_id1),
T.Line,
T.Lvl+1,
Concat(T.Nodes,',',Iif(T.node_id2=T1.node_id1,T1.Node2,T1.Node1))
From T
Inner Join (SELECT N1.Node Node1,
N1.$node_id node_id1,
N2.Node Node2,
N2.$node_id node_id2,
L.Line
FROM Nodes N1, Nodes N2, Lines L
WHERE MATCH(N1-(L)->N2)) T1
On T.Line=T1.Line
And ((T.node_id2=T1.node_id1 And Concat(',',T.Nodes,',') Not Like Concat('%,',T1.Node2,',%')) Or (T.node_id2=T1.node_id2 And Concat(',',T.Nodes,',') Not Like Concat('%,',T1.Node1,',%'))))
Insert
Into Lines2
Select node_id1 [$from_id],
node_id2 [$to_id],
Line
From T;
והמשולשים:
Select N1.Node,
N2.Node,
N3.Node
FROM Nodes N1, Nodes N2, Nodes N3, Lines2 L1, Lines2 L2, Lines2 L3
WHERE MATCH(N1-(L1)->N2-(L2)->N3)
And Match(N1-(L3)->N3)
And L1.Line<>L2.Line
And L2.Line<>L3.Line
And L1.Line<>L3.Line
And N1.Node<N2.Node
And N2.Node<N3.Node
Order By N1.Node,
N2.Node,
N3.Node;
