Databases Reference
In-Depth Information
partitioning of attributes, the mapping functions, etc. The client utilizes this
information to translate a given query
Q
to its server-side representation
Q
S
,
which is then executed by the server. More details can be found in [26].
Translating Relational Operators
Now let us give an idea of how relational operators are implemented in [26].
We illustrate the implementation of the selection and join operators in the
proposed architecture. The strategy is to partition the computation of the
operators across the client and the server such that a superset of answers is
generated by the operator using the attribute indices stored at the server. This
set is then filtered at the client after decryption to generate the true results.
The goal is to minimize the work done at the client (as much as possible).
We use
R
and
T
to denote two relations, and use the operator notations in [17].
σ
The Selection Operator (σ)
:
Consider a selection operation
C
(
R
)onare-
lation
R
, where
C
is a condition specified on one or more of the attributes
A
1
,A
2
,...,A
n
of
R
. A straightforward implementation of such an operator
is to transmit the relation
R
S
from the server to the client. Then the client
decrypts the result using the
D
operator, and implements the selection. This
strategy, however, pushes the entire work of implementing the selection to
the client. In addition, the entire encrypted relation needs to be transmitted
from the server to the client. An alternative mechanism is to partially com-
pute the selection operator at the server using the indices associated with the
attributes in
C
, and push the results to the client. The client decrypts the
results and filters out tuples that do not satisfy
C
. Specifically, the operator
can be rewritten as follows:
C
D
(
Map
cond
(
C
)
R
S
)
σ
σ
σ
S
C
(
R
)=
σ
operator that executes at the server is adorned with a
superscript “
S
”. All non-adorned operators execute at the client. The decryp-
tion operator
D
will only keep the attribute
etuple
of
R
S
, and drop all the
other
A
i
attributes. We explain the above implementation using an example
σ
eid<
395
∧did
=140
(
emp
). Based on the definition of
Map
cond
(
C
) discussed in
the previous section, the above selection operation will be translated into
Note that the
C
D
(
C
emp
S
)
σ
σ
S
where the condition
C
on the server is:
C
=
Map
cond
(
C
)=
eid
S
did
S
=4
∈
[2
,
7]
∧
)
:
Consider a join operation
R
C
S
. The join condition
C
could be either an equality condition (in which case the join corresponds to
The Join Operator (
