論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――NVDL による XML 複合文書の配送と再構築
Dispatching and Reconstructing
Compound Document by NVDL

宮下 尚1

XML村田 真2Hisashi MIYASHITA

Makoto MURATA

XML では、複数の語彙を名前空間によって組み合わせ、複合文書を作成することができる。複合文書の例として、
W3C の XHTML ファミリー並びに IETF の Atom 及びその拡張などがある。しかし、複合文書の変換には、複数の語彙を同時に取り扱うという困難さがある。この困難を克服する
た め 、 本 論 文 で は NVDL(Namespace-based Validation
Dispatching Language)を発展させた分割変換を導入する。
分割変換では、名前空間によって複合文書を分割し、分割された断片をそれぞれ別に変換し、最後に複合文書を再構築する。プログラマは、個々の語彙に専念できるため、複合文書の変換が容易になる。
In XML, multiple vocabularies can be combined to form
compound documents by namespaces. Examples ofcompound documents include the XHTML™ family ofW3C® and the Atom feed (including its extensions) ofIETF. However, conversion of compound documents
requires difficult handling of multiple vocabularies. To
overcome this difficulty, this paper shows thedivide-transform-and-reconstruct approach on the basisof NVDL (Namespace-based Validation Dispatching
Language). In this approach, a compound document is
decomposed into fragments; each fragment istransformed by an application program; and a composite
document is reconstructed from the transformedfragments. Since each programmer can concentrate ona single vocabulary, this approach eases the conversion ofcompound documents.

1. はじめにXML では、複数の語彙を組み合わせて文書を作成することができる。このような XML 文書を複合文書と呼ぶ。複合文書の例として、W3C®3の XHTML™ファミリー（XHTML™,XForms, SVG, MathML, RDF などの組み合わせ）、OASISの ODF、Ecma の OOXML, IETF の Atom とその拡張などがある。複数の語彙を名前の衝突なく組み合わせるには、XML の名前空間を用いる。
複合文書の検証を、名前空間ごとに分割して行なう方法がISO/IEC 規格 NVDL(Namespace-based Validation
Dispatching Language)[2] によって提供されている。分割検証では、各語彙のためのスキーマを組み合わせて複合文書用のスキーマを構築する方法と比べ、スキーマの構築が容易になる。筆者らは以前の論文 [1]において、分割検証をストリーム処理によって実現するアルゴリズムを示した。
本論文では、分割検証をさらに進め、分割変換を提案する。
正会員 日本 IBM 東京基礎研究所, himi@jp.ibm.com
正会員 日本 IBM 東京基礎研究所, eb2-mrt@asahi-net.or.jp
3 W3C®, XHTML™は、The World Wide Web Consortium の商標
121

分割変換では、プログラマは各語彙についての変換をそれぞれ記述する。複合文書全体を扱う変換は記述しない。言い換えると、プログラマが複数の語彙を同時に考慮する必要はな
い。Atom と XHTML™からなる複合文書の例では、Atom についての変換処理と、XHTML™についての変換処理を別々に実現すればよく、両方を同時に扱うプログラムを書く必要はない。
分割と再構築はライブラリとして提供される。すなわち、複合文書を語彙ごとに分割する処理と、分割によって得られた変換単位から複合文書を再構築する処理はライブラリとして利用できる。先の例では、Atom と XHTML™からなる複合文書を Atom 断片と XHTML™断片に分割すること、逆にAtom 断片と XHTML™断片から複合文書を再構築することは、ライブラリによって実現される。
分割変換は、一つのプログラムによって複合文書の変換を実現する従来手法と比べてプログラムの作成が容易になるという利点がある。Atom と XHTML™からなる複合文書の例
では、Atom の変換プログラムと XHTML™の変換プログラムを別に作成すればよく、Atom と XHTML™の両方を扱うプログラムは必要ない。従来手法では、複合文書の変換プログラムの不備により一部の情報が欠落することがある。例えば、ODF は外部名前空間に属する要素・属性(外来要素・属性と呼ばれる)を多くの箇所で許しているが、ODF 文書を編集する OpenOffice.org (http://www.openoffice.org)はこれらを削除してしまう(customXml 要素に含まれる外部名前空間要素・属性などは保存される)。分割変換においては、処理を行わない名前空間に属する文書については、そもそも配送が行われず、欠落が起きることを防ぐことが出来、処理を行わなかった部分については、再構築時に適切に元の構造の複合文書として復元されることになる。

2. XML 複合文書の配送と再構築の例
本節では Atom を例に取り上げ、XML 複合文書がどのように分割・配送されるかを説明する。Atom は「フィード」と呼ばれる配信リストの情報を記述するためのフォーマットで、多くの重要なサイトで情報を配布・更新するために用いられている。
図 1 に Atom による XHTML™コンテンツの配信例を挙げる。
配信内容についての情報は entry 要素に記述される。この例では、記事の参照先は link 要素に、表題についてはtitle 要素に記述されている。ここで、下線部で示した部分が、XHTML™が Atom 中で埋め込まれている部分である。このように Atom は直接コンテンツを配信するための入れ物として利用することもできる。
<entry xmlns="http://www.w3.org/2005/Atom"><title>NVDL Reconstruction</title><link href="http://example.com/rec"/><content type="xhtml"><div xmlns="http://www.w3.org/1999/xhtml"><h1>NVDL Reconstrunction</h1><p>SnRNV supports NVDL reconstruction.</p></div></content></entry>

図 1 Atom フィードの例
Fig.1 An Atom Feed Example
さて、いま、図 2 の上部に示したような Atom 1.0 の基本部分の処理系があったとする。この処理系は、Atom 1.0 の情報を受け取り、再配信に必要な ID(id 要素に記述する)や更

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

論文DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――
新日時(updated 要素に記述する)などを埋め込む処理を担当し、外部の Reader に再配信を行うような処理系であるとする。
一方、図 2 中の下部に示したように、このシステムにおいて、XHTML™の編集作業をする処理系を追加したいとしよう。
単純に両方の処理系が同一の Atom 文書を編集したとしても、その処理結果をひとつの Atom フィードとして再配信することが出来ない。この問題を解決するため、NVDL の配信・再構築機能を利用して、一つの Atom 文書を分割して、各々の処理系に適切に配送し、その後ひとつの Atom 文書に再構築を行う事を考える。

つの複合文書に再構築することが出来る。
Atom 処理器に配送される文書:<entry xmlns="http://www.w3.org/2005/Atom"xmlns:nir="---" nir:sect-id="atom"><title>NVDL Reconstruction</title><link href="http://example.com/rec"/><content type="xhtml" ><nir:slot-node slot-node-id="atom"/><nir:slot-node-end slot-node-id="atom"/></content></entry>

XHTML 編集部に配送される文書:

Add IDs andTimestamps<div xmlns="http://www.w3.org/1999/xhtml"
xmlns:nir="---" nir:sect-id="atom xhtml"><h1>NVDL Reconstrunction</h1><p>SnRNV supports NVDL reconstruction...</p></div>XHTML
Contents

Atominstance

Atom Processor
Browser

EditedAtom Instance
XHTML Editor
Edit XHTMLParts

図 2 Atom の処理の例
Fig.2 An example of Atom processing
この配送・再構築のために必要な NVDL スクリプトを、図 3に示す。このスクリプトは、Atom 文書中の Atom 部分のみをatom ポートに出力し、XHTML™部分のみを xhtml ポートに出力する例である。
<rules xmlns="..."><namespace ns="http://www.w3.org/2005/Atom"><output port="atom" id="atom"><context path="content"><mode><namespace ns="http://www.w3.org/1999/xhtml"><output port="xhtml" id="xhtml"/></namespace></mode></context></output></namespace></rules>

図3

Atom と XHTML™による複合文書を処理する NVDL スクリ
プト。 “...”は、NVDL 名前空間 URI である。
Fig.3 An NVDL script that processes compound documentsof Atom and XHTML™. “...” represents the NVDL namespace
URI.
例えば、図 1 の Atom 文書をこの NVDL によって配送を行うと、図 4 で示した二つの文書となる。
ここで下線のついた部分は、再構築時に必要な印である(nir は、これらの印を記述するための名前空間接頭辞で、URI はここでは仮に``---''としている)。
もし、XHTML™部分をあらわしている空要素を Atom 文書処理側が削除した場合には埋め込まれていた XHTML™文書も削除されることになる。配送された各部分は、この単純化された文書を自由に編集することが出来る。たとえば、XHTML™編集部は、自由に配送された XHTML™部分を編集することが出来る。また、Atom 処理器は 例えば、id や updated といった要素を entry 要素の中に付け加えることが出来る。そして、最終的には、NVDL 再構築器によって、Atom と XHTML™による一図 4 Atom と XHTML™による複合文書の配送の例
Fig.4 An example of dispatching a compound document ofAtom and XHTML™

3. 文書を再構築するアルゴリズム
本節では、NVDLによって分割された文書を再構築するアルゴリズムを提案する。NVDLでは、名前空間ごとに文書を分割する処理をはじめに行い、その後に動作(action)を分割された断片(セクションと呼ばれる)に対して割り当てることによって、配送を行う仕組みになっている[2]。この時、分割された断片は、attachやunwrapといった動作が割り当てられた場合には、それらの断片が組みかえられてから各ソフトウェア部品に配送される。NVDLでは、非常に高度な組み替えも許されているため[1]、複雑に組み替えられてしまった文書断片から元の構造を復元することは容易ではない。

3.1

図 5 XML 複合文書の例
Fig.5 An XML Compound Document Example
この例に対して、NVDL による動作の割り当てを行うと、図7 のように 2 つの解釈が行われる。つまり、一方では ex 要素を文書要素として port1 に対して出力が行われ、もう一方では ns1:e2 要素を文書要素として port2 に対して出力

42

NVDL 標準における検証の参照モデル

以後、例として図 5 に示した XML 文書を採り上げる。そして、この文書を図 6 で示した NVDL 文書を用いて配送することとする。この NVDL では、output という新しい動作が拡張されている。これは、NVDL を検証目的ではなく、配送目的として使うための動作で、意味はほとんど validate 動作と同一であるが、スキーマを用いて検証を行わず、port 属性で指定されたポートに出力を行うための動作である。ポートとは、現在策定中の XProc4における出力先指定であるポートと互換性を持つように設計されている。
また、各動作に id 属性をつけることが出来るようになっている。この情報は、「印」をつけるために用いられるが、省略された場合には自動的に処理系が生成することになっている。
<ex xmlns="ns" xmlns:ns1="ns1" xmlns:ns2="ns2"><e1>t1</e1><ns1:e2><e/></ns1:e2></ex>

http://www.w3.org/TR/2007/WD-xproc-20070920/

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

論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――が行われることになる。
<rules xmlns="..."><namespace ns="ns"><output id="base" port="port1"><mode><namespace ns="ns1"><unwrap id="unwrap-ns1"><mode><namespace ns="ns"><attach id="ns1-ns"/></namespace></mode></unwrap><output id="out-ns1" port="port2"><mode><attach id="out-ns"/></mode></output></namespace></mode></output></namespace></rules>

図 6 NVDL スクリプト例
Fig.6 An NVDL Schema

図 7 図 5 の文書における NVDL による 2 通りの解釈
Fig. 7 Two NVDL interpretations of the document in Fig.5
このとき、NVDL配送機は、それぞれの解釈に対応して、図8で示したような２つの文書を出力する。これは、解釈1においては、output port="port1" の動作によって ex 要素が出力され、 unwrap id="unwrap-ns1" 動作によって ns1:e2 要素が取り除かれ、その子要素である e 要素が attach
id="ns1-ns" 動作によって ns1:e2 要素があった場所に取り付けられて、文書1が出力される。解釈2においては、
output port="port2" によって ns1:e2 要素が文書要素として文書2が出力され、その子要素である e 要素も attach
id="out-ns" 動作によって取り付けられて出力されることとなる。
ここで、下線によって示した部分が、再構築のために用いられる「印」である(ここで、 nir は、再構築の印をつけるための名前空間接頭辞である5)。再構築のために必要な印は、以下の2種類に分類される。
(1). 要素セクションのルートであることを示す外来属性(nir:sect-id)(2). 要素スロットノードの位置を示す空要素6

名前空間 URI は、正式には定義されていないが、今後提案される予定である。
6処理命令(Processor Instruction)を用いる提案もあり、今後の議論
によっては空要素ではなく処理命令によって印がつけられることもあり得る。
53

出力 1:
1: <ex nir:sect-id="base">
2: <e1>t1</e1>
3: <nir:slot-node slot-node-id="base unwrap-ns1"/>
4: <e nir:sect-id="base unwrap-ns1 ns1-ns"/>
5: <nir:slot-node-end slot-node-id="base unwrap-ns1"/>
6: </ex>

出力 2:
1: <ns1:e2 nir:sect-id="base out-ns1">
2: <nir:slot-node slot-node-id="base out-ns1"/>
3: <e nir:sect-id="base out-ns1 out-ns"/>
4: <nir:slot-node-end slot-node-id="base out-ns1"/>
5: </ns1:e2>

図 8 図 5 の文書における 2 つの出力 (名前空間宣言は略)
Fig.8 Two output documents of the document in Fig. 5.
(1)の印が必要な理由について、たとえば、出力1の4行目を考えてみよう。この e 要素は、もし、 nir:sect-id 属性がない場合には、その上の ex 要素と同じ要素セクションに属する他の要素と区別がつかない。再構築は変更後にも機能する必要があるため、たとえば、要素名で識別するというような手段をとった場合には要素名の変更などが出来なくなってしまう。外来属性である nir:sect-id 属性を印としてつけることによって、もともとこの e 要素が独立した要素セクションに由来するものであるということが識別可能となるわけである。なお、 nir:sect-id 中の値は、その要素セクションが受けた解釈を表す値である。具体的には、どのような動作履歴をもとに、その要素セクションが出力されたかを記録している。この例では、 base IDで識別されるoutput 動作、 unwrap-ns1 IDで識別される unwrap 動作、ns1-ns IDで識別される attach 動作によって、この e 要素が出力されたことを示している。
(2)の印が必要な理由は、主に二つある。ひとつ目の理由
は、再構築時に、どの位置に要素セクションを復元すればよいかを示すためである。たとえば、出力2では、2行目にnir:slot-node 空要素が記録されている。これによって、再構築時に、たとえば e 要素を、この印の位置に復元することが出来る。なお、4行目の nir:slot-node-end 空要素は、実際には再構築時には用いられない。
もうひとつの理由は、文書を配送されたソフトウェア部品が、印があった位置に要素セクションがあったことを識別し、編集を行うことが出来るようにするためである。たとえば、この印をもとに新しく編集を行う位置を決めるということが出来る。また、この印を削除した場合には、再構築時には、そのスロットノードに対応する要素セクションも復元されることはない。

3.2

NVDL を処理するための PDA の構築

本節と次節では、再構築のアルゴリズムについて説明する。
本手法では、文献[1]と同じようにプッシュダウンオートマトン(PDA)を用いて再構築に用いることが出来る要素セクシ
ョンの候補を選択する。配送時では、PDAは入力文書に対して動作を割り当てる処理を行うが、再構築時には、編集された文書群から、配送時と同様にPDAの状態を遷移させて配送時と同様のPDAの状態を再現させようと試みる。遷移させることの出来る候補が複数ある場合には、動作の優先順位に基づき文書群をひとつだけ選択して再構築に用いるが、実際の状態遷移は複数の候補に対して行う (すなわち、PDAは非決定的に動作する)。これによって、可能な限り、入力文書群

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

論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――
から再構築を行うことが出来るようにする。
文献[1]によるPDA構築手段を用いて、図6で示したNVDLス
クリプトを変換すると、図9で示すようなPDAが得られる。
なお、NVDLでは、動作が複数のモードに属することはない
ため、動作にIDを割り振ることで、PDAの状態を一意に識別することが出来る。したがって、以降、IDとPDAの状態を同一視する。

図93.3

図 6 の NVDL を変換することによって得られる PDA
Fig. 9 A PDA by the NVDL shown in Fig. 6.

印を利用した PDA による再構築

再構築時においては、前節のようにして構築したPDAを配送時と同様になるように遷移を行っていく。まず、配送された文書が、図5で示したものから全く変更されずに再構築器に送られた場合を考える。まず、PDAは初期状態q0にセットされる。次に出力1、出力2の各々から、SAXイベントを読み出す。その際、 nir:sect-id 属性がなかった場合には、属性が出現する開始タグのイベントまで読み飛ばす7。そして、双方の出力から nir:sect-id 属性から得られる動作の履歴を読み出す。そして、出力1からは base が、出力2からは、 baseout-ns1 が得られる。ここで、要素セクションを選ぶ際には以下の二つをチェックする。
a) 出力から得られるイベントによって、次に遷移を起こすことが出来て、b) さらにその遷移によって次に取りうる状態は、nir:sect-id 属性から得られる動作の履歴と整合性がある。
この例の場合、PDAの状態から、次に取りうる遷移は base のみであり、出力1の1行目からの開始タグのみが、名前空間 nsでa)の条件を満たし、次に、 nir:sect-id 属性の値も baseで次の状態における動作の履歴と整合性があり、b)の条件を満たすため、出力1から1行目による開始タグを読み取り、再構築に用い、PDAに対して遷移を行う(スタックに状態と名前空間のペアをプッシュし、 base に現在の状態を移す。)
そして、一旦、出力を選択した場合には同一の要素セクシ
ョンすべてを出力する。これはNVDLがセクション単位で処理を行うため、同一のセクション中ではどのような編集作業が行われても再構築に影響がでないようにするためである。この例では、出力1の2行目も再構築に用いられる。
そして、出力1の3行目における nir:slot-node 空要素で一旦出力を中断する。ここで、PDAの現在の状態が、状態がbase であるので、同様にしてa), b)を満たす出力を選択する。この場合、出力2の方が ns1:e2 要素でa)の条件を満たし、さらに nir:sect-id もb)の条件を満たしているため、
7

この処理は、何らかの要素によって取り囲まれるような編集が行われてしまった場合に対処するためである。

4

出力2が選択される。この場合には、出力2の1行目の開始タ
グで unwrap-ns1 と out-ns1 の、どちらの状態にも遷移できるため、PDAはどちらの状態にも遷移することに注意する必要がある。
引き続き、出力2の2行目のスロットノードを表す空要素で中断する。同様にしてa), b)を満たす出力を選択することになるが、今度の場合には、どちらの出力も(出力1は4行目、出力2は3行目)条件を満たす要素を持っている。この場合にはNVDLの動作の定義順で現在は優先順位を決めている。
したがって、出力1の4行目の内容が出力されて、PDAの状態は、 ns1-ns および out-ns へ遷移する。これは、前述したとおり、一部のソフトウェア部品が、拡張部分の外来属性や要素を編集後に正常に出力できない場合に、他の出力から、それらの失われた情報を再構築時に復元するための重要な機能である。
残りの出力は、要素の内容と終了タグのイベントであるため、もともと要素セクションが属していた出力を用いて再構築を行う。

4. おわりに
本稿では、XML 複合文書を分割して配送する NVDL について、配送後の文書が編集された後であっても、ストリーム処理によって再構築を行うことができる手法を提案した。本手法では、分割された文書の配送時にセクションやスロットノードがあった場所に「印」を同時に出力する。これによって、個々のソフトウェア部品が単純化された文書に対して独立した編集を行うことを可能とする。そして、編集後の文書群は、再構築器によって元の複合文書に復元される。
本研究では、複雑な XML 複合文書を適切に分割することで、文書を受け取るソフトウェアの部品化を促進し、編集後の再構築処理によって、文書全体の処理をシステム全体で可能なように NVDL を拡張することが出来た。本手法は、既存のシステムの変更を最小限にとどめたまま、外来属性や要素による拡張を許すことが出来る技術であり、今後、XML文書に対して拡張およびモジュール化を行うために必要な技術になるものと期待される。

[文献］[1] Miyashita, H. and Murata, M.: 複 合 XML 文 書 のNVDL による検証のためのストリーム処理アルゴリズム，
TOD34, Vol. 48, No. 11, pp. 1-13 (2007)[2]
Information
technology---Document
SchemaDefinition
Languages(DSDL)
Part4:
Namespace-based Validation Dispatching Language(NVDL) (2006). ISO/IEC 19757-4.

宮下 尚Hisashi MIYASHITA

2001 年 Free Standards Group、OpenI18N WG で Input
Method Subgroup Leader として入力メソッドの開発および標準化に従事．2003 年日本 IBM 東京基礎研究所に入社．
以来、XML、高信頼性ミドルウェア、アクセシビリティの研究開発に従事．ACM、情報処理学会会員．

村田 真

Makoto MURATA

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

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