[
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.
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
|
