content top
GraphDB ב-SQL Server 2017

GraphDB ב-SQL Server 2017

גרסת 2017 שבשעת כתיבת שורות אלו היא עדיין גרסת CTP (מה שנקרא בדרך כלל – גרסת בטה), תומכת ב-GraphDB, וב-SQL Azure הטכנולוגיה כבר זמינה לשימוש.

טכנולוגיה זו שכוללת אובייקטים חדשים מחד, והרחבה של שפת TSQL עבורם; נועדה לטפל ברשתות, או ליתר דיוק – במידע לגבי רשתות.

מבוא קצרצר לתורת הרשתות

image

זו רשת (Graph): אוסף של קודקודים (Nodes) וקשתות (Edges), כשכל קשת מחברת בין שני קודקודים.
הרשת יכולה לייצג אנשים וההיכרויות בינם, תחנות רכבת המקושרות בינן, קשרים בין אטומים במולקולות, ועוד.
במקרה זה הקשתות הן סימטריות: המרחק מתחנת האוניברסיטה לתחנת הרצליה היא כמרחק מתחנת הרצליה לתחנת האוניברסיטה, ואם אני חבר של יוסי בפייסבוק – יוסי הוא גם חבר שלי..

מקרה מיוחד הוא רשת מכוונת, בה יש לקשתות כיוון ומשמעות, והן אינן סימטריות:

image

זה המצב בקשרי משפחה (נכון שאם צילי אחות של גילי אז גילי אחות של צילי, אך זה לא נכון לגבי יחסי הורה-בן, דודה-אחיין וכו’), קווי טיסות, תרשימי זרימה ועוד.

עוד מקרה מיוחד של רשת הוא עץ, למשל עץ מכוון:

image

דוגמאות: מבנה של אינדקס BTree, יחסים היררכיים בארגון, עץ קבלת החלטות..
אם מסדרים את הגרף יפה יותר – זה יראה כמו עץ כשכיוון הזרימה הוא מלמעלה למטה (או להיפך), אבל עקרונית אין עם זה כל בעייה.

ניתן לדבר גם על עצים לא מכוונים.

יצוג של רשתות בדטבייס רלציוני

נתחיל מעצים, ונציין שכעקרון – אנחנו מדברים על רשתות ועצים מכוונים, ומי שרוצה לא מכוון – יצטרך למצוא פתרון שיכפיל את הקשתות כך שלכל קשת מ-X ל-Y תתוסף קשת מ-Y ל-X.

עצים מיוצגים על ידי יחסי 1:N (אחת לרבים, רצוי תוך הגדרת Foreign Key), למשל – ניקח טבלת הזמנות וטבלת שורות הזמנה. לכל הזמנה מספר שורות, אך לכל שורה – הזמנה אחת בלבד:

image

היכן העץ? לא עץ אחד, אלא שלושה עצים בני קומה אחת בלבד.. היה ראוי לקרוא לזה עציץ או אולי עשב חד שנתי, ולא עץ; אבל מבחינת ההגדרות אלו עצים כשרים למהדרין.
ניתן היה להפוך את העצים ליותר “מעניינים” אם היינו מוסיפים, למשל, את טבלת הלקוחות, שמקיימת יחסי 1:N עם טבלת ההזמנות עצמה, כך שלכל לקוח מספר הזמנות ולכל הזמנה מספר שורות; אלא שהעצים היו נשארים אחידים – בני 2 קומות בדיוק..
עצים “מעניינים” הצומחים פרא נקבל במקרה של טבלאות הפונות לעצמן, למשל – טבלת עובדים בה כל עובד כפוף למנהל ישיר שגם הוא עצמו מיוצג בטבלה. מה שנקרא- מערכת היררכית. דוגמאות נוספות – מערכת שיווק רב שכבתית בה כל לקוח הוא גם מוכר שגוייס על ידי מוכר אחר, וכל מגייס מקבל אחוזים על המכירות של מגוייסיו הישירים והעקיפים, או מבנה אירגוני בו להנהלה כפופות יחידות, לכל אחת תתי יחידות וכך הלאה.

מה לגבי רשתות? רשת שאינה עץ נקבל במקרה של יחסי N:N (רבים לרבים), שבמערכת רלציונית נוצרת באמצעות טבלת ביניים (רצוי תוך הגדרת Foreign Keys בינה לבין שתי הטבלאות); למשל- אם נוסיף לתרשים של ההזמנות ושורות ההזמנה גם את טבלת המוצרים; ואז בכל הזמנה יהיו מספר מוצרים, לכל מוצר יהיו מספר הזמנות, וטבלת הביניים תהיה טבלת שורות ההזמנה עצמה:

image

בדרך כלל שני עמודות ה-Foreign Key בטבלת הביניים (שורות ההזמנה) אמורים להיות מפתח ראשי, אך זה אינו הכרחי, ובדרך כלל נמצא עמודות נוספות (למשל- כמות, במקרה זה).
קיבלנו שוב רשת “משעממת” בת שני שלבים, ולא אחת סבוכה ו”מעניינת”. רשת “מעניינת” נקבל כאשר טבלת הביניים היא בין הטבלה לעצמה (כלומר- אותה טבלה בשני הצדדים).
דוגמאות – רשת חברתית כדוגמת Lnkedin או Facebook בה לכל אחד יש הרבה חברים (שימו לב – שבמקרה זה הרשת אינה מכוונת!), או אולי עץ מוצר הכולל מוצרי ביניים ולא רק חומרי גלם ותוצרת גמורה, ואז כל מוצר ביניים יכול להיות מורכב מחומרי גלם או ממוצרי ביניים נוספים, ויכול לשמש למוצרים מוגמרים או למוצרי ביניים אחרים.

טכנולוגיית GraphDB

אקדים ואציין שהטכנולוגייה החדשה מעניינת בעיקר ביחס לרשתות, ובזה אתמקד: במקום טבלת הביניים הרלציונית, ניצור טבלת ביניים תומכת GraphDB. במקרה של עצים אין מלכתחילה צורך בטבלאות ביניים, ומיותר להשמש בהן באופן מאולץ.

המצרכים: GraphDB מפנק אותנו בני סוגי טבלאות חדשים- Node (קודקוד) ו-Edge (קשת) שנועדה לקשר שני קודקודים, והיא מחליפה את טבלת הביניים הרלציונית.
החידוש העיקרי – טבלת הביניים Edge יכולה לקשר בין טבלאות Node שונות ללא הגבלה.
למשל- נניח שטבלת Node אחת היא טבלת משתמשים, טבלת Node שנייה היא טבלת פוסטים, טבלת ה-Edge היא טבלת Like (“חיבובית” בעברית), ואז כל שורה בה מציינת Like של משתמש לפוסט.
אלא שאותה טבלה יכולה לשמש גם ל-Like של משתמשים לשירים (מתוך טבלת Node של שירים), או Like לבתי עסק (מתוך טבלת Node של בתי עסק), ואפילו Like של משתמשים למשתמשים אחרים (כלומר- טבלת ה-Node של המשתמשים בשני הצדדים).
ניתן להוסיף כמובן טבלאות Edge נוספות שאינן Like, למשל – טבלת Edge המציינת מי בן/ת של מי וכך לבנות עצי משפחה (עצי משפחה הם רשתות ולא עצים..), או מי (=Node) קנה ומתי (=Edge) באיזה בית עסק (=Node) וכך הלאה.
לשם כל זאת – לכל טבלת Node נוצרת אוטומטית עמודת (NVarchar(1000 המשמשת כמזהה יחודי ללא קשר למפתח הראשי שנבחר לה, ובה נשמר json המציין את סוג הטבלה (Node), שמה, ומספר השורה;
ולכל טבלת Edge שתי עמודות (NVarchar(1000 המחזיקות את ה-json-ים של שורות ה-Edge, ועמודת (NVarchar(1000 עם ה-json של השורה עצמה שבטבלת ה-Edge.
אם לדייק, המידע נשמר ככל הנראה בעמודות מערכת נסתרות:

  • בטבלת Node יש עמודת BigInt נסתרת בשם graph_id הכוללת מספר רץ, ועמודת node_id$ גלויה הכוללת יצוג json-י של סוג הטבלה, הסכימה, השם, וערך ה-grapg_id.
  • בטבלת Edge יש עמודות graph_id ו-node_id$ כמו ב-Node, ובנוסף שתי שלשות עמודות לכל אחד מה-Nodes המקושרים (כשרק השלישי- היצוג ה-json-י) גלוי:
    from_bj_id, from_id, from_id$ ל-Node הראשון,
    ו-to_bj_id, to_id, to_id$ ל-Node השני.

דוגמה

לאחר כל כך הרבה דיבורים הגיע הזמן לקצת קוד,
ואז מתחילים לדבר על הקוד..
ניצור טבלת עובדים הירארכית (לכל עובד מצויין למי הוא כפוף) מסוג Node (חלק מהגדרת הטבלה!):

Create    Table T_Employees

        (Employee Varchar(20) Primary Key Clustered,

        Manager Varchar(20) Null,

        Constraint [FK_T_Employees] Foreign Key(Manager) References T_Employees(Employee)) As Node;

Go


Insert

Into    T_Employees

Values    ('Avigail',Null),

        ('Beni','Avigail'),

        ('Carmal','Avigail'),

        ('Dalit','Carmal'),

        ('Eli','Dalit'),

        ('Gila','Eli'),

        ('Israel','Eli');

Go

מכיוון שהמבנה ההיררכי הוא עץ, ויתרתי על השימוש בתשתית ה-GraphDB במקרה זה, אבל הטבלה עצמה תשמש ליצירת קשרים אחרים בין העובדים (חברויות למשל), ובין העובדים לאובייקטים אחרים (למשל – מה יודע כל עובד).

מה בטבלה?

Select * From T_Employees;

Exec sp_help T_Employees;

image

בשליפה מהטבלה ניתן לראות את העמודה השמאלית (המחושבת) node_id$ הכוללת את סוג הטבלה, הסכימה, שם הטבלה, והמספר הרץ של השורה. נכון ששם העמודה כולל ספח הקסדצימלי ארוך, אבל ניתן לפנות אליה בתור node_id$.

sp_help חושף את המבנה הסמוי של הטבלה: עמודת graph_id סמוייה מסוג BigInt שכוללת את המספור הרץ, ועמודת node_id$ הגלוייה המציגה את המידע בתור json.

כעת ניצור טבלת Edge שתייצג את הקשרים בין העובדים – האם הם חברים או קרובי משפחה (היחסים הפורמליים ההיררכיים כבר כלולים בטבלת העובדים):

Create    Table T_Relations(Type Varchar(20)) As Edge;


Create Unique Index Idx_T_Relations

        On T_Relations($from_id,$to_id,Type);


Insert

Into    T_Relations

Select    E1.$node_id,

        E2.$node_id,

        K.Type

From    (Values    ('Avigail','Eli','Friends'),

                ('Avigail','Gila','Friends'),

                ('Avigail','Israel','Family'),

                ('Carmel','Avigail','Friends'),

                ('Dalit','Eli','Friends'),

                ('Dalit','Gila','Friends'),

                ('Dalit','Israel','Friends'),

                ('Israel','Gila','Family')) K(Employee1,Employee2,Type)

Inner Join T_Employees E1

        On K.Employee1=E1.Employee

Inner Join T_Employees E2

        On K.Employee2=E2.Employee;

לכאורה רק עמודה אחת בטבלה (Type המציין האם הם חברים או קרובי משפחה), אך כפי שנקרה בהמשך – הגדרתה כ-Edge יוצרת תשתית לקישור ערכים מטבלאות Node), וגם עליה ניתן לוותר: אין מניעה ליצור טבלה כך- ;Create Table T_MyTbl As Edge.

נעיין:

Select * From T_Relations;

Exec sp_help T_Relations;

image

בטבלה רואים שלוש עמודות json:

  1. ה-json של השורה בטבלה זו עצמה (טבלת T_Relations)
  2. ה-Json של שורת ה-from בטבלת ה-Node
  3. ה-json של שורת ה-to בטבלת ה-Node

(במקרה זה ה-from וה-to הם אותה טבלה אך זה אינו הכרחי)

במבנה הטבלה ניתן לראות את שתי עמודות הטבלה עצמה (בירוק),

שלוש עמודות ה-from (בתכלת),

ושלוש עמודות ה-to (בצהוב);

כאשר רק עמודת ה-json גלויה.

כיצד מתחקרים את טבלאות ה-GraphDB?

TSQL שודרגה באופרטור חדש – Match:

Select    E1.Employee,

        T_Relations.Type,

        E2.Employee

From    T_Employees E1, T_Relations, T_Employees E2

Where    Match (E1-(T_Relations)->E2);

image

כלומר, אופרטור שאינו משדך בין שתי טבלאות כמו ה-Join-ים למיניהם, אלא בין שלוש: שני Nodes ו-Edge אחד בינהם.

ככל שהשאילתות נעשות מורכבות יותר, כך מתחוור יתרונו של הסינטקס החדש, למשל: אנחנו מחפשים עובדים שחבריהם קרובי משפחה (למשל- יוסי חבר של צילי וגילי, ושתיהן קרובות משפחה):

Select    E1.Employee,

        R12.Type,

        E2.Employee,

        R13.Type,

        E3.Employee,

        R23.Type

From    T_Employees E1, T_Relations R12, T_Employees E2,

                        T_Relations R13, T_Employees E3,

                        T_Relations R23

Where    Match (E1-(R12)->E2) And R12.Type='Friends'

        And Match (E1-(R13)->E3) And R13.Type='Friends'

        And Match (E2-(R23)->E3) And R23.Type='Family';

image

דלית חברה של ישראל וגילה, ושניהם קרובי משפחה.

לו היינו מנסים לקבל את זה ב-TSQL-ית רלציונית זה היה נראה כך:

Select    E1.Employee,

        R12.Type,

        E2.Employee,

        R13.Type,

        E3.Employee,

        R23.Type

From    T_Employees E1

Inner Join T_Relations R12

        On E1.$node_id=R12.$from_id

Inner Join T_Employees E2

        On R12.$to_id=E2.$node_id

Inner Join T_Relations R13

        On E1.$node_id=R13.$from_id

Inner Join T_Employees E3

        On R13.$to_id=E3.$node_id

Inner Join T_Relations R23

        On E2.$node_id=R23.$from_id

        And R23.$to_id=E3.$node_id

Where    R12.Type='Friends'

        And R13.Type='Friends'

        And R23.Type='Family';

הפלט המתקבל היה אותו פלט ואפילו ה-Execution Plan היה זהה (לפחות אצלי),

אבל הקוד היה הרבה פחות קריא,

וכל זה בשפת SQL שמטבעה כשפה דקלרטיבית היא קריאה.

מה לגבי תחקור רשת הקשרים בין העובדים?

כרגע המערכת אינה תומכת ברקורסיה, ולא נצליח להשתמש באופרטור Match ב-CTE רקורסיבי (בחלק הרקורסיבי של ה-CTE נקבל – Derived tables are not supported in MATCH clauses).

בנוסף, התשתית תומכת ברשתות מכוונות, וכדי לאפשר רשתות לא מכוונות יש ליצור לכל קשת – העתק הפוך: אם דלית חברה של ישראל – ישראל גם חבר של דלית, ואם ישראל קרוב משםחה של גלית – גלית קרובת משפחה של ישראל..

בקיצור, כדי לאפשר CTE רקורסיבי ולהפוך את הרשת ללא מכוונת, ניצור קודם כל סט “מנורמל” של T_Relations, ועליו נבסס את השליפה הרקורסיבית. בנוסף, כדי למנוע לולאות אינסופיות, נשרשר רק את מי שטרם שורשר. קצת מסובך, אך אנחנו איננו נופלים ברוחנו, ונתחקר לעומק את כל מערכת הקשרים של אביגיל:

   1: With V As

   2: (Select    E1.Employee EmployeeF,

   3:         E2.Employee EmployeeT

   4: From    T_Employees E1,

   5:         T_Relations R,

   6:         T_Employees E2

   7: Where    Match(E1<-(R)-E2)

   8: Union All

   9: Select    E1.Employee,

  10:         E2.Employee

  11: From    T_Employees E1,

  12:         T_Relations R,

  13:         T_Employees E2

  14: Where    Match(E1-(R)->E2)),

  15: T As

  16: (Select    EmployeeF Original,

  17:         EmployeeF,

  18:         EmployeeT,

  19:         Cast(Concat(EmployeeF,',',EmployeeT) As Varchar(Max)) Path

  20: From    V

  21: Where    EmployeeF='Avigail'

  22: Union All

  23: Select    T.Original,

  24:         R.EmployeeF,

  25:         R.EmployeeT,

  26:         Cast(Concat(T.Path,',',R.EmployeeT) As Varchar(Max)) Path

  27: From    T

  28: Inner Join V R

  29:         On T.EmployeeT=R.EmployeeF

  30: Where    Concat(',',T.Path,',') Not Like Concat('%,',R.EmployeeT,',%'))

  31: Select    *

  32: From    T;

  • שורות 1-14: טבלת T_Relations מנורמלת ולא מכוונת. שימו לב שבמקום להחליף את E1.Employee ואת E2.Employee במקומות, אפשר להפוך את כיוון התנאים באופרטור ה-Match.
  • שורות 15-30: השליפה הרקורסיבית מתוך הנ”ל, כאשר ב-Where הרקורסיבי מוודאים שהעובד אינו בפנים עדיין (אחרת נקלע חלילה ללואה אינסופית).

מה עוד באמתחתנו?

בואו נוסיף עוד קצת תוכן לדטבייס.

נתחיל מתחומי ידע טכנולוגיים: העובדים הנ”ל מועסקים בהייטק, ורוצים לדעת מה כל אחד יודע.

ניצור קודם כל טבלת Node טכנולוגיות ונמלא אותה בנתונים:

Create    Table T_Technologies

        (Technology Varchar(20) Primary Key Clustered) As Node;


Insert

Into    T_Technologies(Technology)

Values    ('SQL Server'),

        ('Azure'),

        ('Big Data'),

        ('C#'),

        ('PowerShell'),

        ('Python');

עובדים אמורים גם לדעת שפות, ולשם כך נשתמש ברשימת השפות הנתמכות של SQL Server לאכלוס טבלת Nodes:

   1: Create    Table T_Languages

   2:         (Language Varchar(20) Primary Key Clustered) As Node;

   3:

   4: Insert

   5: Into    T_Languages

   6: Select    alias

   7: From    sys.syslanguages;

image

כעת ניצור טבלת Edge שתקשר בין עובדים לטכנולוגיות:

Create    Table T_Knows As Edge;


Insert

Into    T_Knows

Select    E.$node_id,

        T.$node_id

From    (Values    ('Avigail','SQL Server'),

                ('Avigail','C#'),

                ('Beni','SQL Server'),

                ('Carmel','SQL Server'),

                ('Carmel','Azure'),

                ('Carmel','C#'),

                ('Dalit','SQL Server'),

                ('Eli','SQL Server'),

                ('Gila','SQL Server'),

                ('Gila','Azure'),

                ('Gila','C#'),

                ('Gila','Python'),

                ('Israel','SQL Server'),

                ('Israel','Azure'),

                ('Israel','PowerShell')) K(Employee,Technology)

Inner Join T_Employees E

        On K.Employee=E.Employee

Inner Join T_Technologies T

        On K.Technology=T.Technology;

אחד היתרונות החשובים של GraphDB הוא שאותה טבלה יכולה לשמש גם לידיעת שפות:

Insert

Into    T_Knows

Select    E.$node_id,

        L.$node_id

From    (Values    ('Avigail','English'),

                ('Avigail','French'),

                ('Beni','English'),

                ('Carmel','English'),

                ('Carmel','Spanish'),

                ('Carmel','Russian'),

                ('Dalit','English'),

                ('Eli','English'),

                ('Gila','English'),

                ('Gila','Spanish'),

                ('Gila','Polish'),

                ('Gila','German'),

                ('Israel','English'),

                ('Israel','French'),

                ('Israel','Spanish')) K(Employee,Language)

Inner Join T_Employees E

        On K.Employee=E.Employee

Inner Join T_Languages L

        On K.Language=L.Language;

נדלג באלגנטיות מעל הדוגמאות הבאךיות המבקשות (מי יודע אנגלית? מי יודע SQL Server?),

ונפנה לשאלה המאתגרת – מי יודע SQL Server ו-#C ומדבר אנגלית?

Select    E.Employee,

        T1.Technology,

        T2.Technology,

        L.Language

From    T_Employees E, T_Knows K1,  T_Technologies T1,

                        T_Knows K2,  T_Technologies T2,

                        T_Knows K3, T_Languages L

Where    Match (E-(K1)->T1)

        And Match (E-(K2)->T2)

        And Match (E-(K3)->L)

        And T1.Technology='SQL Server'

        And T2.Technology='C#'

        And L.Language='English';

image

השליפה מעט מורכבת מכיוון שהבקשה מורכבת. לו היינו מנסים ב-TSQL-ית סטנדרטית היא לא הייתה הרבה יותר מסובכת, אבל זאת לאור תשתית ה-GraphDB שמאפשרת ליצור את כל הקשרים בטבלה אחת. אני משער שלו היינו מנהלים את הכל באופן רלציוני – השליפה הייתה יותר מורכבת, ובוודאי – פחות אינטואיטיבית.

סיכום

שתי הבשורות הגדולות עד כה:

  • טבלאות Node ו-Edge, כאשר Edge מקשרת שני Nodes ומאפשרת ליצור יחס של “רבים לרבים” (בשפה רלציונית), כשהחידוש – אותה טבלה משמשת לקישור טבלאות שונות.
  • סינטקס משופר של TSQL שמאפשר לתחקר את המידע בצורה אינטואיטיבית יותר (באמצעות האופרטור Match).

בעתיד יתווספו, כך מקווים, יכולות נוספות; ומבחינתי – תמיכה משופרת ברקורסיות: אמרתם רשתות אמרתם רקורסיות.

שתי הערות טכניות:

  • המערכת אינה תומכת ב-Collation מסוג Bin. כרגע יש להשתמש ב-Collations סטנדרטיים.
  • המערכת אינה מונעת שימוש ב-Edge לקישור Edges (במקום Nodes), אולם השליפות אינן נתמכות.. בקיצור – נכון לעכשיו זו פירצה שיש לסגור.

תגובה אחת על “GraphDB ב-SQL Server 2017”

  1. מאת אלכס פרידמן:

    מעניין מאד, תודה!

כתיבת תגובה

האימייל לא יוצג באתר. (*) שדות חובה מסומנים

three × 1 =