A Concurrency Control Algorithm Using Serialization Graph Testing with Write Deferring

• Item type: Journal(1)
• 公開日: 1997-10-15
• タイトル: A Concurrency Control Algorithm Using Serialization Graph Testing with Write Deferring
• タイトル / 言語: en
• タイトル: A Concurrency Control Algorithm Using Serialization Graph Testing with Write Deferring
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: データベース
• 著者所属: Faculty of Engineering Science Osaka University
• 著者所属: Faculty of Engineering Science Osaka University
• 著者所属: Faculty of Engineering Science Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Osaka University
• 著者名: Harumasa, Tada; Masahiro, Higuchi; Mamoru, Fujii
• 著者名(英): Harumasa, Tada; Masahiro, Higuchi; Mamoru, Fujii
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Several scheduling algorithms for preserving the consistency of databases have been pro-posed.One of such algorithm is Serialization Graph Testing(SGT).Under SGT a scheduler maintains a graph called a serialization graph(SG).Database consistecy is preserved by ensuring that the SG is acyclic The scheduler checks the acyclicity of the SG for every operation.If the SG comes to contain a cycle the operation is rejected.It is known that SGT achieves higher concurrency than other scheduling algorithms.However it has some drawbacks.First operations are forced to wait for a long time so that the acyclicity of the serialization graph can be checked.Second a phenomenon called cascading aborts may oc-cur;that is one abortion of a transaction may cause other abortions.To deal with the first drawback of SGT we focused on the scheduling algorithm called SGT certification.Under SGT certification a scheduler checks the acyclicity of the SG only once for each transac-tion at its termination.Therefore all operations are executed immediately at the cost of a delay in cycle detection.As regards the second drawback the scheduling method called Optimistic Concurrency Control(OCC)avoids cascading aborts by using internal buffer to defer substantial write operations.However the consistency checking of OCC differs from that of SGT and the concurrency of OCC is not so high.Therefore we applied this write deferment approach to SGT certification.We call our algorithm Serialization Grapa Testing with Write Deferring(SGT-WD).In this paper we present the SGT-WD algorithm and show its correctness.We also evaluate SGT-WD SGT and SGT certification by means of simu-lations on distributed database systems.The simulation results show that SGT-WD is more effective than the others.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Several scheduling algorithms for preserving the consistency of databases have been pro-posed.One of such algorithm is Serialization Graph Testing(SGT).Under SGT,a scheduler maintains a graph called a serialization graph(SG).Database consistecy is preserved by ensuring that the SG is acyclic,The scheduler checks the acyclicity of the SG for every operation.If the SG comes to contain a cycle,the operation is rejected.It is known that SGT achieves higher concurrency than other scheduling algorithms.However,it has some drawbacks.First,operations are forced to wait for a long time so that the acyclicity of the serialization graph can be checked.Second,a phenomenon called cascading aborts may oc-cur;that is,one abortion of a transaction may cause other abortions.To deal with the first drawback of SGT,we focused on the scheduling algorithm called SGT certification.Under SGT certification,a scheduler checks the acyclicity of the SG only once for each transac-tion,at its termination.Therefore,all operations are executed immediately,at the cost of a delay in cycle detection.As regards the second drawback,the scheduling method called Optimistic Concurrency Control(OCC)avoids cascading aborts by using internal buffer to defer substantial write operations.However,the consistency checking of OCC differs from that of SGT,and the concurrency of OCC is not so high.Therefore,we applied this write deferment approach to SGT certification.We call our algorithm Serialization Grapa Testing with Write Deferring(SGT-WD).In this paper,we present the SGT-WD algorithm and show its correctness.We also evaluate SGT-WD,SGT,and SGT certification by means of simu-lations on distributed database systems.The simulation results show that SGT-WD is more effective than the others.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 38, 号 10, p. 1995-2003, 発行日 1997-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764