演繹オブジェクト指向データベースのための記憶効率のよいデータ構造

点击翻译按钮获取中文摘要

本研究は、演繹オブジェクト指向データベース(Deductive Object-Oriented Databases;DOOD)のための記憶効率の良いデータ構造の開発を目的としている。そのために、論理構造CADの分野で注目されている二分決定グラフ(Binary Decision Diagram;BDD)に着目し、これを関係の記憶構造として用いることを検討した。この方法では関係を論理関数に符号化し、BDDとして実現するところに考慮すべき課題がある。さらにBDDに基づく符号化法では、理論的に超えられない表現サイズの限界がこれまでの研究で分っている。この限界を克服するために、データベース向きの新たなデータ構造として、Patrica BDDを提案した。またこれまでに提案しているBDDに基づく符号化法についても、実装して評価を行なった。(1)Patricia BDDの定義および理論的解析:BDDに代るDOODのための記憶効率のよいデータベース構造としてPAtricia BDDを定義し、その最悪記憶サイズを解析した。(2)効率の解析:対数/線形符号化を用いたBDD、およびPatricia BDDの記憶効率および演算効率を、主記憶型データベースにおいて、種々のパラメータにおける演算効率・記憶効率を評価し、これらBDD型のデータ構造が有効となる状況を明らかにした。(3)二次記憶に対応したシステム:線形符号化に基づくBDDについては、二次記憶格納方式を考案し、その処理系を実装した。そして演繹データベース質問処理について評価を行なった。