著者

中津 楢男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.76, no.6, pp.279-287, 1993-06-25

被引用文献数

3

---

本論文ではデータベースの並行制御に関する直列化可能性理論を扱っている.一般に与えられた実行履歴が直列化可能かどうかの判定はNP完全であることが知られており,直列化可能な実行履歴の部分集合で多項式時間で判定できるクラスがいくつか知られている.こうしたクラスは実際のスケージューラの構成に利用できるほか,任意のスケジューラの能力の上界を与える点から注目されている.本論文では直列化可能性判定のための新しい概念を与える.この概念によれば,直列化可能性判定が明解になるばかりでなく,これまで知られている主な結果を含んだより一般的な定理を証明できる.次にこの定理に基づいて,多項式時間で認識できる,従来知られているより広いクラスをいくつか提案する.最後に多項式時間で動作する先読みスケジューラが存在するかどうかの判定にもこの概念が適用できることを示し,そのような先読みスケジューラが存在するより広いクラスを与える.