جدول معاملات قاعدة البيانات

يقال إن فعلين متعارضان (زوج متعارض) إذا وفقط إذا تحققت جميع الشروط الثلاثة التالية:

1. الإجراءات تنتمي إلى معاملات مختلفة.
2. إحدى هذه العمليات على الأقل هي عملية كتابة.
3. تصل الإجراءات إلى نفس الكائن (قراءة أو كتابة). ^{[ 4 ] [ 5 ]}

بمعنى آخر، يُعتبر فعلان متعارضين إذا وفقط إذا كانا غير تبادليين . بمعنى آخر، يُعتبر فعلان متعارضين إذا وفقط إذا كانا تعارضًا بين القراءة والكتابة ، أو بين الكتابة والقراءة ، أو بين الكتابة والكتابة .

مجموعة الإجراءات التالية متضاربة:

• R1(X)، W2(X)، W3(X) (3 أزواج متضاربة)

في حين أن مجموعات الإجراءات التالية لا تتعارض:

• R1(X)، R2(X)، R3(X)
• R1(X), W2(Y), R3(X)

إن تقليل النزاعات، مثلاً من خلال التبادلية، يعزز الأداء لأن النزاعات هي السبب الأساسي للتأخيرات والإجهاضات.

يتحقق التعارض إذا تم تنفيذ العملية المتعارضة المطلوبة بالفعل: في كثير من الحالات، تتأخر العملية المتعارضة المطلوبة/الصادرة بواسطة معاملة ما، بل وقد لا يتم تنفيذها أبدًا، عادةً بسبب قفل على كائن العملية، تحتفظ به معاملة أخرى، أو عند الكتابة إلى مساحة العمل الخاصة المؤقتة للمعاملة وتحقيقها، أي نسخها إلى قاعدة البيانات نفسها، عند الالتزام؛ طالما لم يتم تنفيذ العملية المتعارضة المطلوبة/الصادرة على قاعدة البيانات نفسها، فإن التعارض غير متحقق ؛ لا يتم تمثيل التعارضات غير المتحققة بحافة في مخطط الأسبقية.

يُقال إن الجدولين S1 و S2 متكافئان من حيث التعارض إذا وفقط إذا تحقق الشرطان التاليان:

1. يتضمن كل من الجدولين S1 و S2 نفس مجموعة المعاملات بحيث تحتوي كل معاملة على نفس الإجراءات بنفس الترتيب.
2. يحتوي كلا الجدولين على نفس مجموعة الأزواج المتضاربة (بحيث تكون الإجراءات في كل زوج متضارب بنفس الترتيب). ^{[ 6 ]} وهذا يعادل اشتراط أن تكون جميع العمليات المتضاربة (أي العمليات في أي زوج متضارب) بنفس الترتيب في كلا الجدولين.

وبصورة مكافئة، يُقال إن جدولين متكافئان من حيث التعارض إذا وفقط إذا كان من الممكن تحويل أحدهما إلى الآخر عن طريق تبديل أزواج من العمليات غير المتعارضة (سواء كانت متجاورة أم لا) مع الحفاظ على ترتيب الإجراءات لكل معاملة. ^{[ 4 ]}

وبصورة مكافئة، يُقال إن جدولين متكافئان من حيث التعارض إذا وفقط إذا كان من الممكن تحويل أحدهما إلى الآخر عن طريق تبديل أزواج من العمليات المتجاورة غير المتعارضة ذات المعاملات المختلفة. ^{[ 7 ]}

يقال إن الجدول الزمني قابل للتسلسل المتعارض عندما يكون الجدول الزمني مكافئًا تعارضيًا لجدول زمني متسلسل واحد أو أكثر.

بصورة مكافئة، يكون الجدول قابلاً للتسلسل في حالة التعارض إذا وفقط إذا كان مخطط أسبقيته غير دوري عند النظر فقط في المعاملات الملتزمة. تجدر الإشارة إلى أنه إذا تم تعريف المخطط ليشمل أيضًا المعاملات غير الملتزمة، فقد تحدث دورات تتضمن معاملات غير ملتزمة دون انتهاك قابلية التسلسل في حالة التعارض.

الجدول الزمني K مكافئ من حيث التعارض للجدول الزمني التسلسلي <T1,T2>، ولكنه ليس <T2,T1>.

يمكن فرض قابلية التسلسل المتعارض عن طريق إعادة تشغيل أي معاملة داخل الدورة في مخطط الأسبقية، أو عن طريق تطبيق قفل ثنائي المرحلة ، أو ترتيب الطوابع الزمنية ، أو عزل اللقطات القابلة للتسلسل . ^{[ 8 ]}

يُقال إن الجدولين S1 و S2 متكافئان من حيث العرض عندما تتحقق الشروط التالية:

1. إذا كانت المعاملة${\displaystyle T_{i}}$في S1، يتم قراءة القيمة الأولية للكائن X، وكذلك يتم تنفيذ نفس المعاملة.${\displaystyle T_{i}}$في S2.
2. إذا كانت المعاملة${\displaystyle T_{i}}$يقرأ قيمة (لكائن X) مكتوبة بواسطة المعاملة${\displaystyle T_{j}}$في المرحلة S1، يجب أن يفعل ذلك في المرحلة S2.
3. إذا كانت المعاملة${\displaystyle T_{i}}$في S1 يتم تنفيذ عملية الكتابة النهائية للكائن X، وكذلك يتم تنفيذ نفس المعاملة.${\displaystyle T_{i}}$في S2.

بالإضافة إلى ذلك، يجب أن يتضمن جدولان متكافئان من حيث العرض نفس مجموعة المعاملات بحيث تحتوي كل معاملة على نفس الإجراءات بنفس الترتيب.

في المثال أدناه، يكون الجدولان S1 و S2 متكافئين من حيث العرض، ولكن لا S1 ولا S2 متكافئان من حيث العرض مع الجدول S3.

لم يتم استيفاء الشروط اللازمة لكي يكون S3 مكافئًا من حيث العرض لـ S1 و S2 عند الرموز العلوية المقابلة للأسباب التالية:

1. فشل الشرط الأول لتكافؤ الرؤية لأن T1 قرأ القيمة الأولية لـ B في S1 و S2، لكن T2 قرأ القيمة الأولية لـ B في S3.
2. فشل الشرط الثاني لتكافؤ العرض لأن T2 قرأ القيمة التي كتبها T1 لـ B في S1 و S2، لكن T1 قرأ القيمة التي كتبها T2 لـ B في S3.
3. فشل الشرط الثالث لتكافؤ العرض لأن T2 قام بالكتابة النهائية لـ B في S1 و S2، لكن T1 قام بالكتابة النهائية لـ B في S3.

لتحليل ما إذا كان جدولان متكافئين من حيث العرض، اكتب كلا الجدولين كقائمة، حيث يمثل رمز كل إجراء شرط التكافؤ الذي ينطبق عليه. يكون الجدولان متكافئين من حيث العرض إذا وفقط إذا كانت جميع الإجراءات تحمل نفس الرمز (أو لا تحمل أي رمز) في كلا الجدولين.

• S1: R1(A) _{قراءة أولية} ، W1(A)، R1(B) _{قراءة أولية} ، W1(B)، Com1، R2(A) _{كتابة بواسطة T1} ، W2(A) _{كتابة نهائية} ، R2(B) _{كتابة بواسطة T1} ، W2(B) _{كتابة نهائية} ، Com2
• S2: R1(A) _{قراءة أولية} ، W1(A)، R2(A) _{كتابة بواسطة T1} ، W2(A) _{كتابة نهائية} ، R1(B) _{قراءة أولية} ، W1(B)، Com1، R2(B) _{كتابة بواسطة T1} ، W2(B) _{كتابة نهائية} ، Com2
• S3: R1(A) _{قراءة أولية} ، W1(A)، R2(A) _{كتابة بواسطة T1} ، W2(A) _{كتابة نهائية} ، R2(B) _{قراءة أولية} ، W2(B)، R1(B) _{كتابة بواسطة T2} ، W1(B) _{كتابة نهائية} ، Com1، Com2

يُعتبر الجدول قابلاً للتسلسل العرضي إذا كان مكافئاً عرضياً لجدول تسلسلي آخر. تجدر الإشارة إلى أنه بحكم التعريف، فإن جميع الجداول القابلة للتسلسل المتعارض قابلة للتسلسل العرضي.

لاحظ أن المثال أعلاه (وهو نفسه المثال الوارد في مناقشة قابلية التسلسل المتعارض) قابل للتسلسل للعرض وقابل للتسلسل المتعارض في الوقت نفسه. مع ذلك، توجد جداول قابلة للتسلسل للعرض ولكنها غير قابلة للتسلسل المتعارض: وهي الجداول التي تتضمن معاملة تُجري كتابة عمياء .

المثال أعلاه غير قابل للتسلسل المتعارض، ولكنه قابل للتسلسل العرضي لأنه يحتوي على جدول تسلسلي مكافئ للعرض <T1,|  T2,|  T3>.

بما أن تحديد ما إذا كان الجدول الزمني قابلاً للتسلسل العرضي هو مسألة NP-كاملة ، فإن قابلية التسلسل العرضي لها أهمية عملية ضئيلة.

الجداول غير المتتالية (المعروفة أيضًا باسم "جداول تجنب الإجهاض المتتالي") هي جداول تتجنب الإجهاض المتتالي عن طريق منع عمليات القراءة غير الملتزمة . يحدث الإجهاض المتتالي عندما يتسبب إجهاض معاملة ما في إجهاض معاملة أخرى لأنها قرأت واعتمدت على تغييرات المعاملة الأولى على كائن ما. تحدث القراءة غير الملتزمة عندما تقرأ معاملة ما بيانات من عملية كتابة غير ملتزمة في معاملة أخرى. ^{[ 9 ]}

الأمثلة التالية هي نفسها تلك الواردة في المناقشة حول البيانات القابلة للاسترداد:

في هذا المثال، على الرغم من إمكانية استعادة F2، إلا أن ذلك لا يمنع حدوث عمليات إجهاض متتالية. يتضح أنه في حال إجهاض T1، فسيتعين إجهاض T2 أيضًا للحفاظ على صحة الجدول الزمني، حيث أن T2 قد قرأ بالفعل القيمة غير الملتزم بها التي كتبها T1.

فيما يلي جدول زمني قابل للاسترداد يتجنب الإجهاض المتتالي. مع ذلك، لاحظ أن تحديث A بواسطة T1 يُفقد دائمًا (لأن T1 يتم إلغاؤه).

لاحظ أن هذا الجدول الزمني لن يكون قابلاً للتسلسل إذا تم الالتزام بالجدول الزمني T1. يُعد تجنب عمليات الإجهاض المتتالية كافياً، ولكنه ليس ضرورياً، لكي يكون الجدول الزمني قابلاً للاسترداد.

يُعتبر الجدول الزمني صارمًا إذا كان لأي معاملتين T1 و T2، إذا سبقت عملية كتابة في T1 عملية متعارضة في T2 (سواء كانت قراءة أو كتابة)، فإن حدث الالتزام أو الإلغاء في T1 يسبق أيضًا تلك العملية المتعارضة في T2. على سبيل المثال، الجدول الزمني F3 المذكور أعلاه صارم.

أي جدول زمني صارم لا يسمح بتكرار العمليات، ولكن ليس العكس. فالصرامة تسمح باستعادة قواعد البيانات بكفاءة بعد الأعطال.