BMJ

0959-8138

BMJ

0959-8138

BMJ

jBMJ

1508

Freeman,George

jBMJ

13-4-2002

1508

324 Freeman,George 7342

13-4-2002

324

7342 Fig. 3. Document D1 obtained from D0 by deleting the sub-article element

SMN

DKE

SMN

7225-4139

DKE

SMN 7225-4139

SMN

Fig. 5. Document D2 obtained from D0 after inserting a new journal-ID element. Fig. 4. Tree with root sub-article to in- sert to document D1 In [2] the authors defined inconsistencies in XML access control policies for write operations, studied the problem of identifying such policies for structured DTDs, showed that finding repairs to those policies is np-complete and provided approx- imation algorithms to compute them. Later, in [4], authors extended those results to deal with a general kind of DTD called Chain Extended DTDs (CEDTDs for 22 short), like the one in Fig. 1, imposing some restriction over the type of updates that were considered. For instance, it only considered updates that replaced el- ement types belonging to a disjunction without +, ∗ or ?. Thus, in the Journal Publishing example, the only valid replace updates would be between element types front and front-stub. In this setting, the problem of repairing inconsistent policies was shown to be np-complete. In this article, we show how an access control policy can be defined for XML databases that conform to CEDTDs in such a way that: (i) it deals with insert, delete and replace updates between any two distinct element types, (ii) policy consistency can be checked in polynomial time, (iii) repairs to inconsistent poli- cies can be found in polynomial time. The cost to achieve this is that it cannot express some policies that can be defined in [4]. However, the type of policies that cannot be expressed are not common in practice. This document is structured as follows. The definitions of XML documents, schemas and updates are provided in Section 2. Section 3 defines access control policies for CEDTDs. Next, in Section 4 the consistency of those policies in analyzed and for the cases in which they are inconsistent, the repair problem is studied in Section 5. Finally, the conclusions are provided in Section 6. 2 Preliminaries An extended DTD (EDTD) is an abstraction of the two main schema definition languages for XML [9], namely DTDs and XSDs, and represented by a quintuple (Ele, Types, Rg, rt, µ) where i) Ele is a finite set of element names ii) Types is a finite set of element types iii) rt is a distinguished element name in Ele and in Types called the root iv) µ is a mapping from Types to Ele such that µ(rt) = rt, and v) Rg defines the element types: that is, Rg : Types → RegTypes , where RegTypes is a set of regular expressions r over Types, considering concatenation, disjunction, element repetition and optionality, empty and string elements. Given a type A we will refer to Rg(A) as its production rule. An element type Bi that appears in the production rule of an element type A is called a subelement type of A. Given an EDTD D, we write A ≤D B for the transitive, reflexive closure of the subelement relation. A structured EDTD is an EDTD such that its regular expressions are defined using the grammar: str | | B1 , . . . , Bn | B1 + · · · + Bn | B∗ , where “,”, “+” and “∗” stand for concatenation, disjunction and Kleene star respectively, for the EMPTY element content, str for text values and B ∈ Types. A Chain EDTDs consists of an EDTD whose regular expressions are: (i) a se- quence of terms (A1 + · · · + An )q , where q is an optional qualifier of the form +, ∗, or ?; (ii) a string str; or (iii) empty [11]. Every structured EDTD is a Chain EDTD. 23 Example 2. The Journal Publishing Schema in Fig. 1 is a chain EDTD but it is not a structured EDTD. For example, element article contains either a front or front-stub element, optionally a body element and zero or more repetitions of sub-articles or response elements. 2 We will model an XML document as rooted unordered trees which conforms to a schema if it validates against its regular expressions. The XML document in Fig. 1 conforms to the chain EDTD in Fig. 2. Example 3. Let t0 be the XML document shown in Figure 6(b), also represented by the tree in Figure 6(c). Let D0 be the chain EDTD rooted in A shown in Figure 6(a). Document t0 conforms to schema D0 . 2 A→(B+C)+ ,D∗ ,(E+F+G) Hello A B → H,I F → str B C E C → str G → str D → str H → str World H I “World” “!!” E → str I→ !! “Hello” (a) CEDTD D0 (b) Document t0 (c) Tree representation of t0 Fig. 6. CEDTD D0 with a document t0 that conforms to it We consider the following updates: op ::= delete(n) | insert(n, t) | replace(n, t) | replaceVal(n, s). A delete(n) will remove node n and all its descendants. An insert(n, t) operation will add a tree t as a child node below n. A replace(n, t) operation will replace the subtree with root n by the tree t. A replaceVal(n, s) operation will replace the text value of node n with string s. An update oper- ation is said to be valid for t and D if the result of applying it over t results in a document that conforms to D. For example, the update delete(E) would not be valid over t0, because the resulting document would not conform to D. In what follows we consider only valid updates. We denote by [[op]](t, D) the resulting XML document obtained by applying update operation op on tree t that conforms to schema D. 3 Access Control Policies We use the notion of update access type to specify the access authorizations. Definition 1. Given a CEDTD D, a base update access type (base UAT) is an expression of the form (A, ut) where ut ::= insert(B) | delete(B) | replaceVal and A and B are types from D. 2 24 Intuitively, each of these UATs controls the operations that insert or delete an element of type B or operations that replace a string. The relation uat valid in D, which indicates that a base update access type uat is valid for the EDTD D, is constrained by the following inference rules: replaceVal valid in str U valid in t U valid in t U valid in t U valid in t∗ U valid in t+ U valid in t? insert(Bi ) valid in (B1 + · · · + Bn ) delete(Bi ) valid in (B1 + · · · + Bn ) U valid in fi U valid in Rg(A) U valid in f1 , . . . , fn (A, U ) valid in D The set of valid base UATs for a given EDTD D is denoted by valid(D) = {uat | uat valid in D}. Example 4. (example 3 cont.) Given schema D0 , valid(D0 ) = {(A, insert(B)), (A, delete(B)), (A, insert(C)), (A, delete(C)), (A, insert(D)), (A, delete(D)), (A, insert(E)), (A, delete(E)), (A, insert(F)), (A, delete(F)), (A, insert(G)), (A, delete(G)),(C, replaceVal), (D, replaceVal), (E, replaceVal), (F, replaceVal), (G, replaceVal), (H, replaceVal)} 2 Definition 2. A policy P defined over an EDTD D, is represented by the set of allowed update access types defined over D such that P ⊆ valid(D). The set of forbidden UAT of a policy P defined over D are F(P, D) = valid(D) r P . 2 Example 5. (example 4 cont.) A policy for D0 is PD0 ={(A,insert(B)),(A,delete(B)), (A, insert(C)), (A, delete(C)), (A, insert(E)), (A, delete(E)),(A, insert(F)),(A, delete(F)), (A, insert(G)), (A, delete(G)), (C, replaceVal), (E, replaceVal), (G, replaceVal)}. The set of UATs that are forbidden by PD0 are F(PD0 , D0 ) = (A, delete(D)), (A, insert(D)), (D, replaceVal), (F, replaceVal), (H, replaceVal)}. 2 We want to enforce restriction over the applications of insert, delete and replace update operations, but the policies, as we have defined so far, allow or forbid only insertions and deletions. Thus, we need to deduce from our policies update access types to control replacements. Definition 3. Given a CEDTD D, an update access type (UAT) defined over D is a base UAT or an expression of the form (A, replace(B, C)) and A, B, C are types from D. 2 In order to enforce a policy P on updates, an expanded version P ↑ is in- ferred from P , adding certain replace operations that are allowed. For instance, replace(Bi , Bj ) is considered an inferred update access type, for which the per- missions are obtained from the allowed and forbidden base UATs such as insert, delete and replaceVal. 25 Since we can apply over a document only updates that result in a new document that conforms to the DTD, we need to define replace UATs only in the cases where the replace could take place. Example 6. For the production rule A → (B+C)+ ,D∗ ,(E+F+G) of the ongoing example, elements E, F and G can only be replaced between them, since a re- placement of an element E by an B, for example, would result in a document that does not conform to the DTD. On the other hand, elements B, C and D can only be replaced between them. 2 As the previous example shows, factor of the form (B1 + · · · + Bn ) impose re- strictions over the type of elements that can be replaced. Definition 4. An XOR factor in A is a factor of the form (B1 + · · · + Bn ) in the production rule of A. Let XOR(A) = {{B1 , · · · , Bn }|(B1 + · · · + Bn ) is an XOR factor in A}. Types Bi and Bj are alternates in A if both Bi and Bj belong to the same XOR factor in A. A types Bi is independent in A if it does not belong to any XOR factor in A. 2 In the policies defined in [4] updates that replaced an independent element by another were not considered. Example 7. The production rule A → (B+C)+ ,D∗ ,(E+F+G) has one XOR fac- tor, namely (E+F+G). The alternates in A are {E,F}, {E, G} and {F, G}. The independent types in A are B, C and D. 2 Definition 5. Given a set of UATs U , the expanded version U ↑ is obtained from U using the following inference rules: (A, delete(Bi )) ∈ U, (A, insert(Bj )) ∈ U, i 6= j, and Bi , Bj are independent in A (A, replace(Bi , Bj )) ∈ U ↑ (A, delete(Bi )) ∈ U , (A, insert(Bj )) ∈ U , i 6= j, and Bi , Bj are alternates in A (A, replace(Bi , Bj )) ∈ U ↑ (A, insert(B)) ∈ U , and B is independent in A (A, insert(B)) ∈ U ↑ (A, delete(B)) ∈ U , and B is independent in A (A, replaceVal) ∈ U ↑ (A, delete(B)) ∈ U (A, replaceVal) ∈ U ↑ Given a schema D and a policy P , the set of extended valid UATs corresponds to valid(D)↑ and the expanded policy to P ↑ . 2 This expanded policy can be used to check if an update is allowed or forbidden by a policy. 26 Example 8. (example 4 cont.) The set of extended valid UATs valid(D)↑ = {(A,insert(B)), (A,insert(C)), (A,insert(D)), (A,delete(B)), (A,delete(C)), (A,delete(D)), (A, replace(E, F)),(A,replace(E, G)), (A, replace(F, E)), (A,replace(F, G)),(A,replace(G, E)), (A,replace(G, F)),(A,replace(B,C)),(A,replace(C,B)),(A,replace(C,D)),(A,replace(D,C)), (A, replace(B,D)), (A, replace(D, B)), (C, replaceVal), (D, replaceVal), (E, replaceVal), (F, replaceVal), (G, replaceVal), (H, replaceVal)}. It differs from valid(D) since it adds all the replace UATs and removes some insert and delete. The set of extended valid UATs represent the types of updates that could result in a document that con- ↑ forms to schema D0 . The extended policy PD 0 = {(A, insert(B)), (A, insert(C)), (A, delete(C)), (A, replace(C, B)), (A, delete(B)), (A, replace(B, C)), (A,replace(E,F)), (A,replace(F,E)),(A,replace(G,E)), (A,replace(E,G)), (A,replace(F,G)), (A,replace(G,F)),(C, replaceVal),(E,replaceVal),(G,replaceVal)}. The UATs that are forbidden by the pol- icy correspond to valid(D)↑ r PD↑ . 2 Intuitively, an UAT in P ↑ represents a set of atomic update operations. More specifically, for t an instance of CEDTD D, op an atomic update and uat an update access type we say that op matches uat on t (op matchest uat) if one of the following inference rules applies: η(n) = A t0 ∈ ID (B) η(n) = B η(parentt (n)) = A 0 insert(n, t ) matchest (A, insert(B)) delete(n) matchest (A, delete(B)) η(n) = B t0 ∈ ID (B0 ) η(parentt (n)) = A η(n) = str η(parentt (n)) = A replace(n, t0 ) matchest (A, replace(B, B0 )) replaceVal(n, s) matchest (A, replaceVal) Function η corresponds to the unique mapping from each node in t to the element type associated to it. This uniqueness follows from the assumption that D is unambiguous. As we said before, we will restrict only to valid update operation which given a document t and a CEDTD D the result of applying it over t results in a document that conforms with D. Since the problem of validity and authorization are orthogonal, we assume that all the operations to checked by the policy are valid. The set of operations that are allowed by a policy P on an XML tree t in an CEDTD D, denoted by [[P ]](t, D), is the union of the atomic valid update opera- tions matching each UAT in P ↑ . More formally, [[P ]](t, D) = {op | op matchest uat and uat ∈ P ↑ }. Analogously, the forbidden operations are [[F]](t, D) = {op | op op1 opn matchest uat, and uat ∈ (valid(D) \ P ↑ )}. A safe run t0 −−→ t1 . . . −−→ tn is allowed w.r.t. P and D if for every i we have opi ∈ [[P ]](ti−1 , D). 4 Consistency of Policies A policy is said to be consistent if it is not possible to simulate a forbidden update through a sequence of allowed updates. More formally: 27 Definition 6. [2] Consider a policy P defined over schema D. An inconsis- op1 opn tency in P for D consists of an allowed run t0 −−→ t1 . . . −−→ tn and an update op0 ∈ [[F]](t0 , D) such that tn = [[op0 ]](t0 , D). A policy P is consistent for D if there are no inconsistencies. 2 We say that nothing is forbidden below an element type A in a policy P defined over D if for every Bi such that A ≤D Bi and every (Bi , x) ∈ valid(D), (Bi , x) ∈ P . If A has any replace operations in valid(D), then we define the replace graph P GA = (VA , EA ) where i) VA is the set of subelements of A and ii) (Bi , Bj ) ∈ EA if there exists (A, replace(Bi , Bj )) ∈ P ↑ . Theorem 1. A policy P defined over a CEDTD D is consistent if and only if for every production rule: 1. If (A,insert(B))∈ P ↑ and (A,delete(B))∈ P ↑, then nothing is forbidden below B P 2. If for every i ∈ [1, . . . n], if Bi is contained in a cycle in GA then nothing is forbidden below Bi . Proof Sketch: Policy P and schema D can be transformed into a new policy Pstruct defined over a new structured schema Dstruct in such a way that P is consistent over D if and only if Pstruct is consistent over Dstruct . In [2] the au- thors identify three cases in which a policy defined over a structured schema is consistent: insert/delete, negative-cycle and forbidden-transitivity. Because of the characteristics of Pstruct only the first two can occur. By reversing the trans- formations, we get the conditions for CEDTDs that correspond to insert/delete and negative cycle inconsistencies. 2 The conditions in Theorem 1 are defined over the expanded policy P ↑ . In order to simplify the consistency checking problem, it is better to see how these conditions can be checked in P instead of P ↑ . Proposition 1. A policy P defined over a CEDTD D is consistent if and only if for every element types A, B and C in D: 1. If B is independent in A and {(A, insert(B)), (A, delete(B))} ⊆ P then nothing is forbidden below B. 2. If B and C are alternates in A and {(A, insert(B)), (A, delete(B)), (A, insert(C)), (A, delete(C))} ⊆ P then nothing is forbidden below B and C. 2 It is possible to check if conditions in Proposition 1 hold for a policy using standard polynomial-time graph algorithms over the DTD. Thus, the problem of deciding policy consistency with respect to CEDTDs is in ptime. Example 9. (example 8 cont) Policy PD0 has several inconsistencies. First, by having both (A, insert(B)) and (A, delete(B)) allowed for an independent element 28 type B under A, but forbidding (H, replaceVal). Another one is given by having (A, insert(E)), (A, delete(E)), (A, insert(F)) and (A, delete(F)) as allowed operations under alternate types E and F, but forbidding (F, replaceVal). Finally, given by having (A, insert(F)), (A, delete(F)), (A, insert(G)) and (A, delete(G)) as allowed op- erations under alternate types F and G, but forbidding (F, replaceVal). 5 Repairing Inconsistent Policies If a policy is inconsistent, we would like to suggest possible minimal ways of modifying it in order to restore consistency. In other words, we would like to find repairs that are as close as possible to the inconsistent policy. We would like this repairs to be more restrictive than the original, this is, a repair should provide less access to the user. Definition 7. [2] A policy P 0 is a repair of a policy P defined over a DTD D if and only if: i) P 0 is defined over D, ii) P 0 is consistent, and iii) P 0 ⊆ P . Furthermore a repair P 0 of P is a minimum-repair if there is no repair P 00 such that |P 0 | < |P 00 |.2 2 In other words a repair is a new policy over the same schema, which is consistent and contains a subset of the allowed UAT in P . For this repair to be minimal, we require that it contains the maximum number of allowed UATs or, equivalently, that a minimal number of UATs has been removed from P . The problem of computing a minimum-repair can be solved in ptime. In what follows we describe an algorithm to do so. By Proposition 1 we have that we need to solve two types of inconsistencies: Type 1: if B is independent in A, {(A, insert(B)), (A, delete(B))} ⊆ P and something is forbidden below B. Type 2: if B and C are alternates in A,{(A,insert(B)),(A,delete(B)),(A,insert(C)), (A, delete(C))} ⊆ P and something is forbidden below B or below C. Because of minimality of repairs, repairs of inconsistencies of Type 1 can be solved independently by removing either (A, insert(B)) or (A, delete(B)). This is not the case for inconsistencies of Type 2, since there might be more than one such inconsistency involving shared types. Example 10. (example 9 continued) There is an inconsistency of Type 2 between E and F since (F, replaceVal) 6∈ P . To solve this inconsistency, we need to forbid either (A, insert(E)),(A, delete(E)),(A, insert(F)) or (A, delete(F)). However, choos- ing to forbid (A, insert(E)) or (A, delete(E)) will not result in a minimal repair since element F is involved in another inconsistency of Type 2 with G since (F, replaceVal) 6∈ P . Thus, when there are several inconsistencies of Type 2 it 2 |P 0 | denotes the cardinality of set P 0 29 Algorithm 1: PolicyRepair Input : CEDTD D = (Ele, Types, Rg, rt, µ), Policy P Output : set toRemove of UATs to remove to restore consistency of P 1 (T1 , T2 ) ← DetectInconsistencies(D, P ) 2 toRemove ← ∅ 3 for A ∈ Types do 4 for B ∈ T1 (A) do 5 U ← either (A, insert(B)) or (A, delete(B)) (choose randomly) 6 toRemove ← toRemove ∪ {U } 7 for S ∈ T2 (A) do 8 if ∇ ∈ S then 9 S ← S r {∇} 10 else 11 Let E be a randomly chosen element in S 12 S ← S r {E} 13 for C ∈ S do 14 U ← either (A, insert(B)) or (A, delete(B)) (choose randomly) 15 toRemove ← toRemove ∪ {U } 16 S ← S r {C} 17 return toRemove is necessary to choose carefully to ensure that a minimal repair is found. In this case, either (A, insert(F)) or (A, delete(F)) need to be forbidden. The pol- icy also has a inconsistency of Type 1 that can be solved by forbidding either (A, insert(B)) or (A, delete(B)) from our policy. Thus, a minimum-repair for P is P 0 = P \ {(A, insert(B)), (A, delete(F))}. 2 Algorithm PolicyRepair, takes a policy P defined over a CEDTD D and returns a set of UATs to remove from P to restore consistency. The algorithm first calls Algorithm DetectInconsistencies that computes with the recursive Algorithm NodeInconsistency the inconsistencies of Type 1 and Type 2 and stores them in two functions T1 and T2 using depth-first search over schema D. Function T1 : Types → 2Types , returns for every type A the set of Types B such that {(A, insert(B)), (A, delete(B))} ⊆ P and something is forbidden below B. These inconsistencies are solved by either deleting (A, insert(B)) or (A, delete(B)) (lines 4- Types 6 of Algorithm PolicyRepair). Function T2 : Types → 22 , returns for every type A, a set of subsets of Types in such a way that if S ∈ T2 (A), then every B ∈ S belongs to the same XOR factor below A and {(A, insert(B)), (A, delete(B))} ⊆ P and something is forbidden below B. Also, if ∇ ∈ S it means there is a type C in the same XOR factor such that {(A, insert(C)), (A, delete(C))} ⊆ P but everything is allowed below C. It is easy to check that in order to solve the inconsistencies of Type 2, for every S ∈ T2 (A) we need to delete either (A, insert(B)) or (A, delete(B)) 30 Algorithm 2: DetectInconsistencies Input : CEDTD D = (Ele, Types, Rg, rt, µ), Policy P Output : A tuple (T1 , T2 ) where T1 and T2 are functions that given a type they return the inconsistencies of Type 1 and Type 2 below it 1 for A ∈ Types do 2 visited(A) ← −1 3 if there exists (A, op) ∈ F(P, D) then 4 ν(A) = 0 5 else 6 ν(A) ← −1 7 T1 (A) ← ∅ 8 T2 (A) ← ∅ 9 NodeInconsistency(D, rt, visited, ν, T1 , T2 ) 10 return (T1 , T2 ) for every B ∈ S except for ∇ if it belongs to F or any type if it does not (see lines 7-15 of Algorithm PolicyRepair). 31 Algorithm 3: NodeInconsistency Input : CEDTD D, Node A, functions:visited, ν, T1 and T2 Result: T1 (A) and T2 (A) contain inconsistencies of Type 1 and Type 2 below A 1 if visited(A) < 0 then 2 for B independent in A do 3 nodeInconsistency(M GD , visited, B) 4 if ν(B) = 0 then 5 ν(A) ← 0 6 if (A, insert(B)) ∈ P and (A, delete(B)) ∈ P then 7 T1 (A) = T1 (A) ∪ {B} 8 for F ∈ XOR(A) do 9 S←∅ 10 for B ∈ F do 11 nodeInconsistency(M GD , visited, B) 12 if ν(B) = 0 then 13 ν(A) ← 0 14 if (A, insert(B)) ∈ P and (A, delete(B)) ∈ P then 15 if ν(B) = 0 then 16 S = S ∪ {B} 17 else 18 S = S ∪ {∇} 19 if |S| > 1 then 20 T2 (A) ← T2 (A) ∪ {S} 21 if ν(A) = −1 then 22 ν(A) ← 1 23 visited(A) ← 1 Example 11. (example 5 continued) Algorithm DetectInconsistencies returns T1 and T2 such that: {B} for E=A {{F, ∇}} for E=A T1 (E) = T2 (E) = ∅ for E6=A ∅ for E6=A To solve the only inconsistency of Type 1, it chooses from either (A, insert(B)) or (A, delete(B)) and adds it to the toRemove set. Next, for sets in T2 (A), it loads them into a variable S and checks if ∇ ∈ S. If such element is in the set, it means that there are cycles inside the XOR factor involving elements that do not have something forbidden below them. In this case, the algorithm erases ∇ from S. Then the algorithm proposes to add either (A, insert(F)) or (A, delete(F)) to the toRemove set. So, by choosing one UAT from each combination shown, and changing them from allowed to forbidden, consistency is restored. 2 32 Even though finding a single minimum-repair can be done in polynomial time, there might an exponential number of them. Proposition 2. Given a policy P over a CEDTD D, a minimum-repair of it can be computed with Algorithm 1 in O(n + m) where n is the number of types in D and m is the number edges in the tree that represents D. All the repairs can be computed in O(n × 2n ). 2 In most of the cases m is O(n) and thus a minimum repair can be found in linear time on the number of types in the DTD. In the worst case m is O(n2 ). Even thought computing all the repairs requires exponential time, it is also possible to show in linear time all the inconsistencies to the designer of the policy so that he can choose how to solve each of them. 6 Conclusions We have provided an access control policy definition language based in basic update access types, that simplifies the administration of authorization, since it only requires that the policy manager defines whether the user should be able to insert or delete elements of the DTD, and automatically deduct replace authorizations from such permissions. For these type of policies, consistency checking and repair computation problems can be solved in polynomial time. We also provided efficient algorithms that, given an inconsistent policy, computes a consistent one that is as close as possible to the inconsistent one in terms of forbidden UATs. These policies are an improvement over the ones defined in [4], since the re- pair computation problem for those is np-hard. This is achieved by instead of defining policies in terms of insert, delete and replace UATs, we here define poli- cies using only insert and delete UATs and deducing from them the replace per- missions. In terms of expressive power they are not comparable since we can define policies that they cannot and vice-versa. For example, consider a DTD with the production rule A → B∗ , C∗ and B and C containing text. A policy P = {insert(C), delete(B)} with P ↑ = {insert(C), delete(B), replace(B, C)} cannot be expressed in policies defined in [4] since they do not consider replace between el- ements that do not belong to an XOR factor. On the other hand, we cannot write a policy P for which P ↑ = {(A, replace(B, C)), (B, replaceVal), (C, replaceVal)} even though P ↑ is a consistent policy in [4]. We believe that the gain in ex- pressive power outweighs the loss since being able to provide permissions for replacements outside of XOR factors is a useful feature and the policies that cannot be expressed do not seem useful in practice. Thus, the policies here in- troduced can be used as a simple, but powerful, way to provide consistent access control to XML databases. 33 Acknowledgements: This work is funded by FONDECYT grant 11080260 and CONICYT grant PSD-57. We would like to thank Irini Fundulaki and James Cheney for useful discussions. References 1. Bertino, E., Ferrari, E.: Secure and Selective Dissemination of XML Documents. ACM TISSEC 5(3), 290–331 (2002) 2. Bravo, L., Cheney, J., Fundulaki, I.: Repairing Inconsistent XML Write-Access Control Policies. In: DBPL. pp. 97–111 (2007) 3. Bravo, L., Cheney, J., Fundulaki, I.: ACCOn: Checking Consistency of XML Write- Access Control Policies. In: EDBT’08 (Demo) (2008) 4. Bravo, L., Cheney, J., Fundulaki, I., Segovia, R.: Consistency and Repair for XML Write-Access Control Policies, VLDB Journal. Accepted (2012) 5. Damiani, E., di Vimercati, S.D.C., Paraboschi, S., Samarati, P.: A Fine-grained Access Control System for XML Documents. ACM TISSEC 5(2), 169–202 (2002) 6. Fan, W., Chan, C.Y., Garofalakis, M.: Secure XML Querying with Security Views. In: ACM SIGMOD. pp. 587–598 (2004) 7. Fundulaki, I., Marx, M.: Specifying Access Control Policies for XML Documents with XPath. In: SACMAT. pp. 61–69 (2004) 8. Kuper, G., Massacci, F., Rassadko, N.: Generalized XML Security Views. In: SAC- MAT. pp. 77–84 (2005) 9. Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and Complexity of XML Schema. ACM Trans. Database Syst. 31(3), 770–813 (2006) 10. Murata, M., Tozawa, A., Kudo, M., Hada, S.: XML Access Control Using Static Analysis. ACM TISSEC 9(3), 290–331 (2006) 11. Van den Bussche, J., Neven, F., Bex, G.J.: DTDs versus XML Schema: A Practical Study. In: WebDB’04. Paris, France (2004) 34