Db סיכום למבחן

- עץ מאוזן (מרחקם של כל העלים מהשורש ‐ זהה) - לכל קודקוד יש לכל היותר d בנים (כאשר d היא דרגת הפיצול) - לכל קודקוד שאינו השורש יש לפחות $\lceil d/2 \rceil$ בנים. - לכל קודקוד (כולל עלים) יש לפחות $\lceil d/2 \rceil - 1$ ערכי חיפוש. - ????????? לכל קודקוד שאינו עלה, שיש לו $k$ בנים - יהיו $k-1$ ערכי חיפוש.

נרצה שכל קודקוד ייכנס בבלוק אחד. ונרצה לנצל כמה שיותר מהבלוק. כלומר נרצה לקיים: $$ (size of pointer) \cdot d + (search key size) \cdot (d - 1) \leq block size $$ וניקח את ה-d המקסימלי שמקיים את זה.

העלות הזאת היא גובה העץ (זה מספר השכבות לא כולל שכבת העלים). אם יש $N$ שורות בטבלה, עלות זו היא: $$ \lceil log_{\lceil \frac{d}{2} \rceil} N \rceil $$

אם עושים Index unique scan רק צריך לקרוא עלה אחד וסיימנו. אחרת צריך לעבור על שכבת העלים ולקרוא כמות עלים מסויימת. נסמן ב-k את כמות הטופלים שמתאימים לשאילה, כלומר השורות בטבלה שעונות על התנאי. מתכונות העץ B+, לכל עלה יש לפחות $\lceil d/2 \rceil - 1$ ערכי חיפוש מתאימים ועל כן k הטופלים יתפרשו על פני כמות העלים הבא: $$ \lceil \frac{k}{\lceil d/2 \rceil - 1} \rceil $$ אם בנוסף נרצה לקרוא את המידע מהדיסק כי הוא לא שמור בעץ נצטרך עוד $$ max(k, totalblocks) $$ קריאות

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

נסמן M היא כמות הבלוקים בזיכרון. נסמן S היחס החיצוני וR היחס הפנימי. נזכור שבאלגוריתם קוראים את היחס החיצוני פעם אחת, ואת היחס הפנימי מספר פעמים עבור כמות החלקים של היחס החיצוני. אז העלות היא: $$ B(S) + B(R) \cdot \lceil \frac{B(S)}{M-2} \rceil $$ בפועל בבחירת תכנית אופטימלית נשתמש בנוסחא הבא: $$ Read(E_S) + Read(E_R) \cdot \lceil \frac{B(E_S)}{M-2} \rceil $$ כאשר Read זו העלות של הקריאה מהדיסק. יכול להיות בלי אינדקס (ואז זה פשוט הגודל של הטבלה), או עם אינקס ופעולת בחירה ואז זה מקטין את זה. ו$B(E_S)$ זה ממש הגודל בבלוקים של מה ששומרים.

- לפעמים משתמשים בסימון V(R,C)=20, זה אומר שיש 20 ערכים שונים לעמודה C בטבלה R. ואז אם רוצים ערך ספציפי מחלקים ב20. - אם אומרים C<145 ולא ידועה התפלגות מחלקים ב-3 (באופן שרירותי) - אם יש שילוב AND של שני תנאים אז מחלקים בשני הדברים. - אם יש שילוב OR נגיד A = ’a’ OR B = ’b’ אז הנוסחא היא: $$ T(R) \cdot (1-(1-\frac{1}{V(R,A)}) \cdot (1 - \frac{1}{V(R,B)})) $$ - אם יש JOIN נגיד SELECT * FROM R, S WHERE R.A = S.A אז הנוסחא היא: $$ \frac{T(R) \cdot T(S)}{max{V(R,A),V(S,A)}} $$ - ואם נגיד מוסיפים לJoin גם תנאי אז פשוט מחלקים. - בנוסף אם בJOIN יש מפתח אז V הוא פשוט כל השורות ואז הגודל יוצא כמות השורות באחת הטבלאות.

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

מתחילים עם קבוצת שדות שהיא כל R ולכל שדה נבדוק האם הוא מיותר כלומר האם אפשר לגרור אותו משאר השדות. אם כן נוציא אותו ונעבור לשדה הבא (בשדה הבא לא נשתמש בו ישר).

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

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

- יוצרים טבלה שבה כל שורה היא תת יחס וכל עמודה היא שדה - ממלאים את הטבלה ב-$a$ ו-$b$. - כל עוד יש שורות בטבלה שסותרות תלות פונקציונלית, נתקן אותן. (a מנצח את b) - לבסוף, אם קיימת שורה שמכילה רק a-ים הפירוק הוא ללא אובדן! - נשים לב כי אם לא קיימת שורה קיבלנו דוגמא נגדית, כלומר מופע של R שמקיים את התלויות ושהפירוק שלו הוא עם אובדן!

- לכל תלות ב-$F$ מהסוג X → Y, מחשבים את מה שנובע מ-X בפירוק. - נשים לב שאם יש תלות ששני הצדדים שלה מוכלים בתת-סכימה, היא בבירור משתמרת! - אחרת, מאתחלים: $$ Z := X $$ - ואז רצים בלולאה ועוברים על תתי היחסים (יכול להיות שנצטרך לעבור עליהם יותר מפעם אחת!) ומבצעים: $$ Z:= Z \cup ((Z \cap R_i)^+ \cap R_i) $$ חישוב הסגור הוא למעשה על פי התלויות ב-$F$ המלא!

- לעיתים ניתן לנו פירוק (שלא על ידי אחד האלגוריתמים הבאים המבטיחים פירוק ב-BCNF או ב-3NF), ושואלים אותנו מה הצורה הנורמלית שלו. לשם כך צריך לחשב את ההטלה של קבוצת התלויות הפונקציונליות על כל תת-יחס. אבל זה אקספוננציאלי. על כן קיים אלגוריתם שמחשב קבוצה שקולה להטלה הזאת וזה סבבה לעבוד איתה! - עוברים ממש על כל תתי הקבוצות: - לכל $X \in R_i$ מוסיפים את התלות הפונקציונלית $X \to (X^+ \cap R_i)$. (הסגור הוא לפי F המלא) - אז כשנרצה לדעת מה הצורה הנורמלית של תת-היחס, נבדוק את הקריטריונים על קבוצת התלויות שמצאנו! - משתמשים באלגוריתם הזה גם בפירוק BCNF.

- בהינתן קבוצת תלויות פונקציונליות נרצה למצוא קבוצה שקולה מינימלית. - מוטיבציה:* כדי להשתמש בזה באלגוריתם למציאת פירוק ללא אובדן, משמר תלויות, 3NF. - שלושה שלבים מרכזיים. מקבלים בתור קלט קבוצת תלויות: 1. נדאג לכך שלכל תלות יהיה רק שדה אחד בצד ימין. 2. נמחק שדות מיותרים מצד שמאל של תלויות פונקציונליות. (כלומר כמו אלגוריתם למציאת מפתח נחשב את הסגור המלא על פי F המקורית (כולל התלות הנוכחית) בלי כל שדה) 3. נמחק תלויות מיותרות (כאלו שנובעות מתלויות אחרות).

- נמצא כיסוי מינימלי G. - לכל $X \to A$ ב-G, נוסיף את תת-הסכימה $XA$. - אם בסוף שום סכימה לא מכילה מפתח, להוסיף מפתח בתור סכימה. - להסיר סכימות שמוכלות בסכימות אחרות.

- הרצה הרצה הרצה כדי להבין - האלגוריתם רקורסיבי, מחפש הפרות. לכל הפרה של X → Y מגדיר: $$ R_1 = X^+ \newline $$ $$ R_2 = X \cup (R - X^+) \newline $$ $$ return \, FindBCNFDecompostion(R_1, F_{R_1}) \cup FindBCNFDecompostion(R_2, F_{R_2}) $$ - טיפים: מריצים עם עץ, צריך לחשב את הסגור פעם אחת, סכימה בגודל 2 בהכרח ב-BNCF (זה התנאי עצירה). לא חייב לחשב את ההטלה המלאה של F על תתי הסכימות, אפשר להתחיל לחשב ולעצור כשמוצאים תלות שנוגדת את BCNF. אם יש n אטריביוטים, קבוצה בגודל n-1 בטוח לא תפר BCNF.

- נבנה גרף שבו כל קודקוד הוא טרנזקציה, ונמתח קשת בין טרנזקציות על פי הקונפליקטים. (למשל אם יש קונפליקט WW בין טרנזקציה 1 ל-2 כאשר הW הראשון הוא של 1, נמתח קשת מכוונת מ-1 ל-2) - אם אין מעגל בגרף הסופי, אז התזמון הוא בר סידור קונפליקטים (!) ויהיה שקול לכל תזמון סדרתי שהוא סידור טיפולוגי של הגרף (!).

- ננסה להוסיף לתזמון פעולות S,X,U עד שנצליח. אם נגיע למצב שבלתי אפשרי להתמודד איתו, הוא לא בר השגה.

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

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

- מציירים גרף קדימויות של מי מחכה למי, אם יש בגרף מעגל יש דדלוק.

- לכל אובייקט שומרים WTS ו-RTS שמאותחלים להיות 0. לכל טרנזקציה נותנים TS על פי הזמן שהיא התחילה. - לטרנזקציות אסור להשתמש בדברים מהעתיד, ז"א: - אם טרנזקציה מנסה לקרוא, הוא בודקת את ה-WTS, אם הוא מהעתיד היא עושה אבורט וריסטראט עם TS חדש. אחרת, היא מעדכנת את ה-RTS להיות ה-TS שלה, שומרת עותק לוקאלי של מה שקראה וממשיכה. - אם טרנזקציה מנסה לכתוב, היא בודקת את ה-RTS, אם הוא מהעתיד היא עושה אבורט וריסטארט עם TS חדש. אחרת, היא בודקת את ה-WTS, אם הוא מהעתיד, ולא משתמשים בחוק הכתיבה של תומאס, היא עושה אבורט וריסטראט עם TS חדש. אם ה-WTS הוא מהעתיד וכן משתמשים בחוק הכתיבה של תומאס, היא מבצעת כתיבה על העתק לוקאלי של האובייקט. לבסוף אם גם ה-RTS וגם ה-WTS לא מהעתיד, הכול סבבה והיא יכולה לכתוב ולעדכן את ה-WTS להיות ה-TS שלה.