中文摘要：

数据库外包是将数据库管理工作外包给专业第三方，而数据库外包中需要解决的关键问题之一是查询结果的验证．提出了外包追加型数据库的问题．根据外包追加型数据库的特点，在现有验证数据结构的基础上，提出了一种新型验证数据结构Min—MaxHashTree，可以有效地解决客户对查询结果进行验证的问题．对于数据所有者端，给出了基本的数据发送算法；对于服务提供商端，分别给出了一次性查询和连续查询的查询算法和查询结果验证算法．最后，对数据所有者端的验证数据结构的存储、数据发送和服务提供商端的连续查询进行了优化处理，大大节省了数据所有者端的存储空间，提高了数据的整体处理效率．实验表明，MinMaxHashTree能够有效完成追加型数据库外包的查询结果验证，并且能够高效率处理大规模数据．

英文摘要：

In the scenario of database outsourcing, database management is outsourced to the professional third-party, and one of the critical problems is integrity authentication of the query results. As far as we are concerned, we are the first to propose the problem of outsourced append-only database. According to the features of outsourced append-only database, a new authentication data structure, Min-Max Hash tree is proposed based on the current authentication data structure. It can be utilized by the clients to solve the problem of authenticating the query results. For the data owner side, a basic data forwarding algorithm is proposed; and for the service provider side, the algorithm of querying rise, fall or oscillation amplitude in price and the algorithm of query results authentication are proposed respectively for one-shot query and continuous query. Finally, optimization measures are proposed for data forwarding, storage of authenticated data structure in the data owner side and continuous query in the service provider side, by which the space of storage is diminished greatly and the whole efficiency of data processing is improved further. Extensive experiments have demonstrated the effectiveness and efficiency of the proposed Min-Max Hash tree. It can be utilized to authenticate the query results and to process the massive data.