複合オブジェクトモデルにおける逆航行を含む経路式に関する研究

オブジェクト指向データベース(OODB)の基礎となるデータモデルである複合オブジェクトに対して,SC(Specialization Constraint)と呼ばれる属性の型付けに関する制約が知られている。これまでに,SCに関する推論問題(あるSCσがSCの集合Σの論理的帰結であるかどうかを判定する)を解くためのアルゴリズムを開発してきた。複合オブジェクトでは経路式を用いてデータベース内を航行するが,最近,属性の逆航行を経路式に許すOODBの質問言語が提案されており,より高度な質問が表現可能になってきている。本研究では,Σに属するSCに現れる経路式の長さを1以下に限定したとき,次の2つの問題を解くための効率的なアルゴリズムの開発を目標とした。(1)推論問題:属性の順航行及び逆航行が混在する経路式を含む一つのSCσが任意に与えられたとき,σがΣの論理的帰結かどうかを判定する。(2)航行可能性問題:任意のクラスC,及び,属性の順航行及び逆航行が混在する任意の経路式pdに対して,Cに属するオブジェクトからpdで指定された経路に沿って航行できるようなデータベースが存在するかどうかを判定する。上記(1)に関して,推論問題に対する完全な公理系を求めた。次に,その公理系を用いて,推論問題を解くための多項式時間手続きを開発した。同様に,(2)についても,航行可能性問題に対する完全な公理系を求め,それを用いた航行可能性問題を解くための多項式時間手続きを開発した。これらの手続きを利用して,経路式に逆航行を含む質問の型の整合性がコンパイル時に判定可能になる。特に,手間の掛かる質問の場合,実行時にそれらに起因するエラーを避けるために有効であると考えられる。

オブジェクト指向データベース(OODB)の基礎となるデータモデルである複合オブジェクトに対して,SC(Specialization Constraint)と呼ばれる属性の型付けに関する制約が知られている。これまでに,SCに関する推論問題(あるSCσがSCの集合Σの論理的帰結であるかどうかを判定する)を解くためのアルゴリズムを開発してきた。複合オブジェクトでは経路式を用いてデータベース内を航行するが,最近,属性の逆航行を経路式に許すOODBの質問言語が提案されており,より高度な質問が表現可能になってきている。本研究では,Σに属するSCに現れる経路式の長さを1以下に限定したとき,次の2つの問題を解くための効率的なアルゴリズムの開発を目標とした。(1)推論問題:属性の順航行及び逆航行が混在する経路式を含む一つのSCσが任意に与えられたとき,σがΣの論理的帰結かどうかを判定する。(2)航行可能性問題:任意のクラスC,及び,属性の順航行及び逆航行が混在する任意の経路式pdに対して,Cに属するオブジェクトからpdで指定された経路に沿って航行できるようなデータベースが存在するかどうかを判定する。上記(1)に関して,推論問題に対する完全な公理系を求めた。次に,その公理系を用いて,推論問題を解くための多項式時間手続きを開発した。同様に,(2)についても,航行可能性問題に対する完全な公理系を求め,それを用いた航行可能性問題を解くための多項式時間手続きを開発した。これらの手続きを利用して,経路式に逆航行を含む質問の型の整合性がコンパイル時に判定可能になる。特に,手間の掛かる質問の場合,実行時にそれらに起因するエラーを避けるために有効であると考えられる。