Managing and Querying Encrypted Data - Database Security: Applications and Trends - page 169

an equijoin), or could be a more general condition (resulting in theta-joins).
The above join operation can be implemented as follows:

C D R S Map cond ( C ) T S

C T =

S

σ R

As before, the S adornment on the join operator denotes the fact that the
join is to be executed at the server. For instance, join operation

emp.did = mgr.did mgr

emp

is translated to:

C D emp S

mgr S

S
C

σ

where the condition C on the server is condition C 1 defined in Section 2.3.
Now we show how the above operators are used to rewrite SQL queries
for the purpose of splitting the query computation across the client and the
server.

Query Execution

Given a query Q , the goal is to split the computation of Q across the server
and the client. The server will use the implementation of the relational oper-
ators discussed in the previous subsection to compute “as much of the query
as possible”, relegating the remainder of the computation to the client. Query
processing and optimization have been extensively studied in database re-
search [20, 12, 41]. The objective is to come up with the “best” query plan
for Q that minimizes the amount of work to be done at the client site. In this
setting, the cost of a query consists of many components - the I/O and CPU
cost of evaluating the query at the server, the network transmission cost, and
the I/O and CPU cost at the client. As an example, consider the following
query over the emp table than retrieves employees whose salary is greater that
the average salary of employees in the department identified by did =1.

SELECT emp.name FROM emp
WHERE emp.salary > (SELECT AVG(salary)
FROM emp WHERE did = 1);

The corresponding query tree and some of the evaluation strategies are
illustrated in Figures 3 to 6. The first strategy (Figure 4) is to simply trans-
mit the emp table to the client, which evaluates the query. An alternative
strategy (Figure 5) is to compute part of the inner query at the server, which
selects (as many as possible) tuples corresponding to Map cond ( did = 1). The
server sends to the client the encrypted version of the emp table, i.e., emp S ,
along with the encrypted representation of the set of tuples that satisfy the
inner query. The client decrypts the tuples to evaluate the remainder of the
query. Yet another possibility (Figure 6) is to evaluate the inner query at the