Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>In order not to be dependent on particular XSLT processor's implementation, I'd recommend that a key should be used</strong>:</p> <pre><code>&lt;xsl:key name="kUserById" match="User" use="idPerson"/&gt; </code></pre> <p><strong>Then, when you need to access a <code>User</code> by <code>idPerson</code>, do just this:</strong></p> <pre><code>key('kUserById', $targetId) </code></pre> <p>Most XSLT processors implement key indexing efficiently (i.e. using a hash-table), therefore, if <code>idPerson</code> is unique for each <code>User</code>, the time for access using the <code>key()</code> function as shown above is O(1) -- constant.</p> <hr> <p><strong>Regarding your other questions</strong>:</p> <blockquote> <p>What is the time complexity of the index access for the following XPath expression in XSLT?</p> <pre><code>&lt;xsl:value-of select="User[2]/username"/&gt; </code></pre> </blockquote> <p>For the provided XML document it would be most likely O(1), however for a document where <code>Users</code> has not only <code>User</code> children, but children with other names too, the access time could be O(N) -- imagine that there are 1000 children named <code>Customer</code> and the very last two children are named <code>User</code>.</p> <blockquote> <p>I am thinking of writing a binary search function in XSLT 2.0 (requiring a fast index access) for a faster search</p> </blockquote> <p>The binary search algorithm assumes that the objects to be searched are in an <em>array</em> (and in an array the access time by index is O(1)). This assumption is wrong for XSLT/XPath, where there is still no <em>array</em> data structure.</p> <p>Some XSLT processors (like Saxon) may implement sequences in an efficient way (using vectors) with time for access O(1), but many of them don't do this.</p> <p>Therefore, to access:</p> <pre><code> $seq[$mid] </code></pre> <p>generally takes O(N), and the binary search algorithm applied on such a sequence is O(N^2).</p>
    singulars
    1. This table or related slice is empty.
    1. POWhat is the time complexity of an index access for an element in an XPath expression used in XSLT?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDimitre Novatchev
    1. USDimitre Novatchev
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks for the general and concrete case explanation. I don't mind sticking to a particular xslt-processor and my xml-file is sorted according to 'idPerson' and not going to change. I was wondering if given these preconditions a real binary search would be possible. It seems to me that it is (with SaxonHE9). Correct me if I am wrong.
      singulars
      1. PO
      1. USIvo
    2. CO@Ivo, Dr. Michael Kay is the authoritative source. In my experience, Saxon doesn't implement all sequences as vectors -- this means that for some sequences the BS would be fast but for some it may be very slow. If there is a guaranteed way of producing a vector-based sequence, then I'd use BS, otherwise I am not convinced in its utility. Anyway, why don't you stick with keys, where possible? Or, if you can use XSLT 3.0, one can use the map data structure for extremely efficient search for a key by its value.
      singulars
      1. PO
      1. USDimitre Novatchev
    3. CO`the binary search algorithm applied on such a sequence is O(N^2)` Just for the record, Isn't it O(n*log(n))? O(log(n)) lookups and O(n) cost for each lookup (all worst case). I just couldn't figure out why O(n²).
      singulars
      1. PO
      1. USIvo
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload