OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: [xml-dev] Using The Principle of Least Power As A Razor

[ Lists Home | Date Index | Thread Index ]

Le mardi 21 février 2006 à 06:56 -0500, Elliotte Harold a écrit :
> Rick Jelliffe wrote:
> > My impression is that as soon as your schema language supports IDREF it 
> > is stuffed,
> > from an NP POV:  Schematron, XSD, RELAX NG, DTDs, the lot!
> Why do you say that? Checking DTD-style IDREFs naively seems to be a 
> linear problem: just read the document twice, once to find the IDREFs 
> and once to find out whether anything matches them. Store the IDs and 
> IDREFs in a couple of stacks as you go and you could do it in a single 
> pass. Keep a counter for each IDREF to find out if it's matched more 
> than once.
> The process would seem to be linear in the size of the document; not at 
> all NP-complete. What am I missing?

I'd say that you're right. 

That's one of the reasons why ID/IDREF have made it into RELAX NG
(through the DTD compatibility feature which is quite restrictive) while
more generic integrity reference checks have been left out of the spec.
That's also the reason why the subset of XPath allowed in W3C XML Schema
key/keyref is so restricted.

In both cases, the expressive power of the integrity checks has been
kept narrow enough to insure that you can process them in streaming mode
through mechanisms such as the one you describe.

Schematron which releases the full power of XPath is, of course, a
different story.


GPG-PGP: 2A528005
Curious about Relax NG? Read my book online.
Eric van der Vlist       http://xmlfr.org            http://dyomedea.com
(ISO) RELAX NG   ISBN:0-596-00421-4 http://oreilly.com/catalog/relax
(W3C) XML Schema ISBN:0-596-00252-1 http://oreilly.com/catalog/xmlschema

Ceci est une partie de message=?ISO-8859-1?Q?num=E9riquement?= =?ISO-8859-1?Q?_sign=E9e?=


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS