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

可扩展数据库管理系统查询优化研究

基本信息

批准号：
12780250
负责人：
加藤弘之
金额：
$ 1.34万
依托单位：
National Institute of Informatics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

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

专注于将XML数据作为扩展数据库系统中的扩展数据类型处理的类型，我们通过重写查询进行了对优化机制的研究。首先，XML数据是根据常规关系数据和面向对象数据库中使用的谓词逻辑进行建模的。在这里，XML数据的元素名称自然建模为谓词名称，并且内容数据作为其域。 XML数据的查询语言的标准化在W3C中正在进行中，并且需要查询元素名称作为其查询描述功能。在上面的建模中，当查询以谓词逻辑表示时，这是高阶逻辑。基于魔术的重写方法已被用作具有此类写作功能的重写查询的方法。到目前为止，魔术已经有效地用于递归查询的固定点计算，但是近年来也发现了其有效性，用于非恢复查询，其实用性很高，以至于在商业关系数据库中已采用。在应用此重写规则时，我们注意到查询是高阶逻辑。因此，我们决定将HILOG中的语法规则写为高级但具有第一级含义的逻辑，并具有声音和完整的证明过程。这使得基于魔术优化查询成为可能。但是，提高重写成本的效率并将其与Xquery（实际查询语言）匹配是一个挑战。