Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: Questions about nested intervals. Help me please!!!

Date: 19 Jul 2005 16:01:08 -0700

ampharos wrote:
> in particular way, using farey encoding, how can I relocating subtrees
> in nested interval model?

ampharos wrote:
> in particular way, using farey encoding, how can I relocating subtrees
> in nested interval model?

The key idea for answering your question is to represent Farey encoding with matrices. Why matrices are required? Because matrix multiplication mimics materialized paths concatenation!

Disclamer. During the discussion below I'll use materialized path as an easy reference. This is only to guide the intuition. The formal answer doesn't refer to materialized path at all.

Consider node 2.2.3, for example. Farey encoding for this node is found by presenting materialized path as a continued fraction

1/(2+1/(2+1/(3))) = 7/17
1/(2+1/(2+1/(3+1))) = 9/22

Since 7/17>9/22, then our Farey Interval is (9/22,7/17). This is the node that we want to move to another position, say 1.4. Farey encoding for 1.4 is calculated similarly (4/5,5/6).

Take any descendant of (9/22,7/17), say 2.2.3.4.1=(37/90,67/163).

In short:
(9/22,7/17) -> (4/5,5/6)
(37/90,67/163) -> ???

Once again, we have to convert Farey fractions into matrix form. Getting them into Moebius encoding is intermediatory step:

```(9/22, 7/17)    = (2x+7)/(5x+17),    where 0<x<1
(4/5,  5/6)     = (1x+4)/(1x+5),     where 0<x<1
(37/90,67/163)  = (30x+37)/(73x+90), where 0<x<1

```

Therefore, in matrix terms

[[2,7],[5,17]] -> [[1,4],[1,5]]
[[30,37],[73,90]] -> ???

Remember, we (rather arbitrarily) selected node [[30,37],[73,90]] as a descendant of [[2,7],[5,17]]. This implies that there is a matrix [[a,b],[c,d]] that satisfies the equation

[[2,7],[5,17]]*[[a,b],[c,d]]=[[30,37],[73,90]]

Here I take a little jump, assuming that finding a,b,c,d is easy for anybody with rudimentary linear algebra skills. (Previous version of the paper http://arxiv.org/pdf/cs.DB/0402051v1 had little bit more details how to find a,b,c,d).

[[a,b],[c,d]]=[[1,1],[4,5]]

As you need a generic solution, you would have to write down the solution explicitly as formulas for a,b,c,d in terms of the components of the two known matrices.

The final step is multiplying

```[[1,4],[1,5]]*[[a,b],[c,d]]=
[[1,4],[1,5]]*[[1,1],[4,5]]=
[[17,21],[21,26]]

```

which is the answer. (Why the matrix is symmetric? The path 1.4.4.1 is symmetric!)

We have to get it back to Farey encoding [[17,21],[21,26]] ---> (17x+21)/(21x+26), where 0<x<1 (17x+21)/(21x+26) ---> (17/21,38/47) Received on Tue Jul 19 2005 - 18:01:08 CDT

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US