אלגברה רלציונית
אלגברה רלציונית (Relational algebra) או אלגברת היחסים היא פורמליזם המשמש לצורך כתיבת שאילתות על מסדי נתונים הבנויים בצורה של טבלאות. הפורמליזם מבוסס על לוגיקה מסדר ראשון ועל תורת הקבוצות.
אלגברת היחסים דומה במעט לאריתמטיקה. אריתמטיקה עוסקת בערכים מספריים, ומתירה עליהם פעולות חשבון. אלגברת היחסים אף היא מאפשר להפעיל פעולות (אופרטורים) על ערכים, אלא שהערכים בהם עוסקת אלגברת היחסים הם "יחסים" (relations) או "טבלאות". באלגברה ישנם שישה אופרטורים בסיסיים, אשר כל אחד מהם מקבל כקלט טבלה אחת או יותר, ומחשב מאלו טבלה חדשה, שבדרך כלל תהיה שונה מהטבלאות הנתונות בקלט.
טבלה היא קבוצה של ערכים מסוג רשומה. האלגברה עוסקת בטבלאות עצמן, ואינה מאפשרת גישה לרשומות בודדות שבטבלה. כל הרשומות שבטבלה חייבות להיות בעלות מבנה זהה: חייב להיות בהן אותו מספר שדות, ולשדות אלו חייבים להיות בדיוק אותם שמות. לשני שדות שונים לא יכול להיות אותו שם.
מבנה הטבלה, הוא קבוצת שמות השדות של הרשומות המופיעים בה.
כך למשל, טבלה יכולה להיות רשימת קשר המשמשת להעברת פרטי התקשרות בין הוריהם של ילדים בכיתה מסוימת. הרשומות שבטבלה מכילות מידע לגבי אותה רשימת השדות. בדוגמת רשימת הקשר, סביר ששדות אלו יהיו: שם הילד, שם האב, שם האם, כתובת, מספר טלפון של האב, ומספר טלפון של האם. הקבוצה המכילה את ששת השמות הללו, היא בדיוק המבנה של טבלת רשימת הקשר.
פורמלית, אסור שרשומות שונות תכלנה רשימת שדות שונה. בדרך כלל, זו אינה מגבלה קשה מדי, בהתחשב בעובדה שנהוג להתיר ערך "ריק" לשדות. רשימת הקשר תהיה עדיין טבלה תקינה גם אם לאחד מהורי הילדים אין טלפון משלו.
האופרטורים היסודיים על טבלאות המוגדרים באלגברת היחסים הם:
- איחוד (union): בהינתן שתי טבלאות שהמבנה שלהם זהה, האופרטור מחשב את הטבלה שהיא האיחוד, במובן של תורת הקבוצות, של שתי הטבלאות. בדוגמה שלנו, ניתן לחשב את האיחוד של רשימת הקשר של הילדים בכיתה, ושל הילדים בקייטנה. איחוד זה יכיל רשומה אחת עבור כל ילד, אפילו אם הילד רשום גם לכיתה וגם לקייטנה. סילוק הכפילויות דורש זהות מוחלטת בין הרשומות. על כן, אם בעבור ילד מסוים, פרטי הקשר בשתי הטבלאות המקוריות הם שונים, תופענה שתי רשומות בטבלה המאוחדת.
- חיסור (substraction), שעל אף שמו, שונה מפעולת החיסור האריתמטית: בהינתן שתי טבלאות שהמבנה שלהם זהה, האופרטור מחזיר את הטבלה הראשונה, לאחר שהסירו ממנה את הרשומות המופיעות בטבלה השנייה. בדוגמה שלנו, אם נחסיר מרשימת הקשר המאוחדת את רשימת הקשר של ילדי הקייטנה, נקבל את רשימת הקשר של הילדים בכיתה אשר אינם משתתפים בקייטנה.
- החלפת שם (renaming): אופרטור המקבל טבלה, שם של שדה שבה, ושם חדש לאותו שדה. בדוגמה שלנו, אפשר להפעיל אופרטור זה על רשימת הקשר כך שבטבלה הנוצרת: השדה המכונה "שם האב" יקרא "שם הורה 1". הפעלה נוספת של האופרטור על התוצאה, תוכל ליצור טבלה חדשה שבה השדות המכילים את שמות ההורים יקראו "שם הורה 1" ו"שם הורה 2".
- הטלה (projection): אופרטור זה מקבל טבלה, ורשימה של שמות של שדות מתוכה, והוא מחזיר טבלה אשר בה מסולקות כל העמודות לבד מאלו המופיעים ברשימה הנתונה. כך, אם נטיל את רשימת הקשר שלנו על השדות "שם הילד" ו "שם האב", נקבל טבלה חדשה שבה רק שתי עמודות אלו תופענה. כיוון שטבלה מיוצגת כקבוצה, הרי אם בגן יש שני ילדים שגם שמם, וגם שם אביהם זהה, הרי הטבלה הנוצרת מההטלה תכיל רק רשומה אחת עבור שני ילדים אלו.
- מכפלה קרטזית (Cartesian Product): בהינתן שתי טבלאות שהמבנה שלהן זר, כלומר שאין אף שם של שדה שמופיע בשתי הטבלאות יחד, אופרטור המכפלה הקרטזית יוצר טבלה חדשה המכילה את כל הצירופים האפשריים של רשומה מהטבלה הראשונה, ורשומה מהטבלה השנייה. כדי להדגים את האופרטור בדוגמה שלנו, נשווה בנפשנו טבלה נוספת, שבה שתי עמודות בלבד: "רחוב" ו"מרחק מבית-הספר". בטבלה זו נרשום את המרחק של כל אחד מרחובות העיר מהגן. אם נכפיל טבלה זו בטבלת רשימת הקשר, נקבל טבלה ענקית, אשר המבנה שלה הוא קבוצת השמות: "רחוב", "מרחק מבית-הספר", " שם הילד", "שם האב", "שם האם", "כתובת", "מספר טלפון של האב", ו"מספר טלפון של האם". בטבלה זו לכל ילד בכיתה, תהינה מספר רב של רשומות, אחת לכל רחוב בעיר.
- בחירה (selection): בהינתן טבלה, ותנאי כלשהו על השדות שבה, פעולת הבחירה מיצרת טבלה חדשה בעלת מבנה זהה לטבלה הנתונה, והמכילה רק את הרשומות שבטבלה הנתונה שמקיימות את התנאי. תנאי הבחירה יכיל בדרך כלל השוואות בין ערכי השדות, וצירופים לוגיים של אלו. בדוגמה שלנו, התנאי "שם הילד זהה לשם האב או שם הילד זהה לשם האם" בהפעלתו כבחירה על רשימת הקשר, יתן את רשימת הקשר של הילדים הנקראים על שם אחד מהוריהם.
בעזרת ששת האופרטורים היסודיים, ובאמצעות אופרטורים נוספים, שאינם אלא קיצורי דרך להפעלת האופרטורים היסודיים, ניתן לבצע חישובים מורכבים ביותר על טבלאות. כך למשל, אם נסתכל שוב על הטבלה הענקית שנוצרה באמצעות המכפלה הקרטזית של רשימת הקשר בטבלת מרחקי הרחובות מבית-הספר, ונבחר מתוכה באמצעות אופרטור הבחירה את הרשומות שבהם הכתובת מכילה את שם הרחוב, נקבל טבלה חדשה שתספק לנו מידע על המרחק של כל ילד מבית הספר. כמובן, אם נרצה נוכל לסלק מטבלה זו שדות מיותרים באמצעות אופרטור ההטלה.
על אף הכח הרב של אלגברת היחסים, ישנן פעולות שאי אפשר לבצע בה. בדוגמה שלנו למשל, אי אפשר לחשב את המרחק הממוצע של מגורי הילדים מבית הספר, וזאת משום שהאלגברה אינה כוללת אופרטורים לסיכום שדות המופיעים ברשומות שונות. לא ניתן גם להשתמש באלגברה כדי לבחור ילד אקראי מהכיתה, משום שהאלגברה אינה עוסקת ברשומות בודדות.
אלגברת היחסים אינה מאפשרת יצירת ביטויים המפעילים אופרטור מסוים מספר בלתי חסום של פעמים. כתוצאה מכך, לא ניתן להשתמש באלגברה כדי לייצר את רשימת כל הדרכים להקיף את העולם בטיסה, גם אם נתונות לנו טבלאות המתארות את כל הטיסות כולן. הקושי הוא בכך שמספר הטיסות שבהן אפשר להקיף את העולם אינו חסום.
20941042אלגברה רלציונית