Efficient inference control for range Sum queries

Abstract

The inference control technique called Auditing is discussed in this paper. Auditing is in many ways better than the previously known techniques. Auditing would log all answered queries, and use this information to decide whether answering a new query could lead to compromise. Unfortunately, expect for small databases, auditing may not be readily usable in practice because of its excessive time and space complexity in processing a new query. In this paper we restrict our study to Sum queries, if there are n records in the database, the problem of determining whether or not answering a new Sum query could lead to compromise may take O(n2) time and space. Furthermore, it is unrealistic to assume that the user can obtain statistical information of any subset of the records in the database; we assume that statistical information is only available for those subsets of records in which one of their attribute values lies within a certain range (range query). With the proper data structure, the time and space complexity for checking if a new range query could be answered can be reduced to O(n) time and space, or O(t log n) time with O(n2) space for t new range queries with t≥n. © 1984.