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

• Item type: Trans(1)
• 公開日: 2005-04-15
• タイトル: XQuery のソースレベル最適化のための等価変換に関する考察
• タイトル / 言語: en
• タイトル: On a Set of Equations for XQuery Source Level Transformation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 国立情報学研究所
• 著者所属: 国立情報学研究所
• 著者所属: 名古屋大学情報連携基盤センター
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Information Technology Center Nagoya University
• 著者名: 日高, 宗一郎; 加藤, 弘之; 吉川, 正俊
• 著者名(英): Soichiro, Hidaka; Hiroyuki, Kato; Masatoshi, Yoshikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: XQuery はXML を対象とした関数型問合せ言語であり，式の組合せで問合せが表現されている．本発表では，この言語の関数型としての側面を利用し，共通部分式の削除，式の畳み込み等を通した不要な演算の削除の試みについて扱う．処理の形態としては，XQuery のソースからソースへの等価変換を想定している．XQuery の根幹をなすFLWOR 式はmap ととらえることができる．本発表では，仕様に併記されている形式的意味論を援用しながら，XQuery のデータの基本構造であるシーケンス（以下，列）と，その上でのmap の意味の付与も行う．map の前後にフィルタリングが存在する場合（FLWOR 式ではWhere 節の述語が該当する），意味を変えずにmap をまたいで移動させることによりコストを低減することができる場合がある．本発表では列上でのmap やリダクション演算の基本となる演算子を定義し，その演算子を使って列上のmap を定義する．FLWOR 式はこのmap とフィルタを用いて定義することができる．また，その他の全称，存在限量式等をこの演算子を使って表現する．主な言語構造はラムダ式に変換され，変換の前後の等価性の議論に用いられる．本発表の定式化は集合意味論に基づく先行研究にならい，列が満たす代数的性質の差異に着目して変換規則を再構築している．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 46, 号 SIG6(PRO25), p. 64-64, 発行日 2005-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会