WEKO3
アイテム
動的Blocked Warshall法による推移的閉包アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32701
https://ipsj.ixsq.nii.ac.jp/records/327012e3d8097-0c60-4ae1-aad0-55455907b5ac
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL89011004.pdf (952.0 kB)
|
Copyright (c) 1989 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1989-10-24 | |||||||
| タイトル | ||||||||
| タイトル | 動的Blocked Warshall法による推移的閉包アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | The Algorithm for The Transitive Closure by The Dynamic Blocked Warshall Algorithm | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 北海道大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 北海道大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 北海道大学工学部情報工学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Engineering, Faculty of Engineering, Hokkaido University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Engineering, Faculty of Engineering, Hokkaido University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Engineering, Faculty of Engineering, Hokkaido University | ||||||||
| 著者名 |
舘下直純
× 舘下直純
|
|||||||
| 著者名(英) |
Naosumi, Tateshita
× Naosumi, Tateshita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 関係データベースの分野における再帰質問処理は、最終的に関係の推移的閉包を求めるものが多い。その推移的閉包を求めるアルゴリズムの一つに動的Blocked Warshall法がある。しかしながら、従来の動的Blocked Warshall法では使用者自身が前もって分割を与えなければならない。本報告では、分割を自動的に決め二次記憶へのアクセスをできるたけ少なくする”改訂動的Blocked Washall法”を提案する。また、提案する方法と従来の方法を実験により比較し、その有効性を確認する。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper, we present a new algorithm for computing the transitive closure of database relations. The algorithm is a revised version of Dynamic Blocked Warshall Algorithm. The proposed algorithm minimizes I/O traffic, and there is no need to create partitions ahead of time. We also present simulation results that show that this proposed algorithm perform uniformly better than the Dynamic Blocked Warshall Algorithm. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1989, 号 89(1989-AL-011), p. 1-8, 発行日 1989-10-24 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
