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] Re: ID/IDREF makes XML generation NP-hard

[ Lists Home | Date Index | Thread Index ]

From: "Murali Mani" <mani@CS.UCLA.EDU>

> The main things about the 3 works are:
> 1. Henry Thompson showed that given a DTD, to check whether there is a
> valid instance is NP complete. It is definitely in NP, and henry showed it
> is NP Hard by reduction from 3SAT.

My point is that Henry showed something different: it applies only to DTD 
containing fixed or defaulted IDs or IDREFs.  So while it applies to DTDs 
in general, it does not apply to *most* DTDs, and it is trivial to figure out 
if the DTD has fixed or defaulted IDs or IDREFs.  

I have seen people use Henry's analysis as some kind of proof that ID/IDREF
itself is bad, and I just cannot see the connection, if indeed it says nothing
about normal use of ID/IDREF. (Who on earth uses fixed or defaulted IDs:
it is very strange?)

> 2. The work by Wenfei Fan et al, show that if we have keys and foreign
> keys specified as path expressions, then whether there is a valid instance
> that satisfies both the DTD and the constraints is undecidable (note: this
> is different from NPC). Note at the same time, for relational model,
> whether there is a valid instance for a given relational schema is
> trivially true.


Presumably one example of this is checking whether there is a valid instance
that conforms to a grammar and to Schematron schemas.

> 3. The work in ICDE 94 shows that given a ER model, whether there is a
> valid instance is polynomially decidable, this is true even in the
> presence of ISA constraints. They further show that whether a cardinality
> is implied by a set of ISA and cardinality constraints is decidable in
> polynomial time.
> My two cents worth: 3) is very promising. I would argue that we should
> design XML models so that it conforms to 3). I have tried to base our work
> on that - the work i pointed about constraint specification. I am not sure
> of the significance of trying to answer whether a key is implied by a
> given set of keys and foreign keys, which is undecidable even for the
> relational model.

I think both the DSDL group at ISO and the W3C XML Schema group 
would be very interested in insight on how to move forward with keys.

> More work needs to be done with respect to constraint specification.
Yes indeed. Which is one reason I suspect the Schematron approach,
of just levering what is convenient and comprehensible, is appropriate 
at the moment: if the properties of paths to trees are still active research. 

Rick Jelliffe


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

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