拡張可能データベース管理システムの問合せ最適化に関する研究

拡張可能データベースシステムの拡張データ型としてXMLデータを扱う型に着目し、問合せの書き換えによる最適化機構について研究を行なった。まずXMLデータを従来の関係データやオブジェクト指向データベースで用いられてきた述語論理に基づいてモデル化した。ここでXMLデータのエレメント名が述語名として内容データがその定義域として自然にモデル化される。XMLデータに関する問合せ言語はW3Cでその標準化が進められており、その問合せ記述能力としてエレメント名に対する問合せが要求されている。これは上記のモデル化において、問合せを述語論理表現した場合高階論理となる。このような記述能力を有する問合せの書き換え方式として、マジックに基づく書き換え方式を採用した。これまでマジックは再帰問合せの不動点計算に対して有効に働くと見られてきたが、近年になって非再帰問合せに対してもその有効性が見出されてきたからであり、その有益性は商用の関係データベースに採用されているほどである。この書き換え規則を適用するにあたって、問合せが高階論理となる点に留意した。そこで、構文規則は高階であるがその意味が一階であり、健全で完全な証明手続きを有する論理としてHiLogで記述することにした。これによりマジックに基づく問合せ最適化が可能となった。但し、書き換えコストの効率化と実際の問合せ言語であるXQueryとの対応付けは今後の課題となっている。

拡張可能データベースシステムの拡張データ型としてXMLデータを扱う型に着目し、問合せの書き換えによる最適化機構について研究を行なった。まずXMLデータを従来の関係データやオブジェクト指向データベースで用いられてきた述語論理に基づいてモデル化した。ここでXMLデータのエレメント名が述語名として内容データがその定義域として自然にモデル化される。XMLデータに関する問合せ言語はW3Cでその標準化が進められており、その問合せ記述能力としてエレメント名に対する問合せが要求されている。これは上記のモデル化において、問合せを述語論理表現した場合高階論理となる。このような記述能力を有する問合せの書き換え方式として、マジックに基づく書き換え方式を採用した。これまでマジックは再帰問合せの不動点計算に対して有効に働くと見られてきたが、近年になって非再帰問合せに対してもその有効性が見出されてきたからであり、その有益性は商用の関係データベースに採用されているほどである。この書き換え規則を適用するにあたって、問合せが高階論理となる点に留意した。そこで、構文規則は高階であるがその意味が一階であり、健全で完全な証明手続きを有する論理としてHiLogで記述することにした。これによりマジックに基づく問合せ最適化が可能となった。但し、書き換えコストの効率化と実際の問合せ言語であるXQueryとの対応付けは今後の課題となっている。