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

Re: Order indicators in the .xsd file

From: Michael Kay <mike@saxonica.com>
Date: Thu, 18 Oct 2012 16:15:05 +0100
Message-ID: <50801CF9.7060205@saxonica.com>
To: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>
CC: xmlschema-dev@w3.org
Michael, I'm sure that you prove mathematically, if you put your mind to 
it, that a Turing machine (or even a Java compiler...) is a conformant 
XML Schema processor. But there are users out there who have practical 
problems to solve, and I'm trying to help them...

Michael Kay

On 18/10/2012 14:30, C. M. Sperberg-McQueen wrote:
> 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?
Received on Thursday, 18 October 2012 15:15:36 UTC

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