シグネチャファイルによる集合値検索のコスト評価

石川 佳治 (筑波大学 工学研究科),
北川 博之 (筑波大学 電子・情報工学系),
大保 信夫 (筑波大学 電子・情報工学系),

情報処理学会第94回データベースシステム研究会,1993年7月.



概要

集合データは基本的なデータ構造であり、複合オブジェクトの部分構造として も頻繁に現れる。 このため、集合値に関する検索条件を効率よく支援する索引機構は、高度な応 用分野を対象としたデータベースシステムにおいて重要なものとなる。 筆者らは、従来テキスト検索で用いられてきたシグネチャファイルを集合値検 索に適用することを提案し、コスト評価、および効率的な問い合わせ処理方式 などについて議論を行なってきた。

これまでの議論は比較的小規模のデータベースを対象として きたが、本論文ではその議論をさらにすすめ、中規模のデータベースにおける シグネチャファイルのコスト評価を行なう。 シグネチャファイルの構成手法としてはビットスライストシグネチャファイル (bit-sliced signature file, BSSF) を対象とし、入れ子型インデックス (nested index) との比較を行なう。 中規模のデータベースにも対応できるよう、従来のコストモデルを拡張し、検 索コスト、記憶コスト、更新コストを評価する。 また、ビットスライストシグネチャファイルを圧縮した場合のコストについて も考察を行ない、圧縮を用いたシグネチャファイルが、中規模のデータベース における集合値検索機構として有望であることを示す。


Cost Evaluation of Set-valued Object Retrieval with Signature Files

Yoshiharu Ishikawa (Doctoral Degree Program in Engineering, University of Tsukuba),
Hiroyuki Kitagawa (Institute of Information Sciences and Electronics, University of Tsukuba)
and
Nobuo Ohbo (Institute of Information Sciences and Electronics, University of Tsukuba)

Abstract

Set-valued data is a primitive data object and appears as sub-structures in complex objects. Therefore, access facilities which can support set-valued object retrieval become important for databases supporting advanced application areas. We have proposed the use of signature files for efficient set-valued object retrieval, and studied their performance and efficient query processing strategies for relatively small databases.

In this paper, we evaluate the efficiency of signature files applied to medium-scale databases. As a signature file organization, we use the bit-sliced signature file (BSSF) and compare its performance with that of the nested index. We extend the cost model of two set access facilities for small-scale databases, and evaluate retrieval costs, storage costs, and update costs of signature files. Then we consider the compressed BSSF and indicate that the compressed BSSF is promising for set-valued retrieval in medium-scale databases.


意見・要望がありましたら、 もしくは
ishikawa@kde.is.tsukuba.ac.jp
もしくは
kitagawa@is.tsukuba.ac.jp
までお願いします。

[BACK]1993年のリストへ戻る
[BACK]全体のリストへ戻る