Databases Reference
In-Depth Information
index structure, like the R-tree, can be used to create verification objects
for multi-dimensional data. The tree is extended with hash values that are
computed using both the hash values of its children nodes in the tree and the
multi-dimensional information that is used to navigate the tree. For the R-tree,
this means that the hash value for a node
N
will contain all the hash values
and the MBR's of the children nodes of
N
. Signature based approaches can
be also used [34, 31]. Furthermore, aggregation queries can be authenticated
using aggregation trees [35, 36]. The only difference is that the aggregate value
of each subtree should be included in the computation of the hash values. That
is, for each node
N
of an aggregation tree we add the aggregate value of the
subtree that starts at
N
and we include this in the hash value of the node [37].
General Query Types.
The authenticated structures presented before can
support other query types as well. We briefly discuss here a possible extension
of these techniques for join queries. Other query types that can be supported
are projections and relational set operations.
Assume that we would like to provide authenticated results for join queries
such as
R
A
i
=
A
j
S
, where
A
i
∈
S
(
R
and
S
could be relations
or result-sets from other queries), and authenticated structures for both
A
i
in
R
and
A
j
in
S
exist. The server can provide the proof for the join as
follows: 1. Select the relation with the smaller size, say
R
, 2. Construct the
VO
for
R
(if
R
is an entire relation then the
R
and
A
j
∈
VO
contains only the signature
of the root node from the index of
R
), 3. Construct the
VO
s for each of the
following selection queries: for each record
r
k
in
R
,
q
k
=“SELECT * FROM
S
WHERE
r.A
j
=
r
k
.A
i
”. The client can easily verify the join results. First,
it authenticates that the relation
R
is complete and correct. Then, using the
VO
for each query
q
k
, it makes sure that it is complete for every
k
(even when
the result of
q
k
is empty). After this verification, the client can construct the
results for the join query and be sure that they are complete and correct.
7 Conclusion
In this chapter we presented three approaches to authenticate range queries
in ODBs. The first approach is based on signature chaining and aggregation,
the second on combining a Merkle hash tree with a B+-tree and the third is
an improved version of the hash tree approach. We discussed advantages and
disadvantages of each approach and we gave an analytical cost model for each
approach and different cost metrics. Finally, we discussed the performance of
each method under a dynamic environment and we gave extensions of these
techniques to other query types. A interesting future direction is to enhance
the proposed methods to work eciently for complex relational queries. An-
other direction is to investigate authentication techniques for other types of
databases beyond relational databases.
