Differential privacy and SPARQL

Abstract

Differential privacy is a framework that provides formal tools to develop algorithms to access databases and answer statistical queries with quantifiable accuracy and privacy guarantees. The notions of differential privacy are defined independently of the data model and the query language at steak. Most differential privacy results have been obtained on aggregation queries such as counting or finding maximum or average values, and on grouping queries over aggregations such as the creation of histograms. So far, the data model used by the framework research has typically been the relational model and the query language SQL. However, effective realizations of differential privacy for SQL queries that required joins had been limited. This has imposed severe restrictions on applying differential privacy in RDF knowledge graphs and SPARQL queries. By the simple nature of RDF data, most useful queries accessing RDF graphs will require intensive use of joins. Recently, new differential privacy techniques have been developed that can be applied to many types of joins in SQL with reasonable results. This opened the question of whether these new results carry over to RDF and SPARQL. In this paper we provide a positive answer to this question by presenting an algorithm that can answer counting queries over a large class of SPARQL queries that guarantees differential privacy, if the RDF graph is accompanied with semantic information about its structure. We have implemented our algorithm and conducted several experiments, showing the feasibility of our approach for large graph databases. Our aim has been to present an approach that can be used as a stepping stone towards extensions and other realizations of differential privacy for SPARQL and RDF.

1. Introduction

As many social norms, privacy, or the right to privacy, is an evolving term that is invoked in many contexts as eloquently described by Louis Menand in [25]: “Privacy is associated with liberty, but it is also associated with privilege (private roads and private sales), with confidentiality (private conversations), with nonconformity and dissent, with shame and embarrassment, with the deviant and the taboo (...), and with subterfuge and concealment”.

In order to get some formal underpinning of privacy in the context of electronic data collection and publishing, Li et al [22] have looked at privacy breaches, studied their general characteristics, and concluded, that electronic privacy breaches always ended with giving an attacker the ability to identify (using public data) whether an individual is member of a set or class that had been intended to be anonymous (e.g., the class of individuals with high cholesterol). Hence, they define preservation of privacy as avoiding privacy breaches in the sense of not disclosing set memberships of individuals.

For the public good, such as the advance of public health, or the fair distribution of government resources, such data is frequently made public. There are also situations in which governmental and commercial organizations collect and analyze data to improve or provide new services. Especially in such cases, society expects a certain level of privacy on the way these organizations use the data. Publishing data with perfect privacy means that no assumption can be made about the prior knowledge an attacker may have about the supposedly anonymous set. Under this assumption, there would be little utility in published data if perfect privacy is expected [11,22]. Therefore, the research community has looked at weaker definitions of “acceptable” privacy. Useful concepts like k-anonymity [33], l-diversity [23] and t-closeness [21] were developed but they were shown to have weak privacy guarantees [10].

In spite of its limitations [12], but because of its formal properties, a privacy notion that has gained a lot of acceptance is differential privacy. We will present precise definitions later in the paper, but informally, differential privacy tries to hide the identity of individuals that are members of a particular class, while still providing quantifiable utility guarantees to the data published about the class. The basic principle is simple. Given a universe $\mathbb{D}$ of all possible datasets and a query $\mathit{f}:\mathbb{D}\to \mathcal{R}$ that can be applied to a dataset D in $\mathbb{D}$ and results in a value of an abstract domain $\mathcal{R}$ , f is said to be differentially private if it yields indistinguishable results when applied to similar datasets. Differential privacy uses randomized algorithms to answer queries, typically by adding noise to the true query results. This noise is calibrated according to query sensitivity – how much the query result varies between similar datasets –, turning the task of query sensitivity computation essential for the endeavor of differential privacy. In practice, calculating the exact sensitivity of a query is not trivial and approximations are used instead [3].

Even though the notion of differential privacy is in principle independent of the data model and query language at steak, so far most practical, automated implementations over well-established languages have been in the context of relational databases, over SQL, and have been restricted to aggregation queries or grouping. Aggregations are queries such as counting, finding maximum or average values over a certain data subset; grouping is the creation of histograms based on aggregations.

Furthermore, to allow for reasonable approximations of sensitivity, the support of these implementations for queries with joins has been rather limited [24]. It was only in 2018, when Johnson et al. [19] introduced a new approach to approximate sensitivity that can be applied to a wider class of SQL joins, with reasonable results.

In the past decades, graph data models have enjoyed a growing adoption in comparison to the more traditional relational model. One such notable example is the RDF data standard, queried over by the SPARQL language, which have become extremely popular, in particular, for their role in the development of the Semantic Web. By the simple nature of RDF, it can be stored using binary relations [6] and most interesting queries will require operations equivalent to joins. This raises the question whether Johnson et al.’s approach [19] can also be applied to RDF and SPARQL.

In this paper we provide a positive answer to this question by presenting an algorithm that can answer counting queries over a large class of SPARQL queries that guarantees differential privacy. This result has been made possible by introducing the notion of a differential privacy schema that allows redefining Johnson et al.’s sensitivity approximation of SQL queries in the appropriate terms for answering SPARQL queries. A differential privacy schema groups sets of RDF tuples into sub-graphs that can be then used as single units for privacy protection. Examples show that this type of schema naturally arises from the semantics of the data stored in the tuples, and it should not be difficult for a database administrator to define.

We demonstrate the applicability of our approach by implementing a differential privacy query engine that uses the approximation to answer counting and grouping SPARQL queries, and evaluate the implementation running simulations using the Wikidata knowledge base [34].

The rest of the paper is organized as follows: in Section 2 we introduce the readers to the fundamental concepts of differential privacy. In Section 3, we present the core concepts of SPARQL used within the paper, including the notion of differential privacy schema. In Section 5 we prove the correctness of our proposed approximation to sensitivity and in Section 6 we evaluate the effectiveness of our proposed approximation in an implementation that we apply to both synthetic and real world datasets and queries. We present related work in Section 7, and we conclude the paper in Section 8.

2. Preliminaries about differential privacy

We now describe the framework of differential privacy, the problem that arises when applying differential privacy to SQL queries with general joins and how it has been addressed by the scientific community.

2.1. Definition

Intuitively, a randomized algorithm [26] is differentially private if it behaves similarly on similar input datasets. To formalize this intuition, the framework of differential privacy relies on a notion of distance between datasets. We model datasets as a multiset of tuples and we say that two datasets are k-far apart if one can be obtained from the other by changing the value of k tuples. Formally, this corresponds to (a mild generalization of) the notion of distance used for defining bounded differential privacy [20], which quantifies (only) over pairs of datasets of the same size. In the remainder, we let $\mathbb{D}$ be the set of all possible datasets, and use $\mathit{d}\mathrm{(}\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\mathrm{)}=\mathit{k}$ to denote that $\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\in \mathbb{D}$ are k-far apart. In particular, two datasets $\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\in \mathbb{D}$ that are 1-far apart are called neighbors, written $\mathit{D}\sim {\mathit{D}}^{\prime }$ .

Definition 1.

Let $\mathit{ϵ}\mathrm{,}\mathit{\delta }⩾0$ . A randomized algorithm $\mathcal{A}$ is $\mathrm{(}\mathit{ϵ}\mathrm{,}\mathit{\delta }\mathrm{)}$ -differentially private if for every pair of neighbor datasets $\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\in \mathbb{D}$ and every set $\mathit{S}\subseteq \mathsf{range}\mathrm{(}\mathcal{A}\mathrm{)}$ , $$\begin{array}{c}\mathsf{Pr}[\mathcal{A}\mathrm{(}\mathit{D}\mathrm{)}\in \mathit{S}]⩽{\mathit{e}}^{\mathit{ϵ}}\mathsf{Pr}\left[\mathcal{A}\mathrm{\right(}{\mathit{D}}^{\prime }\mathrm{)}\in \mathit{S}]+\mathit{\delta }.\end{array}$$

This inequality establishes a quantitative closeness condition between $\mathsf{Pr}[\mathcal{A}\mathrm{(}\mathit{D}\mathrm{)}\in \mathit{S}]$ and $\mathsf{Pr}[\mathcal{A}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}\in \mathit{S}]$ , the probabilities that on inputs D and ${\mathit{D}}^{\prime }$ , the outcome of $\mathcal{A}$ lies within S. The smaller the ϵ and δ, the closer these two probabilities are, and therefore, the less likely that an adversary can tell D and ${\mathit{D}}^{\prime }$ apart. In other words, parameters ϵ and δ quantify the privacy guarantees of the randomized algorithm.

Multi-table datasets Our notions of dataset and distance between datasets can be extended to collections of datasets as follows: A dataset formed by multiple sets ${\mathit{D}}_1\mathrm{,}\dots \mathrm{,}{\mathit{D}}_{\mathit{n}}$ will contain (tagged) data points belonging to ${\mathit{D}}_1\mathrm{,}\dots \mathrm{,}{\mathit{D}}_{\mathit{n}}$ and the distance between two such datasets D, ${\mathit{D}}^{\prime }$ will reduce to $\mathit{d}\mathrm{(}\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\mathrm{)}={\sum }_{\mathit{i}=1}^{\mathit{n}}\mathit{d}\mathrm{(}{\mathit{\pi }}_{\mathit{i}}\mathrm{(}\mathit{D}\mathrm{)}\mathrm{,}{\mathit{\pi }}_{\mathit{i}}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}\mathrm{)}$ , ${\mathit{\pi }}_{\mathit{i}}\mathrm{(}\mathit{D}\mathrm{)}$ representing the subset of data points from D belonging to ${\mathit{D}}_{\mathit{i}}$ . In the context of relational databases, the ${\mathit{D}}_{\mathit{i}}$ ’s correspond to relational tables.

2.2. Realization via global sensibility

Establishing differential privacy for numeric queries of limited sensitivity is relatively simple. The Laplacian mechanism [9] says that we can obtain a differentially private version of query $\mathit{f}:\mathbb{D}\to \mathbb{R}$ by simply perturbing its output: On input D, we return $\mathit{f}\mathrm{(}\mathit{D}\mathrm{)}$ plus some noise sampled from a Laplacian distribution. The noise must be calibrated according to the global sensitivity ${\mathsf{GS}}_{\mathit{f}}$ of f, which measures its maximum variation upon neighbor datasets; formally, ${\mathsf{GS}}_{\mathit{f}}={max}_{\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }|\mathit{D}\sim {\mathit{D}}^{\prime }}|\mathit{f}\mathrm{(}\mathit{D}\mathrm{)}-\mathit{f}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}|$ .

Theorem 1.

Given a numeric query $\mathit{f}:\mathbb{D}\to \mathbb{R}$ of global sensitivity ${\mathsf{GS}}_{\mathit{f}}$ , the randomized algorithm $$\begin{array}{c}\mathcal{A}\mathrm{(}\mathit{D}\mathrm{)}=\mathit{f}\mathrm{(}\mathit{D}\mathrm{)}+\mathsf{Lap}\mathrm{\left(}{\displaystyle \frac{{\mathsf{GS}}_{\mathit{f}}}{\mathit{ϵ}}}\mathrm{\right)}\end{array}$$ is an $\mathrm{(}\mathit{ϵ}\mathrm{,}0\mathrm{)}$ -differentially private version of f.

Here, $\mathsf{Lap}\mathrm{(}\mathit{\lambda }\mathrm{)}$ represents a sample from the Laplacian distribution with parameter λ, a symmetric distribution with probability density function $\mathit{pdf}\mathrm{(}\mathit{x}\mathrm{)}=\frac{1}{2\mathit{\lambda }}{\mathit{e}}^{-|\mathit{x}|\mathrm{/}\mathit{\lambda }}$ , mean 0 and variance $2{\mathit{\lambda }}^2$ . Parameter λ measures how concentrated the mass of the distribution is around its mean 0: The smaller the λ, the less noise we add to the true query result and therefore, the more faithful the mechanism becomes. In the realm of differential privacy, this “faithfulness” property is referred to as the mechanism utility [10]. An important point here is that utility and privacy are always conflicting requirements: adding more noise results in more private and – at the same time – less useful mechanisms.

In practice, when implementing the Laplacian mechanism we approximate the global sensibility of queries by exploiting their structures: Numeric queries are typically constructed by first transforming the original dataset using some standard transformers and by returning as final result some aggregation on the obtained dataset. For example, we join two tables, filter the result (dataset transformations) and return the count (aggregation) of the obtained table. The global sensitivity of such a query can be estimated from the so-called stability properties of the involved transformers. Intuitively, a stable transformer can increase the distance between nearby datasets at most by a multiplicative factor. Formally, we call a dataset transformer $\mathit{T}:\mathbb{D}\to \mathbb{D}$ α-globally-stable if $\mathit{d}\mathrm{(}\mathit{T}\mathrm{(}\mathit{D}\mathrm{)}\mathrm{,}\mathit{T}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}\mathrm{)}⩽\mathit{\alpha }\mathit{d}\mathrm{(}\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\mathrm{)}$ for every $\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\in \mathbb{D}$ . Transformers with bounded global stability yield bounded global sensitivities: ${\mathsf{GS}}_{\mathit{f}\circ \mathit{T}}⩽\mathit{\alpha }{\mathsf{GS}}_{\mathit{f}}$ whenever T is α-globally-stable.

Conversely, the use of transformers with unbounded stability might result in queries of unbounded sensitivity. A prominent example of a transformer exhibiting this problem is join. Assume we join two tables, say ${\mathit{t}}_1$ and ${\mathit{t}}_2$ , by matching a pair of their attributes. A modification in a mere tuple from ${\mathit{t}}_1$ may result in the addition and/or deletion of an unpredictable number of tuples in the result of the join, leaving elementary queries such as counting the number of tuples in a join already out of the scope of the Laplacian mechanism. The applicability of differential privacy approaches based on query global sensitivity is thus rather limited.

2.3. Realization via local sensibility

To handle queries that involve transformers of unbounded stability, such as joins, we require the use of more advanced techniques. The Laplacian mechanism calibrates noise according to the query, overlooking the fact that queries are done on concrete datasets, hence the employed noise could be potentially customized for each dataset. Nissim et al. show how to exploit this idea of instance-based noise [27]. Their approach relies on the notion of local sensitivity.

Definition 2.

The local sensitivity ${\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}$ of a numeric query $\mathit{f}:\mathbb{D}\to \mathbb{R}$ on dataset $\mathit{D}\in \mathbb{D}$ is defined as $$\begin{array}{c}{\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}=\underset{{\mathit{D}}^{\prime }|\mathit{d}\mathrm{(}\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\mathrm{)}=1}{max}|\mathit{f}\mathrm{(}\mathit{D}\mathrm{)}-\mathit{f}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{\left)}\right|.\end{array}$$ The local sensitivity ${\mathsf{LS}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{D}\mathrm{)}$ at distance $\mathit{k}\in {\mathbb{N}}_0$ of D is defined as $$\begin{array}{c}{\mathsf{LS}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{D}\mathrm{)}=\underset{{\mathit{D}}^{\prime }|\mathit{d}\mathrm{(}\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\mathrm{)}=\mathit{k}}{max}{\mathsf{LS}}_{\mathit{f}}\mathrm{\left(}{\mathit{D}}^{\prime }\mathrm{\right)}.\end{array}$$

Observe that ${\mathsf{LS}}_{\mathit{f}}^{\mathrm{(}0\mathrm{)}}\mathrm{(}\mathit{D}\mathrm{)}$ coincides with ${\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}$ . Similar to global stability, a dataset transformer $\mathit{T}:\mathbb{D}\to \mathbb{D}$ , is α-local-stable for a dataset D if $\mathit{d}\mathrm{(}\mathit{T}\mathrm{(}\mathit{D}\mathrm{)}\mathrm{,}\mathit{T}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}\mathrm{)}⩽\mathit{\alpha }\mathit{d}\mathrm{(}\mathit{D}\mathrm{,}{\mathit{D}}^{\prime }\mathrm{)}$ for every ${\mathit{D}}^{\prime }\in \mathbb{D}$ . And as with global sensitivity, ${\mathsf{LS}}_{\mathit{f}\circ \mathit{T}}\mathrm{(}\mathit{D}\mathrm{)}⩽\mathit{\alpha }{\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}$ whenever T is α-local-stable for D.

For answering a query f on dataset D, we cannot simply use noise calibrated according to ${\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}$ because the noise level itself may reveal information about D [19]. Instead, we should use an approximation of ${\mathsf{LS}}_{\mathit{f}}$ that is insensitive to small variations of its input dataset. This is captured by the notion of smooth upper bound.

Definition 3.

A function ${\mathcal{U}}_{\mathit{f}}:\mathbb{D}\to {\mathbb{R}}_{⩾0}$ is called a β-smooth upper bound of the local sensitivity ${\mathsf{LS}}_{\mathit{f}}:\mathbb{D}\to {\mathbb{R}}_{⩾0}$ of query $\mathit{f}:\mathbb{D}\to \mathbb{R}$ if it satisfies the following requirements:

${\mathcal{U}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}⩾{\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}$ for all dataset D, and

${\mathcal{U}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}⩽{\mathit{e}}^{\mathit{\beta }}{\mathcal{U}}_{\mathit{f}}\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}$ for all neighbor datasets D and ${\mathit{D}}^{\prime }$ .

We can readily achieve differential privacy by adding noise calibrated according to a smooth upper bound of the query local sensitivity [28, Corollary 2.4].

Theorem 2.

Let $\mathit{f}:\mathbb{D}\to \mathbb{R}$ be a numeric query and let ${\mathcal{U}}_{\mathit{f}}:\mathbb{D}\to {\mathbb{R}}_{⩾0}$ be a β-smooth upper bound of its local sensitivity ${\mathsf{LS}}_{\mathit{f}}$ . Moreover, let $\mathit{\delta }\in \mathrm{(}0\mathrm{,}1\mathrm{)}$ and let $\mathit{\beta }⩽\frac{\mathit{ϵ}}{2ln\mathrm{(}2\mathrm{/}\mathit{\delta }\mathrm{)}}$ . Then, the randomized algorithm $$\begin{array}{c}\mathcal{A}\mathrm{(}\mathit{D}\mathrm{)}=\mathit{f}\mathrm{(}\mathit{D}\mathrm{)}+\mathsf{Lap}\mathrm{\left(}{\displaystyle \frac{2{\mathcal{U}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}}{\mathit{ϵ}}}\mathrm{\right)}\end{array}$$ is an $\mathrm{(}\mathit{ϵ}\mathrm{,}\mathit{\delta }\mathrm{)}$ -differentially private version of f.

The benefits of this mechanism are twofold. On the one hand, it allows handling queries that fail to have a bounded global sensitivity, but do have a bounded local sensitivity. These include e.g. the query we considered earlier, consisting of the count of the join between two tables. On the other hand, it does not require computing the local sensitivity of the queries itself, but only a smooth upper bound thereof. This is key for its practical adoption since calculating the local sensitivity of queries is computationally prohibitive: As observed by Johnson et al. [19], “it requires running the query on every possible neighbor of the original dataset”.

To apply the mechanism from Theorem 2, we must provide a smooth upper bound for the local sensitivity of queries. We can construct the smooth upper bound using approximations for the local sensitivity at fixed distances.

Lemma 1.

Let $\mathit{f}:\mathbb{D}\to \mathbb{R}$ be a numeric query and assume that ${\mathcal{U}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}$ is a pointwise upper bound of the local sensitivity ${\mathsf{LS}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}$ of f at distance k, that is, $$\begin{array}{c}{\mathcal{U}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{D}\mathrm{)}⩾{\mathsf{LS}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{D}\mathrm{)}\mathit{\text{for all }}\mathit{D}\in \mathbb{D}.\end{array}$$ Then, $$\begin{array}{c}{\mathcal{U}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}=\underset{0⩽\mathit{k}⩽\mathit{size}\mathrm{(}\mathit{D}\mathrm{)}}{max}{\mathit{e}}^{-\mathit{\beta }\mathit{k}}{\mathcal{U}}_{\mathit{f}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{D}\mathrm{)}\end{array}$$ is a β-smooth upper bound of the local sensitivity ${\mathsf{LS}}_{\mathit{f}}\mathrm{(}\mathit{D}\mathrm{)}$ of f on D, where $\mathit{size}\mathrm{(}\mathit{D}\mathrm{)}$ denotes the number of rows (in all the tables) in D.

The goal of Section 5 is to apply the differential privacy mechanism from Theorem 2 to SPARQL counting queries. To do so, we will use Lemma 1 to derive smooth upper bounds of the local sensitivity of queries. In turn, this requires constructing upper bounds for the local sensitivity of queries at fixed distances, for which we will leverage local stability properties of SPARQL dataset transformers.

3. Toward differential privacy over RDF graphs

In this section we examine the semantic information that is necessary considering over RDF graphs, in order to answer counting queries in a differentially private manner. This comprises a data schema and upper bounds on the predicate multiplicities.

3.1. Privacy schema

3.1.1. Motivation

As mentioned earlier, the goal of differential privacy is to protect the (possibly sensible) contribution of each individual within a dataset when publicly releasing aggregate information about the dataset – in our case, the result of counting queries. In the relational model, individuals are typically identified with rows of the database which significantly simplifies all the technical development. For instance, if the database at stake consists of a single table, we consider two instances of the database neighboring, i.e. differing in the contribution of a single individual, if they differ in a single row. On the other hand, if the database consists of multiple tables, we consider two database instances neighboring if they differ in a row of some of the tables (see paragraph in Section 2). The underlying assumption behind this is that each table groups attributes of individuals in a particular entity type, e.g. people, political parties or companies, or part thereof, whose identities must be protected.

Fig. 1.

RDF graph $\mathcal{G}$ containing information about three types of entities: people, companies and cites.

To be able to apply differential privacy to a dataset in the form of an RDF graph, we must thus begin by identifying the different types of entities present in the graph, and the set of individuals in each type. Consider, for instance, the RDF graph $\mathcal{G}$ in Fig. 1, which will be the running example of our presentation. This graph contains information about three types of entities: people, companies and cites. In particular, it contains information about two people (depicted in ), two companies (depicted in ) and two cities (depicted in ). Said otherwise, there are two individuals of each entity type, adding up to six individuals in all. When querying the graph, we will be interested in protecting the contribution of all these individuals, and when applying differential privacy techniques to this end, we will then consider as a neighbor any other graph that differs in the contribution of either of them.

We refer to the semantic information necessary to identify the individuals in an RDF graph $\mathcal{G}$ as a differential privacy schema. More formally, its goal is to partition $\mathcal{G}$ as a set $\{{\mathit{g}}_1\mathrm{,}\dots \mathrm{,}{\mathit{g}}_{\mathit{n}}\}$ of sub-graphs, where each ${\mathit{g}}_{\mathit{i}}$ represents the contribution of an individual, and $\mathcal{G}={⨄}_{\mathit{i}}{\mathit{g}}_{\mathit{i}}$ is the disjoint union of all these sub-graphs. For example, the graph in Fig. 1 is decomposed as the disjoint union of the pair of sub-graphs in blue, the pair of sub-graphs red and the pair of sub-graphs green. Observe that in the relational model, this corresponds to nothing more than understanding a (set of) table(s) as the disjoint union of its (their) rows. Here, our interest is to protect the contribution of the individuals represented by each ${\mathit{g}}_{\mathit{i}}$ . In Fig. 1, this means, for example, the data related to Alice and to the Walt Disney company.

3.1.2. Formal definition

We briefly review some basic RDF terminology following standard notation used in the literature [14,16], where more details can be found. The RDF language assumes the existence of an infinite set U (of URI references), an infinite set B (of blank nodes), and an infinite set L (of RDF literals). An RDF triple is a term of the form $\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{,}{\mathit{v}}_3\mathrm{)}\in \mathrm{(}\mathit{U}\cup \mathit{B}\mathrm{)}\times \mathit{U}\times \mathrm{(}\mathit{U}\cup \mathit{B}\cup \mathit{L}\mathrm{)}$ . An RDF dataset is a finite set of RDF triples. RDF triples are interpreted as labeled arcs or edges in a directed graph from a vertex ${\mathit{v}}_1$ , called the triple subject, to a vertex ${\mathit{v}}_3$ , called the triple object, and label ${\mathit{v}}_2$ , called the triple predicate. Figure 1 shows an example of an RDF graph $\mathcal{G}$ . We denote by $\mathit{voc}\mathrm{(}\mathcal{G}\mathrm{)}$ the finite subset of elements from $\mathrm{(}\mathit{U}\cup \mathit{B}\cup \mathit{L}\mathrm{)}$ that appear in $\mathcal{G}$ . More importantly, because of the nature of the aggregation queries under consideration, we will restrict ourselves to graphs without blank nodes, i.e. graphs where $\mathit{B}=\varnothing$ .1

¹

Calculation of query sensitivity will depend on the domain of blank nodes which can change under different contexts and implementations. This is a topic of future research.

We also require a restricted version of the concept of triple patterns, which, similarly to RDF triples, are terms of the form $\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{,}{\mathit{v}}_3\mathrm{)}\in \mathrm{(}\mathit{U}\cup \mathit{B}\cup \mathit{V}\mathrm{)}\times \mathit{U}\times \mathrm{(}\mathit{U}\cup \mathit{B}\cup \mathit{L}\cup \mathit{V}\mathrm{)}$ , with V an infinite set of variables, and basic graph patterns (BGPs) which are finite sets of triple patterns.2 ²

The more general definition of triple patterns allows also for variables in the predicate component of triple patterns.

To hint how we can formally define entities within an RDF graph, observe first the six colored sub-graphs identified in Fig. 1: two green, two blue and two red. All have a star shape [1], consisting of a “center” with outgoing and/or incoming edges, i.e. predicates. Sub-graphs representing individuals of the same entity type are built from the same set of predicates. For example, both (blue) sub-graphs, representing people, are built from predicates $\mathsf{phone}$ , $\mathsf{livesIn}$ and $\mathsf{member}$ . We can characterize entity types through a set of triple patterns (i.e. a BGP) that share a common or “join” vertex. Formally, a join vertex in a BGP is a variable that appears either as a subject or as an object multiple times in the BGP. The type of BGP’s that we need have further restrictions, which are captured by the notion of star BGP below:

Definition 4 (Star BGP).

A BGP is called a star if

both the subject and the object of all its triple patterns are variables,

all triple patterns have different predicates, and

it consists of either

• a single triple pattern with no join vertex, i.e. a triple pattern whose subject and object are distinct variables, or

• multiple triple patterns with a single join vertex, which appears once and only once in every triple pattern

Example 3.1 (Star BGP).

The three stars employed to identify the different entities in our running example (Fig. 1) are (modulo variable renaming):

Note that in each $\mathit{S}{}_{\mathit{i}}$ , the vertex denoted by $?c_i$ plays the role of the star center, joining all the triple patterns in $\mathit{S}{}_{\mathit{i}}$ . Furthermore, there are no common predicates across , and . Formally, we define the center of a star as the join vertex if the star contains multiple patterns, or the variable appearing in the subject of the triple pattern in case it consists of a single triple pattern.3

³

The notion of star BGP that we use here is similar to that of star query from [1], except that in a star query the center of the star must always appear as subject.

We say that a set of stars is pairwise predicate-disjoint (or simply pairwise disjoint when no ambiguity arises), if no pair of stars in the collection share a common predicate. They thus define what we call a differential privacy schema:

Definition 5 (Dp-schema).

A differential privacy schema (dp-schema, for short) $\mathcal{P}$ is a finite pairwise predicate-disjoint set of stars.

The set is a dp-schema. as well as its sub-set . However, this second schema falls short of describing the whole graph $\mathcal{G}$ , as it leaves out the information related to cities. To formally capture this completeness condition, we require the notion of induced sub-graph, whose formal definition is based on (solution) mappings. In SPARQL, a (solution) mapping is a partial mapping from variables to URI references or blank nodes, $\mathit{\mu }:\mathit{V}\to \mathit{U}\cup \mathit{B}$ . For a triple pattern $\mathit{tp}$ , $\mathit{\mu }\mathrm{(}\mathit{tp}\mathrm{)}$ denotes the triple obtained after replacing the variables in $\mathit{tp}$ according to μ. If μ is defined for all variables in $\mathit{tp}$ , $\mathit{\mu }\mathrm{(}\mathit{tp}\mathrm{)}$ is an RDF triple. Given a graph $\mathcal{G}$ , the solution mappings of a triple pattern $\mathit{tp}$ over $\mathcal{G}$ , denoted by ${[[\mathit{tp}]]}_{\mathcal{G}}$ , is defined by the set $\{\mathit{\mu }|\mathit{\mu }\mathrm{(}\mathit{tp}\mathrm{)}\in \mathcal{G}\}$ . Now, we are ready to define the concept of induced sub-graph:

Definition 6 (Induced sub-graphs).

Let $\mathcal{G}$ be an RDF graph and $?\mathit{x}$ the center of a star BGP $\mathit{S}$ . Given some $\mathit{y}\in \mathit{U}$ , let ${\mathit{\mu }}_{\mathit{y}}$ denote the mapping $\{?\mathit{x}\to \mathit{y}\}$ . The subgraph of $\mathcal{G}$ induced by $\mathit{S}$ and y, denoted by $\mathit{ind}{\mathrm{(}\mathit{S}\mathrm{)}}_{\mathcal{G}}^{\mathit{y}}$ , is defined by the set of RDF triples $\{\mathit{\mu }\mathrm{(}{\mathit{\mu }}_{\mathit{y}}\mathrm{(}\mathit{tp}\mathrm{)}\mathrm{)}|\mathit{\mu }\in {[[{\mathit{\mu }}_{\mathit{y}}\mathrm{(}\mathit{tp}\mathrm{)}]]}_{\mathcal{G}}\wedge \mathit{tp}\in \mathit{S}\}$ , and the subgraphs of $\mathcal{G}$ induced by $\mathit{S}$ , denoted by $\mathit{S}\mathrm{(}|\mathcal{G}|\mathrm{)}$ , is the set of RDF sub-graphs $\{\mathit{ind}{\mathrm{(}\mathit{S}\mathrm{)}}_{\mathcal{G}}^{\mathit{y}}|\mathit{y}\in \mathit{voc}\mathrm{(}\mathcal{G}\mathrm{)}\}$ .

Example 3.2 (Induced sub-graph).

The star induces two sub-graphs and over $\mathcal{G}$ , i.e.. These correspond to the blue sub-graphs in Fig. 1, which are formally defined as:

Likewise, , where

Intuitively, the set of induced sub-graphs $\mathit{S}$ (| $\mathcal{G}$ |) can be recovered by evaluating $\mathit{S}$ over $\mathcal{G}$ , but assuming that the triple patterns in $\mathit{S}$ are optional. This assumption is already exposed by the example, where the triple pattern $\mathrm{(}?s_2\mathrm{,}\mathsf{member}\mathrm{,}?c_1\mathrm{)}$ belongs to , but it is not materialized in . From the privacy point of view, the values of the star center are the unique identifiers of the entities contributing the data in each sub-graph, and their values must be kept confidential.

The notion of induced sub-graphs naturally extends from single stars, to dp-schemas, i.e. sets of stars. Concretely, we let $\mathcal{P}\mathrm{(}|\mathcal{G}|\mathrm{)}={\bigcup }_{\mathit{S}\in \mathcal{P}}\mathit{S}\mathrm{(}|\mathcal{G}|\mathrm{)}$ be the set of sub-graphs of $\mathcal{G}$ induced by dp-schema $\mathcal{P}$ . In our example, .

Now we have all the prerequisites to define the core concept of this section:

Definition 7 (Dp-schema compliance).

We say that an RDF graph $\mathcal{G}$ complies with a dp-schema $\mathcal{P}$ iff $\mathcal{G}$ coincides with the graph induced by $\mathcal{P}$ in $\mathcal{G}$ , i.e. if $\mathcal{G}={\bigcup }_{\mathit{g}\in \mathcal{P}\mathrm{(}|\mathcal{G}|\mathrm{)}}\mathit{g}$ .

Example 3.3 (Dp-schema compliance).

Our running example $\mathcal{G}$ complies with dp-schema . In contrast, it does not comply with dp-schema .

In summary, if a graph $\mathcal{G}$ complies with a dp-schema $\mathcal{P}$ , the schema partitions the graph into a finite set $\mathcal{P}\mathrm{(}|\mathcal{G}|\mathrm{)}$ of sub-graphs, which intuitively model the different individuals in the graph. The fact that sub-graphs are disjoint follows from the definition of dp-schema, which requires stars in the schema to be pairwise predicate disjoint, and that all the occurrences of variables in a star are different except for the center of the star. The fact that the set of sub-graphs cover the entire graph follows from the definition of compliance.

3.1.3. Discussion

We now address a few key points about dp-schemas.

No shared attribute between entities At first sight, the requirement that stars in a dp-schema be predicate pairwise disjoint might seem a limitation, as it requires that each attribute belong to a single entity type. For instance, it might seem natural to consider that predicate $\mathsf{employs}$ should be part of both the employer and the employee, and it should be thus present in both (which identifies companies) and (which identifies people). However, for the sake of protection it makes no difference to which star it belongs, since our application of differential privacy will protect the contribution of all individuals, regardless of its type.

Existence of dp-schemas RDF graphs always admit compliant dp-schemas. In particular, every graph complies with a trivial dp-schema comprising the union of all singleton BGP’s of the form $\{\mathrm{(}?\mathit{x}\mathrm{,}\mathit{p}\mathrm{,}?\mathit{y}\mathrm{)}\}$ , where p ranges over the set of predicates appearing in $\mathcal{G}$ . Intuitively, this schema indicates that each RDF triple is the contribution of a different individual. Even though this is a valid dp-schema, it will yield very weak privacy guarantees. In general, database administrators should aim to provide dp-schemes with a maximal number of triple patterns per star since, as we will see later, it will allow better approximations of queries’ local sensitivity, and thus, better privacy guarantees.

Compliance verification Checking whether an RDF graph complies with a given schema $\mathcal{P}$ is algorithmically straightforward as it amounts to verifying that all predicates in the graph appear also in (some star of) the schema (which, using a hashing algorithm, can be done in $\mathit{O}\mathrm{(}\mathit{n}\mathrm{)}$ steps, n being the number of predicates in the graph).

Dp-schema provision For practical purposes, we assume that the database administrator of the RDF graph at stake is responsible for designing the dp-schema the graph shall comply with, and for ensuring the compliance as the graph evolves. In this latter regard, observe that removing an RDF triple from the graph always preserves the dp-schema compliance, and adding a triple also preserves compliance provided the predicate in the triple already appears in the dp-schema. We believe this is a natural assumption, as in the relational data model this would correspond to changing the schema of the database by adding a new attribute to a relation if the new predicate is incorporated into an existing star of the dp-schema or creating a new table if the predicate is added to the dp-schema as a new star.

3.2. Predicate multiplicity

Automatic approaches to answer dataset queries in a differentially private manner are typically obtained by adding noise to the query results, calibrated according to their sensitivity. Thus, a prerequisite to apply differential privacy to counting queries over RDF graphs is that they have bounded sensitivity. Unfortunately, this does not occur in the general case.

To see this, consider graph $\mathcal{G}$ of our running example and query “How many phone numbers are currently in use?”. If we evaluate the query over $\mathcal{G}$ , the answer is 3. Now assume we consider a neighboring graph ${\mathcal{G}}^{\prime }$ , where Bob’s contribution (i.e. sub-graph ) is replaced by somebody else’s contribution. The query answer over this neighboring graph can certainly be any integer $\mathit{n}⩾1$ , since a priori we do not know how many phone numbers this new individual might have. Therefore, the sensitivity of the query becomes unbounded.

This problem arises because of the presence of predicates that are not one-to-one. To recover bounded sensitivities, we have to restrict ourselves to predicates that have bounded multiplicity. For instance, if the administrator of graph $\mathcal{G}$ requires that individuals declare at most 5 phone numbers, then the above query will have a local sensitivity of at most 5 (recall that if ${\mathit{n}}_1\mathrm{,}{\mathit{n}}_2⩽\mathit{\alpha }$ , then $|{\mathit{n}}_1-{\mathit{n}}_2|⩽\mathit{\alpha }$ ). This approach was already taken by other authors [2,3] to bound the sensitivity of counting queries (in the presence of joins), and is the price one has to pay to apply differential privacy over RDF graphs.

On the formal level, we associate such bounds to triple patterns rather than to predicates. This is because in the presence of compliant dp-schemas, predicates are identified with triple patterns (every predicate within a dp-schema occurs in a single triple pattern, in a single star).

Definition 8 (Triple-pattern multiplicity).

Let $\mathcal{G}$ be an RDF graph that complies with a dp-schema $\mathcal{P}$ . A multiplicity bound κ associates to each triple pattern $\mathit{tp}$ in a star $\mathit{S}$ of $\mathcal{P}$ an integer $\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$ that upper-bounds the number of solution mappings $\mathit{\mu }\in {[[\mathit{tp}]]}_{\mathcal{G}}$ with the same image for the center of $\mathit{S}$ .

Many predicates (or equivalently, triple patterns) would have a natural multiplicity bound of 1. For instance, a city has a unique $\mathsf{area}$ and a unique number of $\mathsf{dailyRobberies}$ . Likewise, we can assume that a person $\mathsf{livesIn}$ a single city (at least for formal purposes). On the other hand, if a predicate does not admit a natural bound for its multiplicity, think e.g. of predicate $\mathsf{friend}$ , we can either a) choose an upper bound that covers most of the cases in practice or b) establish an upper bound in accordance with the size of the graph that the administrator is willing to support.

Henceforth, in the remainder we assume the system administrator provides a dp-scheme $\mathcal{P}$ and that every graph $\mathcal{G}$ is compliant with the dp-scheme $\mathcal{P}$ . Furthermore, we assume that the administrator establishes an upper bound $\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$ for each triple pattern $\mathit{tp}$ in $\mathcal{P}$ . Hence, the graph space that we consider for the purposes of differential privacy will be that of graphs that comply with both $\mathcal{P}$ and κ.

For bounding the local sensitivity of queries in Section 5, it will suffices a coarser notion of multiplicity, at the level of stars rather than triple patterns. The required generalization is straightforward:

Definition 9 (Star multiplicity).

Let $\mathcal{G}$ be an RDF graph that complies with a dp-schema $\mathcal{P}$ and has a multiplicity bound κ. We call the multiplicity of a star $\mathit{S}\in \mathcal{P}$ , by notation convenience written $\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ , to the product of the multiplicity bound of the triple patterns in $\mathit{S}$ , i.e. $\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}={\prod }_{\mathit{tp}\in \mathit{S}}\mathit{\kappa }\mathrm{(}\mathit{tp}\mathrm{)}$ .

Example 3.4 (Star multiplicity).

Assume that a graph administrator adopts dp-schema and requires that each individual $\mathsf{liveIn}$ (at most) a single city, declare at most five phone numbers and be member of at most 3 secret societies. Then the star will have multiplicity .

4. Queries

In this section we describe the subset of queries over RDF graphs for which we provide differential privacy, and show how dp-schemes enable a decomposition result for the evaluation of such queries.

4.1. Supported queries

We develop differential privacy for counting queries over the SPARQL fragment of basic graph patterns with filter expressions, also known as constrained basic graph pattern (CBGP) [1]. In this fragment, a query is denoted by a pair $$\begin{array}{c}\overline{\mathit{B}}=⟨\mathit{B}\mathrm{,}\mathit{F}⟩\mathrm{,}\end{array}$$ where B is a finite set of triple patterns, i.e. a BGP, and $\mathit{F}=\{{\mathit{f}}_1\mathrm{,}\dots \mathrm{,}{\mathit{f}}_{\mathit{n}}\}$ is a finite (possibly empty) set of filter expressions. $\overline{\mathit{B}}$ represents the SPARQL graph pattern $$\begin{array}{c}\mathit{P}=\mathrm{\left(}\mathrm{\right(}\dots \mathrm{(}\mathit{B}\mathsf{FILTER}{\mathit{f}}_1\mathrm{)}\dots \mathrm{\left)}\mathsf{FILTER}{\mathit{f}}_{\mathit{n}}\mathrm{\right)}\mathrm{,}\end{array}$$ and its meaning over an RDF graph $\mathcal{G}$ , denote by ${[[\overline{\mathit{B}}]]}_{\mathcal{G}}$ , is the multiset of solution mappings ${[[\mathit{P}]]}_{\mathcal{G}}$ as defined by the standard semantics of SPARQL queries [16].

For simplicity, we consider only CBGPs that are semantically valid. We also assume that in a graph $\mathcal{G}$ that complies with a dp-schema $\mathcal{P}$ , all predicates appearing in triple patterns of a CBGP also appear in $\mathcal{P}$ .

Example 4.1.

Take RDF graph $\mathcal{G}$ , which complies with dp-schema . Now assume we want to know how many people have a coworker in a company with headquarters in a city with over 20 daily robberies? The query can be cast in terms of the CBGP $\overline{\mathit{B}}=⟨\mathit{B}\mathrm{,}\mathit{F}⟩$ , where $$\begin{array}{c}\begin{array}{rl}\mathit{B}=& \{\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{employs}\mathrm{,}?p_1\mathrm{)}\mathrm{,}\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{employs}\mathrm{,}?p_2\mathrm{)}\mathrm{,}\mathrm{(}?p_2\mathrm{,}\mathsf{livesIn}\mathrm{,}?\mathsf{c}\mathrm{)}\mathrm{,}\mathrm{(}?\mathsf{c}\mathrm{,}\mathsf{dailyRobberies}\mathrm{,}?\mathsf{n}\mathrm{)}\}\end{array}\\ \mathit{F}=\{?\mathsf{n}⩾\mathsf{20}\}\end{array}$$

Triple patterns in an RDF graph compliant with a dp-schema $\mathcal{P}$ naturally inherit the notion of center from the star they “belong to”. Specifically, for a star $\mathit{S}\in \mathcal{P}$ and a triple pattern $\mathit{tp}=\mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}$ such that $\mathrm{(}\mathit{X}\mathrm{,}\mathit{p}\mathrm{,}\mathit{Y}\mathrm{)}$ belongs to $\mathit{S}$ , for some variables X, Y, we let $\mathit{center}\mathrm{(}\mathit{tp}\mathrm{,}\mathcal{P}\mathrm{)}=\mathit{s}$ if X is the center of $\mathit{S}$ ; otherwise $\mathit{center}\mathrm{(}\mathit{tp}\mathrm{,}\mathcal{P}\mathrm{)}=\mathit{o}$ . For instance, in the above example we have $$\begin{array}{c}\mathit{center}\mathrm{(}\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{employs}\mathrm{,}?p_1\mathrm{)}\mathrm{,}\mathcal{P}\mathrm{)}=?\mathsf{x}\\ \mathit{center}\mathrm{(}\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{employs}\mathrm{,}?p_2\mathrm{)}\mathrm{,}\mathcal{P}\mathrm{)}=?\mathsf{x}\mathrm{,}\end{array}$$ since star which contains the triple pattern $$\begin{array}{c}\mathrm{(}?c_2\mathrm{,}\mathsf{employs}\mathrm{,}?o_3\mathrm{)}\end{array}$$ has center $?c_2$ . Note that center is a well-defined function because the predicate of any triple pattern can only appear in single star of the dp-schema. In the remainder, we write $\mathit{center}\mathrm{(}\mathit{tp}\mathrm{)}$ for $\mathit{center}\mathrm{(}\mathit{tp}\mathrm{,}\mathcal{P}\mathrm{)}$ when $\mathcal{P}$ is understood from the context (e.g. when referring to the dp-schema established by the administrator of the RDF graph at stake).

Finally, a user query is a CBGP $\overline{\mathit{B}}$ wrapped by either of the two following aggregation operations:

${\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ , whose semantics ${[[\mathsf{COUN}{T}^{?x}\mathrm{(}\overline{\mathit{B}}\mathrm{)}]]}_{\mathcal{G}}$ is defined as the cardinality of the multiset ${[[\overline{\mathit{B}}]]}_{\mathcal{G}}$ .

${\mathsf{COUNT}}^{\mathsf{DISTINCT}?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ , whose semantics ${[[\mathsf{COUN}{T}^{\mathsf{DISTINCT}?x}\mathrm{(}\overline{\mathit{B}}\mathrm{)}]]}_{\mathcal{G}}$ is defined as the cardinality of the set $\{\mathit{\mu }\mathrm{(}?\mathit{x}\mathrm{)}|\mathit{\mu }\in {[[\overline{\mathit{B}}]]}_{\mathcal{G}}\}$ .

${\mathsf{COUNT}}_{?{\mathit{x}}_1\dots ?{\mathit{x}}_{\mathit{n}}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ , where $?\mathit{x}\mathrm{,}?{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}?{\mathit{x}}_{\mathit{n}}$ are variables appearing in $\overline{\mathit{B}}$ , and whose semantics ${[[{\mathsf{COUNT}}_{?{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}?{\mathit{x}}_{\mathit{n}}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}]]}_{\mathcal{G}}$ is defined by grouping the solution mappings from ${[[\overline{\mathit{B}}]]}_{\mathcal{G}}$ according to (the values they assign to) variables $?{\mathit{x}}_1\dots ?{\mathit{x}}_{\mathit{n}}$ and returning the number of mappings within each of the resulting groups. Loosely speaking, this corresponds to a histogram over tuples grouped by keys created by the different combinations of the values assigned to variables $?{\mathit{x}}_1\dots ?{\mathit{x}}_{\mathit{n}}$ by the solution mappings from ${[[\overline{\mathit{B}}]]}_{\mathcal{G}}$ .

Example 4.2.

The query from the previous example can be expressed as ${\mathsf{COUNT}}^{\mathsf{DISTINCT}?p_1}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ using the previous CBGP.

4.2. Evaluation decomposition

Continuing with the previous example, assume we want to evaluate B (from Example 4.1) over $\mathcal{G}$ (from Fig. 1), that is, to compute ${[[\mathit{B}]]}_{\mathcal{G}}$ (observe that if we are interested in obtaining ${[[⟨\mathit{B}\mathrm{,}\mathit{F}⟩]]}_{\mathcal{G}}$ instead, we simply add a $\mathsf{FILTER}$ operation on top of the evaluation of ${[[\mathit{B}]]}_{\mathcal{G}}$ ). We can do this in a compositional fashion, leveraging the partition that dp-schema induces on $\mathcal{G}$ . Concretely, we can split B as $$\begin{array}{}\text{(1)}& \begin{array}{rl}& {\mathit{B}}_1=\left\{\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{employs}\mathrm{,}?p_1\mathrm{)}\right\}\\ & {\mathit{B}}_2=\left\{\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{employs}\mathrm{,}?p_2\mathrm{)}\right\}\\ & {\mathit{B}}_3=\left\{\mathrm{(}?p_2\mathrm{,}\mathsf{livesIn}\mathrm{,}?\mathsf{c}\mathrm{)}\right\}\\ & {\mathit{B}}_4=\{\mathrm{(}?\mathsf{c}\mathrm{,}\mathsf{dailyRobberies}\mathrm{,}?\mathsf{n}\mathrm{)}\}\end{array}& \end{array}$$

Hence, for any query $\overline{\mathit{B}}=⟨\mathit{B}\mathrm{,}\mathit{F}⟩$ , we can formally define a split ${\mathit{B}}_{÷\mathcal{P}}$ of B from a dp-schema $\mathcal{P}$ , as follows: ${\mathit{B}}_{÷\mathcal{P}}=\{{\mathit{B}}_1\mathrm{,}\dots \mathrm{,}{\mathit{B}}_{\mathit{n}}\}$ iff the following two conditions hold

every ${\mathit{B}}_{\mathit{i}}\in {\mathit{B}}_{÷\mathcal{P}}$ i) is a maximal subset of B for which there exists a star $\mathit{S}\in \mathcal{P}$ such that $\mathit{pred}\mathrm{(}{\mathit{B}}_{\mathit{i}}\mathrm{)}\subseteq \mathit{p}\mathit{r}\mathit{e}\mathit{d}\mathrm{(}\mathit{S}\mathrm{)}$ , and ii) has no predicate repetitions;

for any two triple patterns $\mathit{tp}\mathrm{,}{\mathit{tp}}^{\prime }\in {\mathit{B}}_{\mathit{i}}$ , $\mathit{center}\mathrm{(}\mathit{tp}\mathrm{)}=\mathit{center}\mathrm{(}{\mathit{tp}}^{\prime }\mathrm{)}$ .

Because the stars in $\mathcal{P}$ are predicate disjoint and the ${\mathit{B}}_{\mathit{i}}$ ’s in ${\mathit{B}}_{÷\mathcal{P}}$ are maximal, the split ${\mathit{B}}_{÷\mathcal{P}}$ is unique. In the context of Condition 1 above, we call $\mathit{S}$ the covering star of ${\mathit{B}}_{\mathit{i}}$ . Moreover, we call a BGP B elementary if $|{\mathit{B}}_{÷\mathcal{P}}|=1$ , and, by construction, all members of a split will be elementary.

Example 4.3.

For the CBGP from Example 4.1, B is split into four elementary BGPs by dp-schema , i.e. ${\mathit{B}}_{÷\mathcal{P}}=\{{\mathit{B}}_1\mathrm{,}{\mathit{B}}_2\mathrm{,}{\mathit{B}}_3\mathrm{,}{\mathit{B}}_4\}$ as defined in Equation (1) above. Note that ${\mathit{B}}_1$ and ${\mathit{B}}_2$ have both the same covering star , but they are consireded different elementary BGPs because they share predicate $\mathsf{employs}$ . The covering stars of ${\mathit{B}}_3$ and ${\mathit{B}}_4$ are and , respectively.

If B were extended, e.g. , with triple pattern $$\begin{array}{c}\mathit{tp}=\mathrm{(}\mathsf{Skull}\mathsf{and}\mathsf{Bones}\mathrm{,}\mathsf{member}\mathrm{,}?p_1\mathrm{)}\mathrm{,}\end{array}$$ the splitting ${\mathit{B}}_{÷\mathcal{P}}$ would contain a fifth, member ${\mathit{B}}_5=\{\mathit{tp}\}$ . In this case, ${\mathit{B}}_3$ and ${\mathit{B}}_5$ share the same covering star, , but remain different members of ${\mathit{B}}_{÷\mathcal{P}}$ because their triple patterns have different centers ( $?p_2$ is the center of triple patterns in ${\mathit{B}}_3$ and $?p_1$ the center of the triple pattern in ${\mathit{B}}_5$ ). Alternatively, if B were extended, e.g., with triple pattern $$\begin{array}{c}{\mathit{tp}}^{\prime }=\mathrm{(}?\mathsf{x}\mathrm{,}\mathsf{headquarter}\mathrm{,}\mathsf{Burbank}\mathrm{)}\mathrm{,}\end{array}$$ the number of elementary BGPs does not change but ${\mathit{B}}_1$ and ${\mathit{B}}_2$ should be both augmented with ${\mathit{tp}}^{\prime }$ due to the maximality condition of each ${\mathit{B}}_{\mathit{i}}$ . (In this case, ${\mathit{B}}_1$ and ${\mathit{B}}_2$ remain being covered by star .)

Note also that the elementary BGP where a triple pattern belongs to is determined by the center of the triple pattern, all triple patterns in the same split must share the same variable or RDF term as their center. The interest in ${\mathit{B}}_{÷\mathcal{P}}=\{{\mathit{B}}_1\mathrm{,}\dots \mathrm{,}{\mathit{B}}_{\mathit{n}}\}$ resides in that it lets us isolate the fragment of the graph necessary to answer each ${\mathit{B}}_{\mathit{i}}$ . Assume we denote by ${\mathcal{G}}_{\mathit{S}{}_{\mathit{i}}}$ the subgraph induced by star $\mathit{S}{}_{\mathit{i}}$ , i.e. ${\mathcal{G}}_{\mathit{S}{}_{\mathit{i}}}={\bigcup }_{\mathit{g}\in \mathit{S}{}_{\mathit{i}}\mathrm{(}|\mathcal{G}|\mathrm{)}}\mathit{g}$ .

Lemma 2.

If $\mathit{S}{}_{\mathit{i}}$ is the covering star of ${\mathit{B}}_{\mathit{i}}$ then $$\begin{array}{c}{[[{\mathit{B}}_{\mathit{i}}]]}_{\mathcal{G}}={[[{\mathit{B}}_{\mathit{i}}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{i}}}}\end{array}$$

Then, following the terminology defined in [29] for joins between multisets of solution mappings, we can extend the lemma to B as follows:

Lemma 3.

$$\begin{array}{c}{[[\mathit{B}]]}_{\mathcal{G}}={[[{\mathit{B}}_1]]}_{{\mathcal{G}}_{\mathit{S}{}_1}}\bowtie \mathrm{(}{[[{\mathit{B}}_2]]}_{{\mathcal{G}}_{\mathit{S}{}_2}}\bowtie \cdots \bowtie \mathrm{(}{[[{\mathit{B}}_{\mathit{n}-1}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{n}-1}}}\bowtie {[[{\mathit{B}}_{\mathit{n}}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{n}}}}\mathrm{)}\mathrm{)}\end{array}$$

We have already observed that $\overline{\mathit{B}}$ is such that ${[[\mathit{B}]]}_{\mathcal{G}}$ can be evaluated using only equi-joins. Therefore, there must exist an ordering of the elements in ${\mathit{B}}_{÷\mathcal{P}}$ such that ${[[{\mathit{B}}_{\mathit{i}}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{i}}}}\bowtie {[[{\mathit{B}}_{\mathit{i}+1}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{i}+1}}}$ can also be done with equi-joins. In other words, an ordering where $|\mathit{var}\mathrm{(}{\mathit{B}}_{\mathit{i}}\mathrm{)}\cap \mathit{var}\mathrm{(}{\mathit{B}}_{\mathit{i}+1}\mathrm{)}|=1$ for all $1⩽\mathit{i}\mathrm{<}\mathit{n}$ . We call this order a normal ordering of ${\mathit{B}}_{÷\mathcal{P}}$ , and without loss of generality denote by $?{\mathit{x}}_{\mathit{i}}$ the variable in the equi-join ${[[{\mathit{B}}_{\mathit{i}}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{i}}}}\bowtie {[[{\mathit{B}}_{\mathit{i}+1}]]}_{{\mathcal{G}}_{\mathit{S}{}_{\mathit{i}+1}}}$ . For convenience, in the remainder we assume that the indexing used for ${\mathit{B}}_{÷\mathcal{P}}$ follows a normal order. Note that this is already the case for the splitting from Example 4.3 ( ${\mathit{B}}_1$ and ${\mathit{B}}_2$ share variable $p_2$ , and ${\mathit{B}}_2$ and ${\mathit{B}}_3$ share variable $\mathsf{c}$ ).

We are now in a position to establish differential privacy for SPARQL count and histogram queries.

5. Towards differential privacy for SPARQL

In this section we develop all the prerequisites to extend Lemma 1 from the relational model to the graph model, in terms of the $\text{SPARQL}$ queries over RDF graphs described in the previous section.

5.1. Preliminary notions

We begin defining the notion of size and distance between RDF graphs. These are straightforward adaptations of the relational case, where the induced sub-graphs play the role of table rows. Concretely, the size of a graph refers to the number of individuals present in it. Formally, given an RDF graph $\mathcal{G}$ that complies with a dp-schema $\mathcal{P}={\{{\mathit{B}}_{\mathit{i}}\}}_{\mathit{i}\in \mathit{I}}$ , we define the size of $\mathcal{G}$ w.r.t. $\mathcal{P}$ as $\mathit{size}{\mathrm{(}\mathcal{G}\mathrm{)}}_{\mathcal{P}}={\sum }_{\mathit{i}\in \mathit{I}}|{\mathit{B}}_{\mathit{i}}\mathrm{(}|\mathcal{G}|\mathrm{)}|$ .

Moreover, we say that two graphs are k far apart if one can be obtained from the other by replacing k of its induced sub-graphs. Formally, given a pair of RDF graphs ${\mathcal{G}}_1$ , ${\mathcal{G}}_2$ that comply with a dp-schema $\mathcal{P}={\{{\mathit{B}}_{\mathit{i}}\}}_{\mathit{i}\in \mathit{I}}$ and such that $\mathit{size}{\mathrm{(}{\mathcal{G}}_1\mathrm{)}}_{\mathcal{P}}=\mathit{size}{\mathrm{(}{\mathcal{G}}_2\mathrm{)}}_{\mathcal{P}}$ , their distance is defined as the size of their difference, i.e. $\mathit{d}{\mathrm{(}{\mathcal{G}}_1\mathrm{,}{\mathcal{G}}_2\mathrm{)}}_{\mathcal{P}}=\mathit{size}{\mathrm{(}{\mathcal{G}}_1\setminus {\mathcal{G}}_2\mathrm{)}}_{\mathcal{P}}$ . Note that in the general case where the sizes of ${\mathcal{G}}_1$ and ${\mathcal{G}}_2$ need not coincide, their distance is defined as the size of the their symmetrical difference $\mathrm{(}{\mathcal{G}}_1\setminus {\mathcal{G}}_2\mathrm{)}\cup \mathrm{(}{\mathcal{G}}_2\setminus {\mathcal{G}}_1\mathrm{)}$ , but when the sizes coincide, this reduces to the size of either their differences, making distance commutative as expected.

Finally, this notion of distance between RDF graphs readily induces a notion of local sensitivity (at distance k) ${\mathsf{LS}}_{\mathit{Q}}\mathrm{(}\mathcal{G}\mathrm{)}$ ( ${\mathsf{LS}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ ) of $\text{SPARQL}$ query Q over RDF graph $\mathcal{G}$ , as given by Definition 2.

In order not to clutter the presentation, we usually omit the underlying dp-schema when referring to the size of an RDF graph, the distance between a pair of RDF graphs, and the local sensitivity of a $\text{SPARQL}$ query if the dp-schema is understood from the context.

5.2. Elastic sensitivity

Our next step is, given a user query Q and an RDF graph $\mathcal{G}$ that complies with a dp-schema $\mathcal{P}$ , to compute an upper bound of the local sensitivity ${\mathsf{LS}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ (denoted by ${\mathcal{U}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ in Lemma 1).

To this end, observe that the naive approach of evaluating the query on every neighbor (at distance k) of $\mathcal{G}$ is not a feasible solution, since the number of neighbors can be extremely large. To address this problem in the relational setting, Johnson et al. [19] has introduced the notion of elastic sensitivity, which leverages (maximum) frequency values of the join keys (that can be precomputed or statistically estimated) to provide more efficient upper bounds for the local sensitivity of queries with joins.

In the remainder of the section we adapt Johnson et al.’s approach to the case of RDF graphs and $\text{SPARQL}$ . Intuitively, our notion of elastic sensitivity of a $\text{SPARQL}$ query Q at distance k of a concrete graph $\mathcal{G}$ (that complies with the dp-schema $\mathcal{P}$ ) regards the evaluation of Q as the composition of successive transformations applied to $\mathcal{G}$ , and is defined in terms of the stability properties of such transformations.

In our case, these transformations are given by the CBGP of user queries, more concretely, by their BGP part. We thus introduce the auxiliary notion of BGP elastic stability. A key property of this notion is that it allows bounding the local sensitivity of counting queries: Given a BGP B, its elastic stability at distance k with respect to a graph $\mathcal{G}$ that complies with a dp-schema $\mathcal{P}$ , bounds the local stability for any graph ${\mathcal{G}}^{\prime }$ that also complies with $\mathcal{P}$ and is at distance k of $\mathcal{G}$ . Hence, it bounds the local sensitivity at distance k of ${\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ (for any $\overline{\mathit{B}}=⟨\mathit{B}\mathrm{,}\mathit{F}⟩$ ) over ${\mathcal{G}}^{\prime }$ .

The formal definition of elastic stability relies on the frequency of most popular values. More precisely, if $?\mathit{x}$ is a variable occurring in an elementary BGP B, we use $\mathit{mpv}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}$ to denote the frequency of the most popular value to which $?\mathit{x}$ is mapped to, when evaluating B over $\mathcal{G}$ . We can use $\text{SPARQL}$ itself to determine $\mathit{mpv}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}$ through the query $$\begin{array}{rl}& \mathsf{SELECT}\mathrm{(}\mathsf{COUNT}\mathrm{(}?\mathit{x}\mathrm{)}\mathit{a}\mathit{s}?\mathit{c}\mathrm{)}\mathsf{WHERE}\mathit{B}\\ & \mathsf{GROUP}\text{\_}\mathsf{BY}?\mathit{x}\mathsf{ORDER}\text{\_}\mathsf{BY}?\mathit{c}\mathsf{DESC}\mathsf{LIMIT}1\end{array}$$ Loosely speaking, this corresponds to first evaluating ${\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\mathit{B}\mathrm{)}$ , and then selecting the value with the largest count. This is an upper bound for the frequency of the most popular value yielded by $?\mathit{x}$ within a CBGP query $\overline{\mathit{B}}=⟨\mathit{B}\mathrm{,}\mathit{F}⟩$ , regardless of the filter F, since it can only reduce the size of the result. Alternatively, we could also use the query $$\begin{array}{rl}& \mathsf{SELECT}\mathrm{(}\mathsf{COUNT}\mathrm{(}?\mathit{x}\mathrm{)}\mathit{a}\mathit{s}?\mathit{c}\mathrm{)}\mathsf{WHERE}\mathit{tp}\\ & \mathsf{GROUP}\text{\_}\mathsf{BY}?\mathit{x}\mathsf{ORDER}\text{\_}\mathsf{BY}?\mathit{c}\mathsf{DESC}\mathsf{LIMIT}1\mathrm{,}\end{array}$$ where $\mathit{tp}$ is obtained from a triple pattern in B that 1) has $?\mathit{x}$ as one of its non-predicate (i.e. subject or object) components; 2) $?\mathit{x}$ is participating in a join of the full query $\overline{\mathit{B}}$ ; and 3) it has the other non-predicate component replaced by a fresh variable.4

⁴

Observe that there might be multiple such triple patterns in B, all of them yielding valid upper bounds for $\mathit{mpv}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}$ . If we are interested in obtaining tighter privacy guarantees, we should choose the most precise bound.

The counting on the latter query will be greater than (or equal to) the one on the former query and, therefore, a valid (possibly looser, though) upper bound for $\mathit{mpv}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}$ . Nevertheless, the benefit is that since the second query is merely a variable renaming of a ${\mathit{tp}}^{\prime }\in \mathit{S}$ , the values can be pre-computed for all ${\mathit{tp}}^{\prime }\in \mathit{S}$ within a dp-schema, and simply retrieved during (differentially private) query evaluation. This is possible because the dp-schema of an RDF graph is defined with a set of predicates that includes all the predicates appearing the graph. In contrast, if the former query is used to determine mpv, the sensitivity is likely to be more accurate (i.e. tighter approximations) resulting in better privacy guarantees (smaller ϵ’s), but pre-computations cannot be done, possibly impacting system performance.

To compute the elastic stability of BGP B at distance k of graph $\mathcal{G}$ , written ${\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ , we start by applying Lemma 3 to decompose B as a sequence of elementary BGPs. Once we fix a normal ordering, we have ${\mathit{B}}_{÷\mathcal{P}}={\mathit{B}}_1\bowtie \mathrm{(}{\mathit{B}}_2\bowtie \mathrm{(}\dots \bowtie {\mathit{B}}_{\mathit{n}}\mathrm{)}\dots \mathrm{)}$ . This decomposition allows estimating the frequency of most popular values of graphs k far apart from $\mathcal{G}$ . Formally, the frequency of the most popular values for variable $?\mathit{x}$ in a BGP B for graphs at distance k of $\mathcal{G}$ , written ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}$ , is defined by induction on the length $|{\mathit{B}}_{÷\mathcal{P}}|$ as follows:

Base case: If $|{\mathit{B}}_{÷\mathcal{P}}|=1$ , we let $$\begin{array}{c}{\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}=\mathit{mpv}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}+\mathit{k}\times \mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}\mathrm{,}\end{array}$$ where S is the covering star of ${\mathit{B}}_1$ (recall that, in this base case, ${\mathit{B}}_{÷\mathcal{P}}=\{{\mathit{B}}_1\}$ ).

Inductive case: If $|{\mathit{B}}_{÷\mathcal{P}}|\mathrm{>}1$ , we let $$\begin{array}{rl}{\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?\mathit{x}\mathrm{,}\mathit{B}\mathrm{,}\mathcal{G}\mathrm{)}=& {\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_{÷\mathcal{P}}\setminus \{{\mathit{B}}_1\}\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?\mathit{x}\mathrm{,}{\mathit{B}}_1\mathrm{,}\mathcal{G}\mathrm{)}\mathrm{,}\end{array}$$ where $?{\mathit{x}}_1$ is the common variable shared by ${\mathit{B}}_1$ and $\mathrm{(}{\mathit{B}}_2\bowtie \mathrm{(}\dots \bowtie {\mathit{B}}_{\mathit{n}}\mathrm{)}\dots \mathrm{)}$ , used for their equi-join.

The intuition behind the base case is easy to grasp. For $\mathit{k}=1$ , we take a subgraph from $\mathcal{P}\mathrm{(}|\mathcal{G}|\mathrm{)}$ , induced by a star BFP S in the schema, and replace it with a different one. The maximal difference between the new and the old value on the count of the most popular mapping value of $?\mathit{x}$ is $\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ . This is an upper bound of all the mappings that can be produced by the instance due to the triple-pattern multiplicity, if the instance removed didn’t have an instance of the value and a new instance of the same value is added. Hence, k changes will at most increment the count by $\mathit{k}\times \mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ . For the inductive case, we need to worry about the most frequent mapping value of $?{\mathit{x}}_1$ in ${\mathit{B}}_{÷\mathcal{P}}\setminus \{{\mathit{B}}_1\}$ since for every mapping of $?\mathit{x}$ obtained from ${\mathit{B}}_1$ , if this mapping maps $?{\mathit{x}}_1$ in ${\mathit{B}}_1$ to the same value of the most frequent value of ${\mathit{x}}_1$ in ${\mathit{B}}_{÷\mathcal{P}}\setminus \{{\mathit{B}}_1\}$ , the value of $?\mathit{x}$ will be repeated as many times in the combined mapping of B. Hence, the most frequent value of $?\mathit{x}$ in ${[[{\mathit{B}}_1]]}_{\mathit{S}{}_1}$ can be duplicated, in the worst case, as many as ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_{÷\mathcal{P}}\setminus \{{\mathit{B}}_1\}\mathrm{,}\mathcal{G}\mathrm{)}$ times in the multiset of solution mappings ${[[\mathit{B}]]}_{\mathcal{G}}$ , giving us a safe upper bound for the count. Importantly, observe that because the multiplication operation is commutative, the frequency is not affected by the selected normal ordering.

We are now ready to define the elastic stability of a BGP B at distance k of graph $\mathcal{G}$ , denoted by ${\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ . The definition also proceeds by induction on the cardinality of a fixed normal ordering of ${\mathit{B}}_{÷\mathcal{P}}={\mathit{B}}_1\bowtie \mathrm{(}{\mathit{B}}_2\bowtie \mathrm{(}\dots \bowtie {\mathit{B}}_{\mathit{n}}\mathrm{)}\dots \mathrm{)}$ :

Base case: If $|{\mathit{B}}_{÷\mathcal{P}}|=1$ , we let $$\begin{array}{c}{\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}\mathrm{,}\end{array}$$ where S is the covering star of ${\mathit{B}}_1$ .

Inductive case: If $|{\mathit{B}}_{÷\mathcal{P}}|\mathrm{>}1$ , let ${\mathit{B}}^{\prime }={\mathit{B}}_{÷\mathcal{P}}\setminus \{{\mathit{B}}_1\}$ . We have two cases. If the covering star S of ${\mathit{B}}_1$ is not the covering star of any other ${\mathit{B}}_{\mathit{j}}\in {\mathit{B}}^{\prime }$ , we let $$\begin{array}{}\text{(2)}& {\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=& max\{{\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_1\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\mathrm{,}{\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}^{\prime }\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\}\end{array}$$

If the covering star S of ${\mathit{B}}_1$ is also the covering star of another ${\mathit{B}}_{\mathit{j}}\in {\mathit{B}}^{\prime }$ , we let $$\begin{array}{rl}{\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=& {\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_1\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}+{\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}^{\prime }\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}+{\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\end{array}$$ Loosely speaking, this definition captures the amount of changes that the transformations (i.e. the joins) within the query, add to the final result, when modifying a single element in the induced schema.

As so defined, the local stability bounds the local sensitivity of counting queries:

Lemma 4.

For any CBGP query $\overline{\mathit{B}}=⟨\mathit{B}\mathrm{,}\mathit{F}⟩$ , any $\mathit{k}\in \mathbb{N}$ and any graph $\mathcal{G}$ compliant with dp-schema $\mathcal{P}$ : $$\begin{array}{c}{\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}⩾{\mathsf{LS}}_{{\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}.\end{array}$$

The main intuition behind the proof is that changes made to a graph to get a new graph at distance 1, are limited to a sub-graph ${\mathcal{G}}_{\mathit{i}}$ , that must be covered by a single star pattern $\mathit{S}$ in $\mathcal{P}$ . Then the maximum number of RDF tuples that can change to get the graph at distance 1 is limited by the multiplicity of the predicates in S. Therefore, the change in the number of mappings obtained from the new graph of an elementary BGP covered by S is bounded by $\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ . If these RDF triples contribute in the result mappings of a join vertex, the number of new mappings can increase by as much as the frequency of the most popular result mapping of the joining triple pattern. For example, if $\mathit{B}=\{\mathrm{(}?v_0\mathrm{,}\mathsf{p}\mathrm{,}?\mathsf{u}\mathrm{)}\mathrm{,}\mathrm{(}?\mathsf{u}\mathrm{,}{p}^{\prime }\mathrm{,}?v_1\mathrm{)}\}$ , and the triple $\mathrm{(}\mathsf{s}\mathrm{,}\mathsf{p}\mathrm{,}\mathsf{o}\mathrm{)}$ is part of ${\mathcal{G}}_1$ and o happens to be the most popular result mapping for $\mathrm{(}?\mathsf{u}\mathrm{,}{p}^{\prime }\mathrm{,}?v_1\mathrm{)}$ , then there will be at most ${\mathit{mpv}}^{\mathrm{(}1\mathrm{)}}\mathrm{(}?\mathsf{u}\mathrm{,}\mathrm{(}?\mathsf{u}\mathrm{,}{p}^{\prime }\mathrm{,}?v_1\mathrm{)}\mathrm{,}\mathcal{G}\mathrm{)}$ new mappings in the result.

Proof.

The proof of this lemma follows the same strategy as the proof in [19, Lemma 2], and is by induction on the length of ${\mathit{B}}_{÷\mathcal{P}}$ .

Case $|{\mathit{B}}_{÷\mathcal{P}}|=1$ . Let S be the covering star of B. Hence, its elastic stability is $\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ , a parameter given by the DBA. Thus, we have $$\begin{array}{c}\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}={\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}⩾{\mathsf{LS}}_{{\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\end{array}$$ since the local sensitivity at distance k is calculated as the max of the sensitivities of all graphs at distance 1 of all graphs at distance k or less of $\mathcal{G}$ , meaning the modification of a single star, which may change by at most $\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ tuples and the filter in $\overline{\mathit{B}}$ doesn’t affect its local stability.

Case $|{\mathit{B}}_{÷\mathcal{P}}|=\mathit{n}+1$ : we have a covering star ${\mathit{S}}_1$ for partition ${\mathit{B}}_1$ and a set with n covering stars for partitions ${\mathit{B}}^{\prime }=\{{\mathit{B}}_2\mathrm{,}\dots {\mathit{B}}_{\mathit{n}+1}\}$ . We want to bound the number of RDF triples that can change in graphs ${\mathcal{G}}^{\prime }$ at distance k of $\mathcal{G}$ to get a graph at distance 1, based on the star multiplicities. First, let’s assume ${\mathit{S}}_1$ is not the covering star of any other ${\mathit{B}}_{\mathit{i}}$ in ${\mathit{B}}^{\prime }$ . Hence, changes can happen in either ${\mathcal{G}}_{{\mathit{S}}_1}^{\prime }$ or in a graph ${\mathcal{G}}_{{\mathit{S}}^{\prime }}^{\prime }$ induced by a star ${\mathit{S}}^{\prime }$ different from ${\mathit{S}}_1$ that covers some other ${\mathit{B}}_{\mathit{i}}\in {\mathit{B}}^{\prime }$ , but not in both graphs since the new graph must be at distance 1 from ${\mathcal{G}}^{\prime }$ . Thus, either ${\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=0$ or ${\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=0$ :

When ${\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=0$ , the changes in ${\mathcal{G}}_{{\mathit{S}}^{\prime }}^{\prime }$ , by induction hypothesis using Eq. (2), produce at most ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_1\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ changed mappings since one change in ${\mathcal{G}}_{{\mathit{S}}^{\prime }}^{\prime }$ might affect at most ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_1\mathrm{,}\mathcal{G}\mathrm{)}$ triplets in the same join when applied to a graph at distance 1 of ${\mathcal{G}}^{\prime }$ .

In the symmetric case, when ${\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=0$ , ${\mathcal{G}}_{{\mathit{S}}_1}^{\prime }$ may contain ${\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ changed triplets, producing at most ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}^{\prime }\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ changed mappings in the joined $\text{SPARQL}$ pattern.

We chose the largest of the two values when calculating ${\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ . On the other hand, if ${\mathit{S}}_1$ also covers another ${\mathit{B}}_{\mathit{i}}\in {\mathit{B}}^{\prime }$ , a change in ${\mathcal{G}}_{{\mathit{S}}_1}^{\prime }$ can also imply changes in ${\mathcal{G}}_{{\mathit{S}}^{\prime }}^{\prime }$ . This can cause, in the worst case, ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}_1\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ changed mappings for the change happening in ${\mathcal{G}}_{{\mathit{S}}^{\prime }}^{\prime }$ , plus ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}?{\mathit{x}}_1\mathrm{,}{\mathit{B}}^{\prime }\mathrm{,}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ changed mappings caused by the change in ${\mathcal{G}}_{{\mathit{S}}_1}$ , which may contain ${\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=\mathit{\kappa }\mathrm{(}\mathit{S}\mathrm{)}$ changed triplets. We also need to consider that the change may cause new joins between then new triplets in both ${\mathcal{G}}_{{\mathit{S}}_1}^{\prime }$ and ${\mathcal{G}}_{{\mathit{S}}^{\prime }}^{\prime }$ , for a total of ${\mathcal{S}}_{{\mathit{B}}_1}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\times {\mathcal{S}}_{{\mathit{B}}^{\prime }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ changed mappings in the joined $\text{SPARQL}$ pattern. The sum of these three values is what the definition of ${\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ uses.

 □

Now we have all the prerequisite to define the elastic sensitivity of user queries (at fixed distances of a given graph): $$\begin{array}{c}{\mathsf{ES}}_{{\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}={\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\\ {\mathsf{ES}}_{{\mathsf{COUNT}}^{\mathsf{DISTINC}\mathit{T}?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}={\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\\ {\mathsf{ES}}_{{\mathsf{COUNT}}_{?\overline{\mathit{x}}}^{?{\mathit{x}}_0}\mathrm{(}\overline{\mathit{B}}\mathrm{)}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}=2{\mathcal{S}}_{\mathit{B}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\end{array}$$

And as in Johnson et al. [19], the above lemma readily leads us to the desired bound for (the three kind of) user queries:

Lemma 5.

For any user query Q, and any graph $\mathcal{G}$ compliant with schema $\mathcal{P}$ : $$\begin{array}{c}{\mathsf{ES}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}⩾{\mathsf{LS}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}.\end{array}$$

Proof.

By case analysis on the type of user query Q:

For plain counting queries ( $\mathit{Q}={\mathsf{COUNT}}^{?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ ): the result follows directly from Lemma 4 since the result of the counting query is given by the application of the sensitivity calculation for the $\mathit{C}\mathit{B}\mathit{G}\mathit{P}\mathit{s}$ in the query.

For plain unique counting queries ( $\mathit{Q}={\mathsf{COUNT}}^{\mathsf{DISTINCT}?\mathit{x}}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ ): it can be noted that $\mathsf{DISTINCT}$ reduces the elastic stability of the elementary BGP, ${\mathit{B}}^{\prime }$ , containing $?\mathit{x}$ from $\mathit{\kappa }\mathrm{(}{\mathit{S}}^{\prime }\mathrm{)}$ to 1, where ${\mathit{S}}^{\prime }$ is the star covering ${\mathit{B}}^{\prime }$ .

For counting queries after grouping ( $\mathit{Q}={\mathsf{COUNT}}_{?\overline{\mathit{x}}}^{?{\mathit{x}}_0}\mathrm{(}\overline{\mathit{B}}\mathrm{)}$ ): During the grouping, each changed triple can affect two result mappings in the query since one modified triple may generate a mapping that will fall into a new group, and at the same time the old mapping is dropped from another group.

 □

Lemma 5 readily establishes our main result, which allows applying differential privacy to $\text{SPARQL}$ queries over RDF graphs:

Theorem 3.

Assume that our universe of (valid) RDF graphs is composed by the graphs that comply with dp-schema $\mathcal{P}$ and multiplicity bound κ and let $\mathcal{G}$ be any of those graphs. Let Q be a user query and let $$\begin{array}{c}{\mathcal{U}}_{\mathit{Q}}\mathrm{(}\mathcal{G}\mathrm{)}=\underset{0⩽\mathit{k}⩽\mathit{size}{\mathrm{(}\mathcal{G}\mathrm{)}}_{\mathcal{P}}}{max}{\mathit{e}}^{-\mathit{\beta }\mathit{k}}{\mathsf{ES}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}\mathrm{,}\end{array}$$ where $\mathit{ϵ}\mathrm{>}0$ , $0\mathrm{<}\mathit{\delta }\mathrm{<}1$ , $\mathit{\beta }⩽\frac{\mathit{ϵ}}{2ln\mathrm{(}2\mathrm{/}\mathit{\delta }\mathrm{)}}$ and the elastic sensitivity ${\mathsf{ES}}_{\mathit{Q}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathcal{G}\mathrm{)}$ of Q is computed, as previously described, from multiplicity bound κ and the frequencies of most popular values mapped to the variables in Q as specified by function ${\mathit{mpv}}^{\mathrm{(}\mathit{k}\mathrm{)}}$ . Then, the randomized algorithm $$\begin{array}{c}\mathcal{A}\mathrm{(}\mathcal{G}\mathrm{)}={[[\mathit{Q}]]}_{\mathcal{G}}+\mathsf{Lap}\mathrm{\left(}{\displaystyle \frac{2{\mathcal{U}}_{\mathit{Q}}\mathrm{(}\mathcal{G}\mathrm{)}}{\mathit{ϵ}}}\mathrm{\right)}\end{array}$$ is an $\mathrm{(}\mathit{ϵ}\mathrm{,}\mathit{\delta }\mathrm{)}$ -differentially private version of Q.

The theorem follows immediately from Theorem 2 and Lemmas 1 and 5.

6. Evaluation

Having characterized formally how an algorithm can be implemented to enforce differential privacy on SPARQL queries based on privacy schemes, in this section, we present an empirical evaluation of how the algorithm would behave in real scenarios.

Setup We conducted our evaluation on a 2018 Macbook Pro with 16 GB of RAM memory having installed a Fuseki instance on a 2 AMD Opteron server with an SSD drive and 64 GB of RAM memory. We used Java 1.17 to implement our proof of concept. We also used the SecureRandom Java class to generate the random numbers to calculate the Laplacian probability distribution since that class implements a well-tested random number generator,5

⁵

https://docs.oracle.com/javase/8/docs/api/java/security/SecureRandom.html

an essential component for ensuring the correctness of our privacy guarantees algorithm. The code and all the queries used for this evaluation are available in GitHub.6 ⁶

Repository https://github.com/cbuil/DPSparql.

Data In the evaluation we used real world data and queries from Wikidata [34]. Wikidata is a collaboratively edited knowledge base hosted by the Wikimedia Foundation. It is a common source of data for Wikimedia projects such as Wikipedia, and it has been made available to the general public under a public domain license. Wikidata stores 86,671,701 items (RDF resources), and 1,084,935,969 statements (triples7 ⁷

https://tools.wmflabs.org/wikidata-todo/stats.php

). We selected a subset of the Wikidata Truthy from 2021-06-23, which has all but direct properties (i.e. http://www.wikidata.org/prop/direct/P*) removed [18,35]. The data is available to download from Google Drive.8 ⁸

https://drive.google.com/u/0/uc?id=1oDkrHT68_v7wfzTxjaRg40F7itb7tVEZ

We also provide the scripts to generate this Wikidata version in our Github repository.9 ⁹

https://github.com/MillenniumDB/benchmark/blob/master/src/database_generation/filter_direct_properties.py

We use the following prefixes from Wikidata along this section:

6.1. Privacy schema

Our dp-schema is defined based on three pairwise disjoint stars, ${\mathcal{P}}_1$ , ${\mathcal{P}}_2$ , and ${\mathcal{P}}_3$ , representing data from Humans, Organizations, and Professions, built around Wikidata’s P31 property (the instance of property). We extracted URIs from all the instances of the classes Human, Organization and Profession using queries like:

This gathers the instances of the class Human. Star instances were formed by selecting a subset of properties of the three classes using star queries centered in the URIs (each instance representing either a Human, an Organization or a Profession) to define three sub-graphs covered by three stars, ${\mathcal{P}}_1$ , ${\mathcal{P}}_2$ , and ${\mathcal{P}}_3$ . In other words, we used the mappings of ?center from the initial queries as star centers and for each center we retrieved a few of their properties and used the resulting RDF graph as the basis for our queries. Differential privacy is applied to protect the privacy of the centers. We present the schema with all the properties we used for each star in the following example.

Evaluation privacy schema The three stars employed to identify the different entities in our evaluation schema are (modulo variable renaming):

These three stars shouldn’t be used directly as a privacy schema because $\mathit{S}{}_1$ and $\mathit{S}{}_3$ share a property, P106. Nevertheless, the sets of instances of the property in the sub-graphs induced by $\mathit{S}{}_1$ and $\mathit{S}{}_3$ are disjoint because instances of $?{\mathit{c}}_1$ (human UIRs) and $?{\mathit{c}}_2$ (organization URIs) are disjoint. Hence, for the purpose of our evaluation, we consider this partition of P106 as two different properties that we refer to as P106 Profession in $\mathit{S}{}_1$ and P106 Occupation in $\mathit{S}{}_3$ , keep $\mathit{S}{}_3$ as it is, and rename them ${\mathcal{P}}_1$ , ${\mathcal{P}}_2$ , and ${\mathcal{P}}_3$ respectively.10

¹⁰

Note that this observation suggests a more subtle definition of privacy scheme would be useful.

The Wikidata properties that allow joining data from two different stars are P108 Employer from Humans to Organizations, P106 Profession from Humans to Professions, P106 Occupation from Organizations to Professions and P112 Founded by from Organizations to Humans. Table 1 shows statistics about the instances of the stars in our data, including star size (on top of the table).

Table 1

Table showing key statistics about the data in our privacy schema (the largest schema is by far the Humans star)

Humans: 9,181,487
P569	P570	P106	P108	P2002
5,109,648	2,511,719	6,446,811	1,085,617	159,194
P21	P40
7,223,891	707,747

Professions: 7,786
P1963	P101	P425
97	95	3,018

Organizations: 72,879
P106	P178	P112
50	16	2,789

6.2. Queries

We selected 26 queries from the query logs in [18,35] containing the predicates used in our dp-schema. Since the amount of COUNT queries in the query logs is small [4] for each of these queries we added the COUNT keyword and we removed the triples from the query that were not accessing our schema. In addition, these queries were modified to get a diverse set of query results and types.

We consider star queries which are queries covered by a single star from the dp-schema. These queries can only add filters and remove triple patterns from the star. Therefore, a star query is centered around a single join vertex $?{\mathit{x}}_0$ , corresponding to the center of the star (Fig. 2). We also have linear queries describing a path that must include a join variable that appears in a place that is not the center of any star from the dp-schema (Fig. 3), and snowflake queries (Fig. 4), a concatenation through a join variable of a star query with other queries of different shapes, as defined in [1]. The queries are listed in Appendix B and they can also be found in the companion Github repository for this article. Table 3, also in Appendix A, summarizes their characteristics. We show ${\mathit{Q}}_3$ in Fig. 4, which queries the Humans star, accessing sex, birth and death dates for each human as well as their professions. We use the ?professions variable for connecting to the Professions star. From that star we retrieve each profession’s field of work (property P425), obtaining a snowflake-shaped query.

Fig. 2.

Star-shaped query ${\mathit{Q}}_{16}$ accessing the Humans privacy star.

Fig. 3.

Linear query ${\mathit{Q}}_{15}$ accessing the Humans privacy star.

Fig. 4.

Snowflake query ${\mathit{Q}}_3$ accessing the Humans and Organization privacy schemas.

Table 2

Results of the execution of Wikidata queries using our differential privacy method. Those queries with sensitivity “1.0” are star queries since the sensitivity of a COUNT query over a single star schema is 1 (a COUNT query over a table), and their elastic stability is “x” as described in Section 5.2 if there are joins between star BGPs, the sensitivity increases based on the stability polynomial, calculated according to Theorem 3

Query ID	Actual result	Average private	Average private	Sensitivity	Stability ${\mathit{S}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}{\mathit{Q}}_{\mathit{i}}\mathrm{,}?\mathit{x}\mathrm{)}$
		result using	result using
		Epsilon = 0.1	Epsilon = 1.0
Q1	2,275,177	2,275,176	2,275,176	1.0	1
Q2	1,717,945	1,717,940	1,717,945	1.0	1
Q3	1,274,788	1,189,636	1,270,649	290,415	(x+290,863) * 1
Q4	17,440	17,464	17,319	245	(x+18) * 1
Q5	86	110.8	203.1	245	(x+18) * 1
Q6	1,170,315	3,860,469	1,137,687	400,363	(x+400,981) * 1
Q7	3,018	3019	3,017	1.0	1
Q8	50	57	50	1.0	1
Q9	31	1577	37	241.3	(x+8) * 1
Q10	14,477	14,472	14,477	1.0	1
Q11	2,789	2,792	2,789	1.0	1
Q12	221	1,144	89	1,162.2	(x+1,164) * 1
Q13	6,446,811	6,446,812	6,446,810	1.0	1
Q14	3,615	3,613	3,614	1.0	1
Q15	0	71	8	250.8	(x+33) * 1
Q16	21,683	21,682	21,682	1.0	1
Q17	2,789	2,788	2,788	1.0	1
Q18	25	465	34	248.5	(x+27) * 1
Q19	865	864	865	1.0	1
Q20	7	7,087,181	44,254	1,656,501	(x+6,189) * (x+8) * 1
Q21	3,213	1,739,549	31,357	1,651,883	(x+6) * (x+6,189) * 1
Q22	2,092	377,638,493	1,600,610	408,594,207	(x+7) * (x+1,694,747) * 1
Q23	23,450	23,449	23,449	1.0	1
Q24	2,626	1,071,418	231,278	628,018	(x+628,987) * 1
Q25	29,352	1,593,488	42,317	628,018	(x+628,987) * 1
Q26	29,352	29,350	29,351	1.0	1

6.3. Results

We report the results of our evaluation in Table 2, showing the actual count output by the queries and the average result to these queries with added noise (calculated applying the method described in Section 5). We followed the query schema introduced in Section 5.2, that uses the BGP part of each query to calculate the initial most popular values (mpv). We report the results using two values for ϵ, 0.1 and 1.0. We also report the median error percentage for $\mathit{ϵ}=1.0$ in Fig. 5 between the real counts vs. the counts with added noise segregated by the type of query. To calculate the error we used the following Equation: $$\begin{array}{c}\mathit{median}\mathrm{\left(}{{\displaystyle \frac{\mathrm{(}\mathit{ActualCount}-{\mathit{NoiseResult}}_{\mathit{i}}\mathrm{)}\ast 100}{\mathit{ActualCount}}}}_{\mathit{i}=1\dots 100}\mathrm{\right)}\end{array}$$ We use $\mathit{\delta }={\mathit{n}}^{-\mathit{ϵ}ln\mathit{n}}$ where n is the size of the dataset (i.e. the sum of all the different RDF resources in the schema that the queries access) and $\mathit{\beta }=\mathit{ϵ}\mathrm{/}\mathrm{(}2\times log\mathrm{(}2\mathrm{/}\mathit{\delta }\mathrm{)}\mathrm{)}$ for the β parameter.

(Blue) squares in Fig. 5 represent star queries (typically accessing a single star within the dp-schema), have a very low error (and thus a high utility) compared to the other two types of queries that involved at least one “join” operation across stars.

However, the smaller the result from the COUNT, the larger the error introduced. (Red) triangles represent path queries and thus queries with join operations. Only query ${\mathit{Q}}_9$ is close to the 10% error threshold to be considered a query with enough utility. That query is only two triple patterns that retrieve all data from the Professions and Organizations stars. (Grey) circles represent Snowflake queries, which are queries that join two or more stars in the schema, and also access several properties from each star pattern. Only those queries returning a result greater than 1,000,000 (queries ${\mathit{Q}}_{3\mathrm{,}6}$ ) have a high utility result.

Fig. 5.

This plot shows that star-shaped queries (blue squares) have the greatest utility, since they are likely not to have joins between stars in the schema. It also shows that queries accessing large amounts of data have high utility. Notice that $\mathit{Q}15$ does not appear in the plot since its result is 0.

The sensitivity and stability columns in Table 2 clearly show that the larger the degree in the stability polynomial the greater the query sensitivity, and thus, the higher the error in the result. Note that in most cases the derived queries produce smaller results than the simpler queries, thus the errors are larger. The only queries where this is not the case are queries ${\mathit{Q}}_{1\mathrm{,}2}$ . However, the errors in these queries are so small that much more data should be collected to really establish if they are statistically different. A class of queries with large errors are queries with small outputs and at least one join. See, for example, queries ${\mathit{Q}}_{9\mathrm{,}18\mathrm{,}20}$ . In general, the more joins in the query and the smaller the result size, the worse results. Joins directly affect the stability polynomial, more joins imply larger degree. The effect is exacerbated if the value representing the most popular mapping is large. Large amounts of noise are introduced to results of the three queries associated with polynomials of degree 2, ${\mathit{Q}}_{20\mathrm{,}21\mathrm{,}22}$ , which access data from 3 different stars. Even though the results of the original queries are not small (>2,000), the error introduced is very high. Compare that to the single join query ${\mathit{Q}}_9$ that produces a small result and high errors, but it is much smaller than the errors of ${\mathit{Q}}_{21}$ and ${\mathit{Q}}_{22}$ . Results from queries accessing a single star from the dp-schema are good as expected, since without joins they have low query sensitivity and, hence, small errors.

7. Related work

The study of how to guarantee the privacy of individuals contributing personal data to datasets is a long studied problem. In this work we have focused on how to guarantee this privacy in RDF data graphs accessed through SPARQL queries using differential privacy. The related work can be roughly classified into those that provide some privacy guarantees to accesses to data stored in (social) graphs and those that guarantee privacy over the results returned by SPARQL queries. We briefly look over these works in this section.

7.1. Privacy over SPARQL

There have been several approaches to address privacy concerns related queries to RDF data. A good survey can be found in [32]. There is a basic anonymization protection that a SPARQL engine must provide to queries that directly return individuals, as opposed to aggregated data. Similar to the case of relational databases where attribute values are anonymized using nulls, the work presented in [13] uses blank nodes to hide sensitive data. Delanoux et al. [7] introduce a more general framework with formal soundness guarantees for privacy policies that describe information that should be hidden as well as utility policies that describe information that should be available. The framework checks whether policies are compatible with each other, and based on a set of basic update queries that use blank nodes and deletions of triples, automatically derives from the policies candidate sets of anonymization operations that guarantee to transform any input dataset into a dataset satisfying the required policies. However, their soundness guarantees do not imply any formal privacy guarantees. Two early methods developed for privacy protection when answering queries about classes in a dataset are k-anonymity and l-diversity. In particular, k-anonymity is used in [17,31] to answer queries in RDF datasets. Unfortunately, it is well-known these methods, in contrast to differential privacy, do not provide formal guarantees for privacy.

The only work known to us that directly applies differential privacy to SPARQL queries is [32]. But surprisingly, differential privacy is realized through local sensitivity alone without the use of a smoothing function necessary for correctness [12]. A privacy-preserving query language for RDF streams is introduced in [8]. Limiting queries to that language servers can continuously release privacy-preserving histograms (or distributions) from online streams. Han et al. [15] provide differentially-private variants of the algorithms TransE and RESCAL, aimed at constructing knowledge graph embeddings in the form of real-valued vectors. While the authors show that these encodings allow performing some analyses with a reasonable privacy-utility tradeoff, inlcuding clustering and link prediction, it is an open question whether this generalizes to further analyses or counting queries as addressed in the current article.

7.2. Privacy in social graphs

A central task to the development of any practical differentially private analysis tool is finding appropriate approximations and alternatives to global sensitivity: it should be easy to calculate, and, at the same time, close enough to the real sensitivity to allow the computation of statistically useful results. A well-known approach is to rely on the concept of restricted sensitivity [3]. Restricted sensitivity is tailored to provide privacy guarantees assuming datasets come from a specific subgroup of the universe of all possible datasets, and it was introduced in the context of social-graph data analysis. There are two natural notions from which one can define adjacency of graphs: differences on edges and differences on vertices. The distance between two graphs, ${\mathcal{G}}_1$ and ${\mathcal{G}}_2$ , can be then given by the smallest number of changes (either on edges or vertices) needed to transform ${\mathcal{G}}_1$ and ${\mathcal{G}}_2$ into the same graph, giving rise to two definitions of restricted sensitivity. Blocki et al. [3] provide efficient algorithms to calculate approximations of these sensitivities for a class of social graph queries that involve only one type of join: aggregations over properties of a node and its neighbors (the specific subgroup of interest). Proserpio, Goldberg and McSherry extended the edge-based definition of restricted sensitivity to include weighted datasets [30]. Briefly, the intent was to increase the utility of the answer by considering weights associated with edges during the calculation of noise. Our notion of dp-schema sensitivity can be seen as a vertex-based sensitivity if each induced subgraph ${\mathit{g}}_{\mathit{i}}\in \mathcal{P}\mathrm{(}|\mathcal{G}|\mathrm{)}$ is interpreted as a single node with its attributes. Our proposed elastic sensitivity can be then interpreted as a generalization to handle multiple joins. The polynomial to calculate the selectivity of a query with a single join is always of degree 1. Furthermore, social graphs are essentially defined using a single relationship type. Using our terminology, this implies that the dp-schema would consist of a single star BGP. Hence, Blocki et al. [3] argue that, in practice, the value of x in the degree-1 polynomial (i.e. the frequency of the most popular value) can be bounded by a constant (which would be provided by the RDF data administrator). This is closely akin to our predicate multiplicity. Elastic sensitivity, on the other hand, uses a variable selectivity (the values of x are obtained directly from the dataset), and generalizes to multiple joins. Other works such as [5] proposed differential privacy methods for subgraph counting queries with unrestricted joins (through node differential privacy), however, answering this type of queries is computationally difficult (NP-hard). The result is then more of theoretical interest and limited for general application.

8. Conclusions

In this paper we have introduced a framework to develop differential privacy tools for RDF data repositories. We have used the framework to develop an $\mathrm{(}\mathit{ϵ}\mathrm{,}\mathit{\delta }\mathrm{)}$ -Differential Privacy SPARQL query engine for COUNT queries. A crucial component of our framework is the concept of differential privacy schema or dp-schema. Without it, we would have not been able to develop a differential privacy preserving algorithm to publish data of acceptable quality. The concept is independent of the sensitivity approximation used and we hope that others can build on the concept to get better query answering algorithms. In our algorithm, we adapt the concept of elastic sensitivity of SQL queries from [19] to SPARQL.

We have implemented our algorithm and tested it using the Wikidata RDF database, queries from its log files and other example queries found at the Wikidata endpoint. The simulations show the approach to be effective for queries over large repositories, such as Wikidata, and in many cases for queries within the 10 of thousands answers to aggregate. However, even though elastic sensitivity has been designed to bind the stability of joins, the sensitivity of a query with joins can still be very high. As in the case of SQL queries in relational databases, in order to keep the noise in SPARQL queries under a single percentage digit, query results should have over 1M tuples and $\mathit{ϵ}=1$ . The evaluation shows though that we can safely evaluate star queries.

There are many pending issues to address. We can still apply several optimizations to our framework. For example, public graphs can be treated as public tables. If they participate in joins, we can directly use their most popular result mappings during calculation of the query sensitivity. From the more practical point of view, more operations need to be implemented. We can consider the approaches described in [19] for SQL to add aggregation functions like sum and averages to our framework. There are also issues to consider about the impact that such algorithms will have on SPARQL query engines. From the more formal side, it is still important to keep searching for better approximations of local and global sensitivities as well as alternative definitions that are less onerous than differential privacy. One possibility is to find a way to apply restricted sensitivity to more types of queries by adding more semantic information to a dp-schema. It might also be possible to find a more accurate approximation for the elastic sensitivity of $\mathit{D}\mathit{I}\mathit{S}\mathit{T}\mathit{I}\mathit{N}\mathit{C}\mathit{T}$ queries to make them independent or partially independent of predicate multiplicity. We should point out that most queries that will require privacy protection will be $\mathit{D}\mathit{I}\mathit{S}\mathit{T}\mathit{I}\mathit{N}\mathit{C}\mathit{T}$ (e.g. how many human exists with properties A and B that work in company C?).