[
Lists Home |
Date Index |
Thread Index
]
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@hokkaido.email.ne.jp>
>
> > On 28 Mar 2003 21:59:11 +0000
> > ht@cogsci.ed.ac.uk (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>
>
|
