DProvSQL: Accuracy-Aware Privacy Provenance Framework for Differentially Private SQL Engine

Recent years have witnessed the adoption of differential privacy (DP) in practical database query systems. Such systems, like PrivateSQL and FLEX, allow data analysts to query sensitive data while providing a rigorous and provable privacy guarantee. However, existing systems may use more privacy budgets than necessary in certain cases where different data analysts with different privilege levels ask a similar or even the same query. In light of this deficiency, we propose \oursystem, a fine-grained privacy provenance framework that tracks the privacy loss to each single data analyst and we build algorithms that make use of this framework to maximize the number of queries that could be answered. We implement \oursystem as a middleware between the data analysts and the existing differentially private SQL query answering systems. The empirical results on the TPC-H dataset show that our approach can answer around 4x more queries than the baseline approach on average with marginal performance overhead