OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

RE: XML query engines

[ Lists Home | Date Index | Thread Index ]
• From: Jarle Stabell <jarle.stabell@dokpro.uio.no>
• To: "'xml-dev@ic.ac.uk'" <xml-dev@ic.ac.uk>
• Date: Mon, 1 Feb 1999 01:08:38 +0100

```
Glassbox  wrote:
>
> >There exists a neat trick which enables simple SQL-Select queries
> >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)

```

 News | XML in Industry | Calendar | XML Registry Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement Copyright 2001 XML.org. This site is hosted by OASIS