Abstract
Local sensitivity of a query $Q$ given a database instance $D$, i.e. how much the output $Q(D)$ changes when a tuple is added to $D$ or deleted from $D$, has many applications including query analysis, outlier detection, and in differential privacy. However, it is NP-hard to find local sensitivity of a conjunctive query in terms of the size of the query, even for the class of acyclic queries. Although the complexity is polynomial when the query size is fixed, the naive algorithms are not efficient for large databases and queries involving multiple joins. In this paper, we present a novel approach to compute local sensitivity of counting queries involving join operations by tracking and summarizing tuple sensitivities -- the maximum change a tuple can cause in the query result when it is added or removed. We give algorithms for the sensitivity problem for full acyclic join queries using join trees, that run in polynomial time in both the size of the database and query for an interesting sub-class of queries, which we call 'doubly acyclic queries' that include path queries, and in polynomial time in combined complexity when the maximum degree in the join tree is bounded. Our algorithms can be extended to certain non-acyclic queries using generalized hypertree decompositions. We evaluate our approach experimentally, and show applications of our algorithms to obtain better results for differential privacy by orders of magnitude.
Introduction
In the realm of database privacy, Differential Privacy (DP) is the gold standard for protecting individual records while allowing for aggregate data analysis. The core mechanism of DP involves adding statistical noise to query results, where the noise magnitude is proportional to the query's sensitivity—the maximum change in output caused by adding or removing a single tuple.
While sensitivity is straightforward for simple aggregations, it becomes computationally prohibitive for queries involving joins. A single row addition in one table can cascade through multiple joins, potentially generating thousands of new output rows. Existing methods often resort to loose global sensitivity bounds, which introduce excessive noise and render the data useless, or face exponential computational costs. This research addresses these challenges by providing a practical, efficient method for computing tight local sensitivity bounds for complex join queries.
Methodology: The TSens Algorithm
The authors introduce TSens, an algorithm designed to compute the sensitivity of every tuple in a database without exhaustive simulation.
Join Trees and Multiplicity
For acyclic queries, TSens utilizes a "join tree" representation. It employs a dynamic programming approach, performing a bottom-up pass ("botjoins") and a top-down pass ("topjoins") to track the multiplicity of join paths for every tuple. The sensitivity of a specific tuple is derived from the product of these incoming and outgoing paths.
Handling Upward Sensitivity
A key innovation is the handling of "upward sensitivity"—the impact of adding a new, previously non-existent tuple. TSens manages this by restricting the search to a "representative domain" of active values, ensuring the computational complexity remains polynomial relative to the database size.
Differentially Private Truncation (TSensDP)
Standard DP mechanisms often struggle with join queries because their global sensitivity can be theoretically unbounded. TSensDP addresses this by using the computed tuple sensitivities to perform targeted truncation. By identifying and removing only the most sensitive tuples, the algorithm caps global sensitivity with minimal impact on data utility, allowing for significantly less noise addition.
Experimental Evaluation
The approach was evaluated using two primary datasets:
- TPC-H Benchmark: A standard synthetic dataset for complex database queries, scaled from thousands to millions of rows.
- Facebook Ego-networks (SNAP): A real-world social network dataset used to test complex graph-based join queries.
Key Results and Insights
The experiments demonstrated that TSens provides substantial improvements over existing state-of-the-art methods:
- Tighter Sensitivity Bounds: For a cyclic query on a large database (~866,000 tuples),
TSensachieved a local sensitivity bound 2.2 million times tighter than theElasticsensitivity algorithm. - Enhanced DP Accuracy: In comparative tests against
PrivSQL,TSensDPsignificantly reduced error rates. WhilePrivSQLproduced errors exceeding 99% for most queries,TSensDPmaintained error rates below 8% for nearly all tested scenarios. - Computational Efficiency: Although
TSensis more complex than simpler heuristics, its overhead remains manageable, typically adding between 80% and 320% to the standard query evaluation time.
Conclusion and Future Work
TSens represents a significant advancement in the practical application of differential privacy to complex relational queries. By leveraging join tree structures and tuple-level sensitivity tracking, it enables high-utility data analysis that was previously impossible due to noise constraints.
Future research will focus on extending the algorithm to handle self-joins, where a single table appears multiple times in a query, and optimizing memory usage for extremely large-scale cyclic queries by employing top-$k$ frequency approximations.
Summary updated