כיסוי קנוני

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

כיסוי קנוני $ 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} $ שנותר ללא שינוי. [1]

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

בדוגמה הבאה, $ 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}

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

תכונה המופיעה בתלות היא תכונה עודפת אם אפשר למחוק אותה מן התלות בלי שהסגור ישתנה.[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 $.

הערות שוליים

  1. Silberschatz, Abraham (2011). Database system concepts (PDF) (Sixth ed.). New York: McGraw-Hill. ISBN 978-0073523323. אורכב מ-המקור (PDF) ב-2020-11-08.
  2. Elmasri, Ramez (2016). Fundamentals of database systems. Sham Navathe (Seventh ed.). Hoboken, NJ: Pearson. ISBN 978-0-13-397077-7. OCLC 913842106.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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