Set Operator Examples
Hi all,
Where can I find examples using set operators... wrt BaseX.
Hi John,
XQuery defines three set operators, namely "union", "intersect" and "except". As those are not BaseX-specific, you’ll need to check out other literature on XQuery
Hope this helps, Christian ___________________________
2013/9/24 John Best <johnbest5673 at gmail.com>:
Quoted text · John Best · 15 lines
> Hi all, > > Where can I find examples using set operators... wrt BaseX. > > -- > Have a nice day > JBest > > > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk >
Question was about set operations in BaseX. I had to calculate set difference on a sequence of values. XQuery has operator except, but it works only on nodes. I guess normal code for this is using distinct-values:
declare function local:difference-pred($a, $b) {
distinct-values($a[not(.=$b)])
};I used it on big (thousands of values) sets, and it was slow. Then I tried on maps using BaseX map-module :
declare function local:difference-map($a, $b) {
let $m1 := map:new(for $i in $a return map:entry($i, true()))
let $m2 := map:new(for $i in $b return map:entry($i, false()))
let $m3 := map:new(($m1, $m2))
return for $i in map:keys($m3)
return if ($m3($i)) then $i else ()
};Then we found another solution, with only one map:
declare function local:difference-map-2($a, $b) {
let $m2 := map:new(for $i in $b return map:entry($i, true()))
return for $i in $a
return if($m2($i)) then () else $i
};When trying them at same sequences:
let $a :=for $i in (1 to 100000)
return if (random:double() < 0.01) then () else string($i)
let $b := for $i in $a
return if (random:double() < 0.45) then () else $i
return (count($a), count($b), count(prof:time( local:difference-pred($a, $b), true(), 'pred ')),
count(prof:time( local:difference-map($a, $b), true(), 'map ')),
count(prof:time( local:difference-map($a, $b), true(), 'map2 ')))This gives times (on BaseX 7.6 running on OpenSUSE on VMWare virtual machine on a PC).
pred: 80468.68ms map: 261.23 ms map2: 253.77 ms
That is: map2 is 317 times faster than distinct-values version. I did not measure memory usage. Also on different size sequences, each one of the functions can be fastest!
Hej Arto,
just being interested: How does it compare to a FLOWR expression?
declare function local:difference-flowr($a, $b) {
for $x in $a
where not($x = $b)
group by $x
return $x[1]
};cheers Arve
Quoted text · Arto Viitanen · 52 lines
Am 25.09.13 07:22 schrieb Arto Viitanen: > Question was about set operations in BaseX. I had to calculate set difference on a sequence of values. XQuery has operator except, but it works only on nodes. I guess normal code for this is using distinct-values: > > declare function local:difference-pred($a, $b) { > distinct-values($a[not(.=$b)]) > }; > > I used it on big (thousands of values) sets, and it was slow. Then I tried on maps using BaseX map-module : > > declare function local:difference-map($a, $b) { > let $m1 := map:new(for $i in $a return map:entry($i, true())) > let $m2 := map:new(for $i in $b return map:entry($i, false())) > let $m3 := map:new(($m1, $m2)) > return for $i in map:keys($m3) > return if ($m3($i)) then $i else () > }; > > Then we found another solution, with only one map: > > declare function local:difference-map-2($a, $b) { > let $m2 := map:new(for $i in $b return map:entry($i, true())) > return for $i in $a > return if($m2($i)) then () else $i > }; > > When trying them at same sequences: > > let $a :=for $i in (1 to 100000) > return if (random:double() < 0.01) then () else string($i) > let $b := for $i in $a > return if (random:double() < 0.45) then () else $i > > return (count($a), count($b), count(prof:time( local:difference-pred($a, $b), true(), 'pred ')), > count(prof:time( local:difference-map($a, $b), true(), 'map ')), > count(prof:time( local:difference-map($a, $b), true(), 'map2 '))) > > This gives times (on BaseX 7.6 running on OpenSUSE on VMWare virtual machine on a PC). > > pred: 80468.68ms > map: 261.23 ms > map2: 253.77 ms > > That is: map2 is 317 times faster than distinct-values version. I did not measure memory usage. Also on different size sequences, each one of the functions can be fastest! > > -- > Arto Viitanen > Finland > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk >
Quoted text · Arve Gengelbach · 22 lines
-----Original Message----- From: Arve Gengelbach [mailto:ag at basex.org] Sent: 25. syyskuuta 2013 9:08 To: Arto Viitanen Cc: basex-talk at mailman.uni-konstanz.de Subject: Re: [basex-talk] Set Operator Examples Hej Arto, just being interested: How does it compare to a FLOWR expression? declare function local:difference-flowr($a, $b) { for $x in $a where not($x = $b) group by $x return $x[1] }; pred 51787.06 ms map 485.16 ms map2 325.09 ms flowr 45275.97 ms -- Arto Viitanen Finland
Hej Arto,
One can even improve your map2 by using the [Simple map operator].
declare function local:difference-map-2-excl($a, $b) {
let $m2 := map:new($b ! map:entry(., true()))
return $a ! (if($m2(.)) then () else .)
};- map 299.47 ms - map2 290.96 ms - map2 + ! 128.25 ms
cheers Arve
[Simple map operator] http://www.w3.org/TR/xquery-30/#id-map-operator
Quoted text · Arto Viitanen · 31 lines
Am 25.09.13 10:41 schrieb Arto Viitanen: > > > -----Original Message----- > From: Arve Gengelbach [mailto:ag at basex.org] > Sent: 25. syyskuuta 2013 9:08 > To: Arto Viitanen > Cc: basex-talk at mailman.uni-konstanz.de > Subject: Re: [basex-talk] Set Operator Examples > > Hej Arto, > > just being interested: > How does it compare to a FLOWR expression? > > declare function local:difference-flowr($a, $b) { > for $x in $a > where not($x = $b) > group by $x > return $x[1] > }; > > pred 51787.06 ms > map 485.16 ms > map2 325.09 ms > flowr 45275.97 ms > > -- > Arto Viitanen > Finland >
Hi, Nice work. I wonder if the BaseX query optimizer could not spot the idioms for the set operations and rewrite the query to something similar for the cases:
distinct-values(($arg1, $arg2))
distinct-values($arg1[.=$arg2])
distinct-values($arg1[not(.=$arg2)])From : http://www.xqueryfunctions.com/xq/c0015.html#c0075
Regards /Andy
Quoted text · Arve Gengelbach · 54 lines
On Wed, Sep 25, 2013 at 8:04 PM, Arve Gengelbach <ag at basex.org> wrote: > Hej Arto, > > One can even improve your map2 by using the [Simple map operator]. > > declare function local:difference-map-2-excl($a, $b) { > let $m2 := map:new($b ! map:entry(., true())) > return $a ! (if($m2(.)) then () else .) > }; > > - map 299.47 ms > - map2 290.96 ms > - map2 + ! 128.25 ms > > cheers > Arve > > [Simple map operator] http://www.w3.org/TR/xquery-30/#id-map-operator > > Am 25.09.13 10:41 schrieb Arto Viitanen: >> >> >> -----Original Message----- >> From: Arve Gengelbach [mailto:ag at basex.org] >> Sent: 25. syyskuuta 2013 9:08 >> To: Arto Viitanen >> Cc: basex-talk at mailman.uni-konstanz.de >> Subject: Re: [basex-talk] Set Operator Examples >> >> Hej Arto, >> >> just being interested: >> How does it compare to a FLOWR expression? >> >> declare function local:difference-flowr($a, $b) { >> for $x in $a >> where not($x = $b) >> group by $x >> return $x[1] >> }; >> >> pred 51787.06 ms >> map 485.16 ms >> map2 325.09 ms >> flowr 45275.97 ms >> >> -- >> Arto Viitanen >> Finland >> > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk
I had a typo in my example. The return did not call the map2 version. With it, the results were (now on 7.7 and Windows 7)
- pred 58278.25 ms - map 272.68 ms - map2 74.27 ms - map2! 92.97 ms - flowr 43018.3 ms
Hej Arto,
One can even improve your map2 by using the [Simple map operator].
declare function local:difference-map-2-excl($a, $b) {
let $m2 := map:new($b ! map:entry(., true()))
return $a ! (if($m2(.)) then () else .) };- map 299.47 ms - map2 290.96 ms - map2 + ! 128.25 ms
.. Arto
Quoted text · Arto Viitanen · 1 line
> I had a typo in my example. The return did not call the map2 version. With it, the results were (now on 7.7 and Windows 7)
And I posted the wrong version. Usage of ! within map:new() is not as fast as a flowr expression (in general).
BUT neither of the “fastest two” functions yields valid results (e.g. take 2,2,3 for $a and empty sequence for $b) Arto, I hope replacing one flowr expression with the simple map operator can improve speed in your use-cases. So hopefully this is fastest for you:
declare function local:difference-maps($a, $b) {
let $m1 := map:new(for $i in $a return map:entry($i, true()))
let $m2 := map:new(for $i in $b return map:entry($i, false()))
let $m3 := map:new(($m1, $m2))
return map:keys($m3) ! (if ($m3(.)) then . else ())
};As the speed gain depends on the spreading of the data, rewriting set operations needs proove of efficency for any given data.
Thanks Arto for the interesting comparisons.
One more rewriting for map2 could be..
declare function local:map2($a, $b) {
let $m2 := map:new($b ! map:entry(., true()))
return $a[$m2(.)]
};..but my assumption is that all rewritings should yield similar performance, because the flwor expression, predicates and the map operator are internally basically evaluated the same.
@Andy:
Quoted text · Arve Gengelbach · 3 lines
> distinct-values(($arg1, $arg2)) > distinct-values($arg1[.=$arg2]) > distinct-values($arg1[not(.=$arg2)])
the first query should be fast enough, but it may be beneficial to optimize the (non-)equality test in the next two queries. I’m not sure, though, if this optimization can be generalized that easily. ___________________________
2013/9/26 Arve Gengelbach <ag at basex.org>:
Quoted text · Arve Gengelbach · 23 lines
>> I had a typo in my example. The return did not call the map2 version. With it, the results were (now on 7.7 and Windows 7) > > And I posted the wrong version. Usage of ! within map:new() is not as > fast as a flowr expression (in general). > > BUT neither of the “fastest two” functions yields valid results > (e.g. take 2,2,3 for $a and empty sequence for $b) > Arto, I hope replacing one flowr expression with the simple map operator > can improve speed in your use-cases. So hopefully this is fastest for you: > > declare function local:difference-maps($a, $b) { > let $m1 := map:new(for $i in $a return map:entry($i, true())) > let $m2 := map:new(for $i in $b return map:entry($i, false())) > let $m3 := map:new(($m1, $m2)) > return map:keys($m3) ! (if ($m3(.)) then . else ()) > }; > > As the speed gain depends on the spreading of the data, rewriting set > operations needs proove of efficency for any given data. > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk
Written for BaseX 7.7. BaseX may have changed since: please check the current documentation.