| 講演名 | 1994/11/17 分散型データベースにおける逐次化グラフを用いたスケジューリングアルゴリズム 多田 知正, 樋口 昌宏, 藤井 護, 奥井 順, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | データベースシステムの無矛盾性を保存するスケジューリングアルゴリズムの多くは,2相ロックまたは時刻印に基づく方法である.これらより高いトランザクションの並行性を達成する方法として,逐次化グラフを用いる方法がある.これは,データベースの逐次化グラフを閉聴がない状態に保つことによって無矛盾性を保証するものである.スケジューラはデータベースに対する操作を実行する前に逐次化グラフを検査し,閉路ができなければその操作の実行を許可し,閉路ができればその操作は拒否されるか,遅延される.この方法の問題点として,逐次化グラフが全域的な構造を持っているため,分散型のスケジューラでは,逐次化グラフを保持するための通信のオーバーヘッドが大きくなることがあげられる.本稿では,逐次化グラフの部分グラフを用いてスケジューリングを行なうアルゴリズムを提案する.この方法を用いることによって,分散型スケジューラにおける通信のオーバーヘッドの増大を防ぐことができる. |
| 抄録(英) | Many scehduling algorithms that preserve database consistency are based on two phase locking or timestamp ordering.Serialization graph testing is a method that achieves higher concurrency of transactions than any of the methods mentioned above.This method preserves database consistency by ensuring that the serialization graph (SG) remains acyclic.The scheduler checks the SG before the exectuion of an operation o,and if o does not bring any cycle to the SG,then o is executed immediately,otherwise o is rejected or delayed.If serialization graph testing is implemented on a distributed scheduler,then the cost of communication to maintain the SG increases because the serialization graph has grobal structure.In this paper,we propose a method using subgraphs of the SG.This method suppresses the communicaioncost in a distributed scheduler. |
| キーワード(和) | 分散型データベース / スケジューリング / 逐次化グラフ |
| キーワード(英) | Distributed database / Scheduling / Serialization graph |
| 資料番号 | SS94-41 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1994/11/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 分散型データベースにおける逐次化グラフを用いたスケジューリングアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Scheduling Algorithm using Serialization Graph Testing for Distributed Database System |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散型データベース / Distributed database |
| キーワード(2)（和/英） | スケジューリング / Scheduling |
| キーワード(3)（和/英） | 逐次化グラフ / Serialization graph |
| 第 1 著者 氏名（和/英） | 多田 知正 / Harumasa Tada |
| 第 1 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Faculty of Engineering Science,Osaka University |
| 第 2 著者 氏名（和/英） | 樋口 昌宏 / Masahiro Higuchi |
| 第 2 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Faculty of Engineering Science,Osaka University |
| 第 3 著者 氏名（和/英） | 藤井 護 / Mamoru Fujii |
| 第 3 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Faculty of Engineering Science,Osaka University |
| 第 4 著者 氏名（和/英） | 奥井 順 / Jun Okui |
| 第 4 著者 所属（和/英） | 松下電器産業研究本部中央研究所 Corporate Research Division,Matsushita Electric Industrial Co.,Ltd. |
| 発表年月日 | 1994/11/17 |
| 資料番号 | SS94-41 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 334 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |