# Differentially Private SQL with Bounded User Contribution

arXiv: https://arxiv.org/abs/1909.01917 · HTML: https://mlsanity.com/paper/1909.01917/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2019.

## Built on by (most cited first, 27 of 27)

- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning](https://mlsanity.com/paper/2406.14322/) (2024)
- [OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization](https://mlsanity.com/paper/2210.01318/) (2022)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacy](https://mlsanity.com/paper/2308.12210/) (2023)
- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [Private Quantiles Estimation in the Presence of Atoms](https://mlsanity.com/paper/2202.08969/) (2022)
- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)
- [DP-XGBoost: Private Machine Learning at Scale](https://mlsanity.com/paper/2110.12770/) (2021)
- [Multi-Task Differential Privacy Under Distribution Skew](https://mlsanity.com/paper/2302.07975/) (2023)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)
- [A Case for Computing on Unstructured Data](https://mlsanity.com/paper/2509.14601/) (2025)
- [DPack: Efficiency-Oriented Privacy Budget Scheduling](https://mlsanity.com/paper/2212.13228/) (2022)
- [Qrlew: Rewriting SQL into Differentially Private SQL](https://mlsanity.com/paper/2401.06273/) (2024)
- [Membership Inference Attacks and Privacy in Topic Modeling](https://mlsanity.com/paper/2403.04451/) (2024)
- [Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond](https://mlsanity.com/paper/2509.04919/) (2025)
- [Differentially Private Distributed Estimation and Learning](https://mlsanity.com/paper/2306.15865/) (2023)
- [DPSQL+: A Differentially Private SQL Library with a Minimum Frequency Rule](https://mlsanity.com/paper/2602.22699/) (2026)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)
- [Certified in Theory, Broken in Practice: Assumption Gaps in Cryptographic Model Certification](https://mlsanity.com/paper/2607.21839/) (2026)
- [Trustworthy Data- and ML-Ops for Intelligent Transportation Systems and Logistics](https://mlsanity.com/paper/2610.01282/) (2026)

## Abstract (arXiv)

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.