XML Transformation Language Based On Monadic

XML Transformation Language
Based On
Monadic Second Order Logic
東京大学情報理工学系研究科コンピュータ科学専攻
細谷研究室稲葉一浩
本研究の内容

XML変換言語 MTran の設計と実装
{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} ]
}]}

MTran の特徴



MSO の論理式をXMLへのQuery言語として採用
MSO Query の表現力を活かす変換言語
MSO Query の効率的な評価アルゴリズム
Monadic Second Order Logic

MSO （単項二階論理）
要素そのものを指す一階変数に加え、
要素の集合を指す二階変数を導入した論理
 1950年代から研究されている
 近年、XML処理の理論的基礎として注目

XML処理におけるMSOの利点

強い表現力
1.
2.
3.
4.
全ての Regular Query を表現可能
再帰によらない宣言的な記述
自然な N-ary Query の記述
Queryと無関係な要素への言及が不要
⇒ これらの性質は、XML処理に有用
MSOの表現力1: Regularity

XHTMLの目次作成

『ある要素 x から、文書順で次の
<h1> 要素までの間にある <h2> 要素 y』
•
•
•
•
「xの後ろにある<h2>要素 y」
「xの後ろにある<h1>要素 z」
「zの前にある<h2>要素 y」
それぞれは既存言語(XPath等)
でも書けるが、組み合わせは不可能
x<y & y in <h2> &
all1 z:(x<z & z in <h1> => y<z)
<h1>
... <h2> ....
..... <h2> ..
.... <h3> ...
<h1>
... <h2> ....
.. <h3> .....
<h1>
MSOの表現力2: No-Recursion

LPath[1] Linguistic Queries

『ある構文解析のステップで、要素xの“直後”
にくるような要素y 』 S
VP
NP
PP
NP
N
“I”
V
Det Adj
NP
N Prep Det
“saw” “the” “old” “man” “with”
“a”
N
N
“dog” “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:
x as ~[Any, foo[Any], Any]
• MSO:
• “Any” のようなワイルドカードも不要
ex1 c: (x/c & c in <foo>)
変換言語 MTran の設計
MSO Queryによって
従来より自由度の高いノード抽出が可能になった
 その表現力を活かすXML変換記述言語は？

Query
加工･出力
MSO
???
変換言語の設計

MSO Query の特徴

No-Recursion
• 親子関係をたどるのではない宣言的なノード選択
• 変換でも明示的な再帰を不要に ⇒ “visit” テンプレート

N-ary Queries
• 「カレントノードと、そこから相対的な条件を満たす
ノード」以上に複雑な依存関係の記述
• ⇒ テンプレート・変数スコープのネスト
“visit” テンプレート
全ノードに適用

MTran:
{visit x :: x in <a> :: b[x]}

XSLT:
再帰適用を明示
<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:template>
</xsl:stylesheet>
テンプレートのネスト

MTran:
テンプレートのネスト
変数スコープのネスト
{visit x :: x in <div> ::
{visit y from x :: y in <selflink> ::
@href[{gather z :: x/z:@id :: z}]}}

XSLT:
フラットなテンプレート
明示的な引数渡し
<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
Product
O(t+s) Queryアルゴリズム(概要)
&
Union
解の候補
q1→{(_,v4)(v5,_)(_,v5)(_,v2)(v2,_)(v2,v2)}
Product
q2→{(_,_)(v4,_)(v5,v5)(v2,v2)
...} v1
&
q3→{(v4,v4)(v5,v4)(v2,v5)(v5,v2)
...}
Union
解の候補
q1→{(_,v3)}
q2→{(v3,_)}
q3→{(v3,v3)}
解の候補
解の候補
q1→{(_,_)(_,v4)}
q1→{(v5,_) (_,v5)}
解の候補
v2
v3
q2→{(v4,_)}
q2→{(v5,v5)}
q1→{(_,v1)(v1,v5)(_,v4)(v4,v5)(v2,v1)
q3→{(v4,v4)}
q3→{(_,_)}
(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)
v4
v5
(v2,v3)(v3,v2)(v5,v1)(v4,v2)...}
・途中の集合演算(Product, Union)を遅延処理
・ただし空集合の演算は毎回処理
関連研究 (XML変換言語)

fxgrep, fxt [Berlea et al. 2001]


“既知の最良アルゴリズム”で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仕様への完全対応


静的型検査



名前空間、文字列処理
ツリーオートマトンに基づくXMLの型検査は既に広く利
用されている
“visit” テンプレートの型検査手法の研究
“move” 変換

XML文書中でノードを”移動”する変換のスマートな記述

Download Report