### 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

## No comments:

Post a Comment