論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――

完全な検証を行わずに XML 文書に単純型を付与する方式
Assigning simple types to XML documents
without full validation

村田 真♠
Makoto MURATA

XML データベース検索言語 XQuery は，スキーマに基づいた型情報が XML 文書に付与されていることを前提とする．型情報を付与する処理は，XML スキーマ言語 W3C XML Schemaに基づく検証の一部として行われる．しかし，この方法には
W3C XML Schema 以外のスキーマ言語（とくに RELAX NG）に利用できないという問題点，検証という重い処理が必要になるという問題点がある．これらの問題点を解決するため，検証を行うことなしに単純型だけを付与する方式を提案する．
本方式は,文書が妥当であることを保証せず,複合型も扱わないが,単純型を正しく付与することは保証する.逆に言えば,本方式は妥当でない文書に単純型を付与することができる．
In XQuery, it is assumed that XML documents areaccompanied with type information obtained fromschemas. Assigning type information is done as part ofW3C XML Schema validation. However, this approachhas two problems: (1) other schema languages including
RELAX NG are not supported, and (2) W3C XML
Schema validation, which is very expensive, becomesmandatory. To overcome these problems, this paper
proposes a novel approach for type assignment that does
not require full validation but is restricted to single types.
Although this approach does not ensure validity ofdocuments and cannot handle complex types, it cancorrectly assign simple types. In other words, thisapproach can assign simple types to invalid documents.

1. はじめに
XQuery[1]は，W3Cで制定中のXMLデータベース検索言語である．XQueryが対象とするXML文書は，XML 1.0[2]に規定されているXML文書とは厳密には異なる．すなわち，XML 1.0の構文解析によって得られる木はスキーマに基づく型情報を含まないが，XQueryの検索対象となる木はスキーマに基づく型情報を含む．型情報は，構文解析を行った後に，スキーマ言語W3C XML Schema[3]に基づく検証によって得られる（ただし他の方法が排除されているわけではない）．
型情報は，大きく二つに分かれる．一つは，xsd:intやxsd:booleanのような単純型(simple type)である．XML文書に現れる文字列が，実際にはどんなデータを表しているのかは単純型によって定まる．もう一つは，複合型(complex type)♠である．複合型は，要素がどんな子要素やテキストを持つかについての制約である．W3C XML Schemaでは，複合型宣言(complex type declaration)によって宣言される．
単純型を付与することには，XQuery検索式の信頼性や性能が向上するという利点がある．例えば，<a>3</a>という要素の内容は単なる文字列に過ぎないが，単純型xsd:intを付与すれば3という整数として扱うことができる．これは型エラーの検出やインデックスファイルの作成に役立つ．
しかし，W3C XML Schemaに基づく検証によって型情報を得るという方法には，二つの問題がある．一つは，検証という重い処理が必須になることである．NicolaとJohn[4]は，大手ユーザにおけるXMLデータベースの性能について調査し，検証がXMLデータベース全体の性能を低下させることを報告している．もう一つの問題点は，W3C XML Schema以外のスキーマ言語，とくにRELAX NG[5]に適用できないことである．
調査[6]によれば，2003年にWWW上にあるXML文書のうちW3CXML Schemaを利用しているものは0.09%に過ぎない．
これら二つの問題点を解決するため，本論文では，検証を行うことなしに単純型だけを付与する方式を提案する．この方式は，文書がスキーマに適合していることを保証せず，複合型も扱わないが，単純型を正しく付与することは保証する．
逆に言えば,本方式はスキーマに適合しない文書に単純型を付与することができる．
単純型の付与は，パスオートマトンと部分的な検証を併用して行う．パスオートマトンは，スキーマから構築されるオートマトンであり，ルート要素からのパスを走査して要素・属性の型を選択する．パスオートマトンが単純型を選んだときには，要素・属性の内容である文字列がこの単純型に属することを部分的に検証した上で，この単純型を付与する．簡単のため要素のみについて説明するが，属性を扱えるように拡張することは容易である．

2. スキーマ
本研究では，スキーマを正規木文法によって表現する．DTD,
W3C XML Schema, RELAX NGを含む多くのスキーマ言語が，木オートマトンによって表現可能なことが知られている[7]．
正規木文法は四つ組 G = (N, Σ, S, P) である．ここで，N は非終端記号の有限集合，zzΣ は名前の有限集合，z
S はΣ × N の部分集合，z
P は生成規則 x → r の有限集合である（x は N の元, r はΣ × N の上の正規表現）．
複数の生成規則が左辺の非終端記号を共有することは，本論文では許さない.
正規木文法G による木の解釈とは，各要素に非終端記号を一つ付与したものであって，以下の条件を満たすものである．
z
ルート要素のラベルが a であり，付与された非終端記号を x であるとすると，a[x]は S に属する．
z
どの要素eとその子要素e1, e2,…, enについても，以下の条件を満たす生成規則x → rが存在する．
¾
要素 e に付与された非終端記号が x である¾
子要素e1, e2,…, enのラベルがa1, a2,…, anであり，付与された非終端記号がx1, x2,…, xnであるとす
ると，a1 [x1]a2[x2] …an[xn] は正規表現rにマッチする．

正会員 日本IBM(株)東京基礎研究所・国際大学研究所
mmurata@trl.ibm.com

1

日本データベース学会 Letters Vol.2, No.4

論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――
ある木に対してスキーマG に基づく解釈が少なくとも一つ存在するとき，この木はG に照らして妥当であるという．
木の正規木文法による解釈は，型情報を付与したものと見なすことができる．ここでいう型とは，非終端記号である．
非終端記号のうち，x → εの形の生成規則の左辺に出現するものを，本論文では単純型と見なす（ここでεは空列を表す）．すなわち，単純型とは，N の部分集合{x ∈ N | x →ε ∈ P }である．逆に言えば，単純型d を持つスキーマを正規木文法によって表現するには，非終端記号xd 及び生成規則xd →εを導入する必要がある．
例として，正規木文法G1 = (N1, Σ1, S1, P1)を考える．ここで，xsd:int, xsd:stringは単純型を表す非終端記号である．
N1 = {従業員型, xsd:int, xsd:string},zz
Σ1 = {従業員, 番号, 名前},z
S1 = {従業員[従業員型]},z
P1 = {従業員型 →(番号[xsd:int], 名前[xsd:string]),xsd:int →ε,xsd:string →ε}
なお，この正規木文法は以下のRELAX NGスキーマ（短縮構文）と等価である．
start =element 従業員 {従業員型}
従業員型 =
element 番号{xsd:int},element 名前{xsd:string}
次の文書D1を考える．
<従業員><番号>918</番号><名前>村田</名前></従業員>
この文書はひとつの解釈が存在する．ルート要素「従業員」に，複合型「従業員型」を付与し，子要素「番号」と「名前」にそれぞれ単純型xsd:intとxsd:stringを付与したものである．
したがって，この文書はG1 に照らして妥当である．

3. パスオートマトン
本章では，正規木文法からパスオートマトンを構築する方法を示す．
パスオートマトンは，正規木文法から構築される非決定的有限状態オートマトンである．正規木文法 G = (N, Σ, S, P)
からパスオートマトン M[G] を次のように構築される．
z
アルファベット: Σ をそのまま用いる．
z
状態: 各非終端記号を状態として用いる．また，開始状態 start を導入する．すなわち，N ∪ {start}が状態集合である．
z
開始状態: start が唯一の開始状態である．
z
終了状態: すべての非終端記号を状態とする．すなわ
ち，N が終了状態集合である．

2z

遷移関数: 生成規則に基づいて遷移関数δを以下のように定義する (ここで a はΣに属する名前であり，x は非終端記号とする)．
δ(x, a) = {x’ | ある生成規則 x → r ∈ P に¾
対し a[x’] が r の中に出現する}¾
δ(start, a) = { x’ | a[x’] ∈ S }先のスキーマG1 から構築されるパスオートマトンM[G1]を次に示す．
xsd:int
番号

start

従業員型
xsd:string

従業員
名前

図 1 パスオートマトンM[G1]Fig.1 Path automaton M[G1]zzzzz

アルファベット: {従業員, 番号, 名前},状態: 従業員型, xsd:int, xsd:string, start
開始状態: start
終了状態: 従業員型, xsd:int, xsd:string
遷移関数:¾
δ(start, 従業員) = {従業員型},¾
δ( 従業員型, 番号) = {xsd:int},¾
δ( 従業員型, 名前) = {xsd:string}

4. 型情報の付与
本章では，各要素までのパスに対してパスオートマトンを実行したのち，部分的な検証を行うことによって単純型を付与する方法を示す．
文書中のある要素eを考える．ルート要素から要素eまでのパスに対してパスオートマトンM[G]を実行すると，いくつかの状態からなる集合が得られる．この状態集合をeGで表すことにする．
eGに含まれるすべての単純型t1, t2, …, tnを考える．これらに対してeの内容を部分的に検証する．この結果には次の 4つの場合がある．
場合1. n =0 すなわちeGが単純型を含まない
この場合には，部分的な検証を行う必要がない．
XQueryは，すべてを許容する型としてxsd:anyTypeを提供しているので，これをeの型とする．
場合2. どのtiに対しても部分的な検証が成功しない
どの ti を用いることもできないので，xsd:anyTypeを eの型とする．
場合3. 複数のtiに対して部分的な検証が成功する
一つのtiに決めることができないので，xsd:anyTypeをeの型とする．
場合4. ただ一つのtiに対して部分的な検証が成功する
成功したtiをeの型とする．
先に示した文書D1「番号」要素に対して，型情報を付与することを考える．パスオートマトンM[G1] の実行によって得られる状態は，単純型xsd:intである．次に，この要素の内容

日本データベース学会 Letters Vol.2, No.4

論文
DBSJ Letters Vol.2, No.4――――――――――――――――――――――――――――――――――――である文字列''918''を，xsd:intに照らして部分的に検証する．
この検証に成功するので，xsd:intをこの要素の型として付与することができる．同様にして，「名前」要素に対して，xsd:string型を付与することができる．一方，ルート要素である「従業員」に対しては，型情報としてxsd:anyTypeを付与する．M[G1]の実行によって得られる「従業員型」は，単純型ではないからである．
次に，妥当でない文書に対して型情報を付与する例を示す．
以下のXML文書D2は，余分な「備考」要素があるので，G1に照らして妥当ではない．
<従業員><番号>918</番号><名前>村田</名前><備考>なし</備考></従業員>[6] Mignet, L., Barbosa, D. and Veltri, P.: "The XML Web:a First Study", International World Wide Web
Conference (2003).
[7] Murata, M., Lee, D. and Mani, M.: "Taxonomy of XML
Schema Languages using Formal Language Theory",
Extreme Markup Languages (2001).

村田 真

Makoto MURATA

日本 IBM(株)東京基礎研特別研究員・国際大学研究所特任研究員．1982 京都大学理学部卒業．W3C, IETF, OASIS,ISO/IEC, 国内委員会において XML の仕様制定・研究に従事．情報処理学会会員．日本データベース学会会員．インターネットコンファレンス'98 論文賞．

この文書に対して型情報を付与すると，先の文書とほぼ同様の結果が得られる．すなわち，要素「従業員」，「番号」，「名前」には，それぞれxsd:anyType, xsd:int, xsd:stringが付与される．唯一の違いは，要素「備考」にxsd:anyTypeが付与される点である（eGが空集合となるため）．
妥当でない場合には，そもそも解釈が存在しない．妥当でない場合に型情報を付与するのは不適切であり，検証によって妥当性を確認すべきであるという考え方もある．しかし，実用的には，たとえ妥当でなくても型情報をできるだけ付与したいという要求がある．文書の一部が誤っている又は現時点で完成できない場合でも，単純型を利用した XQuery 検索が可能なのは，むしろ本研究の利点であると筆者は考える．

5. まとめと今後の課題
本論文では，型情報の付与を検証から分離する方式を提案した．この方式は，スキーマからパスオートマトンを構築する処理，パスオートマトンを実行して型の候補を得る処理，文字列を単純型と照合する処理の 3 つからなる．
本方式は文書の妥当性を保証せず，複合型も扱わないが，単純型を正しく付与することは保証する．一方，妥当でない文書についても，単純型を利用した XQuery 検索が可能であるという特徴がある．
今後の課題として，文書の妥当性が何らかの方法（例えば静的な型検査を行う XML 変換言語）によって保証されている場合への対処がある．この場合には，複合型を付与することが可能になる．また，スキーマ以外の手段によってパスオートマトンを構築することも検討していく必要がある．

[謝辞]
DBWeb2003 の匿名の査読者のコメントに感謝する．

[文献］[1] W3C: "XQuery 1.0: An XML Query Language", W3C
Working Draft (2003).
[2] W3C: "Extensible Markup Language (XML) 1.0 (2ndEdition)", W3C Recommendation (2000).
[3] W3C: "XML Schema", W3C Recommendation (2001).
[4] Nicol, M. and John, J.: "XML Parsing: a threat todatabase performance", ACM CIKM (2003).
[5] OASIS: "RELAX NG Specification", OASIS Committee
Specification (2001).

3

日本データベース学会 Letters Vol.2, No.4