TSQLRecordRTree to implement R-Tree virtual tables

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.

Synopse Open Source

TSQLRecordRTree to implement R-Tree virtual tables

Add ping