Re: Extending my question. Was: The relational model and relational algebra - why did SQL become the industry standard?

"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message news:3e6eea6e.0_at_news.ruca.ua.ac.be...
> Bob Badour wrote:
> >"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message
> >news:3e6e4e43.0_at_news.ruca.ua.ac.be...
> >>
> >> 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
to
> >> 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
removal
> >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
that
> 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