Re: Getting a grip on nested intervals and matrix encoding

On Aug 15, 3:01 pm, creecode <creec..._at_gmail.com> wrote:
> Hello all,
>
> On Jul 1, 2:05 pm, creecode <creec..._at_gmail.com> wrote:
>
> > I'm attempting to use Vadim Tropashko's nested intervals and matrix
> > encoding technique.  As described in chapter 5 of his "SQL Design
> > Patterns" book and also in various online articles and discussion
> > groups.
>
> The SQL queries I have so far seem to be working well.  I have parent,
> descendants, direct descendants, next sibling and previous sibling
> queries.  The next two queries I need are next and previous nodes.
> These queries, given a current node, would return the next or previous
> node in the tree if the hierarchy was walked as a flat tree.  I hope
> that makes sense.  With the following data as an example...
>
> name    materialized_path       a11 a12 a21 a22     idx_left    idx_right
>
> KING    1                   2   1   1   0       1           2
> JONES   1.1                 3   2   2   1       1           1.5
> SCOTT   1.1.1               4   3   3   2       1           1.33333
> ADAMS   1.1.1.1             5   4   4   3       1           1.25
> FORD    1.1.2               7   3   5   2       1.33333     1.4
> SMITH   1.1.2.1             11  7   8   5       1.33333     1.375
> BLAKE   1.2                 5   2   3   1       1.5         1.66667
> ALLEN   1.2.1               8   5   5   3       1.5         1.6
> WARD    1.2.2               13  5   8   3       1.6         1.625
> MARTIN  1.2.3               18  5   11  3       1.625       1.63636
>
> Some next examples...
>
> Given KING I would get back JONES.
> Given ADAMS I would get back FORD.
>
> And some previous examples...
>
> Given BLAKE I would get back SMITH.
> Given MARTIN I would get back WARD.
>
> With a series of next queries I'd be able to walk the hierarchy
> like...
>
> KING > JONES > SCOTT > ADAMS > FORD > SMITH > BLAKE > ALLEN > WARD >
> MARTIN.  And with a series of previous queries I'd be able to do the
> reverse...
>
> MARTIN > WARD > ALLEN > etc....
>
> Any help appreciated!
>
> Toodle-loooooooooo.............
> creecode

The records ordered by idx_left, idx_right desc. I assume you want a query that when given a node in a hioerarchy fetches the next node according to the ordering. I found that this query is a mess due to composite ordering key. Therefore, it makes sence to order the values by a scalar, something like (a11-a12)/(a21-a22)*10000000000 - a11/a21

Here is the full query:

with OrderedHier as ( select name, (a11-a12)/(a21-a22)*10000000000 - a11/a21 pos from hierarchy )
SELECT h.name FROM OrderedHier h, OrderedHier node where node.name = 'BLAKE'
and h.pos > node.pos
and not exists (
 SELECT * FROM OrderedHier hh
 where h.pos > hh.pos
 and hh.pos > node.pos
)
;

fetching ALLEN. (Tested everything between KING and BLAKE) Received on Mon Aug 16 2010 - 21:52:26 CEST