Re: whether the given schema is non-deterministic or not

On 18 Feb 2009, at 03:54 , Bharath Kumar Reddy T wrote:

 > Can you please tell me whether the following schema is
 > non-deterministic or not??

 > According to spec. two element particles if they are
 > overlap and if thery both are under choice/ALL model
 > group, then that schema is non-deterministic.

Yes.  (For those readers following at home, this remark
is found in Appendix H of XSD 1.0 Part 1 Structures.)

It's a good thing the spec also says "What follows is
intended as guidance, without claiming to be complete",
because while the remark you paraphrase is true (two
overlapping particles in the same choice group will violate
the determinism rule), it's not complete.  Other
configurations will also violate the determinism rule.

 > But in the following schema, one e1 is under choice and
 > other e1 is under sequence. So, the schema is not a
 > non-deterministic.

 > Please reply me whether i am correct or not.

Your conclusion does not follow from your premise.  The spec
says "If [condition X], then [conclusion Y]"; this does not
allow us to infer that if not X then not Y.

 > <?xml version="1.0"?>
 > <xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">
 >   <xsd:element name="doc" type="foo"/>
 >   <xsd:complexType name="foo">
 >     <xsd:choice>
 >       <xsd:element name="e1" type="xsd:string"/>
 >       <xsd:group ref="group"/>
 >     </xsd:choice>
 >   </xsd:complexType>
 >   <xsd:group name="group">
 >     <xsd:sequence>
 >       <xsd:element name="e1" type="xsd:string"/>
 >     </xsd:sequence>
 >   </xsd:group>
 > </xsd:schema>

When your parser has encountered just this much of
the input document:

   <doc><e1>

do you know which single particle you will match in the
content model of type 'foo'?  If you do, then you probably
have not violated the UPA constraint.  If you don't, you
probably have violated it.

In this case, after encountering the start-tag for 'e1',
I know that I could be matching either the 'e1' declared
by the first child of the xsd:choice, or the 'e1' declared
as the first child of the sequence in group 'group'.  The
matching particle is thus not uniquely determined; therefore
we have a violation of UPA.  In this case, the non-determinism
applies not just once we have read the element's start-tag,
but even later, since the two competing declarations assign
'e1' the same type.

If one of these two element declarations carried the appinfo
notation RED and the other carried the notation GREEN,
which appinfo should the consuming application get?  The
goal of the UPA constraint is to ensure that the schema
validator can know, as soon as the start-tag has been
read, which element declaration and type definition are to
be used to validate the element, and which appinfo is to
go to the consuming application.

Some readers say they find the discussion of the Unique
Particle Attribution constraint a little easier to read in
XSD 1.1; you might consult that.  (But if you do, remember
that XSD 1.1 relaxes UPA to decree that wildcards don't
compete with element declarations; in 1.0 they do.)

I hope this helps.


-- 
****************************************************************
* C. M. Sperberg-McQueen, Black Mesa Technologies LLC
* http://www.blackmesatech.com
* http://cmsmcq.com/mib
* http://balisage.net
****************************************************************

Received on Thursday, 19 February 2009 00:38:18 UTC