オブジェクト指向データベースにおける型整合性判定問題の決定不能性に ついて

清水 將吾 (9651057)


内容梗概

オブジェクト指向プログラミング言語の本質的な特徴の一つとして,メソッド 呼出し機構が挙げられる.この機構は,データのカプセル化やコードの再利用 のために重要なものであるが,実行時に型エラーが起こる危険性がある.特に, オブジェクト指向データベース(OODB)の問合せプログラムの場合は,実行時 に型エラーが起こると,ロールバックを行う必要がある.従って,与えられた OODB スキーマが型整合性をもつこと,すなわち,どんなデータベースインス タンスのもとでも問合せプログラムの実行中に型エラーが起こらないことを保 証できることが望ましい.

本研究では,Hull らによって提案された更新スキーマを OODB スキーマのモ デルとして採用し,(1)停止性を満たすスキーマに対する型整合性判定問題, および,(2)メソッド定義中に更新操作がないスキーマに対する型整合性判 定問題問題がいずれも決定不能であることを示す.

発表の概要

  1. 背景
  2. 型整合性判定問題
  3. OODB のモデル
  4. データベーススキーマの定義
  5. 更新スキーマの構文
  6. 継承
  7. データベースインスタンス
  8. 型エラー
  9. 更新スキーマの型整合性判定問題に関する既知の結果
  10. 本研究で示す結果
  11. 証明の方針
  12. まとめと今後の課題