While there is a large and growing body of literature on differentially private mechanisms for answering various classes of queries, to the best of our knowledge “count-range” queries have not been studied. These are a natural class of queries that ask “is the number of rows in a relation satisfying a given predicate between two integers θ1 and θ2?” Such queries can be viewed as a simple form of SQL “having” queries. We begin by developing a provably optimal differentially private mechansim for count-range queries for a single consumer. For count queries (in contrast to count-range queries), Ghosh et al. [] have provided a differentially private mechanism that simultaneously maximizes utility for multiple consumers. This raises the question of whether such a mechanism exists for count-range queries. We prove that the answer is no — for count range queries, no such mechanism exists. However, perhaps surprisingly, we prove that such a mechanism does exist for “threshold” queries, which are simply count-range queries for which either θ1 = 0 or θ2 = +∞. Furthermore, we prove that this mechanism is a two-approximation for general count-range queries.
展开▼
