[xquery-talk] Time complexity of XQuery
mhk at mhk.me.uk
Tue Feb 22 10:19:51 PST 2005
The time complexity depends on the algorithm used to implement the query,
not on the query itself. But I would expect this simple query to be linear
for most query engines.
If it's going non-linear for higher document sizes, I suspect this is
because the system is short of memory. Try allocating more memory and seeing
how this affects the behaviour.
From: talk-bounces at xquery.com [mailto:talk-bounces at xquery.com] On Behalf Of
Sent: 22 February 2005 10:08
To: talk at xquery.com
Subject: [xquery-talk] Time complexity of XQuery
I invite your attention to the following XML document, data.xml :
Also, pl see the following query :
let $x := doc ("data.xml")/KMeansData/Object
for $y in $x
return ($y/X, $y/Y)
If "n" be the number of elements named "Object" in the XML file above,
then would the time complexity of the XQuery above be O(n) or
I am asking this question because while using a particular XQuery Engine,
I did an experiment with synthetically generated XML data for upto n =
10,000. While the time remained O (n) i.e linear upto n = 7,000 but after
that, I noticed a tendency towards O(n^2).
Will appreciate your comments/ help.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the talk