Zorba - NoSQL Query Processing

Content of set-similarity module

xquery version "1.0";

(:
 : Copyright 2006-2009 The FLWOR Foundation.
 :
 : Licensed under the Apache License, Version 2.0 (the "License");
 : you may not use this file except in compliance with the License.
 : You may obtain a copy of the License at
 :
 : http://www.apache.org/licenses/LICENSE-2.0
 :
 : Unless required by applicable law or agreed to in writing, software
 : distributed under the License is distributed on an "AS IS" BASIS,
 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 : See the License for the specific language governing permissions and
 : limitations under the License.
 :)

(:~
 : &lt;p&gt;This library module provides similarity functions for comparing sets of XML 
 : nodes (e.g., sets of XML elements, attributes or atomic values).&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;These functions are particularly useful for matching near duplicate sets of XML nodes.&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The logic contained in this module is not specific to any particular XQuery implementation.&lt;/p&gt;
 :
 : @author Bruno Martins
 : @project Zorba/Data Cleaning/Set Similarity
 :)

module namespace set = "http://zorba.io/modules/data-cleaning/set-similarity";

declare namespace ver = "http://zorba.io/options/versioning";
declare option ver:module-version "2.0";

(:~
 : &lt;p&gt;Returns the union between two sets, using the deep-equal() function to compare the XML nodes from the sets.&lt;/p&gt;
 : &lt;p/&gt;
 : 
 : &lt;p&gt;Example usage : &lt;pre class="ace-static" ace-mode="xquery"&gt; deep-union ( ( "a", "b", "c") , ( "a", "a", &lt;d/&gt; ) ) &lt;/pre&gt;&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The function invocation in the example above returns : &lt;pre class="ace-static" ace-mode="xquery"&gt; ("a", "b", "c", &lt;d/&gt; ) &lt;/pre&gt;&lt;/p&gt;
 :
 : @param $s1 The first set.
 : @param $s2 The second set.
 : @return The union of both sets.
 : @example test/Queries/data-cleaning/set-similarity/deep-union.xq
 :)
declare function set:deep-union ( $s1 , $s2 ) as item()*{
 let $s := ( $s1 , $s2 )
 for $a at $apos in $s
 where every $ba in subsequence($s, 1, $apos - 1) satisfies not(deep-equal($ba,$a))
 return $a
};

(:~
 : &lt;p&gt;Returns the intersection between two sets, using the deep-equal() function to compare the XML nodes from the sets.&lt;/p&gt;
 : &lt;p/&gt;
 : 
 : &lt;p&gt;Example usage : &lt;pre class="ace-static" ace-mode="xquery"&gt; deep-intersect ( ( "a", "b", "c") , ( "a", "a", &lt;d/&gt; ) ) &lt;/pre&gt;&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The function invocation in the example above returns : &lt;pre class="ace-static" ace-mode="xquery"&gt; ("a") &lt;/pre&gt;&lt;/p&gt;
 :
 : @param $s1 The first set.
 : @param $s2 The second set.
 : @return The intersection of both sets.
 : @example test/Queries/data-cleaning/set-similarity/deep-intersect.xq
 :)
declare function set:deep-intersect ( $s1 , $s2 ) as item()*{
 for $a at $apos in $s1
 let $t1 := every $ba in subsequence($s1, 1, $apos - 1) satisfies not(deep-equal($ba,$a))
 let $t2 := some $bb in $s2 satisfies deep-equal($bb,$a)
 where $t1 and $t2
 return $a
};

(:~
 : &lt;p&gt;Removes exact duplicates from a set, using the deep-equal() function to compare the XML nodes from the sets.&lt;/p&gt;
 : &lt;p/&gt;
 : 
 : &lt;p&gt;Example usage : &lt;pre class="ace-static" ace-mode="xquery"&gt; distinct ( ( "a", "a", &lt;b/&gt; ) ) &lt;/pre&gt;&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The function invocation in the example above returns : &lt;pre class="ace-static" ace-mode="xquery"&gt; ("a", &lt;b/&gt; ) &lt;/pre&gt;&lt;/p&gt;
 :
 : @param $s A set.
 : @return The set provided as input without the exact duplicates (i.e., returns the distinct nodes from the set provided as input).
 : @example test/Queries/data-cleaning/set-similarity/distinct.xq
 :)
declare function set:distinct ( $s ) as item()*{
 for $a at $apos in $s
 where every $ba in subsequence($s, 1, $apos - 1) satisfies not(deep-equal($ba,$a))
 return $a
};

(:~
 : &lt;p&gt;Returns the overlap coefficient between two sets of XML nodes.&lt;/p&gt;
 : &lt;p&gt;The overlap coefficient is defined as the shared information between the input sets 
 : (i.e., the size of the intersection) over the size of the smallest input set.&lt;/p&gt;
 : &lt;p/&gt;
 : 
 : &lt;p&gt;Example usage : &lt;pre class="ace-static" ace-mode="xquery"&gt; overlap ( ( "a", "b", &lt;c/&gt; ) , ( "a", "a", "b" ) ) &lt;/pre&gt;&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The function invocation in the example above returns : &lt;pre class="ace-static" ace-mode="xquery"&gt; 1.0 &lt;/pre&gt;&lt;/p&gt;
 :
 : @param $s1 The first set.
 : @param $s2 The second set.
 : @return The overlap coefficient between the two sets.
 : @example test/Queries/data-cleaning/set-similarity/overlap.xq
 :)
declare function set:overlap ( $s1 , $s2 ) as xs:double {
  count( set:deep-intersect($s1, $s2) ) div min((count(set:distinct($s1)) , count(set:distinct($s2))))
};

(:~
 : &lt;p&gt;Returns the Dice similarity coefficient between two sets of XML nodes.&lt;/p&gt;
 : &lt;p&gt;The Dice coefficient is defined as defined as twice the shared information between the input sets 
 : (i.e., the size of the intersection) over the sum of the cardinalities for the input sets.&lt;/p&gt;
 : &lt;p/&gt;
 : 
 : &lt;p&gt;Example usage : &lt;pre class="ace-static" ace-mode="xquery"&gt; dice ( ( "a", "b", &lt;c/&gt; ) , ( "a", "a", "d") ) &lt;/pre&gt;&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The function invocation in the example above returns : &lt;pre class="ace-static" ace-mode="xquery"&gt; 0.4 &lt;/pre&gt;&lt;/p&gt;
 :
 : @param $s1 The first set.
 : @param $s2 The second set.
 : @return The Dice similarity coefficient between the two sets.
 : @example test/Queries/data-cleaning/set-similarity/dice.xq
 :)
declare function set:dice ( $s1 , $s2 ) as xs:double {
  2 * count( set:deep-intersect($s1,$s2) ) div ( count(set:distinct($s1)) + count(set:distinct($s2)) )
};

(:~
 : &lt;p&gt;Returns the Jaccard similarity coefficient between two sets of XML nodes.&lt;/p&gt;
 : &lt;p&gt;The Jaccard coefficient is defined as the size of the intersection divided by the size of the 
 : union of the input sets.&lt;/p&gt;
 : &lt;p/&gt;
 : 
 : &lt;p&gt;Example usage : &lt;pre class="ace-static" ace-mode="xquery"&gt; jaccard ( ( "a", "b", &lt;c/&gt; ) , ( "a", "a", "d") ) &lt;/pre&gt;&lt;/p&gt;
 : &lt;p/&gt;
 : &lt;p&gt;The function invocation in the example above returns : &lt;pre class="ace-static" ace-mode="xquery"&gt; 0.25 &lt;/pre&gt;&lt;/p&gt;
 :
 : @param $s1 The first set.
 : @param $s2 The second set.
 : @return The Jaccard similarity coefficient between the two sets.
 : @example test/Queries/data-cleaning/set-similarity/jaccard.xq
 :)
declare function set:jaccard ( $s1 , $s2  ) as xs:double {
 count( set:deep-intersect($s1,$s2) ) div count( set:deep-union($s1,$s2) )
};