XML Transformation Language Based On Monadic Second Order Logic 東京大学 情報理工学系研究科 コンピュータ科学専攻 細谷研究室 稲葉一浩

本研究の内容 XML変換言語 MTran の設計と実装 MTran の特徴 MSO の論理式をXMLへのQuery言語として採用 MSO Query の表現力を活かす変換言語 MSO Query の効率的な評価アルゴリズム {visit x :: x in <A> :: Foo[ {visit y from x :: y in <B> & all1 z:(y/z => z in <C>) :: Bar[ {gather z :: y/z :: z} ] }]} 本研究では、新しいXML変換言語MTranを設計し、実装しました。 『細部については後ほど説明しますが』おおまかな雰囲気としてこんな言語です。 MTranの特徴、つまりはこの研究のContributionは、以下の３点になります。 　・ほげ　・ふが　・ぴよ この発表では、この３点について、順に説明します。

Monadic Second Order Logic MSO （単項二階論理） 要素そのものを指す一階変数に加え、 要素の集合を指す二階変数を導入した論理 1950年代から研究されている 近年、XML処理の理論的基礎として注目 XMLからの要求 第一階層いる？

XML処理におけるMSOの利点 強い表現力 ⇒ これらの性質は、XML処理に有用 全ての Regular Query を表現可能 再帰によらない宣言的な記述 自然な N-ary Query の記述 Queryと無関係な要素への言及が不要 「順番にせつめいします」 「これじたいはMSOの既知の性質で、これがXMLに使えることを考えた」ことをいう ⇒ これらの性質は、XML処理に有用

MSOの表現力1: Regularity XHTMLの目次作成 『ある要素 x から、文書順で次の <h1> 要素までの間にある <h2> 要素 y』 「xの後ろにある<h2>要素 y」 「xの後ろにある<h1>要素 z」 「zの前にある<h2>要素 y」 それぞれは既存言語(XPath等) でも書けるが、組み合わせは不可能 <h1> ... <h2> .... ..... <h2> .. .... <h3> ... .. <h3> ..... 論理式をもっとせつめい x<y & y in <h2> & all1 z:(x<z & z in <h1> => y<z)

MSOの表現力2: No-Recursion LPath[1] Linguistic Queries 『ある構文解析のステップで、要素xの“直後”にくるような要素y 』 S VP NP PP NP NP N “I” V “saw” Det “the” Adj “old” N “man” Prep “with” Det “a” N “dog” N “today” [1] Extending XPath to Support Linguistic Queries, Bird et al., PLAN-X 2005

MSOの表現力2: No-Recursion LPath Linguistic Queries XPathでは、表現できない LPathでは、次のようなアルゴリズムでXPathを拡張 xが最右の子なら、親に上る。最右の子でなければ 一個右の兄弟y’に移動。y’の最左の子孫を全て選択 MSOでは二階変数を使って、直接 『ある構文解析のステップで、要素xの“直後”にくるような要素y 』 と書ける pred analysis_step(var2 A) = all1 x:(x notin A  A//x | x//A); pred follow_in(var2 A, var1 x, var1 y) = x in A & y in A & all1 z:(z in A => x<z <=> y<=z); ex2 A: (analysis_step(A) & follow_in(A,x,y))

MSOの表現力3: N-ary Query N-ary Query 『共通の親をもつfoo, bar, buz要素の組』 自由変数が N 個のMSO論理式は、自然に、 N-tuple を探索するクエリとなる ex1 p: (p/x:<foo> & p/y:<bar> & p/z:<buz>)

MSOの表現力4: Don’t Care Regular Expression Patterns と比較して 『<foo>要素を子に持つ要素x』 Patterns: MSO: “Any” のようなワイルドカードも不要 x as ~[Any, foo[Any], Any] Anyがあると困ることがよくわからない ex1 c: (x/c & c in <foo>)

変換言語 MTran の設計 MSO Queryによって 従来より自由度の高いノード抽出が可能になった その表現力を活かすXML変換記述言語は？ Query 加工･出力 一般的にXML処理はこう ぜんたい MSO ???

変換言語の設計 MSO Query の特徴 No-Recursion N-ary Queries 親子関係をたどるのではない宣言的なノード選択 変換でも明示的な再帰を不要に ⇒ “visit” テンプレート N-ary Queries 「カレントノードと、そこから相対的な条件を満たすノード」以上に複雑な依存関係の記述 ⇒ テンプレート・変数スコープのネスト

“visit” テンプレート MTran: XSLT: 全ノードに適用 {visit x :: x in <a> :: b[x]} 再帰適用を明示 <xsl:stylesheet ...> <xsl:template match="a"> <b><a><xsl:apply-templates/></a></b> </xsl:template> <xsl:template match=“@*|node()"> <xsl:copy> <xsl:apply-templates/></xsl:copy> </xsl:stylesheet>

テンプレートのネスト MTran: XSLT: {visit x :: x in <div> :: 変数スコープのネスト MTran: XSLT: {visit x :: x in <div> :: {visit y from x :: y in <selflink> :: @href[{gather z :: x/z:@id :: z}]}} フラットなテンプレート 明示的な引数渡し <xsl:stylesheet ...> <xsl:template match=“div"> <xsl:copy><xsl:apply-templates> <xsl:with-param name=“x” select=“.”/> </xsl:apply-templates></xsl:copy> </xsl:template> <xsl:template match=“selflink”> <xsl:param name=“x”/><xsl:attribute ...> <xsl:value-of select=“$x/@id”/> ... 普通に使う例

MSO Queryの実装 標準的な実装方式 論理式をツリーオートマトンへ変換 ツリーオートマトンを使ってQueryを実行 入力 t 論理式 x in <a> 「各ステップをおりじなーるに工夫しました」 出力 s

MTranでの実装 論理式をツリーオートマトンに変換 ツリーオートマトンを使って実行 MONA[2] を利用 最悪の計算量は超指数的だが、様々な最適化によって実用的な処理時間を達成したシステム XML変換への応用例でも実験・検証を行った ツリーオートマトンを使って実行 遅延評価を用いた O(t+s) アルゴリズム 既存の最善のアルゴリズムは O(tN+s) [2] http://www.brics.dk/mona/ N.Klarlund et al., 1999

O(t+s) Queryアルゴリズム(概要) Product & Union 解の候補 q1→{(_,v4)(v5,_)(_,v5)(_,v2)(v2,_)(v2,v2)} q2→{(_,_)(v4,_)(v5,v5)(v2,v2) ...} q3→{(v4,v4)(v5,v4)(v2,v5)(v5,v2) ...} 解の候補 q1→{(_,v3)} q2→{(v3,_)} q3→{(v3,v3)} Product & Union 解の候補 q1→{(_,_)(_,v4)} q2→{(v4,_)} q3→{(v4,v4)} q1→{(v5,_) (_,v5)} q2→{(v5,v5)} q3→{(_,_)} 解の候補 q1→{(_,v1)(v1,v5)(_,v4)(v4,v5)(v2,v1) (v2,v2)(v3,_)(v3,v3)(v3,v5)(v3,_) (v5,v4)(v1,v2)...} q2→{(_,_)(v4,_)(v5,v5)(v2,v2)} q3→{(v3,v3)(v1,_)(v4,v4)(v2,_)(_,v3) (v2,v3)(v3,v2)(v5,v1)(v4,v2)...} ・途中の集合演算(Product, Union)を遅延処理 ・ただし空集合の演算は毎回処理

関連研究 (XML変換言語) fxgrep, fxt [Berlea et al. 2001] Arb [Koch 2003] “既知の最良アルゴリズム”でBinaryQueryを実装 Arb [Koch 2003] 1-ary MSOと等価な言語をXML Queryに応用 XSLT 1.0 [Clark et al. 1999] XSLT 2.0 (draft) [Kay 2005] 一階論理のexist, forallを導入

まとめ XML変換言語 MTranの設計と実装 MSOの論理式をQuery言語に採用 MSO Queryの表現力を活かす変換言語 “visit” テンプレート テンプレートのネスト MSO Queryの効率的な処理方式 MONAを採用 遅延評価による O(t+s) アルゴリズムを開発 階層

今後の課題 XML仕様への完全対応 静的型検査 “move” 変換 名前空間、文字列処理 “visit” テンプレートの型検査手法の研究 “move” 変換 XML文書中でノードを”移動”する変換のスマートな記述 さっさと