TRM and sorts

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

paul c - 05 Sep 2007 03:22 GMT

I wonder if anybody here has spent much time thinking about the
practicalities of the "trans-relational model"?

I can see its value for joins that don't involve projections of
relations that have a great many attributes, however it seems to assume
that all "tables" are pre-sorted (which for some apps I think is a
reasonable assumption) and since "ORDERing" often involves permutations
of attributes, I think that any implementation that supports ordering on
multiple attributes must either pre-sort every permutation of attributes
or implement the equivalent of a run-time sort.

Sometimes I wonder if this is one reason why it might be thought
deficient. I'm curious as to what others here might condider practical
deficiencies.

p

Reply to this Message

Jonathan Leffler - 05 Sep 2007 05:33 GMT

> I wonder if anybody here has spent much time thinking about the
> practicalities of the "trans-relational model"?
[quoted text clipped - 10 lines]
> deficient. I'm curious as to what others here might condider practical
> deficiencies.

It's been a couple of years (at least) since I read anything concrete
about the TRM, but my impression was that all the columns were always
sorted - so run-time sorts on single columns are unnecessary, and when
you have to sort data on multiple columns, you should be able to
preserve the order of the lead column of the sort, which should simplify
the sorting (if only because you only have to sort each subrange with
the same lead column).

Am I wrong on that?

Signature

Jonathan Leffler #include <disclaimer.h>
Email: jleffler@earthlink.net, jleffler@us.ibm.com
Guardian of DBD::Informix v2007.0826 -- http://dbi.perl.org/

Reply to this Message

paul c - 05 Sep 2007 16:22 GMT

...

> It's been a couple of years (at least) since I read anything concrete
> about the TRM, but my impression was that all the columns were always
[quoted text clipped - 5 lines]
>
> Am I wrong on that?

I'm pretty sure you are right, although I guess with enough added
structure those "subrange" sorts could be replaced with "merges" since
there would always be a structure that would order each attribute's
values (which would make a memory-only version much fatter). I
mentioned only "ORDERing", but "GROUPing" operations might be affected
more in some apps. It just seemed a little ironic to me that after
going to all the trouble to pre-sort or indexing every attribute, some
run-time sorting might still be needed.

p

Reply to this Message

Cimode - 08 Sep 2007 00:29 GMT

> I wonder if anybody here has spent much time thinking about the
> practicalities of the "trans-relational model"?

I did. throughouly. I have implemented an assembly disk only db core
supporting basic domain operations (union, intersection, division)
with select and insert's (*not* in the traditional sql sense)

> I can see its value for joins that don't involve projections of
> relations that have a great many attributes, however it seems to assume
> that all "tables" are pre-sorted

Not exactly. In TRM, only physical data layer is sorted in several
orders and because TRM does make a clean separation between data and
physical layers, *tables* (or R-tables) are not in the physical layer
aymore.

> (which for some apps I think is a
> reasonable assumption) and since "ORDERing" often involves permutations
> of attributes, I think that any implementation that supports ordering on
> multiple attributes must either pre-sort every permutation of attributes
> or implement the equivalent of a run-time sort.

paul,

TRM is the closest possible implementation of what might be an
independence between physical and logical layers. in TRM, the
predetermined *physical* pre-order of data serves the purpose of
allowing a nondeterministic logical odering of a specific R-Table (I
apologize, I just do not like using the term table). R-Tables are run
time built and their order is determined only through memory adresses
permutations. Therefore, one could say that the main advantage of the
computing model is that *logical* representation of data is indeed
sorted in several orders *almost* simultaneously.

> Sometimes I wonder if this is one reason why it might be thought
> deficient. I'm curious as to what others here might condider practical
> deficiencies.

Quite frankly I do not think order is a major drawback that could make
TRM deficient . From the experience I had in the last years, the main
drawback I have found is that it requires more mathematical tools to
support some undefined areas of TRM where basic computing operations
(permutations and combinations) are not sufficient anymore to
implement relational algebra concepts. For instance, at the moment I
am considering using vectorial mahematical tools to support the
implementation of run time domains.

Froe the results I have obtained, I can tell that TRM is the closest
computing model we have to what maybe some day a relational system but
that it requires much more time and effort to do the necessay math to
improve it. I believe the hastiness of Tarin to exploit it
commercially due to its obvious supriority over traditional direct
image is what caused its initial failure. IMHO.

> p

Reply to this Message

paul c - 08 Sep 2007 02:22 GMT

...

> Quite frankly I do not think order is a major drawback that could make
> TRM deficient . From the experience I had in the last years, the main
[quoted text clipped - 5 lines]
> implementation of run time domains.
> ...

just my attitude, but I think lack of ordering or grouping support is
right up there with lack of transitive closure logic as a most
unfortunate omission. maybe that goes back to the times when I couldn't
understand why either the biggest number or the smallest number wasn't
printed first on the 1403 fan-fold pages, preferably the largest
absolute number first AFAIWC. my attitude is probably completely
psychological and maybe pathological too as far as some are concerned.
can't give conventional, aka current, justification for that, sorry!

p

Reply to this Message

Cimode - 10 Sep 2007 10:08 GMT

> ...
>
[quoted text clipped - 18 lines]
>
> p

I kind of understand (and sympathize) to what you are refering to. I
believe that neither transitive closure nor unordered set nature could
be sufficiently clarified through a computing model definition (namely
TRM) without a anterior more explicit definition of unique identifiers
within RM (meaning with abstract mathematical tools other than
algebra). As long as such bricks are still missing at conceptual
level of RM, I hardly see any opportunity to imagine a computing model
that could help into solving such problem. I also hardly see any
opportunity of formulating a viable solution only through
experimentation of TRM. In other words, problem of transitive closure
must be solved in RM first before we may be able to experiment it in
some computing model such as TRM.

Sincerely hoping that will make sense.

I am afraid it would be simplyistic on my part to attempt definition
on this NG of the concepts

Reply to this Message