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

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

דוגמה לתזמון:

$D={\begin{bmatrix}T1&T2&T3\\R(X)&&\\W(X)&&\\Com.&&\\&R(Y)&\\&W(Y)&\\&Com.&\\&&R(Z)\\&&W(Z)\\&&Abort\end{bmatrix}}$

בדוגמה זו, התזמון D מורכב מהתנועות T3, T2, T1. התזמון מתאר אלו פעולות התנועות עושות על מסד הנתונים כאשר:

$R(X)$‎ מסמן קריאה (Read) של אובייקט X.

$W(X)$‎ מסמן כתיבה (Write) לאובייקט X.

$Com.$‎ מסמן שהתנועה התחייבה (Commit).

$Abort$ מסמן שהתנועה התבטלה (Abort).

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

הצורך בתזמון

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

תזמון זה (בצורה מופשטת, בה בקשה אחת מסומנת על ידי T1, הבקשה האחרת על ידי T2, ופעולות הקריאה והכתיבה כפי שצוינו לעיל) עשוי להיראות כך:

$D'={\begin{bmatrix}T1&T2\\&R(X)\\R(X)&\\W(X)&\\&W(X)\\\end{bmatrix}}$

סוגים של תזמונים

תזמון סדרתי (בר-סידור)

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

תזמון שווה-סדרתי (בר-סידור)

תזמון הוא שווה-סדרתי אם הוא שקול לתזמון סדרתי.

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

$E={\begin{bmatrix}T1&T2&T3\\R(X)&&\\&R(Y)&\\&&R(Z)\\W(X)&&\\&W(Y)&\\&&W(Z)\\Com.&Com.&Abort\end{bmatrix}}$

תזמון מאפשר התאוששות

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

$F={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Com.&\\&Com.\\&\end{bmatrix}}F2={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Abort&\\&Abort\\&\end{bmatrix}}$

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

תזמון לא מאפשר התאוששות

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

$G={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\&Com.\\Abort&\\&\end{bmatrix}}$

תזמון המונע גלגול לאחור בשרשרת

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

$F={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Com.&\\&Com.\\&\end{bmatrix}}F2={\begin{bmatrix}T1&T2\\R(A)&\\W(A)&\\&R(A)\\&W(A)\\Abort&\\&Abort\\&\end{bmatrix}}$

בדוגמה לעיל, אף על פי שF2 הוא תזמון מאפשר התאוששות, הוא לא מונע גלגול לאחור בשרשרת.

לעומת זאת, F3 הוא תזמון המונע גלגול לאחור בשרשרת.

$F3={\begin{bmatrix}T1&T2\\&R(A)\\R(A)&\\W(A)&\\&W(A)\\Abort&\\&Commit\\&\end{bmatrix}}$

שווה-סדרתיות בקונפליקט

קונפליקטים

שתי פעולות או יותר נמצאות בקונפליקט אם:

1. הפעולות שייכות לתנועות שונות
2. לפחות אחת מהפעולות היא פעולת כתיבה
3. הפעולות ניגשות לאותו אובייקט

לדוגמה: בסדרת הפעולות הבאה יש קונפליקט:

• T1:R(X), T2:W(X), T1:W(X)

ובאלה אין:

• T1:R(X), T2:R(X), T3:R(X)
• T1:R(X), T2:W(Y), T3:R(X)

שקילות בקונפליקט

שני תזמונים נקראים שקולים בקונפליקט אם מתקיימים התנאים הבאים:

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

תזמון שווה סדרתי בקונפליקט

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

$G={\begin{bmatrix}T1&T2\\R(A)&\\&R(A)\\W(B)&\\Com.&\\&W(A)\\&Com.\\&\end{bmatrix}}$

התזמון G שווה סדרתי בקונפליקט, כיוון שהוא שקול בקונפליקט ל-T1:T2

שווה-סדרתיות במבט

שקילות במבט

שני תזמונים S1 ו-S2 נקראים שקולים במבט אם התנאים הבאים מתקיימים:

1. אם התנועה $T_{i}$ ב-S1 קוראת לראשונה את אובייקט X, אז גם $T_{i}$ ב-S2 תעשה זאת.
2. אם התנועה $T_{i}$ ב-S1 קוראת את הערך באובייקט X שנכתב על ידי התנועה $T_{j}$, אז גם $T_{i}$ ב-S2 תעשה זאת.
3. אם התנועה $T_{i}$ ב-S1 כותבת אחרונה לאובייקט X, אז גם $T_{i}$ ב-S2 תעשה זאת.

תזמון שווה סדרתי במבט

תזמון נקרא שווה סדרתי במבט אם הוא שקול במבט לתזמון סדרתי.

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

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

$H={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\&&\end{bmatrix}}$

התזמון H הוא שווה סדרתי במבט אך לא שווה סדרתי בקונפליקט.

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