Discussion about XML model

Some discussion
Another related interesting result is: polynomial time decidability of constraints for the ER model - this work is titled "On the Interaction between ISA and Cardinality Constraints" by D. Calvanese and M. Lenzerini, and appeared in ICDE 94. 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. 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. There is another result: For the relational model, whether a key is implied by a given set of keys and foreign keys is undecidable. 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. If you see Henry's result 1) it definitely does not conform to ER at all. More work needs to be done with respect to constraint specification. cheers and regards - murali. On XML Integrity Constraints in the Presence of DTDs Journal of the ACM (JACM), Volume 49 , Issue 3, pp 368 - 406, May 2002. Wenfei Fan and Leonid Libkin http://www.bell-labs.com/user/wenfei/papers/jacm.pdf That article should be read with care: it talks of DTDs but it means grammars in general, and it talks of integrity constraints, but these are not ID/IDREF. Thus it seems that they share the same proviso as with Henry's analysis: Henry's analysis seems to apply to DTDs with fixed IDs or fixed IDREFs, and this paper applies to where there is an outside fixed set of constraints such as keys and foreign keys. Cheers Rick Jelliffe