タプル間の依存関係を表現できる確率的データベースモデルの提案

財部 倫孝 (9851060)


確率的データベースとは,確率的な事象や知識,情報を表すことができるデータベースのことであり,このようなデータベースモデルは幾つか提案されている. 従来の確率的データベースモデルでは,確率は要素ごと,あるいはタプルごとに付加するという方法を用いており,さらに要素間やタプル間に依存関係はないと仮定されている. しかし,このようなモデルでは,例えば「二つのタプルがともに存在しない確率は0である.」という情報を表現することができない.

そこで本研究では,このようなタプル間の依存関係を表現できるような確率的データベースモデルを提案する. このモデルは Imielinski らによって提案された条件付きテーブル(conditional table)を基本的枠組とし,条件付きテーブル中に現れる各変数を確率変数として扱うことにより定義される.

また,提案したモデルに対して,与えられたタプルの存在確率を求めるという,確率的な質問について考察し,その質問を解くための計算量や,効率良くその質問を解くための制約条件を示す.

発表手順としては,まず従来のモデルを幾つか紹介し,その問題点を示す. 次に条件付きテーブルについて説明し,さらに確率の付加の方法を示して,本研究で提案する確率的データベースモデルの定義を行う. 続いてタプルの存在確率に対する質問について,その定義と質問を解くための計算量を示す. さらに効率良くその質問を解けるような制約条件を示し,最後にまとめを行う.