תזמון (מסדי נתונים)

בתחום מסדי הנתונים, תזמון הוא הרשימה של פעולות (לרוב קריאה, כתיבה, ביטול והתחייבות) של טרנסאקציות שונות בסדר זמן מסוים. לדוגמה, בתזמון פשוט שלוש טרנסאקציות T1, T2, T3 מבצעות קריאות (R(X), קריאה של אובייקט X), כתיבות (W(X), כתיבה לאובייקט X), התחייבות (Com., Commit) או ביטול (Abort). תזמון שבו כל טרנסאקציה מסתיימת לפני שהבאה מתחילה נקרא תזמון סדרתי.\n\n= הצורך בתזמון =\nכשרצות במקביל טרנסאקציות על אותו מאגר נתונים, צריך לשלוט בסדר הפעולות כדי להימנע מתוצאות שגויות. דוגמה מעשית היא מכירת כרטיסים: אם שתי בקשות בודקות זמינות ואז כותבות במקביל, יתכן ששני לקוחות יקבלו את אותו כרטיס. תזמון נכון מונע בעיות כאלה.\n\n= סוגים של תזמונים =\n= תזמון סדרתי (בר-סידור) =\nתזמון סדרתי הוא כזה שבו הטרנסאקציות רצות אחת אחרי השנייה בלי ערבוב של פעולות ביניהן.\n\n= תזמון שווה-סדרתי (בר-סידור) =\nתזמון נקרא שווה-סדרתי אם הוא שקול בתוצאה שלו לתזמון סדרתי. כלומר, למרות שהפעולות מעורבות, המצב הסופי שווה לזה של סדרת טרנסאקציות מסודרות.\n\n= תזמון מאפשר התאוששות =\nתזמון מאפשר התאוששות אם טרנסאקציות מתחייבות רק אחרי שכל הטרנסאקציות שהן קראו מהן כבר התחייבו. זה מבטיח שאם יש ביטול, אי־דיוקים לא נשארים בבסיס הנתונים.\n\n= תזמון לא מאפשר התאוששות =\nאם טרנסאקציה מתבטלת אבל טרנסאקציה אחרת כבר התחייבה בהתבסס על השינויים שלה, התזמון לא מאפשר התאוששות. זה יוצר מצב בעייתי שבו צריך לתקן או לבטל שינויים.\n\n= תזמון המונע גלגול לאחור בשרשרת =\nתזמון כזה מוודא כי אם טרנסאקציה מתבטלת, אין צורך לבטל טרנסאקציות אחרות שנחשפו לשינויים שלה. סוג זה תמיד מאפשר התאוששות.\n\n= שווה-סדרתיות בקונפליקט =\nשתי פעולות בקונפליקט הן פעולות משתי טרנסאקציות שונות, שמשתמשות באותו אובייקט, ולפחות אחת מהן כותבת. אם הסדר של כל זוגות הפעולות שבקונפליקט נשמר בין שני תזמונים, הם שקולים בקונפליקט. תזמון נקרא שווה סדרתי בקונפליקט אם הוא שקול בקונפליקט לתזמון סדרתי.\n\n= שווה-סדרתיות במבט =\nשקילות במבט מציבה תנאים על מי קורא מה ומי כותב אחרון לאובייקט. תזמון שווה סדרתי במבט שומר על אותם קריאות וכתיבות ביחס לטרנסאקציות כמו בתזמון סדרתי. יש מקרים שבהם תזמון הוא שווה סדרתי במבט אבל לא בקונפליקט; זה קורה למשל כשיש "כתיבה עיוורת", כתיבה לאובייקט ללא קריאה אליו קודם.\n\nחשוב לדעת שהבדיקה האם תזמון הוא שווה סדרתי במבט היא בעיה קשה חישובית (NP-שלמה), ולכן בשימושים מעשיים בדרך כלל משתמשים בבדיקות פשוטות יותר כמו שקילות בקונפליקט.

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