נרמול בסיס נתונים

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

השאלות הבסיסיות שאנו שואלים בבואנו להקים מערכת הן:

1. איזה רלציות יש לכלול בבסיס הנתונים?
   
2. האם כל אחת מהרלציות המוקמות מכילה את כל העמודות שצריכות להיכלל בה?
   
3. האם הרלציות המוקמות לא מכילות עמודות מיותרות?

מניעת כפילות נתונים בתוך הרלציה

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

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

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

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

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

הקשר בין תלמיד לקורס או תלמיד למורה ייוצג על ידי הקמת רלציות קשר מיוחדות לדבר.

חיסכון במקום

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

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

מניעת כפילות נתונים ברלציות שונות

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

(להזכירכם: שלמות הנתונים משמעה מניעת מצב שבו שיש במערכת נתונים חלקיים "יתומים", כמו הזמנה עם מספר זיהוי של לקוח שכבר נמחק, או מצב של נתונים מנוגדים, כמו ציון מעמדו האישי של עובד כרווק ברלציה אחת וכנשוי ברלציה אחרת)

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

1. פיצול הרלציה לשתי רלציות נפרדות, אחת לתלמידי מחקר ואחת לתלמידים רגילים.
   
2. העברת העמודות הקשורות למחקר לרלציה נפרדת שתתקשר לרלצית התלמידים על ידי FKשל מספר התלמיד.

מושג התלות בין עמודות

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

הסימון B Aמשמעותו הוא שערכה של עמודה Aקובע חד חד ערכית את ערכה של עמודה B. Aנקרא 'הקובע' (Determinant) ו-Bנקרא 'התלוי' (Dependant).

הקשר הזה הוא קשר של 1:N. ערך Bעשוי להתחבר למספר רב של ערכי A, אבל ערך Aקשור לערך אחד של B.

דוגמא: בתלות הפונקציונלית שם לקוח מספר זיהוי, ערך A(מספר הזיהוי) קובע חד חד ערכית את ערך B(שם הלקוח), אבל אותו שם (לדוגמא: איציק לוי) יכול להתקשר למספר רב של מספרי זיהוי.

במקרים מסוימים הקשר יכול להצטמצם למקרה של יחס 1:1.

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

הסימון B<<–A <<מורה על כך שערך Aיכול להיות קשור לערכים רבים של Bולהיפך, Bיכול להיות קשור לערכים רבים של A. זהו קשר של N:M, קשר רב רב ערכי

(Multi value dependency). לדוגמא: היחס בין מספר זיהוי של סטודנט למספר קורס: סטודנט יכול ליטול חלק בקורסים רבים, בקורס יכולים להשתתף סטודנטים רבים.

הסימון (B<<–A <<) Cמציין תלות מורכבת.

דוגמא: הקשר הרב רב ערכי בין מספר קורס (A) למספר זיהוי (B) יכול לקבוע את הציון (C).

ולבסוף, יש גם אפשרות של תלות עוברת: אם A Bו-B Cהרי Cתלוי תלות עוברת ב-A

דוגמא מספר שורת הזמנה תלוי במספר הזמנה ומספר הזמנה תלוי במספר לקוח, אזי קיימת תלות עוברת של מספר שורת הזמנה במספר לקוח.

כללי הנירמול

קוד (Codd), אבי המודל הרלציוני, ניסח כמה כללים לבניית רלציות יעילות. כללים אלה נקראים כללי נירמול.

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

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

דרגת נירמול מספר 1 – NF1 (First Normal Form)

דרגה זו עוסקת רק במבנה הכללי של רלציה ואינה אומרת דבר על תקינותה. רלציה בדרגה NF1 היא טבלה המכילה ערכים אטומיים ואשר המפתח שלה אינו מכיל ערכי NULL.

דוגמא לרלציה שערכיה אינם אטומיים:

הרלציה מחלקה DEPT

מיקום מספר מחלקה שם מחלקה

ת"א, רחובות, חיפה 5 מכירות

ירושלים 3 הנהלה

חיפה 1 ייצור

ערך המיקום בשורה 1 אינו אטומי. כדי שהרלציה תענה על כלל נרמול 1 עליה להראות כך:

מיקום מספר מחלקה שם מחלקה

ת"א 5 מכירות

רחובות 5 מכירות

חיפה 5 מכירות

ירושלים 3 הנהלה

חיפה 1 ייצור

(על פי דוגמא 14.8 בספרו של אלמסרי)

דוגמא שניה:

נתונה רלציה עובד-פרויקט EMP_PROJ

30 1 יוסי כהן 5426854

7.5 3

14 1 דוד חסון 3254524

20 2

יש כאן "קינון" של נתונים. כדי שהרלציה תהיה תקינה יש להפרידה לשתי רלציות:

רלצית עובד EMP

רלצית פרויקט PROJ

(על פי דוגמא 14.9 בספרו של אלמסרי)

דרגת נירמול מספר 2 – NF2 (Second Normal Form)

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

לדוגמא ברלציה הבאה:

המפתח הוא מ"ז תלמיד + קוד קורס. שם קורס הוא פונקציה של מספר קורס בלבד. שם תלמיד – פונקציה של מספר תלמיד בלבד. רק הציון תלוי במפתח כולו.

כלל 2 דורש שנפריד את הרלציה לשלוש רלציות נפרדות:

דרגת נירמול מספר 3 – NF3 (>Third Normal Form)

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

קוד מחלקה ושם תלמיד תלויים במפתח – מ"ז תלמיד. אבל תקציב מחלקה תלוי בקוד המחלקה שאינו מפתח ברלציה זו. הפתרון: ליצור שתי רלציות נפרדות:

דוגמא מורכבת:

מפתח הרלציה הוא מ"ז תלמיד + קוד קורס + קוד סימסטר. בין שתי עמודות המפתח הראשונות יש יחס רב רב ערכי.

ציון קורס תלוי במפתח כולו. לעומת זאת ממוצע סימסטר תלוי רק בחלק מן המפתח (מ"ז תלמיד וקוד סימסטר) ולכן נוגד את כלל נירמול 2. גם העמודות שם תלמיד, קוד מחלקה, וממוצע כללי תלויות בחלק מן המפתח (מ"ז תלמיד) דבר הנוגד את כלל 2. שם הקורס ומשקל הקורס תלויים רק בקוד הקורס, שוב ניגוד לכלל 2.

הפתרון הוא:

תלמיד

קורס

מחלקה

הישגי סימסטר

הישגי קורס

כלל הנירמול הדרישה פעולת הנירמול

1NF איסור עמודה לא אטומית פיצול ערך לא אטומי לכמה שורות ברלציה

איסור יחסים מקוננים הפיכת יחס מקונן לרלציה עצמאית.

2NF איסור תלות עמודה פיצול לרלציות תלויות כל המפתח

שאינה מפתח רק בחלק

מן המפתח.

3NF איסור תלות עמודה שאינה פיצול רלציות והעברת העמודות התלויות

מפתח בעמודה אחרת בעמודות אחרות לרלציה החדשה שם

תהיינה תלויות במפתח בלבד.

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

את שלושת הכללים שתיארנו סיכמנו כך:

כלל הנירמול הדרישה פעולת הנירמול

1NF איסור עמודה לא אטומית פיצול ערך לא אטומי לכמה שורות ברלציה

איסור יחסים מקוננים הפיכת יחס מקונן לרלציה עצמאית.

2NF איסור תלות עמודה פיצול לרלציות תלויות כל המפתח

שאינה מפתח רק בחלק

מן המפתח.

3NF איסור תלות עמודה שאינה פיצול רלציות והעברת העמודות התלויות

מפתח בעמודה אחרת בעמודות אחרות לרלציה החדשה שם

שאינה מפתח. תהיינה תלויות במפתח בלבד.

דרגת נירמול רביעית FN4

MVD(Multivalued Dependency) הוא מצב של תלויות מרובות – שני יחסים או יותר של 1:Nבתוך אותה רלציה.

הכלל אומר שאם ברלציה קיימים מצב של MVD, יש לפצל את הרלציה לכמה רלציות נפרדות.

דוגמא: נניח שיש לנו רלצית EMPובה עמודה שפה EM_LANGועמודת מקצוע EM_PROFוכל עובד אפשר שידע כמה שפות ויחזיק בכמה מקצועות. כל אחת משתי העמודות האלה נמצאת ביחס של 1:Nעם המפתח מספר עובד EMP_IDאבל אין קשר הכרחי בין שפה למקצוע.

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

הפתרון לפי כלל 4 יהיה לפרק את הרלציה לשתי רלציות:

דרגת נירמול חמישית FN5

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

דוגמא:

נתונה רלציה AG_COM_PRODובה שלוש עמודות: סוכן (AGENT), מוצר

(PRODUCT) וחברה (COMPANY).

הסוכן מייצג כמה חברות.

הסוכן מוכר כמה מוצרים

לחברה יש כמה מוצרים

קיימות כאן אם כך שלוש תלויות של 1:N

סוכן – חברה

סוכן – מוצר

חברה – מוצר

הפתרון יהיה לפצל את הרלציה לשלוש רלציות:

את ההבדל בין שני הכללים ניתן לתאר בצורה גרפית כך:

הפיצול לרלציות על פי כלל 5 איננו פתרון אוטומטי. לעתים יש גם לפצל את הרלציה לכמה רלציות וגם להשאיר על כנה את הרלציה המשולשת.

ניתן כאן שתי דוגמאות.

(הדוגמא הראשונה מפורטת בשקפים 39 ו-40 בשיעור 5-6-7).

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

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

יש לנו אם כך רלציה משולשת

שעל פי כלל 5 עלינו לפצלה לשלוש רלציות:

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

אם כך לשם מה הרלציות הנוספות?

התשובה היא שעשוי להיות מצב שבו ניתנת הרשאה לתוכניתן מסוים ליטול חלק רק בפרויקטים מסוימים ולא בכל פרויקט. אנו רוצים לשמר את המידע הזה ("פוטנציאל" הפרויקטים המותרים לכל מתכנת) כרלציה נפרדת. כדי לשמור על שלמות הנתונים עלינו להגדיר ברלציה המשולשת את שתי העמודות, מתכנת ופרויקט, לא רק כעמודות מפתח (PK), אלא גם כמפתחות זרים (FK) ביחס לרלציה תוכניתן-פרויקט.

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

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

שאלה:

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

שאלה:

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

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

אפשר לתאר זאת גם באמצעות התרשים הבא:

בכל מקרה שקיים יחס של N:Mבין שתי רלציות או יותר, יש מקום להוסיף רלצית קשר. ההחלטה אם להוסיף רלצית קשר או לא תלויה בדרישות שהוגדרו על ידי מזמין המערכת.

דוגמא נוספת: קיימות שלוש רלציות מרצה קורס ותלמיד. האם יש מקום לקיומה של רלציה משולשת מרצה-קורס-תלמיד? בהחלט. סביר מאוד שהמערכת האוניברסיטאית רוצה לשמש נתונים קונקרטיים באיזה קורס של איזה מרצה השתתף תלמיד מסוים. רלציה זו יכולה להכיל בנוסף גם את עמודת הציון. בקורס הנוכחי למשל יש שלושה מרצים המעבירים את קורס בסיסי נתונים, פרופ' שובל, ד"ר גלזר ועבדכם הנאמן, מר פרץ וחשוב לדעת איזה תלמיד משתתף בקורס בסיסי נתונים של איזה מרצה.

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

האם יש מקום לרלציה תלמיד-מרצה? סביר להניח שלא. בדרך כלל אין הגבלה של מרצים מסוימים לתלמידים מסוימים.

(אבל יתכן שמרצה מסוים הוא כה פופולרי עד שכל התלמידים "בורחים" לשיעורים שלו ונוצרת אי פרופורציה. במקרה כזה האוניברסיטה יכולה לחייב סטודנט מסויים לשמוע דווקא מרצה זה ולא אחר ולעגן זאת במערכת באמצעות רלציה מתאימה…)

הרכבת רלציות

הדוגמא האחרונה מביאה אותנו לנושא הבנייה של רלציות בתוך מערכת.

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

בין שדות נתונים יתכנו בעיקרון שלושה סוגי יחסים: 1:1, 1:Nו-M:N.

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

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

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

כאשר היחס הוא 1:N, למשל שם : מספר-זיהוי, ברור שהצד ה-N-י (מספר זיהוי במקרה זה) הוא המפתח והשם הוא שדה רגיל תלוי מפתח.

כאשר היחס הוא N:M, למשל במקרה של תלמיד : קורס (תלמיד נרשם לקורסים אחדים; לקורס מסוים נרשמים תלמידים אחדים) מוגדרים שני השדות כשדות מפתח (יוצרים מפתח מורכב שבו הצרוף של שני השדות הוא חד חד ערכי).

כאשר יש קשרי N:Mבין יותר משני שדות, ההחלטה אם להקים רלציות עם מפתח בן שלושה שדות (או יותר), או להקים כמה רלציות שבכל אחת מהן מפתח בן שני שדות, או ליצור קומבינציות שונות של גם זה וגם זה, נתונה לשיקול דעת של מקים המערכת, על פי ההנחיות שהוא מקבל מ"בעל הבית" – מזמין העבודה.

סיכום נושא הנירמול

הנירמול תורם ליעילות המערכת, מניעת בזבוז משאבים וכפילויות ברישום, אבל לעתים יש לו גם חסרונות.

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

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

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

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

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