[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Re: ID/IDREF makes XML generation NP-hard

• To: <xml-dev@l...>
• Subject: Re: Re: ID/IDREF makes XML generation NP-hard
• From: "Rick Jelliffe" <ricko@a...>
• Date: Fri, 4 Apr 2003 03:10:19 +1000
• References: <Pine.SOL.4.33.0304030833210.24321-100000@p...>

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

• Follow-Ups:
  • Re: Re: ID/IDREF makes XML generation NP-hard
    • From: Murali Mani <mani@C...>

• References:
  • Re: Re: ID/IDREF makes XML generation NP-hard
    • From: Murali Mani <mani@C...>

• Prev by Date: RE: On the aparent importance of emoticons (was "Design as, one hopes, not premature optimization")
• Next by Date: Re: Time Travel
• Previous by thread: Re: Re: ID/IDREF makes XML generation NP-hard
• Next by thread: Re: Re: ID/IDREF makes XML generation NP-hard
• Index(es):
  • Date
  • Thread