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

Bob Badour wrote:
>"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message
>news:3e6cc096.0_at_news.ruca.ua.ac.be...
>> Bob Badour wrote:
>> >"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message
>> >news:3e6c869e.0_at_news.ruca.ua.ac.be...
>> >> Bob Badour wrote:
>> >> >"Jan Hidders" <jan.hidders_at_REMOVE.THIS.ua.ac.be> wrote in message
>> >> >news:3e6bd183.0_at_news.ruca.ua.ac.be...
>> >> >> Bob Badour wrote:
>> >> >> >
>> >> >> >[...] I cannot count how many times I have heard alleged database
>> >> >> >experts tell users to "Never use DISTINCT." If the result is
>> >> >> >already distinct, the keyword should have no cost.
>> >> >>
>> >> >> Yes. *should* is the right word. Deriving that "at compile time" is
>> >> >> not a trival problem.
>> >> >
>> >> >It is trivial in a system based on sets and requiring logical
>> >> >identity.
>> >>
>> >> No, it is just as difficult.
>> >
>> >The input to every relational operation is a set of distinct tuples with
>> >a given predicate and the output from every relational operation is a
>> >set of distinct tuples with a derivable predicate. Other than projection
>> >and summarization, what operations have intermediate duplicate tuples?
>>
>> The union, if implemented it in a naive way. But is the above somehow
>> supposed to be a proof that the problem is trivial?
>
>I don't need to prove that it is trivial. The onus is on you to prove your
>original assertion that it is not trivial.

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.

• Jan Hidders