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

From: Jan Hidders <>
Date: 12 Mar 2003 09:06:06 +0100
Message-ID: <>

Bob Badour wrote:
>"Jan Hidders" <> 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 to
>> Lauri:
>> 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.

  • Jan Hidders
Received on Wed Mar 12 2003 - 09:06:06 CET

Original text of this message