[Bug 1208] New: deep-equal() is not transitive and reflexive

           Summary: deep-equal() is not transitive and reflexive
           Product: XPath / XQuery / XSLT
           Version: Last Call drafts
          Platform: PC
        OS/Version: Windows XP
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Functions and Operators
        AssignedTo: ashok.malhotra@oracle.com
        ReportedBy: mike@saxonica.com
         QAContact: public-qt-comments@w3.org


The deep-equal() function as currently defined is not transitive and it is not
reflexive (it does not guaranteed that deep-equal($A, $A) is true).

The known problems are as follows:

A. The transitivity problem arises from the condition that two elements are
deep-equal if (among other things):

# One of the following conditions holds:

    * Both element nodes have a type annotation that is either a simple type or
a complex type with simple content, and the typed value of $i1 is deep-equal to
the typed value of $i2.
    * One or both of the element nodes has a type annotation that is neither a
simple type nor a complex type with simple content, and the sequence
$i1/(*|text()) is deep-equal to the sequence $i2/(*|text()).

This means that given

X: <a>1</a> of type xs:integer
Y: <a>1.0</a> of type xs:decimal
Z: <a>1</a> of type xs:anyType

we have X=Y, X=Z, and Y!=Z.

B. The function is not reflexive because of the possibility of NaN values. If $X
is a document that contains a typed NaN value at any depth, then deep-equal($X,
$X) is false.

C. The lack of support for comparison of durations also leads to a problem. If
$X is a document that contains a typed xs:duration value at any depth, then
deep-equal($X, $X) is false.

The effect of these problems is that deep-equal is difficult for an optimizer to
handle, for example if it is used as a join condition then it's not possible to
support it using a hash join. It also means that the function is not suitable to
underpin future developments that introduce a grouping capability or a
deep-distinct() function.

There are several things we could do about the problem:

Option 1: scrap the function

Option 2: live with its deficiencies

Option 3: fix the problems

3A. Specify that two elements can be deep-equal only if they are both annotated
as having complex content or both annotated as having simple content.

3B. Specify that for the purposes of deep-equal, NaN is equal to NaN. (We
already have this rule for distinct-values())

3C. Specify an equality comparison for xs:duration values. Unlike ordering,
there is no good reason for this to be unsupported. Any duration can be simply
and unambiguously represented as the sum of a dayTimeDuration and a
yearMonthDuration and we simply specify that two durations are equal if these
two components are equal.

Michael Kay

Received on Tuesday, 5 April 2005 19:13:14 UTC