arXiv CSopen access

DP4SQL: Differentially Private SQL with Flexible Privacy Policies

DP4SQL: Differentially Private SQL with Flexible Privacy Policies Andrew Cascio

KinChin Tong

Daniel Kifer

Duke University [email protected]

Binghamton University [email protected]

Penn State University [email protected]

Zeyu Ding

Danfeng Zhang

Binghamton University [email protected]

Duke University [email protected] creating DP platforms [21, 24, 26], especially differentially private SQL systems that ingest a non-expert’s SQL queries and produce accurate, privacy-preserving answers [2, 4, 13–15, 18, 22, 23, 29, 30]. However, using such systems does not necessarily mean that DP is used properly. Applying differential privacy correctly requires specifying (1) an appropriate application-dependent plausible deniability model that specifies what pieces of information need to be indistinguishable from each other and (2) the strength of the indistinguishability. The plausible deniability model is an open question for DP SQL systems, and is the topic of this paper. Meanwhile, the strength of the indistinguishability guarantee is a well-understood mathematical concept that links privacy parameters, like the famous 𝜖, to limitations on an attacker’s ability [3, 7, 9, 20, 28] to use the output of a mechanism to make guesses about the information that should be plausibly deniable. Each existing DP SQL system [2, 4, 13–15, 18, 22, 23, 29, 30] provides their own hard-coded, often competing, plausible deniability models. A mismatch between the model and the application requirements could leave the data under-protected or over-protected, with incorrect amount of noise added to query answers. However, in existing systems, data administrators cannot customize the plausible deniability model. There are several reasons for this limitation. (1) The plausible deniability model is tightly integrated into the privacy calculus used by those systems to guarantee DP. Even small changes to the model would require rewriting and manually proving the correctness of the privacy accounting rules. (2) Real-world requirements are so complex that requiring a data administrator to specify a plausible deniability model is a daunting task (even for data administrators with deep expertise in privacy technology). (3) The way plausible deniability is specified in differential privacy—the “neighbor relation”—is extremely low-level and cumbersome. A neighbor relation N is a set of pairs of databases. If a database pair (𝐷, 𝐷 ′ ) ∈ N , it means that an attacker should have difficulty in determining whether the public data products were created from 𝐷 or 𝐷 ′ . The difference in contents between 𝐷 and 𝐷 ′ is a piece of information that gets plausible deniability guarantees. For example, if the database schema contains only one table and every person can contribute only one record, then the appropriate relation N 1 is unbounded neighbors: (𝐷, 𝐷 ′ ) ∈ N 1 if and only if 𝐷 ′ can be obtained from 𝐷 by the removal or addition of an arbitrary record. Hence the existence of a record gets plausible deniability. However, if the size of this table is publicly known, then the appropriate relation N 2 is bounded neighbors: (𝐷, 𝐷 ′ ) ∈ N 2 if and only if 𝐷 ′ can be obtained from 𝐷 by replacing one record. Under DP, the same query gets different noise when using the neighbor relations N 1 vs. N 2 .

arXiv:2606.07883v1 [cs.CR] 5 Jun 2026

Abstract The plausible deniability model of differential privacy for singletable datasets is well-understood. However, applying differential privacy to relational databases is much trickier: each application needs flexibility in specifying the pieces of information about an entity, spread across multiple relations, that require plausible deniability guarantees. Existing differentially private SQL systems only support rigid privacy policies. Even seemingly small changes, such as specifying that some tables need to protect the existence of records while others only need to protect the record contents, require significant manual effort in updating their privacy accountants and proving their correctness. One example of a challenge is the presence of partially public data. Public columns in a table (e.g., faculty names in a university dataset and partial course enrollment information) can cause some queries to require more noise (compared to fully private data), while others require less noise. This kind of reasoning is not supported in existing systems. Another example is when different parts of records (e.g., demographics, financial data) require different levels of privacy protection. Again, existing differentially private SQL systems need to rewrite their rules for calculating query stability in order to support such a feature. This paper presents DP4SQL, a differentially private SQL system that allows data curators to better customize the plausible deniability requirements for their relational databases. This avoids the drawbacks of the “one-sizefits-all” systems that would either underprotect the data or inject too much noise into query answers.

CCS Concepts • Security and privacy → Database and storage security.

Keywords differential privacy, inference systems, SQL

1

Introduction

Differential privacy (DP) [9, 10] is a gold standard for creating mechanisms (algorithms) that generate publicly-releasable data products from confidential datasets, while protecting the private information in those datasets. It has an ever-increasing list of real-world deployments, including the U.S. Census Bureau [1, 17], Uber [13, 14], Apple [25], Facebook [19], Microsoft [6], and Google [11, 12, 29]. Using differential privacy is surprisingly complex. It requires specialized knowledge to design mechanisms that produce useful data products while satisfying the mathematical requirements of DP that guarantee privacy protection. As a result, there is strong interest in 1

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

Incidentally, it is worth noting that no existing DP SQL system can support situations where some tables in a database have publicly known sizes while others do not. Even such a seemingly small detail would require re-defining systems semantics, re-writing their privacy accountants and re-proving their correctness. Common situations in practice introduce even more complexity. Consider our running example of a simplified university database schema (Figure 1) consisting of 5 relations. Student(uid, name, major) lists students enrolled in the university (table 𝑇 1 ), and Faculty(fid, name, salary, age) lists faculty members (table 𝑇 2 ). These are the 2 types of entities that would need privacy protection. Scholarship(aid, uid, amount) provides scholarship information (table 𝑇 3 ), Section(sid, fid, title) lists the course sections (table 𝑇 4 ), and Enrollment(eid, sid, uid, grade, review) has the enrollment, grade, and student review information for each section (table 𝑇 5 ). Complicating matters is the mixed sensitivity of information, even in the same table. For example, faculty name is public, faculty demographics are somewhat sensitive, and financial information is extremely sensitive. The course section information is public. The students table is fully private. The size of the enrollment in each section (i.e., the section id (sid) column in 𝑇 5 ) is public, the grades in the same table are private, and the university may wish to make review scores public while protecting the association between the review and students who gave the review. To what degree can existing systems support such a scenario? Systems that explicitly track record ownership throughout query execution (e.g., [29]) cannot handle databases where different entities interact (e.g., faculty assigning grades to students). Some work cannot handle databases with foreign keys (i.e., it is impossible for them to provide plausible deniability for a student and all records owned by the student across different tables) [13, 18]. The most sophisticated privacy model in a DP SQL system [15] handles those two cases but cannot support fine-grained reasoning about different columns (e.g., a query about the number of highly-paid faculty who teach AI courses should require relatively more noise than a query about the number of male faculty who teach AI courses), cannot reason about tables whose sizes are known, and cannot reason about public columns or protect associations (e.g., who left the review, when the review score is public). Our approach towards more expressive privacy policies, and contributions of the paper are the following:

uid u1 u2 u3

name Alice Bob Chris

fid f1 f2 f3

name Dan Joe Fred

eid e1 e2 e3

major Econ Math Bio

salary 50K 90K 40K

sid s1 s1 s3

uid u1 u2 u1

aid a1 a2 a3

age 35 41 62

sid s1 s2 s3

grade 93 82 88

uid u1 u2 u3

amount 10K 30K 20K

fid 1 2 2

title NLP Calc Phys

review 3 1 5

Figure 1: The data ownership graph of a university schema (left) and an instance of the same schema, where 𝑇 𝑖 is the table for relation 𝑅𝑖 in a hypothetical world W 0 (right).

algebra queries, involving joins and aggregations, in order to compute how much noise must be added to the query answers. • We implement this multi-level system, where a high-level humanfriendly specification is translated into an expressive automatedreasoning-friendly specification, as a tool which we call DP4SQL. It is implemented as database middleware that intercepts SQL queries and determines how much noise needs to be added to satisfy all of the plausible deniability policies. • Experiments on TPC-H [5] and a case study on flexible privacy policies validate our approach and show that competing work does not add appropriate noise levels to SQL queries.

2

Related Work

A central challenge for differentially private SQL is supporting practical multi-table queries—especially join-heavy workloads—without either (1) unsound privacy accounting or (2) overly conservative sensitivity bounds that destroy utility. Joins can amplify an individual’s contribution across multiple relations, and this amplification depends on schema constraints (e.g., foreign keys), data distributions (e.g., fanout), and query structure (e.g., chains of joins, self-joins, and joins composed with grouping). PINQ [18] introduced the idea of integrating privacy accounting into a query-like programming interface, enforcing bounded contribution and tracking stability of transformations to calibrate noise. Following systems in this line focus on expressing analyses as pipelines of relational operators and ensuring that the accumulated stability remains bounded. However, general join patterns remain challenging because contribution can grow rapidly with fanout unless additional structural assumptions (e.g., key-joins) or explicit clipping/truncation are imposed. FLEX [13] advanced the state-of-the-art by providing local sensitivity upper bounds for SQL with reasoning that leverages maximumfrequency (fanout) bounds to control join amplification. These approaches are effective for many join patterns but are typically tied to a fixed privacy interpretation (commonly, under the bounded neighbors setting) and a table-level policy model. As a result, they often treat entire records as uniformly private, which can force noise

• We propose a simple, high-level column labeling framework that allows a data administrator to specify multiple plausible deniability requirements for each type of entity in a database with foreign keys. Although conceptually simple, it provides support for situations where table sizes are known, some columns are public, other columns need more protection, etc. • We propose a flexible, lower-level, plausible-deniability-action framework for specifying plausible deniability requirements in a way that is more suitable for automated reasoning. We develop an inference system with production rules that map the data administrator’s column labeling into this more complex lowerlevel policy specification. This lower-level specification can be mapped into a neighbor relation, and this allows our inference system to further reason soundly about the stability of relational 2

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

Table 1: Table of Notation.

even when only a subset of attributes (or only specific associations across tables) require protection. PrivateSQL [15] formalized an entity-level neighboring relation for multi-relational databases with referential constraints and developed a sensitivity analysis that is cognizant of join structure and ownership induced by foreign keys. This was an important step beyond single-table or record-level models because it aligns privacy with real-world entities that own records in multiple tables. However, PrivateSQL ’s policy model is intentionally simple: it primarily targets unbounded (delete-one-entity) semantics and cannot directly express attribute-level policies where some columns are public and others are private, nor can it simultaneously mix bounded and unbounded notions of plausibility across relations.

3

Notation from Section 3 S: Pair (R, C) of set of relations and integrity constraints. R: A set {𝑅 1, . . . , 𝑅𝑛 } of relations. C: Database integrity constraints (i.e., foreign key links). 𝑅: A relation with attributes attr(𝑅) = {𝑃𝐾, 𝐴1, . . . , 𝐴𝑚 }. 𝑇: A table; concrete instance of a relation. 𝐷: A database; concrete instance of a schema. fk fk → , ↠: Indicates foreign key and transitive foreign key. ow ow → , ↠: Indicates ownership and transitive ownership. ⊗(𝑇 1,𝑇 2, 𝑟 1 ): Records in 𝑇 2 transitively owned by 𝑟 1 ∈ 𝑇 1 . Notation from Section 5 𝑅★ : A distinguished entity relation. P S,𝑅★ : A privacy policy for schema S and entity 𝑅★. N (P S,𝑅★ ): Set of neighboring database pairs w.r.t. policy. Notation from Section 6 mf(𝑇 .𝐴): Frequency of most frequent value of 𝑇 .𝐴. mmf(𝑅.𝐴): Computed upper bound on mf(𝑇 .𝐴). ˆ 1, 𝑅 2 ): ⊗(𝑅 Maximum number of records 𝑅 1 can own in 𝑅 2 . Δ P S,𝑅★ (𝑄): Global sensitivity of query 𝑄 w.r.t. policy. Δ̂ P S,𝑅★ (𝑄): Inferred upper bound on global sensitivity.

Notation and Background

A relational database schema is a pair S = (R, C) where R = {𝑅 1, . . . , 𝑅𝑛 } is a set of relations providing metadata about tables in a database, and C is a set of integrity constraints that specify foreign key restrictions on the relations. Each relation 𝑅 contains a finite set of attributes attr(𝑅) = {𝑃𝐾, 𝐴1, . . . , 𝐴𝑚 }1 . The set of possible values for an attribute 𝐴 is called the domain of 𝐴 and denoted by dom(𝐴). We also write dom(𝑅) = dom(𝑃𝐾) × dom(𝐴1 ) × · · · × dom(𝐴𝑚 ). To distinguish attributes from different relations we write 𝑅.𝐴 to indicate that 𝐴 is an attribute of 𝑅.

if 𝑟 has a foreign key to 𝑟 ′ (i.e., the direction of ownership is the reverse of the direction of foreign keys). Similarly, we say 𝑟 ′ transifk tively owns 𝑟 , denoted by 𝑟 ′ ow ↠𝑟 if and only if 𝑟 ↠ 𝑟 ′ . We extend this notation to relations in the obvious way. The ownership arrows between relations form the data ownership graph:

Relations, Tables, and Records. An instance of a relation 𝑅 is a table, denoted 𝑇 ⊂ dom(𝑅). Each element 𝑟 ∈ 𝑇 is called a row or a record. We use 𝑟 .𝐴 to denote the component of 𝑟 that corresponds to attribute 𝐴, and 𝑇 .𝐴 for multiset {𝑟 .𝐴 | 𝑟 ∈ 𝑇 }. For a schema S = (R, C), dom(S) is the set of database instances of R (i.e., tables of relations in R) that satisfy C. An instance of S is a database 𝐷 ∈ dom(S).

Definition 3.2 (Data Ownership Graph). The data ownership graph of a relational schema S = (R, C) is a directed graph 𝐺 (S) = fk (𝑉 , 𝐸) where 𝑉 = R and (𝑅 ′, 𝑅) ∈ 𝐸 if and only if ∃ 𝑅.𝐴→ 𝑅 ′ .𝑃𝐾 ∈ C.

Integrity Constraints. The set of integrity constraints C specify links between relations. If 𝑅.𝐹𝐾 𝑅 ′ is the foreign key attribute for fk 𝑅 ′ .𝑃𝐾, the primary key of 𝑅 ′ , then we write 𝑅.𝐹𝐾 𝑅 ′ → 𝑅 ′ .𝑃𝐾 and say ′ fk 𝑅 references 𝑅 . For simplicity, we may also write 𝑅→𝑅 ′ . Moreover, fk ′ if 𝑟 ∈ 𝑇 , 𝑟 ′ ∈ 𝑇 ′ and 𝑟 .𝐹𝐾 𝑅 ′ = 𝑟 ′ .𝑃𝐾, then we write 𝑟 → 𝑟 . If there is a path from 𝑅 to 𝑅 ′ that follows foreign keys, we say that 𝑅 transitively refers to 𝑅 ′ . Formally:

We also define the records in 𝑇 2 owned by a record 𝑟 1 ∈ 𝑇 1 : Definition 3.3 (Ownership). Let S = (R, C), let 𝑅1, 𝑅2 ∈ R be any two relations, and let 𝑇 1 ⊂ dom(𝑅 1 ) and 𝑇 2 ⊂ dom(𝑅 2 ). The records that 𝑟 1 ∈ 𝑇 1 owns in 𝑇 2 is defined as: ⊗(𝑇 1,𝑇 2, 𝑟 1 ) = {𝑟 2 ∈ 𝑇 2 | 𝑟 1 ow ↠𝑟 2 } Some relations (e.g., Faculty and Student) are called entity relations because they define entities who need privacy protection. Let E be the set of entity relations. Relations not in E are called non-entity relations. Entity relations are “roots” in the data ownership graph and they can transitively own records in non-entity relations. For example, in the data ownership graph in Figure 1, 𝑅 1 (with table 𝑇 1 ) is the entity relation Student and it has an ownership arrow to Enrollment (𝑅 5 ) because of the foreign key going the other way. The entity relation Faculty (𝑅 2 ) has an ownership arrow to Section (𝑅 4 ), which has an ownership arrow to Enrollment. So Faculty also transitively owns Enrollment. For convenience, our notation is summarized in Table 1 in order of appearance.

Definition 3.1 (Transitive Referral). A relation 𝑅 transitively refers fk to a relation 𝑅 ′ if 𝑅→ 𝑅 ′ or (recursively) if there exists a relation 𝑅 ′′ fk ′′ such that 𝑅→𝑅 and 𝑅 ′′ transitively refers to 𝑅 ′ . Similarly, a record fk ′ 𝑟 ∈ 𝑇 transitively refers to a record 𝑟 ′ ∈ 𝑇 ′ if 𝑟 → 𝑟 or if there exists fk ′′ a record 𝑟 ′′ ∈ 𝑇 ′′ such that 𝑟 → 𝑟 and 𝑟 ′′ transitively refers to 𝑟 ′ . In fk both cases, we use ↠ to denote transitive referral relation. As standard, we require foreign keys to be acyclic (i.e., no relation transitively refers to itself).

3.1

Data Ownership Graph

The data ownership graph (e.g., Figure 1) is a key tool for understanding which entities may potentially have ownership of which ow records. We say a record 𝑟 ′ ∈ 𝑇 ′ owns 𝑟 ∈ 𝑇 , denoted by 𝑟 ′ → 𝑟,

3.2

1We require the primary key, 𝑃𝐾 , to be semantically independent of the data. This

Differential Privacy, Counterfactual Worlds, and Plausible Deniability

The plausible deniability model of differential privacy is often viewed through the lens of counterfactual reasoning [27]. Any

assumption is not restrictive, as one can always introduce a unique random identifier as the primary key. 3

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

possible database 𝐷 that satisfies the integrity constraints and is consistent with public knowledge is part of a hypothetical world W. For each entity 𝑥𝑖 (e.g., a student or a faculty), there is at least one counterfactual version of this world W (−𝑥𝑖 ) whose corresponding database 𝐷 (−𝑥𝑖 ) satisfies the integrity constraints and is consistent with the same public knowledge, but from which private information about 𝑥𝑖 has been scrubbed. Thus 𝐷 (−𝑥𝑖 ) is the privacypreserving baseline for 𝑥𝑖 and differential privacy tries to ensure that an attacker’s inference about 𝑥𝑖 in the world W is nearly the same as in the world W (−𝑥𝑖 ) . Each pair (𝐷, 𝐷 (−𝑥𝑖 ) ) and (𝐷 (−𝑥𝑖 ) , 𝐷) of hypothetical 𝐷 and counterfactual 𝐷 (−𝑥𝑖 ) databases is called a pair of neighbors. Properly defining neighboring databases is subtle and challenging, as we explain in Section 4. Though once a collection of neighboring pairs has been specified, differential privacy can be defined:

The extra protection comes from requiring a smaller 𝜖 to be used for these neighbors. Thus, this is a relatively simple situation that only requires fine-grained column-based reasoning from a DP SQL system (however, this is not supported by prior work).

Definition 3.4 (Differential Privacy). Given a collection N of neighboring database pairs and a privacy parameter 𝜖 ≥ 0, a mechanism M : dom(S) −→ Ω is 𝜖-differentially private if for every set of outputs 𝑂 ⊆ Ω and every (𝐷, 𝐷 ′ ) ∈ N :

PINQ [18] and Flex [13] were the earliest forays into DP SQL systems and so had relatively simple privacy models. These models inherently cannot reason about foreign keys and so cannot support these use-cases. They only support counterfactual worlds in which exactly 1 table differs by 1 record. Thus their counterfactual worlds cannot serve as privacy-preserving baselines and generally they will under-protect query answers—they add just enough noise to mask the existence of one record, rather than enough noise to mask all information owned by an entity. The pioneering work of Wilson et al. [29] tracks the ownership of records through the query processing pipeline but it cannot support databases where entities interact and records can be owned by multiple entities (like the Enrollment relation 𝑅 5 in Figure 1), and cannot support fine-grained reasoning about columns. The most sophisticated DP SQL model was proposed by Kotsogiannis et al. [15] and it can handle both foreign keys and multiple types of interacting entities. However, it cannot perform finegrained reasoning about columns or about tables whose sizes cannot change in counterfactual worlds (like the Faculty table). It also cannot reason about associations (e.g., hiding associations between students and their reviews). So for some queries, it can unnecessarily add too much noise, and for others it can add too little noise. Consider the query SELECT s.amount, AVG(e.grade) FROM Scholarship s, Enrollment e WHERE s.uid = e.uid GROUP BY s.amount. This query calculates the average grade of students for different scholarship amounts. To protect a student, PrivateSQL [15] can only consider counterfactual worlds where all records with the same uid (across Student, Scholarship, and Enrollment) are dropped. This would cause 1 student to drop out of the join and PrivateSQL adds just enough noise to cover such a change. However, such counterfactual worlds are not consistent with public knowledge. Instead, a consistent counterfactual world requires the foreign keys from Scholarship and Enrollment that point to the dropped student to be changed to someone else. Thus, a student’s result would drop out of the join (affecting one group in the group-by), but the changed foreign keys in the Scholarship and Enrollment tables could each link to a new person, therefore affecting many other groups. Thus, to make a world indistinguishable from its counterfactual world, much more noise must be added. Hence, it is an issue of correctness—if the privacy model cannot be customized, some queries will receive too much noise while others will receive too little noise.

Counterfactuals for Students. The entity relation for students is 𝑅 1 and it owns the enrollments relation 𝑅 5 . A counterfactual world for a specific student would drop that student from the students table 𝑇 1 but would only be able to reassign their grade and student id (uid) for all sections the student is enrolled in (i.e., enrollment records cannot be dropped, but parts of them can be modified).

4.1

𝑒 −𝜖 𝑃𝑟 [M (D ′ ) ∈ 𝑂] ≤ 𝑃𝑟 [M (𝐷) ∈ 𝑂] ≤ 𝑒 𝜖 𝑃𝑟 [M (𝐷 ′ ) ∈ 𝑂]

4

Motivation

To motivate the challenges in defining counterfactual worlds, and to see where existing DP SQL frameworks fall short, let us return to the university schema of Figure 1. Suppose this fictitious university has decided on the following policy, stated informally as: (1) Faculty name from relation 𝑅 2 is public. (2) All other faculty information (demographics, salary) should be private but salary should have stronger protections. (3) The review scores from relation 𝑅 5 that students assign to faculty should be public, but the association (i.e., which student assigned which review score) is private. (4) The number of scholarships from relation 𝑅 3 is public, but the award amount and the who the recipients are is private. (5) The sections 𝑅 4 relation is public, but information about which students are in which section is private. Thus the section id (sid) column in 𝑅 5 is public. (6) All other information about students is private. We next consider appropriate counterfactual worlds and then analyze the shortcomings of the privacy models used in prior work. Counterfactuals for Faculty. 𝑅 2 is the entity relation for faculty and faculty have ownership of records in 𝑅 4 (sections they teach) and 𝑅 5 (since they assign grades). Because of the public information (name column of 𝑅 2 , all columns of 𝑅 4 , and review column of 𝑅 5 ), one cannot form a privacy-preserving counterfactual world that deletes any records owned or transitively owned by a faculty member. The best that can be done is to replace the contents of demographics and salary in 𝑅 2 with different values, and replace the grades in 𝑅 5 . This gives multiple counterfactual worlds for each faculty member, where each world corresponds to a different setting of the modifiable attributes in records owned by a faculty. Extra Protections for Salary. To provide extra protections for a faculty salary, one can create additional counterfactual worlds for each faculty by (counter-intuitively) altering just one faculty salary. 4

Limitations in Prior Models

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

5

𝐷, and privacy policy P S,𝑅★ = {𝑃1, · · · , 𝑃𝑛 }, we next formally define the meaning of the privacy policy, in terms of what it means for 𝐷 ′ = {𝑇 1′ , · · · ,𝑇 𝑛′ } to be a neighbor of 𝐷 under the policy. Intuitively the following definition requires that: (1) 𝑇 𝑖 and 𝑇 𝑖′ only differ in the records owned by a single entity 𝑒 ∈ 𝑇 𝑅★ , (2) the difference in those records obeys policy 𝑃𝑖 , and (3) all integrity constraints C are satisfied. Recalling that ⊗(𝑇 𝑅★ ,𝑇 𝑖 , 𝑒) is the set of records in 𝑇 𝑖 transitively owned by entity record 𝑒 ∈ 𝑇 𝑅★ , we define neighbors and DP for the policy as follows:

High-level Privacy Specifications

In our proposed framework, DP4SQL, a data administrator specifies a set of privacy policies for for each entity relation, such as students and faculty, each associated with a level of privacy strength (i.e., a 𝜖 parameter for pure differential privacy). A query would be evaluated against each entity relation and conservatively add the largest noise variance among all to ensure sufficient privacy protection for all entities. Hence, for the rest of this paper, we assume a distinguished entity relation 𝑅★ ∈ R and show how to specify and enforce a privacy policy for 𝑅★. We start with a high-level, “privacy labels” framework that a data administrator can use to specify a policy. Then in Section 6, we propose a lower-level “plausible deniability action” framework that is more suitable for automated reasoning—we show how to translate the labeling policy into a set of plausible deniability actions and how to track query stability and sensitivity so that the right amount of noise can be added.

5.1

Definition 5.1 (Neighboring Databases). Let S = (R, C) be a relational schema and P S,𝑅★ = {𝑃1, · · · , 𝑃𝑛 } a privacy policy. We denote by N (P S,𝑅★ ) the set of pairs of databases 𝐷 = {𝑇 1, · · · ,𝑇 𝑛 } and 𝐷 ′ = {𝑇 1′ , · · · ,𝑇 𝑛′ } such that ∀(𝐷, 𝐷 ′ ) ∈ N (P S,𝑅★ ): • 𝐷 and 𝐷 ′ satisfy C, and • 𝑇 𝑅★ and 𝑇 𝑅′ ★ differ by exactly 1 record 𝑒 ∈ 𝑇 𝑅★ , and • if 𝑂𝑖 = ⊗(𝑇 𝑅★ ,𝑇 𝑖 , 𝑒), 𝑂 𝑖 = 𝑇 𝑖 \ 𝑂𝑖 and 𝑃𝑖 is... Ñ – DEL, then 𝑇𝑖 𝑇𝑖′ = 𝑂 𝑖 and 𝑇 𝑖′ \ 𝑇 𝑖 = ∅. Ñ A – REP , then |𝑇 𝑖 | = |𝑇 𝑖′ |, 𝑇𝑖 𝑇𝑖′ = 𝑂 𝑖 , and ∀𝑟 ∈ 𝑂𝑖 . ∃𝑟 ′ ∈ 𝑇 𝑖′ such that 𝑟 only differs from 𝑟 ′ by the values of attributes in A. – PUB, then 𝑇𝑖′ = 𝑇𝑖 .

High-Level Privacy Labels

Each policy is associated with a distinguished entity relation 𝑅★ ∈ R from the schema S and assigns a label to each relation. Hence we denote a policy as P S,𝑅★ = {𝑃1, · · · , 𝑃𝑛 }, where 𝑃𝑖 is the label for 𝑅𝑖 . For convenience, we simply write P S,𝑅★ (𝑅𝑖 ) = 𝑃𝑖 , and may omit the S in the notation (i.e., P 𝑅★ ) when clear from context. There are 3 choices of labels for a relation 𝑅 and its associated table 𝑇 : • DEL: Everything in the associated table 𝑇 ⊂ dom(𝑅) (including its size) is private, and the existence of records is protected. The counterfactual worlds are created by deleting records. • REP A : The values of all attributes in A are deemed private, but the existence of a record in 𝑇 is not protected. Hence, the table size is public (i.e., not protected by this policy) and attributes not in A are also public. Counterfactual worlds are created by modifying the values of the attributes in A. • PUB: The entire relation is public. Intuitively, the difference between DEL and REP A policies lies in what “protecting an individual” means. DEL protects the existence of an entity in the dataset, while REP A only hides attributes belonging to entities, not their presence. Hence, in a single-relation setting, the DEL policy is the same as using DP with unbounded neighbors, and REP A is akin to bounded neighbors. For example, if the number of students is private, we can give the relation the DEL label to protect the existence of students. If the number of students is public but their names are private, we can give the relation the REP {name} label. If all student information is public (i.e., names, majors), we can give the relation the PUB label. Note that whenever an attribute 𝑅.𝐴 is public, the size of 𝑅 is public as a consequence.

5.2

Note that by instantiating the neighboring relation N in Definition 3.4 with Definition 5.1, we have the formal differential privacy definition with DP4SQL. Definition 5.2 (DP for Privacy Policy). Let S be a schema, P S,𝑅★ be a privacy policy, and 𝜖 a privacy budget. A mechanism M : dom(S) −→ Ω is (P S,𝑅★ , 𝜖)-differentially private if for every set of outputs 𝑂 ⊆ Ω and ∀(𝐷, 𝐷 ′ ) ∈ N (P S,𝑅★ ): 𝑒 −𝜖 𝑃𝑟 [M (𝐷 ′ ) ∈ 𝑂] ≤ 𝑃𝑟 [M (𝐷) ∈ 𝑂] ≤ 𝑒 𝜖 𝑃𝑟 [M (𝐷 ′ ) ∈ 𝑂]

5.3

Checking Privacy Labels

The flexibility of our approach also makes it possible for a data administrator to create nonsensical labels. Thus, when we translate privacy labels into the lower-level plausible deniability actions in Section 6, we also include consistency checks (Section 6.4). To help motivate the need for those checks, we give an example of a nonsensical policy here. Consider a schema with an entity relation 𝑅 1 (eid, 𝐴) having primary key eid and attribute 𝐴, and a non-entity relation 𝑅 2 (id, eid, 𝐵) with a primary key id, foreign key eid into 𝑅 1 and an attribute 𝐵. Suppose the labels are DEL for 𝑅 1 and PUB for 𝑅 2 . This signals the intention to protect the existence of entities (records) in 𝑅 1 . However, the public foreign key in 𝑅 2 already reveals existence of entities and simply deleting records from a table instance 𝑇 1 ⊂ dom(𝑅 1 ) could result in an inconsistent database. The inference system would reject such a policy. Instead, the data administrator would have two choices: (1) either choose the label REP {𝐴} for 𝑅 1 to protect the attribute 𝐴 but not record existence or (2) choose the label REP {eid} for 𝑅 2 to protect the foreign key from 𝑅 2 to 𝑅 1 , but leave the rest of the attributes in 𝑅 2 public.

Neighboring Databases

The definition of neighboring databases can be constructed from the privacy labels. We use the intuition about counterfactual world properties, explained above in the context of individual relation labels, to define counterfactual worlds that are consistent with ownership, public information and integrity constraints. Given the schema S = (R, C), database 𝐷 = {𝑇 1, · · · ,𝑇 𝑛 } ∈ dom(S), distinguished entity relation 𝑅★, its associated table 𝑇 𝑅★ ∈ 5

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

6

6.2

Low-Level Privacy Specifications: The Plausible Deniability Actions

To enforce DP for a privacy policy P S,𝑅★ , a fundamental challenge is to analyze the sensitivity of a given SQL query: to what extent can its output vary when evaluated on two neighboring databases? For example, consider the following query to the database in Figure 1: What is the total number of enrollments? The sensitivity is the greatest change to the answer of this query between any two neighboring databases. For simplicity, consider the unbounded neighbors case, where all neighbors result from removing a single student from the database. In the worst case, the sensitivity is the maximum number of sections a student can be enrolled in by university policy. The stability of a relational operator (distinct from, but closely related to sensitivity) is the greatest number of changed records that may result from applying the relational operator to a pair of neighboring databases. The distinction is that stability is a property of functions that output relations (e.g., relational operators), whereas sensitivity is a property of functions that output numbers (e.g., count queries). Historically, starting with PINQ [18], stability is defined as the number of records in the output of a relational operator that are affected by one record in its input. However, due to its more expressive privacy model, DP4SQL also needs to track which set of attributes is changed. Hence, we propose and use a more general type of stability analysis called plausible deniability actions, which denote the greatest change that may result from applying a relational operator to a pair of neighboring databases. We first introduce plausible deniability actions, which help to reason about the effect of relational operators on neighboring databases (Section 6.1), and then develop an inference system, formalized as a set of derivation rules, to automatically derive plausible deniability actions for SQL queries (Section 6.4). Finally, we transform the actions to an upper bound on the sensitivity (Section 6.9), which determines how much noise must be added to the query answer.

6.1

Maximum Frequency

To soundly approximate all possible changes between two neighboring tables or views generated by SQL queries, we follow prior work [13, 15] by assuming a static upper bound on the maximum frequency of each attribute in the schema. Such upper bounds are even used in work on truncation operators (e.g., [8]) that try to reduce global sensitivity. In the case of tables/attributes that are public in all privacy policies (e.g., globally public), their maximum frequencies can be taken from the data. Let 𝑅 be a relation, let 𝑇 ⊂ dom(𝑅) be an associated table, and let 𝐴 ∈ attr(𝑅) be an attribute. The (instance-specific) maximum frequency mf(𝑇 .𝐴) is the frequency of the most frequent value of 𝐴 in table 𝑇 . We also assume an (instance-independent) upper bound on the maximum frequency among all possible tables, which is denoted mmf(𝑅.𝐴).

6.3

Maximum Ownership

To derive plausible deniability actions, we need to compute an upper bound on the number of records that are owned by an entity 𝑒. This is called the maximum ownership of 𝑒. Generally, if 𝑇 1,𝑇 2 ∈ 𝐷, the maximum number of records owned in 𝑇 2 by any record 𝑟 ∈ 𝑇 1 can be statically computed as follows: Definition 6.1 (Maximum Ownership). Let S = (R, C) where 𝑅 1, 𝑅 2 ∈ R. The maximum number of records a record 𝑟 in an instance of 𝑅 1 can own in an instance of 𝑅 2 is defined as follows: ˆ 1, 𝑅 2 ) = ⊗(𝑅

   1  Í ˆ 1, 𝑅 𝑗 ) mmf(𝑅 2 .𝐹𝐾 𝑖 ) · ⊗(𝑅   fk 𝑅 2 .𝐹 𝐾 𝑖 → 𝑅 𝑗 .𝑃𝐾 

if 𝑅 1 = 𝑅 2 otherwise

We show that maximum ownership is indeed an upper bound on the size of ownership with the following lemma. Lemma 6.2 (Correctness of Maximum Ownership). Let S = (R, C) be a schema, 𝐷 ∈ dom(S) any database, and 𝑅 1, 𝑅 2 ∈ R any two relations with corresponding instances 𝑇 1,𝑇 2 ∈ 𝐷. Then,

Plausible Deniability Actions

ˆ 1, 𝑅 2 ). ∀𝑟 1 ∈ 𝑇 1 . |⊗(𝑇 1,𝑇 2, 𝑟 1 )| ≤ ⊗(𝑅

For multi-relational databases, PrivateSQL [15] defined the global sensitivity of a view as the maximum number of distinct rows that may differ between a query’s outputs when executed on any pair of neighboring databases. However, due to the flexible model of DP4SQL, we need to track more information (e.g., which set of attributes might change) during the stability analysis. DP4SQL proposes the following set of 3 plausible deniability actions. Informally, they describe the operations to be performed on a table 𝑇 or view in one database that can transform it into a table or view in a neighboring database, as specified by the data administrator’s privacy labels.

6.4

Action Inference for Base Relations

We develop an inference system to automatically compute the plausible deniability actions, from privacy labels, for each base relation 𝑅 ∈ R. The inference rules are shown in Figure 2. The rules are relatively simple; there is one rule for each privacy label for each kind of relation. Each rule states that the plausible deniability action below the horizontal line can be derived whenever all assumptions above the line are valid. Distinguished Entity Relations. For a distinguished entity relation 𝑅★, plausible deniability actions are derived directly from the privacy labels themselves. If P 𝑅★ (𝑅★) = DEL (E-Del), then the action for 𝑅★ is Add0 × Del1 , since the existence of a single entity is protected by deletion. If P 𝑅★ (𝑅★) = PUB (E-Pub), then the action for 𝑅★ is Rep0∅ since all attributes are considered public. If P 𝑅★ (𝑅★) = REP A (E-Rep), then the action for 𝑅★ is Rep1A since the values of attributes in A of a single entity are protected by replacement.

(1) Add𝑎 : Add 𝑎 rows. (2) Del𝑑 : Delete 𝑑 rows. (3) Rep𝑘A : Replace values of attributes A in 𝑘 rows. Note that we do not explicitly introduce a no-op action for public relations as this can be modeled with Rep0∅ . Moreover, Add𝑎 and Del𝑑 are always written together as the product action Add𝑎 × Del𝑑 , as some queries may require both the addition and deletion of records when joins are involved. 6

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

Inference Rules for a Distinguished Entity Relation P 𝑅★ (𝑅★) = DEL ★

⊢ 𝑅 : Add0 × Del1 P 𝑅★ (𝑅★) = REP A

𝑄 ::= 𝛾 CNT(∗) (𝑆) | 𝛾 SUM(𝐴) (𝑆) A A

★

(E-Del)

P 𝑅★ (𝑅 ) = PUB ⊢𝑅

A ⊂ attr(𝑅★) ⊢𝑅

★

★

: Rep0∅

𝑆 ::= 𝑅 | 𝜎 𝜑 (𝑆) | 𝜋 A (𝑆) | 𝛾 A (𝑆) | 𝛾 CNT(∗) (𝑆) | 𝑆 1 Z 𝑆 2 A

(E-Pub)

𝐴1 =𝐴2

𝑅★ .𝑃𝐾 ∉ A

Figure 3: Syntax of relational algebra supported by DP4SQL. 𝑄 is a query. 𝑅 is any base relation, 𝐴 is an attribute, A is a set of attributes, and 𝜑 is a logical predicate over attributes.

(E-Rep)

: Rep1A

Inference Rules for Non-Entity Relations P 𝑅★ (𝑅) = DEL ⊢ 𝑅 : Add0 × Del⊗ˆ (𝑅★,𝑅) P 𝑅★ (𝑅) = PUB

clauses, as well as intermediate counting aggregations and subqueries in the WHERE clause. In addition to COUNT(*), DP4SQL also supports the SUM(𝐴) aggregation.

(F-Del)

fk ∀𝑖. 𝑅→ 𝑅𝑖 . ¬private(𝑅𝑖 .𝑃𝐾)

⊢ 𝑅 : Rep0∅ P 𝑅★ (𝑅) = REP A A ⊂ attr(𝑅) 𝑅.𝑃𝐾 ∉ A fk ∀𝑖. 𝑅→ 𝑅𝑖 . private(𝑅𝑖 .𝑃𝐾) =⇒ 𝑅.𝐹𝐾 𝑅𝑖 ∈ A ⊢ 𝑅 : Rep⊗A ˆ (𝑅★,𝑅)

Relational Algebra. As standard, we use relational algebra to model the semantics of the supported SQL queries. The syntax is shown in Figure 3. For a schema S = (R, C), a relational algebra expression 𝑆 is either a base relation 𝑅 ∈ R or a relational transformation. Supported transformations are the select (𝜎), project (𝜋), equijoin ( Z ), grouping (𝛾 A ), and grouping with count (𝛾 CNT(∗) ) A

(F-Pub)

(F-Rep)

𝐴1 =𝐴2

operators. A view 𝑆 (𝐷) is an instance of an expression 𝑆 for database 𝐷. Lastly, a top-level query 𝑄 applies an aggregate function, possibly with grouping, on an expression 𝑆 and is the last step in the query execution. In our language, a top-level query 𝑄 takes a database as input and returns a real number for each of its output grouping bins, 𝑄 : D → R𝑛 . The rest of this section details how to extend the inference system of Figure 2 to support the aforementioned relational operators. Then, after applying the outermost aggregation, we will derive an upper bound on the global sensitivity (formally defined in Section 6.8), which parametrizes the Laplace mechanism [10] used to compute the amount of noise injected into the query answer.

Figure 2: Inference rules for base relations. 𝑅★ is a distinguished entity relation and 𝑅 is any non-entity relation. The private (𝐴) predicate is true when 𝐴 is protected by deletion or replacement under P 𝑅★ .

Non-Entity Relations. For a non-entity relation 𝑅 ≠ 𝑅★, deriving the plausible deniability action is slightly more complicated due to dependencies; 𝑅 may have foreign keys that refer to other relations. Let 𝑒 be an entity record that requires protection. If P 𝑅★ (𝑅) = DEL (F-Del), then the existence of 𝑒 must be protected by deletion. ˆ ★, 𝑅) records in 𝑅. Therefore, the In the worst case, 𝑒 owns ⊗(𝑅 action for 𝑅 is Add0 × Del⊗ˆ (𝑅★,𝑅) . The nontrivial cases are when P 𝑅★ (𝑅) = PUB or P 𝑅★ (𝑅) = REP A . In the former case (F-Pub), the PUB policy requires that the entire relation 𝑅 is public. Therefore, all foreign keys are public, and all matching primary keys are required to be public, as required fk by the assumption: ∀𝑖. 𝑅→ 𝑅𝑖 . ¬private(𝑅𝑖 .𝑃𝐾). Since the entire relation is public, the action for 𝑅 is Rep0∅ . In the latter case (FRep), the REP A policy requires that the attributes in A, which may include foreign keys, are private. Therefore, each private primary key must be matched with a private foreign key, as required by the fk assumption: ∀𝑖. 𝑅→ 𝑅𝑖 . private(𝑅𝑖 .𝑃𝐾) =⇒ 𝑅.𝐹𝐾 𝑅𝑖 ∈ A. Since ˆ ★, 𝑅) records in 𝑅, the action for 𝑅 is Rep A ★ . 𝑒 owns at most ⊗(𝑅 ⊗ˆ (𝑅 ,𝑅) We note that these checks essentially ensure that foreign keys are at least as private as their corresponding primary keys. While they are not needed when P 𝑅★ (𝑅) = DEL since all attributes are private by assumption, they are required for PUB and REP A to rule out nonsensical labels discussed in Section 5.3.

6.5

6.6

Action Inference for Unary Transformations

We next extend the plausible deniability actions to relational transformations. Unary transformations (i.e., select, project, grouping) are detailed first, followed by join transformations. The rules for unary transformations are summarized in Figure 4. Action inference is sequential: the action for each transformation is dependent on the actions of the underlying expressions, starting with the base relations. Each expression can be thought of as a tree where the leaf nodes are base relations and the non-leaf nodes are transformations. The action for each node is computed in a bottom-up manner, starting from the leaves and working up to the root. The root contains the action for the entire query 𝑄. Select. Let 𝑆 be an expression and 𝜎 𝜑 (𝑆) be a selection with a predicate 𝜑. If 𝑆 has action Add𝑎 × Del𝑑 , then 𝜎 𝜑 (𝑆) has the same action since selection does not change rows (T-Sel1). If 𝑆 has action Rep𝑘A , then the action on 𝜎 𝜑 (𝑆) depends on if 𝜑 conditions on any 𝐴 ∈ A. If it does not, then selection will not affect the number of records in the resulting neighboring tables as it always filters the same records in 𝑆 and its neighbor. Hence, the action on the result is still Rep𝑘A (T-Sel2). Otherwise, each replaced value of 𝐴 may add, delete, or replace a record in the resulting neighboring tables. Hence, the action on 𝜎 𝜑 (𝑆) is Add𝑘 × Del𝑘 since replacement can be modeled as simultaneous deletion and addition (T-Sel3).

SQL Queries and Relational Algebra

Next, we extend the inference system to support an expressive subset of SQL. Like PrivateSQL [15], DP4SQL supports useful SQL operations such as SELECT, WHERE, JOIN (equijoins), and GROUP BY 7

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

action for 𝛾 CNT(∗) (𝑆) depends on if A 1 and A 2 share any attributes. A2 If they do, then each replaced record may change the count of 2 groups (i.e., add to the count of one group, and reduce the count of {CNT} another). Therefore, the action is Rep2𝑘 (T-Grp3). Otherwise, the replacement cannot affect the count, so the action is Rep0∅ (T-Grp4). Note that T-Grp3 and T-Grp4 also apply to aggregation without grouping when A 2 = ∅, a special case when all records are put in one group. For example, 𝛾 CNT(∗) (𝑆) returns the size of 𝑆. ∅

Inference Rules for Unary Transformations ⊢ 𝑆 : Rep𝑘A 𝜑 has no 𝐴 ∈ A

⊢ 𝑆 : Add𝑎 × Del𝑑 ⊢ 𝜎 𝜑 (𝑆) : Add𝑎 × Del𝑑 ⊢ 𝑆 : Rep𝑘A 𝜑 has some 𝐴 ∈ A ⊢ 𝜎 𝜑 (𝑆) : Add𝑘 × Del𝑘 ⊢ 𝑆 : Rep𝑘A 1 A1 ∩ A2 = ∅ ⊢ 𝜋 A 2 (𝑆) : Rep0∅

(T-Sel1)

⊢ 𝑆 : Rep𝑘A 1 A1 ∩ A2 ≠ ∅ (T-Sel3)

(T-Prj2)

⊢ 𝜋 A 2 (𝑆) : Rep𝑘A 1 ∩A 2

⊢ 𝛾 A (𝑆) : Rep0∅ (T-Grp1)

{CNT} ⊢ 𝛾 CNT(∗) (𝑆) : Rep2𝑘 A2

(T-Grp3)

6.7

(T-Prj3)

⊢ 𝜋 A (𝑆) : Add𝑎 × Del𝑑

{CNT} ⊢ 𝛾 CNT(∗) (𝑆) : Rep𝑎+𝑑 A

(T-Prj1)

Action Inference for Join Transformations

A join is either a key join, where the join is on a primary-foreign key attribute pair, or a general join, where the join is on any attributes.

⊢ 𝑆 : Add𝑎 × Del𝑑

⊢ 𝑆 : Add𝑎 × Del𝑑

⊢ 𝑆 : Rep𝑘A 1 A1 ∩ A2 ≠ ∅

(T-Sel2)

⊢ 𝜎 𝜑 (𝑆) : Rep𝑘A

6.7.1 Key Joins. A key join has the form of 𝑅

⊢ 𝛾 CNT(∗) (𝑆) : Rep0∅ A2

𝑆 which joins

on the primary key of an expression 𝑆 and a matching foreign key 𝐹𝐾 𝑆 of a base relation 𝑅. In contrast to the general join (when either the foreign key is not from a base relation, or when the join is on arbitrary attributes, which we elaborate in Section 6.7.2), DP4SQL fk leverages the integrity constraint 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾 to derive a tighter bound, as shown at the top of Figure 6. Suppose 𝑅 has action Add0 × Del⊗ˆ (𝑅★,𝑅) . After the join, there are ˆ ★, 𝑅) records deleted (T-Key1) since due to the foreign at most ⊗(𝑅 fk key constraint 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾, all deleted records from 𝑆 match with deleted records from 𝑅. Since 𝑅 may delete more records due to other foreign keys, the number of total deleted records is upper ˆ ★, 𝑅). bounded by the maximum ownership ⊗(𝑅 If instead 𝑅 has action Rep𝑘A , then at most 𝑘 records are replaced. There are two cases: (1) 𝑆.𝑃𝐾 is private or (2) 𝑆.𝑃𝐾 is public. When it is private, each replaced record in 𝑅 may be matched with a different record in 𝑆. So, while the size of the join remains the same, the attributes in attr(𝑆) are also replaced (T-Key2). When it is public, 𝑆 must have a Rep action. In this case, the size of the join also remains the same, but only records in A 1 ∪ A 2 may be replaced (T-Key3).

(T-Grp2)

⊢ 𝑆 : Rep𝑘A 1 A1 ∩ A2 = ∅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

(T-Grp4)

Figure 4: Action inference rules for select (𝜎 𝜑 ), project (𝜋 A ), grouping (𝛾 A ), and grouping with count (𝛾 CNT(∗) ). A Project. Let 𝑆 be an expression and 𝜋 A (𝑆) be a projection of attributes A. If 𝑆 has action Rep𝑘A 1 , then the action on 𝜋 A 2 (𝑆) depends on if A 1 and A 2 share any attributes. If they do, then only attributes in A 1 ∩ A 2 can be replaced (T-Prj1). Otherwise, no attributes in 𝜋 A 2 (𝑆) are replaceable, so the projection is effectively public (T-Prj2). If 𝑆 has action Add𝑎 × Del𝑑 , then 𝜋 A (𝑆) has the same action since projection does not change rows (T-Prj3).

6.7.2 General Joins. The inference rules for general joins are shown at the bottom of Figure 6. The maximum frequency upper bound mmf(𝑆.𝐴) is derived for each attribute 𝐴 of any expression 𝑆. Since these rules are straightforward, they are included in Appendix B. Suppose 𝑆 1 has action Add𝑎1 × Del𝑑1 and 𝑆 2 has action Add𝑎2 × Del𝑑2 . Each record deleted from 𝑆 1 may match at most mmf(𝑆 2 .𝐴2 ) records in 𝑆 2 . Conversely, each record deleted from 𝑆 2 may match at most mmf(𝑆 1 .𝐴1 ) records in 𝑆 1 . Therefore, at most 𝑑 1 · mmf(𝑆 2 .𝐴2 ) + 𝑑 2 · mmf(𝑆 1 .𝐴1 ) records may be deleted in the result of the join. Similar reasoning applies to the added records, with an additional summed 𝑎 1 · 𝑎 2 term since each pair of added records may match (T-Join1). Suppose 𝑆 2 instead has action Rep𝑘A . Similar reasoning applies, where we conservatively treat Rep𝑘A as Add𝑘 × Del𝑘 (TJoin2). Note that due to the symmetry of the join operator, T-Join2 also applies in the case where the actions on 𝑆 1 and 𝑆 2 are swapped. The remaining cases occur when 𝑆 1 has action Rep𝑘A 1 and 𝑆 2

Grouping with Aggregation. A GROUP BY command in SQL can apply aggregate functions like SUM and COUNT to each group. Providing differential privacy in this case is subtle as group keys may leak information due to the existence/non-existence of a group. For example, Figure 5 shows counterfactual world W 1 , where a single student is removed in the true world W 0 . Taking the grouping 𝛾 {major} (𝑇 1 ) in both worlds results in different set of groups: in W 0 , the CS major group exists, whereas in W 1 it does not. Following previous work [13], DP4SQL preserves privacy by ensuring that the grouping bins (i.e., the set of values of the grouping attributes) are public. Specifically, DP4SQL ensures that the set of grouping bins is equal to the domain of the grouping attributes A. Hence, the result of grouping without aggregation, which simply returns grouping bins, is public (T-Grp1). The inference system also supports grouping with count, of the form 𝛾 CNT(∗) (𝑆). In addition to the public grouping bins, this A operator also returns the counts within each bin, akin to a histogram. In all cases, the histogram has a Rep action since the group keys are public. If 𝑆 has action Add𝑎 × Del𝑑 , each added and deleted record may change the count of at most one group. Therefore, the action {CNT} for 𝛾 CNT(∗) (𝑆) is Rep𝑎+𝑑 (T-Grp2). If 𝑆 has action Rep𝑘A 1 , then the A2

1

has action Rep𝑘A 2 . If neither join key is replaceable, then the size of 2 the join remains the same. Therefore, the attributes in A 1 ∪ A 2 of at most 𝑘 1 · mmf(𝑆 2 .𝐴2 ) + 𝑘 2 · mmf(𝑆 1 .𝐴1 ) records may be replaced (T-Join3). Otherwise, the size of the join may change, and at most the same number of records may be added and deleted (T-Join4). 8

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

uid u1 u2 u3

name Alice Bob Chris

major CS Math Bio

uid u1 u1 u2

name Alice Alice Bob

major CS CS Math

eid e1 e2 e3

sid s1 s1 s3

sid s1 s3 s1

uid u1 u2 u1

grade 93 82 88

review 3 1 5

uid u2 u3

name Bob Chris

major Math Bio

eid e1 e3 e2

grade 93 88 82

review 3 5 1

uid u2

name Bob

major Math

eid e2

sid s1

sid s1

uid u2

grade 82

review 1

eid e2

grade 82

review 1

Figure 5: Records in red exist in the hypothetical world W 0 , but are deleted in counterfactual world W 1 . In the worst case, at most 2 records are deleted from the join 𝑇 1 Z𝑇 5 . on the maximum frequency (mmf) of any foreign key is 2. Let Student (𝑅 1 ) be the distinguished entity relation with P 𝑅 1 (𝑅 1 ) = DEL and Enrollment (𝑅 5 ) a non-entity relation with P 𝑅 1 (𝑅 5 ) = DEL. The inference system first derives ⊢ 𝑅1 : Add0 × Del1 by E-Del, then ⊢ 𝑅5 : Add0 × Del2 by F-Del. Figure 5 shows a counterfactual world (W 1 ) where Alice is deleted from 𝑇 1 . Clearly, at most 2 records are deleted from 𝑇 1 Z𝑇 5 as a result. However, there are two ways to derive the action for 𝑅 5 Z 𝑅 1 . First, by T-Join1 we have

Inference Rules for Key Joins fk 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾

⊢ 𝑅 : Add0 × Del⊗ˆ (𝑅★,𝑅) ⊢𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

⊢ 𝑅 : Rep𝑘A

(T-Key1)

𝑆 : Add0 × Del⊗ˆ (𝑅★,𝑅)

fk 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾

private(𝑆.𝑃𝐾) (T-Key2)

⊢ 𝑅 Z 𝑆 : Rep𝑘A∪attr(𝑆 ) 𝐹 𝐾 =𝑃𝐾

𝐹 𝐾 𝑅 1 =𝑃𝐾

𝑆

⊢ 𝑅5

⊢ 𝑅 : Rep𝑘A 1 1 fk 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾

⊢ 𝑆 : Rep𝑘A 2 2

⊲⊳ 𝐹 𝐾𝑅1 =𝑃𝐾

¬private(𝑆.𝑃𝐾)

𝑎 2 ·mmf(𝑅 5 .𝐹 𝐾 𝑅 1 )+ 𝑎 1 ·𝑎 2

𝑑 2 ·mmf(𝑅 5 .𝐹 𝐾 𝑅 1 )

: Add0·1+0·2+0·0 × Del2·1+1·2

(T-Key3)

⊢ 𝑅 Z 𝑆 : Rep𝑘A 1 ∪A 2 1 𝐹 𝐾 =𝑃𝐾

𝑅1 : Add 𝑎1 ·mmf(𝑅 1 .𝑃𝐾 )+ × Del 𝑑1 ·mmf(𝑅 1 .𝑃𝐾 )+

: Add0 × Del4 .

𝑆

This is an overapproximation since 4 > 2. Second, by T-Key1 we have ⊢ 𝑅5 ⊲⊳ 𝑅1 : Add0 ×Del2 , which is equal to the true stability. We

Inference Rules for General Joins

𝐹 𝐾𝑅1 =𝑃𝐾

⊢ 𝑆 1 : Add𝑎1 × Del𝑑1

⊢ 𝑆 2 : Add𝑎2 × Del𝑑2

(T-Join1)

⊢ 𝑆 1 Z 𝑆 2 : Add𝑎1 ·mmf(𝑆 2 .𝐴2 )+ × Del𝑑1 ·mmf(𝑆 2 .𝐴2 )+ 𝐴1 =𝐴2

𝑎 2 ·mmf(𝑆 1 .𝐴1 )+ 𝑎 1 ·𝑎 2

𝑑 2 ·mmf(𝑆 1 .𝐴1 )

⊢ 𝑆 2 : Rep𝑘A

⊢ 𝑆 1 : Add𝑎 × Del𝑑

⊢ 𝑆 1 Z 𝑆 2 : Add𝑎·mmf(𝑆 2 .𝐴2 )+ × Del𝑑 ·mmf(𝑆 2 .𝐴2 )+ 𝐴1 =𝐴2

⊢ 𝑆 2 : Rep𝑘A 2

1

2

𝐴1 ∉ A 1

⊢ 𝑆 2 : Rep𝑘A 2 2 𝑘 2 ·mmf(𝑆 1 .𝐴1 )+ 𝑘 1 ·𝑘 2

Definition 6.4 (Global Sensitivity). Let S be a schema and P S,𝑅★ be a privacy policy. For any query 𝑄, the global sensitivity is

𝐴1 ∈ A 1

⊢ 𝑆 1 Z 𝑆 2 : Add𝑘1 ·mmf(𝑆 2 .𝐴2 )+ × Del𝑘1 ·mmf(𝑆 2 .𝐴2 )+ 𝐴1 =𝐴2

(T-Join3)

2

⊢ 𝑆 1 : Rep𝑘A 1 1

Global Sensitivity

The methods presented thus far infer an upper bound on the number of records that might be changed in a neighboring database when a single entity in the distinguished entity relation 𝑅★ changes. The upper bound provides crucial information to derive the sensitivity of an SQL query. The global sensitivity is the maximum change in the query result on any two neighboring databases.

(T-Join2)

𝐴2 ∉ A 2

∪A 2 ⊢ 𝑆 1 Z 𝑆 2 : Rep𝑘A 1·mmf(𝑆 1 2 .𝐴2 )+𝑘 2 ·mmf(𝑆 1 .𝐴1 ) 𝐴 =𝐴 1

6.8

𝑘 ·mmf(𝑆 1 .𝐴1 )

𝑘 ·mmf(𝑆 1 .𝐴1 )+ 𝑎·𝑘

⊢ 𝑆 1 : Rep𝑘A 1

highlight that this discrepancy may be exacerbated with consecutive joins.

Δ P S,𝑅★ (𝑄) =

(T-Join4)

𝑘 2 ·mmf(𝑆 1 .𝐴1 )

max

(𝐷,𝐷 ′ ) ∈ N ( P S,𝑅★ )

||𝑄 (𝐷) − 𝑄 (𝐷 ′ ))|| 1

where || · || 1 is the 𝐿1 norm2 .

6.9

Figure 6: Action inference rules for key joins, where the join is on a primary-foreign key pair, and general joins, where the join keys may be any attributes.

Plausible Deniability Actions to Sensitivity

As is standard in most of the DP literature, we assume each numerical attribute has a bounded range of possible values, which is commonly linked to the attribute’s datatype in a database management system. We write Range(𝑆.𝐴) = [𝐿, 𝑈 ] to specify the lower

Example 6.3 (Action Calculation). We illustrate that for key joins, the T-Key1 rule derives a tighter bound than the T-Join1 rule. Consider the university database from Figure 1 and suppose an upper bound

2 To be exact, 𝑄 (𝐷 ) is a view with possibly more than one column due to grouping

attributes. We write 𝑄 (𝐷 ) here to mean only the vector of aggregated values. 9

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

If 𝑆 has action Rep𝑘A 1 , the global sensitivity bound for SUM(𝐴) of 𝛾 A 2 (𝑆) depends on whether A 1 and A 2 share any attributes. If they do not, and 𝐴 ∉ A 1 , then the sum does not change and the bound is 0 (S-Sum1). When 𝐴 ∈ A 1 , then each replaced value of 𝐴 at worst changes the sum by |𝐿 − 𝑈 |, so the bound is 𝑘 · |𝐿 − 𝑈 | (S-Sum2). If they do share attributes, then replacing a group changes the sum of a group by at most max(|𝐿|, |𝑈 |). Since two groups change, the bound is 2𝑘 ·max(|𝐿|, |𝑈 |) (S-Sum3). If 𝑆 has action Add𝑎 ×Del𝑑 , then at worst each added or deleted record has a value of max(|𝐿|, |𝑈 |). Therefore, the bound is (𝑎 + 𝑑) · max(|𝐿|, |𝑈 |) (S-Sum4).

Sensitivity Rules for Queries ⊢ 𝑆 : Rep𝑘A 1 A1 ∩ A2 ≠ ∅   (S-Cnt1) Δ̂ 𝛾 CNT(∗) (𝑆) = 2𝑘 A2

⊢ 𝑆 : Rep𝑘A 1 A1 ∩ A2 = ∅   (S-Cnt2) Δ̂ 𝛾 CNT(∗) (𝑆) = 0 A2

⊢ 𝑆 : Add𝑎 × Del𝑑   (S-Cnt3) Δ̂ 𝛾 CNT(∗) (𝑆) = 𝑎 + 𝑑 A

⊢ 𝑆 : Rep𝑘A 1 𝐴 ∉ A1 A1 ∩ A2 = ∅   (S-Sum1) Δ̂ 𝛾 SUM(𝐴) (𝑆) = 0 A2

7

Soundness and Privacy

The next step is to establish the soundness of the inference system, where the formal proof is included in Appendix C. To formalize soundness, we first define an action-induced neighboring relation.

⊢ 𝑆 : Rep𝑘A 1 Range(𝑆.𝐴) = [𝐿, 𝑈 ] 𝐴 ∈ A1 A1 ∩ A2 = ∅   (S-Sum2) Δ̂ 𝛾 SUM(𝐴) (𝑆) = 𝑘 · |𝐿 − 𝑈 | A2

7.1

Action-Induced Neighbors

A plausible deniability action 𝜏 can be thought of as being applied to a view 𝑉 by changing at most the number of specified records in 𝜏. This results in the set of action-induced neighbors.

⊢ 𝑆 : Rep𝑘A 1

Range(𝑆.𝐴) = [𝐿, 𝑈 ] A1 ∩ A2 ≠ ∅   (S-Sum3) SUM(𝐴) Δ̂ 𝛾 A 2 (𝑆) = 2𝑘 · max(|𝐿|, |𝑈 |)

Definition 7.1 (Action-Induced Neighbor). Let 𝑉 ⊂ dom(𝑆) be an instance of expression 𝑆 and 𝜏 be an action. The set of action-induced neighbors of 𝑉 by 𝜏 is the set of views 𝛼 (𝑉 , 𝜏) such that ∀𝑉 ′ ∈ 𝛼 (𝑉 , 𝜏):

⊢ 𝑆 : Add𝑎 × Del𝑑 Range(𝑆.𝐴) = [𝐿, 𝑈 ]   (S-Sum4) Δ̂ 𝛾 SUM(𝐴) (𝑆) = (𝑎 + 𝑑) · max(|𝐿|, |𝑈 |) A2

• If 𝜏 = Add𝑎 × Del𝑑 , then – |𝑉 ′ \ 𝑉 | ≤ 𝑎 and |𝑉 \ 𝑉 ′ | ≤ 𝑑. • If 𝜏 = Rep𝑘A , then – |𝑉 | = |𝑉 ′ | and – 𝑂 = 𝑉 \ 𝑉 ′ and 𝑂 ′ = 𝑉 ′ \ 𝑉 such that |𝑂 | = |𝑂 ′ | ≤ 𝑘 and ∀𝑟 ∈ 𝑂. ∃𝑟 ′ ∈ 𝑂 ′ such that 𝑟 only differs from 𝑟 ′ by the values of attributes in A.

Figure 7: Inference rules to calculate Δ̂(𝑄), an upper bound on the global sensitivity Δ(𝑄). The final aggregation function may be immediately preceded by a grouping operation.

For example, 𝛼 (𝑉 , Add2 × Del3 ) is the set of all views that add at most 2 records to 𝑉 and delete at most 3 records from 𝑉 . The set of action-induced neighbors of a view 𝑉 is used to show that the inference system is sound.

and upper bounds of possible numeric values for 𝑆.𝐴, where 𝐿 ≤ 𝑈 . In certain cases, the range of an attribute can be updated to a tighter bound, which can decrease the sensitivity of SUM. The sensitivity of CNT is dependent on the underlying expression’s action. The sensitivity of SUM is dependent on both the underlying expression’s action and the range of the attribute that is being summed. Additionally, DP4SQL supports the AVG function. The sensitivity of AVG is not computed directly. Instead, a differentially private answer is achieved by the division of a sum query and a counting query to DP4SQL. Similar to PrivateSQL [15], we derive an upper bound on the global sensitivity. Rules to derive this bound for each aggregation function are shown in Figure 7. Here, Δ̂ denotes the upper bound on the global sensitivity. If 𝑆 has action Rep𝑘A 1 , the global sensitivity bound for CNT of 𝛾 A 2 (𝑆) depends on whether A 1 and A 2 share any attributes. If they do, then each replacement at worst decrements the count of one group and increments the count of another in the neighboring view. Since each group changes by at most 1, the bound on the global sensitivity is 2𝑘 (S-Cnt1). Otherwise, each replacement makes no change to the group counts of the neighboring view. Therefore, the bound on the global sensitivity is 0 (S-Cnt2). If 𝑆 has action Add𝑎 × Del𝑑 , then at most 𝑎 records are added and 𝑑 records are deleted in the neighboring view. Therefore, the global sensitivity is at most 𝑎 + 𝑑 (S-Cnt3).

7.2

Soundness

We first prove that for any expression 𝑆 and any pair of neighboring databases (𝐷, 𝐷 ′ ), 𝑆 (𝐷) and 𝑆 (𝐷 ′ ) are action-induced neighbors. Theorem 7.2 (Action Soundness). Let S be a schema and P S,𝑅★ be a privacy policy. For any expression 𝑆 and action 𝜏 such that ⊢ 𝑆 : 𝜏, (𝐷, 𝐷 ′ ) ∈ N (P S,𝑅★ ) =⇒ 𝑆 (𝐷 ′ ) ∈ 𝛼 (𝑆 (𝐷), 𝜏). The sensitivity soundness theorem states that Δ̂ is an upper bound on the global sensitivity Δ. The theorem assumes that the action environment is sound by Theorem 7.2. Theorem 7.3 (Sensitivity Soundness). Let S be a schema and P S,𝑅★ be a privacy policy. For any query 𝑄, Δ P S,𝑅★ (𝑄) ≤ Δ̂ P S,𝑅★ (𝑄). The following soundness theorem is a direct consequence of Theorem 7.3 and the Laplace mechanism. Theorem 7.4. Let 𝐷 be a database with schema S, 𝑄 : D → R𝑛 a SQL query, and P S,𝑅★ a privacy policy. By returning 𝑄 (𝐷) + 10

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

800

(𝛿 1, . . . , 𝛿𝑛 ), where  𝛿 1, . . . , 𝛿𝑛 are i.i.d. random variables drawn from

8

S,𝑅★

(𝑄 )

𝜖

, DP4SQL satisfies (P S,𝑅★ , 𝜖)-differential privacy.

Sensitivity

Lap

Δ̂ P

Case Study

400 200

We begin by examining the university schema S = (R, C) shown in Figure 1 as a case study to illustrate the advantages of supporting flexible privacy policies in DP4SQL. Specifically, we consider a flexible privacy policy, denoted P 𝑅1 1 . This policy is motivated by realistic privacy requirements commonly found in university information systems. In the whole case study, we choose Student (𝑅 1 ) as the distinguished entity relation 𝑅★. As such, we omit the subscript in the notation for clarity hereafter. For P 1 , the entirety of the Student relation (𝑅 1 ) is assumed to be private (i.e., DEL). The number of Faculty (𝑅 2 ) is public, though demographic and financial information is private (i.e., REP {salary,age} ). The total number of scholarships (𝑅 3 ) awarded to students is public, but who they are awarded to and the amount given is private (i.e., REP {uid,amount} ). Information in the course catalog, including the Section relation (𝑅 4 ), is considered entirely public (i.e., PUB). The size of the Enrollment relation is also public, reflecting the fact that students can observe enrollment counts through the course registration system; however, the grade associated with each enrollment is private. P 1 assumes uid to be private, protecting the association between students and their reviews while keeping the review scores themselves public (i.e., REP {uid,grade} ). As no existing DP SQL system can support the flexible privacy policy as stated above, we consider two baseline policies P𝑈 and P 𝐵 , that best match the capabilities of prior work, for comparison. P𝑈 models pure unbounded neighbors as in PrivateSQL [15], where the amount of noise to add to a query is computed by considering the effects of just dropping all records owned by a student (since prior work does not support consistency with public information). This policy has the DEL privacy label for every relation 𝑅 ∈ R. P 𝐵 models pure bounded neighbors in which the amount of noise is computed by considering arbitrary alterations to all records owned by a student. This policy has the REPattr(𝑅) privacy label for every relation 𝑅 ∈ R. Next, we study the following research questions based on several representative SQL queries:

0

Q1

Q2

Baseline Policy U B

Flexible Policy 1

Q3

Q4SUM

Q4CNT

Figure 8: Derived sensitivities for each privacy policy and query. Missing values denote zero sensitivity, and hatching indicates underprotection.

The privacy budget 𝜖 captures the tradeoff between privacy and utility (Definition 5.2). We set 𝜖 = 1 for each SQL query.

8.2

University Queries

We consider the following SQL queries in this case study (the exact queries can be found in Appendix A): 𝑄1 How many sections with less than 10 students is each student enrolled in? 𝑄2 How many times was each review score given in sections with more than 15 students? 𝑄3 How many total scholarships have been awarded to full-time students (i.e., those enrolled in at least 4 sections)? 𝑄4 What is the average review score given to each faculty member teaching NLP? These queries are representative of realistic workloads (e.g., review scores may be used for faculty promotion) and contain a mix of filtering, projection, join, and grouping operators.

8.3

Privacy and Utility Comparison

With DP4SQL, we calculate the sensitivity bound Δ̂ for each query. We focus on sensitivity comparison when possible as it is directly proportional to the injected noise to query answers. Figure 8 shows the sensitivity calculated by DP4SQL for each query and privacy policy combination. We next examine each query in detail.

RQ1 Privacy Improvement. When do existing techniques that can only support baseline policies underprotect the data (i.e., inject less noise than necessary), and how does DP4SQL overcome this limitation? RQ2 Utility Improvement. When do existing techniques that can only support baseline policies overprotect the data (i.e., inject more noise than necessary), and how does DP4SQL overcome this limitation?

8.1

600

60 50 40 30 20 10 0

Q1. This query contains an intermediate grouping with count operation on foreign key 𝑅 5 .sid, followed by a self join on the same key. It also performs a filter on the count followed by a final grouping on 𝑅 5 .uid. The baselines P𝑈 and P 𝐵 both provide overprotection as they treat the grouping attribute 𝑅 5 .sid as private. They both derive large sensitivity due to the self-join in the query, which uses the general but loose join rule. The difference is proportional to the maximum frequency of the join key mmf(𝑅 5 .sid) = 20. In comparison, P 1 treats 𝑅 5 .sid as public, and thus the intermediate grouping with count is also public (see T-Grp4).

Setup

For any relation 𝑅, the primary key 𝑅.𝑃𝐾 is unique by definition (mmf(𝑅.𝑃𝐾) = 1). In the case study, we assume that faculty teach at most 3 sections (mmf(𝑅 4 .fid) = 3). Each section has at most 20 student enrollments (mmf(𝑅 5 .sid) = 20). Each student is enrolled in at most 6 courses (mmf(𝑅 5 .uid) = 6) and can receive at most 2 scholarships (mmf(𝑅 3 .uid) = 2). Lastly, a review is an integer rating where Range(𝑅 5 .review) = [1, 5].

Q2. This query is similar to 𝑄1 except the final grouping on 𝑅 5 .review instead of 𝑅 5 .uid. Since P 1 assumes reviews are public, DP4SQL it is able to return the answer to the query without injecting noise (i.e., a sensitivity of zero). This is intuitively correct as releasing statistical enrollment data from 𝑄2 does not reveal grade and review attributes. 11

1.2

Database Entities, Relationships, and Characteristics The components of the TPC-H database are defined to consist of eight separate and individual tables (the Base Tables). The relationships between columns of these tables Kifer, are illustrated in Figure The TPC-H Schema.Zhang Andrew Cascio, KinChin Tong, Daniel Zeyu Ding,2: and Danfeng Figure 2: The TPC-H Schema

Q3. This simple query illustrates why pure unbounded neighbors (P𝑈 ) is insufficient to provide proper differential privacy. Consider the first step of an evaluation of 𝑄3: (1) Counting the number of enrollments for each student with a grouping count on the private attribute 𝑅 5 .uid. Since the number of enrollments is public, replacing the uid of a student will change the count of two groups in a counterfactual world, thus increasing the stability by a factor of 2. This is followed by the second step (2), a subsequent join with 𝑅 3 on private foreign key uid, which increases the stability proportional to mmf(𝑅 3 .uid). Since P𝑈 assumes at most one entity can be deleted, it under-approximates the stability in step (1); intuitively, replacing the uid of a student is the same as deleting one student record and adding another student record, which results in a a factor of 2 rather than 1 in stability calculation. The under-approximation with policy P𝑈 results in a failure to properly track the overall stability and leading to the incorrect sensitivity displayed in Figure 8.

PART (P_) SF*200,000

PARTSUPP (PS_) SF*800,000

LINEITEM (L_) SF*6,000,000

ORDERS (O_) SF*1,500,000

PARTKEY

PARTKEY

ORDERKEY

ORDERKEY

NAME

SUPPKEY

PARTKEY

CUSTKEY

MFGR

AVAILQTY

SUPPKEY

ORDERSTATUS

BRAND

SUPPLYCOST

LINENUMBER

TOTALPRICE

TYPE

COMMENT

QUANTITY

ORDERDATE

EXTENDEDPRICE

ORDERPRIORITY

SIZE CONTAINER RETAILPRICE

CUSTOMER (C_) SF*150,000 CUSTKEY NAME

COMMENT

ADDRESS SUPPLIER (S_) SF*10,000

NATIONKEY

LINESTATUS

SHIPPRIORITY COMMENT

SHIPDATE COMMITDATE RECEIPTDATE

MKTSEGMENT

ADDRESS

SHIPINSTRUCT

NATIONKEY PHONE

COMMENT SHIPMODE NATION (N_) 25

ACCTBAL COMMENT

NAME REGIONKEY COMMENT

COMMENT REGION (R_) 5 REGIONKEY NAME COMMENT

Legend: 

The parentheses following each table name contain the prefix of the column names for that table;

Figure 9:TheThe TPC-H Schema. The arrows point in the direc arrows point in the direction of the one-to-many relationships between tables; tion of data ownership. number eachof rows) table The number/formula below eachThe table name represents the below cardinality (number of thename table. Some are factored by SF, the Scale Factor, to obtain the chosen database size. The cardinality for the LINEITEM is the cardinality by the TPC-H data generation tool table is approximateoutput (see Clause 4.2.5). (possibly multiplied by a scale factor SF) for that table. TPC BenchmarkTM H Standard Specification Revision 2.17.1

Page 13

We consider two flexible privacy policies; they choose C and S as the distinguished entity relation 𝑅★, and are denoted as P C and P S respectively. In both policies, geographic data about nations (N) and regions (R) is publicly available, as well as part (P) information (i.e., PUB). The number of suppliers (S) using the platform are known, but not their financial or demographic information (i.e., REPattr(S) ). The number of parts each supplier sells (PS) is also public (i.e., REPattr(PS) ). Customer (C) information, including the number of customers, is highly sensitive and entirely private (i.e., DEL). We assume the platform releases an aggregate number of orders (O) placed by all customers (i.e., REPattr(O) ). However, lineitem (L) data, which contains information about each item in an order, is entirely private (i.e., DEL). For comparison, we consider two unbounded baseline policies (i.e., P𝑈C and P𝑈S ) and Tumult Analytics [16], a Python package that builds upon the design principles of PrivateSQL. Tumult Analytics supports two privacy policies, which we call TumultC and TumultS , that protect the existence of customers and suppliers respectively.

Key Takeaways

RQ1 Existing techniques that are limited to supporting only the unbounded policy P𝑈 may introduce insufficient noise, resulting in underprotection. This occurs because they lack the expressiveness needed to account for public table sizes, as demonstrated by 𝑄3. Flexible privacy policies overcome this issue with privacy labels that support a mix of public and private information, including table sizes. RQ2 Existing techniques that are limited to supporting baseline policies only (e.g., P𝑈 , P 𝐵 ) may introduce excessive noise, resulting in overprotection. This occurs because they conservatively treat all attributes as private. In comparison, DP4SQL can differentiate between private and nonprivate attributes, thereby deriving tight sensitivity bounds on query answers. This improvement is demonstrated by the majority of the SQL queries in our case study.

9

RETURNFLAG

CLERK

ACCTBAL

NAME

NATIONKEY

8.4

TAX

PHONE

SUPPKEY

Q4. This query is the most complex, containing two joins, a filter, and a final grouping. DP4SQL supports 𝑄4 by answering two group-by aggregate subqueries. Let 𝑄4SUM and 𝑄4CNT be subqueries identical to 𝑄4 up to replacing the AVG aggregation with SUM and CNT respectively. Then, answering 𝑄4 amounts to the quotient 𝑄4SUM /𝑄4CNT of differentially private answers. The average review score is public information, so DP4SQL correctly derives that releasing the query answer does not reveal any private data: the query has a sensitivity of zero. Unsurprisingly, however, both baseline policies output high sensitivities for 𝑄4SUM since they treat review scores as private. For 𝑄4CNT , they both output high sensitivity since they treat all attributes in Enrollment as private. Notably, P 1 has zero sensitivity for both subqueries, and therefore would need to inject zero noise into the true query answer.

DISCOUNT

9.1

Setup

We generate a database using the TPC-H data generation tool with the default scale factor of 1. This results in 8.7M total records in the database. To compute the upper bounds on maximum frequency, we run the query SELECT COUNT(key) AS count FROM table GROUP BY key ORDER BY count DESC LIMIT 1 for each foreign key. Since TPC-H queries only perform key joins, upper bounds for non-key attributes are not required. We use a standard privacy budget of 𝜖 = 1 for each query.

TPC-H Evaluation

We evaluate DP4SQL on TPC-H [5], an industry standard benchmark. The benchmark dataset consists of eight relations: Region (R), Nation (N), Part (P), Supplier (S), Partsupp (PS), Customer (C), Order (O), and Lineitem (L). These relations comprise a complex business environment (e.g., an online shopping platform), whose schema as a data ownership graph is shown in Figure 9. 12

Sensitivity

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

300 250 200 150 100 50 0

U

C C

Q13 Customer Distribution: Outputs a histogram of how many customers have 1 order, 2 orders, 3 orders, etc. It contains one join on Customer and Orders, as well as an intermediate count aggregation. Q16 Parts/Supplier Relationship: Lists the number of suppliers that can satisfy a particular set of part requirements. The counts are grouped by the attributes that make up the requirements. It has two joins: one on Part and Partsupp, followed by another on Supplier.

U

S S

104 103

Q1

Q4

Q13

Q1

Q4

Q16

Relative Error

Figure 10: Sensitivities for TPC-H queries. Hatching indicates that the policy underprotects the data.

100 10 1 10 2 10 3 10 4 10 5

Q1 with C Policies

10 2 10 3

Relative Error

U

TumultS

C

C

Q4 with C Policies

U

S

S

Q4 with S Policies 101

10 1 10 2

100

Utility. We now compare the utility of all privacy policies with Tumult Analytics. Given a policy P and a query 𝑄, we measure utility with the relative error defined as RelError P (𝑄) = |𝑦 − ˆ 𝑦|/max(1, 𝑦) where 𝑦 is the true answer and 𝑦ˆ is the noisy answer output by a DP SQL system. For each query 𝑄 and each privacy policy P, we sample the relative error RelError P (𝑄) 50 times. The boxplots are displayed in Figure 11. The errors are similar across the board for Q1 and Q4, which is consistent with the results from sensitivity analysis. TumultC overprotects the data for Q13 with a median error of 19.6%, about 12 times larger than that of P C . TumultC exhibits minimal variability across all samples because deterministic contribution bounding clamps group-by inputs before aggregation, fixing query sensitivity and yielding identical noise distributions across samples. As before, P𝑈C underprotects the data because it incorrectly models the number of platform-wide orders as private. Lastly, only P S is able to return the true answer to public query ˆ L), the errors outQ16. Due to the high maximum ownership ⊗(S, put by TumultS and P𝑈S are too high for practical use, performing worse than a model that always outputs 0. These results demonstrate that incorrect privacy modeling (e.g., incorrectly assuming the privacy levels of table sizes and/or attributes) can significantly affect noise calculations by resulting in adding too much or too little noise depending on the query.

10 3 10 4 100

Relative Error

Q1 with S Policies

10 1

TumultC 100

100

Sensitivity. Since Tumult Analytics does not disclose the computed sensitivity, we only show the calculated sensitivity for P𝑈C , P𝑈S , P C , and P S in Figure 10. All policies exhibit comparable sensitivity for Q1, as they all assume the grouping attributes to be private. A similar observation holds for Q4, where all policies treat lineitems (L) as private. Queries Q13 and Q16 are more interesting. Since Q13 does not access any supplier-owned data, it is evaluated exclusively under the C policies. P𝑈C underprotects the data because the privacy policy incorrectly models the total number of orders on the platform as private. The reasoning is similar to that of 𝑄3 in Section 8. Conversely, Q16 does not involve customer data and is thus evaluated only under the S policies. Since Q16 returns public information, DP4SQL is able to return the query answer without injecting noise (i.e., a sensitivity of zero). In contrast, P𝑈S overprotects data as it assumes the number of suppliers is private.

TumultC

10 1

U

C

C

Q13 with C Policies

Violates -DP

U

S

S

Q16 with S Policies 101

10 1

100

10 2

10 1 10 2

10 3 10 4

TumultS

No Error

10 3 TumultC

U

C

C

TumultS

U

S

S

Figure 11: Relative error of DP4SQL and Tumult Analytics for TPC-H queries. C and R policies treat Customer and Supplier relations as the entity relations respectively. The dashed line denotes the error for a system that always outputs 0.

9.2

Comparison with Tumult Analytics

Following existing work [13, 15], we evaluate on the TPC-H queries that have count aggregations: Q1, Q4, Q13, and Q16. Q1 Pricing Summary Report: Outputs the number of lineitems that were shipped before a given date, grouped by return status. It contains no joins. Q4 Order Priority Checking: Lists the number of orders for which at least one lineitem was received late by its customer. The counts are grouped by the priority of the order. It contains one join on its Orders and Lineitem tables.

10

Conclusion and Future Work

We introduce DP4SQL, a flexible DP SQL framework that enables data administrators to meet a mix of complicated privacy needs. Paired with a low-level plausible-deniability-action framework, DP4SQL reasons soundly about the stability of relational algebra 13

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

underlying SQL queries and computes a sufficient amount of noise to add to query answers. For future work, we plan to investigate a high-level declarative policy, such as one that can directly specify privacy requirements for complex views of a database (e.g., protect all grade/review interactions between any faculty/student pair). An extension to DP4SQL would ingest the specification and produce appropriate privacy policies. A second direction is improving system utility with utilityguided query rewriting. While our work avoids semantics-altering rewrites, some techniques, such as truncation and dropping records, can avoid undesirably large global sensitivities when used properly.

the 2014 ACM SIGSAC Conference on Computer and Communications Security (Scottsdale, Arizona, USA) (CCS ’14). ACM, New York, NY, USA, 1054–1067. [12] Google. [n. d.]. Tensorflow Privacy Github. https://github.com/tensorflow/ privacy. [13] Noah Johnson, Joseph P. Near, and Dawn Song. 2018. Towards practical differential privacy for SQL queries. Proc. VLDB Endow. 11, 5 (Jan. 2018), 526–539. doi:10.1145/3187009.3177733 [14] Noah M. Johnson, Joseph P. Near, Joseph M. Hellerstein, and Dawn Song. 2018. Chorus: Differential Privacy via Query Rewriting. CoRR abs/1809.07750 (2018). arXiv:1809.07750 http://arxiv.org/abs/1809.07750 [15] Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. 2019. PrivateSQL: a differentially private SQL query engine. Proc. VLDB Endow. 12, 11 (July 2019), 1371–1384. doi:10.14778/3342263.3342274 [16] Tumult Labs. 2022. Tumult Analytics. https://tmlt.dev [17] Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. 2008. Privacy: Theory meets Practice on the Map. In 2008 IEEE 24th International Conference on Data Engineering. 277–286. doi:10.1109/ICDE.2008. 4497436 [18] Frank D. McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data (Providence, Rhode Island, USA) (SIGMOD ’09). Association for Computing Machinery, New York, NY, USA, 19–30. doi:10.1145/1559845.1559850 [19] Solomon Messing, Bogdan State, Chaya Nayak, Gary King, and Nate Persily. 2018. URLs Dataset for RFP.pdf. In Facebook URL Shares. Harvard Dataverse. doi:10.7910/DVN/EIAACS/PMQG9X [20] Ilya Mironov. 2017. Rényi Differential Privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017. 263–275. [21] Prashanth Mohan, Abhradeep Thakurta, Elaine Shi, Dawn Song, and David Culler. 2012. GUPT: Privacy Preserving Data Analysis Made Easy. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (Scottsdale, Arizona, USA) (SIGMOD ’12). ACM, New York, NY, USA, 349–360. [22] Shangfu Peng, Yin Yang, Zhenjie Zhang, Marianne Winslett, and Yong Yu. 2013. Query optimization for differentially private data management systems. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 1093–1104. doi:10. 1109/ICDE.2013.6544900 [23] Davide Proserpio, Sharon Goldberg, and Frank McSherry. 2014. Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-private Analysis of Weighted Datasets. Proc. VLDB Endow. 7, 8 (April 2014), 637–648. doi:10.14778/2732296.2732300 [24] Indrajit Roy, Srinath T. V. Setty, Ann Kilzer, Vitaly Shmatikov, and Emmett Witchel. 2010. Airavat: Security and Privacy for MapReduce. In Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation (San Jose, California) (NSDI’10). USENIX Association, Berkeley, CA, USA, 20–20. [25] Apple Differential Privacy Team. 2017. Learning with Privacy at Scale. Apple Machine Learning Journal 1, 8 (2017). [26] The OpenDP Team. 2020. The OpenDP White Paper. https://projects.iq.harvard. edu/files/opendp/files/opendp_white_paper_11may2020.pdf [27] Michael Carl Tschantz, Shayak Sen, and Anupam Datta. 2020. SoK: Differential privacy as a causal property. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 354–371. [28] Larry Wasserman and Shuheng Zhou. 2010. A statistical framework for differential privacy. J. Amer. Statist. Assoc. 105, 489 (2010), 375–389. [29] Royce J. Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. 2019. Differentially Private SQL with Bounded User Contribution. CoRR abs/1909.01917 (2019). arXiv:1909.01917 http://arxiv.org/abs/1909.01917 [30] Jianzhe Yu, Wei Dong, Juanru Fang, Dajun Sun, and Ke Yi. 2024. DOP-SQL: A General-Purpose, High-Utility, and Extensible Private SQL System. Proc. VLDB Endow. 17, 12 (Aug. 2024), 4385–4388. doi:10.14778/3685800.3685881

Ethical Considerations All data used in the evaluation of this paper is synthetically generated, publicly available, and is used for demonstration purposes only. As such, there are no stakeholders who are at risk due to the public dissemination of the results produced by DP4SQL in this paper. In a realistic scenario, data processed by DP4SQL may contain sensitive information owned by real stakeholders. The results produced by DP4SQL are 𝜖-differentially private. Stakeholders should make an informed decision about whether differential privacy is right for their use case before deciding to publicly release any results generated by DP4SQL.

References [1] John M. Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. forthcoming. Preprint https://www.census.gov/library/workingpapers/2022/adrm/CED-WP-2022-002.html. The 2020 Census Disclosure Avoidance System TopDown Algorithm. Harvard Data Science Review (forthcoming. Preprint https://www.census.gov/library/working-papers/2022/adrm/CED-WP2022-002.html). [2] Skye Berghel, Philip Bohannon, Damien Desfontaines, Charles Estes, Sam Haney, Luke Hartman, Michael Hay, Ashwin Machanavajjhala, Tom Magerlein, Gerome Miklau, Amritha Pai, William Sexton, and Ruchit Shrestha. 2022. Tumult Analytics: a robust, easy-to-use, scalable, and expressive framework for differential privacy. arXiv preprint arXiv:2212.04133 (2022). [3] Mark Bun and Thomas Steinke. 2016. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985. [4] Lei Cao, Dongqing Xiao, Yizhou Yan, Samuel Madden, and Guoliang Li. 2021. ATLANTIC: making database differentially private and faster with accuracy guarantee. In Proceedings of the VLDB Endowment. [5] T.P.P. Council. 2014. TPC Benchmark H. https://www.tpc.org/tpc_documents_ current_versions/pdf/tpc-h_v2.17.1.pdf [6] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS’17). Curran Associates Inc., USA, 3574–3583. http://dl.acm.org/citation.cfm?id=3294996. 3295115 [7] Jinshuo Dong, Aaron Roth, and Weijie J. Su. 2022. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 84, 1 (2022), 3–37. arXiv:https://rss.onlinelibrary.wiley.com/doi/pdf/10.1111/rssb.12454 doi:10.1111/rssb.12454 [8] Wei Dong, Juanru Fang, Ke Yi, Yuchao Tao, and Ashwin Machanavajjhala. 2022. R2t: Instance-optimal truncation for differentially private query evaluation with foreign keys. In Proceedings of the 2022 International Conference on Management of Data. 759–772. [9] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography (New York, NY) (TCC’06). Springer-Verlag, Berlin, Heidelberg, 265–284. doi:10.1007/11681878_14 [10] Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Theoretical Computer Science 9, 3–4 (2014), 211–407. [11] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proceedings of 14

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

C.1

mmf(𝜎 𝜑 (𝑆).𝐴) = mmf(𝑆.𝐴) mmf(𝜋 A (𝑆).𝐴) = mmf(𝑆.𝐴) mmf(𝛾 A (𝑆).𝐴) = mmf(𝑆.𝐴) ( inf if 𝐴 = CNT CNT(∗) mmf(𝛾 A (𝑆).𝐴) = mmf(𝑆.𝐴) otherwise ( mmf(𝑆 1 .𝐴) · mmf(𝑆 2 .𝐴2 ) mmf((𝑆 1 Z 𝑆 2 ).𝐴) = 𝐴1 =𝐴2 mmf(𝑆 2 .𝐴) · mmf(𝑆 1 .𝐴1 )

Supporting Lemmas

We first prove two supporting lemmas. The first is Lemma 6.2 (Correctness of Maximum Ownership): Proof. By strong induction on foreign keys. Base case: Each record only owns itself in its own relation. Therefore, for all 𝑟 1 ∈ 𝑇 1 , ˆ 1, 𝑅 1 ) = 1. |⊗(𝑇 1,𝑇 1, 𝑟 1 )| = 1 ≤ ⊗(𝑅

if 𝐴 ∈ attr(𝑆 1 ) otherwise

Inductive hypothesis: For all 𝑅 ′ with associated table𝑇 ′ ⊂ dom(𝑅 ′ ) fk such that 𝑅 2 → 𝑅 ′ , assume for all 𝑟 1 ∈ 𝑇 1 ˆ 1, 𝑅 ′ ). |⊗(𝑇 1,𝑇 ′, 𝑟 1 )| ≤ ⊗(𝑅

Figure 12: Rules for maximum frequency upper bound.

A

fk Inductive step: For each 𝑅 ′ such that 𝑅 2 → 𝑅 ′ , |⊗(𝑇 1,𝑇 ′, 𝑟 1 )| ≤ fk ˆ⊗(𝑅 1, 𝑅 ′ ) by the inductive hypothesis. For each 𝑅 2 .𝐹𝐾 𝑖 → 𝑅 ′ .𝑃𝐾, at ˆ 1, 𝑅 ′ ) · mmf(𝑅 2 .𝐹𝐾 𝑖 ) records are owned by 𝑟 1 . Therefore, most ⊗(𝑅 for all 𝑟 1 ∈ 𝑇 1 , ∑︁ ˆ 1, 𝑅 ′ ) |⊗(𝑇 1,𝑇 2, 𝑟 1 )| ≤ mmf(𝑅 2 .𝐹𝐾 𝑖 ) · ⊗(𝑅 fk ′ 𝑅 2 .𝐹 𝐾 𝑖 → 𝑅 .𝑃𝐾 ˆ = ⊗(𝑅 1, 𝑅 2 ).

Case Study SQL Queries

The following SQL queries were used in Section 8. 𝑄1 SELECT COUNT(*) FROM (SELECT e1.sid, COUNT(*) AS enroll_count FROM enrollment e1 GROUP BY e1.sid) INNER JOIN enrollment e2 ON e1.sid = e2.sid WHERE enroll_count < 10 GROUP BY e2.uid 𝑄2 SELECT COUNT(*) FROM (SELECT e1.sid, COUNT(*) AS enroll_count FROM enrollment e1 GROUP BY e1.sid) INNER JOIN enrollment e2 ON e1.sid = e2.sid WHERE enroll_count > 15 GROUP BY e2.review 𝑄3 SELECT COUNT(*) FROM (SELECT e.uid, COUNT(*) AS enroll_count FROM enrollment e GROUP BY e.uid) INNER JOIN scholarship s ON e.uid = s.uid WHERE enroll_count > 4 𝑄4 SELECT AVG(e.review) FROM section s INNER JOIN enrollment e ON s.sid = e.sid GROUP BY s.fid DP4SQL separates 𝑄4 into the following subqueries for sensitivity calculation. 𝑄4SUM SELECT SUM(e.review) FROM section s INNER JOIN enrollment e ON s.sid = e.sid GROUP BY s.fid 𝑄4CNT SELECT COUNT(e.review) FROM section s INNER JOIN enrollment e ON s.sid = e.sid GROUP BY s.fid

B

□ The second is Lemma B.1 (Correctness of mmf): Proof. By induction on the structure of 𝑆. Case 𝑅. By assumption. Case 𝜎 𝜑 (𝑆). Selection does not change any records. Therefore, the result follows from the inductive hypothesis. Case 𝜋 A (𝑆). Projection does not change any records. Therefore the result follows from the inductive hypothesis. Case 𝛾 A (𝑆). Grouping does not add any records. Therefore, the result follows from the inductive hypothesis. } Case 𝛾 {CNT(∗) (𝑆). This transformation adds a CNT attribute for A each group. The maximum frequency of CNT is unbounded since it is at most the number of groups, which is unbounded. For the grouping attributes, the result follows from the inductive hypothesis since grouping does not add records. Case 𝑆 1 Z 𝑆 2 . Suppose 𝐴 ∈ attr(𝑆 1 ). By the inductive hypoth-

Maximum Frequency Upper Bound for Transformations

𝐴1 =𝐴2

esis, mmf(𝑆 1 .𝐴1 ), mmf(𝑆 1 .𝐴), and mmf(𝑆 2 .𝐴2 ) are upper bounds on the maximum frequencies of 𝑆 1 .𝐴1, 𝑆 1 .𝐴, and 𝑆 2 .𝐴2 respectfully. In the worst case, every record with the most frequent value of 𝑆 1 .𝐴 matches with every record with the most frequent value of 𝑆 2 .𝐴2 . This is at most mmf(𝑆 1 .𝐴) · mmf(𝑆 2 .𝐴2 ) records, which is precisely the definition. The case where 𝐴 ∈ attr(𝑆 2 ) is symmetric. □

Recall the maximum frequency upper bound for each attribute in each base relation 𝑅 ∈ R (Section 6.2). Calculating the plausible deniability action for 𝑆 1 Z 𝑆 2 in the general case requires the 𝐴1 =𝐴2

maximum frequencies of both 𝐴1 and 𝐴2 . Figure 12 presents the rules for soundly calculating the maximum frequency upper bound for any view produced by a transformation. The following lemma states that mmf is indeed an upper bound on the maximum frequency for any attribute.

C.2

Lemma B.1 (Correctness of mmf). Let S = (R, C) be a schema and 𝐷 ∈ dom(S) any database. For all relations 𝑅 ∈ R and corresponding instances 𝑇 ∈ 𝐷, assume mf(𝑇 .𝐴) ≤ mmf(𝑅.𝐴) for all 𝐴 ∈ attr(𝑅). Then, mf(𝑆 (𝐷).𝐴) ≤ mmf(𝑆.𝐴). That is, the frequency of the most frequent value of 𝑆 (𝐷).𝐴 is at most mmf(𝑆.𝐴).

C

Soundness Theorems

We now prove the two soundness theorems. The first is Theorem 7.2 (Action Soundness): Proof. Assume (𝐷, 𝐷 ′ ) ∈ N (P S,𝑅★ ). We proceed by induction on the base relation inference rules in Figure 2: Case E-Del. By Definition 5.1, 𝑇 𝑅★ and 𝑇 𝑅′ ★ differ by exactly one record and 𝑇 𝑅′ ★ \ 𝑇 𝑅★ = ∅. Therefore, 𝑇 𝑅′ ★ ∈ 𝛼 (𝑇 𝑅★ , Add0 × Del1 ). Case E-Pub. By Definition 5.1, 𝑇 𝑅★ = 𝑇 𝑅′ ★ . Therefore, 𝑇 𝑅′ ★ ∈ 𝛼 (𝑇 𝑅★ , Rep0∅ ).

Soundness Proofs

We prove the main results of Section 7. 15

Andrew Cascio, KinChin Tong, Daniel Kifer, Zeyu Ding, and Danfeng Zhang

Case E-Rep. By Definition 5.1, 𝑇 𝑅★ and 𝑇 𝑅′ ★ are the same size and differ by the values of A in exactly one record. Therefore, 𝑇 𝑅′ ★ ∈ 𝛼 (𝑇 𝑅★ , Rep1A ). Case F-Pub. By Definition 5.1,𝑇 = 𝑇 ′ . Therefore,𝑇 ′ ∈ 𝛼 (𝑇 , Rep0∅ ). Case F-Del. By Definition 5.1, 𝑇 ′ deletes ⊗(𝑇 𝑅★ ,𝑇 , 𝑒) ⊆ 𝑇 . ˆ ★, 𝑅) records. Therefore, 𝑇 ′ ∈ By Lemma 6.2, this is at most ⊗(𝑅 𝛼 (𝑇 , Add0 × Del⊗ˆ (𝑅★,𝑅) ). Case F-Rep. By Definition 5.1, 𝑇 ′ replaces the values in A of ˆ ★, 𝑅) records. ⊗(𝑇 𝑅★ ,𝑇 , 𝑒) ⊆ 𝑇 . By Lemma 6.2, this is at most ⊗(𝑅 ′ Since 𝐷 satisfies C, A must contain all foreign keys that map to a private primary key. Therefore, 𝑇 ′ ∈ 𝛼 (𝑇 , Rep⊗A ). ˆ (𝑅★,𝑅)

Finally with the join transformation inference rules in Figure 6: Case T-Key1. By the inductive hypothesis, ⊢ 𝑅 : Add0 × Del𝑑 . By fk assumption, 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾. By Definition 5.1, all changed records from 𝑆 match with deleted record from 𝑅. Since 𝑅 may delete more records due to other foreign keys, the number of total deleted ˆ ★, 𝑅). So, records is upper bounded by the maximum ownership ⊗(𝑅 ˆ ★, 𝑅) records are deleted in (𝑅 Z 𝑆)(𝐷 ′ ). Therefore, at most ⊗(𝑅 𝐹 𝐾 𝑆 =𝑃𝐾

(𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

𝑆)(𝐷 ′ ) ∈ 𝛼 ((𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

𝑆)(𝐷), Add0 × Del𝑑 ).

Case T-Key2. By the inductive hypothesis, ⊢ 𝑅 : Rep𝑘A . By asfk sumption, 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾 and private(𝑆.𝑃𝐾). By Definition 5.1, all changed records from 𝑆 match with replaced records from 𝑅. So, at most 𝑘 records are replaced in (𝑅 Z 𝑆)(𝐷 ′ ). Each replaced

Continuing with the unary transformation inference rules in Figure 4:

𝐴1 =𝐴2

Case T-Sel1. By the inductive hypothesis, ⊢ 𝑆 : Add𝑎 × Del𝑑 . In the worst case, added and deleted records are not filtered. Therefore, 𝜎 𝜑 (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝜎 𝜑 (𝑆 (𝐷)), Add𝑎 × Del𝑑 ). Case T-Sel2. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A . By assumption, the predicate 𝜑 does not contain any attribute in A, so replacements do not affect filtering. Therefore, 𝜎 𝜑 (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝜎 𝜑 (𝑆 (𝐷)), Rep𝑘A ). Case T-Sel3. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A . By assumption, the predicate 𝜑 contains some attribute in A. Each replaced record results in an added, deleted, or replaced record after filtering. Therefore, 𝜎 𝜑 (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝜎 𝜑 (𝑆 (𝐷)), Add𝑘 × Del𝑘 ). Case T-Prj1. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . Projection does not change the number of records and, by assumption, A 1 ∩ A 2 ≠ ∅. Therefore, 𝜋 A 2 (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝜋 A 2 (𝑆 (𝐷)), Rep𝑘A 1 ∩A 2 ). Case T-Prj2. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . By assumption, A 1 ∩ A 2 = ∅, so the projection is completely public. Therefore, 𝜋 A 2 (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝜋 A 2 (𝑆 (𝐷)), Rep0∅ ). Case T-Prj3. By the inductive hypothesis, ⊢ 𝑆 : Add𝑎 × Del𝑑 . Again, projection does not change the number of records. Therefore, 𝜋 A 1 (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝜋 A 1 (𝑆 (𝐷)), Add𝑎 × Del𝑑 ). Case T-Grp1. By assumption, the grouping bins are public (so the size is constant). Grouping without aggregation simply returns the set of public grouping bins. Therefore, 𝛾 A (𝑆 (𝐷 ′ )) ∈ 𝛼 (𝛾 A (𝑆 (𝐷)), Rep0∅ ). Case T-Grp2. By the inductive hypothesis, ⊢ 𝑆 : Add𝑎 × Del𝑑 . By assumption, the grouping bins are public (so the size is constant). Each added record may increment a group’s count, and each deleted record may decrement a group’s count. Therefore, 𝛾 {CNT} (𝑆 (𝐷 ′ )) ∈ A

record may replace attributes in A as well as attr(𝑆 2 ) due to the replacement of 𝐹𝐾 𝑆 . Therefore, (𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

𝑆)(𝐷 ′ ) ∈ 𝛼 ((𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

𝑆)(𝐷), Rep𝑘A∪attr(𝑆 ) ).

Case T-Key3. By the inductive hypothesis, ⊢ 𝑅 : Rep𝑘A 1 and 1

fk ⊢ 𝑆 : Rep𝑘A 2 . By assumption, 𝑅.𝐹𝐾 𝑆 → 𝑆.𝑃𝐾. By Definition 5.1, all 2 changed records from 𝑆 match with replaced records from 𝑅. The size of the join does not change since the join key 𝑆.𝑃𝐾 is public, so at most 𝑘 1 records are replaced in (𝑅 Z 𝑆)(𝐷 ′ ). Therefore,

𝐹 𝐾 𝑆 =𝑃𝐾

(𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

′

𝑆)(𝐷 ) ∈ 𝛼 ((𝑅

Z

𝐹 𝐾 𝑆 =𝑃𝐾

𝑆)(𝐷), Rep𝑘A 1 ∪A 2 ). 1

Case T-Join1. By the inductive hypothesis, ⊢ 𝑆 1 : Add𝑎1 × Del𝑑1 and ⊢ 𝑆 2 : Add𝑎2 × Del𝑑2 . There are 5 sources of changed records: (1) A record from 𝑆 1 (𝐷) may match a record added to 𝑆 2 (𝐷 ′ ), (2) a record from 𝑆 1 (𝐷) may match a record deleted from 𝑆 2 (𝐷 ′ ), (3) a record from 𝑆 2 (𝐷) may match a record added to 𝑆 1 (𝐷 ′ ), (4) a record from 𝑆 2 (𝐷) may match a record deleted from 𝑆 1 (𝐷 ′ ), and (5) a record added to 𝑆 1 (𝐷 ′ ) may match a record added to 𝑆 2 (𝐷 ′ ). Considering each source of changed records: (1) In the worst case, each record added to 𝑆 2 (𝐷 ′ ) matches with the most popular join key in 𝑆 1 (𝐷), which is at most mmf(𝑆 1 .𝐴1 ) (Lemma B.1). So, at most 𝑎 2 · mmf(𝑆 1 .𝐴1 ) records are added. (2) By similar reasoning, at most 𝑑 2 · mmf(𝑆 1 .𝐴1 ) records are deleted. (3) By symmetric reasoning, at most 𝑎 1 · mmf(𝑆 2 .𝐴2 ) additional records are added and (4) at most 𝑑 1 · mmf(𝑆 2 .𝐴2 ) additional records are deleted. (5) At most 𝑎 1 · 𝑎 2 additional records are added since each pair of added records may match. The total number of added and deleted records is exactly the action:

{CNT} 𝛼 (𝛾 {CNT} (𝑆 (𝐷)), Rep𝑎+𝑑 ). A Case T-Grp3. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . By assumption, the grouping bins are public (so the size is constant), and grouping attributes can be replaced. Each replaced record may increment one group’s count and decrement another group’s count. {CNT} {CNT} ′ Therefore, 𝛾 {CNT} ). A 2 (𝑆 (𝐷 )) ∈ 𝛼 (𝛾 A 2 (𝑆 (𝐷)), Rep2𝑘

Add𝑎1 ·mmf(𝑆 2 .𝐴2 )+ × Del𝑑1 ·mmf(𝑆 2 .𝐴2 )+ = 𝜏 𝑎 2 ·mmf(𝑆 1 .𝐴1 )+ 𝑑 2 ·mmf(𝑆 1 .𝐴1 ) 𝑎 1 ·𝑎 2 Therefore, (𝑆 1 Z 𝑆 2 )(𝐷 ′ ) ∈ 𝛼 ((𝑆 1 Z 𝑆 2 )(𝐷), 𝜏). 𝐴1 =𝐴2 𝐴1 =𝐴2

Case T-Join2. By the inductive hypothesis, ⊢ 𝑆 1 : Add𝑎 × Del𝑑 and ⊢ 𝑆 2 : Rep𝑘A . There are 4 sources of changed records: (1) A record from 𝑆 1 (𝐷) may match a record replaced from 𝑆 2 (𝐷 ′ ), (2) a record from 𝑆 2 (𝐷) may match a record added to 𝑆 1 (𝐷 ′ ), (3) a record from 𝑆 2 (𝐷) may match a record deleted from 𝑆 1 (𝐷 ′ ), and (4) a record replaced from 𝑆 2 (𝐷 ′ ) may match a record added to 𝑆 1 (𝐷 ′ ). Considering each source of changed records: (1) In the worst case, each record from 𝑆 2 (𝐷 ′ ) after replacement matches with the most

Case T-Grp4. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . By assumption, the grouping bins are public (so the size is constant), and grouping attributes cannot be replaced, so the output is public. {CNT} ′ ∅ Therefore, 𝛾 {CNT} A 2 (𝑆 (𝐷 )) ∈ 𝛼 (𝛾 A 2 (𝑆 (𝐷)), Rep0 ).

16

DP4SQL : Differentially Private SQL with Flexible Privacy Policies

popular join key in 𝑆 1 (𝐷) (before and after replacement), which is at most mmf(𝑆 1 .𝐴1 ) (Lemma B.1). So, at most 𝑘 · mmf(𝑆 1 .𝐴1 ) records are added and deleted. (2) By similar reasoning to T-Join1, at most 𝑎 · mmf(𝑆 2 .𝐴2 ) records are added and (3) at most 𝑑 · mmf(𝑆 2 .𝐴2 ) records are deleted. (4) At most 𝑎 · 𝑘 additional records are added since each pair of added and replaced records may match. The sum of added and deleted records is exactly the action:

1 in its initial group, and increases the count by 1 in its new group. Therefore, the global sensitivity Δ is at most 2𝑘. Case S-Cnt2. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . Since A 1 ∩ A 2 = ∅, the grouping attributes A 2 cannot be replaced. Therefore, the count is unchanged in any neighbor, and the global sensitivity Δ is at most 0. Case S-Cnt3. By the inductive hypothesis, ⊢ 𝑆 : Add𝑎 × Del𝑑 . In the worst case, each added and deleted record is in a different group. Therefore, the global sensitivity Δ is at most 𝑎 + 𝑑. Case S-Sum1. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . By assumption, 𝐴 ∉ A 1 and A 1 ∩ A 2 = ∅, meaning neither the summed attribute nor the grouping attributes can be changed. Therefore, the global sensitivity Δ is at most 0. Case S-Sum2. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . By assumption, 𝐴 ∈ A 1 and A 1 ∩ A 2 = ∅, meaning the summed attribute can be changed but the grouping attributes cannot be changed. In the worst case, a value at 𝐴 is replaced from 𝐿 to 𝑈 , or from 𝑈 to 𝐿. This change is |𝐿 − 𝑈 |. Since at most 𝑘 replacements may occur, the global sensitivity Δ is at most 𝑘 · |𝐿 − 𝑈 |. Case S-Sum3. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . By assumption, A 1 ∩ 𝐴2 ≠ ∅, meaning the grouping attributes may be changed. In the worst case, changing any grouping attribute will cause one record with the most extreme value to move groups. This causes a difference of max(|𝐿|, |𝑈 |) in two groups. Since there are at most 𝑘 replaced records, the global sensitivity Δ is at most 2𝑘 · max(|𝐿|, |𝑈 |). Case S-Sum4. By the inductive hypothesis, ⊢ 𝑆 : Add𝑎 × Del𝑑 . Any two neighbors differ by at most 𝑎 + 𝑑 records. Each added and deleted record changes the sum of a group by at most max(|𝐿|, |𝑈 |). Therefore, the global sensitivity Δ is at most (𝑎 + 𝑑) · max(|𝐿|, |𝑈 |). □

Add𝑎·mmf(𝑆 2 .𝐴2 )+ × Del𝑑 ·mmf(𝑆 2 .𝐴2 )+ = 𝜏 𝑘 ·mmf(𝑆 1 .𝐴1 )+ 𝑘 ·mmf(𝑆 1 .𝐴1 ) 𝑎·𝑘 Therefore, (𝑆 1 Z 𝑆 2 )(𝐷 ′ ) ∈ 𝛼 ((𝑆 1 Z 𝑆 2 )(𝐷), 𝜏). 𝐴1 =𝐴2 𝐴1 =𝐴2

Case T-Join3. By the inductive hypothesis, ⊢ 𝑆 1 : Rep𝑘A 1 and 1

⊢ 𝑆 2 : Rep𝑘A 2 . There are 3 sources of changed records: (1) A record 2 from 𝑆 1 (𝐷) may match a record replaced from 𝑆 2 (𝐷 ′ ), and (2) a record from 𝑆 2 (𝐷) may match a record replaced from 𝑆 1 (𝐷 ′ ) By assumption, the join keys cannot be replaced. So, the size of the join remains constant. Considering each source of changed records: (1) In the worst case, each replaced record in 𝑆 2 (𝐷 ′ ) matches with the most popular join key in 𝑆 1 (𝐷), which is at most mmf(𝑆 1 .𝐴1 ) (Lemma B.1). So, at most 𝑘 2 · mmf(𝑆 1 .𝐴1 ) records are replaced. (2) By symmetric reasoning, at most 𝑘 1 · mmf(𝑆 2 .𝐴2 ) additional records are replaced. The total number of replaced records is exactly the action: Rep𝑘1 ·mmf(𝑆 2 .𝐴2 )+ = 𝜏 𝑘 2 ·mmf(𝑆 1 .𝐴1 )

Therefore, (𝑆 1 Z 𝑆 2 )(𝐷 ′ ) ∈ 𝛼 ((𝑆 1 Z 𝑆 2 )(𝐷), 𝜏). 𝐴1 =𝐴2

𝐴1 =𝐴2

Case T-Join4. By the inductive hypothesis, ⊢ 𝑆 1 : Rep𝑘A 1 and 1

⊢ 𝑆 2 : Rep𝑘A 2 . There are 2 sources of changed records: (1) A record 2 from 𝑆 1 (𝐷) may match a record replaced from 𝑆 2 (𝐷 ′ ), (2) a record from 𝑆 2 (𝐷) may match a record replaced from 𝑆 1 (𝐷 ′ ), and (3) a record replaced from 𝑆 1 (𝐷 ′ ) may match a record replaced from 𝑆 2 (𝐷 ′ ). By assumption, at least one join key can be replaced. So, the size of the join may change. Considering each source of changed records: In the worst case, each replaced record in 𝑆 2 (𝐷 ′ ) matches with the most popular join key in 𝑆 1 (𝐷) (before and after replacement), which is at most mmf(𝑆 1 .𝐴1 ) (Lemma B.1). So, at most 𝑘 2 ·mmf(𝑆 1 .𝐴1 ) records are added and deleted. By symmetric reasoning, at most 𝑘 1 · mmf(𝑆 2 .𝐴2 ) additional records are added and deleted. (3) At most 𝑘 1 · 𝑘 2 additional records are added since each pair of replaced records may match. The total number of added and deleted records is exactly the action: Add𝑘1 ·mmf(𝑆 2 .𝐴2 )+ × Del𝑘1 ·mmf(𝑆 2 .𝐴2 )+ = 𝜏 𝑘 2 ·mmf(𝑆 1 .𝐴1 )+ 𝑘 1 ·𝑘 2

𝑘 2 ·mmf(𝑆 1 .𝐴1 )

Therefore, (𝑆 1 Z 𝑆 2 )(𝐷 ′ ) ∈ 𝛼 ((𝑆 1 Z 𝑆 2 )(𝐷), 𝜏). 𝐴1 =𝐴2

𝐴1 =𝐴2

□

The second is Theorem 7.3 (Sensitivity Soundness): Proof. By induction on the sensitivity rules in Figure 7. Case S-Cnt1. By the inductive hypothesis, ⊢ 𝑆 : Rep𝑘A 1 . Since A 1 ∩ A 2 ≠ ∅, the grouping attributes A 2 may be replaced. In the worst case, for each record 𝑟 , some 𝐴 ∈ A 2 is replaced such that 𝑟 is in a different group in any neighbor. This decreases the count by 17

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505