Cart
[Home] [By Thread] [By Date] [Recent Entries]
From: "Murali Mani" <mani@C...> > 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
|
