[xquery-talk] Time complexity of XQuery

[Michael Kay]

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.
 
Michael Kay
http://www.saxonica.com/


  _____  

From: talk-bounces at xquery.com [mailto:talk-bounces at xquery.com] On Behalf Of
Amitabh Ojha
Sent: 22 February 2005 10:08
To: talk at xquery.com
Subject: [xquery-talk] Time complexity of XQuery



Dear members,

I  invite your attention to the following  XML document, data.xml :

<?xml version="1.0"?>
<KMeansData>

  <Object>
    <X>41</X>
    <Y>3</Y>
  </Object>

  <Object>
    <X>65</X>
    <Y>16</Y>
  </Object>

  <Object>
    <X>10</X>
    <Y>20</Y>
  </Object>

</KMeansData>

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
O(n^2) ?  

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.

Amitabh Ojha



  




 <http://clients.rediff.com/signature/track_sig.asp>  

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://xquery.com/pipermail/talk/attachments/20050222/1aa95aff/attachment.htm