RELAX分割検証参照モデル

$Id: dandVRefereceModel-j.html 1.3 2001/03/11 13:15:53 murata Exp $

2001年3月11日

1. はじめに

この文書では，複数名前空間を持つ文書の合法性を定義します。また，合法性を検証するための参照モデルを示します。次に，この参照モデルに基づいて，分割検証を導入します。分割検証とは，文書のすべての名前空間ではなく，一部の名前空間についてだけ行う検証のことです。分割検証は，それ自体でたいへん有益ですし，RELAX Core以外の言語をRELAX Namespaceから呼び出すのにも役立ちます。

記法を単純にするため，すべての要素はuniversal nameを持ち，名前空間宣言はすべて削除されているものとします。要素のuniversal nameとは， namespace name (URI)とlocal nameの対です。namespace nameが空文字列のときは，どの名前空間にも属さないことを表します。universal nameの表記は， James Clarkのもの(http://www.jclark.com/xml/xmlns.htm) を採用します。

検証の前にあらかじめつぎの処理は行われていると仮定します。

[RELAX Coreの前処理] RELAX Coreの参照モデルで規定されている前処理(element記法の展開，moduleのincludeの展開など）はすべて完了していると仮定します。
[hedgeRuleの展開] 名前空間Aに属するモジュールが，名前空間Bに属するラベルをhedgeRefによって参照しているとします。このラベルは，名前空間Bを記述しているモジュール内にあるhedgeRuleで記述されています。このhedgeRuleの本体によって，最初のhedgeRefは置き換えます。もし，hedgeRuleへの参照がふたたび現れた場合には，再帰的に置き換えます。

注: exportされているhedgeRuleが，他の名前空間のラベルを参照することは禁止されています。

以下では，exportされているhedgeRuleの展開後に現れるref要素が参照するラベル（他の名前空間に属しています）も，exportされているものとみなします。

この文書では，ラベルのexportに限定して考察します（別の文書で，attPool のexportを導入し，この文書の結果を拡張します）。2章では，以降で使う例題を導入します。3章では，検証単位生け垣を導入し，それに基づいて合法性を定義します。4章では，一つの検証単位生け垣に対して一つの検証器を用いる参照モデルを導入します。また，検証器の間の抽象的なインタフェースを示します。5章では，この参照モデルに基づいて，分割検証を導入します。

2. 例題

例題として，文書本体とテーブルの二つのモジュールから構成される文法を考えます。この二つのモジュールは別の名前空間に属します。

2.1 文書本体モジュール

まず、文書本体を表現するモジュールを定義します。

<module xmlns="http://www.xml.gr.jp/xmlns/relaxCore"
    relaxCoreVersion="1.0"
    targetNamespace="urn:document">

  <interface>
    <export label="doc"/>
    <export label="para"/>
  </interface>

  <tag name="doc"/>
  <elementRule role="doc">
    <choice occurs="*">
      <ref label="para"/>
      <ref label="table" namespace="urn:table"/>
    </choice>
  </elementRule>

  <tag name="para"/>
  <elementRule role="para" type="string"/>

</module>

このモジュールは、つぎのことを記述しています。

名前空間は"urn:document"であること
docがparaとtable(名前空間はurn:table)の繰り返しからなること、
docとparaはexportされること

2.2 テーブルモジュール

次に、テーブルモジュールを示します。

<module xmlns="http://www.xml.gr.jp/xmlns/relaxCore"
    relaxCoreVersion="1.0"
    targetNamespace="urn:table">

  <interface>
    <export label="table"/>
  </interface>

  <tag name="table">
    <attribute name="number" type="int"/>
  </tag>

  <elementRule role="table">
    <ref label="row" occurs="*"/>
  </elementRule>

  <tag name="row"/>
  <elementRule role="row">
    <ref label="cell" occurs="*"/>
  </elementRule>

  <tag name="cell"/>
  <elementRule role="cell">
    <ref label="para" namespace="urn:document" occurs="*"/>
  </elementRule>

</module>

このモジュールは、つぎのことを記述しています。

名前空間は"urn:table"であること
tableがrowの繰り返しからなること
rowがcellの繰り返しからなること
cellは，para(名前空間はurn:document)の繰り返しであること
tableはexportされること

2.3 文法

次に、この二つを用いて作成される文法を示します。

<grammar>

  <module namespace="urn:document" location="doc.rxm"/>
  <module namespace="urn:table"  location="table.rxm"/>

  <topLevel>
    <ref label="doc" namespace="urn:document"/>
  </topLevel>

</grammar>

この文法は、つぎのことを記述しています。

文書全体のルートは、名前空間urn:documentのラベルdocを持つこと

2.4 文書例

2.1から2.3に示した文法及びモジュールに適合する文書を示します。この文書は，二つのテーブルを持っています。どちらのテーブルも，二つの段落を含んでいます。テーブル部分は名前空間urn:tableに属しており，文書及び段落部分は，名前空間urn:documentに属しています。

<{urn:document}doc>
  <{urn:document}para>this is a para</{urn:document}para>
  <{urn:table}table number="1">
    <{urn:table}row>
      <{urn:table}cell>
        <{urn:document}para>1st para</{urn:document}para>
        <{urn:document}para>2nd para</{urn:document}para>
      </{urn:table}cell>
    </{urn:table}row>
  </{urn:table}table>
  <{urn:table}table number="2">
    <{urn:table}row>
      <{urn:table}cell>
        <{urn:document}para>3rd para</{urn:document}para>
        <{urn:document}para>4th para</{urn:document}para>
      </{urn:table}cell>
    </{urn:table}row>
  </{urn:table}table>
</{urn:document}doc>

3. 島と合法性

この章では，文書の島への分割を導入します。また，島ごとの合法性と，文書全体についての合法性を定義します。

3.1 島の例

まず，2.4の文書をいくつかの島に分割した結果を示します。

1) 第一段落を表す島（名前空間はurn:document）

<para>1st para</para>

2) 第二段落を表す島（名前空間はurn:document）

<para>2nd para</para>

3) 一番目のテーブルを表す島（名前空間はurn:table）

別の名前空間urn:documentに属する二つの島（段落）を参照するために， dummyノードが導入されていることに注意。dummyノードのnamespaceName属性は，どの名前空間に属する島であるかを表す。

<table number="1">
    <row>
      <cell>
        <dummy namespaceName="urn:document" xmlns="http://www.xml.gr.jp/namespace/dummy"/>
        <dummy namespaceName="urn:document" xmlns="http://www.xml.gr.jp/namespace/dummy"/>
      </cell>
    </row>
  </table>

4) 第三段落を表す島（名前空間はurn:document）

<para>3rd para</para>

5) 第四段落を表す島（名前空間はurn:document）

<para>4th para</para>

6) 二番目のテーブルを表す島（名前空間はurn:table）

ここでも，名前空間urn:documentに属する二つの島（段落）を参照するために， dummyノードが導入されていることに注意。

<table number="2">
    <row>
      <cell>
        <dummy namespaceName="urn:document" 
xmlns="http://www.xml.gr.jp/namespace/dummy"/>
        <dummy namespaceName="urn:document" 
xmlns="http://www.xml.gr.jp/namespace/dummy"/>
      </cell>
    </row>
  </table>

7) 文書全体を表す島（名前空間はurn:document）

名前空間urn:tableに属する二つの島（テーブル）を参照するために，dummyノードが導入されている。

<doc>
  <para>this is a para</para>
  <dummy namespaceName="urn:table" xmlns="http://www.xml.gr.jp/namespace/dummy"/>
  <dummy namespaceName="urn:table" xmlns="http://www.xml.gr.jp/namespace/dummy"/>
</doc>

3.2 島

複数の名前空間を持った文書を，いくつかの島に分割するには，親要素と異なる名前空間に属する子要素を探します。

要素eがその親要素e'と別の名前空間に属するのなら，eはe'から切り離され，新たな島のルートノードになります。e'には，eの代わりにdummyノードを挿入します。dummyノードは名前空間http://www.xml.gr.jp/namespace/dummyに常に属します。dummyノードは属性namespaceNameを持ちます。この属性は，eがどの名前空間に属しているかを示します。

3.3 島の合法性

ある島に属する要素のうちdummyを除くすべては，一つの名前空間に属します。文法での記述から，この名前空間を扱うモジュールが一意に決まります。検証には，このモジュールを用います。

島はいくつかのdummy要素を含みます。各dummy要素は一つの名前空間を参照します。

島が合法なのは，つぎの条件を満たすようにラベルと役割を要素に付与できるときです。

条件1:namespaceName属性で名前空間Xを参照するdummy要素には，名前空間Xのモジュールがexportする適当なラベルがi個割り当てられる。

条件2: 各要素に付与されたラベルと役割は、検証に用いるモジュールにあるelementRule, hedgeRule, attPool, tagを満たしている。

条件3: トップレベルの要素列に付与されたラベルは，すべてexportされている。

備考: 文法内にあるhedgeRule は，module内にある<hedgeRef label="...." namespace="..."/>をすでに展開していることに注意。

例として，二番目のテーブルを表す島をもう一度示します。

<table number="2">
    <row>
      <cell>
        <dummy namespaceName="urn:document" xmlns="http://www.xml.gr.jp/namespace/dummy"/>
        <dummy namespaceName="urn:document" xmlns="http://www.xml.gr.jp/namespace/dummy"/>
      </cell>
    </row>
  </table>

<dummy namespaceName="urn:document" xmlns="http://www.xml.gr.jp/namespace/dummy"/>が二箇所に現れています。名前空間urn:documentのモジュールがexportするラベルであるpara をたものを，どちらにも割り当てます。
テーブルモジュールには，以下のようなtagとelementRuleが存在します。
```
  <tag name="cell"/>
  <elementRule role="cell">
    <ref label="para" namespace="urn:document" occurs="*"/>
  </elementRule>
```
したがって，二つのcell要素にcellという役割，cellというラベルを割り当てることが可能です。
前処理後のテーブルモジュールには，以下のようなtagとelementRuleが存在します。
```
  <tag name="row"/>
  <elementRule role="row">
    <ref label="cell" occurs="*"/>
  </elementRule>
```
したがって，二つのrow要素にrowという役割，rowというラベルを割り当てることが可能です。
テーブルモジュールには，以下のようなtagとelementRuleが存在します。
```
  <tag name="table">
    <attribute name="number" type="int"/>
  </tag>

  <elementRule role="table">
    <ref label="row" occurs="*"/>
  </elementRule>
```
したがって，table要素にtableという役割，tableというラベルを割り当てることが可能です。
table要素は，島のトップレベル要素です。これに付されたラベルtableは，テーブルモジュールからexportされているラベルです。したがって，この島は合法です。

3.4 文書全体の合法性

文書全体の合法性は，島の合法性に基づいて定義されますが，さらに下記の条件が加わります。

条件1: 文書全体のルート要素が，文法のtopLevelにマッチすること。

備考: topLevelに出てくるrefは，すべて同一のnamespaceを参照するという制限をつけておく必要あり。

条件2: 各島uと，その直上の島u'を考えます。u'は，uに対応するdummy要素を含んでいます。dummy要素に振られたラベルと，u のルート要素に付されたラベルとが一致すること。

例: テーブルを表す島

先の文書例について説明します。まず，七つの島の合法性を確認します。ラベルを要素につぎのように割り振ることが可能なので，これらの島は合法です。

1) 第一段落を表す島の合法性

{urn:document}para

2) 第二段落を表す島の合法性

{urn:document}para

3) 一番目のテーブルを表す島の合法性

{urn:table}table
  {urn:table}row
    {urn:table}cell
      {urn:document}para
      {urn:document}para

注: dummy要素には，{urn:document}paraを付与。

4) 第三段落を表す島の合法性

{urn:document}para

5) 第四段落を表す島の合法性

{urn:document}para

6) 二番目のテーブルを表す島の合法性

{urn:table}table
  {urn:table}row
    {urn:table}cell
      {urn:document}para
      {urn:document}para

注: dummy要素には，{urn:document}paraを付与。

7) 文書全体を表す島の合法性

{urn:document}doc
  {urn:document}para
  {urn:table}table
  {urn:table}table

注: dummy要素には，{urn:table}tableを付与。

あとは，条件1及び2が成立していれば分かれば，文書全体は合法です。

まず，条件1を満たしていることを確認します。文書全体のルート要素は， <{urn:document}doc>です。それに付与されたラベルは，{urn:document}docです。文法のtopLevelは<ref label="doc" namespace="urn:document"/>と定義されているので，条件1は満たされています。

次に，条件2を満たしていることを確認します。まず島3)のルート要素に付されたラベルを考えます。これは，{urn:table}table です。そして，島7)の一番目のdummy要素に付されたラベルも同じものです。したがって，ここでは条件2は満たされています。同様に，島6のルート要素と，島7)の二番目のdummy 要素の間でも，条件2は満たされています。

島1)，島2)のルート要素に付されたラベルを考えます。これは，どちらも {urn:document}paraです。そして，島3)の中の二つのdummy要素に付されたラベルもこれと同じです。したがって，ここでも条件2は満たされています。同様に，島4), 5), 6)の間でも，条件2は満たされています。

4. 検証のための参照モデル

従来の実装は，文書全体を一つの検証器で検証していました。しかし，分割検証やRELAX Core以外の言語の呼び出しに対応するためには，複数の検証器によって文書を検証するための枠組みを構築する必要があります。

一つの島は，一つの検証器によって検証されます。言い換えれば，一つの生け垣に一つの検証器を割り当てます。各検証器は，それが受け持つ検証単位生け垣が合法性であることを検証します。

例: テーブルを含んだ文書の例では，七つの島が存在していました。一つの島に，一つの検証器が割り当てられ，検証されます。

文書全体の合法性に関する二つの条件は，各検証器が互いに交信しあうことによって検証されます。実際に交信がどのように行われるかは実装依存ですが，どのような情報がやりとりされるかを示しておきます。

上位の検証器からは，dummy要素にどのようなラベルを割り当てたかを下位の検証器に伝えます。いくつか候補がある場合は，順番に伝えるか，同時にすべての候補を伝えます。
下位の検証器からは，島のルート要素にどのようなラベルを割り当てたかを上位の検証器に伝えます。いくつかの可能性がある場合は，すべての可能性を伝えます。

5. 分割検証

分割検証のときは，すべての検証器を実行するのではなく，一部の検証器だけを実行します。ただし，実行されない検証器からの入力を必要とする検証器のために，仮の検証器を代わりに実行します。

5.1 仮の検証器との情報の授受

仮の検証器は上位・下位の検証器に次のような情報を伝えます。

下位の検証器は，その名前空間がexportしているラベルすべてを確定できます。これらすべてを，仮の検証器から候補として受け取ったとして動作します。
上位の検証器は，その名前空間が参照しているラベルのうち，仮の検証器に対応する名前空間に属するものを確定します。これらすべてを，ルート要素に割り当てられたラベルとして，仮の検証器から受け取ったとして動作します。

5.2 例

テーブルを含んだ文書の例で，一番目のテーブルを表す島に仮の検証器を適用することを考えます。

文書全体を表す島に対する検証器を考えます。名前空間はurn:documentです。このモジュールが参照しているラベルであって，urn:tableに属するのは， {urn:table}tableだけです。したがって，{urn:table}tableが一番目のテーブルを表す島のラベルであると仮の検証器が報告したものとして動作します。

次に，第一段落を表す島の合法性に対する検証器を考えます。名前空間は urn:documentです。このモジュールがexportしているラベルは， {urn:document}paraと{urn:document}docだけです。したがって，この二つを仮の検証器から候補として受け取ったとして動作します。

5.3 分割検証の適切さ

分割検証は，一部の島だけを検証し，他の島は検証しません。また，文書全体としての合法性も十分にはチェックされません。

したがって，分割検証を繰り返しても誤りを発見できないことはあります。たとえば，名前空間fooと名前空間barからなる文法と文書が存在したとします。名前空間fooだけ（正確には名前空間fooに属する検証対象生け垣だけ）について検証し，名前空間barだけ（正確には名前空間barに属する検証対象生け垣だけ）について検証しても，文書全体の合法性についての誤りを見過ごす可能性があります。

しかし，分割検証に十分意味はあります。島の合法性は検証できますし，文書全体の合法性についての誤りも一部は検証できます。誤りでないものを誤りと報告することはありません。実用的には，十分役に立つものと思われます。