Databases Reference
In-Depth Information
R1
R2
AE
F
B
CD
(a)
y
A
B
R2
R1
x
F
D
C
E
t
(b)
Figure 8.3
Retrieval of overlap_during operator using 3D R-trees.
(stored in secondary memory as disk pages). The MBRs of the actual data
objects are assumed to be stored in the leaf nodes of the tree. Intermediate
nodes are built by grouping rectangles (or hyperrectangles, in general) at
the lower level. An intermediate node is associated with some rectangle that
encloses all rectangles that correspond to lower level nodes. To retrieve
objects that belong to the answer set of a spatiotemporal operator, with respect
to a reference object, we have to specify the MBRs that could enclose such
objects and then search the intermediate nodes that contain those MBRs. This
technique was proposed and implemented in [14] to support spatial operators
of high resolution (e.g., meet, contains) that are popular in GIS applications.
As an example, Figure 8.3(b) shows how the MBRs corresponding
to the presentations of the objects are grouped and stored in the three-
dimensional R-tree of our unified scheme. We assume a branching factor of
4, that is, each node contains, at most, four entries. At the lower level, MBRs
of objects are grouped into two nodes, R1 and R2, which in turn compose
the root of the index. We consider a spatiotemporal query, that is, the over-
lap_during operator, with D being the reference object q.Toanswerthis
query, only R2 is selected for propagation. Among the entries of R2, objects C
and (obviously) D are the ones that constitute the qualified answer set. Note
that only the right subtree of the R-tree index in Figure 8.3(a) was propagated
