多版モデルにおける並行処理制御のための先読みスケジューラ

• Item type: SIG Technical Reports(1)
• 公開日: 1986-07-21
• タイトル: 多版モデルにおける並行処理制御のための先読みスケジューラ
• タイトル / 言語: en
• タイトル: Multiversion Cautious Schedulers for Database Concurrency Control
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸商科大学管理科学科
• 著者所属: 京都大学工学部数理工学科
• 著者所属: サイモンフレーザー大学計算科学科
• 著者所属(英): en
• 著者所属(英): Dept. of Management Science, Kobe Univ. of Commerce, Tarumi, Kobe, Japan
• 著者所属(英): en
• 著者所属(英): Dept. of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan
• 著者所属(英): en
• 著者所属(英): Dept. of Computing Science, Simon Fraser University, Burnaby, B.C., Canada
• 著者名: 加藤, 直樹; 茨木, 俊秀; 亀田, 恒彦
• 著者名(英): Naoki, Katoh; Toshihide, Ibaraki; Tiko, Kameda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: これまで単版モデルにおけるデータベーストランザクションの並行処理制御のための先読みスケジューラーが提案されその特性が明らかになってきた。本報告では、それを多版モデルに拡張しその優れた性質について述べる。単版モデルと同様に各トランザクションはあらかじめ読み取りあるいは書き込みを行うデータ項目を宣言しておく必要がある。先読みスケジューラーCSm(MC)はそれらの宣言された情報にもとずいて多版モデルにおける直列可能スケジュールのクラスMCに属するスケジュールを出力する。スケジューラーの中心部分の完成テストは、MC=MWW又はMWRWに対し多項式時間で実行できる。（単版モデルではWRWの完成テストは一般にNP完全。）そして宣言された操作の取消が起こっても正常に動作し，さらにMC=MWWにおいては、読み取り操作の追加が途中で生じても正常に動作する。これは単版モデルのスケジューラーにない優れた特徴である。またその並行処理能力は単版モデルのスケジューラーより高いことも示される。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper deals with multiversion cautious transaction schedulers for database concurrency control. As assumed in single-version cautious schedulers, each transaction, on arrival, predeclares its read and write sets. The multiversion cautious scheduler CSm(MC) reorders incoming requests from transactions in such a way that its output sequence belongs to MC, and it never resorts to rollbacks. We show that the completion test, which is the central part of the scheduler, can be done in polynomial time for MC=MWW and MWRW, while the WRW completion test is in general NP-complete in the single-version scheduler. It is also shown that multiversion cautious schedulers do not have cancellation anomalies, and that CSm(MWW) does not even have augmentation anomaly. Finally it is shown that in almost all cases, CSm(MC) allows more concurrency than the corresponding single-version scheduler, if concurrency is measured in terms of its fixed point set.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 1986, 号 48(1986-DBS-054), p. 1-8, 発行日 1986-07-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会