SQL is the de facto interface for exploratory data analysis; however, releasing exact query results can expose sensitive information through membership or attribute inference attacks. Differential privacy (DP) provides rigorous privacy guarantees, but in practice, DP alone may not satisfy governance requirements such as the minimum frequency rule, which requires each released group (cell) to include contributions from at least k distinct individuals. In this paper, we present DPSQL+, a privacy-preserving SQL library that simultaneously enforces user-level (ε,δ)-DP and the minimum frequency rule. DPSQL+ adopts a modular architecture consisting of: (i) a Validator that statically restricts queries to a DP-safe subset of SQL; (ii) an Accountant that consistently tracks cumulative privacy loss across multiple queries; and (iii) a Backend that interfaces with various database engines, ensuring portability and extensibility. Experiments on the TPC-H benchmark demonstrate that DPSQL+ achieves practical accuracy across a wide range of analytical workloads -- from basic aggregates to quadratic statistics and join operations -- and allows substantially more queries under a fixed global privacy budget than prior libraries in our evaluation.
Table 1: Comparison of differentially private SQL systems. “Accountant” indicates whether privacy budget management across multiple queries is integrated as a system component.
Figure 1: The architecture of DPSQL+.
Figure 2: Mean Relative Error (%) against the ground truth as a function of the privacy parameter (ε,10−7) . The y-axis is shown on a logarithmic scale. Qrlew does not support COUNT_DISTINCT , and SmartNoise SQL does not support COVAR , JOIN and GROUPBY_JOIN . For ε=0.1 , GROUPBY_JOIN is excluded because τ -thresholding removes keys.
Figure 3: Maximum number of queries executable with fixed per-query budget (ε,δ)=(0.1,10−7) under two global budgets.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Type
Query
Description
Scalar
COUNT
The total number of tuples in the customer table.
COUNT_DISTINCT
The number of distinct nation keys in the customer table.
SUM
The sum of account balances in the customer table.
AVG
The mean account balance in the customer table.
VAR
The variance of account balances in the customer table.
STDDEV
The standard deviation of account balances in the customer table.
Appendix
Table 2: Specification of the query set used for the experiments.
Extracting insights from textual data while protecting user privacy is increasingly important. Existing methods produce private insights in diverse forms for different analytical purposes, making their utility difficult to assess and compare. In this work, we formulate differentially private (DP) insights as reusable representations for answering analytical queries, providing a common basis for utility assessment. Answering these queries, however, requires fine-grained details and cross-attribute statistics that existing representations may omit. To capture this information, we introduce Structured and Hierarchical Insight with Privacy (SHIP), which automatically maps queries to attributes, builds a hierarchical hybrid taxonomy, and releases a DP synthetic table for further analysis. We also develop an evaluation protocol based primarily on QA performance and structured fidelity. Our experiments demonstrate SHIP's strong performance on both measures relative to existing private insight baselines, while identifying queries that remain challenging for structured representations.
Text-to-SQL systems are increasingly deployed on production databases, where queries that pass benchmark evaluation can still produce results that distort downstream workflows. Standard set-based execution accuracy (Set-EX) collapses duplicate rows and can therefore miss multiplicity errors, including missing DISTINCT, inflated aggregates, and Cartesian-style join explosions. We call this the Multiplicity Blind Spot (MBS) and introduce Multiset-EX, a multiplicity-preserving evaluation criterion that exposes such failures. Across released DeepEye-SQL artifacts from three backbones (Qwen2.5-Coder-32B, Qwen3-Coder-30B-A3B, and Gemma-3-27B) on executable BIRD-Dev N=1532, we find a consistent 5.81--6.79 pp gap between Set-EX and Multiset-EX. The gap is not specific to DeepEye-SQL: it persists on released DAIL-SQL+GPT-4 (5.22 pp) and BIRD GPT-3.5-turbo (3.39 pp) predictions. We further introduce ModularSQL, a lightweight post-selection runtime guardrail that probes executed results for multiplicity anomalies and applies deterministic patches or low-cost LLM rescue only to flagged queries. Integrated with DeepEye-SQL using Qwen3-Coder, ModularSQL preserves Set-EX at 72.06% while improving Multiset-EX from 65.86% to 67.75% (+1.89 pp). It flags 77 high-risk anomalies, while adding only $0.0076 in total LLM cost and 120 ms amortized latency per query. Cross-pipeline evaluation shows that the candidate-free detector and deterministic patches also transfer to independently released prediction sets. Overall, these results show that benchmark accuracy does not necessarily imply execution-safe SQL, and that lightweight, multiplicity-aware runtime guardrails can narrow this gap with modest computational overhead.
Tianxin Zhou, Ruixi Lin
University of Southern California · Northeastern University
Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rather than on the entire graph -- and by growing privacy concerns, we initiate the study of differentially private range subgraph counting (DPRSC). The goal is to privately count occurrences of a fixed pattern graph within induced subgraphs defined by multi-dimensional attribute ranges. Unlike classical point counting, subgraph counting is inherently nonlinear and exhibits high sensitivity: a single edge modification can affect many subgraph occurrences. We present the first efficient algorithms for DPRSC with small additive error. Our approach introduces a subgraph projection that reduces DPRSC to weighted orthogonal range counting, enabling the use of range trees and local sensitivity estimation to achieve accurate private query answering. We complement our algorithms with matching lower bounds, obtained by reducing reconstruction attacks to DPRSC and leveraging discrepancy theory. In particular, we show that any differentially private algorithm for DPRSC must incur additive error exponential in the dimension. Empirical evaluations demonstrate that our algorithms significantly outperform baseline methods in accuracy and runtime while maintaining strong privacy guarantees.
Xian Chen, Ruobing Bai, Pan Peng
School of Computer Science and Technology, University of Science and Technology of China, Hefei, China.