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

Date: 11 Mar 2003 21:59:47 +0100

Message-ID: <3e6e4e43.0_at_news.ruca.ua.ac.be>

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