Differential privacy and SPARQL

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 D be the set of all possible datasets, and use d(D,D′)=k to denote that D,D′∈D are k-far apart. In particular, two datasets D,D′∈D that are 1-far apart are called neighbors, written D∼D′.

This inequality establishes a quantitative closeness condition between Pr[A(D)∈S] and Pr[A(D′)∈S], the probabilities that on inputs D and D′, the outcome of 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 D′ 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 D1,…,Dn will contain (tagged) data points belonging to D1,…,Dn and the distance between two such datasets D, D′ will reduce to d(D,D′)=∑i=1nd(πi(D),πi(D′)), πi(D) representing the subset of data points from D belonging to Di. In the context of relational databases, the Di’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 f:D→R by simply perturbing its output: On input D, we return f(D) plus some noise sampled from a Laplacian distribution. The noise must be calibrated according to the global sensitivity GSf of f, which measures its maximum variation upon neighbor datasets; formally, GSf=maxD,D′|D∼D′|f(D)−f(D′)|.

Here, Lap(λ) represents a sample from the Laplacian distribution with parameter λ, a symmetric distribution with probability density function pdf(x)=12λe−|x|/λ, mean 0 and variance 2λ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 T:D→D α-globally-stable if d(T(D),T(D′))⩽αd(D,D′) for every D,D′∈D. Transformers with bounded global stability yield bounded global sensitivities: GSf∘T⩽αGSf 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 t1 and t2, by matching a pair of their attributes. A modification in a mere tuple from t1 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.

Observe that LSf(0)(D) coincides with LSf(D). Similar to global stability, a dataset transformer T:D→D, is α-local-stable for a dataset D if d(T(D),T(D′))⩽αd(D,D′) for every D′∈D. And as with global sensitivity, LSf∘T(D)⩽αLSf(D) whenever T is α-local-stable for D.

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

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].

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.

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.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 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 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 G as a differential privacy schema. More formally, its goal is to partition G as a set {g1,…,gn} of sub-graphs, where each gi represents the contribution of an individual, and G=⨄igi 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 gi. In Fig. 1, this means, for example, the data related to Alice and to the Walt Disney company.

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 G of our running example and query “How many phone numbers are currently in use?”. If we evaluate the query over G, the answer is 3. Now assume we consider a neighboring graph G′, 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 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 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 n1,n2⩽α, then |n1−n2|⩽α). 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).

Many predicates (or equivalently, triple patterns) would have a natural multiplicity bound of 1. For instance, a city has a unique area and a unique number of dailyRobberies. Likewise, we can assume that a person 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 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 P and that every graph G is compliant with the dp-scheme P. Furthermore, we assume that the administrator establishes an upper bound κ(tp) for each triple pattern tp in P. Hence, the graph space that we consider for the purposes of differential privacy will be that of graphs that comply with both 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:

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

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

Triple patterns in an RDF graph compliant with a dp-schema P naturally inherit the notion of center from the star they “belong to”. Specifically, for a star S∈P and a triple pattern tp=(s,p,o) such that (X,p,Y) belongs to S, for some variables X, Y, we let center(tp,P)=s if X is the center of S; otherwise center(tp,P)=o. For instance, in the above example we have

Finally, a user query is a CBGP B¯ wrapped by either of the two following aggregation operations:

4.2.Evaluation decomposition

Continuing with the previous example, assume we want to evaluate B (from Example 4.1) over G (from Fig. 1), that is, to compute [[B]]G (observe that if we are interested in obtaining [[⟨B,F⟩]]G instead, we simply add a FILTER operation on top of the evaluation of [[B]]G). We can do this in a compositional fashion, leveraging the partition that dp-schema induces on G. Concretely, we can split B as

Hence, for any query B¯=⟨B,F⟩, we can formally define a split B÷P of B from a dp-schema P, as follows: B÷P={B1,…,Bn} iff the following two conditions hold

Example 4.3.

For the CBGP from Example 4.1, B is split into four elementary BGPs by dp-schema , i.e. B÷P={B1,B2,B3,B4} as defined in Equation (1) above. Note that B1 and B2 have both the same covering star , but they are consireded different elementary BGPs because they share predicate employs. The covering stars of B3 and B4 are and , respectively.

If B were extended, e.g. , with triple pattern

tp=(SkullandBones,member,?p1),

the splitting B÷P would contain a fifth, member B5={tp}. In this case, B3 and B5 share the same covering star, , but remain different members of B÷P because their triple patterns have different centers (?p2 is the center of triple patterns in B3 and ?p1 the center of the triple pattern in B5). Alternatively, if B were extended, e.g., with triple pattern

tp′=(?x,headquarter,Burbank),

the number of elementary BGPs does not change but B1 and B2 should be both augmented with tp′ due to the maximality condition of each Bi. (In this case, B1 and B2 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 B÷P={B1,…,Bn} resides in that it lets us isolate the fragment of the graph necessary to answer each Bi. Assume we denote by GSi the subgraph induced by star Si, i.e. GSi=⋃g∈Si(|G|)g.

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

We have already observed that B¯ is such that [[B]]G can be evaluated using only equi-joins. Therefore, there must exist an ordering of the elements in B÷P such that [[Bi]]GSi⋈[[Bi+1]]GSi+1 can also be done with equi-joins. In other words, an ordering where |var(Bi)∩var(Bi+1)|=1 for all 1⩽i<n. We call this order a normal ordering of B÷P, and without loss of generality denote by ?xi the variable in the equi-join [[Bi]]GSi⋈[[Bi+1]]GSi+1. For convenience, in the remainder we assume that the indexing used for B÷P follows a normal order. Note that this is already the case for the splitting from Example 4.3 (B1 and B2 share variable p2, and B2 and B3 share variable c).

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

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 G that complies with a dp-schema P={Bi}i∈I, we define the size of G w.r.t. P as size(G)P=∑i∈I|Bi(|G|)|.

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 G1, G2 that comply with a dp-schema P={Bi}i∈I and such that size(G1)P=size(G2)P, their distance is defined as the size of their difference, i.e. d(G1,G2)P=size(G1∖G2)P. Note that in the general case where the sizes of G1 and G2 need not coincide, their distance is defined as the size of the their symmetrical difference (G1∖G2)∪(G2∖G1), 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) LSQ(G) (LSQ(k)(G)) of SPARQL query Q over RDF graph 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 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 G that complies with a dp-schema P, to compute an upper bound of the local sensitivity LSQ(k)(G) (denoted by UQ(k)(G) in Lemma 1).

To this end, observe that the naive approach of evaluating the query on every neighbor (at distance k) of 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 SPARQL. Intuitively, our notion of elastic sensitivity of a SPARQL query Q at distance k of a concrete graph G (that complies with the dp-schema P) regards the evaluation of Q as the composition of successive transformations applied to 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 G that complies with a dp-schema P, bounds the local stability for any graph G′ that also complies with P and is at distance k of G. Hence, it bounds the local sensitivity at distance k of COUNT?x(B¯) (for any B¯=⟨B,F⟩) over G′.

The formal definition of elastic stability relies on the frequency of most popular values. More precisely, if ?x is a variable occurring in an elementary BGP B, we use mpv(?x,B,G) to denote the frequency of the most popular value to which ?x is mapped to, when evaluating B over G. We can use SPARQL itself to determine mpv(?x,B,G) through the query

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 mpv(?x,B,G). Nevertheless, the benefit is that since the second query is merely a variable renaming of a tp′∈S, the values can be pre-computed for all tp′∈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 G, written SB(k)(G), we start by applying Lemma 3 to decompose B as a sequence of elementary BGPs. Once we fix a normal ordering, we have B÷P=B1⋈(B2⋈(…⋈Bn)…). This decomposition allows estimating the frequency of most popular values of graphs k far apart from G. Formally, the frequency of the most popular values for variable ?x in a BGP B for graphs at distance k of G, written mpv(k)(?x,B,G), is defined by induction on the length |B÷P| as follows:

Base case: If |B÷P|=1, we let

Inductive case: If |B÷P|>1, we let

The intuition behind the base case is easy to grasp. For k=1, we take a subgraph from P(|G|), 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 ?x is κ(S). 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 k×κ(S). For the inductive case, we need to worry about the most frequent mapping value of ?x1 in B÷P∖{B1} since for every mapping of ?x obtained from B1, if this mapping maps ?x1 in B1 to the same value of the most frequent value of x1 in B÷P∖{B1}, the value of ?x will be repeated as many times in the combined mapping of B. Hence, the most frequent value of ?x in [[B1]]S1 can be duplicated, in the worst case, as many as mpv(k)(?x1,B÷P∖{B1},G) times in the multiset of solution mappings [[B]]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 G, denoted by SB(k)(G). The definition also proceeds by induction on the cardinality of a fixed normal ordering of B÷P=B1⋈(B2⋈(…⋈Bn)…):

Base case: If |B÷P|=1, we let

Inductive case: If |B÷P|>1, let B′=B÷P∖{B1}. We have two cases. If the covering star S of B1 is not the covering star of any other Bj∈B′, we let

If the covering star S of B1 is also the covering star of another Bj∈B′, we let

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

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 Gi, that must be covered by a single star pattern S in 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 κ(S). 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 B={(?v0,p,?u),(?u,p′,?v1)}, and the triple (s,p,o) is part of G1 and o happens to be the most popular result mapping for (?u,p′,?v1), then there will be at most mpv(1)(?u,(?u,p′,?v1),G) new mappings in the result.

Now we have all the prerequisite to define the elastic sensitivity of user queries (at fixed distances of a given graph):

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 readily establishes our main result, which allows applying differential privacy to SPARQL queries over RDF graphs:

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

6.1.Privacy schema

Our dp-schema is defined based on three pairwise disjoint stars, P1, P2, and P3, 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, P1, P2, and P3. 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 S1 and S3 share a property, P106. Nevertheless, the sets of instances of the property in the sub-graphs induced by S1 and S3 are disjoint because instances of ?c1 (human UIRs) and ?c2 (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 S1 and P106 Occupation in S3, keep S3 as it is, and rename them P1, P2, and P3 respectively.1010

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).

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 ?x0, 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 Q3 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 Q16 accessing the Humans privacy star.

Fig. 3.

Linear query Q15 accessing the Humans privacy star.

Fig. 4.

Snowflake query Q3 accessing the Humans and Organization privacy schemas.

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 ϵ=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:

(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 Q9 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 Q3,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 Q15 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 Q1,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 Q9,18,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, Q20,21,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 Q9 that produces a small result and high errors, but it is much smaller than the errors of Q21 and Q22. 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.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, G1 and G2, can be then given by the smallest number of changes (either on edges or vertices) needed to transform G1 and G2 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 gi∈P(|G|) 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.