This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 1208 - [F&O] deep-equal() is not transitive and reflexive
Summary: [F&O] deep-equal() is not transitive and reflexive
Alias: None
Product: XPath / XQuery / XSLT
Classification: Unclassified
Component: Functions and Operators 1.0 (show other bugs)
Version: Last Call drafts
Hardware: PC Windows XP
: P2 normal
Target Milestone: ---
Assignee: Ashok Malhotra
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
Depends on:
Reported: 2005-04-05 09:09 UTC by Michael Kay
Modified: 2005-09-29 10:39 UTC (History)
0 users

See Also:


Description Michael Kay 2005-04-05 09:09:51 UTC
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
Comment 1 Ashok Malhotra 2005-05-26 20:54:40 UTC
The joint WGs decided on 5/17/2005 to close this bug by accepting Michael Kay's
recommendations.  Ashok Malhotra requested clarification on 3A which were
provided by Michael Kay and Henry Thompson in (member-only) messages: and