Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Extending my question. Was: The relational model and relational algebra - why did SQL become the industry standard?

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

From: Jan Hidders <jan.hidders_at_REMOVE.THIS.ua.ac.be>
Date: 12 Mar 2003 09:06:06 +0100
Message-ID: <3e6eea6e.0@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.

Received on Wed Mar 12 2003 - 02:06:06 CST

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US