כיסוי קנוני

כיסוי קנוני $F_c$ (באנגלית: Canonical Cover) עבור קבוצת תלויות פונקציונליות F על תבנית יחסים, הוא קבוצת תלויות כך ש-F מסיק לוגית את כל התלויות ב-$F_c$, ו-$F_c$ מסיק לוגית את כל התלויות ב-F.

לכיסוי הקנוני $F_c$ יש שתי תכונות חשובות:

1. אף תלות פונקציונלית ב-$F_c$ אינה תלות עודפת.
2. כל צד שמאל של תלות פונקציונלית ב-$F_c$ הוא ייחודי. כלומר, אין ב-$F_c$ שתי תלויות פונקציונליות מהצורה $a\to b$ ו $c\to d$ ב $F_c$ כזה ש $a=c$ .

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

אלגוריתם לחישוב כיסוי קנוני

1. $F_c=F$
2. חזור :
   1. השתמש בכלל האיחוד כדי להחליף כל תלות ב $F_c$ של הטופס $a\to b$ ו $a\to d$ עִם $a\to bd$ .
   2. מצא תלות פוקציונלית ב $F_c$ עם תכונה מיותרת ומחק אותה מ- $F_c$.
3. עַד $F_c$ שנותר ללא שינוי.

דוגמה לכיסוי קנוני

בדוגמה הבאה, $F_c$ הוא הכיסוי הקנוני של F.

בהינתן תבנית היחסים ואוסף התלויות הפונקציות החלות עליה נמצא את הכיסוי הקנוני:

, R = (A, B, C, G, H, I), F = {A→BC, B→C, A→B, AB→C}

1. {A→BC,B→C,A→B,AB→C}
2. {A → BC, B →C, AB → C}
3. {A → BC, B → C}
4. {A → B, B →C}

F _c = {A → B, B →C}

תכונות עודפות

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

בהינתן אוסף של תלויות פונקציונליות $F$ ותלות פוקציונלית $A\to B$ ב $F$.

תכונה $a\in A$ היא תכונה עודפת באגף שמאל אם אפשר להסיק מ-$F$ את התלות $((A-a)\to B)$.

תכונה $b\in B$ היא תכונה עודפת באגף ימין אם אפשר להסיק מקבוצת התלויות $((F-(A\to B))\cup \{A\to (B-b)\})$ את התלות $A\to B$. כלומר, אם ניתן לשחזר את התלות $A\to b$ מתוך יתר התלויות, לאחר מחיקת $b$ מאגף ימין של $A\to B$.