Hira Asghar

Christophe Bobineau

Marie-Christine Rousset
email: christine.rousset@univ-grenoble-alpes.fr

Compatibility Checking Between Privacy and Utility Policies: A Query-Based Approach

Keywords: temporal RDF graphs, temporal aggregated conjunctive queries, utility policy, privacy policy

Data sharing over the internet through smart devices is susceptible to disclose sensitive information of data producers.

To protect the privacy of data producers, we propose a querybased approach where data producers keep their data on decentralized personal data servers and only disclose data to data consumers over secure communication links according to their privacy policies. Data consumers specify the data needed to provide services as utility policies. In our approach, we express the privacy and utility policies as sets of temporal aggregated conjunctive queries. We make explicit several sufficient conditions of compatibility between privacy and utility policies based on their query expressions. On the basis of these results, sensitive data breaches can be prevented by checking whether one of these sufficient conditions is satisfied.

Introduction

Personal data are increasingly disseminated over Internet through mobile devices and smart environments, and are exploited for developing more and more sophisticated services and applications. All these advances come with serious risks for privacy breaches that may reveal private information wanted by users to remain undisclosed. It is therefore of utmost importance to help data producers to keep the control on their data for their privacy protection while preserving the utility of disclosed data for service providers.

In this paper, we approach the problem of utility-aware privacy preservation in the setting of applications where service providers (e.g., power suppliers) perform data analytics on data concerning their customers (e.g., smart home occupants) for optimization or recommendation purposes. In such settings, (sensor) data are gathered, abstracted and transferred through internet protocols from data producers environment (e.g., smart home, smart personal devices) to a centralized data consumer in charge of aggregating data for conducting varied analytics tasks.

Sensitive data leakage can occur at different stages and places due to security vulnerabilities of (1) the network, [START_REF] Baader | Preliminary Results on the Identity Problem in Description Logic Ontologies[END_REF] the centralized server used by the data consumer for collecting data outsourced by the different data producers, and (3) the local servers of each data producer.

Following the vision of [START_REF] Allard | Secure personal data servers: a vision paper[END_REF], we propose, first, to rely on data encryption to secure data exchange through the network and, second, to avoid the privacy risks of data centralization by keeping the data produced by each data owner decentralized in secure personal data servers.

The approach that we promote to face the privacy versus utility dilemma in this setting can be summarized as follows:

1. Data producers keep the control on the data they accept to transmit to the data consumer according to their own privacy policy. 2. The data consumer makes explicit his/her utility policy to explain for which task or service s/he requests data from data producers. 3. In case of incompatibility of the utility policy with the privacy policy of a data producer, the data producer negotiates with the data consumer to find an acceptable privacy-utility trade-off.

In the remaining of this paper, we focus on the problem of checking compatibility between privacy and utility policies, that is at the core of our approach.

Our contribution is twofold. First, we extend the framework proposed in [START_REF] Delanaux | Query-Based Linked Data Anonymization[END_REF] to formalize privacy and utility policies as temporal aggregate queries. Second, we formally define and study the compatibility problem in this query-based framework. In particular, we exhibit several conditions for compatibility or incompatibility that can be automatically verified by comparing the query expressions defining privacy and utility policies.

The paper is organized as follows. In Section 2, we provide the formal background on which our approach relies. In Section 3, we describe the query-based formal framework that we propose to define privacy and utility policies and their compatibility. In Section 4, we summarize our contribution for checking compatibility between privacy and utility policies. Section 5 presents related work, and Section 6 concludes our paper and highlights the future work that we plan to conduct.

By convention and for homogeneity purpose we consider RDF graphs where all the triples are temporal by using 𝑎𝑛𝑦 as a special timestamp when the corresponding triples holds at any time. We will call static the properties involved in triples with 𝑎𝑛𝑦 as timestamps.

Example 1 illustrates a temporal RDF graph describing the data of a given house owner using a simple ontology with properties familySize, address, city, street (that are static) and consumption.

Example 1. The family size, address and street are expressed as triples with special timestamp 𝑎𝑛𝑦 whereas energy consumption triples are timestamped.

Temporal RDF graph of data producer 𝐷𝑃 1 Notation: For a tuple of variables x, 𝜇 ( x) is the tuple obtained by replacing each variable 𝑥 by its value 𝜇 (𝑥). that is bijective and its inverse is also a homomorphism.

(𝑑𝑝 1 𝑓 𝑎𝑚𝑖𝑙 𝑦𝑆𝑖𝑧𝑒 4, 𝑎𝑛𝑦) (𝑑𝑝 1 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 _ : 𝑏 1 , 𝑎𝑛𝑦) (_ : 𝑏 1 𝑠𝑡𝑟𝑒𝑒𝑡 "𝐴𝑙𝑠𝑎𝑐𝑒𝐿𝑜𝑟𝑟𝑎𝑖𝑛𝑒", 𝑎𝑛𝑦) (_ : 𝑏 1 𝑐𝑖𝑡 𝑦 "𝐺𝑟𝑒𝑛𝑜𝑏𝑙𝑒", 𝑎𝑛𝑦) (𝑑𝑝 1 𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛

Temporal aggregated conjunctive queries

We first formally define the general form of temporal aggregate conjunctive queries (TACQs) with a SPARQL-like syntax extended with time windows for capturing aggregate on time.

To simplify the exposition, we will only consider aggregate queries which have a single aggregation term. In most cases, queries with several aggregate terms are equivalent to the unions of queries with same body and a single aggregate term [START_REF] Cohen | Containment of aggregate queries[END_REF]. The general syntax can be simplified as follows for capturing particular cases:

• When either x is empty or there is no aggregate term, we can omit the GROUP BY clause. • When 𝑆𝑖𝑧𝑒 = ∞ (and thus 𝑆𝑡𝑒𝑝 = 0), the TIMEWIN-DOW clause can be omitted. • The 𝐹 𝐼𝐿𝑇 𝐸𝑅 clause can be omitted when the corresponding boolean expression is TRUE (called empty 𝐹 𝐼𝐿𝑇 𝐸𝑅). Note however, that when TIMEWINDOW is specified, FILTER always contains the implicit following constraints for each timestamp variable ?𝑡𝑠: ?𝑡𝑠 ≤ ?𝑡𝑖𝑚𝑒𝑊 𝑖𝑛𝑑𝑜𝑤𝐸𝑛𝑑 ∧ ?𝑡𝑠 > ?𝑡𝑖𝑚𝑒𝑊 𝑖𝑛𝑑𝑜𝑤𝑠𝐸𝑛𝑑 -𝑆𝑖𝑧𝑒. • For static properties, the timestamp variables can be omitted as they can only be assigned to the special timestamp 𝑎𝑛𝑦, and the corresponding temporal triple patterns can be simplified into standard triple patterns. In Example 3, we illustrate several of these cases.

Example 3.

𝑇 𝐴𝐶𝑄 1 is an example of a standard conjunctive query which is a particular case of a TACQ in which there is no (temporal) aggregation. It asks the street and city of each data producer.

𝑇 𝐴𝐶𝑄 1 : a particular case of a simple conjunctive query x TIMEWINDOW (𝑆𝑖𝑧𝑒, 𝑆𝑡𝑒𝑝) its evaluation over a given temporal data graph 𝐺 is defined in terms of filtered homomorphism and groups (respectively defined in Definition 9 and Definition 10) for obtaining its answer set (Definition 11).

Definition 9 (Filtered homomorphisms). Let 𝑀 the set of homomorphisms from 𝐺𝑃 to 𝐺. The filtered set of homomorphisms is the subset of 𝑀 of homomorphisms 𝜇 such that 𝜇(FILTER) = TRUE.

When FILTER is empty then the filtered set of homomorphisms is equal to 𝑀.

Definition 10 states that there are as many groups as homomorphisms allowing to match the tuple x with tuples of values v multiplied by the number of time intervals defined by values of 𝑘 as: ]𝑛𝑜𝑤 -𝑘 × 𝑆𝑡𝑒𝑝 -𝑆𝑖𝑧𝑒, 𝑛𝑜𝑤 -𝑘 × 𝑆𝑡𝑒𝑝] where 𝑛𝑜𝑤 denotes the timestamp at which the query is executed.

Definition 10 (Groups). Let 𝐹 𝑀 be the set of filtered homomorphisms from 𝐺𝑃 to 𝐺. Groups are defined for each tuple v and each time interval 𝑘 as follows:

𝐺𝑟𝑜𝑢𝑝 𝑘 ( v) = {𝜇 (𝑦) | 𝜇 ∈ 𝐹 𝑀, 𝜇 ( x) = v,
and for each timestamp variable ?𝑡𝑠 𝜇 (?𝑡𝑠) = 𝑎𝑛𝑦 or 𝜇 (?𝑡𝑠) ∈ ]𝑛𝑜𝑤 -𝑘 × 𝑆𝑡𝑒𝑝 -𝑆𝑖𝑧𝑒, 𝑛𝑜𝑤 -𝑘 × 𝑆𝑡𝑒𝑝]) and 𝜇 (?𝑡𝑖𝑚𝑒𝑊 𝑖𝑛𝑑𝑜𝑤𝐸𝑛𝑑) = 𝑛𝑜𝑤 -𝑘 × 𝑆𝑡𝑒𝑝}.

It is important to note that if there is no aggregate term, there is only one time interval (i.e., ] -∞, 𝑛𝑜𝑤]) and there are as many groups as distinct tuples v.

For each group 𝐺𝑟𝑜𝑢𝑝 𝑘 ( v), an answer is: either the tuple v if there is no aggregate term, or the tuple ( v, 𝑟 ) obtained by concatenating the tuple v with the result 𝑟 of the aggregation function applied to the values in the group. This is formalized in Definition 11.

Definition 11 (Answer set

). The answer set of 𝑇 𝐴𝐶𝑄 evaluated over 𝐺 is defined as follows:

• if there is no aggregate term:

𝐴𝑛𝑠 (𝑇 𝐴𝐶𝑄, 𝐺) = {v | 𝐺𝑟𝑜𝑢𝑝 𝑘 ( v) is a group of 𝑇 𝐴𝐶𝑄 for 𝐺 }. • else: 𝐴𝑛𝑠 (𝑇 𝐴𝐶𝑄, 𝐺) = {( v, 𝑎𝑔𝑔(𝐺𝑟𝑜𝑢𝑝 𝑘 ( v))) | 𝐺𝑟𝑜𝑢𝑝 𝑘 ( v) is a group of 𝑇 𝐴𝐶𝑄 for 𝐺 }.
Definition 12 makes explicit the homomorphism support of an answer.

Definition 12 (Homomorphism support of an answer). Let ā an answer obtained from a given group 𝐺𝑟𝑜𝑢𝑝 𝑘 ( v). Its homomorphism support, denoted 𝐻𝑠𝑢𝑝𝑝𝑜𝑟𝑡 ( ā), is the subset of filtered homomorphisms 𝜇 such that 𝜇 ( x) = v.

Example 4 shows the answers sets of queries in Example 3 over the temporal RDF graph 𝐷𝑃 1 of Example 1.

Example 4.

The answer set of 𝑇 𝐴𝐶𝑄 1 is:

Answer set of 𝑇 𝐴𝐶𝑄 1 over 𝐷𝑃 1 𝐴𝑛𝑠 (𝑇 𝐴𝐶𝑄 1 , 𝐷𝑃 1 ) = {(𝑑𝑝 1 , " Alsace Lorraine " , " Grenoble ") }
The homomorphism support of its single answer is restricted to the single homomorphism ℎ shown below.

Homomorphism support of 𝐴𝑛𝑠 (𝑇 𝐴𝐶𝑄 1 , 𝐷𝑃 1 ) 𝐻𝑠𝑢𝑝𝑝𝑜𝑟𝑡 = {ℎ } ℎ : {?𝑑𝑝/𝑑𝑝 1 , ?𝑎/_ : 𝑏 1 , ?𝑠𝑡𝑟𝑒𝑒𝑡 /"𝐴𝑙𝑠𝑎𝑐𝑒𝐿𝑜𝑟𝑟𝑎𝑖𝑛𝑒", ?𝑐𝑖𝑡 𝑦/"𝐺𝑟𝑒𝑛𝑜𝑏𝑙𝑒"} } When 𝑇 𝐴𝐶𝑄 3 is evaluated at 17:30 the same day as the temporal triples in 𝐷𝑃 1 (i.e., 𝑛𝑜𝑤 = 2021-04-04T17:30:00), its answer set is:

Answer set of 𝑇 𝐴𝐶𝑄 3 over 𝐷𝑃 1 𝐴𝑛𝑠 (𝑇 𝐴𝐶𝑄 3 , 𝐷𝑃 1 ) = {( 𝑑𝑝 1
, " Alsace Lorraine " , 2021 -04 -04 T17 :30:00 , 10) ( 𝑑𝑝 1 , " Alsace Lorraine " , 2021 -04 -04 T16 :30:00 , 25) ( 𝑑𝑝 1 , " Alsace Lorraine " , 2021 -04 -04 T15 :30:00 , 40) }

The homomorphism support of the second answer is made of two homomorphisms ℎ 1 and ℎ 2 which differ in the assignment of the aggregate variable ?consumption. Based on Definition 3, the evaluation over (partially instantiated) graph patterns of plain conjunctive queries is possible and the resulting set of answers is defined in Definition 13.

Homomorphism support of an answer of 𝑇 𝐴𝐶𝑄

3 𝐻𝑠𝑢𝑝𝑝𝑜𝑟𝑡 = {ℎ 1 , ℎ 2 } ℎ 1 : { ? dp /𝑑𝑝

Definition 13 (Conjunctive query evaluated over graph patterns).

Let 𝑄: SELECT x WHERE GP be a plain conjunctive query, and let 𝑃𝐼𝐺 a graph pattern. The answer set of 𝑄 over 𝑃𝐼𝐺 is:

𝐴𝑛𝑠 (𝑄, 𝑃𝐼𝐺) = { ā| ā is a tuple of constants and ℎ is an homomorphism from 𝐺𝑃 to 𝑃𝐼𝐺 such that ℎ( x) = ā }

Query-based specification of policies

We define utility and privacy policies in the form of TACQs that are built upon a common schema or ontology.

Definition 14 (Utility policy). A utility policy is defined by a set of TACQ queries, called utility queries. A utility policy (issued by a service provider) is satisfied by a data producer if s/he accepts to provide the set of answers of all of the utility queries for any RDF graph storing her/his data.

Definition 15 (Privacy policy). A privacy policy is defined by a set of TACQ queries, called privacy queries. A privacy policy, specific to each data producer, is satisfied when all the answers of all the privacy queries remain undisclosed for any temporal RDF graph storing her/his data.

Checking whether her/his privacy policy is incompatible with the utility policy of a service provider is an important property to be checked in the name of each data producer for guiding her/his decision of satisfying the utility policy.

Independently of any graph data, we have to prevent that answers to an utility query allow to infer answers to one of the privacy queries. Definition 17 formalizes incompatibility as inferring answers of a privacy query from sets of answers of utility queries on the same data graph 𝐺 without necessarily knowing it.

It relies on Definition 16 that defines the logical signature of an answer (set) of a query as the logical formula characterizing all the (unknown) temporal data graphs leading to this answer (set) for this query.

Given a TACQ Q: SELECT x, 𝑎𝑔𝑔(𝑦) WHERE {𝐺𝑃 . 𝐹 𝐼𝐿𝑇 𝐸𝑅} GROUP BY x TIMEWINDOW (𝑆𝑖𝑧𝑒, 𝑆𝑡𝑒𝑝) we interpret 𝐺𝑃 as the logical conjunction of its triple pattern seen as atomic formulas.

Definition 16 (Logical signature of answers). For an answer ( ā, 𝑟 ) to the query 𝑄, let 𝜇 ā the mapping assigning each grouping variable 𝑥 in x to the corresponding constant 𝑎 in ā. The logical signature of ( ā, 𝑟 ) and 𝑄, denoted 𝜎 (( ā, 𝑟 ), 𝑄), is the formula:

(∃𝑦∃z 𝜇 ā (𝐺𝑃) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅))
∧ 𝑎𝑔𝑔({𝑦|∃z, 𝜇 ā (𝐺𝑃) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅)}) = 𝑟 where z is the (possibly empty) subset of variables in 𝑉 𝑎𝑟 (𝐺𝑃) non including the aggregate variable 𝑦. When there is no aggregate variable, the logical signature is reduced to the formula:

(∃𝑦∃z 𝜇 ā (𝐺𝑃) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅)) .
The logical signature of an answer set 𝐴𝑛𝑠𝑤𝑒𝑟𝑆𝑒𝑡 of a given query 𝑄 is the conjunction of the logical signatures of each answer:

𝜎 (𝐴𝑛𝑠𝑤𝑒𝑟𝑆𝑒𝑡, 𝑄) = 𝑎𝑛𝑠 ∈𝐴𝑛𝑠𝑤𝑒𝑟𝑆𝑒𝑡 𝜎 (𝑎𝑛𝑠, 𝑄)
Example 5 shows logical signatures of answers of a simple conjunctive query and of a temporal aggregate query.

Example 5. The logical signature of the answer (dp 1 , "Alsace Lorraine", "Grenoble") of 𝑇 𝐴𝐶𝑄 1 is provided in the following listing.

Logical signature of the answer (dp 1 , "Alsace Lorraine", "Grenoble") of 𝑇 𝐴𝐶𝑄 1 𝜎 (( dp 1 , " Alsace Lorraine " ," Grenoble ") , 𝑇 𝐴𝐶𝑄 1 ) : ∃ ?𝑎 , dp 1 address ?𝑎 ∧ ?𝑎 street " Alsace Lorraine " ∧ ?𝑎 city " Grenoble ".

The logical signature 𝜎 ((dp 1 , "Alsace Lorraine",2021-04-04T17:30:00, 20), 𝑇 𝐴𝐶𝑄3) is provided in the following listing.

Logical signature of the answer (dp 1 , "Alsace Lorraine", 2021-04-04T17:30:00, 20) of 𝑇 𝐴𝐶𝑄 3 𝜎 (( dp 1 , " Alsace Lorraine " , 2021 -04 -04 T17 :30:00 , 20) , 𝑇 𝐴𝐶𝑄 3 ) : ∃ ?𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 ∃ ?𝑡𝑠 ∃?𝑓 𝑆𝑖𝑧𝑒 ∃?𝑎 , ( dp 1 consumption ?𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 ,?𝑡𝑠 ) ∧ dp 1 familySize ?𝑓 𝑆𝑖𝑧𝑒 ∧ dp 1 address ?𝑎 ∧ ?𝑎 street " Alsace Lorraine " ∧ ?𝑎 city " Grenoble " ∧ ?𝑓 𝑆𝑖𝑧𝑒 > 2 ∧ ?𝑡𝑠 ≤ 2021 -04 -04 T17 :30:00 ∧ ?𝑡𝑠 > 2021 -04 -04 T14 :30:00 ∧ AVG {?𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 | ∃ ?𝑡𝑠 ∃?𝑓 𝑆𝑖𝑧𝑒 ∃?𝑎 , ( dp 1 consumption ?𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 , ?𝑡𝑠 ) ∧ dp 1 familySize ?𝑓 𝑆𝑖𝑧𝑒 ∧ dp 1 address ?𝑎 ∧ ?𝑎 street " Alsace Lorraine " ∧ ?𝑎 city " Grenoble " ∧ ?𝑓 𝑆𝑖𝑧𝑒 > 2 ∧ ?𝑡𝑠 ≤ 2021 -04 -04 T17 :30:00 ∧ ?𝑡𝑠 > 2021 -04 -04 T16 :30:00 } = 20

Definition 17 (Incompatibility between privacy and utility).

A privacy policy is incompatible with a utility policy if the logical signature of an answer to a privacy query is entailed by the union of logical signatures of answers sets of utility queries.

Continuing Example 5, we have: 𝜎 ((𝑑𝑝 1 , "𝐴𝑙𝑠𝑎𝑐𝑒 𝐿𝑜𝑟𝑟𝑎𝑖𝑛𝑒", 2021 -04 -04𝑇 17 : 30 : 00, 20), 𝑇 𝐴𝐶𝑄 3 ) |= 𝜎 ((𝑑𝑝 1 , "𝐴𝑙𝑠𝑎𝑐𝑒 𝐿𝑜𝑟𝑟𝑎𝑖𝑛𝑒", "𝐺𝑟𝑒𝑛𝑜𝑏𝑙𝑒"),𝑇 𝐴𝐶𝑄 1 ) Therefore a privacy policy made of the single privacy query 𝑇 𝐴𝐶𝑄 1 is incompatible with any utility policy containing 𝑇 𝐴𝐶𝑄 3 as utility query.

Definition 20 defines a weaker notion of incompatibility that prevents from the risk to get an answer to a privacy query among the answers inferred by variants of utility queries. A variant of a query only differs from the original query with the FILTER condition while preserving satisfiability.

Definition 18 (Satisfiable Boolean expression). A Boolean expression 𝐸𝑥𝑝 is satisfiable if there exists at least an assignment of variables in 𝐸𝑥𝑝 that makes it TRUE. SELECT ?x WHERE {?x p ?y. FILTER (?y < 4 )} Note that 𝑄 𝑝 is compatible (i.e., not incompatible) with 𝑄 𝑢 since the logical signature of each answer 𝑎 of 𝑄 𝑝 is: ∃ ?y (a p ?y) ∧ (?y > 2) which is not logically entailed by the logical signature of an answer 𝑎 of 𝑄 𝑢 which is the formula: ∃ ?y (a p ?y) ∧ (?y < 4).

However it is incompatible with the variant 𝑄 ′ 𝑢 of 𝑄 𝑢 given in Example 6.

Compatibility checking

In this section, we exhibit a set of sufficient and necessary conditions for compatibility or incompatibility.

In Section 4.1, we start by focusing on the case where utility and privacy queries are plain conjunctive queries without aggregate terms and without FILTER conditions. Then, in Section 4.2, we handle the case where utility and privacy queries are conjunctive queries with FILTER conditions. Finally, Sections 4.3 and 4.4 are dedicated to the more general case of queries with aggregate terms possibly with time windows.

Without loss of generality, by renaming variables within each query, we consider that queries have no variable in common.

For a TACQ in its general form, we will often rely on its conjunctive part defined in Definition 21. Proof. In the case of conjunctive queries and according to Definition 16, the logical signature of an answer ā to a query 𝑄 is a formula of the form: ∃z 𝜇 ā (𝐺𝑃) where 𝐺𝑃 is the conjunction of triples patterns in the graph pattern of 𝑄 interpreted as logical atoms and 𝜇 is an assignment of the tuple x of the output variables of 𝑄 to the tuple of constants ā, and z are the other variables occurring in 𝑄.

If 𝑄 𝑝 is incompatible with the utility queries, it means by definition that there exists tuples of constants ā, ā1 , ..., ā𝑛 such that ∃z 1 ... ∃z 𝑛 𝜇 ā1 (𝐺𝑃 𝑢 1 )∧...∧𝜇 ā𝑛 (𝐺𝑃 𝑢 𝑛 ) |= ∃z 𝜇 ā (𝐺𝑃 𝑝 ).

Since the sets of variables in each query are pairwise disjoint, the entailment is only possible if there exists an homomorphism ℎ from the variables in z to the variables or constants in the left hand side so that all the atoms in ℎ(𝜇 ā (𝐺𝑃 𝑝 )) appear in the union of the atoms in 𝜇 ā1 (𝐺𝑃 𝑢 1 ) ∧ ... ∧ 𝜇 ā𝑛 (𝐺𝑃 𝑢 𝑛 ).

Let 𝐹𝑟𝑜𝑧𝑒𝑛 be the freezing of 𝑖 ∈ [1.

.𝑛] 𝐺𝑃 𝑢 𝑖 obtained by replacing each output variable 𝑥 𝑢 𝑖 by 𝜇 ā𝑖 (𝑥 𝑢 𝑖 ). The homomorphism ℎ ∪ 𝜇 ā from the graph pattern 𝐺𝑃 𝑝 to 𝐹𝑟𝑜𝑧𝑒𝑛 allows to show that ā is an answer of 𝑄 𝑝 when evaluated over 𝐹𝑟𝑜𝑧𝑒𝑛.

For the converse way of the proof, Let us consider 𝐹𝑟𝑜𝑧𝑒𝑛 a freezing of the output variables of 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 such that there exists an answer c of 𝑄 𝑝 when evaluated over 𝐹𝑟𝑜𝑧𝑒𝑛. There exists an homomorphism ℎ from 𝐺𝑃 𝑝 to 𝐹𝑟𝑜𝑧𝑒𝑛 such that ℎ( x) = c. The homomorphism ℎ allows to show the entailment between the formulas ∃z 𝑢 𝐹𝑟𝑜𝑧𝑒𝑛 and ∃z ℎ c (𝐺𝑃 𝑝 ) where 𝐺𝑃 𝑝 and 𝐹𝑟𝑜𝑧𝑒𝑛 are interpreted as the conjunction of their respective triple patterns seen as logical atoms, and ℎ c is the restriction of ℎ to the output variables of 𝑄 𝑝 .

In fact, the formula ∃z ℎ c (𝐺𝑃 𝑝 ) is the logical signature of the answer c of 𝑄 𝑝 , while the formula ∃z 𝑢 𝐹𝑟𝑜𝑧𝑒𝑛 is the conjunction of logical signatures of the answers 𝑓 𝑟𝑒𝑒𝑧𝑒 ( x𝑢 𝑖 ) of each 𝑄 𝑢 𝑖 where 𝑓 𝑟𝑒𝑒𝑧𝑒 is the freezing function applied to the output variables of the different 𝑄 𝑢 𝑖 to obtain 𝐹𝑟𝑜𝑧𝑒𝑛.

Therefore, the privacy query 𝑄 𝑝 is incompatible with the utility queries. □ Example 7. Let us consider the following privacy and utility queries: 𝑄 𝑝 : SELECT ?x WHERE ?x p ?y . ?y q ?z 𝑄 𝑢 1 : SELECT ?x1 ?y1 WHERE ?x1 p ?y1? . ?y1 r ?z1 𝑄 𝑢 2 : SELECT ?x2 WHERE ?x2 q ?y2 The following 𝐹𝑟𝑜𝑧𝑒𝑛 and 𝐹𝑟𝑜𝑧𝑒𝑛 ′ are different freezing of the output variables in the union of the utility graph patterns: 𝐹𝑟𝑜𝑧𝑒𝑛 = {c1 p c2 . c2 r ?z1 . c3 q ?y2 } 𝐹𝑟𝑜𝑧𝑒𝑛 ′ = {c1 p c2 . c2 r ?z1 . c2 q ?y2 } 𝐴𝑛𝑠 (𝑄 𝑝 , 𝐹𝑟𝑜𝑧𝑒𝑛) is empty but 𝐴𝑛𝑠 (𝑄 𝑝 , 𝐹𝑟𝑜𝑧𝑒𝑛 ′ ) = {𝑐1}. This is enough to prove that 𝑄 𝑝 is incompatible with the utility policy composed by the two utility queries 𝑄 𝑢 1 and 𝑄 𝑢 2 .

Let us replace the utility query 𝑄 𝑢 1 by the utility query with same graph pattern but with one output variable less: 𝑄 ′ 𝑢 1 : SELECT ?x1 WHERE ?x1 p ?y1 . ?y1 r ?z1 No freezing of the output variable ?x1 of 𝑄 ′ 𝑢 1 combined with a freezing the output variable of 𝑄 𝑢 2 can lead to an answer of 𝑄 𝑝 when evaluated over the resulting graph pattern which is of the form: {c1 p ?y1. ?y1 r ?z1. c2 q ?y2 } Therefore 𝑄 𝑝 is compatible with 𝑄 ′ 𝑢 1 and 𝑄 𝑢 2 . Complexity: In the worst case, checking compatibility of plain conjunctive queries using Theorem 4.1 requires to evaluate the privacy query over the frozen graph patterns resulting from all the possible freezing of the output variables of the utility queries. The evaluation of the privacy query over a frozen graph pattern is polynomial in the size of the utility queries but the number of possible freezing is 2 𝑂𝑉 𝑢 where 𝑂𝑉 𝑢 is the number of output variables of the utility queries. As a matter of fact, a freezing can be obtained from the initial freezing, which assigns each output variable to a distinct fresh constant, by equating a subset of these constants. In practice, the choice of constants to equate is strongly constrained by the joins between variables of the privacy query that are required to make possible the existence of an answer to 𝑄 𝑝 .

We end this section by two theorems that provide sufficient conditions of compatibility. Theorem 4.2 states a sufficient condition for compatibility of plain conjunctive queries, while Theorem 4.3 states a sufficient condition of compatibility for general TACQs based on checking their conjunctive parts.

Theorem 4.2 (Sufficient condition of compatibility for conjunctive queries). When privacy and utility queries are plain conjunctive queries, a privacy query is compatible with utility queries if its graph pattern is disjoint with every graph pattern of the utility queries.

Proof Proof. In the case of conjunctive queries with FILTER, the logical signature of an answer ā to a query 𝑄 is a formula of the form: (∃z, 𝜇 ā (𝐺𝑃) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅)) where 𝐺𝑃 is the conjunction of triples patterns in the graph pattern of 𝑄 interpreted as logical atoms and 𝜇 is an assignment of the tuple x of the output variables of 𝑄 to the tuple of constants ā, and z are the other variables occurring in 𝑄.

If 𝑄 𝑝 is incompatible with the utility queries, it means by definition that there exists tuples of constants ā, ā1 , ..., ā𝑛 such that ∃z 1 ...

∃z 𝑛 𝜇 ā1 (𝐺𝑃 𝑢 1 )∧𝜇 ā1 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 1 )∧...∧ 𝜇 ā𝑛 (𝐺𝑃 𝑢 𝑛 ) ∧𝜇 ā𝑛 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑛 ) |= ∃z 𝜇 ā (𝐺𝑃 𝑝 ) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ).
Since the sets of variables in each query are pairwise disjoint, the entailment is only possible if there exists an homomorphism ℎ from the variables in z to the variables or constants in the left hand side so that all the atoms in ℎ(𝜇 ā (𝐺𝑃 𝑝 )) appear in the union of the atoms in 𝜇 ā1 (𝐺𝑃 𝑢 1 ) ∧ ...∧𝜇 ā𝑛 (𝐺𝑃 𝑢 𝑛 ), and ℎ(𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )) is entailed by 𝜇 ā1 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 1 ) ∧... ∧ 𝜇 ā𝑛 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑛 ).

Let 𝐹𝑟𝑜𝑧𝑒𝑛 be the result on 𝑖 ∈ [1.

.𝑛] 𝐺𝑃 𝑢 𝑖 of the freezing 𝑓 𝑟𝑒𝑒𝑧𝑒 that replaces each output variable 𝑥 𝑢 𝑖 by 𝜇 ā𝑖 (𝑥 𝑢 𝑖 ). The homomorphism ℎ ∪ 𝜇 ā from the graph pattern 𝐺𝑃 𝑝 to 𝐹𝑟𝑜𝑧𝑒𝑛 allows to show that ā is an answer of the conjunctive part of 𝑄 𝑝 when evaluated over 𝐹𝑟𝑜𝑧𝑒𝑛, and: 𝑓 𝑟𝑒𝑒𝑧𝑒

( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) |= ℎ ∪ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )
For the converse way of the proof, Let us consider 𝐹𝑟𝑜𝑧𝑒𝑛 the result on 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 of a freezing 𝑓 𝑟𝑒𝑒𝑧𝑒 of the output variables such that there exists an answer c of 𝑄 𝑝 when evaluated over 𝐹𝑟𝑜𝑧𝑒𝑛 with a support homomorphism ℎ such that ℎ( x) = c and 𝑓 𝑟𝑒𝑒𝑧𝑒

( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) |= ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ).
The homomorphism ℎ allows to show the entailment between the formulas 𝜙 1 : ∃z 𝑢 𝐹𝑟𝑜𝑧𝑒𝑛 ∧𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) and 𝜙 2 : ∃z ℎ c (𝐺𝑃 𝑝 ) ∧ ℎ c (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) where 𝐺𝑃 𝑝 and 𝐹𝑟𝑜𝑧𝑒𝑛 are interpreted as the conjunction of their respective triple patterns seen as logical atoms, and ℎ c is the restriction of ℎ to the output variables of 𝑄 𝑝 . . In fact, 𝜙 1 and 𝜙 2 are respectively the conjunction of logical signatures of the answers 𝑓 𝑟𝑒𝑒𝑧𝑒 ( x𝑢 𝑖 ) of each 𝑄 𝑢 𝑖 , and the logical signature of the answer c of 𝑄 𝑝 .

Therefore, the privacy query 𝑄 𝑝 is incompatible with the utility queries. □ Example 8. Let us consider the following privacy and utility queries, which are obtained by adding FILTER conditions to the queries in Example 7.

𝑄𝐹 𝑝 : SELECT ?x WHERE ?x p ?y . ?y q ?z . FILTER ( ?y < 6 ∧ ?z > 3) 𝑄𝐹 𝑢 1 : SELECT ?x1 ?y1 WHERE ?x1 p ?y1? . ?y1 r ?z1.

FILTER ( ?y1 < 5) 𝑄𝐹 𝑢 2 : SELECT ?x2 WHERE ?x2 q ?y2. FILTER (?y2 > 10) In Example 7, we have seen that the conjunctive part of 𝑄𝐹 𝑝 (the query 𝑄 𝑝 in Example 7) has the answer c1 when evaluated over 𝐹𝑟𝑜𝑧𝑒𝑛 ′ : {c1 p c2 . c2 r ?z1 . c2 q ?y2 }, obtained by applying the freezing function of the output variables of the utility queries: 𝑓 𝑟𝑒𝑒𝑧𝑒(?x1) = c1 , 𝑓 𝑟𝑒𝑒𝑧𝑒(?y1) = c2 and 𝑓 𝑟𝑒𝑒𝑧𝑒(?x2) = c2.

We get: 𝑓 𝑟𝑒𝑒𝑧𝑒 ((?y1 < 5) ∧ (?y2 > 10)) = (c2 < 5) ∧ (?y2 > 10)

The homomorphism support h of the answer c1 of 𝑄𝐹 𝑝 over 𝐹𝑟𝑜𝑧𝑒𝑛 ′ is: h(?x) = c1 , h(?y) = c2 , h(?z) = ?y2. and ℎ(?y < 6 ∧ ?z > 3) = (c2 < 6 ∧ ?y2 > 3) Checking that (c2 < 6 ∧ ?y2 > 3) is entailed by (c2 < 5) ∧ (?y2 > 10) is enough to prove that 𝑄𝐹 𝑝 is incompatible with the utility policy composed by the two utility queries 𝑄𝐹 𝑢 1 and 𝑄𝐹 𝑢 2 .

Let us replace the utility query 𝑄𝐹 𝑢 2 by 𝑄𝐹 ′ 𝑢 2 : 𝑄𝐹 ′ 𝑢 2 : SELECT ?x2 WHERE ?x2 q ?y2. FILTER (?y2 > 1)

We have to check whether (c2 < 6 ∧ ?y2 > 3) is entailed by (c2 < 5) ∧ (?y2 > 1). This is not the case and so 𝑄𝐹 𝑝 is compatible with the utility queries 𝑄𝐹 𝑢 1 and 𝑄𝐹 ′ 𝑢 2 . However, 𝑄𝐹 𝑝 is weakly incompatible with the utility queries 𝑄𝐹 𝑢 1 and 𝑄𝐹 ′ 𝑢 2 .

Theorem 4. For doing so, first we remark that each freezing satisfying the conditions of the theorem can be constrained by equating freezing constants for getting a connected freezing satisfying also the conditions of the theorem. A freezing is connected if each single 𝐺𝑃 𝑢 𝑖 has a fresh constant in common with the freezing of atleast another 𝐺𝑃 𝑢 𝑗 ).

Then:

-for each atomic comparison 𝑡 comp 𝑡 ′ in ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) such that 𝑡 and 𝑡 ′ are either numbers or terms in the freezing of a single 𝐺𝑃 𝑢 𝑖 , we add to 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 the atomic constraint obtained by defreezing the constants possibly involved in 𝑡 𝑐𝑜𝑚𝑝 𝑡 ′ .

-for each atomic comparison 𝑡 𝑐𝑜𝑚𝑝 𝑡 ′ in ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) such that 𝑡 and 𝑡 ′ are not in the freezing of single 𝐺𝑃 𝑢 𝑖 , we can build a chain of comparisons 𝑡 0 𝑐𝑜𝑚𝑝 𝑡 1 , ...,𝑡 𝑘-1 𝑐𝑜𝑚𝑝 𝑡 𝑘 where 𝑡 0 = 𝑡 and 𝑡 𝑘 = 𝑡 ′ where each pair 𝑡 𝑗 , 𝑡 𝑗+1 are terms appearing in the freezing of single 𝐺𝑃 𝑢 𝑗 . We just have to add to each 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 2 based on the triple patterns ?y q ?z and ?x2 q ?y2 leads to the unsatisfiability of: ?y < 6 ∧ ?z > 3 ∧ ?z < 2.

This makes 𝑄 𝑝 compatible with the utility queries 𝑄𝐹 ′ 𝑢 1 and 𝑄𝐹 ′ 𝑢 2 .

Case of aggregates with same time windows

From now, based on Theorem 4.3, we aim at conditions for a privacy query with aggregate to be compatible or incompatible with utility queries with aggregate in the case where their conjunctive parts are incompatible.

Since the aggregate values are computed based on groups that are specific to each query, if the conjunctive part 𝐶𝑜𝑛 𝑗 (𝑄 𝑝 ) of a privacy query 𝑄 𝑝 is compatible with the conjunctive part 𝐶𝑜𝑛 𝑗 (𝑄 𝑢 𝑖 ) of each utility query 𝑄 𝑢 𝑖 , there is no way to infer the aggregate value 𝑟 of an answer ( ā, 𝑟 ) of 𝑄 𝑝 from the union of answer sets of utility queries with aggregates.

Therefore we focus now on the compatibility between one privacy query 𝑄 𝑝 and one utility query 𝑄 𝑢 such that 𝐶𝑜𝑛 𝑗 (𝑄 𝑝 ) is incompatible with 𝐶𝑜𝑛 𝑗 (𝑄 𝑢 ).

We ?dp' familySize ?s'} GROUP BY ?street' Freezing the ?city variable of 𝑄 𝑝 with the constant "Grenoble" in 𝑄 𝑢 results in: 𝐹𝑟𝑜𝑧𝑒𝑛 = {?dp city "Grenoble" . ?dp street ?street . ?dp fam-ilySize ?s} which is isomorphic with the graph pattern of 𝑄 𝑢 .

In this case, the group 𝐺𝑟𝑜𝑢𝑝 ("𝐺𝑟𝑒𝑛𝑜𝑏𝑙𝑒") of 𝑄 𝑝 can be obtained as the union of the groups of 𝑄 𝑢 on all the values of ?𝑠𝑡𝑟𝑒𝑒𝑡 ′ resulting from the evaluation of 𝑄 𝑢 .

Since, in addition, the aggregate function is the same in 𝑄 𝑝 and 𝑄 𝑢 , 𝑄 𝑝 is thus incompatible with 𝑄 𝑢 . Let us consider now 𝑄 ′ 𝑝 : SELECT ?city AVG(?s) WHERE {?dp city ?city . ?dp street "Alsace Lorraine" . ?dp familySize ?s} Data security is also an important topic for which secure protocols based on encryption has been proposed that enable to do some computations on encrypted outsourced data. In contrast with our work, each protocol may be specific to the target computations to be feasible in practice like in [START_REF] Ciucanu | GOOSE: A Secure Framework for Graph Outsourcing and SPARQL Evaluation[END_REF].

An alternative approach for protecting against privacy breaches consists in applying access control methods to RDF data ( [START_REF] Kirrane | Access control and the Resource Description Framework: A survey[END_REF][START_REF] Oulmakhzoune | Privacy Policy Preferences Enforced by SPARQL Query Rewriting[END_REF][START_REF] Villata | An Access Control Model for Linked Data[END_REF]). In the Semantic Web setting, when data are described by description logics ontologies, preliminary results on role-based access control have been obtained in [START_REF] Baader | Preliminary Results on the Identity Problem in Description Logic Ontologies[END_REF] for the problem of checking whether a sequence of role changes and queries can infer that an anonymous individual is equal to a known individual. However, all these works do not handle utility queries.

A query-based logical framework for RDF data has been introduced in [START_REF] Bernardo | Logical Foundations of Privacy-Preserving Publishing of Linked Data[END_REF][START_REF] Bernardo | Logical Foundations of Linked Data Anonymisation[END_REF], where sensitive information is expressed as a privacy policy in the form of SPARQL query whose results must not disclose sensitive information of individual. It has been extended to handling utility queries in [START_REF] Delanaux | Query-Based Linked Data Anonymization[END_REF][START_REF] Delanaux | RDF graph anonymization robust to data linkage[END_REF]. These approaches however are restricted to privacy and utility policies that are simple conjunctive queries.

Conclusion and future work

In this paper we have proposed a query-based declarative framework for a formal specification and verification of privacy and utility policies expressed as temporal aggregate conjunctive queries.

We do think that this framework is well suited for guaranteeing data producers to keep the control and protect their data in many real-world situations where sensitive data are collected by mobile personal devices or smart environments.

Based on the implementation of this framework, we plan to design and implement a negotiation mechanism that will be triggered when a utility policy turns out to be incompatible with a privacy policy. New relaxed utility queries will be automatically computed to restore compatibility with the privacy policy of a given data producer. They will be the formal basis of a dialogue between each data producer and the service provider in order to find a trade-off acceptable in terms of utility while guaranteeing privacy preservation for each data producer.

We also plan to extend our framework to take into account ontological knowledge in the possible inference of answers of privacy queries by answers of utility queries. This will bring stronger constraints on compatibility between privacy and utility policies.

  40, 2021 -04 -04𝑇 15 : 30 : 00) (𝑑𝑝 1 𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 20, 2021 -04 -04𝑇 16 : 00 : 00) (𝑑𝑝 1 𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 30, 2021 -04 -04𝑇 16 : 30 : 00) (𝑑𝑝 1 𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 10, 2021 -04 -04𝑇 17 : 00 : 00) Definition 2 (Temporal graph pattern). A Temporal graph pattern is a finite set of temporal triple patterns, where a temporal triple pattern is a pair (𝑠 𝑝 𝑜, ?𝑡𝑠) such that 𝑠 𝑝 𝑜 ∈ (𝐼 ∪ 𝐵 ∪ 𝑉 𝑎𝑟 ) × (𝐼 ∪ 𝑉 𝑎𝑟 ) × (𝐼 ∪ 𝐿 ∪ 𝐵 ∪ 𝑉 𝑎𝑟 ). Variables ?𝑡𝑠 are called timestamp variables. For a temporal graph pattern 𝐺𝑃, we will denote 𝑉 𝑎𝑟 (𝐺𝑃) the set of all variables occurring in 𝐺𝑃, including ?𝑡𝑖𝑚𝑒𝑊 𝑖𝑛𝑑𝑜𝑤𝐸𝑛𝑑. Definition 3 (Graph homomorphisms). Let 𝐻 and 𝐻 ′ be temporal RDF graphs or temporal graph patterns. An homomorphism from 𝐻 ′ to 𝐻 is an application ℎ : (𝐼 ∪ 𝐿 ∪ 𝐵 ∪ 𝑉 𝑎𝑟 ) → (𝐼 ∪ 𝐿 ∪ 𝐵 ∪ 𝑉 𝑎𝑟 ) such that h(c) = c for 𝑐 ∈ 𝐿 ∪ 𝐼 and ℎ(𝐻 ′ ) ⊆ 𝐻 where: ℎ((𝑠 𝑝 𝑜, 𝑡)) = (ℎ(𝑠) ℎ(𝑝) ℎ(𝑜), ℎ(𝑡))

  Definition 4 (Unifiable graph patterns). Let 𝐺𝑃 1 and 𝐺𝑃 2 two temporal graph patterns. 𝐺𝑃 1 and 𝐺𝑃 2 are unifiable if there exists a function 𝑠 replacing variables from 𝐺𝑃 1 and 𝐺𝑃 2 by constants or by variables of 𝐺𝑃 1 , such that 𝑠 (𝐺𝑃 1 ) = 𝑠 (𝐺𝑃 2 ). Definition 5 (Overlapping graph patterns). Let 𝐺𝑃 1 and 𝐺𝑃 2 two temporal graph patterns. 𝐺𝑃 1 and 𝐺𝑃 2 are overlapping if they contain subgraphs that are unifiable. Definition 6 (Disjoint graph patterns). Let 𝐺𝑃 1 and 𝐺𝑃 2 two temporal graph patterns. 𝐺𝑃 1 and 𝐺𝑃 2 are disjoint if they are not overlapping. Definition 7 (Isomorphic graph patterns). Let 𝐺𝑃 1 and 𝐺𝑃 2 two temporal graph patterns. 𝐺𝑃 1 and 𝐺𝑃 2 are isomorphic if there is a homomorphism h from 𝐺𝑃 1 to 𝐺𝑃

	Example 2. The two following listings show two overlapping
	temporal graph patterns, where the unifiable subgraphs are
	indicated in bold.
	Temporal graph pattern 𝐺𝑃 1
	(?dp address ?a, ?ts)
	(?a city ?city, ?ts)
	(?𝑎 𝑠𝑡𝑟𝑒𝑒𝑡 ?𝑠𝑡𝑟𝑒𝑒𝑡, ?𝑡𝑠)
	Temporal graph pattern 𝐺𝑃 2

(?𝑑𝑝 𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛 ?𝑐𝑜𝑛𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛, ?𝑡𝑠) (?dp address ?a, ?ts) (?a city "Grenoble", ?ts)

  [START_REF] Baader | Preliminary Results on the Identity Problem in Description Logic Ontologies[END_REF]

•

  𝐺𝑃 is a temporal graph pattern, • 𝐹 𝐼𝐿𝑇 𝐸𝑅 is a boolean combination of atomic comparisons of the form 𝑡 > 𝑡 ′ or 𝑡 ≥ 𝑡 ′ where 𝑡 and 𝑡 ′ are variables of 𝑉 𝑎𝑟 (𝐺𝑃) or literals (numbers, strings or dates), • x is a tuple of variables called the output (or grouping) variables, • when the aggregate term 𝑎𝑔𝑔(𝑦) is present, 𝑦 (called the aggregate variable) is not in x and 𝑎𝑔𝑔 is an aggregate function that produces a single value when applied to a set of values assigned to 𝑦. • 𝑆𝑖𝑧𝑒 and 𝑆𝑡𝑒𝑝 are time durations (i.e. differences between timestamps),

	Definition 8 (Temporal aggregated conjunctive query). A
	𝑇 𝐴𝐶𝑄 is defined as
	SELECT x, 𝑎𝑔𝑔(𝑦)
	WHERE {𝐺𝑃 . 𝐹 𝐼𝐿𝑇 𝐸𝑅}
	GROUP BY	x
	TIMEWINDOW (𝑆𝑖𝑧𝑒, 𝑆𝑡𝑒𝑝)
	where

  Definition 19. A query 𝑄 ′ is a variant of 𝑄 if the two queries differ only on their FILTER part and FILTER 𝑄 ∧ FILTER 𝑄 ′ is satisfiable.Definition 20 (Weak incompatibility between privacy and utility). A privacy query 𝑄 𝑝 is weakly incompatible with a set of utility queries if 𝑄 𝑝 is incompatible with some variants of the utility queries.

	Example 6. 𝑄 ′ 𝑢 is a variant of 𝑄 𝑢 where 𝑄 ′ 𝑢 is:
	SELECT ?x WHERE {?x p ?y . FILTER (?y > 2)}
	and 𝑄 𝑢 is:
	SELECT ?x WHERE {?x p ?y . FILTER (?y < 4)}

Continuing Example 6, let us consider the privacy query 𝑄 𝑝 :

SELECT ?x WHERE {?x p ?y. FILTER (?y > 2 )} 𝑄 𝑝 is weakly incompatible with a utility policy made of the single utility query 𝑄 𝑢 :

  The conjunctive part of 𝑄, noted 𝐶𝑜𝑛 𝑗 (𝑄) is the plain conjunctive query defined as follows:𝐶𝑜𝑛 𝑗 (𝑄) : SELECT x WHERE {𝐺𝑃} 4.1 Case of plain conjunctive queries Theorem 4.1 is a characterization of incompatibility of a privacy query 𝑄 𝑝 and a set of 𝑛 utility queries 𝑄 𝑢 1 , ..., 𝑄 𝑢 𝑛 when all the queries are plain conjunctive queries. We will use the following notations for the different query expressions: Privacy query 𝑄 𝑝 : SELECT x𝑝 WHERE {𝐺𝑃 𝑝 } Utility query 𝑄 𝑢 𝑖 : SELECT x𝑢 𝑖 WHERE {𝐺𝑃 𝑢 𝑖 } Theorem 4.1 relies on the evaluation of the privacy query over the union of partially instantiated graph patterns obtained by freezing the output variables in the graph patterns of the utility queries. Definition 22 (Frozen graph patterns). Let 𝐺𝑃 a temporal graph pattern and 𝑋 a subset of variables occurring in it. A freezing of 𝑋 in 𝐺𝑃, denoted Frozen(GP,X), is the graph pattern obtained from 𝐺𝑃 by replacing each occurrence of 𝑥 ∈ 𝑋 by a constant. Theorem 4.1 (Incompatibility of conjunctive queries). The privacy query 𝑄 𝑝 is incompatible with the set of utility queries if and only if 𝐴𝑛𝑠 (𝑄 𝑝 , 𝐹𝑟𝑜𝑧𝑒𝑛) ≠ ∅ where 𝐹𝑟𝑜𝑧𝑒𝑛 is a freezing in 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 of the output variables of the utility queries.

	Definition 21 (Conjunctive part of a query). Let 𝑄 a TACQ
	of the form:
	SELECT x 𝑎𝑔𝑔(𝑦)
	WHERE {𝐺𝑃 . 𝐹 𝐼𝐿𝑇 𝐸𝑅}
	GROUP BY	x
	TIMEWINDOW (𝑆𝑖𝑧𝑒, 𝑆𝑡𝑒𝑝)

  . If the graph pattern 𝐺𝑃 𝑝 of 𝑄 𝑝 is disjoint with every graph pattern 𝐺𝑃 𝑢 𝑖 of the utility queries, based on Definition 6, there exists a triple pattern in 𝐺𝑃 𝑝 that cannot be projected by any homomorphism to the union of 𝐺𝑃 𝑢 𝑖 . Based on Definitions 17 and 16, this means that no answer of 𝑄 𝑝 can be inferred from answers to 𝑄 𝑢 𝑖 . 𝑟 from logical signatures of answers to 𝑄 𝑢 𝑖 . □ 4.2 Case of conjunctive queries with FILTER conditions We will use the following notations: Privacy query 𝑄 𝑝 : SELECT x𝑝 WHERE {𝐺𝑃 𝑝 . 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 } Utility query 𝑄 𝑢 𝑖 : SELECT x𝑢 𝑖 WHERE {𝐺𝑃 𝑢 𝑖 . 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 } Theorem 4.4 is based on extending the proof of Theorem 4.1 by the verification of the entailment of the FILTER conditions of 𝑄 𝑝 by the FILTER conditions of utility queries. When their conjunction is just satisfiable, we obtain a characterization of weak compatibility in Theorem 4.5. Note that, by definition, weak incompatibility and compatibility does not differ for the cases of queries without FILTER conditions. Theorem 4.4 (Incompatibility of conjunctive queries with FILTER). The privacy query 𝑄 𝑝 is incompatible with the set of utility queries if and only if there exists a 𝑓 𝑟𝑒𝑒𝑧𝑒 of the output variables in 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 , and an answer c of the conjunctive part of 𝑄 𝑝 over 𝐹𝑟𝑜𝑧𝑒𝑛 = 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 ) with an homomorphism support ℎ such that: 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) |= ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )

	𝑓 𝑟𝑒𝑒𝑧𝑒 (
	𝑖 ∈ [1..𝑛]

□

Theorem 4.3 (Sufficient condition of compatibility for general TACQs). If the conjunctive part of a privacy query 𝑄 𝑝 is compatible with the conjunctive parts of the utility queries then 𝑄 𝑝 is compatible with the utility queries.

Proof. If 𝐶𝑜𝑛 𝑗 (𝑄 𝑝 ) is compatible with 𝐶𝑜𝑛 𝑗 (𝑄 𝑢 1 ), ..., 𝐶𝑜𝑛 𝑗 (𝑄 𝑢 𝑛 ), this means that no answer ā to 𝐶𝑜𝑛 𝑗 (𝑄 𝑝 ) can be inferred from answers to 𝐶𝑜𝑛 𝑗 (𝑄 𝑢 𝑖 ). Any answer ( ā, 𝑟 ) to 𝑄 𝑝 is such that ā is an answer to 𝐶𝑜𝑛 𝑗 (𝑄 𝑝 ) and 𝑟 is the result of an aggregate function. If there is no way to infer the logical signature of ā from the logical signatures of answers to 𝐶𝑜𝑛 𝑗 (𝑄 𝑢 𝑖 ), a fortiori there will be no way to infer a more constrained logical signature of the form: (∃𝑦 ∃z, 𝜇 ā (𝐺𝑃 𝑝 ) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )) ∧ 𝑎𝑔𝑔{𝑦|∃z, 𝜇 ā (𝐺𝑃 ) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )} =

  5 (Weak incompatibility of conjunctive queries with FILTER). The privacy query 𝑄 𝑝 is weakly incompatible with the set of utility queries if and only if there exists a freezing 𝑓 𝑟𝑒𝑒𝑧𝑒 of the output variables in 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 , and an answer c of the conjunctive part of 𝑄 𝑝 over 𝐹𝑟𝑜𝑧𝑒𝑛 = 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 ) with an homomorphism support ℎ such that: 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) ∧ ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) is satisfiable. Proof. If 𝑄 𝑝 is weakly incompatible with the set of utility queries, 𝑄 𝑝 is incompatible with a set of variants 𝑄 ′ 𝑢 𝑖 of the utility queries 𝑄 𝑢 𝑖 . By applying Theorem 4.4, there exists a freezing 𝑓 𝑟𝑒𝑒𝑧𝑒 of the output variables in 𝑖 ∈ [1..𝑛] 𝐺𝑃 ′ 𝑢 𝑖 , and an answer c of the conjunctive part of 𝑄 𝑝 over 𝐹𝑟𝑜𝑧𝑒𝑛 = 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐺𝑃 ′ 𝑢 𝑖 ) with an homomorphism support ℎ such that: 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 ′ 𝑢 𝑖 ) |= ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) This means that every variable assignment satisfying 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 ′ 𝑢 𝑖 ) satisfies ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) too. By definition of the variants, there exists a variable assignment satisfying both 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 ′ 𝑢 𝑖 ) and 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ). This assignment satisfies ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) too. Thus 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) ∧ ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) is satisfiable. For the converse way, let us suppose that there exists a freezing 𝑓 𝑟𝑒𝑒𝑧𝑒 of the output variables in 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 , and an answer c of the conjunctive part of 𝑄 𝑝 over 𝐹𝑟𝑜𝑧𝑒𝑛 = 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐺𝑃 𝑢 𝑖 ) with an homomorphism support ℎ such that: 𝑓 𝑟𝑒𝑒𝑧𝑒 ( 𝑖 ∈ [1..𝑛] 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 ) ∧ ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) is satisfiable. The goal is to build variants 𝑄 ′ 𝑢 𝑖 of utility queries by adding to the FILTER constraints 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 some constraints making ℎ(𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) true.

  𝑢 𝑗 the atomic constraint obtained by defreezing the constants possibly involved in 𝑡 𝑗 𝑐𝑜𝑚𝑝 𝑡 𝑗+1 . □ Theorem 4.6 (Sufficient condition of compatibility for conjunctive queries with FILTER). A privacy query 𝑄 𝑝 is compatible with utility queries if for each utility query 𝑄 𝑢 with a graph pattern 𝐺𝑃 𝑢 overlapping with 𝐺𝑃 𝑝 through an unifier 𝑜𝑣𝑒𝑟𝑙𝑎𝑝: 𝑜𝑣𝑒𝑟𝑙𝑎𝑝 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) ∧ 𝑜𝑣𝑒𝑟𝑙𝑎𝑝 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 ) is unsatisfiable. Proof. If 𝑄 𝑝 is incompatible with the utility queries, it means by definition that there exists tuples of constants ā, ā𝑖 1 , ..., ā𝑖 𝑘 such that : ∃z 1 ... ∃z 𝑘 𝜇 ā𝑖 1 (𝐺𝑃 𝑢 𝑖 1 ) ∧ 𝜇 ā𝑖 1 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 1 )...𝜇 ā𝑖 𝑘 (𝐺𝑃 𝑢 𝑖 𝑘 ) ∧ 𝜇 ā𝑖 𝑘 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 𝑘 ) |= ∃z 𝜇 ā (𝐺𝑃 𝑝 ) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ) where 𝐺𝑃 𝑢 𝑖 𝑗 are the graph patterns of utility queries overlapping with the graph pattern 𝐺𝑃 𝑝 of 𝑄 𝑝 . Thus, there exists an homomorphism ℎ from 𝜇 ā (𝐺𝑃 𝑝 ) to 𝜇 ā𝑖 1 (𝐺𝑃 𝑢 𝑖 1 ) ∧ ... ∧ 𝜇 ā𝑖 𝑘 (𝐺𝑃 𝑢 𝑖 𝑘 ) such that every model satisfying ℎ(𝜇 ā𝑖 1 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢𝑖 1 )) ∧ ...ℎ(𝜇 ā𝑖 𝑘 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 𝑘 )), and in particular each 𝑜𝑣𝑒𝑟𝑙𝑎𝑝(ℎ(𝜇 ā𝑖 1 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 𝑖 𝑗 ))), also satisfies 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 ), and in particular 𝑜𝑣𝑒𝑟𝑙𝑎𝑝 (𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )), which contradicts the if condition of the theorem. □ Example 9. Let us consider the following privacy and utility queries, which are obtained by modifying the FILTER conditions to the queries in Example 9.

	𝑄𝐹 ′ 𝑝 : SELECT ?x WHERE ?x p ?y . ?y q ?z .
	FILTER ( ?y < 6 ∧ ?z > 3)
	𝑄𝐹 ′ 𝑢 1 : SELECT ?x1 ?y1 WHERE ?x1 p ?y1? . ?y1 r ?z1.
	FILTER ( ?y1 > 8)
	𝑄𝐹 ′ 𝑢 2 : SELECT ?x2 WHERE ?x2 q ?y2. FILTER (?y2 < 2)
	An overlapping of 𝑄𝐹 ′ 𝑝 with the graph pattern of 𝑄𝐹 ′ 𝑢 1 is
	based on unifying the triple patterns ?x p ?y and ?x1 p ?y1?
	with the unifier 𝑜𝑣𝑒𝑟𝑙𝑎𝑝(?x1) = ?x and 𝑜𝑣𝑒𝑟𝑙𝑎𝑝(?y1) = ?y
	𝑜𝑣𝑒𝑟𝑙𝑎𝑝(?y < 6 ∧ ?z > 3) ∧ 𝑜𝑣𝑒𝑟𝑙𝑎𝑝(?y1 >8)
	= ?y < 6 ∧ ?z > 3 ∧ ?y > 8
	which is unsatisfiable.
	Similarly, the overlap of 𝑄𝐹 ′ 𝑝 with the graph pattern of
	𝑄𝐹 ′
	Theorem 4.6 is the counterpart of Theorem 4.2 for con-
	junctive queries with FILTER conditions.

  will use the following notations: Privacy query 𝑄 𝑝 : SELECT x𝑝 WHERE {𝐺𝑃 𝑝 . 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 } GROUP BY x𝑝 TIMEWINDOW (𝑆𝑖𝑧𝑒 𝑝 , 𝑆𝑡𝑒𝑝 𝑝 ) Utility query 𝑄 𝑢 : SELECT x𝑢 WHERE {𝐺𝑃 𝑢 . 𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 } GROUP BY x𝑢 TIMEWINDOW (𝑆𝑖𝑧𝑒 𝑢 , 𝑆𝑡𝑒𝑝 𝑢 ) By definition, the answer set of a query 𝑄 𝑤𝑖𝑛𝑑𝑜𝑤 : SELECT x WHERE {𝐺𝑃. 𝐹 𝐼𝐿𝑇 𝐸𝑅} GROUP BY x TIMEWINDOW (𝑆𝑖𝑧𝑒, 𝑆𝑡𝑒𝑝) is the union of the answer sets resulting of the evaluation over each time window of 𝑄 𝑤𝑖𝑛𝑑𝑜𝑤 of the query 𝑄: SELECT x WHERE {𝐺𝑃. 𝐹 𝐼𝐿𝑇 𝐸𝑅} GROUP BY x Thus, in this section, we focus on studying the compatibility between 𝑄 𝑝 and 𝑄 𝑢 evaluated on a common time window, e.g., the first time windows of 𝑄 𝑝 and 𝑄 𝑢 (𝑘 𝑢 = 𝑘 𝑝 = 0) when 𝑆𝑖𝑧𝑒 𝑢 = 𝑆𝑖𝑧𝑒 𝑝 . Theorem 4.7 provides conditions for incompatibility of utility and privacy queries with aggregates. Theorem 4.7 (Incompatibility conditions for aggregate queries). A privacy query 𝑄 𝑝 is incompatible with the utility query 𝑄 𝑢 if there exists a (possibly empty) freezing 𝑓 𝑝 of output variables in 𝐺𝑃 𝑝 with constants of 𝐺𝑃 𝑢 , or a (possibly empty) freezing 𝑓 𝑢 of output variables in 𝐺𝑃 𝑢 with constants in 𝐺𝑃 𝑝 such that 𝑓 𝑝 (𝐺𝑃 𝑝 ) and 𝑓 𝑢 (𝐺𝑃 𝑢 ) are isomorphic. When 𝑄 𝑝 and 𝑄 𝑢 have no FILTER conditions and the same aggregate functions, they are incompatible if and only if the above condition is satisfied. Proof. Based on Definition 16, an answer ( ā, 𝑟 ) of an aggregate query 𝑄 𝑝 can be inferred from a set of answers {( ā𝑢 , 𝑟 𝑢 )} only if the group 𝐺𝑟𝑜𝑢𝑝 𝑝 ( ā) = {𝑦 𝑝 |∃z, 𝜇 ā (𝐺𝑃 𝑝 ) ∧ 𝜇 ā (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑝 )} can be obtained as a group, or the union of groups, of 𝑄 𝑢 , i.e., unions of {𝑦 𝑢 |∃z 𝑢 , 𝜇 ā𝑢 (𝐺𝑃 𝑢 )∧𝜇 ā𝑢 (𝐹 𝐼𝐿𝑇 𝐸𝑅 𝑢 )}.Based on[START_REF] Cohen | Containment of aggregate queries[END_REF], this situation is true only if (if and only if, when there is no FILTER conditions) either 𝜇 ā (𝐺𝑃 𝑝 ) and (𝐺𝑃 𝑢 ) are isomorphic, or if there exists an answer ā𝑢 of 𝐺𝑃 𝑢 such that 𝜇 ā (𝐺𝑃 𝑝 ) and 𝜇 ā𝑢 (𝐺𝑃 𝑢 ) are isomorphic, i.e, 𝐺𝑃 𝑝 (or one of its freezing of output variables by constants in 𝐺𝑃 𝑢 ) is isomorphic to 𝐺𝑃 𝑢 (or to one of its freezing of output variables by constants in 𝐺𝑃 𝑝 ). □

	Example 10. Let us consider the following privacy and utility
	queries:
	𝑄 𝑝 :
	SELECT ?city AVG(?s)
	WHERE {?dp city ?city . ?dp street ?street . ?dp familySize ?s}
	GROUP BY ?city
	𝑄

𝑢 : SELECT ?street', AVG(?s') WHERE {?dp' city "Grenoble" . ?dp' street ?street' .

Acknowledgments

This work has been partially supported by MIAI@Grenoble Alpes (ANR-19-P3IA-0003), PERSYVAL-Lab (ANR-11-LABX-0025-01) and TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.

GROUP BY ?city

𝑄 ′

𝑝 is also incompatible with 𝑄 𝑢 since freezing the variable ?street' of 𝑄 𝑢 with "Alsace Lorraine" and the variable ?city of 𝑄 𝑝 with "Grenoble" makes the resulting graph patterns isomorphic, and the group 𝐺𝑟𝑜𝑢𝑝 ("𝐺𝑟𝑒𝑛𝑜𝑏𝑙𝑒") of 𝑄 ′ 𝑝 can be obtained as the group 𝐺𝑟𝑜𝑢𝑝 ("𝐴𝑙𝑠𝑎𝑐𝑒 𝐿𝑜𝑟𝑟𝑎𝑖𝑛𝑒") of 𝑄 𝑢 .

Case of aggregate with different time windows

In the general case of TACQ with explicit TIMEWINDOW clause, a privacy query 𝑄 𝑝 and a utility query 𝑄 𝑢 are compatible if no time window of 𝑄 𝑝 can be built by unions and/or differences of time windows of one or more 𝑄 𝑢 . A sufficient condition is that for any 𝑄 𝑢 no boundary of a time window of 𝑄 𝑢 should correspond to a boundary of a time window of 𝑄 𝑝 , except of course the first one (i.e. 𝑘 𝑢 = 𝑘 𝑝 = 0) where the ends of time windows is 𝑛𝑜𝑤. Theorem 4.8 (Sufficient condition of compatibility). A privacy query 𝑄 𝑝 is compatible with a set of utility queries if there is no utility query 𝑄 𝑢 such that:

In the first case, assuming that 𝑇 𝑢 1 starts before 𝑇 𝑢 2 then 𝑇 𝑢 1 has to start at the same time than 𝑇 𝑝 and 𝑇 𝑢 2 has to end at the same time than 𝑇 𝑝 . If there is no WHERE {((?dp' consumption ?cons'), ?ts')} GROUP BY ?timeWindowEnd TIMEWINDOW (1h, 8h) We have 0 × 𝑆𝑡𝑒𝑝 𝑢 1 -𝑆𝑖𝑧𝑒 𝑢 1 = 1 × 𝑆𝑡𝑒𝑝 𝑝 -𝑆𝑖𝑧𝑒 𝑝 meaning that the first interval 𝐼 𝑢 1 (𝑘 𝑢 1 = 0) of 𝑄 𝑢 1 starts at the same time than the second interval 𝐼 𝑝 (𝑘 𝑝 = 1) of 𝑇 𝐴𝐶𝑄 2 at now -7ℎ.

We have also 0 × 𝑆𝑡𝑒𝑝 𝑢 2 -𝑆𝑖𝑧𝑒 𝑢 2 = 1 × 𝑆𝑡𝑒𝑝 𝑝 meaning that the first interval 𝐼 𝑢 2 (𝑘 𝑢 2 = 0) of 𝑄 𝑢 2 starts at the end of the second interval 𝐼 𝑝 (𝑘 𝑝 = 1) of 𝑇 𝐴𝐶𝑄 2 at now -1ℎ. This example does not satisfy the sufficient condition of Theorem 4.8 for both 𝑄 𝑢 1 and 𝑄 𝑢 2 . In fact, as 𝐼 𝑝 (𝐾 𝑝 = 1) = 𝐼 𝑢 1 (𝑘 𝑢 1 = 0) -𝐼 𝑢 2 (𝑘 𝑢 2 = 0), the sum of consumption of 𝑇 𝐴𝐶𝑄 2 for its second interval can be computed in the following way:

Related work

Privacy preserving data publishing has been a long-standing research goal for several research communities, as witnessed by a flurry of work on the topic [START_REF] Benjamin | Privacy-preserving data publishing: A survey of recent developments[END_REF]. A rich variety of privacy models have been proposed, ranging from 𝑘-anonymity [START_REF] Sweeney | k-Anonymity: A Model for Protecting Privacy[END_REF] and 𝑙-diversity [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF] to 𝑡-closeness [START_REF] Li | t-Closeness: Privacy Beyond k-Anonymity and l-Diversity[END_REF] and 𝜖-differential privacy [START_REF] Dwork | Differential Privacy[END_REF]. Compared to our work, all these approaches are based on changing the exposed data either by adding noise in the data or by applying generalization operations on sensitive data.