無閉路オブジェクト指向データベーススキーマに対する型検査問題の計算
量
横内 淳史 (9851125)
オブジェクト指向プログラミング言語の本質的な特徴の一つとして，メソッド
呼出し機構が挙げられる．この機構は，データのカプセル化やコードの再利用
のために重要なものであるが，実行時に型エラーが起こる危険性がある．特に，
オブジェクト指向データベース（OODB）の問合せプログラムの場合は，実行時
に型エラーが起こると，ロールバックを行う必要がある．従って，与えられた
OODB スキーマが型整合性をもつこと，すなわち，どんなデータベースインス
タンスのもとでも問合せプログラムの実行中に型エラーが起こらないことを保
証できることが望ましい．
本研究では，Hull らによって提案された更新スキーマを OODB スキーマのモ
デルとして採用する．更新スキーマは，クラス階層，継承，複合オブジェクト
といったオブジェクト指向データベースの基本的な特徴をすべてもつ．
一般に更新スキーマに対する型検査問題は決定不能であることが知られている．
そこで本研究では，無閉路スキーマと呼ばれる更新スキーマの部分クラスを提
案し，型検査問題の決定可能性を示す．更に，無閉路スキーマの二つの部分ク
ラスについても考察する．