Computing Local Sensitivities of Counting Queries with Joins

Yuchao Tao, Xi He, Ashwin Machanavajjhala, Sudeepa Roy

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.

Figure 1: Example of a database instance, its join result, hypergraph representation, and corresponding join tree.

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:

  1. TPC-H Benchmark: A standard synthetic dataset for complex database queries, scaled from thousands to millions of rows.
  2. 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), TSens achieved a local sensitivity bound 2.2 million times tighter than the Elastic sensitivity algorithm.
  • Enhanced DP Accuracy: In comparative tests against PrivSQL, TSensDP significantly reduced error rates. While PrivSQL produced errors exceeding 99% for most queries, TSensDP maintained error rates below 8% for nearly all tested scenarios.
  • Computational Efficiency: Although TSens is 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

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.
BibTeX
@inproceedings{tao2020computing,
  author = {Yuchao Tao and Xi He and Ashwin Machanavajjhala and Sudeepa Roy},
  title = {{Computing Local Sensitivities of Counting Queries with Joins}},
  booktitle = {SIGMOD},
  year = {2020},
  url = {https://openreview.net/forum?id=JzKZPgTo74f},
}
Figure