Verifying completeness of relational query results in data publishing

Abstract

In data publishing, the owner delegates the role of satisfy- ing user queries to a third-party publisher. As the publisher may be untrusted or susceptible to attacks, it could produce incorrect query results. In this paper, we introduce a scheme for users to verify that their query results are complete (i.e., no qualifying tuples are omitted) and authentic (i.e., all the result values originated from the owner). The scheme sup-ports range selection on key and non-key attributes, project as well as join queries on relational databases. Moreover, the proposed scheme does not conflict with access control policies, is computationally secure, and can be implemented efficiently.