כיסוי קנוני

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

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

 אף תלות פונקציונלית ב- אינה תלות עודפת.
 כל צד שמאל של תלות פונקציונלית ב- הוא ייחודי. כלומר, אין ב- שתי תלויות פונקציונליות מהצורה  ו  ב  כזה ש  .

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

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


 חזור :
 השתמש בכלל האיחוד כדי להחליף כל תלות ב  של הטופס  ו  עִם  .
 מצא תלות פוקציונלית ב  עם תכונה מיותרת ומחק אותה מ- .
 עַד  שנותר ללא שינוי. 

 דוגמה לכיסוי קנוני 
בדוגמה הבאה,  הוא הכיסוי הקנוני של 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}

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

בהינתן אוסף של תלויות פונקציונליות  ותלות פוקציונלית  ב .

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

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

 הערות שוליים 

קטגוריה:מסדי נתונים
קטגוריה:אלגוריתמים