כיסוי קנוני
כיסוי קנוני $ F_{c} $ (באנגלית: Canonical Cover) עבור קבוצת תלויות פונקציונליות F על תבנית יחסים, הוא קבוצת תלויות כך ש-F מסיק לוגית את כל התלויות ב-$ F_{c} $, ו-$ F_{c} $ מסיק לוגית את כל התלויות ב-F.
לכיסוי הקנוני $ F_{c} $ יש שתי תכונות חשובות:
- אף תלות פונקציונלית ב-$ F_{c} $ אינה תלות עודפת.
- כל צד שמאל של תלות פונקציונלית ב-$ F_{c} $ הוא ייחודי. כלומר, אין ב-$ F_{c} $ שתי תלויות פונקציונליות מהצורה $ a\to b $ ו $ c\to d $ ב $ F_{c} $ כזה ש $ a=c $ .
כיסוי קנוני אינו ייחודי עבור קבוצה נתונה של תלויות פונקציונלית, לכן קבוצה אחת F יכולה להיות בעלת מספר כיסויים $ F_{c} $ .
אלגוריתם לחישוב כיסוי קנוני
- $ F_{c}=F $
- חזור :
- השתמש בכלל האיחוד כדי להחליף כל תלות ב $ F_{c} $ של הטופס $ a\to b $ ו $ a\to d $ עִם $ a\to bd $ .
- מצא תלות פוקציונלית ב $ F_{c} $ עם תכונה מיותרת ומחק אותה מ- $ F_{c} $.
- עַד $ F_{c} $ שנותר ללא שינוי. [1]
דוגמה לכיסוי קנוני
בדוגמה הבאה, $ F_{c} $ הוא הכיסוי הקנוני של F.
בהינתן תבנית היחסים ואוסף התלויות הפונקציות החלות עליה נמצא את הכיסוי הקנוני:
, R = (A, B, C, G, H, I), F = {A→BC, B→C, A→B, AB→C}
- {A→BC,B→C,A→B,AB→C}
- {A → BC, B →C, AB → C}
- {A → BC, B → C}
- {A → B, B →C}
F c = {A → B, B →C}
תכונות עודפות
תכונה המופיעה בתלות היא תכונה עודפת אם אפשר למחוק אותה מן התלות בלי שהסגור ישתנה.[2]
בהינתן אוסף של תלויות פונקציונליות $ F $ ותלות פוקציונלית $ A\rightarrow B $ ב $ F $.
תכונה $ a\in A $ היא תכונה עודפת באגף שמאל אם אפשר להסיק מ-$ F $ את התלות $ ({(A-a)\rightarrow B}) $.
תכונה $ b\in B $ היא תכונה עודפת באגף ימין אם אפשר להסיק מקבוצת התלויות $ ((F-(A\rightarrow B))\cup \{A\rightarrow (B-b)\}) $ את התלות $ A\rightarrow B $. כלומר, אם ניתן לשחזר את התלות $ A\rightarrow b $ מתוך יתר התלויות, לאחר מחיקת $ b $ מאגף ימין של $ A\rightarrow B $.
הערות שוליים
- ↑ Silberschatz, Abraham (2011). Database system concepts (PDF) (Sixth ed.). New York: McGraw-Hill. ISBN 978-0073523323. אורכב מ-המקור (PDF) ב-2020-11-08.
- ↑ Elmasri, Ramez (2016). Fundamentals of database systems. Sham Navathe (Seventh ed.). Hoboken, NJ: Pearson. ISBN 978-0-13-397077-7. OCLC 913842106.

כיסוי קנוני40314081Q1723874