[boost] Relational Templates enhanced: indexing added, etc.

From: Arkadiy Vertleyb (vertleyb_at_[hidden])
Date: 2002-10-23 12:37:01

Hi Boosters,

A few month ago we introduced a relational algebra library, which provided a
C++ programmer with the following:

1. A "relational table" container, that allows to have columns of any
built-in or user-defined type.  That means one could define a tuple that
contains, e.g., integers, strings, pointers, functors, or objects of any
other type.  The access to fields is done in a type-safe manner.

2. A full set of relational operations, such selection, projection,
x-product, etc.

A number of people expressed certain interst.  We were pointed out that
there are two major problems with the library:

1. All the operations are done sequentially, which maybe very slow even if
the data is located in memory.

2. The implementation of the table is too much integrated into the system,
thus making it difficult to provide alternative ones.  These alternative
implementations could, for example, utilize disk storage instead of keeping
all the data in memory.

We are greatfull for all the coments.  Specifically, we would like to thank
Greg Colvin for providing invaluable insights on the indexing issue, as well
as general encouragememt.

So now we are offering to your attention an enhanced version of the library
that is intended to be free from the above drawbacks.  We introduced range
queries based on either original sort order of the table, or indexes that
can be created from the original table.  Both tables and operators can be
range-queried, and both tables and operators can be indexed.

We also achieved a better separation of the table implementation from the
rest of the system.  Although we did not try to provide an alternative
implementation ourselves, we think there should be no problem with this.  We
are planning to do it in the future.  If there is someone who would like to
contribute in this area (or in any other part of the library) he/she is
wellcome.

Finally, we think that such a library could bring relational algebra into
the areas where it previously wasn't considered because of the overhead the
traditional systems contain.  Consider, for example, simulation tasks or
game programming.  Which particles hit each other at this particular moment?
The ones whose coordinates are equal.  How to find all the pairs?  This task
is tailored for join.  How to determine integral characteristics of the
system?  Use groupby.  etc..  Most importantly those are still first-class
objects, that can live their own life, move, interact, etc.  Just instead of
placing them in the vector, one can put them in a relational table, and have
all the means of relational algebra at hand.

Here is the link:

http://groups.yahoo.com/group/boost/files/tables.zip

Any comments are appriciated.

Arkadiy Vertleyb
Dmitriy Arapov