💻 computer science

DP4SQL: Differentially Private SQL with Flexible Privacy Policies

This paper introduces DP4SQL, a differentially private SQL system that enables flexible, customizable privacy policies for relational databases, overcoming the rigid "one-size-fits-all" limitations of existing systems by allowing data curators to specify distinct protection levels for different entities, tables, and data attributes.

Original authors: Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, Danfeng Zhang

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, Danfeng Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the librarian of a massive, complex library. This library doesn't just have one big book; it has thousands of interconnected notebooks, ledgers, and folders. Some notebooks list every student in the university, others list their grades, and others list how much money they got in scholarships.

The Problem: The "One-Size-Fits-All" Mistake

In the past, if someone asked a question about this library (like "How many students got an A in Math?"), the librarians had a very strict, rigid rule for protecting privacy. They treated every single piece of information as if it were a top-secret state document.

The Old Way: To protect privacy, they would add a huge amount of "static" or "noise" (like turning up the volume on a radio until you can't hear the music) to every answer.
- The Flaw: Sometimes, this was too much. If the question was about something that was already public (like "How many students are in the library?"), adding noise made the answer useless.
- The Other Flaw: Sometimes, it wasn't enough. If the question was about something very sensitive (like "Who got a specific scholarship?"), the old rigid rules might not add enough noise, accidentally revealing private details.

The old systems were like a security guard who either locks the entire building down or leaves the front door wide open, with no middle ground. They couldn't handle the nuance that some parts of a person's record are public (like their name) while other parts are secret (like their salary).

The Solution: DP4SQL (The Smart Librarian)

The paper introduces DP4SQL, a new system that acts like a highly trained, flexible librarian. Instead of using one rigid rule for everything, DP4SQL lets the library owner (the data administrator) draw a detailed map of what needs protecting.

Here is how it works, using simple analogies:

1. The "Labeling" System

Imagine you have a stack of files for every person. With DP4SQL, you can put different colored stickers on different parts of the file:

Red Sticker (Secret): "This salary number is top secret. If we change it, we must add a lot of noise to hide the change."
Green Sticker (Public): "This name is public. We don't need to hide it."
Blue Sticker (Count Only): "We can tell you how many people are in this room, but we can't tell you who they are."

The old systems couldn't understand these different stickers. They treated the whole file as either all Red or all Green. DP4SQL understands that a file can be a mix of both.

2. The "Domino Effect" (Connecting the Dots)

The library is tricky because the notebooks are connected. If you change a student's name in the "Student List," it might change the "Grade List" and the "Scholarship List" too.

The Challenge: If a student drops out, does that mean we delete their name, their grades, and their scholarship record? Or do we just change their grade to a dummy value?
The DP4SQL Magic: The system has a special "inference engine" (a smart calculator) that traces these connections. It looks at your stickers and says: "Okay, if we change this student's salary (Red sticker), we have to add noise to the Scholarship table. But since the Course List is Green (public), we don't need to add noise there."

It calculates the exact amount of noise needed—no more, no less.

3. The "Counterfactual" Game

To figure out how much noise to add, the system plays a mental game called "What If?"

The Game: It imagines two versions of the library. In Version A, Student Alice is there. In Version B, Student Alice is gone (or her salary is different).
The Goal: The system asks, "If I give you the answer to a question based on Version A, can you guess that it's not Version B?"
The Result: If the answer changes too much between the two versions, the system adds more "static" (noise) to the final answer so that you can't tell the difference. If the answer stays mostly the same, it adds very little noise, keeping the data useful.

Why This Matters (The Results)

The authors tested this system on two scenarios: a fake university database and a standard business benchmark (TPC-H).

The "Under-Protecting" Fix: In one test, an old system thought a public count of orders was a secret. It added way too much noise, making the answer useless. DP4SQL realized the count was public and gave a clean, accurate answer.
The "Over-Protecting" Fix: In another test, an old system treated a public list of course names as a secret. It added so much noise that the answer was garbage. DP4SQL saw the course names were public and gave a precise answer.

In Summary

Think of DP4SQL as a tailor instead of a machine.

Old Systems (The Machine): Cut every suit from the same pattern. Some people get a suit that's too tight (too much noise, useless data), and some get one that's too loose (too little noise, leaked secrets).
DP4SQL (The Tailor): Takes your measurements (your specific privacy rules for names, salaries, grades, etc.) and sews a custom suit. It adds just enough noise to keep the secrets safe, but leaves the rest of the data clear and useful.

The paper proves that this flexible approach is mathematically safe (it really does protect privacy) and much more useful than the rigid systems we have today.

Technical Summary: DP4SQL - Differentially Private SQL with Flexible Privacy Policies

Problem Statement

Differential privacy (DP) is well-established for single-table datasets, but its application to relational databases remains challenging due to the complexity of defining "plausible deniability" across multiple relations. Existing differentially private SQL systems suffer from rigid, hard-coded privacy models that cannot accommodate the nuanced requirements of real-world applications.

The core limitations of current systems include:

Inflexible Policies: They cannot handle scenarios where different tables or even different columns within the same table require varying levels of protection (e.g., protecting record existence in one table while only protecting attribute values in another).
Public Knowledge Integration: They struggle to incorporate public information (e.g., known table sizes, public column values like faculty names) into the privacy calculus. Ignoring public knowledge often leads to over-protecting data (injecting excessive noise) or under-protecting it (failing to mask the existence of records when the table size is known).
Complex Entity Interactions: Existing models often fail to correctly handle foreign keys and transitive ownership, particularly when entities interact (e.g., a faculty member assigning grades to a student). This leads to incorrect sensitivity calculations, resulting in either insufficient noise (privacy breaches) or excessive noise (loss of utility).

Methodology

The paper proposes DP4SQL, a system that decouples high-level privacy policy specification from low-level automated reasoning. The methodology consists of three main components:

1. High-Level Privacy Labeling Framework

Data administrators specify policies using a simple, high-level labeling system for each relation in the schema. For a distinguished entity relation $R^\star$ (e.g., Students or Faculty), each relation $R_i$ is assigned one of three labels:

DEL (Delete): The existence of records is private. Counterfactual worlds are created by deleting records. This corresponds to unbounded neighbors.
REPA (Replace): The existence of records is public, but specific attributes $A$ are private. Counterfactual worlds are created by replacing values in $A$ . This corresponds to bounded neighbors.
PUB (Public): The entire relation is public.

This framework allows for mixed policies, such as protecting student existence (DEL) while keeping faculty names public (PUB) but faculty salaries private (REPA).

2. Low-Level Plausible Deniability Actions

To automate reasoning, the system translates high-level labels into a set of plausible deniability actions that describe the maximum changes a query result can undergo between neighboring databases. The actions are:

Add $_a$ / Del $_d$ : Adding or deleting $a$ or $d$ rows.
Rep $^A_k$ : Replacing values of attributes $A$ in $k$ rows.

The system employs an inference system with production rules to derive these actions for complex SQL queries involving:

Base Relations: Rules map privacy labels to initial actions, considering maximum ownership ( $\hat{\otimes}$ ) derived from foreign key constraints.
Unary Transformations: Rules for Selection ( $\sigma$ ), Projection ( $\pi$ ), and Grouping ( $\gamma$ ) propagate actions based on whether predicates or grouping keys intersect with protected attributes.
Joins: The system distinguishes between Key Joins (on primary-foreign key pairs) and General Joins. Key joins leverage integrity constraints to derive tighter bounds on record changes, avoiding the over-approximation common in general join rules.

3. Sensitivity Calculation and Noise Injection

The inferred actions are mapped to an upper bound on global sensitivity ( $\hat{\Delta}$ ). This bound determines the scale of noise added via the Laplace mechanism. The system calculates sensitivity for aggregate functions (COUNT, SUM) by analyzing how the inferred actions (additions, deletions, replacements) affect the output vector.

Key Contributions

Flexible Policy Specification: A high-level column labeling framework that supports mixed privacy requirements (public sizes, public columns, private attributes) across relational schemas with foreign keys.
Automated Reasoning Engine: A formal inference system that translates high-level labels into low-level plausible deniability actions, soundly reasoning about the stability of relational algebra queries (joins, aggregations, subqueries).
Tighter Sensitivity Bounds: By explicitly modeling public knowledge (e.g., known table sizes) and using key-join specific rules, DP4SQL derives tighter sensitivity bounds than existing systems, which often assume worst-case scenarios for all attributes.
Implementation and Validation: The system is implemented as database middleware (DP4SQL) that intercepts SQL queries, computes the required noise, and returns differentially private answers.

Results

The paper evaluates DP4SQL using a university schema case study and the TPC-H benchmark, comparing it against baseline policies (pure unbounded and pure bounded neighbors) and the Tumult Analytics system (based on PrivateSQL).

Privacy Correctness (Under-protection): In scenarios where table sizes are public (e.g., the number of orders in TPC-H), baseline unbounded models (like Tumult) incorrectly assume record existence is private. This leads to under-protection (insufficient noise) because they fail to account for the fact that replacing a record (rather than deleting it) is the valid counterfactual when size is known. DP4SQL correctly identifies these cases and applies appropriate noise.
Utility Improvement (Over-protection): Baseline models often treat all attributes as private, leading to over-protection (excessive noise). For example, in the university case study, queries about public review scores or faculty names resulted in zero sensitivity under DP4SQL's flexible policy, whereas baselines injected significant noise. In TPC-H, DP4SQL achieved zero sensitivity for queries returning public information (e.g., supplier counts), while baselines added noise that rendered results unusable (relative error > 100%).
Accuracy: In cases where baselines over-protected, DP4SQL demonstrated significantly lower relative error (e.g., 19.6% vs. much higher errors in baselines for specific TPC-H queries).

Significance and Claims

The paper claims that DP4SQL addresses the "one-size-fits-all" limitation of current DP SQL systems. By allowing data curators to customize plausible deniability requirements, the system avoids the trade-off between privacy breaches (due to under-protection) and data utility loss (due to over-protection).

The authors emphasize that their approach is sound: they provide formal proofs that the inference system correctly derives an upper bound on global sensitivity, ensuring that the resulting mechanism satisfies $(PS, R^\star, \epsilon)$ -differential privacy. The work highlights that correct privacy modeling—specifically the ability to reason about public table sizes, public columns, and fine-grained attribute protection—is essential for deploying differential privacy in complex, multi-table relational environments.