{'fraction_non_alphanumeric': 0.029509323452067894, 'fraction_numerical': 0.007844250537891466, 'mean_word_length': 5.058019551049964, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Chorus: a Programming Framework for Building Scalable Differential Privacy Mechanisms

Differential privacy is fast becoming the gold standard in enabling statistical analysis of data while protecting the privacy of individuals. However, practical use of differential privacy still lags behind research progress because research prototypes cannot satisfy the scalability requirements of production deployments. To address this challenge, we present Chorus, a framework for building scalable differential privacy mechanisms which is based on cooperation between the mechanism itself and a high-performance production database management system (DBMS). We demonstrate the use of Chorus to build the first highly scalable implementations of complex mechanisms like Weighted PINQ, MWEM, and the matrix mechanism. We report on our experience deploying Chorus at Uber, and evaluate its scalability on real-world queries.


Introduction
Organizations are collecting more and more sensitive information about individuals. As this data is highly valuable for a broad range of business interests, organizations are motivated to provide analysts with flexible access to the data. At the same time, the public is increasingly concerned about privacy protection. There is a growing and urgent need for technology solutions that balance these interests by supporting general-purpose analytics while guaranteeing privacy protection.
Differential privacy [28], [32] is widely recognized by experts as the most rigorous theoretical solution to this problem. Differential privacy provides a formal guarantee of privacy for individuals while allowing general statistical analysis of the data. In short, it states that the presence or absence of any single individual's data should not have a large effect on the results of a query. This allows precise answers to questions about populations in the data while guaranteeing the results reveal little about any individual. Unlike alternative approaches such as anonymization and k-anonymity, differential privacy protects against a wide range of attacks, including attacks using auxiliary information [27], [61], [65], [77]. Current research on differential privacy focuses on development of new algorithms, called mechanisms, to achieve differential privacy for a particular class of queries. Researchers have developed dozens of mechanisms covering a broad range of use cases, from generalpurpose statistical queries [19], [30], [54], [55], [59], [64], [67] to special-purpose analytics tasks such as graph analysis [24], [42], [46], [47], [72], linear queries [8], [25], [41], [50]- [53], [68], [81], [82], [85], and analysis of data streams [31], [74].
Despite extensive academic research and an abundant supply of mechanisms, differential privacy has not been widely adopted in practice. Existing applications of differential privacy in practice are limited to specialized use cases [2], [34].
A major challenge for the practical adoption of differential privacy is the ability to deploy differential privacy mechanisms at scale. Today's data analytics infrastructures include industrial-grade database management systems (DBMSs) carefully tuned for performance and reliability, designed to process datasets consisting of billions of rows.
The simplest mechanisms for differential privacy, like the Laplace mechanism [30], answer an analyst's query by adding noise to the final result of the query. This mechanism can be easily deployed atop an existing highperformance DBMS by leveraging the DBMS to execute the analyst's query, then adding the right amount of noise to the result. Since it uses the DBMS to perform the actual data processing tasks, this approach scales well. Some existing work, such as FLEX [44], takes this approach, which we call the post-processing architecture. For appropriate mechanisms, the post-processing architecture solves the scalability problem.
However, more advanced differential privacy mechanisms require fundamental changes to the way queries execute. Summation queries, for example, require clipping the data before summing it to control the influence of outliers. The post-processing approach is fundamentally incompatible with mechanisms like this one-it is impossible to run the analyst's query unmodified and then achieve differential privacy by post-processing the results. Unfortunately, the vast majority of recently-developed mechanisms fall into this category (e.g. [8], [24], [25], [41], [42], [46], [47], [50]- [53], [68], [72], [81], [82], [85]), and cannot be implemented using the post-processing architecture.
As a result, no scalable implementation exists for many of the exciting differential privacy mechanisms developed in recent years. The implementations which have been developed (e.g. [49], [55], [59], [67], [80]) modify or replace the DBMS with a custom engine, which is unlikely to offer performance on par with modern production DBMSs.
The CHORUS Framework. This paper describes CHO-RUS, a framework for developing and deploying cuttingedge differential privacy mechanisms at scale. CHO-RUS makes it easy to develop mechanism implementations which work in cooperation with an existing highperformance DBMS, even for mechanisms which require modifying queries or generating entirely new ones. CHO-RUS supports scalable implementations by leveraging the DBMS for data processing tasks, instead of custom code. We call this the cooperative architecture for differential privacy mechanisms.
CHORUS provides a programming framework to support implementing mechanisms in the cooperative architecture. The framework has three major components: rewriting, for modifying queries to perform functions like clipping; analysis, for analyzing queries to determine properties like how much noise is required for differential privacy; and post-processing, for processing the results of executing queries. To implement a summation mechanism with clipping, for example, we can use CHORUS's rewriting component to modify the analyst's query so that the DBMS performs the clipping as well as the summation. With this modification, the rest of the mechanism can be implemented via analysis and post-processing of the rewritten query.
CHORUS supports integration with any standard SQL database. The framework is designed to facilitate working directly with SQL queries, since SQL is the most commonly used language for high-performance production DBMSs. By using a standard SQL database engine instead of a custom runtime, CHORUS can leverage the reliability, scalability and performance of modern databases, which are built on decades of research and engineering experience.
The cooperative architecture applies to all of the recently-developed differential privacy mechanisms-even ones that require significant changes to the way queries execute or generate entirely new queries. We demonstrate the flexibility of the approach, and of the CHORUS framework, by implementing both simple mechanisms like summation with clipping and complex mechanisms like wPINQ, MWEM, and the matrix mechanism. In all of these implementations, CHORUS supports scalability by moving data processing tasks to the DBMS. Deployment. We have made CHORUS available as open source software [3], and it is designed for integration in production environments. We describe how to deploy CHORUS to provide differential privacy in the face of untrusted analysts who may submit malicious queries, and present practical strategies for privacy budget management as part of a CHORUS deployment.
We report on our experience deploying CHORUS at Uber for its internal analytics tasks. CHORUS represents a significant part of the company's General Data Protection Regulation (GDPR) [4] compliance efforts, and provides both differential privacy and access control enforcement. Evaluation. We evaluate the scalability of CHORUS on real queries written by analysts at Uber, using a 300 million rows sampled from the production data. Our evaluation results demonstrate that mechanism implementations built with CHORUS are capable of scaling to real-world analysis tasks. Contributions. In summary, we make the following con-tributions: 1) We present the CHORUS framework, which enables a novel cooperative architecture for implementing differential privacy mechanisms atop high-performance DBMSs ( § 3). 2) We demonstrate CHORUS's flexibility by developing scalable implementations for a number of advanced differential privacy mechanisms ( § 5). 3) We release CHORUS as open source [3] and describe how to deploy it to provide differential privacy in production settings ( § 6). 4) We report on our experience deploying CHORUS to enforce differential privacy at Uber, where it processes more than 10,000 queries per day ( § 6). 5) We demonstrate the scalability of CHORUS by evaluating it on 18,774 real-world queries with a database of 300 million rows ( § 7).

Background
Differential privacy provides a formal guarantee of indistinguishability. This guarantee is defined in terms of a privacy budget -the smaller the budget, the stronger the guarantee. The formal definition of differential privacy is written in terms of the distance d(x, y) between two databases, i.e. the number of entries on which they differ: d(x, y) = |{i : x i = y i }|. Two databases x and y are neighbors if d(x, y) = 1. A randomized mechanism K : D n → R preserves ( , δ)-differential privacy if for any pair of neighboring databases x, y ∈ D n and set S of possible outputs: Differential privacy can be enforced by adding noise to the non-private results of a query. The scale of this noise depends on the sensitivity of the query. The global sensitivity of a query f : D n → R is defined as: |f (x) − f (y)| Importantly, differential privacy mechanisms satisfy a sequential composition property: if F 1 satisfies ( 1 , δ 1 )differential privacy, and F 2 satisfies ( 2 , δ 2 )-differential privacy, then running both F 1 and F 2 satisfies ( 1 + 2 , δ 1 + δ 2 )-differential privacy. For more on differential privacy, see Dwork and Roth [32]. Statistical queries. Differential privacy aims to protect the privacy of individuals in the context of statistical queries. In SQL terms, these are queries using standard aggregation operators (COUNT, AVG, etc.) as well as histograms created via the GROUP BY operator in which aggregations are applied to records within each group. Differential privacy is not suitable for queries that return raw data (e.g. rows in the database) since such queries are inherently privacy-violating. Mechanism design. Research on differential privacy has produced a large and growing number of differential privacy mechanisms. Some mechanisms are designed to provide broad support for many types of queries [19], [30], [49], [54], [55], [59], [64], [67], while others are designed to produce maximal utility for a particular application [8], [24], [25], [34], [41]- [43], [46], [47], [50], [52], [68], [72], [81], [82], [85]. While mechanisms adopt unique strategies for enforcing differential privacy in their target domain, they generally share a common set of design choices and algorithmic components. For example, many mechanisms require addition of Laplace noise to the result of the query.

The CHORUS Architecture
This section presents the system architecture and advantages of CHORUS, and compares it against existing architectures for differentially private analytics. We first describe the design goals motivating the CHORUS architecture. Then, in Section 3.1, we describe the limitations of existing architectures preventing previous work from attaining these goals. Finally, Section 3.2 describes the novel architecture of CHORUS and provides an overview of our approach. Design Goals. The design of CHORUS is motivated by the desire to enforce differential privacy at the scale of real-world industrial deployments. To that end, CHORUS has the following design goals: • Process data using a DBMS, not a custom system • Support a broad range of privacy mechanisms • Integrate easily with existing data environments As we will demonstrate in the next section, achieving these goals is challenging, and no existing system manages to achieve all three. We emphasize the importance of integration with an existing, highly-tuned database management system (DBMS)-such systems are the result of decades of research, and the massive scale of modern data warehouses is made possible only by leveraging these results. A custom-built system specific to differential privacy is unlikely to ever match the performance of a highly-tuned DBMS designed for big data. Motivating example: bounded sum queries. Consider a simple example query over a table called trips containing information about taxi trips. Suppose we want to return the sum of miles driven over all of the trips in the database. We might use a query like this: SELECT SUM( t r i p d i s t a n c e ) FROM t r i p s Satisfying differential privacy for this query is challenging, because there is no obvious bound on the global sensitivity of the SUM. Two neighboring databases differ in only a single row, but that row may have any value, and adding a row to the database increases the sum by the value of an attribute in the new row. Without some upper bound on the attribute values rows can have, it is not possible to bound the sensitivity of the summation query.
The usual strategy for solving this problem is clipping: we first enforce a bound on the maximum distance of any trip in the database, then perform the sum on the clipped distances. We can implement this strategy using a revised query: SELECT SUM( max ( 0 , min ( 1 0 0 , t r i p d i s t a n c e ) ) ) FROM t r i p s The revised query has a global sensitivity of 100, because all trip distances are clipped to lie between 0 and 100 miles. We can achieve differential privacy for the revised query by adding Laplace noise scaled to 100 [32].

Existing Architectures
Existing systems for enforcing differential privacy for data analytics tasks adopt one of two architecture types: they are either deeply integrated systems or post processing systems. These architectures are summarized in Figure 1(a) and Figure 1(b). PINQ [55], Weighted PINQ [67], GUPT [59], and Airavat [71] follow the deep integration architecture: each one provides its own specialized DBMS, and cannot be used with a standard DBMS. As described earlier, the use of a specialized DBMS is likely to prevent the use of these systems for large-scale deployments.
The FLEX [44] system uses the post processing architecture: it runs the analyst's original query on the database, then adds noise to the result. This approach supports mechanisms that do not modify the semantics of the original query, like Elastic Sensitivity, PINQ, and Restricted sensitivity. The major advantage of the post processing architecture is that it is compatibile with existing DBMSs.
However, the post processing architecture is fundamentally incompatible with mechanisms that change how the original query executes-such as queries that perform clipping, like the motivating example above. FLEX is not capable of answering SUM queries with differential privacy unless bounds on the values of the summed columns are known a priori (which is often not the case).
Many differential privacy mechanisms make even more complicated changes to the query the analyst actually wants to answer. For example, Sample & Aggregate splits the database into chunks and runs the analyst's query on each chunk separately, then aggregates the results, and WPINQ assigns a weight to each row of the database and updates these weights as the query executes. More recent algorithms, like MWEM, the Matrix Mechanism, and others are even more complicated. These approaches are impossible to implement via post-processing: they require running queries which are different from the analyst's original query, and they often require multi-stage interaction with the DBMS.
The deeply integrated and post processing architectures in Figure 1(a) and (b) therefore both fail to address two major challenges in implementing a practical system for differentially private data analytics: • Deeply integrated systems use custom DBMSs, which are unlikely to achieve parity with mature DBMSs in terms of performance and scalability, query optimization, recoverability, and distribution.
• Neither architecture supports all of the different mechanisms discussed earlier. The deeply integrated architecture requires building a new DBMS for each mechanism, while the post processing architecture is inherently incompatible with some mechanisms.

The CHORUS Architecture
In CHORUS, we propose a novel alternative, which we call the cooperative architecture. As shown in Figure 1(c), the cooperative architecture has two major differences with existing architectures: • CHORUS integrates tightly with an existing unmodified SQL DBMS, which holds the sensitive data.  • CHORUS can perform post-processing operations and modify the way queries execute, enabling implementations of all the mechanisms discussed earlier.

Deep Integration
CHORUS provides a flexible framework for implementing differential privacy mechanisms in the cooperative architecture. In this architecture, the analyst specifies the task to be completed via one or more queries to be answered, plus additional metadata (for example, the desired values for the privacy parameter(s)). CHORUS provides the following components: • Rewriting supports generating new SQL queries, by modifying queries from the analyst's workload or generating new ones.
• Analysis supports analyzing queries in the workload to determine their properties (e.g. sensitivity).
• Post-processing supports post-processing of query results (e.g. to combine results or add noise). For counting queries like those supported by FLEX [44], CHORUS can simply execute the queries in the workload and add noise to the results via post-processing. For a SUM query requiring clipping, like our motivating example, CHORUS rewrites the query to include the clipping bound specified by the analyst in the metadata, executes the rewritten query on the DBMS, and adds noise to the result. For more complicated mechanisms like the Matrix Mechanism [51], CHORUS may generate entirely new queries not present in the original workload. CHORUS has two key advantages over previous work: • CHORUS is DBMS-independent (unlike the deeply integrated approach): it requires neither modifying the database nor switching to purpose-built database engines. Our approach can therefore leverage existing high-performance DBMSs to scale to big data.
• CHORUS can implement a wide variety of privacypreserving techniques. Unlike the post processing approach, CHORUS is compatible with all of the mechanisms discussed earlier, and many more. CHORUS's architecture is specifically designed to be easily integrated into existing data environments. We report on the deployment of CHORUS at Uber in Section 6. Challenges. Developing differential privacy mechanisms to target the cooperative architecture is much more challenging than developing either deeply integrated or postprocessing solutions. In particular, this model requires interacting closely with a DBMS which may have a nonstandard dialect or feature set, analyzing SQL queries which may have complicated structure or target a specific dialect, and generating new queries which target the appropriate DBMS.
CHORUS is designed specifically to address these challenges. We detail the solutions to each one in Section 4. We also develop a number of case studies (in Section 5) to demonstrate how the features of CHORUS support programmers in developing differential privacy mechanisms in the cooperative architecture, following the rewrite-analyze-postprocess structure outlined above.

Threat Model
Typical deployments of CHORUS mechanisms involve three kinds of parties: data subjects, who contribute sensitive data to the database, the data curator, who manages the database containing the sensitive data, and analysts, who submit queries to be answered using the sensitive data. CHORUS is designed primarily to protect the sensitive data contributed by data subjects against malicious analysts.
As with most systems designed around the central model of differential privacy, we assume that the data curator behaves honestly. The DBMS, CHORUS-based mechanisms, and other systems maintained by the data curator for answering queries are assumed to be trusted, and cannot be corrupted.
The adversary in this setting is represented by a group of one or more malicious analysts, who would like to discover a fact about an individual data subject in the sensitive data. The analyst may submit arbitrary queries to the system, designed to expose private information about an individual. These queries may be adaptively chosen based on previous results, and more than one analyst may collude to infer private information. CHORUS is designed to guarantee that each query response satisfies differential privacy, which implies a bound on the total privacy cost of all queries posed by the analyst.
Our deployment enforces that the adversary may access the sensitive data only via the centralized query interface. All components of the system, including the query interface, the privacy budget accountant, CHORUS, and the DBMSs themselves, are protected from tampering by the adversary via access-control protections.

Selecting a Mechanism
As described in Section 2, many differential privacy mechanisms exist, and many of these require the analyst to re-phrase queries in a new way or provide additional inputs. As a result, it is not always possible to automatically select the best mechanism for answering a SQL query posed by the analyst-the best mechanism might depend on domain knowledge, other queries in the workload, or the ability of the analyst to re-phrase the query. For certain classes of queries-for example, linear queries over a single database table-Hay et al. [48] demonstrate that a machine learning-based approach can leverage properties of the data to select a mechanism most likely to yield high utility.
The interface provided to the analyst in each deployment of CHORUS will therefore depend on the analyst's expected expertise in differential privacy.
• Non-experts will submit standard SQL queries, without any knowledge about how differential privacy is being enforced. CHORUS can attempt to select a mechanism which supports the features used in the query. If no suitable mechanism is found, CHORUS rejects the query. • Privacy-conscious analysts will submit workloads of queries written in subsets of SQL (e.g. linear queries), and CHORUS can select the best approach (e.g. using a machine learning model). • Privacy experts will manually select a mechanism, and phrase their queries appropriately for that mechanism (e.g. for the Sparse Vector Technique, a sequence of queries and a threshold). The CHORUS API is designed to facilitate all three possibilities. For our prototype deployment (discussed in Section 6), we expected users to be non-experts, and implemented a simple rule-based mechanism to select a mechanism based on the aggregation function used and whether or not the query contained joins. Section 4.4 describes the use of the CHORUS API for this purpose.

Privacy Budget Management
We have designed CHORUS to be flexible in its handling of the privacy budget, since the best approach in a given setting is likely to depend on the domain and the kinds of queries posed.
One approach to budget management involves tracking a single global budget, subtracting from the budget when each query runs using standard composition. One straightforward optimization is to use advanced composition [33], which improves the total budget for k queries to be proportional to √ k. Recent advances in composition, like Rényi differential privacy [58], zero-concentrated differential privacy [22], and truncated concentrated differential privacy [21], can be directly applied in a similar way. Some mechanisms build a differentially private synthetic representation of the data, and use this representation to answer queries (e.g. MWEM and the matrix mechanism). This is another form of budget management: once the representation is built, it can be used to answer an unbounded number of queries without incurring additional privacy cost. Such mechanisms often offer better accuracy over workloads of queries than any composition approach which supports online answering of queries.
We describe the CHORUS API for implementing budgeting strategies in Section 4.4. Mechanism definitions return the privacy cost of one execution, and approaches to budgeting can be built on top of this interface.

Assumptions & Limitations
CHORUS's guarantees rely on the soundness of several underlying components. Bugs in these components could cause a failure of the guarantee, and the release of sensitive information without differential privacy. Correctness of Underlying Libraries. CHORUS uses the Apache Calcite [1] framework for parsing SQL queries and translating them to a bag-based variant of relational algebra. A bug in Calcite could cause a query to be wrongly parsed or converted. Such a failure would result in incorrect results being returned to the analyst, but would not cause a failure in differential privacy, since CHORUS analyzes, rewrites, and executes the final output of Calcite's processing pipeline. In addition, Apache Calcite is widely used and therefore likely to be reliable. Soundness of Abstract Interpretation. To analyze a query's sensitivity, CHORUS performs abstract interpretation of the query (see Section 5). CHORUS provides an abstract interpretation framework, which enables implementing many different kinds of analyses. A bug in either the framework or the implementation of a specific analysis could cause unsoundness in the analysis results, leading to a failure to ensure differential privacy. To mitigate this risk, we designed the framework to be compact and easily audited; further mitigation using formal verification techniques might also be possible in future work. Semantics of DBMSs. A more subtle failure of the abstract interpretation occurs when the concrete semantics of the DBMS used to execute queries do not match the semantics encoded by the abstract interpreter. This is a special concern for CHORUS, since we aim to support many different DBMSs, and because DBMSs sometimes differ significantly in their semantics [37]. Mitigation of this risk would require formal analysis of specific DBMS implementations to verify their compliance with a standard semantics. Dialects and Other Languages. CHORUS uses Apache Calcite [1] to parse and process queries, and works for queries that Calcite supports. Calcite does offer support for a number of SQL dialects, but it may not support all of the vendor-specific extensions offered by a particular DBMS, and CHORUS will therefore not support them either (without modifications to Calcite). Code written in languages other than SQL (including stored or userdefined functions) are not supported for the same reason. Sources of Randomness. CHORUS relies on randomness generated by both the DBMS and the Java runtime, and previous work has shown [57] that inadequate sources of randomness can lead to a failure of differential privacy. However, the same work also demonstrated simple solutions for improving faulty sources of randomness to recover differential privacy. Large-scale deployments of CHORUS should verify that both the DBMS and Java runtime used provide high-quality sources of randomness, or implement the appropriate countermeasures. Correctness of Mechanism Implementations. Bugs may also exist in mechanism implementations themselves. The CHORUS framework is designed to simplify mechanism implementations to reduce bugs, but it does not eliminate them entirely. Integrating an approach for formal verification of mechanism correctness (e.g. [10], [12]- [16], [26], [35], [62], [69], [73], [79], [83], [84]) could ensure bugfree mechanisms, and is an exciting area for future work.

The CHORUS Programming Framework
The CHORUS framework provides a Scala library for implementing differential privacy mechanisms in the cooperative model we have proposed. The library provides support for all three components of the model: • A rewriting component, with support for modifying existing SQL queries and generating new ones • An analysis component, which provides an abstract interpretation framework for analyzing SQL queries • A post-processing component, which provides utilities for post-processing results In this section, we describe each of the three components. We begin with our simple motivating example from earlier: a SUM query over a column with no known upper bound. As described earlier, bounding the sensitivity of this query requires clipping the values being summed, but this is impossible to accomplish by post-processing alone.
We will implement a CHORUS mechanism to answer such queries in three steps: (1) rewrite SUM aggregations in the analyst's query to perform clipping; (2) analyze the rewritten query to determine its sensitivity; (3) run the rewritten query and add noise to the result based on the sensitivity computed in step (2).

Rewriting
For the first step, CHORUS provides a powerful rewriting API for modifying the analyst's queries. The following Scala code implements the rewriter for step (1) above. CHORUS's rewriter API contains an embedded DSL for building SQL queries; the expression max(l, min(u, col .expr)) uses this embedded DSL to generate a new expression for the argument to the SUM aggregation. Running this rewriter on our simple query from earlier, with a lower bound of 0 and upper bound of 100, produces the following change: SELECT SUM( t r i p d i s t a n c e ) FROM t r i p s ⇓ SELECT SUM( max ( 0 , min ( 1 0 0 , t r i p d i s t a n c e ) ) ) AS sum FROM t r i p s CHORUS's rewriting library is designed to address the challenges of rewriting tasks like the one above. Solving such tasks requires matching on generalized patterns in the query, and replacing sections of the query with new text. This process requires building an abstract syntax tree for the query, since searching through its text (e.g. with regular expressions) will not provide enough information about the query's structure to implement the correct semantics. Modern DBMSs use a variety of SQL dialects; many SQL queries in production are hundreds or thousands of lines long and use many of these special features, so analyzing these queries is difficult.
CHORUS provides a query parser based on Apache Calcite [1], and also allows extending the parser to support features of specialized dialects. We translate special features into an abstract syntax tree (AST) based on relational algebra for rewriting, and provide an API for pattern matching on pieces of the AST. The rewriteRecursive method, for example, makes it easy to search for a particular pattern in the query and replace it with something new. This method also allows the program to perform simultaneous analysis of the query, using the abstract interpretation framework described in the next section.
A second challenge of rewriting is producing new queries (or sections of queries). CHORUS provides an embedded domain-specific language (DSL) as a library of Scala operators for this purpose. SQL queries produced using our DSL have two major advantages over a simpler solution based on formatting strings: first, they are more readable, and can easily incorporate other AST nodes (as in min(u, col .expr) above), and second, the AST objects produced by our DSL operators can be easily translated back into different SQL dialects. For example, if the DBMS used for deployment provides the minimum function instead of min, CHORUS can translate the above query appropriately for this dialect.

Analysis
The next step is to analyze the rewritten query to determine its sensitivity. For this purpose, CHORUS provides a query analysis API which implements an abstract interpretation framework for SQL queries. Abstract interpretation is the execution of a program using abstract values instead of concrete (normal) values. Abstract values are members of an abstract domain, and each abstract value represents a set of possible concrete values. For example, the abstract domain {Even, Odd, Unknown} might correspond to the concrete domain of the integers, and the abstract value Even represents the set of even numbers. Abstract interpretation enables analysis of program properties: if a program outputs the value Even, then we know its output is always an even number. In CHORUS, we use abstract interpretation on SQL queries to determine properties like the sensitivity of the query independent of the underlying concrete data.
The sensitivity analysis for our rewritten query depends on three properties. First, the stability [55] of the underlying relation is 1. The stability of a relation measures how much the transformations used to create it from underlying tables change the number of rows before aggregation. A stability of 1 means that these transformations do not change the number of rows. Second, each value is clipped to lie between 0 and 100 before being aggregated. Third, the aggregation being performed is a SUM, whose global sensitivity is equal to (u − l) · s where u and l are the upper and lower clipping bounds, respectively, and s is the stability of the underlying relation.
We can use CHORUS to build an analysis which encodes these three properties by developing a pair of abstract domains that track properties of subexpressions of the query. The second part is to implement the analysis itself, which encodes the rules for updating the domain. For stability, we will return a stability of 1 for relations resulting from a single table, and a stability of infinity otherwise. For sensitivity, we will follow the rules outlined above: the sensitivity and upper and lower bounds of a column reference start out infinite; upper and lower bounds are introduced using the max and min functions, respectively; and sensitivity is bounded using the COUNT and SUM aggregation functions. The definition of the analysis appears in Figure 2.
The abstract interpretation framework in CHORUS addresses a key challenge of deploying differentially private mechanisms for realistic SQL queries: SQL queries can be extremely complicated, and building sound analyses of these queries (e.g. for determining sensitivity) is correspondingly difficult.
The CHORUS analysis library allows a small amount of code to define sound analyses which support these complicated queries. The analysis we have defined here can be used even on queries with features we have not discussed, including subqueries, queries with WHERE clauses, and so on. This ability is based on the same parser and relational abstract syntax tree support described in the last section, extended with a dataflow analysis.
CHORUS implements a dataflow library for relational ASTs based on the classic monotone framework [45]. In this framework, the programmer defines an abstract domain as a lattice, provides a join operator for computing the least upper bound of two points in the lattice, and writes transfer functions to specify the effect of each  operator in the programming language on its inputs. In CHORUS, these are specified as regular Scala functions. The framework uses these to generate an abstract interpreter [63] that checks properties of programs by computing conservative approximations of the program's output.
This abstract interpretation framework greatly simplifies the task of analyzing a query to determine its properties. Above, we have defined a domain which tracks two properties of the query: (1) bounded ranges for values in sub-parts of the query, introduced by clipping, and (2) sensitivity of the query, based on aggregation functions and the bounded ranges determined in part (1). Implemented directly on abstract syntax trees, such an analysis would comprise hundreds of lines of complicated code; CHORUS's analysis library is designed to provide re-usable components to make these tasks simple.

Post-Processing
Finally, we use the rewriter and analyzer we have defined to produce a new SQL query with bounded sensitivity, run the query using the DBMS, and add Laplace noise to the results. Here, the call to DB.execute actually runs the query on the DBMS used in deployment. CHORUS works with any DBMS with a JDBC interface, and the configuration information for the DBMS is specified in CHORUS's configuration file.
This mechanism is ready for deployment using CHO-RUS, which enables it to run alongside any standard SQL DBMS and scale to massive databases. Since the code we have defined here is part of a static analysis of just the query, the scalability of our mechanism depends only on the ability of the cooperating DBMS to execute the rewritten query (which has only minor changes).
Our mechanism definitions are simply Scala functions, and can be exposed to analysts in a number of different ways depending on the deployment scenario (more in Section 6). The CHORUS post-processing library provides a number of useful utilities, including the Laplace mechanism (used above), the Gaussian mechanism, the Exponential mechanism, and various forms of clipping.
This simple example illustrates how CHORUS enables a rewrite-analyze-postprocess pattern to achieve its design goals of enabling mechanisms which change how the query executes while integrating easily with an existing DBMS. We will see this pattern repeatedly in the more complicated mechanisms we will develop in Section 5.

Budgeting & Mechanism Selection
The CHORUS API provides two interfaces for privacy budget accounting: PrivacyCost, to represent privacy costs, and PrivacyAccountant, to track the total cost of composing many mechanisms.
The PrivacyCost interface requires the programmer to define the + method in accordance with the sequential composition property of the corresponding privacy definition. The following two classes define privacy costs for pure -differential privacy and Rényi differential privacy [58] (we have also defined privacy cost for ( , δ)-differential privacy and Zero-concentrated differential privacy [22]): The PrivacyAccountant class enables different approaches to computing the total budget used over many queries. The base class tracks the privacy costs of individual mechanisms, and the programmer defines a getTotalCost method to compose these costs. For example, the following two classes define accountants for advanced composition of pure -differentially private mechanisms and for Rényi differential privacy:

l a s s RenyiCompositionAccountant extends P r i v a c y A c c o u n t a n t { d e f g e t T o t a l C o s t ( ) = c o s t s . f o l d ( RenyiDPCost ( 0 , 0 ) ) ( + ) }
Finally, the ChorusMechanism abstract class defines a standard interface for mechanisms, and integrates them with a chosen privacy accountant. Each mechanism class defines a run method that returns a differentially private result and a PrivacyCost object. To run a mechanism with accountant a, the programmer calls execute(a), which invokes run, adds the mechanism's cost to the accountant, and returns the result. For example, we can package our Laplace mechanism into a CHORUS mechanism: EpsilonDPCost ( e p s i l o n ) ) } These interfaces provide a flexible way to build systems that leverage existing mechanisms, permit building new mechanisms from old ones, and even allow implementing automatic mechanism selection (via "mechanisms" that use query properties to select from a list of mechanisms to run). For example, for our prototype deployment, we implemented a CHORUS mechanism that runs one of three individual mechanisms using a simple rule-based approach.

Mechanism Development with CHORUS
This section demonstrates the use of CHORUS to implement a number of different mechanisms, from simple ones based on the Laplace mechanism to more advanced algorithms like Sample and Aggregate and MWEM.

Average Queries
Average queries are typically answered with differential privacy by transforming the query into two separate differentially private queries-a SUM and a COUNT-and performing the division as post-processing.
We can implement this approach in CHORUS by reusing the building blocks we have already built. First, we will develop two rewriters: one that turns AVG into SUM, and another that turns AVG into COUNT. We will rewrite the input query twice, once with each rewriter, and then run both rewritten queries using the mechanism we developed in Section 4. The full implementation appears in Figure 3.
This modular approach illustrates a key benefit of CHORUS's design: the ability to re-use existing mechanisms to implement new ones. We will see this pattern used again in later mechanisms to reduce complexity.

Report Noisy Max
The report noisy max mechanism [32] takes a list of queries as input, adds independently drawn noisy to each one, and returns the index of the maximum noisy result.
The key advantage of report noisy max is that it consumes privacy budget proportional to one query, regardless of the length of the list of queries specified by the analyst.
This mechanism can be implemented in CHORUS by extending the ideas in the laplaceMechClip mechanism to a list of queries, and returning only the index of the maximum value in the resulting list: Our implementation of the report noisy max mechanism demonstrates two important principles. First is the use of a workload of queries: since CHORUS mechanisms are implemented as regular Scala functions, they can accept queries in any format, including a workload of SQL queries. Second is the splitting of mechanism logic between Scala and SQL: query results can be postprocessed with Scala code in arbitrary ways (here, we use Scala to find the maximum workload result).

Exponential Mechanism
The exponential mechanism [54] is the generalized version of report noisy max: it selects an element of a set R which approximately maximizes the value of a scoring function. The scoring function q : D n → R → R assigns numeric scores to each element of R based on the private database (in report noisy max, the scoring function simply returns the value of the query). For a scoring function with sensitivity ∆ = GS(q) and a database X, the exponential mechanism outputs r ∼ R with probability proportional to: Pr[r] ∼ exp q(X, r) 2∆ In report noisy max, the scoring function was fixed, so it was easy to assume something about its sensitivity and apply it directly to each query in the workload. The generalized exponential mechanism makes this process more difficult: since the analyst specifies the scoring function, we cannot assume anything about its sensitivity.
The solution is to ask the analyst to provide the scoring function as a query, so that we can analyze its sensitivity directly. This query should produce a relation mapping elements in R to their scores. For example, the following query implements a scoring function which will allow selecting the day of the week with approximately the largest number of trips: SELECT day , COUNT( * ) as score FROM t r i p s GROUP BY day We can use the same basic analysis as before to show that this query has a sensitivity of 1, and then perform

U t i l s . c h o o s e W i t h P r o b a b i l i t y ( p r o b a b i l i t i e s ) . 1 }
Our implementation here uses Utils .chooseWithProbability to select from the elements of R with the appropriate probabilities (this function expects a list of tuples mapping domain elements to their probabilities, and implements weighted random selection). We return just the identity of the element which was selected, similar to the report noisy max mechanism.

Sparse Vector Technique
The sparse vector technique (SVT) [32] releases the index (but not the result) of the first query in a sequence of queries whose result exceeds a threshold set by the analyst. Like report noisy max, SVT consumes privacy budget proportional to just one query. In situations where only a small number of queries are likely to have large enough results to be useful to the analyst (but the analyst does not know which ones), SVT can be applied repeatedly to answer the useful queries while minimizing privacy budget consumption.
We can define a CHORUS mechanism to implement SVT in a similar way to the report noisy max mechanism. In contrast to the report noisy max mechanism, however, SVT is iterative-it runs the queries in the workload in sequence, and may halt before running all of them. SVT first adds Laplace noise to the threshold, then compares the noisy result of each query to the noisy threshold. SVT releases the index of the first query whose noisy value exceeds the noisy threshold.
Our implementation appears in Figure 4. First, it analyzes each query to ensure that the query's sensitivity does not exceed 1, and returns None if not. Then, it uses Utils .Laplace to add noise to both the threshold and each query result, and returns Some(i) for the first index i whose noisy query result exceeds the noisy threshold. If no query exceeds the threshold, we return None.
This implementation corresponds to the AboveThreshold algorithm described by Dwork and Roth [32]. This algorithm can be combined with our earlier mechanisms to release the value of the first query above the threshold: This mechanism combines SVT with the Laplace mechanism to find the value of the first query above the threshold (not just its index), splitting the privacy budget between these two tasks. This mechanism illustrates the ease of combining mechanisms in CHORUS to build complex functionality.

Sample & Aggregate
The Sample & Aggregate [64], [75] mechanism works for all statistical estimators, but does not support joins. Sample & Aggregate has been implemented in GUPT [59], a standalone data processing engine that operates on Python programs, but has never been integrated with a high-performance DBMS. As defined by Smith [75], the mechanism has three steps: 1) Split the database into disjoint subsamples 2) Run the query on each subsample independently 3) Aggregate the results using a differentially private algorithm We can use the DBMS to accomplish tasks 1 and 2 by modifying the analyst's original query. We add a GROUP BY clause to the original query which groups rows according to their row number. Sample and aggregate does not require the subsamples to be randomized, so basing the selection of the subsamples on row number satisfies its requirements. For example, we can transform a simple AVG query as follows: SELECT AVG( t r i p d i s t a n c e ) FROM t r i p s ⇓ SELECT AVG( t r i p d i s t a n c e ) , ROW NUM( ) MOD n AS grp FROM t r i p s GROUP BY grp This transformation generates n subsamples and runs the original query on each one. Once we have obtained the answers to query on the subsamples, we can perform differentially private aggregation as a post-processing stepwith clipping followed by a noisy average. The complete implementation appears in Figure 5.

Additional Mechanisms
We present CHORUS implementations of three additional mechanisms in in Appendix A: Weighted PINQ, the Matrix Mechanism, and MWEM.

Implementation & Deployment
This section describes the deployment of CHORUS to protect sensitive data and provide a secure, differentially private interface for analysts to query that data. We also describe our experience deploying CHORUS to enforce differential privacy at Uber.
A typical deployment of a CHORUS mechanism includes a centralized query interface which allows the DBMSs containing sensitive data to be queried only via the mechanism. In such a deployment, untrusted analysts submit queries to the centralized query interface, which runs the mechanism and updates the privacy budget. The interface may enable auditing of the budget by a trusted curator of the system, and rejection of queries after the budget has been exhausted. Implementation. Our implementation is built on Apache Calcite [1], a generic query optimization framework that transforms input queries into a relational algebra tree and provides facilities for transforming the tree and emitting a new SQL query. We built CHORUS's custom dataflow analysis and rewriting components on Calcite to support the CHORUS programming framework. The framework, mechanism-specific analyses, and rewriting rules are implemented in 5,096 lines of Java and Scala code.
The approach could also be implemented with other query optimization frameworks or rule-based query rewriters such as Starburst [66], ORCA [5], and Cascades [36]. Real-world Deployment. CHORUS has been tested in a deployment to enforce differential privacy for queries over customer data at Uber. The primary goals of this deployment are to protect the privacy of customers from insider attacks, and to ensure compliance with the requirements of Europe's General Data Protection Regulation (GDPR) [4]. The mode of deployment calls for CHORUS to process more than 10,000 queries per day.
The deployment's data environment consists of several DBMSs (three primary databases, plus several more for specific applications), and a single central query interface through which all queries are submitted. The query interface is implemented as a microservice that performs query processing and then submits the query to the appropriate DBMS and returns the results.
Deployment involved building a minimal wrapper around the CHORUS library to expose its rewriting functionality as a microservice. The only required change to the data environment was a single modification to the query interface, to submit queries to the CHORUS microservice for rewriting before execution. The wrapper around CHORUS also queries a policy microservice to determine the security and privacy policy for the user submitting the query. This policy informs which mechanism is used-by default, differential privacy is required, but for some privileged users performing specific business tasks, differential privacy is only used for older data.
A major challenge of this deployment has been supporting the variety of SQL dialects used by the various DBMSs. This challenge motivated the built-in support for different dialects in the CHORUS framework.
The privacy budget is managed by the microservice wrapper around CHORUS. The microservice maintains a small amount of state to keep track of the current cumulative privacy cost of all queries submitted so far, and updates this state when a new query is submitted. The current design of the CHORUS microservice maintains a single global budget.

Evaluation
In this section, we evaluate the performance overhead of enforcing differential privacy using CHORUS in the context of real-world queries on a large production dataset. Our results demonstrate that the mechanism implementations we have developed using CHORUS scale effectively to realistic datasets using commodity DBMSs.
Our evaluation is intended to demonstrate the scalability of the CHORUS approach, rather than the ability of the mechanisms we implemented to produce accurate results. The accuracy we obtain in each of our experiments is a direct result of the underlying mechanism used in the experiment, and the same accuracy would be obtained using an alternative implementation of the same mechanism. Corpus. We use a corpus of 18,774 real-world queries containing all statistical queries executed by data analysts at Uber during a single month. The corpus includes queries written for several use cases including fraud detection, marketing, business intelligence and general data exploration. Dataset. We used a database of data sampled from the production database in our evaluation. This database contained 300 million records representing trip data similar in nature to the New York City Taxi Trip Data [6]-including information about trips, riders, and drivers. Mechanisms. In our evaluation, we considered two more complicated variants of the sensitivity-based mechanism we developed in Section 4: elastic sensitivity [44] and restricted sensitivity [19]. These mechanisms can answer existing counting and summation queries written by analysts unfamiliar with differential privacy, like those in our corpus. We also considered the performance of Weighted PINQ [67], since it performs more serious modifications to the analyst's query.

Performance Overhead
We conduct a performance evaluation demonstrating the performance overhead of several mechanisms implemented with CHORUS. Experiment Setup. We used a single HP Vertica 7.2.3 [7] node containing 300 million records including trips, rider and driver information and other associated data stored across 8 tables. We submitted the queries locally and ran queries sequentially to avoid any effects from network latency and concurrent workloads.
To establish a baseline we ran each original query 10 times and recorded the average after dropping the lowest and highest times to control for outliers. Then, we ran each CHORUS mechanism 10 times and recorded the average execution time, again dropping the fastest and slowest times. We calculate the overhead for each query by comparing the average runtime of the original query and the CHORUS mechanism. Results. Figure 6 shows the distribution of overhead as a function of original query execution time. This distribution shows that the percentage overhead is highest when the original query was very fast (less than 100ms). This is because even a small incremental performance cost is fractionally larger for these queries.
WPINQ significantly alters the way the query executes (see Section 5) and these changes increase query execution time. In particular, the query transformation adds a new join to the query each time weights are rescaled (i.e. one new join for each join in the original query), and these new joins result in the additional overhead. Figure 6 shows that, in both cases, the performance impact is amortized over higher query execution times, resulting in a lower relative overhead for more expensive queries.

Utility
We also measured the ability of some of the mechanisms we have implemented with CHORUS to produce accurate differentially private results for queries in our corpus, primarily as a study of whether or not differential privacy is a good fit for these queries. These mechanisms were previously proposed, and their accuracy properties were previously known. Our experimental results confirm existing knowledge using real-world queries and data.
For this experiment, we used the elastic sensitivity and restricted sensitivity mechanisms described earlier. Evaluating the utility of more complicated mechanisms would require re-formulating the queries in our corpus with the help of the original analyst. All of these mechanisms have been previously evaluated on synthetic query workloads, and their ability to improve utility is well-understood; as we gain experience with practical deployments, analysts will begin to adopt these mechanisms and re-formulate their queries. Experiment Setup. We use the same setup described in the previous section. For each query, we set the privacy budget = 0.1 for all mechanisms. For Elastic Sensitivity, we set δ = 1 n 2 (where n is the database size). We ran each query 10 times on the database and report the median relative error across these executions. For each run we report the relative error as the percentage difference between the differentially private result and the original non-private result. Consistent with previous evaluations of differential privacy [43] we report error as a proxy for utility since data analysts are primarily concerned with accuracy of results.  Query Sample Size. Our corpus includes queries covering a broad spectrum of use cases, from highly selective analytics (e.g., trips in San Francisco completed in the past hour) to statistics of large populations (e.g., all trips in the US). Differential privacy generally requires the addition of more noise to highly selective queries than to queries over large populations, since the influence of any individual's data diminishes as population size increases. Consequently, a query's selectivity is important for interpreting the relative error introduced by differential privacy. To measure the selectivity we calculate the sample size of every aggregation function in the original query, which represents the number of input records to which the function was applied. Results. Figure 7 shows the results of this experiment. Both mechanisms exhibit the expected inverse relationship between sample size and error; moreover, this trend is apparent for queries with and without joins.
Importantly, a very large portion of the queries with large sample sizes have very small relative error-the majority of queries with a sample size of over 10,000, for example, have less than 1% error. This suggests that for at least a subset of the queries in this production corpus, differential privacy can be enforced without significant harm to accuracy. Furthermore, more advanced mechanisms like the ones described in Section 5 could provide significant improvements for the accuracy of these queries.
A significant number of queries with small sample size also result in large relative error. It is likely that many of these queries are intended to violate privacyperhaps they examine the data of an individual or small set of individuals directly-and so differential privacy is probably not appropriate for these queries.

Discussion and Key Takeaways
Strengths & weaknesses of differential privacy. The mechanisms we studied generally worked best for statis-tical queries over large populations. None of the mechanisms was able to provide accurate results (e.g. within 1% error) for a significant number of queries over populations smaller than 1,000. These results confirm the existing wisdom that differential privacy is ill-suited for queries with small sample sizes. For large populations (e.g. more than 10,000), accurate differentially private results for real-world queries appears to be an achievable goal. A large set of such queries exists in our corpus. These results suggest that differential privacy can provide both strong privacy guarantees and accurate query responses for a large portion of the queries written by analysts in practice.
Our results also agree with the prior knowledge that queries with joins make ensuring differential privacy more challenging. For both mechanisms we used in our evaluation, the proportion of queries with less than 1% error was much smaller for queries with joins than for queries without joins. Differential privacy for joins is an active area of research [44], [49], and we hope that future mechanisms can be implemented in CHORUS to provide more accurate answers for these queries. Mechanism performance. Our performance evaluation demonstrates the scalability of mechanisms implemented with CHORUS-the vast majority of the queries executed with the elastic sensitivity and restricted sensitivity mechanisms resulted in less than 50% overhead, and the mean overhead for both was below 25%. However, the results also highlight the variability in computation costs of differential privacy mechanisms-WPINQ's added joins resulted in high performance overhead for some queries.

Related Work
Differential Privacy. Differential privacy was originally proposed by Dwork [28]- [30]. The reference by Dwork and Roth [32] provides an overview of the field.
Much recent work has focused on task-specific mechanisms for graph analysis [24], [42], [46], [47], [72], range queries [8], [25], [41], [50]- [53], [68], [81], [82], [85], and analysis of data streams [31], [74]. As described in Section 7.3, such mechanisms are complementary to our approach, and could be implemented on top of CHORUS to provide more efficient use of the privacy budget. Differential Privacy Systems. As differential privacy is more widely adopted, scalable implementations of differential privacy mechanisms have received more attention. Wilson et al. recently developed an open source, highly performant C++ library [80] which provides basic differential privacy mechanisms as an extension to PostgreSQL. However, their approach does not support other DBMSs. It also does not provide a framework for development of additional mechanisms; more complex mechanisms, like MWEM, would need to be added directly to the C++ library as new primitives.
The problem of answering SQL queries has also received considerable attention in recent years. The FLEX [44] system answers counting queries with differential privacy, and since it implements the postprocessing architecture, it is DBMS-independent. However, FLEX cannot implement more complex mechanisms like MWEM. PrivateSQL [49] answers SQL queries with differential privacy by generating differentially private synopses of views, then using the synopses to answer queries. This approach is potentially scalable, but limits the set of implementable mechanisms.
A number of other systems for enforcing differential privacy have been developed. PINQ [55] supports a LINQ-based query language, and implements the Laplace mechanism with a measure of global sensitivity. Weighted PINQ [67] extends PINQ to weighted datasets, and implements a specialized mechanism for that setting.
Airavat [71] enforces differential privacy for MapReduce programs using the Laplace mechanism. Fuzz [35], [40] enforces differential privacy for functional programs, using the Laplace mechanism in an approach similar to PINQ. DJoin [60] enforces differential privacy for queries over distributed datasets. Due to the additional restrictions associated with this setting, DJoin requires the use of special cryptographic functions during query execution so is incompatible with existing databases. GUPT [59] implements the Sample & Aggregate framework for Python programs. None of these systems offers integration with high-performance DBMSs. Security & Privacy via Query Rewriting. Automated query transformations have been used in previous work to implement access control. Stonebreaker and Wong [76] presented the first approach. Barker and Rosenthal [11] extended the approach to role-based access control by first constructing a view that encodes the access control policy, then rewriting input queries to add WHERE clauses that query the view. Byun and Li [23] use a similar approach to enforce purpose-based access control: purposes are attached to data in the database, then queries are modified to enforce purpose restrictions drawn from a policy.
Since then, a number of rewriting-based approaches have been proposed for enforcing access control. Agrawal et al. [9] use query rewriting to enforce row-level privacy policies focused on access control. Bender et al. [17], [18] combine query rewriting with specially-designed views to enforce privacy policies organized in "disclosure lat-tices." Wang et al. [78] propose fine-grained cell-level access control policies, with an enforcement mechanism based on query rewriting. Rizvi et al. [70] propose an access control mechanism based on "authorization views" which define policies, and use query rewriting to re-phrase queries in terms of these views. Oracle's Virtual Private Database [20] enforces fine-grained access control policies using query rewriting. All of these are primarily focused on access control policies.
Mehta et al. present Qapla [56], a system which uses query rewriting to enforce policies written in SQL. Notably, Qapla includes aggregation policies, which go beyond traditional access control policies to allow the release of aggregate statistics while protecting the underlying rows, but Qapla does not support differential privacy or other formal notions of privacy.
Guarnieri et al. [38], [39] explore the challenges of enforcing access control policies in the context of a complicated and expressive query language like SQL, and highlight the need for provable guarantees about the enforcement mechanism. Zhang and Mendelzon [86] study one of these challanges-the problem of "query containment"-in the context of proving correctness for query rewriting enforcement mechanisms. These results reinforce the value of additional work in the future to verify the correctness of our rewriting algorithms.

Conclusion
This paper presents CHORUS, a framework which enables a novel cooperative architecture for enforcing differential privacy. CHORUS works closely with a highperformance DBMS to scale differential privacy mechanisms to real-world deployments. CHORUS combines the strengths of integrated implementations (whose scalability does not match high-performance industrial DBMSs) and post-processing based implementations (which scale up, but are incompatible with many modern differential privacy mechanisms). We have described how CHORUS can be deployed to provide differential privacy, and released it as open source [3]. initialize weights to 1, and joins with subqueries that update the weights as above. By modifying the analyst's query to track and update weights using the DBMS, our CHORUS implementation enables WPINQ to scale to large datasets. We evaluate its performance in Section 7.1.

A.2. The Matrix Mechanism
The matrix mechanism [52] is another general approach for answering a set of counting queries. The insight behind the matrix mechanism is that the optimal way of answering a workload of counting queries might involve first answering a different set of queries, then inferring the answers to the workload queries based on these answers. The matrix mechanism is defined in terms of three matrices: the workload queries, represented as a matrix; the strategy matrix, which specifies the queries to submit to the database, and a matrix containing the answers to the queries in the strategy matrix. Given these three matrices, the method for answering the workload queries can be specified as a matrix multiplication.
We present an implementation of the matrix mechanism in CHORUS in Figure 8. Its inputs are matrices representing the workload and strategy, and a list of SQL queries corresponding to the strategy queries. We use the Laplace mechanism to answer the strategy queries, then transform the results into a matrix representation and perform the matrix multiplication specified by Li et al. [52] to obtain the workload results. The mpInverse method on matrices implements the Moore-Penrose pseudoinverse.
The challenge of determining an optimal set of strategy queries remains; Li et al. [52] consider this an orthogonal problem, and provide some heuristics for developing good strategies. Each of these heuristics can be implemented as Scala functions to generate sets of strategy queries for our implementation of the matrix mechanism.