boxcolor=black,boxtype=ox,charf=,boxfill = red!20

# DProvDB: Differentially Private Query Processing with Multi-Analyst
Provenance

Shufan Zhang  University of WaterlooWaterloo, Canada<EMAIL_ADDRESS>and  Xi He  University of WaterlooWaterloo, Canada<EMAIL_ADDRESS>
(2018)

###### Abstract.

Recent years have witnessed the adoption of differential privacy (DP) in
practical database systems like PINQ, FLEX, and PrivateSQL. Such systems allow
data analysts to query sensitive data while providing a rigorous and provable
privacy guarantee. However, the existing design of these systems does not
distinguish data analysts of different privilege levels or trust levels. This
design can have an unfair apportion of the privacy budget among the data
analyst if treating them as a single entity, or waste the privacy budget if
considering them as non-colluding parties and answering their queries
independently. In this paper, we propose DProvDB, a fine-grained privacy
provenance framework for the multi-analyst scenario that tracks the privacy
loss to each single data analyst. Under this framework, when given a fixed
privacy budget, we build algorithms that maximize the number of queries that
could be answered accurately and apportion the privacy budget according to the
privilege levels of the data analysts.

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

With the growing attention on data privacy and the development of privacy
regulations like GDPR (Voigt and Von dem Bussche, 2017), companies with
sensitive data must share their data without compromising the privacy of data
contributors. Differential privacy (DP) (Dwork and Roth, 2014) has been
considered as a promising standard for this setting. Recent years have
witnessed the adoption of DP to practical systems for data management and
online query processing, such as PINQ (McSherry, 2009), FLEX (Johnson et al.,
2018), PrivateSQL (Kotsogiannis et al., 2019a), GoogleDP (Amin et al., 2022),
and Chorus (Johnson et al., 2020). In systems of this kind, data curators or
system providers set up a finite system-wise privacy budget to bound the
overall extent of information disclosure. An incoming query consumes some
privacy budget. The system stops processing new queries once the budget has
been fully depleted. Thus, the privacy budget is a crucial resource to manage
in such a query processing system.

In practice, multiple data analysts can be interested in the same data, and
they have different privilege/trust levels in accessing the data. For
instance, tech companies need to query their users’ data for internal
applications like anomaly detection. They also consider inviting external
researchers with low privilege/trust levels to access the same sensitive data
for study. Existing query processing systems with DP guarantees would regard
these data analysts as a unified entity and do not provide tools to
distinguish them or track their perspective privacy loss. This leads to a few
potential problems. First, a low-privilege external data analyst who asks
queries first can consume more privacy budget than an internal one, if the
system does not interfere with the sequence of queries. Second, if naïvely
tracking and answering each analyst’s queries independently of the others, the
system can waste the privacy budget when two data analysts ask similar
queries.

The aforementioned challenges to private data management and analytics are
mainly on account of the fact that the systems are “ _stateless_ ”, meaning
none of the existing DP query-processing systems records the individual budget
limit and the historical queries asked by the data analysts. That is, the
metadata about _where the query comes from, how the query is computed, and how
many times each result is produced_ , which is related to the provenance
information in database research (Buneman and Tan, 2007; Cheney et al., 2009).
As one can see, without privacy provenance, the query answering process for
the multi-analyst use case can be unfair or wasteful in budget allocation.

To tackle these challenges, we propose a “stateful” DP query processing system
DProvDB, which enables a novel privacy provenance framework designed for the
multi-analyst setting. Following the existing work (Kotsogiannis et al.,
2019b), DProvDB answers queries based on private synopses (i.e., materialized
results for views) of data. Instead of recording all the query metadata, we
propose a more succinct data structure — a privacy provenance table, that
enforces only necessary privacy tracing as per each data analyst and per view.
The privacy provenance table is associated with privacy constraints so that
constraint-violating queries will be rejected. Making use of this privacy
provenance framework, DProvDB can maintain global (viz., as per view) and
local (viz., as per analyst) DP synopses and update them dynamically according
to data analysts’ requests.

DProvDB is supported with a new principled method, called _additive Gaussian
approach_ , to manage DP synopses. The additive Gaussian approach leverages DP
mechanism that adds correlated Gaussian noise to mediating unnecessary budget
consumption across data analysts and over time. This approach first creates a
global DP synopsis for a view query; Then, from this global synopsis, it
provides the necessary local DP synopsis to data analysts who are interested
in this view by adding more Gaussian noise. In such a way DProvDB is tuned to
answer as many queries accurately from different data analysts. Even when all
the analysts collude, the privacy loss will be bounded by the budget used for
the global synopsis. Adding up to its merits, we notice the provenance
tracking in DProvDB can help in achieving a notion called proportional
fairness. We believe most of if not all, existing DP query processing systems
can benefit from integrating our multi-analyst privacy provenance framework —
DProvDB can be regarded as a middle-ground approach between the purely
interactive DP systems and those based solely on synopses, from which we both
provably and empirically show that DProvDB can significantly improve on system
utility and fairness for multi-analyst DP query processing.

The contributions of this paper are the following:

  * $\bullet$

We propose a multi-analyst DP model where mechanisms satisfying this DP
provide discrepant answers to analysts with different privilege levels. Under
this setting, we ask research questions about tight privacy analysis, budget
allocation, and fair query processing. (Section $\S$3)

  * $\bullet$

We propose a privacy provenance framework that compactly traces historical
queries and privacy consumption as per analyst and as per view. With this
framework, the administrator is able to enforce privacy constraints, enabling
dynamic budget allocation and fair query processing. (Section $\S$4)

  * $\bullet$

We design new accuracy-aware DP mechanisms that leverages the provenance data
to manage synopses and inject correlated noise to achieve tight collusion
bounds over time in the multi-analyst setting. The proposed mechanisms can be
seamlessly added to the algorithmic toolbox for DP systems. (Section $\S$5)

  * $\bullet$

We implement DProvDB 111The system code is available at
https://github.com/DProvDB/DProvDB., as a new multi-analyst query processing
interface, and integrate it into an existing DP query system. We empirically
evaluate DProvDB, and the experimental results show that our system is
efficient and effective compared to baseline systems. (Section $\S$6)

Paper Roadmap. The remainder of this paper is outlined as follows. Section 2
introduces the necessary notations and background knowledge on database and
DP. Our multi-analyst DP query processing research problems are formulated in
section 3 and a high-level overview of our proposed system is briefed in
section 4. Section 5 describes the details of our design of the DP mechanisms
and system modules. In section 6, we present the implementation details and an
empirical evaluation of our system against the baseline solutions. Section 7
discusses extensions to the compromisation model and other strawman designs.
In section 8 we go through the literature that is related and we conclude this
work in section 9.

##  2\. Preliminaries

Let $\mathcal{D}$ denotes the domain of database and $D$ be a database
instance. A relation $R\in D$ consists of a set of attributes,
$attr({R})=\\{a_{1},\dots,a_{j}\\}$. We denote the domain of an attribute
$a_{j}$ by $Dom(a_{j})$ while $|Dom(a_{j})|$ denotes the domain size of that
attribute. We introduce and summarize the related definitions of differential
privacy.

###### Definition 0 (Differential Privacy (Dwork et al., 2006b)).

We say that a randomized algorithm
$\mathcal{M}:\mathcal{D}\rightarrow\mathcal{O}$ satisfies
$(\epsilon,\delta)$-differential privacy (DP), if for any two neighbouring
databases $(D,D^{\prime})$ that differ in only 1 tuple, and
$O\subseteq\mathcal{O}$, we have

$\Pr[\mathcal{M}(D)\in O]\leq e^{\epsilon}\Pr[\mathcal{M}(D^{\prime})\in
O]+\delta.$

DP enjoys many useful properties, for example, post-processing and sequential
composition (Dwork and Roth, 2014).

###### Theorem 2.2 (Sequential Composition (Dwork and Roth, 2014)).

Given two mechanisms $\mathcal{M}_{1}:\mathcal{D}\rightarrow\mathcal{O}_{1}$
and $\mathcal{M}_{2}:\mathcal{D}\rightarrow\mathcal{O}_{2}$, such that
$\mathcal{M}_{1}$ satisfies $(\epsilon_{1},\delta_{1})$-DP and
$\mathcal{M}_{2}$ satisfies $(\epsilon_{2},\delta_{2})$-DP. The combination of
the two mechanisms
$\mathcal{M}_{1,2}:\mathcal{D}\rightarrow\mathcal{O}_{1}\times\mathcal{O}_{2}$,
which is a mapping
$\mathcal{M}_{1,2}(D)=(\mathcal{M}_{1}(D),\mathcal{M}_{2}(D))$, is
$(\epsilon_{1}+\epsilon_{2},\delta_{1}+\delta_{2})$-DP.

###### Theorem 2.3 (Post Processing (Dwork and Roth, 2014)).

For an $(\epsilon,\delta)$-DP mechanism $\mathcal{M}$, applying any arbitrary
function $f$ over the output of $\mathcal{M}$, that is, the composed mechanism
$f\circ\mathcal{M}$, satisfies $(\epsilon,\delta)$-DP.

The sequential composition bounds the privacy loss of the sequential execution
of DP mechanisms over the database. It can naturally be generalized to the
composition of $k$ differentially private mechanisms. The post-processing
property of DP indicates that the execution of any function on the output of a
DP mechanism will not incur privacy loss.

###### Definition 0 ($\ell_{2}$-Global Sensitivity).

For a query $q:\mathcal{D}\rightarrow\mathbb{R}^{d}$ the $\ell_{2}$ global
sensitivity of this query is

$\Delta q=\max_{D,D^{\prime}:d(D,D^{\prime})\leq
1}\|q(D)-q(D^{\prime})\|_{2},$

where $d(\cdot,\cdot)$ denotes the number of tuples that $D$ and $D^{\prime}$
differ and $\|\cdot\|_{2}$ denotes the $\ell_{2}$ norm.

###### Definition 0 (Analytic Gaussian Mechanism (Balle and Wang, 2018)).

Given a query $q:\mathcal{D}\rightarrow\mathbb{R}^{d}$, the analytic Gaussian
mechanism $\mathcal{M}(D)=q(D)+\eta$ where
$\eta\sim{\mathcal{N}}\left(0,\sigma^{2}I\right)$ is $(\epsilon,\delta)$-DP if
and only if

$\Phi_{\mathcal{N}}\left(\frac{\Delta q}{2\sigma}-\frac{\epsilon\sigma}{\Delta
q}\right)-e^{\epsilon}\Phi_{\mathcal{N}}\left(-\frac{\Delta
q}{2\sigma}-\frac{\epsilon\sigma}{\Delta q}\right)\leq\delta,$

where $\Phi_{\mathcal{N}}$ denotes the cumulative density function (CDF) of
Gaussian distribution.

In this mechanism, the Gaussian variance is determined by $\sigma=\alpha\Delta
q/\sqrt{2\epsilon}$ where $\alpha$ is a parameter determined by $\epsilon$ and
$\delta$ (Balle and Wang, 2018).

DP mechanisms involve errors in the query answer. A common and popular utility
function for numerical query answers is the expected mean squared error (MSE),
defined as follows:

###### Definition 0 (Query Utility).

For a query $q:\mathcal{D}\rightarrow\mathbb{R}^{d}$ and a mechanism
$\mathcal{M}:\mathcal{D}\rightarrow\mathbb{R}^{d}$, the query utility of
mechanism $\mathcal{M}$ is measured as the expected squared error,
$v=\mathbb{E}[q(D)-\mathcal{M}(D)]^{2}$
$=\sum_{i=1}^{n}(q(D)[i]-\mathcal{M}(D)[i])^{2}$. For the (analytic) Gaussian
mechanism, the expected squared error equals its variance, that is,
$v=d\sigma^{2}$.

##  3\. Problem Setup

We consider a new multi-analyst setting, where there are multiple data
analysts $\mathcal{A}=\\{A_{1},\dots,A_{m}\\}$ who want to ask queries on the
database $D$. The administrator who manages the database wants to ensure that
the sensitive data is properly and privately shared with the data analysts
$A_{1},\dots,A_{m}$. In our threat model, the data analysts can adaptively
select and submit arbitrary queries to the system to infer sensitive
information about individuals in the protected database. Additionally, in our
multi-analyst model, data analysts may submit the same query and collude to
learn more information about the sensitive data.

In practice, data analysts have varying privilege levels, which the standard
DP does not consider. An analyst with a higher privilege level is allowed more
information than an analyst with a lower privilege level. This motivates us to
present the following variant of DP that supports the privacy per analyst
provenance framework and guarantees different levels of privacy loss to the
analysts.

###### Definition 0 (Multi-analyst DP).

We say a randomized mechanism
$\mathcal{M}:\mathcal{D}\rightarrow(\mathcal{O}_{1},\ldots,\mathcal{O}_{m})$
satisfies
$[(A_{1},\epsilon_{1},\delta_{1}),...,(A_{m},\epsilon_{m},\delta_{m})]$-multi-
analyst-DP if for any neighbouring databases $(D,D^{\prime})$, any $i\in[m]$,
and all $O_{i}\subseteq\mathcal{O}_{i}$, we have

$\Pr[\mathcal{M}(D)\in O_{i}]\leq
e^{\epsilon_{i}}\Pr[\mathcal{M}(D^{\prime})\in O_{i}]+\delta_{i},$

where $O_{i}$ are the outputs released to the $i$th analyst.

The multi-analyst DP variant supports the composition across different
algorithms, as indicated by the following theorem.

###### Theorem 3.2 (Multi-Analyst DP Composition).

Given two randomized mechanisms $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, where
$\mathcal{M}_{1}:\mathcal{D}\rightarrow(\mathcal{O}_{1},\ldots,\mathcal{O}_{m})$
satisfies
$[(A_{1},\epsilon_{1},\delta_{1}),...,(A_{m},\epsilon_{m},\delta_{m})]$-multi-
analyst-DP, and
$\mathcal{M}_{2}:\mathcal{D}\rightarrow(\mathcal{O}_{1}^{\prime},\ldots,\mathcal{O}_{m}^{\prime})$
satisfies
$[(A_{1},\epsilon_{1}^{\prime},\delta_{1}^{\prime}),...,(A_{m},\epsilon_{m}^{\prime},\delta_{m}^{\prime})]$-multi-
analyst-DP, then the mechanism $g(\mathcal{M}_{1},\mathcal{M}_{2})$ gives the
$[(A_{1},\epsilon_{1}+\epsilon_{1}^{\prime},\delta_{1}+\delta_{1}^{\prime}),...,(A_{m},\epsilon_{m}+\epsilon_{m}^{\prime},\delta_{m}+\delta_{m}^{\prime})]$-multi-
analyst-DP guarantee.

Unlike prior DP work for multiple data analysts, our setup considers data
analysts who are obliged under laws/regulations should not share their privacy
budget/query responses with each other. We provide a detailed discussion on
comparing other work in Section 8.

Under our new multi-analyst DP framework, several, natural but less well-
understood, research questions (RQs) are raised and problem setups are
considered of potential interest.

RQ 1: worst-case privacy analysis across analysts. Under this multi-analyst DP
framework, what if all data analysts collude or are compromised by an
adversary, how could we design algorithms to account for the privacy loss to
the colluded analysts? When this happens, we can obtain the following trivial
lower bound and upper bound for the standard DP measure.

###### Theorem 3.3 (Compromisation Lower/Upper Bound, Trivial).

Given a mechanism $\mathcal{M}$ that satisfies
$[(A_{1},\epsilon_{1},\delta_{1}),...,$
$(A_{n},\epsilon_{n},\delta_{n})]$-multi-analyst-DP, when all data analysts
collude, its DP loss is (i) lowered bounded by
$(\max\epsilon_{i},\max\delta_{i})$, where $(\epsilon_{i},\delta_{i})$ is the
privacy loss to the $i$-th analyst, and (ii) trivially upper bounded by
$(\sum\epsilon_{i},\sum\delta_{i})$.

The lower bound indicates the least amount of information that has to be
released (to the analyst) and this upper bound is simply derived from
sequential composition. Obviously, the trivial upper bound does not match the
lower bound, rendering the question of designing multi-analyst DP mechanisms
to close the gap. Closing this gap means _even if these data analysts break
the law and collude, the overall privacy loss of the multi-analyst DP
mechanism is still minimized._ In this paper, we would like to design such
algorithms that achieve the lower bound, as shown in Section 5.

RQ 2: dynamic budget allocation across views.  The DP query processing system
should impose constraints on the total privacy loss by all the analysts (in
the worst case) and the privacy loss per analyst. When handling incoming
queries, prior work either dynamically allocates the privacy budget based on
the budget request per query (McSherry, 2009; Johnson et al., 2018) or query
accuracy requirements (Ge et al., 2019) or predefine a set of static DP views
that can handle the incoming queries (Kotsogiannis et al., 2019a).

The dynamic budget per query approach can deplete the privacy budget quickly
as each query is handled with a fresh new privacy budget. The static views
spend the budget in advance among them to handle unlimited queries, but they
may fail to meet the accuracy requirements of some future queries. Therefore,
in our work, we consider the view approach but assign budgets dynamically to
the views based on the incoming queries so that more queries can be answered
with their accuracy requirements. Specifically, we would like to use the
histogram view, which queries the number of tuples in a database for each
possible value of a set of attributes. The answer to a view is called a
synopsis. We consider a set of views that can answer all incoming queries.

###### Definition 0 (Query Answerability (Kotsogiannis et al., 2019a)).

For a query $q$ over the database $D$, if there exists a query $q^{\prime}$
over the histogram view $V$ such that $q(D)=q(V(D))$, we say that $q$ is
answerable over $V$.

###### Example 3.5.

Consider two queries $q_{1}$ and $q_{2}$ over a database for employees in
Figure 1. They are answerable over the $V_{1}$, a 3-way marginal contingency
table over attributes (age, gender, education), via their respective
transformed queries $\hat{q}_{1}$ and $\hat{q}_{2}$.

Given a set of views, we would like to design algorithms that can dynamically
allocate privacy budgets to them and update their corresponding DP synopses
over time. We show how these algorithms maximize the queries that can be
handled accurately in Section 5. Since we can dynamically allocate budget to
views, our system can add new views to the system as overtime. We discuss this
possibility in Section 5.3.

RQ 3: fair query answering among data analysts. A fair system expects data
analysts with higher privacy privileges to receive more accurate answers or
larger privacy budgets than ones with lower privacy privileges. However,
existing DP systems make no distinctions among data analysts. Hence, it is
possible that a low-privilege external analyst who asks queries first consumes
all the privacy budget and receives more accurate query answers, leaving no
privacy budgets for high-privilege internal data analysts. It is also
impossible to force data analysts to ask queries in a certain order. In this
context, we would like the system to set up the (available and consumed)
privacy budgets for data analysts according to their privacy privilege level.
In particular, we define privacy privilege levels as an integer in the range
of 1 to 10, where a higher number represents a higher privilege level. We also
define a fairness notion inspired by the literature on resource allocation
(Kelly et al., 1998; Banerjee et al., 2023; Stoyanovich et al., 2018).

###### Definition 0 (Proportional Fairness).

Consider a DP system handling a sequence of queries $Q$ from multiple data
analysts with a mechanism $\mathcal{M}$, where each data analyst $A_{i}$ is
associated with a privilege level $l_{i}$. We say the mechanism $\mathcal{M}$
satisfies proportional fairness, if $\forall A_{i},A_{j}$ ($i\neq j$),
$l_{i}\leq l_{j}$, we have

$\frac{Err_{i}(M,A_{i},Q)}{\mu(l_{i})}\leq\frac{Err_{j}(M,A_{j},Q)}{\mu(l_{j})},$

where $Err_{i}(M,A_{i},Q)$ denotes the analyst $A_{i}$’s privacy budget
consumption and $\mu(\cdot)$ is some linear function.

This fairness notion suggests the quality of query answers to data analysts,
denoted by $Err_{i}(M,A_{i},Q)$ is proportional to their privilege levels,
denoted by a linear function $\mu(\cdot)$ of their privilege levels. We first
consider the privacy budget per data analyst as the quality function, as a
smaller error to the query answer is expected with a larger privacy budget. We
show in Section 5.3 how to set up the system to achieve fairness when the
analysts ask a sufficient number of queries, which means they finish consuming
their assigned privacy budget.

##  4\. System overview

In this section, we outline the key design principles of DProvDB and briefly
describe the modules of the system.

###  4.1. Key Design Principles

To support the multi-analyst use case and to answer the aforementioned
research questions, we identify the four principles and propose a system
DProvDB that follows these principles.

Principle 1: fine-grained privacy provenance. The query processing system
should be able to track the privacy budget allocated per each data analyst and
per each view in a fine-grained way. The system should additionally enable a
mechanism to compose privacy loss across data analysts and the queries they
ask.

Principle 2: view-based privacy management. The queries are answered based on
DP views or synopses. Compared to directly answering a query from the database
$D$, view-based query answering can answer more private queries (Kotsogiannis
et al., 2019a), but it assumes the accessibility of a pre-known query
workload. In our system, the view is the minimum data object that we keep
track of its privacy loss, and the views can be updated dynamically if higher
data utility is required. The privacy budgets spent on different views during
the updating process depend on the incoming queries.

Principle 3: dual query submission mode. Besides allowing data analysts to
submit a budget with their query, the system enables an accuracy-aware mode.
With this mode, data analysts can submit the query with their desired accuracy
levels regarding the expected squared error. The dual mode system supports
data analysts from domain experts, who can take full advantage of the budgets,
to DP novices, who only care about the accuracy bounds of the query.

Principle 4: maximum query answering. The system should be tuned to answer as
many queries accurately as possible without violating the privacy constraint
specified by the administrator as per data analyst and per view based on their
privilege levels.

Figure 1. Illustration of the Histogram View, the Query Transformation and the
Privacy Provenance Table: 1 Histogram view $V_{1}$ over age, gender, and
education is built on the database snapshot; 2 Forthcoming queries $q_{1}$ and
$q_{2}$ are transformed into linearly answerable queries $\hat{q}_{1}$ and
$\hat{q}_{2}$ over $V_{1}$; 3 Analysts ($A_{1},A_{2}$ with low, $A_{3}$ with
high privilege) are recorded in the provenance table – the privacy loss for
each view to each analyst is tracked for real-time queries.

###  4.2. Privacy Provenance Table

To meet the first two principles, we propose a privacy provenance table for
DProvDB, inspired by the access matrix model in access control literature (di
Vimercati, 2011), to track the privacy loss per analyst and per view, and
further bound the privacy loss. Particularly, in our model, the state of the
overall privacy loss of the system is defined as a triplet
$(\mathcal{A},\mathcal{V},\mathcal{P})$, where $\mathcal{A}$ denotes the set
of data analysts and $\mathcal{V}$ represents the list of query-views
maintained by the system. We denote by $\mathcal{P}$ the privacy provenance
table, defined as follows.

###### Definition 0 (Privacy Provenance Table).

The privacy provenance table $\mathcal{P}$ consists of (i) a provenance matrix
$P$ that tracks the privacy loss of a view in $\mathcal{V}$ to each data
analyst in $\mathcal{A}$, where each entry of the matrix $P[A_{i},V_{j}]$
records the current cumulative privacy loss $S^{A_{i}}_{V_{j}}$, on view
$V_{j}$ to analyst $A_{i}$; (ii) a set of row/column/table constraints,
$\Psi$: a _row constraint_ for $i$-th row of $P$, denoted by $\psi_{A_{i}}$,
refers to the allowed maximum privacy loss to a data analyst
$A_{i}\in\mathcal{A}$ (according to his/her privilege level); a _column
constraint_ for the $j$-th column, denoted by $\psi_{V_{j}}$ refers to as the
allowed maximum privacy loss to a specific view $V_{j}$; the _table
constraint_ over $P$, denoted by $\psi_{P}$, specifies the overall privacy
loss allowed for the protected database.

The privacy constraints and the provenance matrix are correlated. In
particular, the row/column constraints cannot exceed the overall table
constraint, and each entry of the matrix cannot exceed row/column constraints.
The correlations, such as the composition of the privacy constraints of all
views or all analysts, depend on the DP mechanisms supported by the system. We
provide the details of DP mechanisms and the respective correlations in
privacy provenance table in Section 5.

###### Example 4.2.

Figure 1 gives an example of the privacy provenance table for $n$ views and
$m$ data analysts. When DProvDB receives query $q_{1}$ from Bob, it plans to
use view $V_{1}$ to answer it. DProvDB first retrieves the previous cumulative
cost of $V_{1}$ to Bob from the matrix, $P[Bob,V_{1}]$, and then computes the
new cumulative cost $S_{V_{1}}^{Bob}$ for $V_{1}$ to Bob as if it answers
$q_{1}$ using $V_{1}$. If the new cost $S_{V_{1}}^{Bob}$ is smaller than Bob’s
privacy constraint $\psi_{Bob}$, the view constraint $\psi_{V_{1}}$, and the
table constraint $\psi_{P}$, DProvDB will answer $q_{1}$ and update
$P[Bob,V_{1}]$ to $S_{V_{1}}^{Bob}$; otherwise, $q_{1}$ will be rejected.

Due to the privacy constraints imposed by the privacy provenance table,
queries can be rejected when the cumulative privacy cost exceeds the
constraints. DProvDB needs to design DP mechanisms that well utilize the
privacy budget to answer more queries. Hence, we formulate the _maximum query
answering problem_ based on the privacy provenance table.

###### Problem 1.

Given a privacy provenance table $(\mathcal{A},\mathcal{V},\mathcal{P})$, at
each time, a data analyst $A_{i}\in\mathcal{A}$ submits the query with a
utility requirement $(q_{i},v_{i})$, where the transformed
$\hat{q}_{i}\in\mathcal{V}$, how can we design a system to answer as many
queries as possible without violating the row/column/table privacy constraints
in $P$ while meeting the utility requirement per query?

Hence we would like to build an efficient system to satisfy the aforementioned
design principles and enable the privacy provenance table, and develop
algorithms to solve the maximum query answering problem in DProvDB. We next
outline the system modules in DProvDB, and then provide detailed algorithm
design in Section 5.

###  4.3. System Modules

The DProvDB system works as a middle-ware between data analysts and existing
DP DBMS systems (such as PINQ, Chorus, and PrivateSQL) to provide intriguing
and add-on functionalities, including fine-grained privacy tracking,
view/synopsis management, and privacy-accuracy translation. We briefly
summarize the high-level ideas of the modules below.

Privacy Provenance Tracking. DProvDB maintains the privacy provenance table
for each registered analyst and each generated view, as introduced in Section
4.2. Constraint checking is enabled based on this provenance tracking to
decide whether to reject an analyst’s query or not. We further build DP
mechanisms to maintain and update the DP synopses and the privacy provenance
table.

Dual Query Submission Mode. DProvDB provides two query submission modes to
data analysts. Privacy-oriented mode (McSherry, 2009; Johnson et al., 2018,
2020; Zhang et al., 2018): queries are submitted with a pre-apportioned
privacy budget, i.e., $(A_{i},q_{i},\\{\epsilon_{i},\delta_{i}\\})$. Accuracy-
oriented mode (Ge et al., 2019; Vesga et al., 2020): analysts can write the
query with a desired accuracy bound, i.e., queries are in form of
$(A_{i},q_{i},v_{i})$. We illustrate our algorithm with the accuracy-oriented
mode.

Input: Analysts $\mathcal{A}\coloneqq A_{1},\dots,A_{n}$; Database instance
$D$; Privacy provenance table $\mathcal{P}=(P,\Psi)$.

1

2Administrator sets up the privacy provenance table $\mathcal{P}$

3Initialize all the synopses for $V\in\mathcal{V}$

4

5Set $\delta$ in the system

6

7repeat

8 Receive $(q_{i},v_{i})$ from data analyst $A_{i}$

9 Select view $V\in\mathcal{V}$ to answer query $q_{i}$

10 Select mechanism $M\in\mathcal{M}$ applicable to $q_{i}$

11

12 $\epsilon_{i}\leftarrow$ M.privacyTranslate($q_{i},v_{i},V,p$)

13

14 if  __M.constraintCheck(_ $P,A_{i},V,\epsilon_{i},\Psi$_)__ then

15

16 $V_{A_{i}}^{\epsilon^{\prime}}\leftarrow$M.run($P,A_{i},V,\epsilon_{i}$)

17 Answer $q_{i}$ with $V_{A_{i}}^{\epsilon^{\prime}}$ and return answer
$r_{i}$ to $A_{i}$

18 else

19 reject the query $q_{i}$

20 end if

21

22until  _No more queries sent by analysts_

Algorithm 1 System Overview

Algorithm Overview. Algorithm 1 summarizes how DProvDB uses the DP synopses to
answer incoming queries. At the system setup phase (line 1-3), the
administrator initializes the privacy provenance table by setting the matrix
entry as 0 and the row/column/table constraints $\Psi$. The system initializes
empty synopses for each view. The data analyst specifies a query $q_{i}$ with
its desired utility requirement $v_{i}$ (line 5). Once the system receives the
request, it selects the suitable view and mechanism to answer this query (line
6-7) and uses the function privacyTranslate() to find the minimum privacy
budget $\epsilon_{i}$ for $V$ to meet the utility requirement of $q_{i}$ (line
8). Then, DProvDB checks if answering $q_{i}$ with budget $\epsilon_{i}$ will
violate the privacy constraints $\Psi$ (Line 9). If this constraint check
passes, we run the mechanism to obtain a noisy synopsis (line 10). DProvDB
uses this synopsis to answer query $q_{i}$ and returns the answer to the data
analyst (line 11). If the constraint check fails, DProvDB rejects the query
(line 13). We show concrete DP mechanisms with their corresponding interfaces
in the next section.

Remark. For simplicity, we drop $\delta$ and focus on $\epsilon$ as privacy
loss/budget in privacy composition, but $\delta$’s of DP synopses are
similarly composited as stated in Theorem 3.2. For the accuracy-privacy
translation, we consider a fixed given small delta and aim to find the
smallest possible epsilon to achieve the accuracy specification of the data
analyst.

##  5\. DP Algorithm Design

In this section, we first describe a vanilla DP mechanism that can instantiate
the system interface but cannot maximize the number of queries being answered.
Then we propose an additive Gaussian mechanism that leverages the correlated
noise in query answering to improve the utility of the vanilla mechanism.
Without loss of generality, we assume the data analysts do not submit the same
query with decreased accuracy requirement (as they would be only interested in
a more accurate answer).

###  5.1. Vanilla Approach

1

2Set $\delta$ in the system

3 Function  __run(_ $P,A_{i},V,\epsilon_{i}$_)_ _ :

4 Generate a synopsis $V_{A_{i}}^{\epsilon_{i}}$ from view $V$

5 Update privacy provenance table $P[A_{i},V]\leftarrow
P[A_{i},V]+\epsilon_{i}$

6 return $r_{i}\leftarrow V_{A_{i}}^{\epsilon_{i}}$

7 end

8Function  __privacyTranslate(_ $q_{i},v_{i},V,p$_)_ _ :

9 Set $u=\psi_{P},~{}l=0$

10 $v\leftarrow$ calculateVariance($q_{i},v_{i},V$)

11 $\epsilon=$ binarySearch($l,u,$testAccuracy($\cdot,v,\Delta q_{i},\delta$),
$p$)

12 return $\epsilon$

13 end

14Function  __constraintCheck(_ $P,A_{i},V_{j},\epsilon_{i},\Psi$_)_ _ :

15

16 if  _$(P$._composite()_ \+ $\epsilon_{i}\leq\Psi.\psi_{P})\land$
$(P$._composite(_ axis=Row _)_ \+ $\epsilon_{i}\leq\Psi.\psi_{A_{i}})\land$
$(P$._composite(_ axis=Column _)_ \+ $\epsilon_{i}\leq\Psi.\psi_{V_{j}})$_
then

17 return True/Pass

18

19 end

Algorithm 2 Vanilla Approach

The vanilla approach is based on the Gaussian mechanism (applied to both the
basic Gaussian mechanism (Dwork and Roth, 2014) and the analytic Gaussian
mechanism (Balle and Wang, 2018)). We describe how the system modules are
instantiated with the vanilla approach.

####  5.1.1. Accuracy-Privacy Translation

This module interprets the user-specified utility requirement into the minimum
privacy budget (Algorithm 2: line 2-2). Note that instead of perturbing the
query result to $q_{i}$ directly, we generate a noisy DP synopsis and use it
to answer a query (usually involving adding up a number of noisy counts from
the synopsis). Hence, we need to translate the accuracy bound $v_{i}$
specified by the data analyst over the query to the corresponding accuracy
bound $v$ for the synopsis before searching for the minimal privacy budget
(Algorithm 2: line 2). Here, $v$ represents the variance of the noise added to
each count of the histogram synopsis. Next, we search for the minimal privacy
budget $\epsilon$ that results in a noisy synopsis with noise variance not
more than $v$, based on the following analytic Gaussian translation.

###### Definition 0 (Analytic Gaussian Translation).

Given a query $q:\mathcal{D}\rightarrow\mathbb{R}^{d}$ to achieve an expected
squared error bound $v$ for this query, the minimum privacy budget for the
analytic Gaussian mechanism should satisfy
$\Phi_{\mathcal{N}}\left(\frac{\Delta q}{2v}-\frac{\epsilon v}{\Delta
q}\right)-e^{\epsilon}\Phi_{\mathcal{N}}\left(-\frac{\Delta
q}{2v}-\frac{\epsilon v}{\Delta q}\right)\leq\delta.$ That is, given $\Delta
q,\delta,v$, to solve the following optimization problem to find the minimal
$\epsilon$.

(1) $\displaystyle\min_{\epsilon\in(0,\psi_{P}]}\epsilon\mbox{ s.t.
}\Phi_{\mathcal{N}}\left(\frac{\Delta q}{2v}-\frac{\epsilon v}{\Delta
q}\right)-e^{\epsilon}\Phi_{\mathcal{N}}\left(-\frac{\Delta
q}{2v}-\frac{\epsilon v}{\Delta q}\right)\leq\delta$

Finding a closed-form solution to the problem above is not easy. However, we
observe that the LHS of the constraint in Equation (1) is a monotonic function
of $\epsilon$. Thus, we use binary search (Algorithm 2: line 2) to look for
the smallest possible value for $\epsilon$. For each tested value of
$\epsilon$, we compute its analytic Gaussian variance (Balle and Wang, 2018),
denoted by $v^{\prime}$. If $v^{\prime}>v$, then this value is invalid and we
search for a bigger epsilon value; otherwise, we search for a smaller one. We
stop at an epsilon value with a variance $v^{\prime}\leq v$ and a distance $p$
from the last tested invalid epsilon value. We have the following guarantee
for this output.

###### Proposition 5.2 (Correctness of Translation).

Given a query $(q_{i},v_{i})$ and the view $V$ for answering $q_{i}$, the
translation function (Algorithm 2, privacyTranslation) outputs a privacy
budget $\epsilon$. The query $q_{i}$ can then be answered with expected square
error $v_{q}$ over the updated synopsis $V^{\epsilon}_{A}$ such that: i) meets
the accuracy requirement $v_{q}\leq v_{i}$, and ii) $\epsilon-\epsilon^{*}\leq
p$, where $\epsilon^{*}$ is the minimal privacy budget to meet the accuracy
requirement for Algorithm 2 (run function).

###### Proof Sketch.

First, line 2 derives the per-bin accuracy requirement based on the submitted
per-query accuracy, and plugs it into the search condition (Equation (1)).
Note that our DP mechanism and the accuracy requirement are data-independent.
As long as the searching condition holds, the noise added to the query answer
in run satisfies $v_{q}\leq v_{i}$. Second, the stopping condition of the
search algorithm guarantees 1) there is a solution, 2) the searching range is
reduced to $\leq p$. Thus we have $\epsilon-\epsilon^{*}\leq p$. ∎

####  5.1.2. Provenance Constraint Checking

As mentioned, the administrator can specify privacy constraints in privacy
provenance table. DProvDB decide whether _reject or answer a query_ using the
provenance matrix $P$ and the privacy constraints $\Psi$ in privacy provenance
table, as indicated in Algorithm 2: 2-2 (the function constraintCheck). This
function checks whether the three types of constraints would be violated when
the current query was to issue. The composite function in this constraint-
checking algorithm can refer to the basic sequential composition or tighter
privacy composition given by Renyi-DP (Mironov, 2017) or zCDP (Dwork and
Rothblum, 2016; Bun and Steinke, 2016). We suggest to use advanced composition
for accounting privacy loss over time, but not for checking constraints,
because the size of the provenance table $n*m$ is too small for a tight bound
by this composition.

####  5.1.3. Putting Components All Together

The vanilla approach is aligned with existing DP query systems in the sense
that it adds independent noise to the result of each query. Hence, it can be
quickly integrated into these systems to provide privacy provenance and
accuracy-aware features with little overhead. Algorithm 2: 2-2 (the function
run) outlines how the vanilla method runs. It first generates the DP synopsis
$V^{\epsilon_{i}}_{A_{i}}$ using analytic Gaussian mechanism for the chosen
view $V$ and updates the corresponding entry $P[A_{i},V]$ in the privacy
provenance table by compositing the consumed privacy loss
$(\epsilon_{i},\delta_{i})$ on the query (depending on the specific
composition method used). We defer the analysis for the accuracy and privacy
properties of the vanilla mechanism to Section 5.4.

###  5.2. Additive Gaussian Approach

While ideas of using correlated Gaussian noise have been exploited (Li et al.,
2012), we adopt similar statistical properties into an additive Gaussian DP
mechanism, a primitive to build our additive Gaussian approach for synopses
maintenance. Then, we describe how DProvDB generates and updates the (local
and global) DP synopses with this algorithm across analysts and over time.

####  5.2.1. Additive Gaussian Mechanism

The additive Gaussian mechanism (additive GM or aGM) modifies the standard
Gaussian mechanism, based on the nice statistical property of the Gaussian
distribution — the sum of i.i.d. normal random variables is still normally
distributed. We outline this primitive mechanism in Algorithm 3. This
primitive takes a query $q$, a database instance $D$, a set of privacy budgets
$\mathcal{B}$ corresponding to the set of data analysts $\mathcal{A}$ as
input, and this primitive outputs a noisy query result to each data analyst
$A_{i}$, which consumes the corresponding privacy budget
$(\epsilon_{i},\delta)$. Its key idea is only to execute the query (to get the
true answer on the database) once, and cumulatively inject noises to previous
noisy answers, when multiple data analysts ask the same query. In particular,
we sort the privacy budget set specified by the analysts. Starting from the
largest budget, we add noise w.r.t the Gaussian variance $\sigma_{i}^{2}$
calculated from the query sensitivity $\Delta q$ and this budget
$(\epsilon_{i},\delta)$. For the rest of the budgets in the set, we calculate
the Gaussian variance $\sigma_{j}^{2}$ in the same approach but add noise
w.r.t $\sigma_{j}^{2}-\sigma_{i}^{2}$ to the previous noisy answer. The
algorithm then returns the noisy query answer to each data analyst. The
privacy guarantee of this primitive is stated as follows.

Input: Analysts $\mathcal{A}\coloneqq A_{1},\dots,A_{n}$; A query $q$;
Database instance $D$; A set of privacy budgets
$\mathcal{B}{\coloneqq\\{\mathcal{E},\mathcal{D}\\}=}(\epsilon_{1},\delta),(\epsilon_{2},\delta),\dots,(\epsilon_{n},\delta)$.

Output: A set of noisy answers $r_{1},r_{2},\dots,r_{n}$.

1 Function  __additiveGM(_ $\mathcal{A},\mathcal{B},q,D$_)__ :

2 $r\leftarrow$ queryExec($q,D$) $\triangleright$ Obtain true query answer.

3 $\Delta q\leftarrow$ sensCalc($q$) $\triangleright$ Sensitivity calculation.

4 $\mathcal{B}^{\prime}\leftarrow$ sort($\mathcal{B},\epsilon_{i}$)
$\triangleright$ Sort $\mathcal{B}$ on the desc order of $\epsilon$’s.

5 $(\epsilon_{i},\delta)\leftarrow$ pop($\mathcal{B}^{\prime}$)
$\triangleright$ Pop the 1st element.

6 $\sigma_{i}\leftarrow$ analyticGM($\epsilon_{i},\delta,\Delta q$)
$\triangleright$ (Balle and Wang, 2018)

7 $r_{i}\leftarrow r+\eta_{i}\sim\mathcal{N}(0,\sigma_{i}^{2})$
$\triangleright$ Add Gaussian noise.

8 while  _$\mathcal{B}^{\prime}\neq\varnothing$_ do

9 $(\epsilon_{j},\delta)\leftarrow$ pop($\mathcal{B}^{\prime}$)

10 $\sigma_{j}\leftarrow$ analyticGM($\epsilon_{j},\delta,\Delta q$)
$\triangleright$ (Balle and Wang, 2018)

11 $r_{j}\leftarrow
r_{i}+\eta_{j}\sim\mathcal{N}(0,\sigma_{j}^{2}-\sigma_{i}^{2})$;

12 end while

13 return $\mathcal{R}\coloneqq\\{r_{i}|i\in[n]\\}$;

14 end

Algorithm 3 Additive Gaussian Noise Calibration

###### Theorem 5.3.

Given a database $D$, a set of privacy budgets
$\mathcal{B}\coloneqq(\epsilon_{1},\delta),(\epsilon_{2},\delta),\dots,(\epsilon_{n},\delta)$
and a query $q$, the additive Gaussian mechanism (Algorithm 4) that returns a
set of noisy answers $r_{1},r_{2},\dots,r_{n}$ to each data analyst $A_{i}$
satisfies $[(A_{1},\epsilon_{1},\delta),...,$
$(A_{n},\epsilon_{n},\delta)]$-multi-analyst-DP and
$(\max\\{\epsilon_{1},\dots,\epsilon_{n}\\},\delta)$-DP.

###### Proof Sketch.

To each data analyst $A_{i}$, the DP mechanism is equivalent to the standard
Gaussian mechanism with a proper variance that satisfies
$(\epsilon_{i},\delta)$-DP. Since the data is looked at once, the
$(\max\\{\epsilon_{1},\dots,\epsilon_{n}\\},\delta)$-DP is guaranteed by post-
processing. ∎

Discussion on $\delta$. If the $\delta$ is not a fixed parameter in the
system, it could happen in privacy budget $(\epsilon_{i},\delta_{i})$ that
$\epsilon_{i}=\max\mathcal{E}$ but $\delta_{i}=\min\mathcal{D}$. Algorithm 3
can be simply modified to handle this by not sorting $\mathcal{B}$ based on
descending $\epsilon$’s (line 3) but according to the ascending order of the
calculated $\sigma$ (line 3).

####  5.2.2. Synopses Management

We introduce the concept of global and local DP synopses and then discuss the
updating process in our additive GM. A DP synopsis (or synopsis for short) is
a noisy answer to a (histogram) view over a database instance. We first use
the privacy-oriented mode to explain the synopses management for clarity, and
then elaborate the accuracy-oriented mode in the accuracy-privacy translation
module (Section 5.2.3).

Global and Local DP Synopses. To solve the maximum query answering problem,
for each view $V\in\mathcal{V}$, DProvDB maintains a _global DP synopsis_ with
a cost of $(\epsilon,\delta)$, denoted by $V^{\epsilon,\delta}(D)$ or
$V^{\epsilon}$, where $D$ is the database instance. For simplicity, we drop
$\delta$ by considering the same value for all $\delta$ and $D$. For this
veiw, DProvDB also maintains a _local DP synopsis_ for each analyst
$A_{i}\in\mathcal{A}$, denoted by $V_{A_{i}}^{\epsilon^{\prime}}$, where the
local synopsis is always generated from the global synopsis $V^{\epsilon}$ of
the view $V$ by adding more noise. Hence, we would like to ensure
$\epsilon\geq\epsilon^{\prime}$. This local DP synopsis
$V_{A_{i}}^{\epsilon^{\prime}}$ will be used to answer the queries asked by
the data analyst $A_{i}$.

The process of updating synopses consists of two parts. The first part is to
update the local synopses based on the global synopses. The second part is to
update the global synopses by relaxing the privacy guarantee, in order to
answer a query with a higher accuracy requirement. We discuss the details
below.

Generating Local Synopses from Global Synopses. We leverage our additive GM
primitive to release a local DP synopsis $V_{A_{i}}^{\epsilon^{\prime}}$ from
a given global synopsis $V^{\epsilon}$, where $V^{\epsilon}$ is generated by a
Gaussian mechanism. Given the privacy guarantee $\epsilon$ (and $\delta$) and
the sensitivity of the view, the Gaussian mechanism can calculate a proper
variance $\sigma^{2}$ for adding noise and ensuring DP. The additive GM
calculates $\sigma^{2}$ and $\sigma^{\prime 2}$ based on $\epsilon$ and
$\epsilon^{\prime}$ respectively, and then generates the local synopsis
$V_{A_{i}}^{\epsilon^{\prime}}$ by injecting independent noise drawn from
$\mathcal{N}(0,\sigma^{\prime 2}-\sigma^{2})$ to the global synopsis
$V^{\epsilon}$. As the global synopsis is hidden from all the analysts, the
privacy loss to the analyst $A_{i}$ is $\epsilon^{\prime}$. Even if all the
analysts collude, the maximum privacy loss is bounded by the budget spent on
the global synopsis.

Figure 2. Illustration of the Additive Gaussian Approach

###### Example 5.4.

Alice and Bob are asking queries to DProvDB. Alice asks the first query
$q_{1}$ (which is answerable on $V_{1}$) with _budget requirement_
$\epsilon_{V_{1},Alice}=0.5$. DProvDB generates a global synopsis $V^{0.5}$
for $V$ with budget 0.5 and then generate a local synopsis $V^{0.5}_{Alice}$
from the global synopsis $V^{0.5}$ for Alice. Bob next asks query $q_{2}$
(which is also answerable on $V_{1}$) with budget $\epsilon_{V_{1},Bob}=0.3$.
Since the budget $0.3<0.5$, we use the additive GM to generate a local
synopsis $V^{0.3}_{Bob}$ from the global synopsis $V^{0.5}$ for Bob and return
the query answer based on the local synopsis $V^{0.3}_{Bob}$. This example
follows “Case 1” in Fig. 2.

Updating Global Synopses by Combining Views. When the global DP synopsis
$V^{\epsilon}$ is not sufficiently accurate to handle a local synopsis request
at privacy budget $\epsilon_{t}$, DProvDB spends additional privacy budget
$\Delta\epsilon$ to update the global DP synopsis to
$V^{\epsilon+\Delta\epsilon}$, where $\Delta\epsilon=\epsilon_{t}-\epsilon$.
We still consider Gaussian mechanism, which generates an intermediate DP
synopsis $V^{\Delta\epsilon}$ with a budget $\Delta\epsilon$. Then we combine
the previous synopses with this intermediate synopsis into an updated one. The
key insight of the combination is to properly involve the fresh noisy synopses
by assigning each synopsis with a weight proportional to the inverse of its
noise variance, which gives the smallest expected square error based on UMVUE
(Kiefer, 1952; Rao, 1949). That is, for the $t$-th release, we combine these
two synopses:

(2) $V^{\epsilon_{t}}=(1-w_{t})V^{\epsilon_{t-1}}+w_{t}V^{\Delta\epsilon}.$

The resulted expected square error for $V^{\epsilon_{t}}$ is
$v_{t}=(1-w_{t})^{2}v_{t-1}+w_{t}^{2}v_{\Delta}$, where $v_{t-1}$ is the noise
variance of view $V^{\epsilon_{t-1}}$, and $v_{\Delta}$ is derived from
$V^{\Delta\epsilon}$. To minimize the resulting error,
$w_{t}=\frac{v_{t-1}}{v_{\Delta}+v_{t-1}}$.

###### Example 5.5.

At the next time stamp, Bob asks a query $q_{1}$ with budget
$\epsilon_{V_{1},Bob}=0.7$. Clearly the current global synopsis $V^{0.5}$ is
not sufficient to answer this query because $0.7>0.5$. Then the system needs
to update $V^{0.5}$ and this is done by: 1) first generating a fresh global
synopsis $V^{0.2}$ using analytic GM from $V(D)$; 2) then combining it with
$V^{0.5}$ to form $V^{0.7}$ using Equation (2). This example is illustrated as
steps 2a and 2b of “Case 2” in Fig. 2.

###### Lemma 5.6 (Correctness of View Combination).

Releasing the combined DP synopsis in the $t$-th update is
$(\epsilon_{t-1}+\Delta\epsilon,\delta_{t-1}+\Delta\delta)$-DP.

###### Proof Sketch.

The $t$-th update combines an $(\epsilon_{t-1},\delta_{t-1})$-DP synopsis and
a fresh synopsis that is $(\Delta\epsilon,\Delta\delta)$-DP. By sequential
composition, the combined synopsis is
$(\epsilon+\Delta\epsilon,\delta+\Delta\delta)$-DP. ∎

The view combination is not _frictionless_. Although the combined synopsis
$V^{\epsilon+\Delta\epsilon}$ achieves
$(\epsilon+\Delta\epsilon,\delta+\Delta\delta)$-DP, if we spend the whole
privacy budget on generating a synopsis all at once, this one-time synopsis
$V^{*}$ has the same privacy guarantee but is with less expected error than
$V^{\epsilon+\Delta\epsilon}$. We can show by sequentially combining and
releasing synopses over time it is optimal among all possible linear
combinations of synopses, however, designing a frictionless updating algorithm
for Gaussian mechanisms is non-trivial in its own right, which remains for our
future work.

###### Theorem 5.7 (Optimality of Linear View Combination).

Given a sequences of views,
$V^{\epsilon_{1}},V^{\Delta\epsilon_{2}},\ldots,V^{\Delta\epsilon_{t}}$, the
expected squared error of our $t$-th release is less than or equal to that of
releasing
$w_{1}^{\prime}V^{\epsilon_{1}}+\sum_{i=2}^{t}w_{i}^{\prime}V^{\Delta\epsilon_{i}}$
for all $\\{w_{i}\mid i=1,\ldots,t\\}$ s.t. $\sum_{i}w_{i}^{\prime}=1$.

Intuitively, this theorem is proved by a reduction to the best unbiased
estimator and re-normalizing weights based on induction.

Updating Local Synopses and Accounting Privacy. When a local DP synopsis is
not sufficiently accurate to handle a query, but the budget request for this
query $\epsilon_{i}$ is still smaller than or equal to the budget
$\epsilon_{t}$ for the global synopsis of $V$, DProvDB generates a new local
synopsis $V^{\epsilon_{i}}_{A_{i}}$ from $V^{\epsilon_{t}}$ using additive GM.
The analyst $A_{i}$ is able to combine query answers for a more accurate one,
but the privacy cost for this analyst on view $V$ is bounded as
$\min(\epsilon_{t},P[A_{i},V]+\epsilon_{i})$ which will be updated to
$P[A_{i},V]$.

###### Example 5.8.

Analysts’ queries are always answered on local synopses. To answer Bob’s query
$(q_{1},\epsilon_{V_{1},Bob}=0.7)$, DProvDB uses additive GM to generate a
fresh local synopsis $V^{0.7}_{Bob}$ from $V^{0.7}$ and return the answer to
Bob. Alice asks another query $(q_{1},\epsilon_{V_{1},Alice}=0.6)$. DProvDB
updates $V^{0.5}_{Alice}$ by generating $V^{0.6}_{Alice}$ from $V^{0.7}$. Both
analysts’ privacy loss on $V$ will be accounted as $0.7$. This example
complements the illustration of step 2c of “Case 2” in Fig. 2.

####  5.2.3. Accuracy-Privacy Translation

The accuracy translation algorithm should consider the friction at the
combination of global synopses. We propose an accuracy-privacy translation
paradigm (Algorithm 4: 4) involving this consideration. This translator module
takes the query $q_{i}$, the utility requirement $v_{i}$, the synopsis $V$ for
answering the query, and additionally the current global synopsis
$V^{\epsilon}$ (we simplify the interface in Algorithm 1) as input, and
outputs the corresponding budget $\epsilon_{i}$ for run (omitting the same
value $\delta$).

As the first query release for the view does not involve the frictional
updating issue, we separate the translation into two phases where the first
query release directly follows the analytic Gaussian translation in our
vanilla approach. For the second phase, given a global DP synopsis
$V^{\epsilon_{c}}$ at hand (with _tracked_ expected error $v^{\prime}$) for a
specific query-view and a new query is submitted by a data analyst with
expected error ${v_{i}}<v^{\prime}$, we solve an optimization problem to find
the Gaussian variance of the fresh new DP synopsis. We first calculate the
Gaussian variance of the current DP synopsis $v^{\prime}$ (line 4) and solve
the following optimization problem (line 4).

(3)
$\displaystyle\operatorname*{arg\,max}_{\sigma}~{}~{}{v_{i}}=w^{2}v^{\prime}+(1-w)^{2}v_{t}~{}~{}\mbox{
s.t. }w\in[0,1]$

The solution gives us the minimal error variance $v_{t}=\sigma^{2}$ (line 4).
By translating $\sigma^{2}$ into the privacy budget using the standard
analytic Gaussian translation technique (Def. 5.1), we can get the minimum
privacy budget that achieves the required accuracy guarantee (line 4). Note
that when the requested accuracy ${v_{i}}>v^{\prime}$, the solution to this
optimization problem is $w=0$, which automatically degrades to the vanilla
translation.

###### Theorem 5.9.

Given a query $(q_{i},v_{i})$ and the view $V$ for answering $q_{i}$, the
translation function (Algorithm 4, privacyTranslation) outputs a privacy
budget $\epsilon$. The query $q_{i}$ can then be answered with expected square
error $v_{q}$ over the updated synopsis $V^{\epsilon}_{A}$ such that: i) meets
the accuracy requirement $v_{q}\leq v_{i}$, and ii) $\epsilon-\epsilon^{*}\leq
p$, where $\epsilon^{*}$ is the minimal privacy budget to meet the accuracy
requirement for Algorithm 4 (run function).

###### Proof Sketch.

The privacyTranslation in additive Gaussian approach calls the translation
function in the vanilla approach as subroutine (Algorithm 4: 4). The
correctness of the additive Gaussian privacyTranslation depends on inputting
the correct expected square error, which is calculated based on the accuracy
requirement $v_{i}$ while considering the frictions, into the subroutine. The
calculation of the expected squared error with an optimization solver has been
discussed and analyzed above. ∎

1 Set $\delta$ in the system

2 Function  __run(_ $q,\mathcal{P},A_{i},V_{A_{i}},\epsilon_{i}$_)_ _ :

3 if  _$\epsilon_{i} >\epsilon$ for global synopsis $V^{\epsilon}$_ then

4 $\Delta\epsilon=\epsilon_{i}-\epsilon$

5 $V^{\Delta\epsilon}\leftarrow V+\eta\sim\mathcal{N}(0,$
analyticGM($\Delta\epsilon,\delta,1$)${}^{2}I)$

6 Update global synopsis to $V^{\epsilon\leftarrow\epsilon_{i}}$ with
$V^{\Delta\epsilon}$

7

8 $\\_\text{,}~{}V_{A_{i}}^{\epsilon_{i}}\leftarrow$
additiveGM($\\{A_{i},A_{j,V^{\epsilon}=V^{\epsilon}_{A_{j}}}\\},\\{\epsilon_{i},\epsilon\\},q,D$)

9 Update local synopsis to $V_{A_{i}}^{\epsilon_{i}}$

10 Update $P[A_{i},V]\leftarrow\min(\epsilon,P[A_{i},V]+\epsilon_{i})$

11 return $r_{i}\leftarrow V_{A_{i}}^{\epsilon_{i}}$

12 end

13Function  __privacyTranslate(_ ${q_{i},v_{i}},V,V^{\epsilon},p$_)_ _ :

14 $v^{\prime}\leftarrow$ estimateError(${q_{i},v_{i}},V^{\epsilon}$)

15 $w\leftarrow$
minimizer(func=$-\frac{({v_{i}}-w^{2}v^{\prime})}{(1-w)^{2}}$, bounds=$[0,1]$)

16 $\epsilon\leftarrow$
privacyTranslate($q,\frac{({v_{i}}-w^{2}v^{\prime})}{(1-w)^{2}},V,p$)
$\triangleright$ C.f. Def 5.1.

17 return $\epsilon$

18 end

19Function  __constraintCheck(_ $P,A_{i},V^{\epsilon},\epsilon_{i},\Psi$_)_ _
:

20

21 $\epsilon^{\prime}=\min(\epsilon,P[A_{i},V]+\epsilon_{i})-P[A_{i},V]$

22 if  _$(P$._max(_ axis=Column, $c$=$V_{j}$_)_ \+
$\epsilon^{\prime}\leq\Psi.\psi_{V_{j}})\land$ $(P$._composite(_ axis=Row,
$r$=$P$._max_ _())_ \+ $\epsilon^{\prime}\leq\Psi.\psi_{P})\land$
$(P$._composite(_ axis=Row _)_ \+ $\epsilon^{\prime}\leq\Psi.\psi_{A_{i}})$ _
then

23 return True/Pass

24

25

26 end

Algorithm 4 Additive Gaussian Approach

####  5.2.4. Provenance Constraint Checking

The provenance constraint checking for the additive Gaussian approach (line 4)
is similar to the module for the vanilla approach. We would like to highlight
3 differences. 1) Due to the use of the additive Gaussian mechanism, the
composition across analysts on the same view is bounded as tight as the $\max
P[A_{i},V],\forall A_{i}\in\mathcal{A}$. Therefore, we check the view
constraint by taking the max over the column retrieved by the index of view
$V_{j}$. 2) To check table constraint, we composite a vector where each
element is the maximum recorded privacy budget over every column/view. 3) The
new cumulative cost is no longer $\epsilon_{i}$, but
$\epsilon^{\prime}=\min(\epsilon,P[A_{i},V]+\epsilon_{i})-P[A_{i},V]$.

###### Theorem 5.10.

Given the same sequence of queries $Q$ and at least 2 data analysts in the
system and the same system setup, the total number of queries answered by the
additive Gaussian approach is always more than or equal to that answered by
vanilla approach.

###### Proof Sketch.

DProvDB processes incoming queries with DP synopsis (vanilla approach) or
local synopsis (additive Gaussian approach). For each query $q$ in $Q$, if it
can be answered (w.r.t the accuracy requirement) with cached synopsis, both
approaches will process it in the same manner; otherwise, DProvDB needs to
update the synopses. Comparing the cost of synopses update in both methods,
$\min(\epsilon,P[A_{i},V]+\epsilon_{i})-P[A_{i},V]\leq\epsilon_{i}$ always
holds. Therefore, given the same privacy constraints, if a synopsis can be
generated to answer query $q$ with vanilla approach, the additive Gaussian
approach must be able to update a global synopsis and generate a local
synopsis to answer this query, which proves the theorem. ∎

We note that vanilla approach generates independent synopses for different
data analysts, while in the additive Gaussian approach, we only update global
synopses which saves privacy budgets when different analysts ask similar
queries. We empirically show the benefit in terms of answering more queries
with the additive Gaussian approach in Section 6.

####  5.2.5. Putting Components All Together

The additive Gaussian approach is presented in Algorithm 4: 4-4 (the function
run). At each time stamp, the system receives the query $q$ from the analyst
$A_{i}$ and selects the view that this query can be answerable. If the
translated budget $\epsilon_{i}$ is greater than the budget allocated to the
global synopsis of that view (line 3), we generate a delta synopsis (lines
4-5) and update the global synopsis (line 6). Otherwise, we can use additive
GM to generate the local synopsis based on the (updated) global synopsis
(lines 7-9). We update the provenance table with the consumed budget
$\epsilon_{i}$ (line 10) and answer the query based on the local synopsis to
the analyst (line 11).

####  5.2.6. Discussion on Combining Local Synopses

We may also update a local synopsis $V_{A_{i}}^{\epsilon^{\prime}}$ (upon
request $\epsilon_{i}$) by first generating an intermediate local synopsis
$V_{A_{i}}^{\Delta\epsilon}$ from $V^{\epsilon_{t}}$ using additive GM, where
$\Delta\epsilon=\epsilon_{i}-\epsilon^{\prime}$ and then combining
$V_{A_{i}}^{\Delta\epsilon}$ with the previous local synopsis in a similar way
as it does for the global synopses, which leads to a new local synopsis
$V_{A_{i}}^{\epsilon^{\prime}+\Delta\epsilon}$.

###### Example 5.11.

To answer Bob’s query $(q_{1},\epsilon_{V_{1},Bob}=0.7)$, we can use additive
GM to generate a fresh local synopsis $V^{0.4}_{Bob}$ from $V^{0.7}$, and
combine $V^{0.4}_{Bob}$ with the existing $V^{0.3}_{Bob}$ to get
$V^{0.7}_{Bob}$.

However, unlike combining global synopses, these local synopses share
correlated noise. We must solve a different optimization problem to find an
unbiased estimator with minimum error. For example, given the last combined
global synopsis (and its weights)
$V^{\prime}=w_{t-1}V^{\epsilon_{t-1}}+w_{t}V^{\epsilon_{t}-\epsilon_{t-1}}$,
if we know $V_{A}^{\epsilon_{t-1}}$ is a fresh local synopsis generated from
$V^{\epsilon_{t-1}}$, we consider using the weights $k_{t-1},k_{t}$ for local
synopsis combination:

$\displaystyle V_{A}^{\prime}=$
$\displaystyle~{}k_{t-1}V_{A}^{\epsilon_{t-1}}+k_{t}V_{A}^{\Delta\epsilon}$
$\displaystyle=$
$\displaystyle~{}k_{t-1}(V^{\epsilon_{t-1}}+\eta_{A}^{t-1})+k_{t}(w_{t-1}V^{\epsilon_{t-1}}+w_{t}V^{\epsilon_{t}-\epsilon_{t-1}}+\eta_{A}^{t})$
$\displaystyle=$
$\displaystyle~{}(k_{t-1}+k_{t}w_{t-1})V^{\epsilon_{t-1}}+k_{t}w_{t}V^{\epsilon_{t}-\epsilon_{t-1}}+k_{t-1}\eta_{A}^{t-1}+k_{t}\eta_{A}^{t},$

where $\eta_{A}^{t-1}$ and $\eta_{A}^{t}$ are the noise added to the local
synopses in additive GM with variance $\sigma_{t-1}^{2}$ and $\sigma_{t}^{2}$.
We can find the adjusted weights that minimize the expected error for
$V_{A}^{\prime}$ is
$v_{A,t}=(k_{t-1}+k_{t}w_{t-1})^{2}v_{t-1}+k_{t}^{2}w_{t}^{2}v_{\Delta}+k_{t-1}^{2}\sigma_{t-1}^{2}+k_{t}^{2}\sigma_{t}^{2}$
subject to $k_{t-1}+k_{t}w_{t-1}+k_{t}w_{t}=1$, using an optimization solver.
Allowing the optimal combination of local synopses tightens the cumulative
privacy cost of $A_{i}$ on $V$, i.e.,
$\epsilon_{i}<\min(\epsilon_{t},P[A_{i},V]+\epsilon_{i})$. However, if the
existing local synopsis $V_{A}^{\epsilon_{t-1}}$ is a combined synopsis from a
previous time stamp, the correct variance calculation requires a nested
analysis on _from where the local synopses are generated and with what weights
the global/local synopses are combined_. This renders too many parameters for
DProvDB to keep track of and puts additional challenges for accuracy
translation since solving an optimization problem with many weights is hard,
if not intractable. For practical reasons, DProvDB adopts the approach
described in Algorithm 4.

###  5.3. Configuring Provenance Table

In existing systems, the administrator is only responsible for setting a
single parameter specifying the overall privacy budget. DProvDB, however,
requires the administrator to configure more parameters.

####  5.3.1. Setting Analyst Constraints for Proportional Fairness

We first discuss guidelines to establish per-analyst constraints in DProvDB,
by proposing two specifications that achieve proportional fairness.

###### Definition 0 (Constraints for Vanilla Approach).

For the vanilla approach, we propose to specify each analyst’s constraint by
proportional indicated normalization. That is, for the table-level constraint
$\psi_{P}$ and analyst $A_{i}$ with privilege $l_{i}$,
$\psi_{A_{i}}=\frac{l_{i}}{\sum_{j\in[n]}l_{j}}\psi_{P}$.

Note that this proposed specification is not optimal for the additive Gaussian
approach, since the maximum utilized budget will then be constrained by
$\max\psi_{A_{i}}<\psi_{P}$ when more than 1 analyst is using the system.
Instead, we propose the following specification.

###### Definition 0 (Constraints for Additive Gaussian).

For the additive Gaussian approach, each analyst $A_{i}$’s constraint can be
set to as $\frac{l_{i}}{l_{max}}\psi_{P}$, where $l_{max}$ denotes the maximum
privilege in the system.

Comparing Two Specifications. We compare the two analyst-constraint
specifications (Def. 5.12 and 5.13) with experiments in Section 6.2. Besides
their empirical performance, the vanilla constraint specification (Def. 5.12)
requires all data analysts to be registered in the system before the
provenance table is set up. The additive Gaussian approach (with specification
in Def. 5.13), however, allows for the inclusion of new data analysts at a
later time.

####  5.3.2. Setting View Constraints for Dynamic Budget Allocation

Existing privacy budget allocator (Kotsogiannis et al., 2019a) adopts a static
splitting strategy such that the per view privacy budget is equal or
proportional to their sensitivity. DProvDB subsumes theirs by, similarly,
setting the view constraints to be equal or proportional to the sensitivity of
each view, i.e.,
$\\{\psi_{V_{j}}|V_{j}\in\mathcal{V}\\}=\\{\lambda_{V_{j}}\cdot\epsilon/\hat{\Delta}_{V_{j}}\\}_{\forall
V_{j}\in\mathcal{V}}$, where $\hat{\Delta}_{V_{j}}$ is the upper bound of the
sensitivity of the view $V_{j}$. We therefore propose the following water-
filling view constraint specification for a better view budget allocation.

###### Definition 0 (Water-filling View Constraint Setting).

The table constraint $\psi_{P}$ has been set up as a constant (i.e., the
overall privacy budget) in the system. The administrator simply set all view
constraints the same as the table constraint,
$\psi_{V_{j}}\coloneqq\psi_{P},\forall V_{j}\in\mathcal{V}$.

With water-filling constraint specification, the provenance constraint
checking will solely depend on the table constraint and the analyst
constraints. The overall privacy budget is then dynamically allocated to the
views based on analysts’ queries. Compared to existing budget allocation
methods on views, our water-filling specification based on the privacy
provenance table reflects the actual accuracy demands on different views. Thus
it results in avoiding the waste of privacy budget and providing better
utility: i) DProvDB spends fewer budgets on unpopular views, whose consumed
budget is less than $\lambda_{V_{j}}\cdot\epsilon/\hat{\Delta}_{V_{j}}$; ii)
DProvDB can answer queries whose translated privacy budget
$\epsilon>\lambda_{V_{j}}\cdot\epsilon/\hat{\Delta}_{V_{j}}$. In addition, the
water-filling specification allows DProvDB to add views over time.

###  5.4. Privacy and Fairness Guarantees

###### Theorem 5.15 (System Privacy Guarantee).

Given the privacy provenance table and its constraint specifications,
$\Psi=\\{\psi_{A_{i}}|A_{i}\in\mathcal{A}\\}\cup\\{\psi_{V_{j}}|V_{j}\in\mathcal{V}\\}\cup\\{\psi_{P}\\}$,
both mechanisms for DProvDB ensure
$[\ldots,(A_{i},\psi_{A_{i}},\delta),\ldots]$-multi-analyst-DP; they also
ensure $\min(\psi_{V_{j}},\psi_{P})$-DP for view $V_{j}\in\mathcal{V}$ and
overall $\psi_{P}$-DP if all the data analysts collude.

With the provenance table, DProvDB can achieve proportional fairness when
analysts submit a sufficient number of queries, stated as in the following
theorem. Both proofs are deferred to appendices.

###### Theorem 5.16 (System Fairness Guarantee).

Given the privacy provenance table $P$ and the described approaches of setting
analyst constraints, both mechanisms achieve proportional fairness, when the
data analysts finish consuming their assigned privacy budget.

##  6\. Experimental Evaluation

In this section, we compare DProvDB with baseline systems and conduct an
ablation investigation for a better understanding of different components in
DProvDB. Our goal is to show that DProvDB can improve existing query answering
systems for multi-analyst in terms of the number of queries answered and
fairness.

###  6.1. Experiment Setup

We implement DProvDB in Scala with PostgreSQL for the database system, and
deploy it as a middle-ware between Chorus (Johnson et al., 2020) and multiple
analysts. Our implementation follows existing practice (Johnson et al., 2020)
to set all $\delta$ parameter to be the same and small (e.g., 1e-9) for all
queries. The $\delta$ parameters in the privacy constraints (column/row/table)
in the privacy provenance table are set to be capped by the inverse of the
dataset size.

####  6.1.1. Baselines

Since we build on top of Chorus (Johnson et al., 2020), we develop a number of
baseline approaches for the multi-analyst framework using Chorus as well for
fair comparisons.

  * $\bullet$

Chorus (Johnson et al., 2020): This baseline is the plain Chorus, which uses
GM and makes no distinction between data analysts and uses no views. The
system only sets the overall privacy budget.

  * $\bullet$

DProvDB minus Cached Views (ChorusP): This baseline enables privacy provenance
tracking for each data analyst but does not store any synopses. We use Def.
5.12 to set up analyst constraints and Def. 5.14 for view constraints.

  * $\bullet$

DProvDB minus Additive GM (Vanilla): We equip Chorus with privacy provenance
table and the cached views, but with our vanilla approach to update and manage
the provenance table and the views. The privacy provenance table is configured
the same as in ChorusP.

  * $\bullet$

Simulating PrivateSQL (sPrivateSQL)(Kotsogiannis et al., 2019a): We simulate
PrivateSQL by generating the static DP synopses at first. The budget allocated
to each view is proportional to the view sensitivities (Kotsogiannis et al.,
2019a). Incoming queries that cannot be answered accurately with these
synopses will be rejected.

Figure 3. End-to-end Comparison (_RRQ_ task, over _Adult_ dataset), from left
to right: a) utility v.s. overall budget, round-robin; b) utility v.s. overall
budget, randomized; c) fairness against baselines, round-robin; d) fairness
against baselines, randomized.

####  6.1.2. Datasets and Use Cases

We use the Adult dataset (Dua and Graff, 2017) (a demographic data of 15
attributes and 45,224 rows) and the TPC-H dataset (a synthetic data of 1GB)
(Council, 2008) for experiments. We consider the following use cases.

  * $\bullet$

Randomized range queries (RRQ): We randomly generate 4,000 range queries _per
analyst_ , each with one attribute randomly selected with bias. Each query has
the range specification $[s,s+o]$ where $s$ and the offset $o$ are drawn from
a normal distribution. We design two types of query sequences from the data
analysts: a) round-robin, where the analysts take turns to ask queries; b)
random, where a data analyst is randomly selected each time.

  * $\bullet$

Breadth-first search (BFS) tasks: Each data analyst explores a dataset by
traversing a decomposition tree of the cross product over the selected
attributes, aiming to find the (sub-)regions with underrepresented records.
That is, the data analyst traverses the domain and terminates only if the
returned noisy count is within a specified threshold range.

To answer the queries, we generate one histogram view on each attribute. We
use two analysts with privileges 1 and 4 by default setting and also study the
effect of involving more analysts.

####  6.1.3. Evaluation Metrics

We use four metrics for evaluation.

  * $\bullet$

Number of queries being answered: We report the number of queries that can be
answered by the system when no more queries can be answered as the utility
metric to the system.

  * $\bullet$

Cumulative privacy budget: For BFS tasks that have fixed workloads, it is
possible that the budget is not used up when the tasks are complete.
Therefore, we report the total cumulative budget consumed by all data analysts
when the tasks end.

  * $\bullet$

Normalized discounted cumulative fairness gain (nDCFG): We coined an empirical
fairness measure here. First, we introduce DCFG measure for a mechanism
$\mathcal{M}$ as
$\text{DCFG}_{\mathcal{M}}=\sum^{n}_{i=1}\frac{|Q_{A_{i}}|}{\log_{2}(\frac{1}{l_{i}}+1)}$,
where $l_{i}$ is the privilege level of analyst $A_{i}$ and $|Q_{A_{i}}|$ is
the total number of queries of $A_{i}$ being answered. Then nDCFG is DCFG
normalized by the total number of queries answered.

  * $\bullet$

Runtime: We measures the run time in milliseconds.

We repeat each experiment 4 times using different random seeds.

Figure 4. End-to-end Comparison (BFS task): Cumulative privacy budget
assumption v.s. workload indices. Left: over Adult dataset; Right: over TPC-H
dataset.

###  6.2. Empirical Results

We initiate experiments on the default settings of DProvDB and the baseline
systems for comparison, and then study the effect of modifying the components
of DProvDB.

####  6.2.1. End-to-end Comparison

This comparison is with the setup of the analyst constraints in line with Def.
5.13 for DProvDB, and with Def. 5.12 for vanilla approach. We brief our
findings.

Results of RRQ task. We present Fig. 3 for this experiment. We fix the entire
query workload and run the query processing on the five mechanisms. DProvDB
outperforms all competing systems, in both round-robin or random use cases.
Chorus and ChorusP can answer very few queries because their privacy budgets
are depleted quickly. Interestingly, our simulated PrivateSQL can answer a
number of queries which are comparable to the vanilla appraoch when
$\epsilon=6.4$, but answers a limited number of queries under higher privacy
regimes. This is intuitive because if one statically fairly pre-allocates the
privacy budget to each view when the overall budget is limited, then possibly
every synopsis can hardly answer queries accurately. One can also notice the
fairness score of ChorusP is significantly higher than Chorus, meaning the
enforcement of privacy provenance table can help achieve fairness.

Results of BFS task. An end-to-end comparison of the systems on the BFS tasks
is depicted in Fig. 4. Both DProvDB and vanilla can complete executing the
query workload with near constant budget consumption, while Chorus(P) spends
privacy budget linearly with the workload size. DProvDB saves even more budget
compared to vanilla approach, based on results on the TPC-H dataset.

Runtime performance. Table 1 summarizes the runtime of DProvDB and all
baselines. DProvDB and sPrivateSQL use a rather large amount of time to set up
views, however, answering large queries based on views saves more time on
average compared to Chorus-based mechanisms. Recall that aGM requires solving
optimization problems, where empirical results show incurred time overhead is
only less than 2 ms per query.

We draw the same conclusion for our RRQ experiments and runtime performance
test on the other dataset. We defer the results to the appendices.

Figure 5. Component Comparison (_RRQ_ task, over _Adult_ dataset): Enabling
Cached Synopses. Utility v.s. the size of query workload (round-robin)From
left to right: $\epsilon=\\{0.4,0.8,1.6,3.2,6.4\\}$.  Figure 6. Component
Comparison (_RRQ_ task, over _Adult_ dataset): Additive GM v.s. Vanilla. Left:
utility v.s. #analysts, round-robin; Right: utility v.s. overall budgets,
round-robin.  Table 1. Runtime Performance Comparison over Different
Mechanisms on TPC-H Dataset (running on a Linux server with 64 GB DDR4 RAM and
AMD Ryzen 5 3600 CPU, measured in milliseconds)

Systems | Setup Time | Running Time | No. of Queries | Per Query Perf
---|---|---|---|---
DProvDB | 20388.65 ms | 297.30 ms | 86.0 | 3.46 ms
Vanilla | 20388.65 ms | 118.04 ms | 86.0 | 1.37 ms
sPrivateSQL | 20388.65 ms | 166.51 ms | 86.0 | 1.94 ms
Chorus | N/A | 7380.47 ms | 62.0 | 119.04 ms
ChorusP | N/A | 7478.69 ms | 62.0 | 120.62 ms

####  6.2.2. Component Comparison

We consider three components in DProvDB to evaluate separately.

Cached Synopses. Given the same overall budget, mechanisms leveraging cached
synopses outperform those without caches in terms of utility when the size of
the query workload increases. This phenomenon can be observed for all budget
settings, as shown in Fig. 5. Due to the use of cached synopses, DProvDB can
potentially answer more queries if the incoming queries hit the caches. Thus,
the number of queries being answered would increase with the increasing size
of the workload, given the fixed overall budget.

Additive GM v.s. Vanilla. Given the same overall budget, additive GM
outperforms the vanilla mechanism on utility. The utility gap increases with
the increasing number of data analysts presented in the system. The empirical
results are presented in Fig. 6. When there are 2 analysts in the system,
additive GM can only gain a marginal advantage over vanilla approach; when the
number of data analysts increases to 6, additive GM can answer around
$\sim$2-4x more queries than vanilla. We also compare different settings of
analyst constraints among different numbers of analysts and different overall
system budgets (with 2 analysts). It turns out that additive GM with the
setting in Def. 5.13 (DProvDB-l_max), is the best one, outperforming the
setting from Def. 5.12 (DProvDB-l_sum, Vanilla-l_sum) all the time for
different epsilons and with $\sim$4x more queries being answered when
#analysts=6.

Constraint Configuration. If we allow an expansion parameter $\tau\geq 1$ on
setting the analyst constraints (i.e., overselling privacy budgets than the
constraint defined in Def. 5.13), we can obtain higher system utility by
sacrificing fairness, as shown in Fig. 7. With 2 data analysts, the number of
total queries being answered by additive GM is slightly increased when we
gradually set a larger analyst constraint expansion rate. Under a low privacy
regime (viz., $\epsilon=3.2$), this utility is increased by more than 15%
comparing setting $\tau=1.9$ and $\tau=1.3$; on the other hand, the fairness
score decreases by around 10%.

This result can be interpretable from a basic economic view, that we argue, as
a system-wise public resource, the privacy budget could be _idle resources_
when some of the data analysts stop asking queries. Thus, the _hard privacy
constraints_ enforced in the system can make some portion of privacy budgets
unusable. Given the constraint expansion, we allow DProvDB to tweak between a
fairness and utility trade-off, while the overall privacy is still guaranteed
by the table constraint.

Figure 7. Component Comparison (_RRQ_ task, over _Adult_ dataset): Constraint
Configuration. First row: utility v.s. constraint settings. Second row:
fairness v.s. constraint settings. Left: round-robin. Right: randomized.

Varying $\delta$ parameter. In this experiment, we control the overall privacy
constraint $\epsilon=6.4$ and vary the $\delta$ parameter as per query. We use
the BFS workload as in our end-to-end experiment and the results are shown in
Fig. 8. While varying a small $\delta$ parameter does not much affect the
number of queries being answered, observe that increasing $\delta$, DProvDB
can slightly answer more queries. This is because, to achieve the same
accuracy requirement, the translation module will output a smaller $\epsilon$
when $\delta$ is bigger, which will consume the privacy budget slower. Note
that the overall privacy constraint on $\delta$ should be set no larger than
the inverse of the dataset size. Setting an unreasonably large per-query
$\delta$ can limit the total number of queries being answered.

Other experiments. We also run experiments to evaluate DProvDB on data-
dependent utility metric, i.e. relative error (Xiao et al., 2011a), and
empirically validate the correctness of the accuracy-privacy translation
module. In particular, we performed experiments to show that the noise
variance $v_{q}$ (derived from the variance of the noisy synopsis) of the
query answer, according to the translated privacy budget, is always no more
than the accuracy requirement $v_{i}$ submitted by the data analyst. As shown
in Fig. 9 (a), the difference between the two values, $v_{q}-v_{i}$, is always
less than 0, and very small for a given BFS query workload (where the accuracy
requirement is set to be above $v_{i}>10000$).

Furthermore, we consider the following data-dependent utility, namely relative
error (Xiao et al., 2011a), which is defined as

$\text{Relative Error}=\frac{|\text{True Answer}-\text{Noisy
Answer}|}{\max\\{\text{True Answer},c\\}},$

where $c$ is a specified constant to avoid undefined values when the true
answer is 0.

Note that DProvDB does not specifically support analysts to submit queries
with _data-dependent_ accuracy requirements. The translated query answer can
have a large relative error if the true answer is small or close to zero. We
thereby merely use this utility metric to empirically evaluate the answers of
a BFS query workload, as a complementary result [Fig. 9 (b)] to the paper.
DProvDB and the Vanilla approach have a larger relative error than Chorus and
ChorusP because they can answer more queries, many of which have a
comparatively small true answer – incurring a large relative error, than
Chorus-based methods.

Figure 8. #queries being answered vs. varying delta parameter (BFS task,
Adult). Left: round-robin, Right: randomized.

Figure 9. (a) The cumulative average of $v_{q}-v_{i}$ for a BFS query workload
(on Adult dataset), where $v_{i}$ represents the submitted accuracy
requirement and $v_{q}$ denotes the noise variance of the query answer. (b)
Relative error of processing the BFS query workload (on Adult dataset) among
different mechanisms.

##  7\. Discussion

In this section, we discuss a weaker threat model of the multi-analyst
corruption assumption, with which additional utility gain is possible. We also
discuss other strawman solutions toward a multi-analyst DP system.

###  7.1. Relaxation of Multi-analyst Threat Model

So far we have studied that all data analysts can collude. A more practical
setting is, perhaps, considering a subset of data analysts that are
compromised by the adversary. This setting is common to see in the multi-party
computation research community (Dwork et al., 2006a) (_a.k.a_ active security
(Damgård and Nielsen, 2007; Beaver and Goldwasser, 1989)), where $t$ out of
$n$ participating parties are assumed to be corrupted.

###### Definition 0 ($(t,n)$-compromised Multi-analyst Setting).

We say a multi-analyst setting is $(t,n)$-compromised, if there exist $n$ data
analysts where at most $t$ of them are malicious (meaning they can collude in
submitting queries and sharing the answers).

The $(t,n)$-compromised multi-analyst setting makes weaker assumptions on the
attackers. Under this setting, the privacy loss is upper bounded by
$(\sum_{t}\epsilon_{i},\sum_{t}\delta_{i})$, which is the summation over $t$
largest privacy budgets. However, we cannot do better than the current DProvDB
algorithms with this weaker setting under worst-case privacy assumption.

###### Theorem 7.2 (Hardness on Worst-case Privacy).

Given a mechanism $\mathcal{M}$ which is
$[\ldots,(A_{i},\epsilon_{i},\delta_{i}),\dots]$-multi-analyst-DP, the worst-
case privacy loss under $(t,n)$-compromised multi-analyst DP is lower bounded
by $(\max\epsilon_{i},\max\delta_{i})$, which is the same as under the all-
compromisation setting.

###### Proof Sketch.

Under the worst-case assumption, the analyst with the largest privacy budget
$(\max\epsilon_{i},\max\delta_{i})$ is sampled within the $t$ compromised data
analysts. Then it is natural to see that the lower bound of the privacy loss
is $(\max\epsilon_{i},\max\delta_{i})$. ∎

At first glance, the relaxation of the $(t,n)$-compromisation does not provide
us with better bounds. A second look, however, suggests the additional trust
we put in the data analyst averages the privacy loss in compromisation cases.
Therefore, with this relaxed privacy assumption, it is possible to design
mechanisms to achieve better utility using policy-driven privacy.

Policies for multi-analyst. Blowfish privacy (He et al., 2014) specifies
different levels of protection over sensitive information in the curated
database. In the spirit of Blowfish, we can use policies to specify different
levels of trust in data analysts using DProvDB.

###### Definition 0 ($(t,n)$-Analysts Corruption Graph).

Given $n$ data analysts and assuming $(t,n)$-compromised setting, we say an
undirected graph $G=(V,E)$ is a $(t,n)$-analysts corruption graph if,

  * •

Each node in the vertex set $v_{i}\in V$ represents an analyst $A_{i}$;

  * •

An edge is presented in the edge set $\operatorname{e}(v_{i},v_{j})\in E$ if
data analysts $A_{i}$ and $A_{j}$ can collude;

  * •

Every connected component in $G$ has less than $t$ nodes.

The corruption graph models the prior belief of the policy designer (or DB
administrator) to the system users. Groups of analysts are believed to be not
compromised if they are in the disjoint sets of the corruption graph. Based on
this corruption graph, we can specify the analysts’ constraints as assigning
the overall privacy budget $\psi_{P}$ to each connected component.

###### Theorem 7.4.

There exist mechanisms with $(t,n)$-multi-analyst DP perform at least as well
as with multi-analyst DP.

###### Proof.

Given a $(t,n)$-analysts corruption graph $G$, we show a naïve
budget/constraint that makes $(t,n)$-multi-analyst DP degrade to multi-analyst
DP. Ignoring the graph structure, we split the overall privacy budget
$\psi_{P}$ and assign a portion to each node proportional to the privilege
weight on each node. ∎

Let $k$ be the number of disjoint connected components in $G$. Then we have at
most $\lceil k\rceil\cdot\psi_{P}$ privacy budget to assign to this graph.
Clearly, the mechanisms with $(t,n)$-multi-analyst DP achieve $(\lceil
k\rceil\cdot\psi_{P})$-DP. When $n>t$, we have more than 1 connected
component, meaning the overall privacy budget we could spend is more than that
in the all-compromisation scenario.

###  7.2. Comparison with Strawman Solutions

One may argue for various alternative solutions to the multi-analyst query
processing problem, as opposed to our proposed system. We justify these
possible alternatives and compare them with DProvDB.

Strawman #1: Sharing Synthetic Data. Recall that DProvDB generates global and
local synopses from which different levels of noise are added with additive
GM, and answers analysts’ queries based on the local synopses. We show our
proposed algorithm is optimal in using privacy budgets when all data analysts
collude. One possible alternative may be just releasing the global synopses
(or generating synthetic data using all privacy budgets) to every data
analyst, which also can achieve optimality in the all-compromisation setting.
We note that this solution is
$\min\left(\psi_{P},(\max\epsilon_{i},\max\delta_{i})\right)$-DP (same as the
overall DP guarantee provided by DProvDB), however, it does not achieve the
notion of _Multi-analyst DP_ (all data analysts get the same output).

Strawman #2: Pre-calculating Seeded Caches. To avoid the cost of running the
algorithm in an online manner, one may consider equally splitting the privacy
budgets into small ones and using additive GM to pre-compute all the global
synopses and local synopses. This solution saves all synopses and for future
queries, it can directly answer by finding the appropriate synopses. If the
space cost is too large, alternatively one may store only the seeds to
generate all the synopses from which a synopsis can be quickly created.

This scheme arguably achieves the desired properties of DProvDB, if one
ignores the storage overhead incurred by the pre-computed synopses or seeds.
However, for an online query processing system, it is usually unpredictable
what queries and accuracy requirements the data analysts would submit to the
system. This solution focuses on doing most of the calculations offline, which
may, first, lose the precision in translating accuracy to privacy, leading to
a trade-off between precision and processing time regarding privacy
translation. We show in experiments that the translation only happens when the
query does not hit the existing cache (which is not too often), and the per-
query translation processing time is negligible. Second, to pre-compute all
the synopses, one needs to pre-allocate privacy budgets to the synopses. We
has shown as well using empirical results that this approach achieves less
utility than DProvDB.

##  8\. Related Work

Enabling DP in query processing is an important line of research in database
systems (Near and He, 2021). Starting from the first end-to-end interactive DP
query system (McSherry, 2009), existing work has been focused on generalizing
to a larger class of database operators (Proserpio et al., 2014; Johnson et
al., 2018; Dong and Yi, 2021; Dong et al., 2022; Amin et al., 2022), building
a programmable toolbox for experts (Johnson et al., 2020; Zhang et al., 2018),
or providing a user-friendly accuracy-aware interface for data exploration (Ge
et al., 2019; Vesga et al., 2020). Another line of research investigated means
of saving privacy budgets in online query answering, including those based on
cached views (Kotsogiannis et al., 2019a; Mazmudar et al., 2022) and the
others based on injecting correlated noise to query results (Xiao et al.,
2022; Koufogiannis et al., 2016; Bao et al., 2022). Privacy provenance (on
protected data) is studied in the personalized DP framework (Ebadi et al.,
2015) as a means to enforce varying protection on database records, which is
dual to our system. The multi-analyst scenario is also studied in DP
literature (Xiao et al., 2021; Knopf, 2021; Pujol et al., 2021, 2022). Our
multi-analyst DP work focuses on the online setting, which differs from the
offline setting, where the entire query workload is known in advance (Xiao et
al., 2021; Knopf, 2021; Pujol et al., 2021). The closest related work (Pujol
et al., 2022) considers an online setup for multi-analyst DP, but the problem
setting differs. The multi-analyst DP in (Pujol et al., 2022) assumes the data
analysts have the incentive to share their budgets to improve the utility of
their query answers, but our multi-analyst DP considers data analysts who are
obliged under laws/regulations should not share their budget/query responses
to each other (e.g., internal data analysts should not share their results
with an external third party). Our mechanism ensures that (i) even if these
data analysts break the law and collude, the overall privacy loss is still
minimized; (ii) if they do not collude, each of the analysts $A_{i}$ has a
privacy loss bounded by $\epsilon_{i}$ (c.f. our multi-analyst DP, Definition
3.1). However, (Pujol et al., 2022) releases more information than the
specified $\epsilon_{i}$ for analyst $A_{i}$ (as (Pujol et al., 2022)
guarantees DP). Some other DP systems, e.g. Sage (Lécuyer et al., 2019) and
its follow-ups (Luo et al., 2021; Tholoniat et al., 2022; Küchler et al.,
2023), involve multiple applications or end-users, and they care about the
budget consumption (Lécuyer et al., 2019; Küchler et al., 2023) or fairness
constraints (Luo et al., 2021) in such scenarios. Their design objective is
orthogonal to ours — they would like to avoid running out of privacy budget
and maximize utility through batched execution over a growing database.

The idea of adding correlated Gaussian noise has been exploited in existing
work (Bao et al., 2021; Li et al., 2012). However, they all solve a simpler
version of our problem. Li et al. (Li et al., 2012) resort algorithms to
release the perturbed results to different users once and Bao et al. (Bao et
al., 2021) study the sequential data collection of one user. When putting the
two dimensions together, understudied questions, such as how to properly
answer queries to an analyst that the answer to the same query with lower
accuracy requirements has already been released to another analyst, arise and
are not considered by existing work. Therefore, we propose the provenance-
based additive Gaussian approach (Section 5.2) to solve these challenges,
which is not merely injecting correlated noise into a sequence of queries.

##  9\. Conclusion and Future Work

We study how the query meta-data or provenance information can assist query
processing in multi-analyst DP settings. We developed a privacy provenance
framework for answering online queries, which tracks the privacy loss to each
data analyst in the system using a provenance table. Based on the privacy
provenance table, we proposed DP mechanisms that leverage the provenance
information for noise calibration and built DProvDB to maximize the number of
queries that can be answered. DProvDB can serve as a middle-ware to provide a
multi-analyst interface for existing DP query answering systems. We
implemented DProvDB and our evaluation shows that DProvDB can significantly
improve the number of queries that could be answered and fairness, compared to
baseline systems.

While as an initial work, this paper considers a relatively restricted but
popular setting in DP literature, we believe our work may open a new research
direction of using provenance information for multi-analyst DP query
processing. We thereby discuss our ongoing work on DProvDB and envision some
potential thrusts in this research area.

  * $\bullet$

Tight privacy analysis. In the future, we would like to tighten the privacy
analysis when composing the privacy loss of the local synopses generated from
correlated global synopses.

  * $\bullet$

Optimal processing for highly-sensitive queries. While currently DProvDB can
be extended to answer these queries naïvely (by a truncated and fixed
sensitivity bound), instance optimal processing of these queries (Dong et al.,
2022) requires data-dependent algorithms, which is not supported by our
current approaches. Our ongoing work includes enabling DProvDB with the
ability to optimally answer these queries.

  * $\bullet$

System utility optimization. We can also optimize the system utility further
by considering a more careful design of the structure of the cached synopses
(Mazmudar et al., 2022; Ghazi et al., 2023), e.g. cumulative histogram views,
making use of the sparsity in the data itself (Xiao et al., 2011b), or using
data-dependent views (Li et al., 2014).

  * $\bullet$

Other DP settings. DProvDB considers minimizing the collusion among analysts
over time in an online system. The current design enforces approximate DP due
to the nature of Gaussian properties. Our ongoing work extends to use Renyi DP
or zCDP for privacy composition. Future work can also consider other noise
distributions, e.g. Skellam (Bao et al., 2022), to support different DP
variants, or other utility metrics, e.g., confidence intervals (Ge et al.,
2019) or relative errors, for accuracy-privacy translation, or other
application domain, e.g., location privacy (Yu et al., 2022; He et al., 2015)
.

  * $\bullet$

Other problems with access control settings. More research questions and works
may be spawned by a deeper intertwinement between privacy provenance and
access/leakage control (Pappachan et al., 2022). For instance, an analyst can
submit queries with different privilege levels, which requires a more
expressive model for privacy provenance. Another use case is that the user can
temporarily delegate his/her privilege to others (Wang et al., 2008; Theimer
et al., 1992). One potential approach to resolving the first scenario may be
to enable hierarchical privacy accounting over a more fine-grained provenance
table, i.e., composite privacy loss as per each privilege level and per
analyst, and the privacy loss per each data analyst is still bounded in a
similar way. For the second use case, the system may further allow a “grant”
operator that records more provenance information – for example, the privacy
budget consumed by a lower-privileged analyst during delegation is accounted
to the analyst who grants this delegation.

###### Acknowledgements.

This work was supported by NSERC through a Discovery Grant. We would like to
thank the anonymous reviewers for their detailed comments which helped to
improve the paper during the revision process. We also thank Runchao Jiang,
Semih Salihoğlu, Florian Kerschbaum, Jiayi Chen, Shuran Zheng for helpful
conversations or feedback at the early stage of this project.

## References

  * (1)
  * Amin et al. (2022) Kareem Amin, Jennifer Gillenwater, Matthew Joseph, Alex Kulesza, and Sergei Vassilvitskii. 2022\.  Plume: Differential Privacy at Scale.  _CoRR_ abs/2201.11603 (2022).  arXiv:2201.11603 https://arxiv.org/abs/2201.11603
  * Balle and Wang (2018) Borja Balle and Yu-Xiang Wang. 2018.  Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ _(Proceedings of Machine Learning Research, Vol. 80)_ , Jennifer G. Dy and Andreas Krause (Eds.). PMLR, 403–412.  http://proceedings.mlr.press/v80/balle18a.html
  * Banerjee et al. (2023) Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. 2023.  Proportionally Fair Online Allocation of Public Goods with Predictions. In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China_. ijcai.org, 20–28.  https://doi.org/10.24963/ijcai.2023/3
  * Bao et al. (2021) Ergute Bao, Yin Yang, Xiaokui Xiao, and Bolin Ding. 2021\.  CGM: An Enhanced Mechanism for Streaming Data Collectionwith Local Differential Privacy.  _Proc. VLDB Endow._ 14, 11 (2021), 2258–2270.  https://doi.org/10.14778/3476249.3476277
  * Bao et al. (2022) Ergute Bao, Yizheng Zhu, Xiaokui Xiao, Yin Yang, Beng Chin Ooi, Benjamin Hong Meng Tan, and Khin Mi Mi Aung. 2022.  Skellam Mixture Mechanism: a Novel Approach to Federated Learning with Differential Privacy.  _Proc. VLDB Endow._ 15, 11 (2022), 2348–2360.  https://www.vldb.org/pvldb/vol15/p2348-bao.pdf
  * Beaver and Goldwasser (1989) Donald Beaver and Shafi Goldwasser. 1989.  Multiparty Computation with Faulty Majority. In _Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings_ _(Lecture Notes in Computer Science, Vol. 435)_ , Gilles Brassard (Ed.). Springer, 589–590.  https://doi.org/10.1007/0-387-34805-0_51
  * Blocki et al. (2013) Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. 2013\.  Differentially private data analysis of social networks via restricted sensitivity. In _Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013_ , Robert D. Kleinberg (Ed.). ACM, 87–96.  https://doi.org/10.1145/2422436.2422449
  * Bun and Steinke (2016) Mark Bun and Thomas Steinke. 2016.  Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In _Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I_ _(Lecture Notes in Computer Science, Vol. 9985)_ , Martin Hirt and Adam D. Smith (Eds.). 635–658.  https://doi.org/10.1007/978-3-662-53641-4_24
  * Buneman and Tan (2007) Peter Buneman and Wang Chiew Tan. 2007.  Provenance in databases. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007_ , Chee Yong Chan, Beng Chin Ooi, and Aoying Zhou (Eds.). ACM, 1171–1173.  https://doi.org/10.1145/1247480.1247646
  * Cheney et al. (2009) James Cheney, Laura Chiticariu, and Wang Chiew Tan. 2009\.  Provenance in Databases: Why, How, and Where.  _Found. Trends Databases_ 1, 4 (2009), 379–474.  https://doi.org/10.1561/1900000006
  * Council (2008) The Transaction Processing Performance Council. 2008.  The TPC Benchmark H (TPC-H).  https://www.tpc.org/tpch/
  * Damgård and Nielsen (2007) Ivan Damgård and Jesper Buus Nielsen. 2007.  Scalable and Unconditionally Secure Multiparty Computation. In _Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings_ _(Lecture Notes in Computer Science, Vol. 4622)_ , Alfred Menezes (Ed.). Springer, 572–590.  https://doi.org/10.1007/978-3-540-74143-5_32
  * Desfontaines and Pejó (2020) Damien Desfontaines and Balázs Pejó. 2020.  SoK: Differential privacies.  _Proc. Priv. Enhancing Technol._ 2020, 2 (2020), 288–313.  https://doi.org/10.2478/popets-2020-0028
  * di Vimercati (2011) Sabrina De Capitani di Vimercati. 2011\.  Access Control Policies, Models, and Mechanisms.  In _Encyclopedia of Cryptography and Security, 2nd Ed_ , Henk C. A. van Tilborg and Sushil Jajodia (Eds.). Springer, 13–14.  https://doi.org/10.1007/978-1-4419-5906-5_806
  * Dong et al. (2022) 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 _SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022_ , Zachary G. Ives, Angela Bonifati, and Amr El Abbadi (Eds.). ACM, 759–772.  https://doi.org/10.1145/3514221.3517844
  * Dong and Yi (2021) Wei Dong and Ke Yi. 2021\.  Residual Sensitivity for Differentially Private Multi-Way Joins. In _SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021_ , Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 432–444.  https://doi.org/10.1145/3448016.3452813
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Dwork et al. (2006a) Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006a.  Our Data, Ourselves: Privacy Via Distributed Noise Generation. In _Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings_ _(Lecture Notes in Computer Science, Vol. 4004)_ , Serge Vaudenay (Ed.). Springer, 486–503.  https://doi.org/10.1007/11761679_29
  * Dwork et al. (2006b) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006b.  Calibrating Noise to Sensitivity in Private Data Analysis. In _Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings_ _(Lecture Notes in Computer Science, Vol. 3876)_ , Shai Halevi and Tal Rabin (Eds.). Springer, 265–284.  https://doi.org/10.1007/11681878_14
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. 2014.  The Algorithmic Foundations of Differential Privacy.  _Found. Trends Theor. Comput. Sci._ 9, 3-4 (2014), 211–407.  https://doi.org/10.1561/0400000042
  * Dwork and Rothblum (2016) Cynthia Dwork and Guy N. Rothblum. 2016.  Concentrated Differential Privacy.  _CoRR_ abs/1603.01887 (2016).  arXiv:1603.01887 http://arxiv.org/abs/1603.01887
  * Ebadi et al. (2015) Hamid Ebadi, David Sands, and Gerardo Schneider. 2015.  Differential Privacy: Now it’s Getting Personal. In _Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15-17, 2015_ , Sriram K. Rajamani and David Walker (Eds.). ACM, 69–81.  https://doi.org/10.1145/2676726.2677005
  * Ge et al. (2019) Chang Ge, Xi He, Ihab F. Ilyas, and Ashwin Machanavajjhala. 2019.  APEx: Accuracy-Aware Differentially Private Data Exploration. In _Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019_ , Peter A. Boncz, Stefan Manegold, Anastasia Ailamaki, Amol Deshpande, and Tim Kraska (Eds.). ACM, 177–194.  https://doi.org/10.1145/3299869.3300092
  * Ghazi et al. (2023) Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. 2023\.  Differentially Private Data Release over Multiple Tables. In _Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ (Seattle, WA, USA) _(PODS ’23)_. Association for Computing Machinery, New York, NY, USA, 207–219.  https://doi.org/10.1145/3584372.3588665
  * Hall et al. (2021) David Hall et al. 2021\.  Breeze: numerical processing library for Scala.  https://github.com/scalanlp/breeze.  Accessed: March 12, 2023.
  * He et al. (2015) Xi He, Graham Cormode, Ashwin Machanavajjhala, Cecilia M. Procopiuc, and Divesh Srivastava. 2015\.  DPT: Differentially Private Trajectory Synthesis Using Hierarchical Reference Systems.  _Proc. VLDB Endow._ 8, 11 (2015), 1154–1165.  https://doi.org/10.14778/2809974.2809978
  * He et al. (2014) Xi He, Ashwin Machanavajjhala, and Bolin Ding. 2014\.  Blowfish privacy: tuning privacy-utility trade-offs using policies. In _International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014_ , Curtis E. Dyreson, Feifei Li, and M. Tamer Özsu (Eds.). ACM, 1447–1458.  https://doi.org/10.1145/2588555.2588581
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen. 2002\.  Cumulated gain-based evaluation of IR techniques.  _ACM Trans. Inf. Syst._ 20, 4 (2002), 422–446.  https://doi.org/10.1145/582415.582418
  * Johnson et al. (2020) Noah M. Johnson, Joseph P. Near, Joseph M. Hellerstein, and Dawn Song. 2020.  Chorus: a Programming Framework for Building Scalable Differential Privacy Mechanisms. In _IEEE European Symposium on Security and Privacy, EuroS &P 2020, Genoa, Italy, September 7-11, 2020_. IEEE, 535–551.  https://doi.org/10.1109/EuroSP48549.2020.00041
  * Johnson et al. (2018) Noah M. Johnson, Joseph P. Near, and Dawn Song. 2018.  Towards Practical Differential Privacy for SQL Queries.  _Proc. VLDB Endow._ 11, 5 (2018), 526–539.  https://doi.org/10.1145/3187009.3177733
  * Kairouz et al. (2015) Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015\.  The Composition Theorem for Differential Privacy. In _Proceedings of the 32nd International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 37)_ , Francis Bach and David Blei (Eds.). PMLR, Lille, France, 1376–1385.  https://proceedings.mlr.press/v37/kairouz15.html
  * Kairouz et al. (2017) Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2017\.  The Composition Theorem for Differential Privacy.  _IEEE Trans. Inf. Theory_ 63, 6 (2017), 4037–4049.  https://doi.org/10.1109/TIT.2017.2685505
  * Kelly et al. (1998) Frank P Kelly, Aman K Maulloo, and David Kim Hong Tan. 1998\.  Rate control for communication networks: shadow prices, proportional fairness and stability.  _Journal of the Operational Research society_ 49, 3 (1998), 237–252.
  * Kiefer (1952) J Kiefer. 1952.  On minimum variance estimators.  _The Annals of Mathematical Statistics_ 23, 4 (1952), 627–629.
  * Knopf (2021) Karl Knopf. 2021\.  Framework for Differentially Private Data Analysis with Multiple Accuracy Requirements. In _SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021_ , Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 2890–2892.  https://doi.org/10.1145/3448016.3450587
  * Kotsogiannis et al. (2019a) Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. 2019a.  PrivateSQL: A Differentially Private SQL Query Engine.  _Proc. VLDB Endow._ 12, 11 (2019), 1371–1384.  https://doi.org/10.14778/3342263.3342274
  * Kotsogiannis et al. (2019b) Ios Kotsogiannis, Yuchao Tao, Ashwin Machanavajjhala, Gerome Miklau, and Michael Hay. 2019b.  Architecting a Differentially Private SQL Engine. In _9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings_. www.cidrdb.org.  http://cidrdb.org/cidr2019/papers/p125-kotsogiannis-cidr19.pdf
  * Koufogiannis et al. (2016) Fragkiskos Koufogiannis, Shuo Han, and George J. Pappas. 2016\.  Gradual Release of Sensitive Data under Differential Privacy.  _J. Priv. Confidentiality_ 7, 2 (2016).  https://doi.org/10.29012/jpc.v7i2.649
  * Küchler et al. (2023) Nicolas Küchler, Emanuel Opel, Hidde Lycklama, Alexander Viand, and Anwar Hithnawi. 2023\.  Cohere: Privacy Management in Large Scale Systems.  _CoRR_ abs/2301.08517 (2023).  https://doi.org/10.48550/arXiv.2301.08517 arXiv:2301.08517
  * Lécuyer et al. (2019) Mathias Lécuyer, Riley Spahn, Kiran Vodrahalli, Roxana Geambasu, and Daniel Hsu. 2019\.  Privacy accounting and quality control in the sage differentially private ML platform. In _Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP 2019, Huntsville, ON, Canada, October 27-30, 2019_ , Tim Brecht and Carey Williamson (Eds.). ACM, 181–195.  https://doi.org/10.1145/3341301.3359639
  * Li et al. (2014) Chao Li, Michael Hay, Gerome Miklau, and Yue Wang. 2014\.  A Data- and Workload-Aware Query Answering Algorithm for Range Queries Under Differential Privacy.  _Proc. VLDB Endow._ 7, 5 (2014), 341–352.  https://doi.org/10.14778/2732269.2732271
  * Li et al. (2012) Yaping Li, Minghua Chen, Qiwei Li, and Wei Zhang. 2012\.  Enabling Multilevel Trust in Privacy Preserving Data Mining.  _IEEE Trans. Knowl. Data Eng._ 24, 9 (2012), 1598–1612.  https://doi.org/10.1109/TKDE.2011.124
  * Luo et al. (2021) Tao Luo, Mingen Pan, Pierre Tholoniat, Asaf Cidon, Roxana Geambasu, and Mathias Lécuyer. 2021.  Privacy Budget Scheduling. In _15th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2021, July 14-16, 2021_ , Angela Demke Brown and Jay R. Lorch (Eds.). USENIX Association, 55–74.  https://www.usenix.org/conference/osdi21/presentation/luo
  * Mazmudar et al. (2022) Miti Mazmudar, Thomas Humphries, Jiaxiang Liu, Matthew Rafuse, and Xi He. 2022.  Cache Me If You Can: Accuracy-Aware Inference Engine for Differentially Private Data Exploration.  _Proc. VLDB Endow._ 16, 4 (2022), 574–586.  https://www.vldb.org/pvldb/vol16/p574-mazmudar.pdf
  * McSherry (2009) Frank McSherry. 2009\.  Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009_ , Ugur Çetintemel, Stanley B. Zdonik, Donald Kossmann, and Nesime Tatbul (Eds.). ACM, 19–30.  https://doi.org/10.1145/1559845.1559850
  * Mironov (2017) Ilya Mironov. 2017\.  Rényi Differential Privacy. In _30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017_. IEEE Computer Society, 263–275.  https://doi.org/10.1109/CSF.2017.11
  * Near and He (2021) Joseph P. Near and Xi He. 2021.  Differential Privacy for Databases.  _Found. Trends Databases_ 11, 2 (2021), 109–225.  https://doi.org/10.1561/1900000066
  * Pappachan et al. (2022) Primal Pappachan, Shufan Zhang, Xi He, and Sharad Mehrotra. 2022\.  Don’t Be a Tattle-Tale: Preventing Leakages through Data Dependencies on Access Control Protected Data.  _Proc. VLDB Endow._ 15, 11 (2022), 2437–2449.  https://www.vldb.org/pvldb/vol15/p2437-pappachan.pdf
  * Proserpio et al. (2014) Davide Proserpio, Sharon Goldberg, and Frank McSherry. 2014\.  Calibrating Data to Sensitivity in Private Data Analysis.  _Proc. VLDB Endow._ 7, 8 (2014), 637–648.  https://doi.org/10.14778/2732296.2732300
  * Pujol et al. (2022) David Pujol, Albert Sun, Brandon Fain, and Ashwin Machanavajjhala. 2022.  Multi-Analyst Differential Privacy for Online Query Answering.  _Proc. VLDB Endow._ 16, 4 (2022), 816–828.  https://www.vldb.org/pvldb/vol16/p816-pujol.pdf
  * Pujol et al. (2021) David Pujol, Yikai Wu, Brandon Fain, and Ashwin Machanavajjhala. 2021.  Budget Sharing for Multi-Analyst Differential Privacy.  _Proc. VLDB Endow._ 14, 10 (2021), 1805–1817.  https://doi.org/10.14778/3467861.3467870
  * Rao (1949) C Radhakrishna Rao. 1949\.  Sufficient statistics and minimum variance estimates. In _Mathematical Proceedings of the Cambridge Philosophical Society_ , Vol. 45. Cambridge University Press, 213–218.
  * Raskhodnikova and Smith (2015) Sofya Raskhodnikova and Adam D. Smith. 2015.  Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions.  _CoRR_ abs/1504.07912 (2015).  arXiv:1504.07912 http://arxiv.org/abs/1504.07912
  * Stoyanovich et al. (2018) Julia Stoyanovich, Ke Yang, and H. V. Jagadish. 2018\.  Online Set Selection with Fairness and Diversity Constraints. In _Proceedings of the 21st International Conference on Extending Database Technology, EDBT 2018, Vienna, Austria, March 26-29, 2018_ , Michael H. Böhlen, Reinhard Pichler, Norman May, Erhard Rahm, Shan-Hung Wu, and Katja Hose (Eds.). OpenProceedings.org, 241–252.  https://doi.org/10.5441/002/edbt.2018.22
  * Theimer et al. (1992) Marvin Theimer, David A. Nichols, and Douglas B. Terry. 1992\.  Delegation Through Access Control Programs. In _Proceedings of the 12th International Conference on Distributed Computing Systems, Yokohama, Japan, June 9-12, 1992_. IEEE Computer Society, 529–536.  https://doi.org/10.1109/ICDCS.1992.235000
  * Tholoniat et al. (2022) Pierre Tholoniat, Kelly Kostopoulou, Mosharaf Chowdhury, Asaf Cidon, Roxana Geambasu, Mathias Lécuyer, and Junfeng Yang. 2022\.  Packing Privacy Budget Efficiently.  _CoRR_ abs/2212.13228 (2022).  https://doi.org/10.48550/arXiv.2212.13228 arXiv:2212.13228
  * van Erven and Harremoës (2014) Tim van Erven and Peter Harremoës. 2014.  Rényi Divergence and Kullback-Leibler Divergence.  _IEEE Trans. Inf. Theory_ 60, 7 (2014), 3797–3820.  https://doi.org/10.1109/TIT.2014.2320500
  * Vesga et al. (2020) Elisabet Lobo Vesga, Alejandro Russo, and Marco Gaboardi. 2020\.  A Programming Framework for Differential Privacy with Accuracy Concentration Bounds. In _2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020_. IEEE, 411–428.  https://doi.org/10.1109/SP40000.2020.00086
  * Voigt and Von dem Bussche (2017) Paul Voigt and Axel Von dem Bussche. 2017.  The EU general data protection regulation (GDPR).  _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ 10 (2017), 3152676\.
  * Wang et al. (2008) Qihua Wang, Ninghui Li, and Hong Chen. 2008.  On the Security of Delegation in Access Control Systems. In _Computer Security - ESORICS 2008, 13th European Symposium on Research in Computer Security, Málaga, Spain, October 6-8, 2008. Proceedings_ _(Lecture Notes in Computer Science, Vol. 5283)_ , Sushil Jajodia and Javier López (Eds.). Springer, 317–332.  https://doi.org/10.1007/978-3-540-88313-5_21
  * Wang et al. (2013) Yining Wang, Liwei Wang, Yuanzhi Li, Di He, and Tie-Yan Liu. 2013.  A Theoretical Analysis of NDCG Type Ranking Measures. In _COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA_ _(JMLR Workshop and Conference Proceedings, Vol. 30)_ , Shai Shalev-Shwartz and Ingo Steinwart (Eds.). JMLR.org, 25–54.  http://proceedings.mlr.press/v30/Wang13.html
  * Wilson et al. (2020) Royce J. Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. 2020\.  Differentially Private SQL with Bounded User Contribution.  _Proc. Priv. Enhancing Technol._ 2020, 2 (2020), 230–250.  https://doi.org/10.2478/popets-2020-0025
  * Xiao et al. (2011a) Xiaokui Xiao, Gabriel Bender, Michael Hay, and Johannes Gehrke. 2011a.  iReduct: differential privacy with reduced relative errors. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011_ , Timos K. Sellis, Renée J. Miller, Anastasios Kementsietsidis, and Yannis Velegrakis (Eds.). ACM, 229–240.  https://doi.org/10.1145/1989323.1989348
  * Xiao et al. (2011b) Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. 2011b.  Differential Privacy via Wavelet Transforms.  _IEEE Trans. Knowl. Data Eng._ 23, 8 (2011), 1200–1214.  https://doi.org/10.1109/TKDE.2010.247
  * Xiao et al. (2021) Yingtai Xiao, Zeyu Ding, Yuxin Wang, Danfeng Zhang, and Daniel Kifer. 2021.  Optimizing Fitness-For-Use of Differentially Private Linear Queries.  _Proc. VLDB Endow._ 14, 10 (2021), 1730–1742.  https://doi.org/10.14778/3467861.3467864
  * Xiao et al. (2022) Yingtai Xiao, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. 2022.  Answering Private Linear Queries Adaptively using the Common Mechanism.  _CoRR_ abs/2212.00135 (2022).  https://doi.org/10.48550/arXiv.2212.00135 arXiv:2212.00135
  * Yu et al. (2022) Le Yu, Shufan Zhang, Lu Zhou, Yan Meng, Suguo Du, and Haojin Zhu. 2022.  Thwarting Longitudinal Location Exposure Attacks in Advertising Ecosystem via Edge Computing. In _42nd IEEE International Conference on Distributed Computing Systems, ICDCS 2022, Bologna, Italy, July 10-13, 2022_. IEEE, 470–480.  https://doi.org/10.1109/ICDCS54860.2022.00052
  * Zhang et al. (2018) Dan Zhang, Ryan McKenna, Ios Kotsogiannis, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. 2018.  EKTELO: A Framework for Defining Differentially-Private Computations. In _Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018_ , Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 115–130.  https://doi.org/10.1145/3183713.3196921

##  Appendix A Other DP Notions

Table 2. Notation Summary Notation | Definition
---|---
$\epsilon,\delta$ | The privacy budget
$\mathcal{A},A_{i}$ | (A set of) Data analyst(s)
$\mathcal{D},D$ | Database domain, database instance
$q_{i},v_{i}$ | Query and accuracy requirement associated
$\mathcal{P}$ | The privacy provenance table
$\Psi,\psi$ | (A set of) Privacy constraint(s)
$\mathcal{V},V$ | (A set of) View(s)
$V^{\epsilon},V^{\epsilon}_{A_{i}}$ | Global/Local synopsis

We summarize the common notations in Table 2 and some other DP notions that
are also included and supported in DProvDB.

###### Theorem A.1 (Advanced Composition (Kairouz et al., 2015, 2017)).

For any $\epsilon\geq 0$ and $\delta\in(0,1)$, the $k$-fold composition of
$(\epsilon,\delta)$-DP mechanisms satisfies
$((k-2i)\epsilon,1-(1-\delta)^{k}(1-\delta_{i}))$-DP, for all
$i=\\{0,1,\ldots,\lfloor k/2\rfloor\\}$, where
$\delta_{i}=\frac{\sum_{\ell=0}^{i-1}\binom{k}{\ell}(e^{(k-\ell)\epsilon}-e^{(k-2i+\ell)\epsilon})}{(1+e^{\epsilon})^{k}}$.

###### Definition 0 ($(\alpha,\epsilon)$-Rényi Differential Privacy (Mironov,
2017)).

For $\alpha\geq 1$, we say a privacy mechanism
$\mathcal{M}:\mathcal{D}\rightarrow\mathcal{O}$ satisfies
$(\alpha,\epsilon)$-Rényi-differential-privacy (or RDP) if for all pairs of
neighbouring databases D and D’ and all $O\subseteq\mathcal{O}$, we have

$\mathbb{E}_{O\sim\mathcal{M}(D)}[e^{(\alpha-1)\mathcal{L}_{D/D^{\prime}}(O)}]\leq
e^{(\alpha-1)\epsilon}.$

When $\alpha\rightarrow 1$, $(1,\epsilon)$-RDP is defined to be equivalent to
$\epsilon$-KL privacy (Desfontaines and Pejó, 2020; van Erven and Harremoës,
2014).

###### Theorem A.3 (Rényi DP Composition (Mironov, 2017)).

Given two mechanisms $\mathcal{M}_{1}:\mathcal{D}\rightarrow\mathcal{O}_{1}$
and $\mathcal{M}_{2}:\mathcal{D}\rightarrow\mathcal{O}_{2}$, s.t.
$\mathcal{M}_{1}$ satisfies $(\alpha,\epsilon_{1})$-RDP and $\mathcal{M}_{2}$
satisfies $(\alpha,\epsilon_{2})$-RDP. The combination of the two mechanisms
$\mathcal{M}_{1,2}:\mathcal{D}\rightarrow\mathcal{O}_{1}\times\mathcal{O}_{2}$,
which is a mapping
$\mathcal{M}_{1,2}(D)=(\mathcal{M}_{1}(D),\mathcal{M}_{2}(D))$, is
$(\alpha,\epsilon_{1}+\epsilon_{2})$-RDP.

###### Theorem A.4 (Rényi DP to $(\epsilon,\delta)$-DP (Mironov, 2017)).

If a mechanism $\mathcal{M}$ satisfies $(\alpha,\epsilon)$-RDP, it also
satisfies $(\epsilon+\frac{\log 1/\delta}{\alpha-1},\delta)$-DP, for any
$\delta\in(0,1)$.

DProvDB supports advanced composition and Rényi DP composition for privacy
accounting techniques, other than the basic (sequential) composition.

##  Appendix B Omitted Proofs

###  B.1. Proof of Theorem 3.2

###### Proof of Theorem 3.2.

Note that by our definition of multi-analyst DP, if $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$ satisfies the notion of multi-analyst DP, then on each
coordinate (i.e., for each data analyst), the mechanism provides DP guarantee
according to each data analyst’s privacy budget. Applying the sequential
composition theorem (Theorem 2.2) to each coordinate, we can get this
composition upper bound for multi-analyst DP. ∎

###  B.2. Proof of Theorem 5.3

###### Proof of Theorem 5.3.

For each data analyst $A_{j}$, where $j\in[n]$, its corresponding privacy
budget is $(\epsilon_{j},\delta)$ and the additive Gaussian mechanism
$\mathcal{M}_{aGM}$ returns $r_{j}$ to $A_{j}$. We first prove the additive
Gaussian mechanism $\mathcal{M}_{aGM}$ satisfies multi-analyst-DP, that is, we
need to show that,

(4) $\Pr[\mathcal{M}_{aGM}(D)=r_{j}]\leq
e^{\epsilon_{j}}\Pr[\mathcal{M}_{aGM}(D^{\prime})=r_{j}]+\delta_{j}.$

Case 1. If
$\epsilon_{j}=\max\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n}\\}$, it is
not hard to see the noise generation and addition to the query answer are the
same as in the analytic Gaussian mechanism, and therefore equation 4 holds.

Case 2. If
$\epsilon_{j}\neq\max\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n}\\}$,
w.l.o.g., we can assume
$\epsilon_{i}=\max\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n}\\}$. If we
use analytic Gaussian mechanism to calculate the Gaussian variance, we have,

$\Phi_{\mathcal{N}}\left(\frac{\Delta
q}{2\sigma_{i}}-\frac{\epsilon_{i}\sigma_{i}}{\Delta
q}\right)-e^{\epsilon_{i}}\Phi_{\mathcal{N}}\left(-\frac{\Delta
q}{2\sigma_{i}}-\frac{\epsilon_{i}\sigma_{i}}{\Delta q}\right)\leq\delta$

and

$\Phi_{\mathcal{N}}\left(\frac{\Delta
q}{2\sigma_{j}}-\frac{\epsilon_{j}\sigma_{j}}{\Delta
q}\right)-e^{\epsilon_{j}}\Phi_{\mathcal{N}}\left(-\frac{\Delta
q}{2\sigma_{j}}-\frac{\epsilon_{j}\sigma_{j}}{\Delta q}\right)\leq\delta.$

Then for the noisy answer returned to data analyst $A_{j}$, we have
$r_{j}\coloneqq r_{i}+\eta_{j}=r+\eta_{i}+\eta_{j}$, where
$\eta_{i}\sim\mathcal{N}(0,\sigma_{i}^{2})$ and
$\eta_{j}\sim\mathcal{N}(0,\sigma_{j}^{2}-\sigma_{i}^{2})$. Since $\eta_{i}$
and $\eta_{j}$ are independent random variables drawn from Gaussian
distribution, we obtain $\eta_{i}+\eta_{j}\sim\mathcal{N}(0,\sigma_{j}^{2})$.
Thus, Equation (4) holds according to the analytic Gaussian mechanism (Def.
2.5).

Then we need to prove $\mathcal{M}_{aGM}$ satisfies
$(\max\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n}\\},\delta)$-DP. In the
additive Gaussian mechanism, we look at the true query answer (and the data)
only once and add noise drawn from $\mathcal{N}(0,\sigma_{i}^{2})$ to it
(assuming
$\epsilon_{i}=\max\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n}\\}$).
According to the post-processing theorem of DP (Theorem 2.3), the overall
privacy guarantee is bounded by
$(\max\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{n}\\},\delta)$-DP. ∎

###  B.3. Proof of Theorem 5.15

###### Proof of Theorem 5.15.

We analyze the privacy guarantee for the vanilla approach and the additive
Gaussian approach separately.

_Analysis of the vanilla approach._ In vanilla approach, the accuracy
requirement is translated to the minimal privacy cost (as in Def. 5.1) and
recorded in the privacy provenance table $P$ by composition tools if the
sanity checking passes. The
$[\ldots,(A_{i},\psi_{A_{i}},\delta),\ldots]$-multi-analyst-DP is guaranteed
by the analyst constraint checking on $P$. The privacy loss on each view is
either bounded by its own constraint $\psi_{V_{j}}$ or bounded by the table
constraint $\psi_{P}$ for water-filling specification (Def. 5.14), so DProvDB
guarantees $\min(\psi_{V_{j}},\psi_{P})$-DP for view $V_{j}$. The table
constraint $\psi_{P}$ bounds the overall information disclosure on the private
database. Hence, even when all data analysts $A_{1},\ldots,A_{m}$ collude, the
vanilla mechanism is $\psi_{P}$-DP.

_Analysis of the additive Gaussian approach._ Recall that in the additive
Gaussian approach, the noise added to different analysts’ queries that can be
answered on the same view is calibrated using additive GM. By Theorem 5.3, for
each view $V_{j}$, the mechanism achieves
$[\ldots,(A_{i},\min(\psi_{A_{i}},\psi_{V_{j}}),\delta),\ldots]$-multi-
analyst-DP and $\psi_{V_{j}}$-DP for collusion. Composing for all views, the
mechanism provides $[\ldots,(A_{i},\psi_{A_{i}},\delta),\ldots]$-multi-
analyst-DP and provides $\min(\max\psi_{A_{i}},\sum\psi_{V_{j}})=\psi_{P}$-DP
guarantee for the protected DB. Note that additive Gaussian approach use the
same view constraint specification as in vanilla approach, therefore, provides
the same per view privacy guarantee. ∎

###  B.4. Proof of Theorem 5.16

###### Proof of Theorem 5.16.

Recall the proportional fairness says that for system or mechanism
$\mathcal{M}$, $\forall A_{i},A_{j}$ ($i\neq j$), $l_{i}\leq l_{j}$, we have
$\frac{Err_{i}(M,A_{i},Q)}{\mu(l_{i})}\leq\frac{Err_{j}(M,A_{j},Q)}{\mu(l_{j})}.$
Note that $Err_{i}(M,A_{i},Q)$ represents the amount of privacy budgets spent
by analyst $A_{i}$. When a sufficient number of queries are submitted and
answered, we have $\lim_{|Q|\to\infty}Err_{i}(M,A_{i},Q)=\psi_{A_{i}}$. Then
we show that the inequality holds for both analyst constraint specifications.

_Analysis of the vanilla approach._ (Def. 5.12) In vanilla approach, the
analyst constraint of $A_{i}$ is set as
$\psi_{A_{i}}=\frac{l_{i}}{\sum_{j\in[n]}l_{j}}\psi_{P}$. For a given set of
analysts and their privilege levels, $\frac{\psi_{P}}{\sum_{j\in[n]}l_{j}}$ is
a constant, and therefore $\psi_{A_{i}}$ is a linear function of $l_{i}$. Then
for $l_{i}\leq l_{j}$,
$\frac{Err_{i}(M,A_{i},Q)}{\mu(l_{i})}\leq\frac{Err_{j}(M,A_{j},Q)}{\mu(l_{j})}.$
holds for any linear $\mu(\cdot)$.

_Analysis of the additive Gaussian approach._ (Def. 5.13) In the additive
Gaussian approach, the analyst constraint of $A_{i}$ is set as
$\psi_{A_{i}}=\frac{l_{i}}{l_{max}}\psi_{P}$. Note that $l_{max}$ is the
maximum privilege in the system, not the maximum privilege of a set of
analysts. Thus $\frac{\psi_{P}}{l_{max}}$ is also a constant which makes the
inequality hold as well. ∎

##  Appendix C Other Experimental Evaluation

###  C.1. Implementation Details

We implement DProvDB in Scala 2.12.2 and use sbt as the system dependency
management tool. First, we re-implement the analytic Gaussian mechanism (Balle
and Wang, 2018) library in Scala. Second, we use PostgreSQL as the underlying
database platform and utilize the Breeze library222Breeze (Hall et al., 2021)
is a numerical processing and optimization library for Scala. for noise
calibration and solving the optimization problem in privacy translation (c.f.
additive Gaussian approach). DProvDB works as a middleware between the data
analysts and the existing DP SQL query processing system, and provides
advanced functionalities such as privacy provenance, query control, query
answering over the cached views, and privacy translation. DProvDB enables
additional mechanisms like additive Gaussian mechanism to allow existing DP
SQL systems to answer more queries with the same level of overall privacy
protection under the multi-analyst DP framework. To demonstrate this as a
proof-of-concept, we build DProvDB over Chorus (Johnson et al., 2020), which
is an open-source DP query answering system. That is, DProvDB involves Chorus
as a sub-module and uses its built-in functions, such as database connection
and management, query rewriting (i.e., we use Chorus queries to construct the
histogram DP synopses), and privacy accountant (including the basic
composition and the Rényi composition). Other than the algorithms and
necessary data structures supported by DProvDB, we build the view management
and privacy provenance table management modules, and implement a query
transformation module that can transform the incoming queries into linear
queries over the DP views/synopses.

Implementation of the Provenance Table. The privacy provenance table as a
matrix can be sparse. Similar to the conventional wisdom applied in access
control (di Vimercati, 2011), we can store the privacy provenance table by row
or column to reduce the storage overhead.

###  C.2. Other Results on TPC-H Dataset

We present the missing empirical results on TPC-H dataset, including the end-
to-end comparison (Fig. 10) and the additive GM component analysis (Fig. 11).

###  C.3. Other Results on Adult Dataset

We present the missing run-time performance comparison on Adult dataset in
Table 1.

Table 3. Runtime Performance Comparison over Different Mechanisms on Adult
Dataset (running on a Linux server with 64 GB DDR4 RAM and AMD Ryzen 5 3600
CPU, measured in milliseconds, average over 4 runs)

Systems | Setup Time | Running Time | No. of Queries | Per Query Perf
---|---|---|---|---
DProvDB | 8051.06 ms | 541.77 ms | 294.5 | 1.84 ms
Vanilla | 8051.06 ms | 393.42 ms | 289.5 | 1.36 ms
sPrivateSQL | 8051.06 ms | 564.68 ms | 295.8 | 1.91 ms
Chorus | N/A | 3583.47 ms | 212.0 | 16.90 ms
ChorusP | N/A | 3424.79 ms | 212.0 | 16.15 ms

Figure 10. End-to-end Comparison (_RRQ_ task, over _Adult_ dataset), from left
to right: a) utility v.s. overall budget, round-robin; b) utility v.s. overall
budget, randomized; c) fairness against baselines, round-robin; d) fairness
against baselines, randomized. Figure 11. Component Comparison (_RRQ_ task,
over _Adult_ dataset): Additive GM v.s. Vanilla. Left: utility v.s. #analysts,
round-robin; Right: utility v.s. overall budgets, round-robin.

##  Appendix D Discussion on Design of Views and Supported Queries

As discussed earlier, DProvDB can properly select a set of materialized
histogram views such that incoming queries can be answered using the noisy