TSQLRecordRTree to implement R-Tree virtual tables
By A.Bouchez on 2011, Thursday June 2, 15:00 - SQLite3 Framework - Permalink
An R-Tree is a special index that is designed for doing range queries.
R-Trees are most commonly used in geospatial systems where each entry is a rectangle with minimum and maximum X and Y coordinates. Given a query rectangle, an R-Tree is able to quickly find all entries that are contained within the query rectangle or which overlap the query rectangle.
This idea is easily extended to three dimensions for use in CAD systems. R-Trees also find use in time-domain range look-ups. For example, suppose a database records the starting and ending times for a large number of events. A R-Tree is able to quickly find all events, for example, that were active at any time during a given time interval, or all events that started during a particular time interval, or all events that both started and ended within a given time interval. And so forth. See http://www.sqlite.org/rtree.html
Since the 2010-06-25 source code repository update, the RTREE extension is
compiled by default within all supplied .obj files of the
framework.
A dedicated ORM class, named TSQLRecordRTree, is available to
create such tables. It inherits from TSQLRecordVirtual, like the
other virtual tables types (e.g. TSQLRecordFTS3 or
our custom virtual
tables).
Any record which inherits from this TSQLRecordRTree class must
have only sftFloat (i.e. Delphi double) published
fields, grouped by pairs, each as minimum- and maximum-value, up to 5
dimensions (i.e. 11 columns, including the ID property).
Its ID: integer property must be set before adding a
TSQLRecordRTree to the database, e.g. to link an R-Tree
representation to a regular TSQLRecord table containing the main
data.
Queries against the ID or the coordinate ranges are almost immediate: so you
can e.g. extract some coordinates box from the main regular
TSQLRecord table, then use a TSQLRecordRTree-joined
query to make the process faster; this is exactly what the
TSQLRestClient. RTreeMatch method offers: for instance, running
with aMapData. BlobField filled with
[-81,-79.6,35,36.2] the following lines:
aClient.RTreeMatch(TSQLRecordMapData,'BlobField',TSQLRecordMapBox, aMapData.BlobField,ResultID);
will execute the following SQL statement:
SELECT MapData.ID From MapData, MapBox WHERE MapData.ID=MapBox.ID
AND minX>=:(-81.0): AND maxX<=:(-79.6): AND minY>=:(35.0): AND :(maxY<=36.2):
AND MapBox_in(MapData.BlobField,:('\uFFF0base64encoded-81,-79.6,35,36.2'):);
The MapBox_in SQL function is registered in
TSQLRestServerDB. Create constructor for all
TSQLRecordRTree classes of the current database model. Both
BlobToCoord and ContainedIn class methods are used to
handle the box storage in the BLOB.
By default, it will process a raw array of double, with a
default box match (that is ContainedIn method will match the
simple minX>=...maxY<=... where clause).
Feedback and comments are welcome on our forum.