Re: Hierarchical Query

Mikito Harakiri wrote:
> --CELKO-- wrote:
> > I wish I had seen this before finishing TREES & HIERARCHIES IN SQL.
> > The only problem I can see is the size of the primes as the trees get
> > larger, but we are living in a 64-bit world now. Since the math is
> > simple integer division and multiplication, the speed is probably
> > pretty good.
>
> Kendall Willets suggested this method on comp.databases.theory some
> time ago.
>
> > Random thought: if we give each node a prime in a general graph, then a
> > cycle
>
> Prime numbers set with "divided by" binary relation is a partial order.
> More specifically it is a lattice. An arbitrary DAG can be embedded
> into a lattice. However, the prime numbers encoding for graphs is
> volatile. Adding a node into a graph would force to recalculate
> encodings for large graph fragment. Plus, how to handle acyclic graphs?

Could the access path be indexed? Imagine that we don't have this silly 64 bit limit and you are presented with a node encoded with a number

31074182404900437213507500358885679300373460228427 27545720161948823206440518081504556346829671723286 78243791627283803341547107310850191954852900733772 4822783525742386454014691736602477652346609

(RSA-640) and are asked what are the ancestors. Can you answer that in a reasonable amount of time.

I'm cheating of course, if the primes are small you can factor the number reasonably fast. Still, what about the access path? For comparison, in case of nested sets we are talking about index range scan (at least one way). Received on Wed May 25 2005 - 21:55:03 CEST