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

Key words: Database security, Outsourced database, Hash join, Data authenticity