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

用于演绎面向对象数据库的存储高效数据结构

基本信息

批准号：
07780280
负责人：
岩井原瑞穂
金额：
$ 0.64万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

项目摘要

本研究は、演繹オブジェクト指向データベース(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については、二次記憶格納方式を考案し、その処理系を実装した。そして演繹データベース質問処理について評価を行なった。

这项研究旨在开发高度记忆有效的数据结构，以实现针对对象的数据库（DOOD）。为此，我们专注于二进制决策图（BDD），该图引起了逻辑结构CAD领域的关注，并以此作为关系的内存结构进行了检查。该方法涉及将关系编码为逻辑函数，并将其视为BDD，这有要考虑的问题。此外，先前的研究表明，在基于BDD的编码方法中，在理论上无法超过表达大小的限制。为了克服这一限制，我们提出了Patrica BDD作为适合数据库的新数据结构。我们还实施并评估了先前提出的基于BDD的编码方法。（1）Patricia BDD：Patricia BDD的定义和理论分析定义为DOOD代替BDD的存储效率数据库结构，并分析了其最差的记忆大小。（2）效率分析：我们使用日志/线性编码和Patricia BDD评估了BDD的存储和操作效率，以及主存储数据库中各种参数的计算效率，并揭示了这些BDD型数据结构有效的情况。（3）支持二次内存的系统：对于基于线性编码的BDD，设计了二次内存存储方法，并实现了处理系统。然后，评估了演绎数据库问题处理。