Re: The TransRelational Model: Performance Concerns

On Sat, 13 Nov 2004 22:55:32 GMT, Alistair Bayley <alistair_at_abayley.org> wrote:

>I assumed that the tables would be implemented by something that gave
>O(1) lookup time (amortized perhaps, but still more-or-less constant).

This is an option but hash tables consume a lot of memory.

O(log2 n) lookup time is enough for many applications.  

>And following from this, reconstructing a record would also be a
>constant time operation (or rather, O(n) where n is the number of
>columns), as you'd have (say) to fetch 1 block per column from the value
>table, and 1 block per column from the reconstruction table. Is this
>more-or-less correct, or have I misunderstood?

It depends on many things.

If the blocks are indexed with a B-Tree like structure and that indices are loaded in the cache what you said is more or less correct.

The number of "sorted" attributes is always optional. If you only want to make lookups over a single attribute you don't need a reconstruction table at all.

The same about a single and fixed sequence of attributes.

>> The ring structure is only one of the possible structures we may use.
>
>Can tell me some of the others, please?

Any structure that links all the sorted attributes like: double rings, stars, bidirectional rings, etc.

Regards Received on Mon Nov 15 2004 - 11:47:48 CET