Databases Reference
In-Depth Information
a
time horizon
,
H
, representing the time interval during which the velocities
of the moving objects hold good. It assumes that the tree is constructed by
bulkloading the moving objects at some point in time (say
t
0
) and reconstructs
thetreeafter
H
. In essence, the tree is good during [
t
0
,t
0
+
H
]intervaland
all predictions made within this interval are acceptable in terms of the degree
of accuracy. The TPRs, organized as a hierarchical structure forms the TPR-
tree. At the bottom-most level of the hierarchy, a set of moving objects could
be grouped to form TPRs. Each TPR of the next higher level is the bounding
TPR of the set of TPRs of all of its children. The root of the hierarchy is thus
the bounding TPR covering all its lower level TPRs in a recursive manner.
The
S
TPR-Tree constructed by overlaying authorizations over the nodes
of the TPR-tree. For a given authorization
α
, we denote the spatiotemporal
extent of the authorization as
α
if the type of the authorization is
α
MS
or
α
SM
.Incaseof
α
MM
, we denote the spatiotemporal extent associated
with
α.se
as
α
S
and
α.ge
as
α
O
because we need to differentiate the spa-
tiotemporal extents because it could be from
se
or
ge
. Also, we denote the
spatiotemporal extent (TPR) of a node
N
as
N
.
Overlaying is done by traversing the tree recursively starting from the
root node to the leaf level and for each node
N
in the traversal path,
α
is
compared with
N
. We encounter the following possible cases:
•
Case 1:
The spatiotemporal extent of
α
fully encloses that of the node
N
. In this case the tree traversal will be stopped and
α
is overlaid on
N
.
This is because, if a subject is allowed to access objects within a certain
spatiotemporal region, it is allowed to access objects in the
subregion
of
that [4]. After overlaying an authorization on a node, it is not necessary
to overlay the same authorization on any of its descendants.
•
Case 2:
The spatiotemporal extent of
α
overlaps with that of the node
N
.If
N
is a non-leaf node, for each of
N
's children a comparison between
α
and child
is done. The goal here is to check if there exists a child
of
N
whose spatiotemporal extent is enclosed by that of
α
. On the other
hand, if
N
is a leaf node,
α
is overlaid on
N
. This is because, when the
spatiotemporal extent of the authorization
α
does not enclose, but over-
laps with that of the leaf node
N
, we need to ensure that no relevant
authorizations are discarded. Also, note that only part of the spatiotem-
poral extent of
N
is in the authorized region. The moving objects from
the remaining unauthorized spatiotemporal region must be removed from
the user's output, if the user request includes this region.
Case 3:
If neither of the above is true,
α
is disjoint with that of
N
.
Then the overlaying process is stopped. This is because, if
α.se
does not
have a privilege to the region covered by
N
, then
α
is not applicable
to that region. Also, since
N
includes spatiotemporal extent of all of its
children nodes,
α
is disjoint with the spatiotemporal extent of each child.
Thus, there is no need to traverse further down the tree.
•
