オブジェクト指向データベースにおける問い合わせプログラムの型検査法の開発

本研究によって以下の成果を得た.1. 無閉路OODBスキーマに対する型検査問題の計算複雑さ型検査問題が決定可能となる実用的な部分クラスとして,無閉路OODBスキーマというクラスを提案した.無閉路OODBスキーマとは,そのデータベースインスタンスが必ず無閉路グラフで表現できるクラスであり,例えば機械の部品関係を表すデータベースなどがこのクラスに属する.本研究では,無閉路OODBスキーマに対する型検査問題がco非決定性指数時間完全であることを示した.現在発表準備中である.また,更新操作のない無閉路OODBスキーマに対する型検査問題がPSPACE完全であるという予想をたてており,現在その証明を行っている.2. OODBセキュリティへの型検査問題の応用データベースのユーザが,実行を許可された問い合わせプログラムのみを用いて,それらの実行結果から(極秘な)情報を推論することを,推論攻撃と呼ぶ.データベーススキーマの設計やアクセス権の設定を行う際に,極秘情報が推論攻撃により漏洩する可能性があるかどうかをあらかじめ設計者が知ることができるかどうかは,データベースのセキュリティの保全を計る上で極めて重要な問題である.本研究では,型検査問題の計算量に関する既知の結果を利用して,OODBに対する推論攻撃について以下の結果を得た.・与えられたデータベースインスタンスのもとで,与えられた極秘情報が推論攻撃によって漏洩し得るかどうかは,極めて非実用的な特殊な場合を除いて,多項式時間で解くことができる.・与えられた極秘情報が推論攻撃によって漏洩し得るようなデータベースインスタンスが存在するかどうかは,一般に決定不能である.

本研究によって以下の成果を得た.1. 無閉路OODBスキーマに対する型検査問題の計算複雑さ型検査問題が決定可能となる実用的な部分クラスとして,無閉路OODBスキーマというクラスを提案した.無閉路OODBスキーマとは,そのデータベースインスタンスが必ず無閉路グラフで表現できるクラスであり,例えば機械の部品関係を表すデータベースなどがこのクラスに属する.本研究では,無閉路OODBスキーマに対する型検査問題がco非決定性指数時間完全であることを示した.現在発表準備中である.また,更新操作のない無閉路OODBスキーマに対する型検査問題がPSPACE完全であるという予想をたてており,現在その証明を行っている.2. OODBセキュリティへの型検査問題の応用データベースのユーザが,実行を許可された問い合わせプログラムのみを用いて,それらの実行結果から(極秘な)情報を推論することを,推論攻撃と呼ぶ.データベーススキーマの設計やアクセス権の設定を行う際に,極秘情報が推論攻撃により漏洩する可能性があるかどうかをあらかじめ設計者が知ることができるかどうかは,データベースのセキュリティの保全を計る上で極めて重要な問題である.本研究では,型検査問題の計算量に関する既知の結果を利用して,OODBに対する推論攻撃について以下の結果を得た.・与えられたデータベースインスタンスのもとで,与えられた極秘情報が推論攻撃によって漏洩し得るかどうかは,極めて非実用的な特殊な場合を除いて,多項式時間で解くことができる.・与えられた極秘情報が推論攻撃によって漏洩し得るようなデータベースインスタンスが存在するかどうかは,一般に決定不能である.