Re: Constitutionally incapable (was Re: [xml-dev] W3C Schema: Resistance is Futile, says Don Box)

[MURATA Makoto <murata@hokkaido.email.ne.jp>]

On Fri, 07 Jun 2002 10:22:34 -0400
"Simon St.Laurent" <simonstl@simonstl.com> wrote:

> At 03:12 PM 6/7/2002 +0100, Henry S. Thompson wrote:
> >RELAX NG is constitutionally incapable of providing reliable
> >type assertions.
> 
> Constitutionally incapable?
> 
> While I understand that RELAX NG _can_ support non-deterministic/unreliable 
> models, I don't believe that makes it incapable of supporting reliable type 
> assertions provided that the writers of the schema consider that a goal.
> 
> I've argued for a long while that type information should be 'painted' as a 
> separate process from validation.  Compared to that approach, I can't say I 
> find W3C XML Schema particularly reliable as a source of type assertions.


I agree with Simon.  Type assignment is trivial when a RELAX NG
grammar satisfies a constraint called "single-type".

When a RELAX NG grammar is single-type, we can easily assign a "type" 
(in the RELAX NG terminology, a named pattern) to each element without
performing full validation.  To determine the "type" of an element, we
only have to know the type of the parent element and the start tag.  We
are not required to implement the semantics of <oneOrMore>, <choice>,
etc.

The constraint "single-type" is formally shown in page 6
of this note:

	http://citeseer.nj.nec.com/murata00taxonomy.html

Using the RELAX NG terminology, I sketch when a RELAX NG 
grammar fails to be single-type.  I assume that a RELAX NG 
grammar is already normalized to the simple syntax (defined 
in the RELAX NG spec).

Suppose that a named pattern 

  <define name="foo">
    <element>
      <name ns="http://www.example.com";>foo-tag</name>
      ....
    </element>
  </define>

is referenced by another named pattern

  <define name="bar">
    <element>
      <name ns="http://www.example.com";>bar-tag</name>
      ....<ref name="foo"/>...
    </element>
  </define>

.

Consider an instance fragment:

  <example:bar-tag>
    ....
    <example:foo-tag>....</example:foo-tag>
    ....
  </example:bar-tag>

From "bar" (the "type" of the parent element) and "foo-tag" (the tag
name), we want to say that "foo" is the "type" of the child element.
But we cannot easily do so, when another pattern, say "another-foo", is
also referenced, and "another-foo" also allow the tag name example:foo-tag 
(to be precise, the prefix can be different).

That is, when we also have

  <define name="another-foo">
    <element>
      <name ns="http://www.example.com";>foo-tag</name>
      ....
    </element>
  </define>

and the named pattern "bar" is actually

  <define name="bar">
    <element>
      <name ns="http://www.example.com";>bar-tag</name>
      ....<ref name="foo"/>...
      ....<ref name="another-foo"/>...
    </element>
  </define>

, then type assignment is not straightforward and the grammar is 
NOT single-type


I think that this simple approach is often good enough.  Actually, 
we can sometimes do type-assignment, even  when a RELAX NG grammar 
is not single-type, but this becomes tricky.

It is fairly easy to write a program which determines whether a given
RELAX NG grammar is single-type.  Such a program requires handling of 
name classes of RELAX NG and simplification from the full syntax to 
the simple syntax.  These notes are helpful.

http://thaiopensource.com/relaxng/simplify.html
http://thaiopensource.com/relaxng/nameclass.html
http://www.kohsuke.org/relaxng/NameClassCookBook.html

Cheers,

Makoto