XML query engines
jarle.stabell at dokpro.uio.no
Mon Feb 1 00:04:20 GMT 1999
> >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
> 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.
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".)
Digital Logikk AS
xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)
More information about the Xml-dev