データベースの集合制約質問およびその処理法

概要

論文の詳細を見る
データベースに対する質問の答えは,条件を満たす組の集合であることが多い.これに対して,答えが条件を満たす集合,または組合せの集合であるような質問が考えられる.この質問では,集合全体として条件を満たし,集合としてまとめられたとき,初めて意味を持つような組合せを求めることができる.このような質問を,本稿では集合制約質問と呼ぶ.データベース理論において,集合が陽に構成要素として扱われる例として,オブジェクト指向データベースや,非正規関係などが挙げられる.これらにおいて,集合の構造は静的にスキーマとして扱われることが多く,集合制約質問のように動的に集合を生成する機能についてはあまり考慮されていない.また,NEST/UNNEST操作では,求めたい組合せの条件を記述するには,表現力が不足する.本稿で考察する集合制約質問は,反射的かつ対称的な関係の組集合上の二項関係が,条件として与えられ,その数学的性質から導かれる集合が解となる.二項関係を質問に用いた例として[3]があるが,集合を生成する質問に用いた文献は見あたらない.組合せを求める質問においては,例えば最適配置問題のように最大要素数の組合せの解が必要となることが多い.最大要素数の解が,常に関係の組数の多項式時間で求められる質問のクラスが,明かにされることは重要である.本稿では,条件が関数従属性(FD)の集合で表される集合制約質問を考え,FDが2つの場合の多項式時間アルゴリズムを与える.また,FDが3つ以上の場合はNP完全になることも示す.
1989-03-15

データベースの集合制約質問およびその処理法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク