単項制約を含む集合制約質問を処理するための従属性の計算

概要

論文の詳細を見る
データベースに対し、高水準の検索機能の実現を試みる場合、高水準化に伴う計算量の増大に対処しなければならない。データベースのデータ量は一般に大きいため、質問はデータベースサイズの多項式時間で計算される必要がある。集合制約質問は、基底関係の中から与えられた制約を満たす部分集合を見つけ出す質問である。文献[2]では、多項式時間で処理可能な質問のクラス、およびNP完全のクラスを示している。またNP完全の質問でも、基底関係に関数従属性(FD)や結合従属性(JD)が存在する場合には、これらを用いて多項式時間で処理する方法を求めた。文献[3]では、解は必ず与えられた条件を満たす組を含まなければならないという存在制約や、解の全ての組は条件を満たさなければならないという全称制約からなる単項制約を含む質問の処理法を示した。[2]と[3]の方法を組み合わせる場合、単項制約により基底関係の従属性が破壊され、効率的処理法を適用できなくなるという問題が生じる。本稿では、従属性が破壊されないための質問の制約に対する条件を考察する。一般に与えられた関係代数式が満たす全ての従属性をFDとJDのクラスで表現することはできないが、本稿では基底関係の従属性が質問処理の過程で保存されるかに注目し、しかも集合差演算を含む場合を考察する。
一般社団法人情報処理学会の論文
1990-03-14

単項制約を含む集合制約質問を処理するための従属性の計算

スポンサーリンク

概要

著者

関連論文

スポンサーリンク