Re: Extending my question. Was: The relational model and relational algebra - why did SQL become the industry standard?
Date: Wed, 12 Mar 2003 11:20:46 -0500
"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message
> Bob Badour wrote:
> >"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message
> >> Sure, but you asserted that it isn't, so that onus is on you. The
> >> complexity of the problem is discussed in the reference I already gave
> >> Lauri:
> >> http://citeseer.nj.nec.com/paulley94exploiting.html
> >> The particular problem they study there is NP-complete.
> >Okay, you are right. It is an NP-complete problem to avoid duplicate
> >in every conceivably avoidable situation.
> That's not NP-complete. That's actually undecidable.
> >I note first the authors grant that no duplicate removal avoidance
> >optimization exists if either of the input tables allows duplicate rows
> >(section 3.2).
> ?? Where do you see that? I would be highly surprised if they would say
> because it isn't true.
Not with their theorem, anyway. They require both tables have at least one key.
> -- Jan Hidders
Received on Wed Mar 12 2003 - 17:20:46 CET