Loose associations to increase utility in data publishing 1

4.1. k-Looseness

We start by identifying the constraints that are potentially exposed by the release of group associations involving a set T of fragments, as follows.

Intuitively, the constraints relevant for a set of fragments are all those constraints covered by the fragments (i.e., all confidentiality constraints that are a subset of the union of the fragments). For instance, the only constraint among those reported in Fig. 1(b) that is relevant for the set of fragments in Fig. 1(c) is c 1 ; all constraints are instead relevant for the set of fragments in Fig. 3.

OPEN IN VIEWER

Fig. 4.

Graphical representation (a) and corresponding relations (b) of a 4-loose association among three fragments F l , F m and F r of relation Patients in Fig. 1(a).

The definition of a group association over different fragments is a natural extension of the case with two fragments, where the association is induced by groupings enforced within the different fragments. The consideration of the universal group association implies that only one grouping is applied within each fragment. Hence, given a fragmentation F = { F 1 , … , F n } , a ( k 1 , … , k n ) -grouping is a set { G 1 , … , G n } of grouping functions defined over fragments { f 1 , … , f n } (i.e., a set of k i -groupings over f i , i = 1 , … , n ). Figure 4 illustrates a ( 2 , 2 , 2 ) -grouping over fragments F l = { Name , YoB } , F m = { Edu , ZIP } and F r = { Job , MarStatus , Disease } of relation Patients in Fig. 1(a), and the induced group association A lmr .

Like for the case of two fragments, a group association permits to establish relationships among the tuples in the different fragments, while maintaining the uncertainty on which tuple in each fragment is actually associated with each tuple in another fragment. Such an uncertainty is given by the cardinality of the groups. The reconstruction made available by a group association, and obtained as the joins of the fragments in F and A, generates in fact all possible combinations among the tuples of associated groups. Let us denote with F ⋈ A such a join. Guaranteeing k-looseness for the sensitive associations represented by relevant constraints requires ensuring that the reconstruction of tuples, made possible by the association among groups, is such that: for each constraint c relevant for F and for each fragment F, there are at least k tuples t 1 a , … , t k a in F ⋈ A such that, if t 1 a [ F ∩ c ] = ⋯ = t k a [ F ∩ c ] , then t 1 a [ c ∖ F ] ≠ ⋯ ≠ t k a [ c ∖ F ] . The k-looseness requirement must then take into consideration not only the number of tuples in other fragments with which a tuple can be associated but also the diversity of their values for the attributes involved in confidentiality constraints. In fact, different tuples that have the same values for these attributes do not provide the diversity needed to ensure k-looseness. We then start by identifying these tuples as follows.

According to this definition, given a fragmentation F , two tuples in a fragment instance f i of fragment F i ∈ F are alike if they have the same values for the attributes in at least one constraint relevant for F . For instance, with reference to the fragments in Fig. 4, r 4 ≃ c 3 r 8 as r 4 [ Disease ] = r 8 [ Disease ] = Asthma . Since we are interested in evaluating the alike relationship with respect to the set C F of relevant constraints, in the following we omit the subscript of the alike relationship whenever clear from the context (i.e., we write t i ≃ t j instead of t i ≃ C F t j ).

Based on the definition of relevant constraints and alike relationship, we can now define k-looseness of a group association. Intuitively, a group association A is k-loose if, for each relevant constraint c ∈ C F , each tuple t a in A represents at least k associations among sub-tuples in fragments including attributes in c, and these associations correspond to at least k different combinations of values of the attributes in c. In other words, t a represents k tuples that may belong to the original relation and that are not alike with respect to c. Formally, k-looseness is defined as follows.

As an example, consider the group association in Fig. 4 and confidentiality constraint c 5 = { YoB , ZIP , MarStatus } in Fig. 1. The first tuple in A lmr represents 8 possible associations among sub-tuples in F l , F r and F m (i.e., any possible combination of tuples from sets { l 1 , l 2 } , { m 1 , m 3 } and { r 1 , r 4 } ). These associations correspond to the following 8 possible combinations of values of attributes YoB, ZIP and MarStatus that may belong to the original relation: ⟨1974, 90015, Married⟩, ⟨1974, 90015, Divorced⟩, ⟨1974, 90001, Married⟩, ⟨1974, 90001, Divorced⟩, ⟨1965, 90015, Married⟩, ⟨1965, 90015, Divorced⟩, ⟨1965, 90001, Married⟩, ⟨1965, 90001, Divorced⟩.

k-looseness guarantees that none of the sensitive associations represented by relevant constraints can be reconstructed with confidence higher than 1 / k . Figure 4 illustrates a fragmentation of the relation in Fig. 1(a) and a group association A lmr that guarantees 4-looseness for the sensitive associations expressed by the confidentiality constraints in Fig. 1(b).

Clearly, there is a correspondence between the size of the groupings and the k-looseness of the association induced by them. Trivially, a ( k 1 , … , k n ) -grouping cannot provide k-looseness for a k > ∏ i = 1 n k i . Consider a constraint c, which includes attributes in F i and F j only. The ( k 1 , … , k n ) -grouping can provide uncertainty over the associations existing among the attributes in c for a k ⩽ k i · k j . Indeed, any tuple in f i is associated with at least k i · k j tuples in f j , which have different values for the attributes in c if groups are properly defined. With reference to the group association in Fig. 4, the sensitive association represented by constraint c 1 = { YoB , Edu } enjoys a k-looseness of four: each value of YoB can be indistinguishably associated with at least four possible values of Edu and vice versa. A constraint c involving more than two fragments may enjoy higher protection from the same ( k 1 , … , k n ) -grouping. Considering the example in Fig. 4, the sensitive association expressed by constraint c 5 = { YoB , ZIP , MarStatus } enjoys a k-looseness of eight: for each value of YoB there are at least eight possible different pairs of ( ZIP , MarStatus ); for each value of ZIP there are at least eight possible different pairs of ( YoB , MarStatus ); and for each value of MarStatus there are at least eight possible different pairs of ( YoB , ZIP ). For instance, value 1965 for attribute YoB can be associated with ⟨90015, Married⟩, ⟨90015, Divorced⟩, ⟨90001, Divorced⟩, ⟨90001, Married⟩, ⟨90038, Widow⟩, ⟨90038, Single⟩, ⟨90025, Widow⟩, ⟨90025, Single⟩. Since we consider minimal fragmentations, for each pair of fragments F i , F j in F there exists at least a confidentiality constraint c relevant for F i and F j only (i.e., ∀ { F i , F j } ∈ F , i ≠ j , ∃ c ∈ C s.t. c ⊆ F i ∪ F j , Theorem A.2 in [14]), which enjoys a k-looseness of k i · k j . Hence, a ( k 1 , … , k n ) -grouping can ensure k-looseness with k ⩽ min { k i · k j : i , j = 1 , … , n , i ≠ j } for the constraints in C F . Whether the ( k 1 , … , k n ) -grouping provides k-looseness for lower values of k depends on how the groups are defined. In the following, we introduce three heterogeneity properties of grouping (revising and extending those provided in [14]) whose satisfaction ensures k-looseness for k = min { k i · k j : i , j = 1 , … , n , i ≠ j } .

4.2. Heterogeneity properties

The heterogeneity properties ensure diversity of the induced associations, which are defined as sensitive by confidentiality constraints. They operate at three different levels: groupings, group associations, and value associations.

The first property we introduce is group heterogeneity, which ensures diversity within each group by imposing that groups in a fragment do not include tuples with the same values for the attributes in relevant constraints. In this way, the minimum size k i of the groups in fragment F i , i = 1 , … , n , reflects the minimum number of different values in the group for each subset of attributes that appear together in a relevant constraint.

This property is a straightforward extension of the one operating on two fragments, as its enforcement is local to each individual fragment to take into account all constraints relevant for F (not only those relevant for a pair). For instance, in Fig. 4 the grouping functions of the three fragments satisfy group heterogeneity for C F = { c 1 , … , c 5 } while the grouping function of fragment F r in Fig. 5(a) violates it with respect to confidentiality constraint c 4 = { YoB , ZIP , Disease } . In fact, fragment instance f r includes a group with tuples assuming the same value for attribute c 4 ∩ F r = Disease (i.e., Diabetes).

OPEN IN VIEWER

Fig. 5.

Examples of violations of heterogeneity properties with respect to constraint c 4 = { YoB , ZIP , Disease } .

The second property we introduce is association heterogeneity, which imposes diversity in the group association. For a group association A between two fragments, this property requires that A does not include duplicate tuples, that is, at most one association can exist between each pair of groups of the two fragments. By considering the more general case of a group association among an arbitrary number of fragments, this property requires that, for each constraint c in C F , each group in a fragment f i such that F i ∩ c ≠ ∅ appears in at least k tuples in A that differ at least in the group of one of the fragments f j storing attributes in c (i.e., c ∩ F j ≠ ∅ ). In other words, the association heterogeneity property implies that A cannot have two tuples with the same group identifier for all attributes G i j , j = 1 , … , l corresponding to fragments storing attributes that appear in a constraint. Since we consider minimal fragmentations, there exists at least one relevant constraint for each pair of fragments in F . Therefore, a group association A satisfies the association heterogeneity property if it does not have two tuples with the same group identifier for any pair of group attributes G i , G j , i , j = 1 , … , n , and i ≠ j .

Figure 4 illustrates a group association that satisfies the association heterogeneity property, while the group association in Fig. 5(b) violates it since a group of fragment f l is associated twice with a group in fragment f r .

The third property we introduce is deep heterogeneity, which captures the need of guaranteeing diversity in the associations of values behind the groups. Considering a pair of fragments f i and f j , deep heterogeneity requires that a group in f i be associated with groups in f j that do not include duplicated values for the attributes in a constraint c ⊆ F i ∪ F j (i.e., tuples are not alike with respect to c). In fact, if the groups in f j with which a group in f i is associated contain alike tuples with respect to c, the k i · k j corresponding tuples do not contain k i · k j different values for the attributes in c, meaning that the group association offers less protection than expected. For instance, groups jmd1 and jmd3 in Fig. 4 have the same values for attribute Disease (i.e., Flu and Asthma). Therefore, a group in f l cannot be associated with both jmd1 and jmd3 because of constraint c 3 = { Name , Disease } (otherwise, the association between F l and F r would be 2-loose instead of 4-loose). Considering the more general case of a group association among an arbitrary number of fragments, and a constraint c composed of attributes stored in fragments { F 1 , … , F n } , deep heterogeneity requires a group f i ( i = 1 , … , n ) be associated with groups in { f 1 , … , f n } ∖ { f i } that do not permit to reconstruct (via the loose join F ⋈ A ) possible semi-tuples that have the same values for all the attributes in c. Note that deep heterogeneity does not require diversity over all the fragments storing the attributes composing a constraint, since this condition would be more restrictive than necessary to guarantee k-looseness. In fact, it is sufficient, for each tuple in a fragment f i , to break the association with one of the fragments f j ( j = 1 , … , n , i ≠ j ) storing the attributes in c. For instance, with reference to the example in Fig. 4, it is sufficient that each group in f l be associated with groups of non-alike tuples in either f m or f r to guarantee a 4-looseness for the sensitive association modeled by c 4 . The deep heterogeneity property is formally defined as follows.

Given a constraint c whose attributes appear in fragments { F i 1 , … , F i j } , deep heterogeneity is satisfied with respect to c if no two tuples t, t ′ in A that have the same group g y in f i y are associated with groups that include alike tuples with respect to c for all the fragments f i x , x = 1 , … , j and x ≠ y . This property must be true for all the groups in each fragment. This guarantees that, for each constraint, no sensitive association can be reconstructed with confidence higher than 1 / k . An example of group association that satisfies deep heterogeneity is illustrated in Fig. 4. Note that deep heterogeneity is satisfied even though the two tuples in group ny2 for f l are associated with groups jmd1 and jmd2 in f r , which include tuples r 1 ≃ c 5 r 3 and r 4 ≃ c 5 r 7 . In fact, constraint c 5 is not covered by F l and F r but by the three fragments all together, and heterogeneity of the associations in which r 1 and r 3 ( r 4 and r 7 , respectively) are involved is provided by the tuples in f m . Figure 5(c) illustrates an example of violation of the deep heterogeneity property with respect to confidentiality constraint c 4 = { YoB , ZIP , Disease } . In fact, the groups in the instances f m and f r with which a group in f l is associated include tuples that are alike with respect to confidentiality constraint c 4 (i.e., two tuples in f m have the same value for attribute ZIP and two tuples in f r have the same value for attribute Disease), clearly reducing the protection offered by the association. In fact, the tuples that can be reconstructed by joining these two groups in f m and f r include occurrences of the same values for the attributes in c 4 (i.e., ZIP = 90025 and Disease = Asthma ). Hence, the association YoB = 1972 , ZIP = 90025 and Disease = Asthma holds with probability higher than 1 / k .

If the three properties above are satisfied by a ( k 1 , … , k n ) -grouping and its induced group association, then the group association is k-loose for any k ⩽ min { k i · k j : i , j = 1 , … , n , i ≠ j } , as stated by the following theorem.

Theorem 4.7.

Given a fragmentation F = { F 1 , … , F n } with its instance { f 1 , … , f n } , the set C F of constraints relevant for F , and a ( k 1 , … , k n ) -grouping that satisfies Properties 4.4–4.6, the group association A induced by the ( k 1 , … , k n ) -grouping is k-loose with respect to C F (Definition 4.3) for each k ⩽ min { k i · k j : i , j = 1 , … , n , i ≠ j } .

Proof.

(Sketch). To assess the protection offered by the release of a ( k 1 , … , k n ) -grouping that satisfies Properties 4.4–4.6, we first analyze the protection provided to the sensitive association represented by an arbitrary confidentiality constraint c in C F .

By Definition 2.2, each group g a ∈ GID i contains at least k i tuples, ∀ F i ∈ F . Each group g a ∈ GID i appears in at least k i tuples in A, each associating g a to a different group g b in GID j , for each fragment F j in F by Property 4.5. Hence, each g a ∈ GID i is associated with at least k i different groups in GID j , ∀ F j ∈ F : F j ∩ c ≠ ∅ , i ≠ j . Each tuple t a in A having t a [ G i ] = g a has at least ∏ j k j (with F j ∈ F : F j ∩ c ≠ ∅ , i ≠ j ) occurrences in the join F ⋈ A . Let us denote with groups_a i the tuples in F ⋈ A of the occurrences of a tuple t i a in A. Tuples in groups_a i are not alike with respect to c. In fact, by Properties 4.4, each group in GID j is composed of at least k j tuples that are not alike with respect to c, ∀ F j ∈ F such that F j ∩ c ≠ ∅ . By Property 4.6, for each pair of tuples t x a , t y a in A with t x a [ G i ] = t y a [ G i ] = g a , the tuples in groups _ a x ∪ groups _ a y are not alike with respect to c. Hence, F ⋈ A has at least k i · ∏ k j tuples, all with t a [ G i ] = g a , that are note alike with respect to c.

Then, a ( k 1 , … , k n ) -grouping satisfying Properties 4.4–4.6 induces a group association that is k-loose with respect to c for each k ⩽ ∏ k i , ∀ F j ∈ F such that F j ∩ c ≠ ∅ .

Since we consider minimal fragmentations only, for each pair of fragments F i , F j in F there exists at least a confidentiality constraint c that is relevant for F i and F j only. Hence, the ( k 1 , … , k n ) -grouping satisfying Properties 4.4–4.6 induces a group association that is k-loose with k = k i · k j between F i and F j (i.e., it guarantees a protection degree k i · k j to the constraints relevant for F i and F j ).

We can then conclude that the ( k 1 , … , k n ) -grouping satisfying Properties 4.4–4.6 induces a group association that is k-loose with respect to C F for each k ⩽ min { k i · k j : i , j = 1 , … , n , i ≠ j } . □

We note that the protection degree offered by a ( k 1 , … , k n ) -grouping that satisfies Properties 4.4–4.6 may be different (but not less than k) for each confidentiality constraint c in C F . Indeed, the protection degree for a constraint c is min { k i · k j : F i , F j ∈ F and F i ∩ c ≠ ∅ and F j ∩ c ≠ ∅ } .

4.3. Some observations on k-looseness

The consideration of all the constraints relevant for the fragments involved in a group association guarantees that no sensitive association can be reconstructed with a probability greater than 1 / k . For instance, confidentiality constraint c 3 = { Name , Disease } is properly protected, for a looseness of 4, by the group association in Fig. 4 while, as already illustrated in Section 3, the two group associations in Fig. 3 grant only a 2-looseness protection to it.

Given a k-loose association A among a set F of fragments, the release of this loose association is equivalent to the release of 2 n − n , with n = | F | , k-loose associations (one for each subset of fragments in F ). Indeed, the projection over a subset of attributes in A represents a k-loose association for the fragments corresponding to the projected group of attributes. This is formally captured by the following observation.

Observation 1.

Given a fragmentation F = { F 1 , … , F n } , a subset { F i , … , F j } of F , and a k-loose association A ( G 1 , … , G n ) over F , group association A ′ ( G i , … , G j ) is a k-loose association over { F i , … , F j } .

For instance, with respect to the 4-loose association in Fig. 4, the projection of A over attributes G l and G m is a 4-loose association between F l and F m .

Since a k-loose association defined over a set F of fragments guarantees that sensitive associations represented by constraints in C F be properly protected, the release of multiple loose associations among arbitrary (and possibly overlapping) subsets of fragments in F provides the data owner with the same protection guarantee. The data owner can therefore decide to release either one loose association A encompassing all the associations among the fragments in F , or a subset of loose associations defined among arbitrary subsets of fragments in F by projecting the corresponding attributes from A. This is formally captured by the following observation.

Observation 2.

Given a fragmentation F = { F 1 , … , F n } and a k-loose association A ( G 1 , … , G n ) over it, the release of an arbitrary set of k-loose associations { A 1 ( G h , … , G i ) , … , A m ( G j , … , G k ) } , with { G h , … , G k } ⊆ { G 1 , … , G n } , provides at least the same protection guarantees as the release of A.

For instance, the data owner can decide to release the group associations obtained projecting ⟨ G l , G m ⟩ and ⟨ G m , G r ⟩ from the group association in Fig. 4. This solution does not suffer from the privacy breach illustrated in Section 3, while providing associations between groups of the same size (i.e., the same utility for data recipients).

According to the two observations above, the data owner can release more than one group association among arbitrary subsets of fragments in F without causing privacy breaches. Note however that if the group associations of interest operate on disjoint subsets of fragments (i.e., no fragment is involved in more than one group association), they can be defined independently from each other without risks of unintended disclosure of sensitive associations. This is formally captured by the following observation. Observation 3.

Given a fragmentation F , and a set { F 1 , … , F n } of subsets of fragments in F , the release of n loose associations A i , i = 1 , … , n does not expose any sensitive association if F i ∩ F j = ∅ , i , j = 1 , … , n , i ≠ j .

5. Queries and data utility with loose associations

The reason for publishing group associations among fragments, representing vertical views over the original data, is to provide some (not precise) information on the associations among the tuples in the fragments while ensuring not to expose the sensitive associations defined among their attributes (for which the degree of uncertainty k should be maintained). Group associations then increase the utility of the data released for queries involving different fragments. However, given a set of fragments, different group associations might be defined satisfying a given degree k of looseness to be provided. There are two different issues that have to be properly addressed in the construction of group associations: one is how to select the size k i of the grouping of each fragment f i such that the product of any two k i is equal to or greater than k; and one is how to group tuples within the fragments so to maximize utility.

With respect to the first issue of sizing the groups, there are different possible values of the different k i that can satisfy the degree k of protection. For instance, for a group association between two fragments, we can use ( k , 1 ) , ( ⌈ k ⌉ , ⌊ k ⌋ ) , and ( 1 , k ) . In the case of multiple fragments, the best utility can be achieved by distributing as much evenly as possible the sizing of the groups, hence imposing on each group a size close to k . An uneven distribution would in fact result in an over-protection of the group associations over some of the fragments (a value of looseness much higher than the required k for constraints covered by a subset of the fragments in F ). Experiments show that this would lead to a significant reduction in the precision of the queries (see Section 7). For instance, a looseness of 12 over three fragments could be achieved with a ( 3 , 4 , 4 ) -grouping; a solution creating a ( 1 , 12 , 12 ) -grouping would indeed provide the required protection overall but would probably provide little utility for the association between the second and third fragments (whose association would in fact be 144-loose for the constraints that are relevant for the second and third fragment only).

OPEN IN VIEWER

Fig. 6.

An example of group association between two fragments F m and F r of relation Patients in Fig. 1(a) where tuples are grouped taking into account the similarity of the values of attributes Race and Salary.

With respect to the issue of grouping within a fragment, we first note that queries that involve a single fragment (i.e., all the attributes in the query belong to the same fragment) are not affected by fragmentation as they can be answered exactly by querying the fragment. For instance, with respect to the fragments in Fig. 6, query q = “select avg(Salary) from Patients group byJob” involves attributes that belong to fragment F r only. Hence, the execution of the query over fragment F r returns exactly the same result as its execution over the original relation Patients in Fig. 1(a). On the following, we focus our discussion on queries that involve two or more fragments, on which a group association is to be defined, with the goal of determining how to group the tuples in fragments so that the induced group associations maximize query utility. In particular, we consider aggregate queries of the form “selectAtt, AGG i ( a i ) , … , AGG j ( a j ) fromSgroup byAtt”, where AGG i , … , AGG j are aggregation functions (e.g., count, avg, min, max functions), and a i , … , a j as well as set Att (this latter optional in the select clause) are attributes that appear in fragments. For instance, with reference to Fig. 6, query q = “select avg(Salary) from Patients group byRace” aims at computing the average salary grouped by the race of patients. We measure utility of a group association as the average improvement over the accuracy of the results (i.e., with less error) with respect to the results obtained in absence of the group association. Intuitively, utility is obtained as 1 minus the ratio of the average difference with respect to the real values in presence of group associations, and the average difference with respect to the real values in absence of group associations.

The execution of queries over group associations brings in, together with the real tuples on which the query should be executed, all the tuples together with them in their groups and the uncertainty – by definition – of which sub-tuples in a fragment are associated with which sub-tuples in other fragments. Our observation is therefore that groups within fragments should be formed so to contain as much as possible tuples that are similar for the attributes involved in the queries (have close values for continuous attributes). The intuition behind this is that, although the query is evaluated on a possibly larger number of tuples included in the returned groups, such tuples – assuming similar values – maintain the query result within a reasonable error, thus providing utility of the response. The more the attributes involved in the query on which such an observation has been taken into account in the grouping, the better the utility provided by the group association for the query. In fact, similarity of values within groups (even when ensuring diversity of the values) might provide limited uncertainty of values within a group. We therefore expect that not all the attributes involved in confidentiality constraints should be taken into account in this process.

Let us see now an example of queries over our fragmentation involving attributes such that none, some, or all of them have been subject to the observation above in the grouping (i.e., groups include similar values for none of, some of, or all the attributes in the query). Consider the fragments and group association in Fig. 6, computed over relation Patients in Fig. 1(a), where the group association has been produced grouping tuples with similar Race values for fragment f m and similar Salary values for fragment f r . We can then see the following three different cases.

A query q n s involves none of the attributes whose similarity has been considered in the grouping. An example of such a query on the group association in Fig. 6 is q n s = “selectEdu, avg(InsAmount) from Patients group byEdu”, requiring the average insurance amount for the different education levels recorded. In this case, the utility of the association typically remains limited. We note however that the utility for this kind of queries has always been positive in our experimental analysis, reaching values close to 40% for some queries.

A query q a s involves also (but not only) attributes whose similarity has been considered in the grouping. An example of such a query on the group association in Fig. 6 is q a s = “selectInsCompany, avg(Salary) from Patients group byInsCompany,” requiring, for each insurance company, the average salary of insurance holders. Enjoying the fact that the additional tuples involved in the computation will typically have salary close to the values of real tuples, this query provides quite appreciable utility with respect to the real result. As we will discuss in Section 7, utility for queries of this type has typically shown values close to 80% in our experimental evaluation.

A query q o s involves only attributes whose similarity has been considered in the grouping. An example of such a query on the group association in Fig. 6 is q o s = “selectRace, avg(Salary) from Patients group byRace” requiring the average salary of patients grouped by race. This query can benefit from the fact that similarity has been considered for both the attributes involved, which ensures that the additional tuples, brought-in in the evaluation because of the looseness of the association, have values for the involved attributes close to the ones on which the computation would have been executed if the query was performed on the original relation. As we will discuss in Section 7, the utility for this kind of queries is very high, and has typically shown values near 100% in our experimental evaluation.

Figure 7 shows the results of the queries above when executed over the group association in Fig. 6 or over the original relation in Fig. 1(a).

OPEN IN VIEWER

Fig. 7.

Results of sample queries on a group association (a), on the original relation (b), and on fragments without group association (c) for queries involving none ( q n s ), some ( q a s ), or all ( q o s ) of the attributes that have been considered for similarity in the grouping.

OPEN IN VIEWER

Fig. 8.

Heuristic algorithm that computes a k-loose association.

Figure 8 illustrates our heuristic algorithm that computes a k-loose association aiming at providing greater utility in query evaluation. The algorithm takes as input a relation s defined over relation schema S ( a 1 , … , a m ) , a fragmentation F = { F 1 , … , F n } and its instance { f 1 , … , f n } , a set C F of confidentiality constraints relevant for F , privacy parameters k 1 , … , k n , and a set A of attributes often involved in the expected queries. The algorithm returns a k-loose association (with k = min { k i · k j : i , j = 1 , … , n , i ≠ j } ), and the corresponding grouping functions G 1 , … , G n . Intuitively, the algorithm first identifies an optimal group for each tuple – without considering heterogeneity properties – in such a way that each group in a fragment contains tuples with similar values for attributes in A . Our solution to identify such an optimal grouping is based on the observation that similarity can be conveniently translated into an ordering of values within the attribute domains. Maximum similarity can in fact be guaranteed by keeping in the same groups elements that are contiguous in the ordered sequence of attribute values. The algorithm first orders tuples in the fragment instances based on their values for attributes in A , and then partitions the tuples in groups of size k. In this way, each optimal group will contain k tuples that, thanks to the ordering, have similar values for attributes in A . Clearly, different ordering criteria can be applied to different attributes, to properly model the similarity requirement. As an example, for numerical values, we adopt the traditional ⩾ order relationship. The groupings obtained by ordering the tuples according to A are optimal with respect to similarity (and hence utility of query responses), but they do not provide any guarantee with respect to the confidentiality of sensitive associations. Optimal groupings are then used by the algorithm to drive the real allocation of tuples to groups: for each fragment, the algorithm tries to assign the tuples to the group closest to the optimal group so that also the heterogeneity properties are satisfied. In the assignment of tuples to groups, the algorithm follows two main criteria: (i) it favors groups close to the optimal group of each tuple; and (ii) it prefers groups of size k i over larger groups. Our heuristic algorithm implementing this approach is presented in details in the remainder of this section.

The algorithm starts by initializing variable To _ Place , representing the set of tuples that still need to be allocated to groups, to the tuples in s, and by creating an empty group association A (lines 1–2). The algorithm then operates in four steps as follows.

Step 1: Ordered grouping.  For each fragment F i , the algorithm identifies the optimal grouping, allocating tuples with similar values for the attributes in A ∩ F i to the same group(s). To this purpose, the algorithm orders the tuples in s according to the attributes in A ∩ F i (line 5). It then partitions the ordered tuples in sets of k i contiguous tuples each, and assigns to each partition a different group identifier g current i (lines 6–13). In this way, contiguous tuples in the ordered relation are ideally assigned to the same group (or to contiguous groups). The result of this step is a matrix OptimalGrouping with one row for each tuple t in s, one column for each fragment F in F , and where each cell OptimalGrouping [ t ] [ F i ] contains the identifier of the optimal group for tuple t in fragment F i .

Step 2: Under-quota grouping.  The algorithm tries to assign each tuple to the group closest to the optimal one that satisfies all the heterogeneity properties, but without generating over-quota groups (i.e., groups in F i with more than k i tuples) to maximize utility. In fact, large groups limit the utility that can be obtained in query evaluation. For each tuple t in To _ Place , the algorithm calls function Find_Assignment in Fig. 9 (lines 15–16), which allocates tuples to groups according to the heterogeneity properties.

OPEN IN VIEWER

Fig. 9.

Pseudocode of functions Find_Assignment, Try_Assignment and Re_Assign.

Function Find_Assignment receives as input a tuple t, the candidate tuple assoc _ tuple that represents t in the group association A (which is null when t has not been assigned to any group), a fragment identifier i, a Boolean variable over _ quota (which is true only if over-quota groups are permitted), and the array OptimalGrouping computed in Step 1. This function then tries to assign t to a group in F i close to the optimal one. Function Find_Assignment first checks whether t can be inserted into OptimalGrouping [ t ] [ F i ] , that is, it checks whether the heterogeneity properties are satisfied. If the heterogeneity properties are not satisfied, the function checks the groups of fragment F i , denoted g candidate i , in increasing order of distance from OptimalGrouping [ t ] [ F i ] (lines 3–13). In fact, similar values are ideally assigned by Step 1 to groups close to the optimal one. The satisfaction of the heterogeneity properties is verified by calling function Try_Assignment in Fig. 9 (line 9 and line 13). Function Try_Assignment takes as input tuple t, the candidate tuple assoc _ tuple that represents t in the group association A, the fragment identifier i, and a group identifier g, and returns true if t [ F i ] can be assigned to g; false, otherwise. When a correct assignment of t to a group in F i is found, if F i is the last fragment in F , function Find_Assignment returns tuple assoc _ tuple representing the computed assignment of t to groups (lines 14–15). Otherwise, function Find_Assignment recursively calls itself to assign t to a group in fragment F i + 1 (line 16). If the recursive call succeeds (i.e., it returns a group association for t), function Find_Assignment returns assoc _ tuple ; it tries to allocate t to a group at higher distance from OptimalGrouping [ t ] [ F i ] , otherwise (lines 18–19). If t cannot be assigned to any group in F i , the function returns null (line 20).

If function Find_Assignment returns a tuple ta , the algorithm inserts ta into the group association A and removes t from To _ Place (lines 17–19).

Step 3: Over-quota grouping.  If Step 2 could not allocate all the tuples in s, the algorithm tries to allocate the remaining tuples in To _ Place to the existing groups, thus possibly creating over-quota groups. To this purpose, for each tuple t in To _ Place , the algorithm calls function Find_Assignment with variable over _ quota set to true. The algorithm updates A and To _ Place according to the result returned by function Find_Assignment (lines 20–25).

Step 4: Re-assignment.  Once tuples in s (or a subset thereof) have been allocated to groups, the algorithm determines the set To _ Empty of groups generated by Steps 2–3 that are under-quota, that is, the groups that do not include the minimum number of tuples necessary to provide privacy guarantees (line 27). The algorithm then calls function Re_Assign in Fig. 9 (line 28).

Function Re_Assign receives as input the set To _ Empty of non-empty but under-quota groups, and tries to reallocate their tuples to other groups (lines 30–38). Tuples in under-quota groups that cannot be reallocated will be removed from the fragmentation and are inserted into To _ Remove (lines 39–40). When a tuple t is inserted into To _ Remove , the corresponding tuple ta in A is removed from the group association and, for each fragment F l , G l ( t ) is set to null (lines 44–45). Due to the removal of t, the group g l to which t belong in F l loses a tuple and it might become under-quota with the consequence that it should be removed. If this is the case, g l is inserted into To _ Empty (line 43). Function Re_Assign returns the set To _ Remove of tuples to be removed from the fragmentation (line 46).

The algorithm then deletes from each fragment both the tuples that have never been assigned to groups and the tuples returned by function Re_Assign (lines 29–30).

The utility of the k-loose association computed by this heuristic algorithm as well as its efficiency are evaluated in Section 7.

We implemented a prototype, written in Python, of the algorithm described in the previous section, and ran several sets of experiments to the aim of evaluating the ability of our approach to compute a k-loose association, while limiting the number of suppressed tuples (i.e., tuples that cannot be included in any group), and of assessing its performance (Section 7.2). We then analyzed the utility provided in query evaluation (Section 7.3). We now present the experimental setting (Section 7.1) and then discuss the experimental results.

7.2. Coverage and performance

We ran a first set of experiments on synthetic data aimed at assessing the coverage of the solution computed by our algorithm, that is, the number of tuples of the original relation that could not be published as they could not be allocated to any group without violating k-looseness. The experiments focused on evaluating how the number of tuples in the relation (Fig. 10(a)) and the variability in the distribution of attribute values (Fig. 10(b)) have an impact on the number of tuples that cannot be released, for different values of k.

OPEN IN VIEWER

Fig. 10.

Percentage of tuples in the original relation that are not released, varying the number of tuples in the relation (a) and the variability in the distribution of attribute values (b). (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140513.)

Figure 10(a) shows that the algorithm is more likely to suppress tuples when operating over small datasets, as the number of candidate groups in each fragment is small. It is then harder to find an assignment for each tuple that satisfies all the heterogeneity properties. As it can be expected, the percentage of suppressed tuples grows with k, since it is harder to define larger groups of tuples (especially for small datasets).

Figure 10(b) illustrates the impact of the variability in the distribution of attribute values on the number of suppressed tuples. As visible from the figure, datasets characterized by low variability cause higher suppression. This is due to the fact that it is hard to assign tuples to groups when there is a higher probability that some of them have the same values for attributes in relevant confidentiality constraints. Indeed, two tuples with the same values for attributes in constraints cannot be assigned to the same group. In the experiments performed on the IPUMS dataset, no tuple has been suppressed.

OPEN IN VIEWER

Fig. 11.

Computational time necessary to determine a k-loose association, varying the number of tuples in the relation (a) and the variability in the distribution of attribute values (b). (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140513.)

A second set of experiments on synthetic data evaluated the impact of the size of the original relation and of the variability in the distribution of attribute values on the performance of our algorithm.

To prove the scalability of our approach, we ran our algorithm with large instances of the original relation, with a number of tuples varying between 2,000 and 100,000. Figure 11(a) illustrates the time necessary to compute a k-loose association and confirms the scalability of the proposed approach. In fact, our prototype is able to find a k-loose association for relations with 100,000 tuples in less than one minute for k = 16 (and we speculate that, according to publicly available Python/C performance ratios [28], an optimized C implementation would take less than one second).

Figure 11(b) illustrates the impact of the variability in the distribution of attribute values on the time necessary to compute a k-loose association, considering configurations with 10,000 tuples. The figure confirms that, as already noted, the lower the variability, the harder the task to find a k-loose association. Both Fig. 11(a) and (b) also show that the computational time grows with the protection degree offered by the k-loose association: higher values of k require a higher computational cost.

In the experiments on the IPUMS dataset, our algorithm always computed a solution in less than 90 s.

7.3. Utility

We ran a set of experiments specifically focused on assessing the gain provided by loose associations, in terms of the utility of query results. We used as a reference the query that identifies the relationship between the Education level of patients and their Salary (i.e., select avg(Salary) from Patients group byEducation). We then defined a k-loose association that aims at keeping in the same group patients with the same Education level in fragment F m and with similar Salary in fragment F l .

OPEN IN VIEWER

Fig. 12.

Utility provided by a k-loose association, varying the number of tuples in the relation (a) and the variability in the distribution of attribute values (b). (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140513.)

Figure 12(a) compares the utility provided by the release of a k-loose association with different values for k, varying the number of tuples in the input dataset. The figure clearly shows that the release of a k-loose association permits to obtain high utility in query evaluation. In most of the considered configurations, utility is nearly 100%, meaning that the result computed over fragmented data complemented with loose associations is nearly the same obtained on the original relation. This figure also confirms that the quality of the loose association computed by our algorithm improves with the number of tuples in the dataset, as it becomes easier to have tuples with similar values for Education and Salary in the same group.

Figure 12(b) illustrates the impact of the variability in the distribution of attribute values on the obtained utility. Greater values of γ increase the variability and lead to a reduction in the probability for an attribute to present the same values in different tuples. Conflicts arise in a group when tuples present the same values on the attributes involved in a constraint. Then, the probability of conflicts decreases as γ increases. The utility provided by the release of a k-loose association is always high, and increases as the variability in the attribute values increases. Our experiments also clearly show that, in line with the observation that utility and privacy are two contrasting requirements, utility decreases as k increases. It is then expected that improvements in confidentiality guarantees of the solution correspond to worsening in the utility of the released data. It is however worth noticing that, also for the worst case in which k = 20 , if the size of the input dataset is not too limited (i.e., in the order of hundreds of tuples) the measured utility was higher than 80%, implying a high utility in query evaluation also when adopting privacy parameters higher than the values we expect to be used in real-world scenarios.

OPEN IN VIEWER

Fig. 13.

Utility provided by a k-loose association with ordering on Education and Salary. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140513.)

We ran a second set of experiments for evaluating the impact of keeping in the same group similar values for an attribute (or a set thereof) of interest for query evaluation (see Section 5). To this aim, we compared the utility of queries q o s (operating on both Education and Salary), q a s (operating only on Education or only on Salary), and q n s (operating on neither Education nor Salary). Figure 13 compares the utility obtained with 7 different queries (query q 0 as representative for q o s , queries q 1 , q 2 , q 3 for q a s , and queries q 4 , q 5 , q 6 for q n s ) with k = 12 , varying k l and k m . Each query is represented by a group of bars, where each bar presents the utility obtained with one of the configurations for parameters k l and k m . The results clearly show that the query with highest utility (almost 100%) is q 0 , which benefits from the ordering over both Education and Salary (i.e., query q o s ). Queries q 2 , q 3 and q 4 take advantage only of the ordering over one attribute, which however permits to obtain utility higher than 80% in all the considered configurations. Our experimental evaluation shows that the release of a loose association provides limited, but not null, utility also for queries q n s . We can then conclude that keeping in the same group tuples with similar values permits to achieve better results in the utility of query evaluation.

OPEN IN VIEWER

Fig. 14.

Utility provided by a k-loose association over two (a) and three (b) fragments. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140513.)

In the experiments performed on the IPUMS dataset, we first defined a k-loose association between fragments F l and F m , and identified two representative sets of queries. The first set of queries operates on the attributes on which fragments of the loose association have been ordered (i.e., q o s , represented by query q 0 and q a s , represented by queries q 1 , q 2 , q 3 ). The second set of queries instead operates only on attributes different from those on which the ordering was performed (i.e., q n s , represented by queries q 4 , … , q 11 ). Figure 14(a) illustrates the utility obtained in executing these two sets of queries over a k-loose association with k = 12 and varying the values of k l and k m . Each query is represented by a group of bars in the figure. Queries involving at least one of the attributes on which the ordering has been performed (i.e., queries q 0 , … , q 3 ) showed excellent utility in the result, close to 100% for all queries. As expected, the utility in executing queries operating on unordered attributes only (i.e., queries q 4 , … , q 11 ) is lower. It is however worth noticing that the results are still appreciable, with most of the queries showing utility between 20% and 35%. Compared to the experiments on the synthetic dataset, the queries of type q n s exhibit better utility. In particular, Fig. 14(a) shows that queries q a s involving both ordered and unordered attributes exhibit utility values similar to query q 0 that involves ordered attributes only. Our explanation for the higher utility obtained on IPUMS dataset is that real data are more structured and present greater regularity and correlations among attribute values than the randomly generated data in our synthetic dataset, which is characterized by one correlation only (the one between attributes Education and Salary).

Figures 13 and 14(a) describe configurations that, keeping k constant, progressively increase the value of parameter k l (and reduce k m accordingly). The utility remains relatively stable across all these configurations, even if we can see that, for some queries, the utility decreases as k l increases, while for a few queries the utility grows with k l . Overall, we consider as preferable the intermediate solutions, with k l and k m near to k , because they are not associated with the lowest levels of utility and because this criterion offers strong benefit when applied to fragmentations with more than two fragments, as observed in the following.

To further evaluate our technique, we performed the same experimental analysis on the fragmentation of IPUMS dataset composed of three (rather than two) fragments. Figure 14(b) reports the utility of queries provided by the release of a k-loose association with k = 12 , comparing the results obtained with a ( 1 , 12 , 12 ) -, ( 2 , 6 , 6 ) - and ( 3 , 4 , 4 ) -grouping. The crucial difference among these configurations is that queries that combine the second and third fragment will operate on a k-loose association between the two fragments with k equal to 144, 36 and 16 (for the constraints that are relevant for the second and third fragment). As we already noticed, an increase in k leads to a reduction in utility. The graph in Fig. 14(b) clearly shows the increase in utility that occurs going from ( 1 , 12 , 12 ) - to ( 3 , 4 , 4 ) -grouping for queries q 0 , … , q 3 . This result proves that, for fragmentations with more than two fragments, there is a significant utility benefit in building loose associations with similar values for parameter k i on all the fragments.

OPEN IN VIEWER

Fig. 15.

Query results computed ordering on Educ and IncWage on a k-loose association among two (a) and three (b) fragments. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140513.)

Figure 15 demonstrates in a different way the utility that can be obtained by the use of loose associations, analyzing query q 0 of the previous experiments. The graph has on the x-axis the different values of attribute Educ, which represents the number of years of education reported in the census, and on the y-axis the average salary (attribute IncWage) for the cohort of people with that level of education. In essence, the graphs plot the result of query q 0 = “select avg(IncWage) from ipums_census group byEduc”. The continuous green line (i.e., the line labeled “real”) reports the results obtained on the real data. The dashed blue horizontal line (i.e., the line labeled “without loose associations”) in the middle is the result that we can obtain without loose associations, because IncWage and Educ belong to different fragments and the global average salary will be returned for every education level. The continuous red line (i.e., the line labeled “with loose associations (ordered)”) describes the result obtained with a k-loose association with k = 12 . Figure 15(a) shows the results obtained in the configuration with two fragments and assuming a ( 4 , 3 ) -grouping, while Fig. 15(b) illustrates the results obtained in the configuration with three fragments and assuming a ( 3 , 4 , 4 ) -grouping. In both graphs, the green and red lines are overlapping over most of the range, clearly showing the utility that can be obtained by loose associations.

Several research efforts have addressed the problem of protecting privacy in data publishing, proposing approaches based on either sanitizing (e.g., [10,15,16,19–21,23,30]) or fragmenting data (e.g., [1,2,7–9,11,29]) before their release. Our approach bears some similarity with k-anonymity [24] for the notion of grouping and more similarity with ℓ-diversity [21] for the consideration of the different values that are involved in the sensitive associations. Apart from this, our problem and solution are different from k-anomymity-like approaches, which are typically based on generalization of quasi-identifying attributes. By contrast, in our approach fragments contain the attribute values that appear in the original relation, while it is the association among fragments that is obfuscated. Most fragmentation works, although showing similarities with our proposal, address an orthogonal problem with respect to the one considered in this paper, as they aim at breaking sensitive associations while maximizing the ability of recipients of evaluating queries on fragments. Recent proposals have also considered the problem of improper information leakage due to data dependencies, which can be exploited to link different fragments [3,13]. Our loose associations can nicely complement these proposals, thus increasing the utility of fragmented data and ensuring proper protection of confidentiality constraints also in presence of data dependencies.

The works closest to our complement published (fragmented) data with information on their association, without disclosing sensitive information [11,14,31]. Our proposal is however more general than these solutions, since they operate on two fragments (or views/tables) only, while we consider an arbitrary number of fragments when defining loose associations. The work in [11] does not take into consideration the possible existence of duplicate values for non-key attributes. Sensitive associations on non-key attributes are therefore exposed to frequency-based attacks. Our heterogeneity properties overcome this issue by preventing the presence of duplicates in the same group of tuples. Anatomy [31] considers the specific problem of protecting the association between respondents’ quasi-identifiers and a sensitive attribute while our solution permits to protect any association among attributes. Anatomy also partitions the original relation in groups of ℓ tuples before splitting attributes in two disjoint fragments. Our approach provides more flexibility in defining groups of tuples because for each fragment F i we can consider a different privacy parameter k i (and a different grouping function) instead of a single ℓ value. By comparing Anatomy with a loose association on two fragments, we can see that the two techniques provide the same protection guarantees and the same utility [14]. Anatomy can then be considered as a specific instance of our approach, where the original relation is partitioned in two fragments: F l , storing the quasi-identifier, F r , storing the sensitive attribute, and k l = 1 and k r = ℓ (or vice versa).

Our work may also bring some resemblance with the proposals in [6,26,27]. The work in [27] adopts horizontal and vertical fragmentation to protect privacy of sparse multidimensional data (e.g., transactional data). The approach in [6] focuses instead on protecting recommendation data expressed by customers (i.e., Netflix movie ratings). Besides operating on different data models, both these proposals differ from our work since they are specifically targeted at protecting respondents’ identities and their association with sensitive attributes. Also, they both adopt a dual approach with respect to loose associations, requiring homogeneity of values in fragments. The work in [26] addresses the problem of destroying the correlation between two disjoint subsets of attributes, preserving as much as possible the other correlations. Our approach does not aim at destroying correlations among attributes, as our goal is to preserve them as much as possible, while satisfying privacy constraints. Also, the solution in [26] adopts masking techniques, while our approach maintains data truthfulness.

Alternative approaches to protect privacy in data release are based on differential privacy (e.g., [15,16]). Although addressing a similar problem, approaches based on differential privacy are not directly applied since they introduce noise in the dataset that depends on the expected users queries. Our approach instead aims at releasing truthful data.

A different line of work is represented by Controlled Query Evaluation (CQE) (e.g., [2,4]). These solutions provide the data owner storing a data collection with a technique for controlling whether users’ queries should be permitted or denied depending on both confidentiality constraints and the history of past interactions. These approaches are not applicable to our scenario, since we publicly release a dataset.

9. Conclusions

We addressed the problem of extending loose associations to operate on multiple fragments. We first described how the publication of multiple loose associations between pairs of fragments can expose sensitive associations, and then presented an approach supporting the definition of a loose association among an arbitrary number of fragments. We also described a heuristic algorithm for the computation of a loose association, and showed the results of an extensive experimental evaluation aimed at analyzing both the efficiency and the effectiveness of the proposed heuristics as well as the utility provided by loose associations in query execution. Our work leaves space for further investigations, including the consideration of external knowledge that data recipients can exploit to reconstruct sensitive associations among attributes in different fragments, and of dynamic datasets, where data in the original relation change over time.