From: "Murali Mani" <mani@[...].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.

s/DTD/grammar/   

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. 

Cheers
Rick Jelliffe

-----------------------------------------------------------------
The xml-dev list is sponsored by XML.org <http://www.xml.org> , an
initiative of OASIS <http://www.oasis-open.org> 

The list archives are at http://lists.xml.org/archives/xml-dev/

To subscribe or unsubscribe from this list use the subscription
manager: <http://lists.xml.org/ob/adm.pl>