外包数据库中的哈希连接一致性算法

Algorithm for Authenticated Hash Join Processing in Outsourced Database

外包数据库中的连接查询比范围查询更困难,因为客户端需要验证连接结果的一致性,而传统的对单个表的签名不能有效地支持对连接查询结果的直接验证。提出了使用哈希连接保证数据一致性的2种算法,它们分别通过在服务器端和客户端计算哈希函数来实现连接查询。给出了这2种算法的详细描述,证明了它们满足一致性要求,而且分析了算法在通信量、服务器端和客户端执行的代价。最后在实验中通过设置不同的参数对它们在服务器端和客户端的运行时间进行了比较,总结了它们在实际应用中的优缺点。

In outsourced database,authenticated join processing is more difficult than authenticated rang queries because the previous approach for signature on a single relation can not be used to verify join results directly.This paper providedtwo kinds of authenticated hash join processing algorithms,which respectively compute hash functions by database service provider and by client.These two methods were described in detail and proved to guarantee the authenticity of join results.The analysis of the performance was presented with respect to cost factors,such as communication cost,server-side cost and client-side cost.Finally,we experimentally compared the two methods on the running time of server-side and client-side in different parameters and summarized their advantages and disadvantages in the application.