#databases

Design Theory for Relational Databases

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

Functional Dependencies

אילוץ פונקציונלי $F D$ על יחס $R$ (תזכורת, יחס הוא אוסף של מידע שמסודר באופן כלשהו, במסד נתונים רלציוני זה יהיה בטבלה, כמו כן היחס בנוי באמצעות סכמה)
הוא הצהרה מהצורה-

אם שתי tuples של $R$ מסכימים על כל הערכים $A_{1}, \dots, A_{n}$ (tuple=רשומה בטבלה), כלומר לשתי רשומות יש בידיוק את הערכים האלו לפי הסדר של הסכמה, אזי הם חייבים להסכים על הערכים $B_{1}, B_{2} \dots, B_{m}$ ״.

במילים אחרות אם לשתי records בטבלה יש את אותם ערכים בסדר מסויים בסכמה אז ישנה מוסכמה שיהיו להם ערכים מסויים זהים.
בנוסח פורמלי

A_{1}, A_{2}, \dots, A_{n} \to B_{1}, B_{2} \dots, B_{m}

ונאמר גם ש

A_{1}, A_{2}, \dots, A_{n} functionally determine B_{1}, B_{2} \dots, B_{m}

Pasted image 20230101165631.png|300

נגיד ש $R$ מספק $F D$ אם לכל מופע של יחס $R$ אותו $F D$ יהיה נכון לכל מופע שכזה. נשים לב שזה בעצם הפעלה של איזשהו אילוץ על הטבלה.
כמו כן נשים לב שה FD הבא

A_{1}, A_{2}, \dots, A_{n} \to B_{1}, B_{2} \dots, B_{m}

שקול לקבוצת ה FD הבאים

\begin{matrix} A_{1} A_{2} \dots A_{n} \to B_{1} \\ A_{1} A_{2} \dots A_{n} \to B_{2} \\ A_{1} A_{2} \dots A_{n} \to B_{3} \\ ⋮ \\ A_{1} A_{2} \dots A_{n} \to B_{m} \end{matrix}

נביט בדוגמה הבאה:
Pasted image 20230101170807.png
הסכמה היא Movies1(title,year,lenght,genre, studioName, starName) .
נשים לב שכל שהטבלה הזאת ״עושה יותר מדי״ היא מחזיקה מידע שיכול להיות שייך לשלוש טבלאות אחרות Movies, Studio , StarsIn .
בהמשך נראה יותר למה הסכמה הנ״ל לא טובה בכלל. אבל כדי להבין למה הסכמה הזאת לא טובה ומה שגוי בעיצוב שלה, עלינו לקבוע מהי התלות הפונקציונלית שמחזיקה את המידע. נוכל לטעון שהתלות הפונקציונלית הבאה תקינה

title year \to length genre studioName

כלומר באופן לא פורמלי, התלות אומרת שאם לשתי מופעים יש את אותה שנה ואותה כותרת, יש להם גם את אותו אורך של סרט, ז׳אנר ושם סטודיו.

נשים לב אבל ש

title year \to starName

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

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

מפתחות

נאמר שקבוצה של ערך או מספר ערכים ${A_{1}, A_{2}, \dots, A_{n}}$ הוא מפתח ליחס $R$ אם

הערכים האלה קובעים באמצעות FD את כל הערכים הערכים של היחס. כלומר, כל שתי מופעים שונים של היחס לא מחליטים באופן מלא על הערכים האלו.
לא קיימת תת קבוצה של קבוצת הערכים הנ״ל שקובעת את כל שאר הערכים של $R$ . כלומר מפתח הוא הקבוצה המינימלית ביותר שמכריעה על שאר הערכים.

כאשר מפתח מחזיר ערך יחיד $A$ נסמן את המפתח כולו כ $A$ ולא כ ${A}$ .

בהקשר לטבלה למעלה נוכל להגיד ש ${title, year, starName}$ יהווה מפתח עבור הטבלה Movie1 .לא בעייה להוכיח את זה שכן כבר אמרנו ש כותרת ושנה קובעים את כל הפרמטרים האחרים חוץ משם השחקן. לאחר שהוספנו אותו ברור שיש הכרעה על כל שאר הערכים של הטבלה.

סופר-מפתחות

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

חוקים של תלות פונקציונלית

נדבר על חוקים של תלות פונקציונלית שיעזרו לנו לנתח איזה עוד תלויות יש לטבלה בהינתן תלות קיימת.

טרנזיטיביות:

A_{1} A_{2} A_{3} \dots A_{n} \to B_{1} B_{2} B_{3} \dots B_{m}

וגם

B_{1} B_{2} B_{3} \dots B_{m} \to C_{1} C_{2} C_{3} \dots C_{k}

אז

A_{1} A_{2} A_{3} \dots A_{n} \to C_{1} C_{2} C_{3} \dots C_{k}

splitting rule:
כפי שרשמנו למעל

A_{1}, A_{2}, \dots, A_{n} \to B_{1}, B_{2} \dots, B_{m}

שקול ל:

\forall_{i \in [m]} : A_{1}, A_{2}, \dots, A_{n} \to B_{i}

טירוויאליות:

\forall_{i \in [n]} : A_{1}, A_{2}, \dots, A_{n} \to A_{i}

\forall_{i \in [n]} : A_{1}, A_{2}, \dots, A_{n} \to ֿ A_{1} A_{2} A_{3} \dots A_{m} where: 1 \leq m \leq n

ישנו מצב ביניים שבו חלק אבל לא כל התכונות בצד ימין הם גם בצד שמאל. התלות הזאת אינה טריווויאלית אבל ניתן לפשט אותה על ידי הסרה מצד ימין את כל התכונות שמופיעול בצד שמאל כמו בתמונה למטה. בפשטות נוכל להגיד ש $A_{1} \dots A_{n} \to B_{1} \dots B_{m}$ שקול ל $A_{1} \dots A_{n} \to C_{1} \dots C_{k}$ כאשר $C$ זה כל ה $B$ שלא נמצאים גם ב $A$ .
Pasted image 20230101195213.png|300

השאווה בין תלויות:
נאמר ששתי קבוצות של $F D$ , $S, T$ שקולות אם כל המופעים של הטבלה שמספקים את $S$ שקולות לכל המופעים של הטבלה שמספקים את $T$ .
באופן כללי יותר נאמר ש קבוצה של $F D$ נסמנה $S$ עוקבת אחרי $T$ אם כל מופע של טבלה שמספק את $T$ יספק גם את $S$ .

טרמינולוגיה :

מופע של טבלה או relation instance מייצגת מעין snapshot של הטבלה בנקודת זמן מסויימת.
tuple הוא ערך כלשהו בטבלה כלומר record או שורה בטבלה.

computing the closure of attributes

נניח ש ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$ הוא קבוצה שלתכונות ו $S$ היא קבוצה של תלויות פונקציונליות .
נגדיר את ה closure של ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$ תחת $S$ כקבוצה התכונות $B$ כך שכל טבלה שמספקת את $S$ גם מספקת את

A_{1} A_{2} \dots A_{n} \to B

כלומר התלות הנ״ל עוקבת אחרי $S$ .

נסמן את הסגור של ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$ תחת $S$ כ

{A_{1}, A_{2}, A_{3} \dots, A_{n}}^{+}

נשים לב שיתקיים תמיד

{A_{1}, A_{2}, A_{3} \dots, A_{n}} \subseteq {A_{1}, A_{2}, A_{3} \dots, A_{n}}^{+}

מתכונת הטריוויאליות.

חישוב של closure:
בהנתן ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$ ו $S$ נרצה לחשב את ${A_{1}, A_{2}, A_{3} \dots, A_{n}}^{+}$

אם נחוץ, פצל את כל האיברים ב $S$ כך שכל $F D$ יהיה רק עם ערך אחד מימין.
נגדיר את $X$ להיות ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$
הוסף ל $X$ את כל $C$ כאשר יתקיים שב $S$ נמצא $B_{1}, B_{2} \dots, B_{m} \to C$ . כך שמתקיים

{B_{1}, B_{2}, \dots B_{m}} \subseteq X \land C \notin X

החזר את $X$ כאשר לא ניתן לבצע עוד את 3.

Pasted image 20230101200406.png|300
התמונה מסבירה את הליך החישוב, בהתחלה אנחנו מוסיפים את כל הפרמטרים עצמם מהכלל הטירוויאלי, לאחר מכן מוסיפים את צד ימין של $F D$ מיד לאחר שהוספנו את צד שמאל שלו ולאחר מכן שוב מרחיבים את החיפוש. בעצם זה מעין סגור טרנזיטיבי של קבוצת התכונות הזאת.

נתבונן על דוגמה:
נניח שיש טבלה עם התכונות $A, B, C, D, E, F$ ונניח שיש לה את ה FD הבאים

A B \to C, B C \to A D, D \to E, C F \to B

נרצה לחשב את הסגור של ${A, B}$
אם כן אנחנו יודעים ש $A, B$ כבר שייכים לסגור,
כעת נרצה לקחת את

B C \to A D

ולפצל אותו ל

B C \to A, B C \to D

כעת $X = {A, B}$ .
באיטרציה הבאה נשים לב ש $A B \to C$ שייך לקבוצת ה FD שהגדנו ולכן $C$ ייכנס ל $X$ .
לאחר מכן נראה ש $B C \to D, D \to E$ מתקיימים אז באיטרצייה הבאה נכניס את $D$ ולאחר מכן נכניס את $E$ וזהו.
אם כן הגענו למסקנה ש

X = {A, B}^{+} = {A, B, C, D, E}

בפסודו זה ייראה כך

closure(X={A1,A2,...,An},F)
	while (exists rule B1,B2,...,Bm in F such that:
		 {B1,B2,...Bm} subset of X AND C not in X) :
		add C to X
	return X

ההוכחה של זה לא מסובכת אך יכולה להיות ארוכה, צריך להוכיח ש
א) האלגוריתם לא מוסיף תכונות שלא מתאימות כלומר שאכן $A_{1}, A_{2} \dots A_{n} \to B$ הוא יחס נכון מהתכונות שלמדנו והוא מסופק על ידי טבלה שמספקת את כל מי שב $S$
הוכחה באינדוקצייה על מספר הפעמים שהגדלנו את $X$ . כלומר לאחר כל צעד אם ניקח $D \in X$ יתקיים ש $A_{1} \dots A_{n} \to D$ הוא אכן $F D$ תקין.

בסיס- כאשר לא עשינו אף צעד, במצב זה עבור $D \in X$ יתקיים ש $D$ הוא אחד מהתכונות ומהתכונה הטריוויאלית מתקיים הדרוש.
צעד- נניח שהוספנו את $D$ לאחר שמצאנו $B_{1} B_{2} \dots B_{m} \to D$ אם כן אנחנו יודעים מהנחת האינדוקצייה ש

A_{1} A_{2} \dots A_{n} \to B_{1} B_{2} \dots B_{m}

מסופק על ידי $R$ . ולכן אוטומטי נובע מתכונת הטרנזיטיביות הדרוש.

ב) צריך להוכיח שהאלגוריתם לא נכשל בלבנות סגור שעוקב אחרי $S$ .
נניח ש $A_{1} A_{2} \dots A_{n} \to B$ הוא תלות פונקציונלית שהאלגוריתם קבע שהיא אינה עוקבת אחרי $S$ .
כלומר $B$ לא שייך לסגור של התכונות תחת $S$ . נרצה להראות שאכן התלות הנ״ל באמת לא עוקבת אחרי $S$ . כלומר נרצה להראות שיש לפחות מופע אחד של הטבלה שמספק את $S$ אבל לא מספק את $A_{1} A_{2} \dots A_{n} \to B$ .
נגדיר את המופע הזה כ $I$ ומאוד קל לבנות אותו.
Pasted image 20230101211844.png|300
יש לו רק שתי tuples $t, s$ והם יסיכמו על כל התכונות שבסגור ולא יסכימו על כל מי שלא בסגור.
מכאן קל להוכיח שהמופע הזה עוקב אחרי $S$ מאיך שהאלגוריתם בנוי אבל לא עוקב אחרי $A_{1} A_{2} \dots A_{n} \to B$ שכן $B$ אינו בסגור.

closures and keys

נשים לב ש ${A_{1}, A_{2}, A_{3} \dots, A_{n}}^{+}$ יהווה את קבוצת כל התכונות של טבלה אם ורק אם $A_{1} \dots, A_{n}$ הוא סופר מפתח.
אם כן יש לנו אלגוריתם די פשוט לקביעה האם אוסף של תכונות הוא מפתח:
א) בהינתן ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$ חשב את הסגור שלו.
ב) אם הסגור הוא כל התכונות המשך לסעיף ג , אחרת תחזיר false.
ג) הורד כל פעם תכונה מ ${A_{1}, A_{2}, A_{3} \dots, A_{n}}$ , הפעל את אלגוריתם למציאת סגור ובדוק האם עדיין כל התכונות נשארו, במידה ועבור אחד מהם לא נשארו כל התכונות, החזר false. אם זה מפתח מיד לאחר הורדת התכונה הראשונה אנחנו אמורים לקבל שהסגור לא מכיל את כל תכונות הטבלה.

Closing Sets of Functional Dependencies

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

מסקנה מידית היא ש אין FD טריוויאלי בבסיס מינימלי.

לדוגמה, ניקח את הטבלה $R (A, B, C)$ כך שכל תכונה מספקת את השתיים האחרות כלומר ,

A \to B, A \to C, B \to A, B \to C, C \to A, C \to B

היא כמובן כוללת בתוכה גם את

A B \to C, A C \to B, B C \to A

ואת הטריוויאלים.
בסיס מינימלי לדוגמה במקרה הזה יהיה

{A \to B, B \to C, C \to A}

זה בסיס כיוון שמחוקי הטרנזיטיביות נוכל לקבל את כל הנ״ל כלומר היא שקולה לקבוצת ה FD של R. וגם אם נוריד איבר אחד מהקבוצה זה כבר לא יהיה בסיס כי לא נוכל להסיק מטרנזיטיביות את השקילות. כמו כן סעיף 3 לא רלוונטי כי יש רק איבר אחד בכל צד.

Armstrong’s axioms

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

רפלקסיביות

if {B_{1} \dots, B_{m}} \subseteq {A_{1}, \dots, A_{n}} than A_{1} \dots A_{n} \to B_{1} \dots B_{m}

אוגמנטציה

if A_{1} \dots A_{n} \to B_{1} \dots B_{m} than A_{1} \dots A_{n} C_{1} \dots C_{k} \to B_{1} \dots B_{m} C_{1} \dots C_{k}

ואם יש כפילויות בין $C_{i}, B_{j}$ או עם $A_{i}, C_{t}$ פשוט נשמיט אותם.

טרנזיטיביות

A_{1} A_{2} A_{3} \dots A_{n} \to B_{1} B_{2} B_{3} \dots B_{m}

וגם

B_{1} B_{2} B_{3} \dots B_{m} \to C_{1} C_{2} C_{3} \dots C_{k}

אז

A_{1} A_{2} A_{3} \dots A_{n} \to C_{1} C_{2} C_{3} \dots C_{k}

Projecting Functional Dependencies

באלגברה רלציונית הקרנהם היא פעולה על $R$ יחס מסויים שבפעולה זו משמיטה מספר מסויים של עמודות והיא מסומנת כ $π$ .
אם כן, נרצה שעבור יחס $R$ עם קבוצה של FD שתסומן כ $S$ , כאשר נעשה ״הקרנה״ על $R$ כלומר נחשב $R_{1} = π_{L} (R)$ כאשר $L$ היא קבוצת התכונות שנשארות לאחר ההקרנה. נרצה לדעת איזה מה $F D$ נשארו ב $R 1$ .
את התשובה ניתן להשיג על ידי חישוב ההקרנה של תלות פונקציונלית $S$ שזאת קבוצת כל התלויות ש

עוקבות אחר $S$
מכילות רק תכונות מ $R_{1}$
מאחר ויכולות להיות הרבה תלויות כאלו וברבים מהם גם יתכנו כפילויות, נרצה להקל ולהקטין את הקבוצה הזאת לנוחיותנו.
באופן כללי החישוב הוא אקספוננציאלי למספר התכונות ב $R_{1}$ והאלגוריתם ייראה כך:

קלט: טבלה $R$ וטבלה נוספת $R_{1}$ שמוקרנת מ $R$ וגם $S$ קבוצה של תלויות פונקציונליות ש $R$ מספק
פלט: קבוצת כל התלויות שמוחזקות ב $R_{1}$
א) הגדר $T$ קבוצה ריקה
ב) עבור כל תת קבוצה של תכונות $X \subseteq R_{1}$ , חשב את $X^{+}$ ביחס ל $S$ . פעולה זאת עלולה לכלול תכונות מ $R$ שאינן ב $R_{1}$ ולכן, נוסיף ל $T$ את כל התלויות הלא טריוויאליות $X \to A$ כאשר $A$ נמצאת גם ב $X^{+}$ וגם היא תכונה של $R_{1}$ .
ג) כעת, $T$ הוא בסיס לכל התלויות שמוחזקות ב $R_{1}$ אך הוא לא בהכרח מינימלי. נחשב את הבסיס המינימלי באופן הבא
1) אם קיים FD נסמנו $F \in T$ כך שהוא עוקב אחרי אחד התלויות האחרות ב $T$ , הסר אותו מ $T$
2) יהי $Y \to B$ תלות ב $T$ עם לפחות שתי תכונות ב $Y$ ויהי $Z$ להיות $Y$ עם תכונה אחת שהורדנו. אם $Z \to B$ עוקב אחרי כל התלויות ב $T$ כולל $Y \to B$ אז הסר את $Y \to B$ והחלף ב $Z \to B$ .
3) חזור על כל השלבים הנ״ל בכל הצירופים האפשריים.

נפעיל את האלגוריתם על דוגמה פשוטה להמחשה,
נניח ש $R (A, B, C, D)$ עם התלויות $A \to B, B \to C, C \to D$ . נניח שנרצה להקרין החוצה את התכונה $B$ , כלומר להשאיר את הטבלה $R_{1} (A, C, D)$ . עקרונית, כדי למצוא את התלויות של $R_{1}$ , נרצה לקחת את הסגור של כל תתי הקבוצות של ${A, C, D}$ , ביחס לקבוצת כל התלויות של $R$ . במקרה הזה יש כמה דרכים פשוטות לחישוב שנוכל לעשות

אנחנו יודעים שהקבוצה הריקה וקבוצת כל התכונות לא יכולות להכיל $F D$ אינן טריוויאלית.
אם אנחנו יודעים כבר שהסגור של קבוצה כלשהי $X$ היא כל התכונות, אז אנחנו לא יכולים למצוא תלויות חדשות על ידי supersets של $X$ .
אם כן, נתחיל מכל הסגורים הסינגלטונים ולאחר מכן נעבור לכל הסגורים הכפולים אם יש צורך בכך.
תחילה

{A}^{+} = {A, C, B, D}

ומכאן ש $A \to C, A \to D$ מחזיקים ב $R_{1}$ .
באופן דומה ${C}^{+} = {C, D}$ ו ${D}^{+} = {D}$ .
נשים לב שבגלל שהסגור של $A$ מכיל כבר את כל התכונות, אין מה לחשוב על קבוצה שמכילה את $A$ . אם כן נובע מכך הסגור הכפול היחיד שצריך לקחת בחשבון הוא

{C, D}^{+} = {C, D}

סך הכל גילינו שב $R_{1}$ מתקיים ש $A \to C, A \to D, C \to D$ ונוכל לצמצם את $A \to D$ מטרנזיטיביות ולקבל בסיס מינימלי ${A \to C, C \to D}$