W3C home > Mailing lists > Public > xmlschema-dev@w3.org > October 2012

Re: Order indicators in the .xsd file

From: C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com>
Date: Thu, 18 Oct 2012 07:30:08 -0600
Cc: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>, xmlschema-dev@w3.org
Message-Id: <0C984337-E953-4CD7-8BD0-F3BA3F713EFB@blackmesatech.com>
To: Michael Kay <mike@saxonica.com>

On Oct 18, 2012, at 2:48 AM, Michael Kay wrote:

> >I agree that it is often difficult, and the result is almost never easy to read and understand. But I do not believe it is ever impossible.
> 
> Depends whether your definition of "impossible" is a mathematical definition or an engineering definition.

As you will perhaps have expected, I was taking a mathematical view.

> 
> In practice, enumerating the different permutations to permit all possible orderings of 24 elements, some of which can be repeated, is impossible on the kind of computers that are available for purchase today, whatever the computer science theory might say.

You may be right (although I think you'll find that any attempt to prove your
claim will have to rely rather heavily on computer science theory, rather than
overturning it).  But unless we believe that the computers available for purchase
today are the best that there can or will ever be, the correct way to describe
problems that are soluble in principle but beyond their current capacity is
as "beyond the capacity of current systems", rather than "impossible", which
suggests somewhat more finality than I think is given here.

In particular, consider the following argument:

- XSD 1.0 allows schema components to be built in any way
the implementation chooses; reading them from valid schema 
documents is just one possible way, and the wording in the spec
has systematically been made so weak and obscure that it's
impossible to show, from the wording of the 1.0 spec, that 
any class of conforming processor is required to read any actual
XML documents.

- The software implementing schema components does not 
need to have data structures corresponding in detail to the 
descriptions in the XSD 1.0 spec; all that is required is that the 
behavior of the processor be consistent with that of a processor
whose data structures are built as described in the spec.

- While enumerating 24! or 120! disjuncts in a large regular expression
or content model whose top-level operator is choice may
exceed current engineering capacity, it is not beyond the wit of
human beings or the memory capacity of current machines to
construct a finite state automaton for the same language; if there
are 23 child elements, of which 3 have the range {1, unbounded},
4 more have the range {1,1} and 16 have the range {0,1}, the 
FSA will need 2 ** 23 states.  (This is, of course, the same
state machine an XSD 1.1 machine will need to manage the
all-group one might write for this content model.)

- So is it really impossible -- in principle -- for an XSD 1.0 implementation
to support the content model described?   

I am not aware of any XSD 1.0 implementations that support 
user-supplied schema components, but I think you will agree 
that supporting them is neither a mathematical nor an
engineering impossibility?

-- 
****************************************************************
* C. M. Sperberg-McQueen, Black Mesa Technologies LLC
* http://www.blackmesatech.com 
* http://cmsmcq.com/mib                 
* http://balisage.net
****************************************************************
Received on Thursday, 18 October 2012 13:30:52 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 23:16:02 UTC