xml-dev - RE: XML query engines

[Jarle Stabell <jarle.stabell@dokpro.uio.no>]

Glassbox  wrote:
>
> >There exists a neat trick which enables simple SQL-Select queries 
answering
> >for two given nodes, whether one is a subnode of the other, and also how
> >many levels deep, in constant time, assuming you do some simple
> >preprocessing on the structure. (Assigning two integers to each node in 
the
> >tree).
>
> Can you please explain it precisely ?

I will only do a very short explanation, or else I will be much too tired 
(and/or late) at work tomorrow! :-) (it's already Monday here)
(But I think you either will understand it directly, or have some fun 
playing with the details, it's a simple and elegant idea.)

The basic idea is to assign an interval (using a pair of integers) to each 
node, and assigning them such that Interval(n1) contains Interval(n2) if 
and only if n2 is a subnode of n1.

Then you only need to do two integer compares in order to check whether a 
given node is a subnode of another.

You can think of the interval of a parent node p as the union of all the 
intervals of the subnodes.
(or projection)

To assign the integers, you may start with assigning the "left" side of the 
root node the number 1 (or whatever!), and traverse the tree and increase 
the number as appropriate. (When you come to a leaf node, you assign both a 
"leftside" number and "rightside" number)  (I believe different strategies 
for when to increase the number may give slightly different extra info when 
comparing the intervals of two nodes, but I don't remember whether the 
differences are substantial. You may increase by 1 on each "step".)




Cheers,

Jarle Stabell
Digital Logikk AS


xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@ic.ac.uk)