直列化可能性

データベース、トランザクション処理(トランザクション管理)、多くのトランザクショナルなアプリケーション、集中型および分散コンピューティングにおいて、トランザクションスケジュール(履歴)の結果(最終的なデータベースの状態およびデータベースデータの値)がトランザクションを直列的に実行した場合、つまり、時間的な重複無くシリアルに実行した場合と結果が等しい時、直列化可能である、あるいは直列化可能性Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987):  Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, ISBN 0-20110-715-5
 Gerhard Weikum, Gottfried Vossen (2001):  Transactional Information Systems, Elsevier, ISBN 1-55860-508-8 という性質を持っていると言う。トランザクションは通常並列に実行され(時間的に重複があり)、それはこの方法がもっとも効率的であるからである。直列化可能性は並列トランザクションの実行において重要な正確性の判定基準である。トランザクション間の最高のレベルでのトランザクション分離レベルであると考えられ、並行性制御において重要な役割を担っている。そのため、汎用データベースシステムの全てにおいて実装されている。厳密な (Strict) ツーフェーズロック(SS2PL)は1970年代の初期から多くのデータベースシステムにおいて用いられている一般的な直列化可能性機構である。

分散直列化可能性はトランザクショナルな分散システム(例えば分散データベースシステム)のスケジュールの直列化可能性である。インターネット、クラウドコンピューティング、グリッドコンピューティング
、小型で携帯可能な高性能なコンピューティングデバイス(例えばスマートフォン)の普及により、分散アプリケーション間において正確性を保証するための効率的な分散直列化可能性を提供する技術の必要が増している。コミットメント順序付けYoav Raz,  On the Significance of Commitment Ordering - Call for patenting, Memorandum, Digital Equipment Corporation, November 1990. Yoav Raz, US patents 5,504,899  5,504,900   5,701,480 (もしくはコミット順序付け; CO; 1991発表)は一般的な順列化技術であり、異なる(どのような)並列処理管理機構において効率的に分散直列化可能性を実現するものであり、異なる機構による異種混合環境でも適用できる。COは機構の処理に干渉せず、さらに自動的な分散デッドロック解消を保証する。他の分散直列化可能性機能とは違い、COはローカルな並行性制御情報(例えば、ローカルな優先関係、ロック、タイムスタンプ、チケット)の配布を必要とせず、このことがスケーラビリティをもたらし、通常多くのオーバヘッドや遅延を減らすことが出来る。従って、CO(SS2PLのような派生種を含む)は分散直列化可能性のための唯一の既知で効果的な一般的手法である。そして唯一実在しているものである。広く使われているSS2PLはCOの特殊なケースであり、1980年代から複数の(SS2PLベースの)データベースシステム間の分散直列化可能性のためのデファクトスタンダードであり、COの特徴を多く継承している。COは1997年より、トランザクショナルプロセスの研究における分散直列化可能性の実現法として広く活用されている。Heiko Schuldt, Hans-Jo"rg Schek, and Gustavo Alonso (1999): "Transactional Coordination Agents for Composite Systems", In Proceedings of the 3rd International Database Engineering and Applications Symposium (IDEAS’99), IEEE Computer Society Press, Montrteal, Canada, pp. 321--331.Klaus Haller, Heiko Schuldt, Can Tu"rker (2005): "Decentralized coordination of transactional processes in peer-to-peer environments", Proceedings of the 2005 ACM CIKM, International Conference on Information and Knowledge Management, pp. 28-35, Bremen, Germany, October 31 - November 5, 2005, ISBN 1-59593-140-6 近年ではグリッドコンピューティングの実現法Laura Cristiana Voicu, Heiko Schuldt, Fuat Akal, Yuri Breitbart, Hans Jo"rg Schek (2009a):  "Re:GRIDiT -- Coordinating Distributed Update Transactions on Replicated Data in the Grid", 10th IEEE/ACM International Conference on Grid Computing (Grid 2009), Banff, Canada, 2009/10. や、クラウドコンピューティングの実現法Laura Cristiana Voicu and Heiko Schuldt (2009b):  "How Replicated Data Management in the Cloud can benefit from a Data Grid Protocol ― the Re:GRIDiT Approach", Proceedings of the 1st International Workshop on Cloud Data Management (CloudDB 2009), Hong Kong, China, 2009/11. として、COの楽観的な派生種が提案された。

関連項目
 線形化可能性
 一貫性モデル (ソフトウェア)

脚注

Category:データベース
Category:排他制御
Category:トランザクション処理
Category:分散コンピューティング問題

el:Σειριοποιησιμότητα Συγκρούσεων