[
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.
Eric
>
--
GPG-PGP: 2A528005
Curious about Relax NG? Read my book online.
http://books.xmlschemata.org/relaxng/
------------------------------------------------------------------------
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?=
|
