PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Practical Differential Privacy for SQL Queries

Noah Johnson, Joseph P. Near, Dawn Song

arXiv:1706.09479v5cs.CRcs.DB

TL;DR

Existing differential privacy mechanisms do not support the diverse queries and databases used for general-purpose SQL analytics, despite the need to protect individuals while enabling analysis. The paper derives practical requirements from 8.1 million real-world queries, proposes elastic sensitivity, and builds FLEX around it. FLEX supports real-world SQL queries across existing databases, with 0.03% performance overhead and high utility on a majority of queries with large population sizes.

  • Problem

    Existing differential privacy mechanisms do not support the wide variety of queries and databases required for general-purpose SQL analytics while protecting individuals.

  • Method

    The paper derives practical requirements from 8.1 million real-world queries, proposes elastic sensitivity as an approximation of local sensitivity supporting equijoins, and builds FLEX to enforce differential privacy.

  • Results

    FLEX supports real-world SQL queries across existing databases, incurs 0.03% performance overhead, and provides high utility on a majority of queries with large population sizes.

  • Takeaways & Limitations

    A differential privacy system meeting real-world query requirements could support a majority of real-world statistical queries.

  • Takeaways & Limitations

    The paper focuses on counting queries and discusses extensions needed to support other aggregation functions.

Abstract

from arXiv · show

Differential privacy promises to enable general data analytics while protecting individual privacy, but existing differential privacy mechanisms do not support the wide variety of features and databases used in real-world SQL-based analytics systems. This paper presents the first practical approach for differential privacy of SQL queries. Using 8.1 million real-world queries, we conduct an empirical study to determine the requirements for practical differential privacy, and discuss limitations of previous approaches in light of these requirements. To meet these requirements we propose elastic sensitivity, a novel method for approximating the local sensitivity of queries with general equijoins. We prove that elastic sensitivity is an upper bound on local sensitivity and can therefore be used to enforce differential privacy using any local sensitivity-based mechanism. We build FLEX, a practical end-to-end system to enforce differential privacy for SQL queries using elastic sensitivity. We demonstrate that FLEX is compatible with any existing database, can enforce differential privacy for real-world SQL queries, and incurs negligible (0.03%) performance overhead.

1. INTRODUCTION

Organizations need to protect sensitive individual data while analysts depend on general-purpose SQL access, but existing privacy approaches do not provide both. The paper proposes elastic sensitivity and FLEX as a practical path toward differential privacy for real-world SQL analytics.

  • Motivation: Unrestricted organizational data access can cause privacy breaches, while access controls cannot govern how authorized analysts use data.Data anonymization also cannot be relied upon because re-identification attacks have demonstrated its weaknesses.
  • Motivation: Differential privacy supports general statistical analysis while providing a formal guarantee protecting information about individuals.
  • Research gap: General-purpose differential privacy for real-world SQL remains an open challenge because existing research focuses largely on special-purpose use cases.
  • Research gap: Existing SQL-like differential privacy mechanisms support only subsets of queries and require database-engine modifications, complicating practical adoption.
  • Approach: The paper proposes elastic sensitivity, designed to support standard SQL, integrate with real database environments, and advance practical differential privacy.
  • Approach: 8.1 million real-world queries provide the empirical basis for requirements intended to make differential privacy practical for SQL analytics.

2. REQUIREMENTS FOR PRACTICAL DIFFERENTIAL PRIVACY

The study derives practical differential privacy requirements from 8.1 million real-world SQL queries. It emphasizes compatibility with existing databases, broad support for joins, and focus on statistical counting queries.

  • Study scope: 8.1 million SQL queries executed across more than 6 database backends motivate requirements for practical differential privacy.The dataset covers sensitive rider, driver, trip-log, and customer-support data.
  • Query characteristics: All queries use Select, more than half use Join, and fewer than 1% use operators such as Union, Minus, and Intersect.
  • Join requirements: 76% of joins are equijoins, 64% use one-to-many relationships, 28% of queries include self joins, and 69% are inner joins.
  • Requirements: A practical mechanism must work with heterogeneous existing databases without requiring a specific distribution or custom execution engine.The study concludes that satisfying these requirements could support a majority of real-world statistical queries.
  • Join requirements: 62.1% of queries use SQL Join, with multiple joins, self joins, and one-to-one, one-to-many, and many-to-many relationships represented.These findings require support for equijoins, arbitrary nested joins, and the full spectrum of join relationships.
  • Statistical queries: 34% of queries return aggregate statistics, and Count is the most common aggregation at 51%.The paper therefore focuses on statistical counting queries and discusses extensions to other aggregation functions.

3. Elastic Sensitivity

Elastic sensitivity addresses the difficulty of applying local sensitivity to SQL queries with general equijoins. It approximates local sensitivity tractably while preserving a provable privacy-use condition.

  • Motivation: Global sensitivity can be unbounded for queries with general joins because one input record may influence arbitrarily many output records.
  • Motivation: Directly computing local sensitivity is infeasible because it requires running each query on every possible neighboring database.In the described environment, this would require more than 1 billion queries per original query.
  • Approach: Elastic sensitivity models each join using precomputed join-key frequency metrics to conservatively approximate local sensitivity without additional database interactions.
  • Guarantee: Elastic sensitivity is an upper bound on local sensitivity and can therefore be used with any local sensitivity-based differential privacy mechanism.

3.2 Background

This section introduces differential privacy and the sensitivity concepts used to analyze query changes while protecting database privacy. It also defines the paper’s multi-table privacy setting and its tuple-level scope.

  • Differential privacy: Differential privacy provides formal indistinguishability while enabling statistical analysis of data about individuals.A differentially private result reveals limited information about which neighboring database generated it.
  • Sensitivity: Global sensitivity measures the maximum query-result difference across neighboring databases.It considers all neighboring database pairs rather than one true database.
  • Sensitivity: Local sensitivity measures the maximum difference between a query’s result on the true database and any neighbor.Because it depends on one true database, local sensitivity is often lower than global sensitivity.
  • Stability: The paper extends stability to local sensitivity by fixing the reference database to the true database.Locally c-stable transformations bound output changes for neighbors of that database.
  • Multi-table privacy: For multi-table databases, tables are mapped to disjoint subsets of one database, protecting the presence or absence of a single tuple.If one user contributes multiple protected tuples, tuple-level protection may be insufficient.
  • Smoothing: Smoothing techniques are required before local sensitivity can be used safely to enforce differential privacy.The section introduces local sensitivity at distance k as part of this framework.

3.3 Definition of Elastic Sensitivity

Elastic sensitivity recursively bounds query sensitivity across relational-algebra operations, including arbitrary equijoins and self joins. It uses maximum join-key frequencies and ancestor relations to handle distance from the true database.

  • Definition: Elastic sensitivity is defined recursively at arbitrary distance k from the true database, with local sensitivity corresponding to k = 0.This distance-based definition supports later smoothing functions.
  • Supported queries: The supported relational algebra includes selection, projection, joins, counting, and grouped counting, including arbitrary equijoins and self joins.The formal definition is expressed over this core relational-algebra subset.
  • Supported queries: The approach naturally extends aggregations nested within queries when arithmetic or other modifications of aggregation results are absent.The presentation assumes counting is the outermost operation, but the inner relation can serve as the query root.
  • Elastic sensitivity: Elastic sensitivity ˆS(k)(q, x) is defined using elastic stability ˆS_R(k)(r, x) for relational transformations.Elastic stability bounds local stability at distance k.
  • Maximum frequency: Maximum frequency bounds join sensitivity by tracking the most frequent attribute value and its possible increase at distance k.The metric mfk(a, r, x) is defined from the database’s maximum frequency mf(a, r, x).
  • Scope: Additional predicates in conjunctions may reduce true join stability, so the definition remains an upper bound; unsupported query cases are discussed separately.The example uses only the equijoin term a.id = b.id.

3.4 Example: Counting Triangles

The triangle-counting example applies elastic sensitivity recursively to a SQL query with multiple self joins. It computes relation stability from maximum-frequency bounds, then smooths the result before adding Laplace noise.

  • Query: The example counts directed-graph triangles using a SQL query with two joins over aliases of the edges table.The query contains multiple self joins, illustrating complex recursive cases.
  • Setup: The ca-HepTh dataset has maximum frequency metric 65, and the example uses privacy budget ϵ = 0.7.These values parameterize the sensitivity calculation.
  • First join: 131 + 2k is the elastic stability calculated for the first self-join relation.The expression substitutes the maximum-frequency value 65 into the recursive definition.
  • Second join: (65 + k)(131 + 2k) + (65 + k) + (131 + 2k) is the elastic stability for the second join.The calculation combines the maximum-frequency and preceding-relation stability terms.
  • Query sensitivity: For a counting query, the elastic sensitivity equals the elastic stability of the relation being counted.Thus the second-join expression defines the full query’s elastic sensitivity.
  • Privacy mechanism: Smoothing computes the maximum elastic sensitivity weighted by an exponentially decaying function in k before applying the Laplace mechanism.The smoothed value is used to scale the added noise.
  • Privacy mechanism: S = 8896.95 occurs at distance k = 19, and Laplace noise is scaled to 2S.The example sets δ = 10^-8 in the smoothing parameter.

3.5 Elastic Sensitivity is an Upper Bound on Local Sensitivity

The paper proves that elastic sensitivity upper-bounds local sensitivity for the supported query class. The proof handles relational-algebra operators, non-self joins, self joins, and histogram queries through recursive stability bounds.

  • Proof strategy: The proof proceeds by induction on relational-expression structure, with table, projection, selection, join, and count cases.Projection preserves row counts, selection can only filter rows, and ungrouped count produces one row.
  • Non-self joins: For non-self joins, disjoint ancestor sets ensure that changing one underlying row affects at most one input relation.The bound chooses the larger changed-row contribution from the two symmetric cases.
  • Self joins: Self joins require three changed-row classes because one database-row change can affect both joined inputs.The classes cover original-to-changed matches in either direction and changed-to-changed matches.
  • Self joins: Maximum-frequency bounds control each self-join class, while the total changed-row bound sums the three class bounds.The most popular join key determines the worst-case number of matches.
  • Main theorem: The main theorem states that elastic sensitivity ˆS(k)(q, x) upper-bounds local sensitivity A(k)_q(x) at distance k.This establishes the soundness of using elastic sensitivity with local sensitivity-based privacy mechanisms.
  • Histograms: For histogram queries, each changed underlying row can change two histogram rows, yielding a local-stability bound of 2 ˆS(k)_R.Non-histogram counting queries instead inherit the relation-stability bound directly.

3.6 Optimization for Public Tables

Elastic sensitivity can be tightened when joined tables are publicly known, while preserving protection against disclosure from repeated public join keys.

  • 3.6 Optimization for Public Tables: Public tables need not be protected, enabling tighter elastic-sensitivity bounds for joins on non-sensitive tables.The set of public tables is domain-specific and varies across data environments.
  • 3.6 Optimization for Public Tables: For T1 JOIN T2 ON T1.A = T2.B with public T2, join elastic stability equals T1’s elastic stability times the maximum frequency of T2.B.This formulation prevents repeated join keys in a public table from revealing information about a private table.

3.7 Discussion of Limitations and Extensions

Elastic sensitivity supports counting queries broadly but has scope limitations for join types, derived join keys, and non-count aggregations, with utility depending on the aggregation.

  • Unsupported joins: Elastic sensitivity does not support non-equijoins because bounding matches such as A.x > B.y requires knowledge of all values in both join-key columns.More than three-quarters of joins are equijoins; supporting other join types would require database interactions for each query.
  • Unsupported queries: Queries whose join keys come from subquery-computed counts must be rejected because max-frequency metrics cover only attributes from original tables.This criterion holds for 98.5% of joins in the dataset, limiting the practical consequence of the restriction.
  • Extensions: Value range vr(a, r) is defined as the maximum minus the minimum value allowed for column a in relation r.It can come from column constraints, current database values, or domain-expert knowledge, and must be enforced for privacy guarantees.
  • Sum and Average: For Sum, elastic sensitivity equals local sensitivity when relation stability is 1, but utility degrades as join-induced stability increases.The degradation reflects a worst-case assumption that each duplicated row has the maximum permitted attribute value.
  • Sum and Average: For Average, elastic sensitivity matches local sensitivity only for single-row averages, and utility degradation grows with relation stability and the number of averaged records.A lower bound on the number of averaged records could scale sensitivity down, but would require inspecting filters and additional database metrics.
  • Max and min: For Max and Min, relation stability does not affect local sensitivity, but outliers make these functions inherently sensitive and generally yield poor utility under differential privacy.The data-model value range directly provides global sensitivity, which upper-bounds local sensitivity.

4. FLEX: PRACTICAL DIFFERENTIAL PRIVACY FOR SQL QUERIES

FLEX combines query analysis, elastic sensitivity, smooth sensitivity, and Laplace noise to enforce differential privacy on existing databases without database interaction. Its optimization limits sensitivity search to a query-dependent range, while the mechanism is formally shown to provide (ϵ, δ)-differential privacy.

  • System architecture: FLEX analyzes a SQL query, applies smooth sensitivity to elastic sensitivity, and adds Laplace noise to the original results.The system requires static query analysis and result post-processing, rather than database modifications or enforcement-time interactions.
  • System architecture: FLEX requires no database interaction to enforce privacy and can operate on any existing database.Precomputed max-frequency metrics can be reused across queries but must be recomputed when the most frequent join attribute changes.
  • Histogram bin enumeration: Histogram bin enumeration requires finite, enumerable, non-protected bin-label domains; otherwise analysts must specify the labels.When labels are available, FLEX can construct the histogram and return the original labels with differentially private counts.
  • FLEX mechanism: The FLEX mechanism releases q_ℓ(x) + Lap(2S/ϵ), where S is the maximum smoothed elastic sensitivity over database distances.The smoothing parameter is β = ϵ / (2 ln(2/δ)).
  • Privacy guarantee: Theorem 2 establishes that the FLEX mechanism provides (ϵ, δ)-differential privacy.The proof uses elastic sensitivity as an upper bound on local sensitivity within the smooth-sensitivity mechanism.
  • Efficiently calculating S: Because elastic sensitivity grows polynomially while smoothing decays exponentially, FLEX need only search distances up to a query-dependent bound rather than the full database size.The maximum occurs from k = 0 to k = j(r)^2/β, typically much smaller than n.

5. EXPERIMENTAL EVALUATION

FLEX is evaluated on diverse real-world and benchmark SQL queries, measuring support, performance overhead, utility, privacy-budget effects, optimization benefits, and comparison with wPINQ. It supports joins and delivers high utility for many sufficiently large-population queries, while errors remain concentrated in unsupported features, low-population analyses, and some many-to-many joins.

  • 5.1 Success Rate and Performance of FLEX: 76% of queries successfully received elastic-sensitivity calculations, while unsupported queries caused 14.14% of errors and parsing caused 6.58%.The remaining errors accounted for 3.21% of queries.
  • 5.1 Success Rate and Performance of FLEX: 0.03% average performance overhead resulted from 7.03 milliseconds of analysis and 4.86 milliseconds of perturbation against 42.4 seconds of database execution.
  • 5.2 Utility of FLEX on Real-World Queries: Less than 10% median error occurred for a majority of queries with and without joins, with joined-query error falling below 10% above 5 million population size.Median error generally decreased as population size increased, while many-to-many private-table joins formed a higher-error cluster.
  • 5.3 Effect of Privacy Budget: 49.8% of less sensitive queries achieved less than 1% median error at ϵ = 0.1, and larger ϵ values produced lower median error.The TPC-H experiment reproduced the trend of decreasing error with increasing population size.
  • 5.3 Effect of Privacy Budget: 72% of high-error queries involved low-population statistics, while 8% targeted individual-specific data and 20% involved many-to-many joins with large maximum-frequency metrics.These categories identify privacy-sensitive query patterns and cases where elastic sensitivity can yield loose bounds.
  • 5.4 Impact of Public Table Optimization: 23.4% of queries used the public-table optimization, which increased the less-than-1% error group from 28.5% to 49.8%.The improvement primarily moved queries from the greater-than-100% error bin into the 1% error bin.
  • 5.5 Comparison with wPINQ: FLEX produced lower median error than wPINQ for programs 1, 2, 3, and 6, but higher error for programs 4 and 5.The reduction exceeded 90% for programs 2 and 3 and was nearly 50% for programs 1 and 6.

6. RELATED WORK

Related work provides differential privacy for restricted query classes, programming models, or specialized tasks, but leaves gaps for general-purpose SQL with joins. FLEX’s elastic sensitivity complements local-sensitivity frameworks while retaining broader SQL and database compatibility.

  • Existing general mechanisms support only subsets of SQL-like queries and often require database-engine modifications.
  • Fuzz excludes one-to-many and many-to-many joins, while specialized graph mechanisms are not applicable to general-purpose analytics.
  • Elastic sensitivity supplies the local-sensitivity bound required by propose-test-release, enabling that framework to apply to SQL queries with joins.
  • Sample & aggregate cannot support joins or counting queries because database splitting breaks join semantics and the method targets statistical estimators.
  • Extending FLEX to categorical outputs would require an analyst-provided scoring function and a sensitivity bound for the exponential mechanism.
  • Database constraints such as primary-key uniqueness can leak private data, but calculating constraint-aware sensitivity is computationally hard.

7. CONCLUSION

The paper concludes that elastic sensitivity is a first step toward practical differential privacy for general-purpose SQL queries. FLEX supports real-world queries and provides high utility for a majority of queries with large population sizes.

  • Elastic sensitivity is an efficiently computed approximation of local sensitivity that supports joins.
  • FLEX uses elastic sensitivity to enforce differential privacy for SQL queries and is evaluated on a wide variety of queries.
  • High utility occurs for a majority of evaluated queries with large population sizes.
Loading 1706.09479v5…