Source-linked AI summary
Differentially Private SQL with Bounded User Contribution
Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, Bryant Gipson
TL;DR
Existing differentially private query engines assume one record per individual, which is unrealistic when users contribute many rows. This paper develops and implements a user-level contribution-bounding mechanism for SQL aggregations, tests it on typical queries, and validates it with stochastic privacy checks. The authors report that the approach is useful, robust, and scalable, while identifying accuracy improvements and usability studies as future work.
Problem
Existing differentially private query engines assume each individual is associated with at most one database record, although real datasets may contain arbitrarily many rows per individual.
Method
The paper expresses user-level contribution bounding as a relational-algebra operator and implements it in a SQL engine with bounded aggregations, joins, and stochastic privacy testing.
Results
The authors report that the system performs well for typical use-cases and is useful, robust, and scalable based on empirical evidence.
Takeaways & Limitations
Contribution bounds can support practical user-level differential privacy for realistic data with multiple contributions per user and may generalize beyond SQL-based mechanisms.
Takeaways & Limitations
The system restricts some queries, and extending it to a wider class may require different query semantics for queries with unbounded sensitivity.
Abstract
from arXiv · showhide
Differential privacy (DP) provides formal guarantees that the output of a database query does not reveal too much information about any individual present in the database. While many differentially private algorithms have been proposed in the scientific literature, there are only a few end-to-end implementations of differentially private query engines. Crucially, existing systems assume that each individual is associated with at most one database record, which is unrealistic in practice. We propose a generic and scalable method to perform differentially private aggregations on databases, even when individuals can each be associated with arbitrarily many rows. We express this method as an operator in relational algebra, and implement it in an SQL engine. To validate this system, we test the utility of typical queries on industry benchmarks, and verify its correctness with a stochastic test framework we developed. We highlight the promises and pitfalls learned when deploying such a system in practice, and we publish its core components as open-source software.
1 Introduction
Differential privacy protects individuals while enabling aggregate analysis, but existing SQL engines often assume one record per person. This work introduces user-level contribution bounding, implements it in a SQL engine, and supports testing and open-source adoption.
- Differential privacy formally limits how much an algorithm’s output reveals about an individual in sensitive data.
- Existing differentially private query engines typically assume each individual contributes at most one database record, weakening their guarantees on many real-world datasets.
- The system includes stochastic privacy testing, accuracy communication for analysts, and common SQL aggregations such as counts, sums, and medians.
- The proposed engine enforces user-level privacy by allowing multiple rows per owner and bounding sensitivity across aggregations, transforms, and joins.
- Core aggregation operations and the stochastic tester are released as open-source software to support reproducibility and adoption.
2 A simple example: histograms
A histogram query can leak users through repeated rows, newly appearing GROUP BY keys, or contributions spread across many partitions. The proposed solution bounds user contributions, filters low-count keys, and extends the mechanism to broader aggregations and joins.
- User contribution: Adding Laplace noise to row counts protects records but not users who contribute arbitrarily many rows.
- User contribution: Counting distinct users bounds each partition’s sensitivity, while allowing multiple contributions requires increasing sensitivity to the permitted maximum.
- GROUP BY keys: A newly appearing GROUP BY key can reveal a record regardless of noisy counts, so low-count keys are removed using τ-thresholding.
- Multiple partitions: Users contributing to many partitions can create unbounded sensitivity, so the mechanism randomly retains contributions to at most C_u partitions per user.
- Multiple partitions: The resulting noise scale is C_u/ε, and the approach is extended to bounded-sensitivity aggregations and joins.
3 System model and design
The system bounds user contributions across partitions and within partitions, then applies differentially private aggregate functions in a SQL engine. It enforces row-ownership constraints, supports bounded aggregates, and provides user-level (ε, δ)-DP guarantees, although some queries remain unsupported.
- System model: Users may own multiple rows, so the system tracks a user-identifier column as the protected ownership unit.The identifier can represent a user, device, organization, or unique row ID.
- System design: The engine combines custom SQL aggregation operators with a query rewriter that validates and enforces anonymization semantics.The underlying SQL engine tracks user-ID metadata and invokes rewriting for anonymization queries when permission checks succeed.
- Contribution bounding: The two-stage operator first aggregates by user and group, samples at most Cu partial rows per user, and then performs the cross-user DP aggregation.This ensures that the second stage receives at most one input row per user in each partition.
- Bounded aggregation: Each aggregate clamps inputs to lower and upper bounds when needed, then adds Laplace noise calibrated to the resulting sensitivity.ANON_AVG, ANON_VAR, and ANON_STDDEV derive noisy statistics from bounded sums, counts, means, and squares; ANON_NTILE uses noisy Bayesian binary search.
- Sensitivity analysis: Table 1 provides sensitivity bounds for the aggregate suite, but the authors state that these bounds are loose and emphasize boundedness and order of magnitude.The bounds assume at least one contributing user and depend on U and L.
- Limitations: Restricting intermediate rows to single-user ownership limits the system because some queries cannot be run.The authors report that most practical use cases fit the constraints and leave broader query support for future work.
- Privacy guarantee: The engine satisfies user-level (ε, δ)-DP by calibrating aggregate privacy parameters from ε, δ, and Cu.The construction allows both user-privacy parameters to be bounded arbitrarily small by analysts and data owners.
4 Accuracy
The system’s accuracy is evaluated on TPC-H queries and through parameter studies covering thresholding, contribution bounds, and clamping. Results show comparable accuracy to PINQ under correct sensitivity bounds, while thresholding and parameter choices materially affect error.
- TPC-H evaluation: The evaluation uses TPC-H, an industry-standard benchmark with joins and varied aggregations, measuring utility by median relative error.A smaller median relative error indicates higher utility.
- Aggregation comparisons: With correctly set sensitivity bounds, the model’s count and average results are comparable to PINQ’s, while its median error is lower by a factor of 2.Flex does not support average or median, preventing those comparisons.
- Aggregation comparisons: Both PINQ and the model outperform Flex’s count result by around an order of magnitude, but incorrectly set bounds can produce results that are not differentially private.The comparison disables τ-thresholding and uses fixed sensitivity for fairness.
- Aggregations with joins: Across joined TPC-H queries, little τ-thresholding produces low error, whereas many low-user-count partitions can cause very large error or uninterpretable results.Q4 has little thresholding; Q16 and Q21 remove most partitions, while Q13 has moderate thresholding and remains quite accurate.
- Effect of δ and Cu: As δ increases exponentially, the proportion of thresholded partitions decreases somewhat linearly.This relationship is measured on TPC-H Query 13 with ε = .1.
- Effect of δ and Cu: Increasing Cu lowers median percent error across distributions, but the decline rate depends on distribution shape.The study uses N = 1000 and distributions centered at 100.
- Effect of clamping: Clamping accuracy depends on balancing an overestimated input spread against restricted sensitivity, with an optimal point varying across ε.The analysis uses uniform inputs on [50, 150], N = 100, and a lower bound of −200.
5 Practical considerations
The system addresses practical usability and assurance challenges through automatic bounds, utility reporting, thresholding support, and stochastic testing. Deployment testing also exposed implementation pitfalls, including floating-point and noisy-threshold errors that can violate privacy.
- 5.1 Usability: Analysts must provide bounds for inputs such as ANON_SUM, creating a workflow burden when they lack prior knowledge of the data.The system addresses this with APPROX_BOUNDS(col), which automatically computes bounds intended to minimize accuracy loss.
- 5.1.1 Automatic bounds determination: APPROX_BOUNDS(col) uses a differentially private logarithmic histogram to select approximate extrema, while balancing clipping, false positives, and failure risk.The method allocates privacy budget to bound inference and noisy aggregation, and supports signed and floating-point values.
- 5.1 Usability: The engine reports utility information through confidence intervals for added noise and an estimated fraction of inputs exceeding automatically selected bounds.Confidence intervals do not account for clamping or thresholding effects; low-count partitions may also be combined into a reported leftovers partition.
- 5.2 Manual testing: Floating-point special values and rounded Laplace noise can create privacy risks: NaN values may bypass contribution bounds, while rounding can underestimate δ in τ-thresholding.The authors recommend error hardening and use of an unrounded Laplace mechanism for thresholding, while noting that complete mitigation is difficult.
- 5.3 Testing: Stochastic testing explores database pairs and compares output distributions against the DP predicate, detecting implementation violations without proving differential privacy.The tests focus on DP primitives in isolation, while contribution bounding is tested separately; end-to-end user-level DP testing remains future work.
- 5.3.4 Case study: noisy average: Testing found that an incorrect ANON_AVG implementation violated DP, and the stochastic tester detected a later sensitivity regression in the corrected design.The tester exposed errors involving noisy sums and averages, enabling the implementation to be modified to use the correct sensitivity.
6 Conclusion and future work
The paper concludes that its user-level differentially private SQL system is useful, robust, and scalable, while identifying accuracy and usability improvements for future work.
- Conclusion: The system answers SQL queries with user-level differential privacy and captures most aggregation-based data analysis tasks.It provides a generic system for typical use cases and supports privacy-utility decisions through accuracy requirements.
- Conclusion: The stochastic checker tests implemented mechanisms, preventing regressions and increasing confidence in the robustness of the privacy guarantee.
- Conclusion: Empirical evidence indicates that the relatively simple algorithms are useful, robust, and scalable.
- Future work: Future work could improve accuracy through Gaussian noise, better composition theorems, query-specific optimization, or amplification by sampling.
- Future work: The authors did not attempt to cache results for query reruns and identify usability and privacy impacts of such caching as future work.
- Future work: Contribution bounds may generalize beyond SQL-based mechanisms because realistic data often contains multiple contributions from one user.
B Proof of Theorem 1
Theorem 1 bounds user sensitivity by combining transformation stability with bounded per-user contributions and bounded per-row aggregation sensitivity.
- Theorem: Theorem 1 concludes that user sensitivity satisfies ∆u h ≤ CuM for model-defined Cu and M.
- Sensitivity bound: For an allowed query h = F ◦ f, stability c bounds the change in F when databases differ by k rows.The transformation satisfies ||F(D1) − F(D2)|| ≤ kc.
- Sensitivity bound: If a user owns at most k rows, adding or deleting that user changes F by at most k · c.
- Stochastic test: The stochastic test takes a random mechanism, privacy parameters, databases, samples, and histogram buckets, then returns a differential-privacy decision.
21 end
The proof establishes user-level sensitivity by bounding each user’s contributing rows and per-row influence, while noting that unbounded factors would make sensitivity unbounded.
- Limitation: Per-user sensitivity is unbounded if k, c, or ∆f is unbounded, so the privacy model bounds their product.
- Sensitivity bound: The proof uses bounded per-row sensitivities for finite aggregation vectors to derive the overall bound M.
- Contribution bound: The operator T bounds each user’s transformed contribution to Cu rows after per-user aggregation.
- Sensitivity bound: Each user contributes at most Cu rows to f, each with bounded contribution M, yielding sensitivity bounded by model-defined constants Cu and M.
C Proof of Theorem 2
Theorem 2 proves user-level (ε, δ)-differential privacy for thresholded noisy group counts by combining composition with a bound on newly released groups.
- Theorem: Each non-empty group releases an ε/Cu-DP noisy user count, while a user may affect at most Cu counts.
- Proof: For databases with the same non-empty groups, composition over at most Cu affected counts establishes the privacy predicate.
- Proof: A single user can create at most Cu additional non-empty groups, so the proof partitions groups into newly affected and shared sets.
- Proof: The partitioned systems satisfy the differential-privacy predicate separately and therefore satisfy it when recombined.
- Conclusion: The proof concludes that the engine provides user-level (ε, δ)-DP.
D Laplace median error
The analysis derives theoretical median error for Laplace noise by comparing its theoretical median noise with the exact result.
- Theoretical median error is obtained by dividing theoretical median noise by the exact result.The method is described for the ANON_COUNT function, which applies Laplacian noise with parameter ∆u /ε.
E Automatic bounding threshold
The automatic bounding algorithm selects a threshold for noisy logarithmic histograms by controlling false positives among zero-count bins.
- The threshold t is derived for APPROX_BOUNDS(col) using privacy parameter ε, histogram-bin count B, and false-positive probability P.The function scans bins from most to least significant until it finds one exceeding t.
- Solving the no-false-positive probability condition yields the desired threshold.
- The threshold must prevent the B −1 zero-count bins preceding the desired least-significant bin from exceeding t.This is the worst case considered for finding the most significant bin above threshold.
F Aggregation sensitivity bounds
The section establishes sensitivity bounds for bounded differentially private aggregates, including count, sum, average, variance, standard deviation, and ntile.
- The listed bounds consider neighboring databases with one or more rows; τ-thresholding handles the empty-versus-one-row case.Some sensitivity bounds are described as very loose.
- ANON_COUNT(col) has sensitivity 1 because adding any row changes the count by 1.
- ANON_SUM(col, L, U) has sensitivity max(|L|, |U|) after inputs are clamped to [L, U].
- ANON_AVG(col, L, U) has sensitivity |U −L| because clamped averages remain within [L, U].
- ANON_VAR(col, L, U) and ANON_STDDEV(col, L, U) are bounded by sensitivity |U −L|2.The standard-deviation bound follows by taking the square root of the variance bound.
- ANON_NTILE(col, L, U) has sensitivity |U −L| because its search space and output lie within [L, U].
G Clamping analysis
The clamping analysis compares expected clamping error with the median noise added by ANON_AVG, finding different growth rates for the two error sources.
- The expected error of the clamped mean is compared with the median noise added by ANON_AVG(S, l, u).
- Clamping error grows quadratically with (b−u), whereas noise error grows linearly with |u −l|.The text states that behavior for other distributions is similar and refers to Figure 9 for distributions centered at 100.