Re: Extending my question. Was: The relational model and relational algebra - why did SQL become the industry standard?
Date: 12 Mar 2003 09:06:06 +0100
Message-ID: <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.
- Jan Hidders