Cart
[Home] [By Thread] [By Date] [Recent Entries]
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 Fri, 4 Apr 2003, Rick Jelliffe wrote: > From: "MURATA Makoto" <murata@h...> > > > On 28 Mar 2003 21:59:11 +0000 > > ht@c... (Henry S. Thompson) wrote: > > > > > Somewhat surprisingly, it turns out that answering the question, for an > > > arbitrary XML DTD, "Are there any valid instances of the document type > > > defined by this DTD?", is an NP-hard problem. > > > > A similar result was shown by: > > > > 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 > > > ----------------------------------------------------------------- > 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> >
|
