כיסוי קנוני

כיסוי קנוני $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$.

הערות שוליים

ערך זה הוא יתום, כלומר אין ערכים במכלול שמקשרים אליו. אתם מוזמנים לתרום למכלול ולקשר אליו מכמה מהערכים שמכילים את המונח "כיסוי קנוני".

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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