MISC

2005年4月15日

XQuery のソースレベル最適化のための等価変換に関する考察

情報処理学会論文誌プログラミング(PRO)
  • 日高 宗一郎
  • ,
  • 加藤 弘之
  • ,
  • 吉川 正俊

46
6
開始ページ
64
終了ページ
64
記述言語
日本語
掲載種別
出版者・発行元
一般社団法人情報処理学会

XQuery はXML を対象とした関数型問合せ言語であり,式の組合せで問合せが表現されている.本発表では,この言語の関数型としての側面を利用し,共通部分式の削除,式の畳み込み等を通した不要な演算の削除の試みについて扱う.処理の形態としては,XQuery のソースからソースへの等価変換を想定している.XQuery の根幹をなすFLWOR 式はmap ととらえることができる.本発表では,仕様に併記されている形式的意味論を援用しながら,XQuery のデータの基本構造であるシーケンス(以下,列)と,その上でのmap の意味の付与も行う.map の前後にフィルタリングが存在する場合(FLWOR 式ではWhere 節の述語が該当する),意味を変えずにmap をまたいで移動させることによりコストを低減することができる場合がある.本発表では列上でのmap やリダクション演算の基本となる演算子を定義し,その演算子を使って列上のmap を定義する.FLWOR 式はこのmap とフィルタを用いて定義することができる.また,その他の全称,存在限量式等をこの演算子を使って表現する.主な言語構造はラムダ式に変換され,変換の前後の等価性の議論に用いられる.本発表の定式化は集合意味論に基づく先行研究にならい,列が満たす代数的性質の差異に着目して変換規則を再構築している.XQuery is a functional query language for XML. This presentation tries to exploit this functional aspect to deal with traditional redundant computation elimination techniques such as common subexpression elimination and expression folding. XQuery source is transformed into equivalent one that is expected to be evaluated more efficiently. FLWOR expression which is the heart of XQuery can be treated as a map. Formal semantics that is a part of specifications of the language is used as well to describe semantics of sequence which is one of fundamental XQuery data models, and those of map on it. Filtering operations (predicate for Where clause in FLWOR expression, for example) can be moved across maps without changing their semantics, by which overall cost of evaluation can be reduced for underlying implementations. In this presentation, fundamental operator upon which maps and reduction operators on sequences are build is introduced. FLWOR expressions can be defined using this map and filter. Other language constructs such as existentially or universally quantified expressions are defined similarly. Major language constructs are described in terms of lambda expressions for discussing equivalences of expressions before and after transformations. Formulation in this presentation borrows that of preceding paper based on set semantics, and is rebuilt upon different algebraic properties that sequences satisfy.

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/110002769554
CiNii Books
http://ci.nii.ac.jp/ncid/AA11464814
URL
http://id.nii.ac.jp/1001/00016631/
ID情報
  • ISSN : 1882-7802
  • CiNii Articles ID : 110002769554
  • CiNii Books ID : AA11464814

エクスポート
BibTeX RIS