資料庫管理系統中一個權序協同控制法

Abstract

資料庫管理系統中提升平行程度(concurrency degree)及確保資料庫系統之資料一 致性(consistence) 一直是頂重要的課題。提供一個有效的協同控制方法即是解決 此一課題之重要法門。多年來在資料庫管理系統中協同控制之研究與發展也不斷推 陳出新。例如，Two-Phase Locking 、Timestamp Ordering、Optimistic Method 及Serialization Graph Testing 等方法即是典型之作。這些方法在資料庫管理系 統之設計發展上也一直是主流。僅管如些，這些方法並不是完美無缺。例如，two- phase locking 方法有發生死鎖 (deadlock) 之可能性； timestamp ordering 方 法有較高的失敗率 (abort rate) ； optimistic method 方法對執行的交互能力 (interleaving ability)較差；而serialization graph testing 方法在維持順序 圖(serialization graph) 的負擔上也較重等問題。 本篇論文即針對上述之問題提出一個新的協同控制方法。此方法稱為P/O method。 此P/O method主要是藉由權序值(precedence)來作同步(synchronization) 控制。 所謂的權序值是transactions間交互執行的過程中transactions的相依關係。藉此 可克服上述方法所存在的缺點及提高系統輸出率(throughput)。為了驗證此一方法 ，此文中針對順序性(serializability) 作了完善的數學證明，也針對其效率作實 驗評估。此驗證結果證明P/O method是正確而優的新方法。