W3C home > Mailing lists > Public > public-qt-comments@w3.org > September 2003

Re: Fw: RE: FW: DN-FO-09: 15.1.11 fn:distinct-values

From: Dimitre Novatchev <dnovatchev@yahoo.com>
Date: Wed, 24 Sep 2003 12:52:31 -0700 (PDT)
Message-ID: <20030924195231.74337.qmail@web41106.mail.yahoo.com>
To: public-qt-comments@w3.org
Cc: Dimitre Novatchev <dnovatchev@gmx.net>


> The WGs considered your request in the meeting on 9/16/2003 and decided
> not to change the semantics of fn:distinct-values to return values in
> order of first appearance.  The feeling was that such a constraint would
> inhibit optimization of this function.  

Thank you very much for considering this request.

I am very much concerned about the way the WG seems to take its decisions:

 1. Based on "feeling".

 2. Is the above reply  a statement that there do not exist efficient 
    algorithms for returning the distinct values of a sequence in order of

    first appearance
 or
   is this an expression of a belief or feeling or lack of information?

 3. What are the facts about the computational complexity of the 
    algorithms for the implementation of the two discussed variants of the

    function that support the decision of the WG?


In my personal experience I have worked with an efficient implementation
of the EXSLT set:distinct() function.

Another observation is that the definition of fn:distinct-values() in the
current WD is overspecified, which unnecessarily narrows the types of the
first argument of the function.

The unnecessary condition is the requirement that "The type must have a
total order".

A total order relation is in fact not necessary condition for solving the
problem of finding unique values of a sequence.

A necessary and sufficient condition is just that the type of the elements
of the sequence has an equality relation defined on it.

The fact that total order is required in the specification narrows
unnecessarily the type of sequences on which the function is defined.

This fact also shows that the authors have a pre-determined solution (most
probably involving a sort operation), for which the existence of a total
order is required.


As the above analysis shows, having total order is not required in order
to define the fn:distinct-values().

Therefore, I propose to remove this unnecessary condition from the
definition of the function and to leave as requirement only that the type
of the elements of the sequence must have equality defined.



Best regards,
Dimitre Novatchev.

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
Received on Wednesday, 24 September 2003 15:55:41 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:45:14 UTC