数据库作为一个已经发展了几十年的相对成熟的领域，衍化的诸多产品比如IBM DB2，Oracle DB，Microsoft SQL Server已经成为了当前诸多的信息系统的重要组成部分。但是，由于数据库其灵活性以及复杂性，部署数据库应用往往需要投入大量的专职数据库管理人员(DBA)来跟踪数据库的状态，随时对数据库结构，索引，存储以及其上的事务处理进行调整、优化，以满足企业日常应用的需要。而且，数据库产品，其对应硬件的采购以及软件、硬件升级、维护都需要相当巨大的开销。所以，对于规模较小的企业以及个人而言，选择购买数据库产品，进行部署并维护所有的软硬件是非常昂贵的并且不现实的。因此，将数据库作为一种服务Database-As-A-Service），由专门的数据库服务提供商来提供所有的支持，而将所有的软件、硬件及维护开销从客户的负担中分离出来就自然而言地成为了一种必然，对因为数据问题困扰的小规模企业以及个人用户而言，提供了一种灵活的选择。　　虽然数据库外包服务有很多优点，但是一个制约其发展的重要因素是外包数据库中的安全问题。对于企业或者个人等数据拥有者而言，数据库中的数据往往存在很多涉及其隐私而不应被外界访问到的信息，因此，简单的将数据以原文的方式发送到未知的第三方服务提供商会导致用户的隐秘信息泄露。其次，由于第三方服务提供商不是完全可信任的服务提供者，客户对数据的访问很有可能被服务提供商攻击。比如，服务提供商为了节省访问开销，只对部分数据进行访问，对于用户提出的访问请求只返回部分的结果。再次，服务提供商很有可能被客户的竞争对手收买，从而泄露客户的所有数据信息，访问信息给客户的竞争对手。　　本文针对外包数据库的安全性问题以及之前工作效率低下以及不能处理复杂查询等问题，提出了一种创新的基于概率的解决方案，利用顺序保持的加密算法保证数据的隐秘性，同时，通过向外包数据库中添加额外的用监测的元组来有效地验证各种查询的正确性。　　本文的贡献主要体现在下面几个方面:　　1.本文提出了一种基于概率的完整性验证方案。通过向外包数据中添加额外的监测元组，本文提出的方法可以有效地验证选择查询服务的正确性。　　2.本文提出了两种实现该机制的方法，一种基于随机监测元组的方法，以及另一种基于函数的改良方法。并且，本文提出一种空间划分优化方法，大大提高了方法验证服务正确性的成功率。　　3.通过扩展基于检测元组的基本方法，本文提出了有效的用于验证连接查询以及更新查询的方法。　　4.本文通过大量真实数据以及合成数据上的实验，验证了提出方法在保证外包数据库完整性上的有效性，在客户端以及服务器端存储和查询的高效性。