การประมวลผลรายการเปลี่ยนแปลงอย่างเป็นลำดับ

ระบบจัดการฐานข้อมูลสมัยใหม่อนุญาติให้มีการทำรายการเปลี่ยนแปลงหลายรายการพร้อมกันได้ ดังนั้นจึงจำเป็นจะต้องมีการตรวจสอบอยู่เสมอว่าผลลัพธ์ที่เกิดจากการทำงานของรายการเปลี่ยนแปลงเหล่านั้นถูกต้อง ในการที่จะตรวจสอบความถูกต้องของข้อมูลอันเนื่องมาจากการทำงานของรายการเปลี่ยนแปลงนั้น เราสามารถตรวจสอบได้ตั้งแต่ก่อนจะเริ่มทำตามรายการเปลี่ยนแปลง นั่นคือ การตรวจสอบที่ตัวรายการเปลี่ยนแปลงเองว่ามีขั้นตอนการทำงานใดบ้าง และลำดับขั้นตอนการทำงานในรายการเปลี่ยนแปลงนั้นถูกต้องหรือไม่ ถ้าไม่ถูกต้องก็ทำการแก้ไขหรือไม่ทำรายการเปลี่ยนแปลงนั้น

ในการตรวจสอบการทำงานภายในรายการเปลี่ยนแปลงนั้น การทำงานที่สนใจจะมีอยู่เพียงสองรายการเท่านั้น คือ รายการอ่าน (Read) และรายการเขียน (Write) เนื่องจากเป็นรายการที่มีผลกับความถูกต้องของการทำงานโดยตรง รายการอ่านและเขียนที่สนใจขณะใดขณะหนึ่งสามารถเขียนให้อยู่ในรูป Read(M) และ Write(N) เมื่อ M และ N เป็นข้อมูลที่ถูกอ่านหรือเขียน การอ่านและเขียนที่เหล่านี้สามารถถูกจัดลำดับใหม่ได้แต่ต้องอยู่ภายใต้เงื่อนไขต่อไปนี้

1. การจัดลำดับโดยการสลับกันอย่างสมดุล (Conflict serializability)

2. การจัดลำดับโดยใช้ผลลัพธ์เสมือน (View serializability)

ระบบจัดการฐานข้อมูลสามารถจัดลำดับการทำงานของรายการเปลี่ยนแปลงใหม่ แต่ยังคงให้ผลการทำงานที่สมดุลกับลำดับเดิม โดยพิจารณาจากลำดับการการอ่านและเขียนภายใน ลำดับที่การทำงาน S ประกอบด้วยชุดของรายการเปลี่ยนแปลง T_i และ T_j ซึ่งประกอบไปด้วยลำดับการอ่านและเขียนภายใน ระบบจัดการฐานข้อมูลจะสลับ Operation(M)_i และ Operation(N)_j ถ้า M และ N คือข้อมูลคนละตัวกัน และรักษาลำดับเดิมของ Operation(M)_i และ Operation(N)_j เอาไว้ถ้า M และ N คือข้อมูลตัวเดียวกัน การสลับลำดับการทำงานของรายการเปลี่ยนแปลงที่ใช้กระทำบนข้อมูลตัวเดียวกันมีหลักการดังนี้

1. ถ้าชนิดของการกระทำเป็นการอ่านทั้งคู่ เช่น Read(M)_i และ Read(M)_j สามารถสลับได้ทันทีและจะสลับให้ Read(M)_i หรือ Read(M)_j เริ่มก่อนก็ได้

2. ถ้าชนิดของการกระทำเป็นการเขียนทั้งคู่ เช่น Write(M)_i และ Write(M)_j การกระทำทั้งสองไม่มีผลกระทบต่อกันโดยตรงแต่ละมีผลกระทบต่อการอ่านที่ตามมา ดังนั้นจึงไม่สามารถสลับได้

3. ถ้าชนิดของการกระทำเป็นการอ่านก่อนการเขียน เช่น Read(M)_i และ Write(M)_j แล้ว T_j จะต้องเขียนข้อมูลหลังจาก T_i อ่าน M ไปแล้วเท่านั้น และ T_i จะไม่อ่านข้อมูลที่เขียนโดย T_j

4. ถ้าชนิดของการกระทำเป็นการเขียนก่อนการอ่าน เช่น Write(M)_i และ Read(M)_j แล้ว T_j จะต้องอ่านข้อมูลหลังจาก T_i เขียน M ไปแล้วเท่านั้น และ T_i จะต้องเขียนข้อมูลก่อนที่ T_j จะอ่านค่า M ไป

การกระทำบนข้อมูลตัวเดียวกันจากรายการเปลี่ยนแปลงคนละชุด และมีการกระทำอย่างน้อยหนึ่งอย่างเป็นการอ่าน เรียกว่า Conflict Operation การกระทำบนข้อมูลคนละตัวกันไม่เรียกว่าเป็น Conflict Operation ดังนั้นในการสลับตำแหน่งการทำงานกับข้อมูลจะพิจารณาจาก Non-Conflict Operation นั่นคือ การกระทำบนข้อมูลคนละตัวกัน หรือ การอ่านข้อมูลตัวเดียวกัน สามารถสลับตำแหน่งการกระทำได้ ลำดับใหม่ที่ได้การสลับลำดับ S โดยพิจารณาจาก Non-Conflict Operation ในที่นี้จะเรียกว่าลำดับ S เสมือน หรือ Conflict Serializability

ตัวอย่างของลำดับที่เป็น Conflict Serializability แสดงได้ดังลำดับต่อไปนี้

ลำดับที่ 1

ลำดับที่ 2 คือลำดับที่เกิดจากการสลับตำแหน่งของการกระทำในลำดับที่ 1 โดยการสลับ Write(A) ของรายการเปลี่ยนแปลงที่ 2 และ Read(B) ของรายการเปลี่ยนแปลงที่ 1 จากลำดับที่ 2 จะเห็นว่ามีการกระทำอีกหลายคู่ที่เป็น Non-Conflict Operation และสามารถสลับกันได้ เช่น

Read(A) ของรายการเปลี่ยนแปลงที่ 2 และ Read(B) ของรายการเปลี่ยนแปลงที่ 1 เมื่อสลับแล้วจะได้ลำดับที่ 3

จากลำดับที่ 3 สลับ Write(A) ของรายการเปลี่ยนแปลงที่ 2 และ Write(B) ของรายการเปลี่ยนแปลงที่ 1 เมื่อสลับแล้วจะได้ลำดับที่ 4

จากลำดับที่ 4 สลับ Read(A) ของรายการเปลี่ยนแปลงที่ 2 และ Write(B) ของรายกการเปลี่ยนแปลงที่ 1 เมื่อสลับแล้วจะได้ลำดับที่ 5

ลำดับที่ 3

ลำดับที่ 4

ลำดับที่ 5

รายการเปลี่ยนแปลงบางชุดไม่สามารถจัดลำดับโดยใช้การสลับกันได้เนื่องจากตำแหน่งของการกระทำเป็นเรื่องสำคัญ ในรายการเปลี่ยนแปลงแบบนี้จะยึดถือที่ผลลัพธ์จากการทำรายการเปลี่ยนแปลงเป็นสำคัญ ดังนั้นลำดับ S จะมีลำดับ S เสมือนเมื่อให้ผลลัพธ์การทำงานที่เหมือนกัน (View Serializability) ในการพิจารณาลำดับการทำงานสองลำดับว่าให้ผลลัพธ์ที่เหมือนกันหรือไม่ สามารถพิจารณาได้จากเงื่อนไข 3 ข้อด้วยกัน คือ

---

3.1 การกู้คืน 3.2 การประมวลผลรายการเปลี่ยนแปลงอย่างเป็นลำดับ 3.3 การจัดลำดับการทำงานของรายการเปลี่ยนแปลง