[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Using The Principle of Least Power As A Razor


Re:  Using The Principle of Least Power As A Razor
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?=


PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
 

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.


Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.