[boost] RTL: Relational Template Library

From: Arkadiy Vertleyb (vertleyb_at_[hidden])
Date: 2005-10-05 08:17:18

Hi All.

I just uploaded the latest version of  Dmitriy Arapov's and my Relational
Template Library (RTL) to the Boost file vault, http://tinyurl.com/8lbmg.
This version is compatible with Boost 1.33.

The RTL was discussed on this list at some time in the past.  The early
version of RTL is described in the March 2004 issue of CUJ.  The main
difference from currently discussed RML is that we decided against using
SQL - like interface, and use the relational algebra-based interface
instead.

This choice is caused by our belief that the optimizer -- the module
converting SQL query into an optimized relational expression -- is one of
the most sophisticated parts of modern database engines.  Also, writing a
good optimizer in a system like RTL (or RML) would have to be done in large
part at compile time, by the means of template meta-programming.  This task
doesn't seems to be feasible, at least currently.

OTOH, writing a primitive optimizer, would, in our opinion do more harm than
good.

So, the RTL gives its user the possibility to build arbitrary relational
expressions by hand.  We augment the pure relational algebra with a few
things, such as sort order, indexing, groupby, join, etc.  We also allow
indexing of any relational expressions, not just tables.

So, for example, a user can do a selection on some arbitrary complicated
criteria, and then index this selection.  This would ultimately result in
the index storing just keys to these records.  This index would be
incrementally updated when the underlying table has been changed.

Achieving the same effect with conventional approach would require creation
of a much larger index on a calculated field.

Another example -- you have table of cities, and you need to get all the
pairs, such as the distance between them is less than certain number.  How
would one solve the problem with the conventional SQL approach?  This is a
self-join.  But how to make this query fast?

With RTL approach, we could create an index on this self-join.

The RTL can currently be compiled with VC7.1 or GCC 3.3+ (although with GCC
there might still remain some naming conflicts between MPL and STL, that
show up with certain usages)

Regards,
Arkadiy