在XPath 2.0中表达集合相等的自动方式

Question

如果$ A和$ B是序列,那么测试$ A和$ B的集合平等的首选方法是什么？我知道存在的语义行为($A = $B)使得这个表达不是答案.排序语义也deep-equal()禁止我使用它.

我的冲动是使用:

((every $a in $A satisfies $a = $B) and (every $b in $B satisfies $b = $A))

我发现通过谷歌进行集合平等测试的确很少(确切地说,我发现什么都没有),我没有在@ Michael-Kay的第8章,第9章,第10章或第13章中看到它.我很难相信我是第一个遇到这种需求的XPath用户.这让我想知道我是否提出了错误的问题.

Answer 1

首先，这取决于您如何评估项目之间的相等性，例如您是否使用“=”、“is”、“eq”或“deep-equal”来比较两个项目？您自己的答案表明您正在考虑“=”，当应用于项目时，它与“eq”几乎相同，只是它的转换规则略有不同。事实上，它不是一个与集合一起使用的好运算符，因为它不具有传递性：untypedAtomic("4") = 4，untypedAtomic("4") = "4"，但 not(4 = "4")。因此，我们假设“eq”是可传递的，除非涉及“几乎相等”的值的数字舍入的极端情况。

然后我倾向于建议（正如其他人所做的那样）

deep-equal(sort($A), sort($B)) 

除了某些数据类型（例如 QName）定义了相等运算符，但没有定义顺序。因此这适用于整数和字符串，但不适用于 QName。

显然，您的“脉冲”解决方案中给出了 O(n^2) 方法，但是可以做得更好吗？

怎么样

let $A := count(distinct-values($a))
let $B := count(distinct-values($b))
let $AB := count(distinct-values(($a, $b))
return $A = $AB and $B = $AB

这应该是 O(n log n)。