--- title: "Reasoning about Disclosure in Data Integration in the Presence of Source Constraints" authors: - "Michael Benedikt" - "Pierre Bourhis" - "Louis Jachiet" - "Michaël Thomazo" doi: "10.24963/ijcai.2019/215" url: "https://ijcai.org/proceedings/2019/215" pdf: "https://ijcai.org/proceedings/2019/0215.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "1551-1557" track: "Main track" keywords: - "Knowledge Representation and Reasoning: Computational Complexity of Reasoning" - "Knowledge Representation and Reasoning: Description Logics and Ontologies" --- # Reasoning about Disclosure in Data Integration in the Presence of Source Constraints Michael Benedikt, Pierre Bourhis, Louis Jachiet, Michaël Thomazo *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 1551-1557. DOI: [10.24963/ijcai.2019/215](https://doi.org/10.24963/ijcai.2019/215) ## Abstract Data integration systems allow users to access data sitting in multiple sources by means of queries over a global schema, related to the sources via mappings. Datasources often contain sensitive information, and thus an analysis is needed to verify that a schema satisfies a privacy policy, given as a set of queries whose answers should not be accessible to users. Such an analysis should take into account not only knowledge that an attacker may have about the mappings, but also what they may know about the semantics of the sources.In this paper, we show that source constraints can have a dramatic impact on disclosure analysis. We study the problem of determining whether a given data integration system discloses a source query to an attacker in the presence of constraints, providing both lower and upper bounds on source-aware disclosure analysis. ## Full text ## 1 Introduction In data integration, users are shielded from the heterogeneity of multiple datasources by querying via a global schema, which provides a unified vocabulary. The relationship between sources and the user-facing schema are specified declaratively via mapping rules. In data integration systems based on knowledge representation techniques, users pose queries against the global schema, and these queries are answered using data in the sources and background knowledge. The computation of the answers involves reasoning based on the query, the mappings, and any additional semantic information that is known on the global schema. Data integration brings with it the danger of disclosing information that data owners wish to keep confidential. In declarative data integration, detection of privacy violations is complex: although explicit access to source information may be masked by the global schema, an attacker can infer source facts via reasoning with schema and mapping information. Example 1. We consider an information integration setting for a hospital, which internally stores the following data: | Predicate | Meaning | |-----------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | IsOpen(b, t) PatBdlg(p, b) PatSpec(p, s) PatDoc(p, d) DocBldg(d, b) DocSpec(d, s) | building b is open on date t patient p is present in building b patient p was treated for specialty s patient p was treated by doctor d doctor d is associated with building b doctor d is associated with specialty s | The hospital publishes the following data: OpenHours(b, t) giving opening times t for building b, VisitingHours(p, t) giving times t when a given patient p can be visited, and DocList(d, s, b) listing the doctors d with their specialty s and their building b. Formally the data being exposed is given by the following mappings: Prior work [Benedikt et al., 2018] has studied disclosure in knowledge-based data integration, with an emphasis on the role of semantic information on the global schema - in the form of ontological rules that relate the global schema vocabulary. The presence of an ontology can assist in privacy, since distinctions in the source data may become indistinguishable in the ontology. More dangerous from the point of view of protecting information is semantic information about sources. For example, the sources in a data integration setting will generally overlap: that is, they will satisfy referential integrity constraints, saying that data items in one source link to items in another source. Such constraints should be assumed as public knowledge, and with that knowledge the attacker may be able to infer information that was intended to be secret. Example 2. Continuing Example 1, suppose that we know that each patient has a doctor specialized in their condition, which can be formalized as: And that we also know that when a patient is in a building, they must have a doctor there: Due to the presence of these constraints, there can be a disclosure of the relationship of patient to speciality PatSpec(p, s). Indeed, an attacker can see the VisitingHours for p, and from this, along with OpenHours, they can sometimes infer the building b where p has visited (e.g. if b has a unique set of open hours). From this they may be able to infer, using DocList, the specialty that p has been treated for - for example, if all the doctors in b share a specialty. In this work, we perform a detailed examination of the role of source constraints in disclosing information in the context of data integration. We focus on mappings from the sources given by universal Horn rules, where the global schema comes with no constraints. Since our disclosure problem requires reasoning over all sources satisfying the constraints, we need a constraint formalism that admits effective reasoning. We will look at a variety of well-studied rule-based formalisms, with the simplest being referential constraints, and the most complex being the frontier-guarded rules [Baget et al., 2011]. While decidability of our disclosure problems will follow from prior work [Benedikt et al., 2016], we will need new tools to analyze the complexity of the problem. In Section 3, we give reductions of disclosure problems to the query entailment problem that is heavily-studied in knowledge representation. While a na¨ıve application of the reduction allows us only to conclude very pessimistic bounds, a more fine-grained analysis, combined with some recent results on CQ entailment, will allow us to get much better bounds, in some cases ensuring tractability. In Section 4, we complement these results with lower bounds. Both the upper and lower bounds revolve around a complexity analysis for reasoning with guarded existential rules and a restricted class of equality rules, where the rule head compares a variable and a distinguished constant. We believe this exploration of limited equality rules can be productive for other reasoning problems. Overall we get a complete picture of the complexity of disclosure in the presence of source constraints for many natural classes: see Tables 1 in Section 6 for a summary of our bounds. Full proofs are available at the address https: //hal.inria.fr/hal-02145369. ## 2 Preliminaries We adopt standard notions from function-free first-order logic over a vocabulary of relational names. An instance is a finite set of facts. By a query we always mean a conjunctive query (CQ), which is a first-order formula of the form ∃⃗x ∧ Ai, where each Ai is an atom. The arity of a CQ is the number of its free variables, and CQs of arity 0 are Boolean. Data integration. Assume that the relational names in the vocabulary are split into two disjoint subsets: source and global schema. The arity of such a schema is the maximal arity of its relational names. We consider a set Mof mapping rules between source relations and a global schema relation T given. We focus on rules φ(⃗x, ⃗y) → T (⃗x) where φ is a conjunctive query, there are no repeated variables in T (⃗x), and where each global schema relation T is associated with exactly one rule. Such rules are sometimes called "GAV mappings" in the database literature [Lenzerini, 2002], and the unique φ associated to a global relation T is referred to as the definition of T . The rules are guarded (M ∈ GuardedMap) if for every rule, there exists an atom in the antecedent φ that contains all the variables of φ. The rules are atomic (M ∈ AtomMap) if each φ consists of a single atom, and they are projection maps (M ∈ ProjMap) if each φ is a single atom with no repeated variables. Given an instance D for the source relations, the image of D under mapping M, denotedM(D), is the instance for the global schema consisting of all facts {T (⃗c) | D |= ∃⃗y φ(⃗c)}, where φ is the definition of T . Source constraints. We consider restrictions on the sources in the form of rules. A tuple-generating dependency (TGD) is a universally quantified sentence of the form ϕ(x, z) → ∃yψ(x, y), where the body ϕ(x, z) and the head ψ(x, y) are conjunctions of atoms such that each term is either a constant or a variable in x ∪ z and x ∪ y, respectively. Variables x, common to the head and body, are called the frontier variables. A frontier-guarded TGD (FGTGD) is a TGD in which there is an atom of the body that contains every frontier variable. We focus on FGTGDs because they have been heavily studied in the database and knowledge representation community, and it is known that many computational problems involving FGTGDs are decidable [Baget et al., 2011]. In particular this is true of the query entailment problem, which asks, given a finite collection of facts F, a finite set Σ of sentences, and a CQ Q, whether F ∧ Σ entails Q. We use QEntail(F,Σ,Q) to denote an instance of this problem and also say that "F entails Q w.r.t. constraints Σ". A special case of FGTGDs are Guarded TGDs (GTGDs), in which there is an atom containing all body variables. These specialize further to linear TGDs (LTGDs), whose body consists of a single atom; and even further to inclusion dependencies (IncDeps), a linear TGD with a single atom in the head, in which no variable occurs multiple times in the body, and no variable occurs multiple times in the head. Even IncDeps occur quite commonly: for example, the source constraints of Example 2 can be rewritten as IncDeps. The most specialized class we study are the unary IncDeps:(UIDs), which are IncDeps with at most one frontier variable. Queries and disclosure. The sensitive information in a data integration setting is given by a CQ p over the source schema, which we refer to as the policy. Intuitively, disclosure of sensitive information occurs in a source instance D whenever the attacker can infer from the imageM(D) that p holds of a tuple in D. Formally, we say an instance V for the global schema is realizable, with respect to mappingsMand source constraints ΣSource if there is some source instance D that satisfies ΣSource such that M(D) = V. For a realizable V, the set of such D are the possible source instances for V. A query result p(⃗t) is disclosed at V if p(⃗t) holds on all possible source instances for V. A query p admits a disclosure (for mappingsMand source constraints ΣSource) if there is some realizable instance V and binding ⃗t for the free variables of p for which p(⃗t) is disclosed. In this terminology, the conclusion of Example 2 was that policy PatSpec(p, s) admits a disclosure with respect to the constraints and mappings. For a class of constraints C, a class of mappings Map, a class of policies Policy, we write DiscloseC(C,Map) to denote the problem of determining whether a policy (a CQ, unless otherwise stated) admits a disclosure for a set of mappings in Map and a set of source constraints in C. Given ΣSource,Mand a CQ p, the corresponding instance of this problem is denoted by Disclose(C,M, p). In this paper we will focus on disclosure for queries and constraints without constants, although our techniques extend to the setting with constants, as long as distinct constants are not assumed to be unequal. ## 3 Reducing Disclosure to Query Entailment Our first goal is to provide a reduction from DiscloseC(TGD,Map) to a finite collection of standard query entailment problems. For simplicity we will restrict to Boolean queries p in stating the results, but it is straightforward to extend the reductions and results to the non-Boolean case. We first recall a prior reduction of DiscloseC(TGD,Map) to a more complex problem, the hybrid open and closed world query answering problem [Lutz et al., 2013; Lutz et al., 2015; Franconi et al., 2011], denoted HOCWQ. HOCWQ takes as input a set of facts F, a collection of constraints Σ, a Boolean query Q, and additionally a subset C of the vocabulary. A possible world for such HOCWQ(F, Σ, Q, C) is any instance D containing F, satisfying Σ, and such that for each relation C ∈ C, the C-facts in D are the same as the C-facts in F. HOCWQ(F,Σ,Q, C) holds if Q holds in every possible world. Note that the query entailment problem is a special case of HOCWQ, where C is empty. Given a set of mapping rules M of the form φ(⃗y, ⃗x) → T (⃗x), we let G(M) be the set of global schema predicates, and let ΣM(M) be the mapping rules, considered as bidirectional constraints between global schema predicates and sources. We now recall one of the main results of [Benedikt et al., 2016]: Theorem 1. There is an instance D′ computable in linear time from ΣSource,M, p, such that Disclose(ΣSource,M, p) holds if and only if HOCWQ(D′ , ΣSource ∪ ΣM(M), p, G(M)) holds. In fact, the arguments in [Benedikt et al., 2016] show that D′ can be taken to be a very simple instance, the critical instance over the global schema G(M) denoted DG(M) Crit where DS Crit , for S a set of predicates, denotes the instance that mentions only a single element cCrit, and contains, for each relation R in S of arity n, the fact R(cCrit, . . . cCrit). Corollary 1. DiscloseC(FGTGD, CQMap) is in 2EXPTIME. Proof. The non-classical aspect of HOCWQ comes into play with rules of ΣM(M) of form φ(⃗x, ⃗y) → T (⃗x). But in the context of DG(M) Crit , these can be rewritten as single-constant equality rules (SCEQrules) φ(⃗x, ⃗y) → ∧i xi = cCrit. Such rules remain in the Guarded Negation Fragment of first-order logic, which also subsumes FGTGDs, while having a query entailment problem in 2EXPTIME [B´ar´any et al., 2015]. We now want to conduct a finer-grained analysis, looking for cases that give lower complexity. To do this we will transform further into a classical query entailment problem. This will require a transformation of our query p, a transformation of our source constraints and mappings into a new set of constraints, and a transformation of the instance DG(M) Crit . The idea of the transformation is that we remove the SCEQrules that are implicit in the HOCWQ problem, replacing themwith constraints and queries that reflect all the possible impacts the rules might have on identifying two variables. We first describe the transformation of the query and the constraints. They will involve introducing a new unary predicate IsCrit(x); informally this states that x is equal to cCrit. Consider a CQ Q = ∃⃗y ∧ Ai. An annotation of Q is a subset of Q's variables. Given an annotation Annot of Q, we let QAnnot be the query obtained from Q by performing the following operation for each v in Annot: for all occurrences j of v except the first one, replacing v with a fresh variable vj ; and adding conjuncts IsCrit(vj) as well as IsCrit(v) to QAnnot. A critical-instance rewriting of a CQ Q is a CQ obtained by applying the above process to Q for any annotation. We write QAnnot ∈ CritRewrite(Q) to indicate that QAnnot is such a rewriting. To transform the mapping rules and constraints to a new set of constraints using IsCrit(x), we lift the notion of criticalinstance rewriting to TGDs in the obvious way: a criticalinstance rewriting of a TGD σ (either in ΣSource or ΣM(M)), is the set of TGDs formed by applying the above process to the body of σ. We write σAnnot ∈ CritRewrite(Σ) to indicate that σAnnot is a critical-instance rewriting for a σ ∈ Σ, and similarly for mappings. For example, the second mapping rule in Example 1 has several rewritings; one of them will change the rule body to PatBdlg(p, b) ∧ IsOpen(b′ , d) ∧ IsCrit(b) ∧ IsCrit(b′ ). Our transformed constraints will additionally use the set of constraints IsCrit(M), including all rules: where T ranges over the global schema and 1 ≤ i ≤ n. Informally IsCrit(M) states that all elements in the mapping image must be cCrit. We also need to transform the instance, using a source instance with "witnesses for the target facts". Consider a fact T (cCrit . . . cCrit) in DG(M) Crit formed by applying a mapping rule ∧i Ai(⃗xi, ⃗yi) → T (⃗x) in M. The set of witness tuples for T (⃗x) is the set Ai(⃗c), where ⃗c contains cCrit in each position containing a variable xj and containing a constant cyj in every position containing a variable yj. That is the witness tuples are witnesses for the fact T (cCrit . . . cCrit), where each existential witness is chosen fresh. Let HideM(DG(M) Crit ) be the instance formed by taking the witness tuples for every fact T (cCrit . . . cCrit) ∈ DG(M) Crit . We are now ready to state the reduction of the disclosure problem to query entailment: Theorem 2. Disclose(ΣSource,M, p) holds exactly when there is a pAnnot ∈ CritRewrite(p) such that HideM(DG(M) Crit ) entails pAnnot w.r.t. constraints: Note that Theorem 2 does not give a polynomial time reduction: both CritRewrite(ΣSource) and CritRewrite(M) can contain exponentially many rewritings, and further there can be exponentially many rewritings in CritRewrite(p). However, the algorithm does give us a better bound in the case of Guarded TGDs with bounded arity. Corollary 2. If we bound the arity of schema relations, then DiscloseC(GTGD, GuardedMap) is in EXPTIME. Proof. First, by introducing additional intermediate relations and source constraints, we can assume that M contains only projection mappings. Thus we can guarantee that CritRewrite(M) just contains the rules in M. By introducing intermediate relations and additional source constraints, we can also assume that each GTGD ∈ ΣSource has a body with at most two atoms. Since the arity of relations is fixed, the size of such 1- or 2-atom bodies is fixed as well. From this we see that the number of constraints in any CritRewrite(σ) is polynomial. The reduction in Theorem 2 thus gives us exponentially many GTGD entailment problems of polynomial size. Since entailment over Guarded TGDs with bounded arity is in EXPTIME [Cal`ı et al., 2013], we can conclude. ## 3.1 Refinements of the Teduction to Identify Lower Complexity Cases In order to lower the complexity to EXPTIME without bounding the arity, we refine the construction of the function CritRewrite(σ) in the case where σ is a linear TGD, providing a function CritRewritePTIME(σ) that constructs only polynomially many rewritten constraints. Let σ = B(⃗x) → ∃⃗y H(⃗z) be a linear TGD with relation B of arity k, and suppose ⃗x contains d distinct free variables V = {v1 . . . vd}. Let P be the set of pairs (e, f) with e < f ≤ k such that the same variable vi sits at positions e and f in ⃗x. We order P as (e0, f0) . . . (eh, fh); for each (e, f) that is not the initial pair (e0, f0), we let (e, f)- be its predecessor in the linear order. We let Be,f denote new predicates of arity k for each (e, f) ∈ P. Let ⃗w be a set of k distinct variables, and ⃗wi=j be formed from ⃗w by replacing wj with wi. We begin the construction of CritRewritePTIME(σ) with the constraints: B(⃗we0=f0 ) → Be0,f0 (⃗we0=f0 ) and B(⃗w) ∧ IsCrit(we0 ) ∧ IsCrit(wf0 ) → Be0,f0 ( ⃗w). For each (e, f) with a predecessor (e, f)- = (e′ , f ′ ), we add to CritRewritePTIME(σ) the following constraints: Be′ ,f ′ ( ⃗we=f ) → Be,f ( ⃗we=f ) and Be′ ,f ′ ( ⃗w) ∧ IsCrit(we) ∧ IsCrit(wf ) → Be,f ( ⃗w). Letting eh, fh the final pair in P, we add to CritRewritePTIME(σ) the constraint Beh,fh (⃗x′ ) → ∃⃗y H(⃗z) where ⃗x′ is obtained from ⃗x by replacing all but the first occurrence of each variable v by a fresh variable. If ΣSource consists of LTGDs, we let CritRewritePTIME(ΣSource) be the result of applying this process to every σ ∈ ΣSource. Similarly, if M consists of atomic mappings (implying that the associated rules are LTGDs), then we let CritRewritePTIME(M) the result of applying the process above to the rule going from source relation to global schema relation associated to m ∈ M. Then we have: Theorem 3. When ΣSource consists of LTGDs, Disclose(ΣSource,M, p) holds exactly when there is a pAnnot ∈ CritRewrite(p) such that HideM(DG(M) Crit ) entails pAnnot w.r.t. to the constraints CritRewritePTIME(ΣSource)∪CritRewritePTIME(M)∪IsCrit(M) We can combine this result with recent work on finegrained complexity of GTGDs to improve the doubly exponential upper bound of Corollary 1 for linear TGD source constraints and atomic mappings: Theorem4. DiscloseC(LTGD, AtomMap) is in EXPTIME. If the arity of relations in the source schema is bounded, then the complexity drops to NP, while if further the policy is atomic, the problem is in PTIME. Proof. It is sufficient to get an EXPTIME algorithm for the entailment problem produced by Theorem 3, since then we can apply it to each pAnnot in EXPTIME. The constraints in CritRewritePTIME(ΣSource) ∪ CritRewritePTIME(M) are Guarded TGDs that are not necessarily LTGDs. But the bodies of these guarded TGDs consist of a guard predicate and atoms over a fixed "side signature", namely the unary predicate IsCrit. It is known that the query entailment for IncDeps and guarded TGDs with a fixed side signature is in EXPTIME, with the complexity dropping to NP (resp. PTIME) when the arity is fixed (resp. fixed and the query is atomic) [Amarilli and Benedikt, 2018]. Can we do better than EXPTIME? We can note that when the constraints σ ∈ ΣSource are IncDeps, CritRewrite(σ) consists only of σ; similarly if a mapping m ∈ M is a projection, then CritRewrite(m) consists only of m. This gives us a good upper bound in one of the most basic cases: Corollary 3. DiscloseC(IncDep, ProjMap) is in PSPACE. If further a bound is fixed on the arity of relations in the source schema, then the problem becomes NP, dropping to PTIME when the policy is atomic. Proof. Our algorithm will guess a pAnnot in CritRewrite(Q) and checks the entailment of Theorem 2. This gives an entailment problem for IncDeps, known to be in PSPACE in general, in NP for bounded arity, and in PTIME for bounded arity and atomic queries [Johnson and Klug, 1984]. ## 3.2 Obtaining Tractability Thus far we have seen cases where the complexity drops to PSPACE in the general case and NP in the bounded arity case, and PTIME for atomic queries. We now present a case where we obtain tractability for arbitrary queries and arity. Recall that a UID is an IncDep where at most one variable is exported. They are actually quite common, capturing referential integrity when data is identified by a single attribute. We can show that restricting to UIDs while having only projection maps leads to tractability: Theorem 5. DiscloseC(UID, ProjMap) is in PTIME. Proof. The first step is to refine the reduction of Theorem 2 to get an entailment problem with only UIDs, over an instance consisting of a single unary fact IsCrit(cCrit). The main issue is avoid the constraints in ΣM(M), corresponding to the mapping rules. The intuition for this is that on DG(M) Crit , the only impact of the backward and forward implications of ΣM(M) is to create new facts among the source relations. In these new facts only cCrit, is propagated. Rather than creating SCEQrules (implicitly what happens in the HOCWQ reduction) or generating classical constraints where the impact of the equalities are "baked in" (as in the critical-instance rewritings of Theorems 2 and 3), we truncate the source relations to the positions where non-visible elements occur, while generating UIDs on these truncated relations that simulate the impact of back-and-forth using ΣM(M). The second step is to show that query entailment with UIDs over the instance consisting only of IsCrit(cCrit) is in PTIME. This can be seen as an extension of the PTIME inference algorithm for UIDs [Cosmadakis et al., 1990]. The idea behind this result is to analyze the classical "chase procedure" for query entailment with TGDs [Fagin et al., 2005]. In the case of UIDs over a unary fact, the shape of the chase model is very restricted; roughly speaking, it is a tree where only a single fact connects two values. Based on this, we can simplify the query dramatically, making it into an acyclic query where any two variables co-occur in at most one predicate. Once query simplification is performed, we can reduce query entailment to polynomial many entailment problems involving individual atoms in the query. This in turn can be solved using the UID inference procedure of [Cosmadakis et al., 1990]. ## 4 Lower Bounds We now focus on providing lower bounds for DiscloseC(C,Map), showing in particular that the upper bounds provided in Section 3 can not be substantially improved. For many classes of constraints it is easy to see that the complexity of disclosure inherits the lower bounds for the classical entailment problem for the class. From this we get a number of matching lower bounds; e.g. 2EXPTIME for GTGD constraints, PSPACE for IncDep constraints. But note that in some cases the upper bounds we have provided for disclosure in Section 3 are higher than the complexity of entailment over the source constraints. For example, for IncDeps we have provided only a 2EXPTIME upper bound for guarded mappings (from Corollary 1), and only an exponential bound for atomic mappings (from Theorem 4). This suggests that the form of the mappings influences the complexity as well, as we now show. Most of our proofs for hardness above the entailment bound for source constraints rely on the encoding of a Turing machine. Source constraints are used to generate the underlying structures (tree of configurations, tape of a Turing machine) while mappings are used to ensure consistency (a universal configuration is accepting if and only if all its successor configurations are accepting, the content of the tape is consistently represented,...). To illustrate our approach, we sketch the proof of the following result. Theorem 6. DiscloseC(IncDep, GuardedMap) and DiscloseC(GTGD, ProjMap) are 2EXPTIME-hard, and are EXPTIME-hard even in bounded arity. Proof. Recall that Theorem 1 relates disclosure to a HOCWQ problem on DG(M) Crit . Also recall from Section 3 the intuition that such a problem amounts to a classical entailment problem for a CQ over a very simple instance, using the source dependencies and SCEQrules: of the form φ(⃗x) → x = cCrit, where φ will be the body of a mapping. We will sketch how to simulate an alternating EXPSPACE Turing machine M using a QEntail problem using IncDeps and guarded SCEQrules. This can in turn be simulated using our HOCWQ problem. We first build a tree of configurations using IncDeps, such that each node has a type (existential or universal) and is the parent of two nodes (called α-successor and β-successor) of the opposite type. This tree structure is represented, together with additional information, by atoms such as: Intuitively, this states that c is a universal configuration, parent of cα and cβ. ac (resp. acα, resp. acβ) is the acceptance bit for c (resp. cα, resp. cβ), which will be made equal to cCrit if and only if the configuration represented by c (resp. cα, resp. cβ) is accepting. ⃗ y0, ⃗ y1 will be used to represent cell addresses, while r is the identifier of the root of the configuration tree. The initial instance is such an atom, where the first position and the last position are the same constant, ⃗ y0 is a vector of n 0's, ⃗ y1 is a vector of n 1's, and all other arguments are distinct constants. We use SCEQrules to propagate acceptance information up in the tree. For instance, a universal configuration is accepting if both its successors are accepting. This is simulated by the following SCEQrule: To simulate M, we need access to an exponential number of cells for each configuration. We identify a cell by the configuration it belongs to and an address, which is a vector, generated by IncDeps, of length n whose arguments are either 0 or 1. The atom for representing a cell is thus Cell(cp, c, ⃗ addr,⃗v,⃗vprev,⃗vnext), where cp is the parent configuration of c, which is the configuration to which the represented cell belongs, ⃗ addr is the address of the cell, ⃗v its content, ⃗vprev the content of the previous cell, and ⃗vnext the content of the next cell. Note that this representation is redundant, and we need to use SCEQrules to ensure its consistency. Note that ⃗v is a tuple of length the size of (Σ ∪ {♭}) × (Q∪ {⊥}). Each position corresponds to an element of that set, and the content of a represented cell is the element which corresponds to the unique position in which cCrit appears. We now explain how to build the representation of the initial tape, and simulate the transition function. Both steps are done by unifying some nulls with cCrit. W.l.o.g., we assume that the initial tape contains a l in the first cell, on which points the head of M in a state s, and that (l, s) corresponds to the first bit of ⃗v. We thus use a SCEQrule to set this bit to cCrit in the first cell of the first configuration. We then set (w.l.o.g.) the second bit of all the other cells of that configuration to cCrit (assuming this represents (♭,⊥)). To simulate the transitions, we note that the content of a cell in a configuration depends only on the content of the same cell in the parent configuration, along with the content of parent's previous and next cells. We thus add a SCEQrule that checks for the presence of cCrit specifying the content of three consecutive cells in a configuration, and unify a null with cCrit to specify the content of the corresponding cell of a child configuration. Table 1: Complexity of disclosure: PSPACEU=C3 L=QEntail means the corresponding problem is PSPACE-complete, where the Upper bound is given by Corollary 3 (U=C3) and the Lower bound is inherited from entailment. We omit bounds inferred from inclusion (M or ΣSource). | M - ΣSource | Unbounded arity - ProjMap | Unbounded arity - AtomMap | Unbounded arity - GuardedMap | Unbounded arity - CQMap | Bounded arity - ProjMap | Bounded arity - AtomMap | Bounded arity - GuardedMap | Bounded arity - CQMap | |---------------|-----------------------------|-----------------------------|--------------------------------|---------------------------|---------------------------|---------------------------|------------------------------|-------------------------| | IncDep | PSPACEU=C3 L=QEntail | EXPTIMEL=T7 | 2EXPTIMEL=T6 | 2EXPTIME | NPL=QEntail | NP | EXPTIMEL=T6 | 2EXPTIMEL=T8 | | LTGD | EXPTIMEL=T7 | EXPTIMEU=T4 | 2EXPTIME | 2EXPTIME | NP | NPU=T4 | EXPTIME | 2EXPTIME | | GTGD | 2EXPTIMEL=T6 | 2EXPTIME | 2EXPTIME | 2EXPTIME | EXPTIMEL=T 6 | EXPTIME | EXPTIMEU=C2 | 2EXPTIME | | FGTGD | 2EXPTIME | 2EXPTIME | 2EXPTIME | 2EXPTIMEU=C1 | 2EXPTIMEL=QEntail | 2EXPTIME | 2EXPTIME | 2EXPTIMEU=C1 | The argument above uses IncDeps and GuardedMaps, but we can simplify the mappings to ProjMap using GTGDs. A simple variation of the construction used for PSPACEhardness of entailment with IncDeps [Casanova et al., 1984] shows that our upper bounds for IncDep source constraints and atomic maps are tight. The case of LTGD source constraints and projection maps can be done via reduction to that of IncDep source constraints and atomic maps: Theorem 7. DiscloseC(IncDep, AtomMap) and DiscloseC(LTGD, ProjMap) are both EXPTIME-hard. The above results, coupled with argument that the lower bounds for entailment are inherited by disclosure, show tightness of all upper bounds from Table 1 in the unbounded arity case. Another variation of the encoding in Theorem 6 shows that with no restriction on the mappings one can not do better than the 2EXPTIME upper bound of Corollary 1 even for IncDep constraints in bounded arity, Theorem8. DiscloseC(IncDep, CQMap) is 2EXPTIME-hard in bounded arity. The theorem above, again combined with results showing that the lower bounds for entailment are inherited, suffice to show tightness of all upper bounds from Table 1 in the case of bounded arity. We can also show that our tractability result for UID constraints and projection maps does not extend when either the maps or the constraints are broadened. Informally, this is because with these extensions we can generate an instance on which CQ querying is NP-hard. ## 5 RelatedWork Disclosure analysis has been approached from many angles. We do not compare with the vast amount of work that analyzes probabilistic mechanisms for releasing information, providing probabilistic guarantees on disclosure [Dwork, 2006]. Our work focuses on the impact of reasoning on mapping-based mechanisms used in knowledge-based information integration, which are deterministic; thus one would prefer, and can hope for, deterministic guarantees on disclosure. We deal here with the analysis of disclosure, while there is a complementary literature on how to enforce privacy [Biskup and Weibert, 2008; Bonatti et al., 1995; Bonatti and Sauro, 2013; Studer and Werner, 2014]. The problem of whether information is disclosed on a particular instance (variation of HOCWQ introduced in Section 3) has been studied in both the knowledge representation [Lutz et al., 2013; Lutz et al., 2015; Franconi et al., 2011; Ahmetaj et al., 2016; Amendola et al., 2018] and database community [Abiteboul and Duschka, 1998]. The corresponding schema-level problem was defined in [Benedikt et al., 2016], which allows arbitrary constraints relating the source and the global schema. However, results are provided only for constraints in guarded logics, which does not subsume the case of mappings given here. Our results clarify some issues in prior work: [Benedikt et al., 2016] claimed that disclosure with IncDep source constraints and atomic maps is in PSPACE, while our Theorem 7 shows that the problem is EXPTIME-hard. Our notion of disclosure corresponds to the complement of [Benedikt et al., 2018]'s "data-independent compliance". The formal framework of [Benedikt et al., 2018] is orthogonal to ours. On the one hand, source constraints are absent; on the other hand a more powerful mapping language is considered, with existentials in the head of rules, while constraints on the global schema, given by ontological axioms, are now allowed. [Benedikt et al., 2018] assume that the attacker has an interface for posing queries against the global schema, with the queries being answered under entailment semantics. In general, the semantic information on the global schema makes disclosure harder, since the outputs of different mapping rules may be indistinguishable by an attacker who only sees the results of reasoning. In contrast, source constraints make disclosure of secrets easier, since they provide additional information to the attacker. ## 6 Summary and Conclusion We have isolated the complexity of information disclosure from a schema in the presence of commonly-studied sets of source constraints. A summary of many combinations of mappings M and source constraints ΣSource is given in Table 1: note that all problems are complete for the complexity classes listed. We have shown tractability in the case of UIDs and projection maps (omitted in the tables), while showing that lifting the restriction leads to intractability. But we leave open a finer-grained analysis of complexity for frontierone constraints with more general mappings. Our results depend on a fine-grained analysis of reasoning with TGDs and SCEQrules, a topic we think is of independent interest. ## Acknowledgements This work was partially funder by CNRS Momentum project "Managing Data without Leak". ## References 1. [Abiteboul and Duschka, 1998] Serge Abiteboul and Olivier Duschka. Complexity of answering queries using materi- alized views. In PODS, pages 254-263, 1998. 2. [Ahmetaj et al., 2016] Shqiponja Ahmetaj, Magdalena Or- tiz, and Mantas Šimkus. Polynomial datalog rewritings for expressive description logics with closed predicates. In IJCAI, pages 878-885, 2016. 3. [Amarilli and Benedikt, 2018] Antoine Amarilli and Michael Benedikt. When Can We Answer Queries Using Result-Bounded Data Interfaces? In PODS, pages 281-293, 2018. 4. [Amendola et al., 2018] Giovanni Amendola, Nicola Leone, Marco Manna, and Pierfrancesco Veltri. Enhancing exis- tential rules by closed-world variables. In IJCAI, pages 1676-1682, 2018. 5. [Baget et al., 2011] Jean-Franc ¸ois Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with ex- istential variables: Walking the decidability line. Artif. In- tell., 175(9-10), 2011. 6. [Bárány et al., 2015] Vince Bárány, Balder Ten Cate, and Luc Segoufin. Guarded negation. J. ACM, 62(3):356-367, 2015. 7. [Benedikt et al., 2016] Michael Benedikt, Pierre Bourhis, Balder ten Cate, and Gabriele Puppis. Querying visible and invisible information. In LICS, pages 297-306, 2016. 8. [Benedikt et al., 2018] Michael Benedikt, Bernardo Cuenca Grau, and Egor V. Kostylev. Logical foundations of infor- mation disclosure in ontology-based data integration. Ar- tif. Intell., 262:52-95, 2018. 9. [Biskup and Weibert, 2008] Joachim Biskup and Torben Weibert. Keeping Secrets in Incomplete Databases. Int. J. Inf. Sec., 7(3):199-217, 2008. 10. [Bonatti and Sauro, 2013] Piero A. Bonatti and Luigi Sauro. A confidentiality model for ontologies. In ISWC, pages 17-32, 2013. 11. [Bonatti et al., 1995] Piero Bonatti, Sarit Kraus, and V. S. Subrahmanian. Foundations of Secure Deductive Databases. TKDE, 7(3):406-422, 1995. 12. [Calì et al., 2013] Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive relational constraints. JAIR, pages 70-80, 2013. 13. [Casanova et al., 1984] Marco Casanova, Ronald Fagin, and Christos Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. JCSS, 28(1):29- 59, 1984. 14. [Cosmadakis et al., 1990] Stavros S. Cosmadakis, Paris C. Kanellakis, and Moshe Y. Vardi. Polynomial-time implica- tion problems for unary inclusion dependencies. J. ACM, 37(1):15-46, 1990. 15. [Dwork, 2006] Cynthia Dwork. Differential privacy. In ICALP, pages 1-12, 2006. 16. [Fagin et al., 2005] Ronald Fagin, Phokion G. Kolaitis, Re- nee J. Miller, and Lucian Popa. Data Exchange: Seman- tics and Query Answering. Theoretical Computer Science, 336(1):89-124, 2005. 17. [Franconi et al., 2011] Enrico Franconi, Yasmin Ibáñez- García, and Inanc ¸Seylan. Query answering with DBoxes is hard. ENTCS, 278:71-84, 2011. 18. [Johnson and Klug, 1984] David S. Johnson and Anthony C. Klug. Testing Containment of Conjunctive Queries un- der Functional and Inclusion Dependencies. JCSS, 28(1), 1984. 19. [Lenzerini, 2002] Maurizio Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233-246, 2002. 20. [Lutz et al., 2013] Carsten Lutz, Inanc ¸Seylan, and Frank Wolter. Ontology-based data access with closed predicates is inherently intractable (sometimes). In IJCAI, pages 1024-1030, 2013. 21. [Lutz et al., 2015] Carsten Lutz, Inanc ¸Seylan, and Frank Wolter. Ontology-mediated queries with closed predicates. In IJCAI, pages 3120-3126, 2015. 22. [Studer and Werner, 2014] Thomas Studer and Johannes Werner. Censors for Boolean Description Logic. Trans. on Data Privacy, 7(3):223-252, 2014.