On the Translatability of View Updates

Abstract

We revisit the view update problem and the abstract functional framework by Bancilhon and Spyratos in a setting where views and updates are exactly given by functions that are expressible in rst-order logic. We give a characterisation of views and their inverses based on the notion of de nability, and we introduce a general method for checking whether a view update can be uniquely translated as an update of the underlying database under the constant complement principle. We study the setting consisting of a single database relation and two views de ned by projections and compare our general criterion for translatability with the known results for the case in which the constraints on the database are given by functional dependencies. We extend the setting to any number of projective views, full dependencies (that is, egd's and full tgd's) as database constraints, and classes of updates rather than single updates.

Introduction

Updating a database by means of a set of views is a challenging task that requires updates performed on the views to be \translated" into suitable updates of the underlying database, in order to consistently propagate the changes on the views to the base relations over which the views are de ned.

A general and precise understanding of the view update problem is due to the seminal work [ 2 ] by Bancilhon and Spyratos (B&S), who devise a functional framework in which they formalise the problem and provide an elegant solution to it. They introduce the notion of view complement, representing what is missing from a view to have the same informative content of the underlying database. Moreover, they introduce the constant complement principle, establishing that the changes made on a view must not in uence the content of its complement. B&S do not provide actual methods for checking the translatability of updates and computing their translations, asserting that \computational algorithms (if they exist) must be sought in speci c problems".

In the context of SQL databases, Lechtenborger [ 12 ] gives a characterisation of the constant complement principle in terms of \undo" operations, showing that view updates are translatable under constant complement precisely if users have the chance to undo all e ects of their updates by using further view updates. It is then argued that testing whether this holds could be an alternative to checking whether users can observe all e ects of their updates in the view schema.

Gottlob et al. [ 9 ] extend the results of [ 2 ] to the class of so-called consistent views, which properly contains the views translating under constant complement. The main di erence is that, during the translation of an update on a consistent view, the complement is not required to remain invariant, but it is allowed to \decrease" according to a suitable partial order. Indeed, when the partial order is the equality, the framework coincides with the one in [ 2 ].

Cosmadakis and Papadimitriou [ 6 ] consider a restricted setting that consists of a single database relation and two views de ned by projections. They provide necessary and su cient conditions for the translatability of insertions, deletions and replacements under constant complement w.r.t. a speci c database instance and when the constraints on the database are given by functional dependencies (fd's). To the best of our knowledge, [ 6 ] is the only comprehensive work in which the framework by B&S is applied to a relational setting. We discuss in detail this application scenario in Sec. 4, where we extend the setting to any number of views de ned by projections, rather than just two, and more expressive database constraints, namely full dependencies (egd's and full tgd's), and to classes of updates rather than single updates.

In [ 2 ], the view update problem is formalised at a high level of abstraction, where views and updates are arbitrary functions, of which no constructive characterisation is given, as indeed one might not even be possible. In this paper, we consider the view update problem at a lower level of abstraction, by revisiting B&S' framework in a setting where views and updates are exactly given by functions that are expressible in rst-order logic (FOL). Under certain conditions, this class of functions can be constructively characterised through the notion of logical de nability, in terms of which we introduce a general method for checking the translatability of arbitrary FO-expressible view updates. With this work we mainly contribute the following: { a general framework for view updating that is based on the notion of determinacy and constructively revisits [ 2 ] in a setting with constraints; { a general method, applicable whenever the inverse of a view mapping can be constructively characterised, for checking whether a view update can be propagated to the underlying database in a unique way; { a practical application setting consisting of projective views of a single database relation, that, although still very limited, extends the known existing results [ 6 ] to more expressive database constraints, any number of acyclic projective views and more general view updates.

The paper is organised as follows: in Sec. 2 we introduce some notation and basic de nitions; in Sec. 3 we present our logic-based framework and characterise when and whether a FO-expressible view update is uniquely translatable under constant complement; in Sec. 4 we study the case considered in [ 6 ] and generalise the results to a more general setting; we conclude in Sec. 5 by pointing out some future research directions. Proofs and more detailed examples are given in the full version [ 7 ]. 2

Preliminaries

An n-ary relation on a set A, where n 2 N1 denotes the arity of the relation, is a subset of the Cartesian product An, that is, a set of n-tuples of elements of A. A signature is a nite set S of relation symbols and each symbols S 2 S has an associated arity denoted by arity(S). A relational structure s over a signature S is a pair h s; si where s is a (possibly in nite) domain of objects and s is an interpretation function that associates each symbol S 2 S with a relation Ss on s, called the extension of S, of appropriate arity. For two relational structures s = h ; si and t = h ; ti over two disjoint signatures S and S0, respectively, s ] t = h ; s [ ti is a relational structure over S [ S0. A constraint is a closed formula ' in (some fragment of) FOL. The set of relation symbols occurring in ' is denoted by sig(') and ' is said to be over a signature S if sig(') S. We extend sig( ) to sets of constraints in the natural way. Sequences (i.e., tuples) are denoted with an overline, e.g., x, and x[k] denotes the k-th element in x. The number of elements in x is denoted by jxj and, when x is a sequence of variables, var(x) denotes the set of variables occurring in it.

A renaming over a signature S is a bijective function ren : S ! S0, where S0 is a signature disjoint with S. We extend ren( ) to signatures, relational structures and (sets of) constraints in the natural way. For instance, given a constraint ', ren(') is obtained from ' by replacing every occurrence of each relation symbol r 2 sig(') with ren(r). Clearly, for a set of constraints over S and a relational structure s over ren(S), we have that s j= ren( ) i ren 1(s) j= .

A database schema is a signature R of database symbols and a database state is a relational structure over R. A view schema is a signature V of view symbols not occurring in R and a view state is a relational structure over V. We denote the set of all database (resp., view) states by S (resp., T). For a database state s 2 S and a view state t 2 T having the same domain, the relational structure s ] t is called a global state over R [ V. We consider a satis able nite set of global constraints over the signature R [ V. A database state s (resp., view state t) is -consistent i there exists a view state t (resp., database state s) with the same domain such that the global state s ] t is a model of . We denote the set of -consistent database states (resp., view states) by S (resp., T ). When is understood from the context, we refer to -consistent states generically as globally consistent states or states that are consistent with the global constraints.

De nition 1 (View under constraints). A view from R to V under con

straints is a total mapping f : S ! T s.t. s ] f (s) j= for every s 2 S .

Since R and V are disjoint, every model of has the form s ] t, where s 2 S and t 2 T are (globally consistent) states with the same domain. We say that V 2 V is implicitly de ned by the symbols in R under if for every pair of global states s ] t and s ] t0 satisfying , it is the case that V t = V t0 . In other words, every two models of (with the same domain) agreeing on the interpretation of the symbols in R also agree on the interpretation of V .

De nition 2. R de nes V under (written R

t; t0 2 T, it is the case that t = t0 whenever s ] t j=

V) i , for every s 2 S and and s ] t0 j= .

In particular, R . We use V

V means that every V 2 V is implicitly de ned by R under R, R = V and V = R with the obvious meaning.

fdisjoint, completeg Male

Female Under the constraints in , whenever we \ x" who the persons and the males are, we also implicitly determine who the females are. Indeed, when Person(x) and Male(x) are considered database predicates, Female(x) is explicitly de ned as the view Person(x) ^ : Male(x). That is, under the given constraints, a female is exactly a person who is not male.

In general, there might exist more than one view mapping satisfying a given set of constraints. An important connection between de nability and views under constraints is that the mapping is unique exactly when each view symbol can be de ned in terms of the database symbols under the given constraints.

Theorem 1. R

V i there is one and only one view from R to V under

.

The above theorem gives a characterisation of the views that are expressible by means of constraints in FOL. In what follows, we write R f V to indicate that R V and f is the (one and only) view induced by the constraints from R to

V in light of Theorem 1. The surjection induced by (or surjective restriction of ) a

function f is the surjective function obtained from f by restricting its codomain to its image. We use concatenation to indicate composition, e.g., f g denotes the composition of f with g.

The framework we will present in the next section is based on the notion of logical de nability, and relies on the fact that whenever something is implicitly de ned it is possible to nd its explicit de nition as a view in FOL [ 8 ]. Unfortunately, Beth's result [ 4 ] holds when instances are unrestricted (i.e., allowed to be possibly in nite), while it fails [ 10 ] when considering nite instances only, which is the usual case of interest in database applications. Clearly, when something holds for unrestricted models it also holds in particular for nite models, therefore our framework is sound. On the other hand, if something holds on nite models, it does not necessarily hold on all models, hence our approach might in general be incomplete, in the sense that we may fail to discover invertible view mappings and translatable view updates that are such only on nite models, because our techniques require these properties to hold on unrestricted models. We say that a problem is nitely controllable i it holds true for unrestricted models whenever it holds true for nite ones (the vice versa is always true). We will prove that the implicit de nability problem in the application scenario we discuss in detail in Sec. 4 is nitely controllable; so, in this case, our results are going to be sound and complete. 3

A Logic-Based Framework for View Updates

In this section, we present our framework for view updating based on the notion of de nability in logic. We rst revisit some of the formal de nitions given in [ 2 ], adapting them to our logic-based setting. Next, we show that a view induced by a set of constraints is invertible exactly when each database symbol is implicitly de ned by the view symbols under the same constraints. We then give a general criterion for translatability in terms of a special set of view constraints that are satis ed exactly by each and every FO-expressible translatable view update. We conclude by discussing the notion of view complement and show how the results on translatability extend to the case of translation under constant complement.

A database update (resp., view update) is a function d : S ! S (resp., u : T ! T) associating each database state (resp., view state) with another one having the same domain. The sets of all the database and view updates are denoted by UR and UV , respectively.

Given a view under constraints and a view update, we want to nd a suitable database update that propagates the changes to the base relations in a consistent way. More precisely, the view update should be translated as a database update that brings the database to a new state from which, through the view mapping, we reach exactly the updated view state. In addition, unjusti ed and unnecessary changes in the database are to be avoided, in the sense that if the view update does not modify the view state, then the database update must not modify the corresponding database state either.

De nition 3 (Translation). Let f be a view from R to V under , let d 2 UR

and u 2 UV . The database update d is a translation of u (w.r.t. f ) if and only if 1) uf = f d and 2) 8s 2 S ; uf (s) = f (s) =) d(s) = s.

A translation can only exist if the updated view state lies in the image of f ; otherwise, there would be no chance of reaching the new view state by means of f from some database state. A view update that can be translated into a suitable database update, i.e., for which there exists a translation, is called translatable.

De nition 4 (Translatability). Let f : S ! T be a view from R to V

under . A view update u 2 UV is translatable (w.r.t. f ) if and only if for each s 2 S there exists s0 2 S such that f (s0) = uf (s).

Translatability of view updates ensures that there exists a translation, but does not rule out the possibility that there might be more than one. To avoid ambiguity, we are only interested in view updates that are uniquely translatable, that is, for which there exists one and only one translation. For injective views, a view update is translatable if and only if it is uniquely translatable, and the following theorem [ 2 ] gives a characterisation of the unique database update into which a translatable view update can be translated when the view is injective.

Theorem 2. Let f be an injective view under , let u 2 UV be translatable and

let d 2 UR. Let f^ denote the surjection induced by f and let u^ be obtained from u by restricting its domain and codomain to f (S ).1Then, d is a translation of u if and only if d = f^ 1u^f^.

It is possible to invert a view induced by a set of constraints i the database symbols are implicitly de ned by the view symbols under the same constraints, in which case the inverse is also e ectively computable. In such a situation, the constraints induce two mappings, one from the database states to the view states and one in the opposite direction, which are indeed one the inverse of the other.

Lemma 1. Let R

Theorem 3. Let R

f V. Then, f is surjective; and f is injective i V R. f V. Then, f is invertible i V h R, and h = f 1.

Given over R [ V, we denote by impl-def(R; V; ) the problem of checking whether R 2 R is implicitly de ned by the symbols in V under , which amounts to checking whether the following entailment holds:

[ ren( ) j= 8x R(x) $ R0(x) ; where ren is a renaming over R and R0 = ren(R). Note that, as R0 is simply a renaming of R, for symmetric reasons it is su cient to check the entailment of only one of the implications on the r.h.s. of (3). Given a view f from R to V induced by , we denote by invert(V; ) the problem of determining whether f is invertible, which amounts to checking whether impl-def(R; V; ) for each R 2 R (where R is given by sig( ) n V).

In the following, we provide an interesting characterisation of when a view update is translatable. The idea consists essentially in imposing additional constraints on the view schema so that every legal view update is translatable and vice versa. Whenever V R there exists an explicit de nition for each of the 1 As u is assumed to be translatable, u f (S ) f (S ). database symbols in terms of the view symbols. By substituting every occurrence in of each R 2 R with its explicit de nition we obtain a set eV of constraints over V which we call eV the V-embedding of .

Theorem 4. Let V

R and let t 2 T. Then, t is -consistent i t j= eV .

The V-embedding of a set of global constraints is a set of view constraints having the same \restrictiveness" of the whole , but with the advantage that they can be checked locally on the view schema. This is of particular relevance for surjective views, in which case it turns out that such constraints ensure the translatability of every view update satisfying them and enforce every translatable view update to be legal with respect to them.

Theorem 5. Let f be a surjective view from R to V under , let V R and let u 2 UV . Then, u is translatable if and only if u(t) j= eV for every t 2 T .

In other words, when updating a view state that is legal w.r.t. eV , we need to make sure that we always end up in another legal view state.

Let ren be a renaming over R [ V and let be a set of constraints over V [ V0 s.t. V V0, where V0 = ren(V). Let eV be obtained from by replacing, for each symbol V 0 2 V0, every occurrence of the predicate V 0(x) with its explicit de nition in terms of V. Then, the function induced by expresses a view update u : T ! T i eV is valid.2 Indeed, in such a case, takes a view state t over V and returns an updated view state (t) over V0. The view update u expressed by is then the function associating each t 2 T with ren 1 (t) . Note that every set of constraints over V [ V0 that expresses a view update is equivalent to a set of constraints over V [ V0 consisting of exactly one formula for each V 2 V of the form 8x V (x) $ V (x) , with sig V (x) V0.

For a view symbol V , insertion and deletion of a tuple x are represented by the following open formulae:

V 0(y) ! V (y) ^ V (y) !

V 0(y) _ y = x ^ :V 0(x) : insertV (x) deleteV (x) 8y V 0(y) $ 8y

V (y) _ y = x ; Any update that does not modify V can be represented by the closed formula noopV 8x V 0(x) $ V (x) , while the replacement of a tuple x with a tuple y is expressed by the open formula replaceV (x; y) de ned by: :V (x) _ x = y ! noopV ^

V (x) ^ x 6= y ! deleteV (x) ^ insertV (y) : In our formalism we can also directly express transactional updates, in the sense of sequences of updates that are applied one after the other. For instance, suppose we want to insert a tuple a into the extension of V and then delete tuple b from it. Note that the update insertV (a) ^ deleteV (b) implies V 0(a) and :V 0(b) (where V 0 represents V after the update), hence it is inconsistent if a = b. The correct way to represent the two sequential updates as a transaction is to consider the 2 This is needed to ensure that does not impose constraints on the view schema.

Theorem 6. Let f be a surjective view from R to V under

let u 2 UV be expressed by . Then, u is translatable i update insertV (a) ^ deleteV 0 (b), where deleteV 0 (b) is applied on V 0, which is the result of applying insertV (a) on V .

From Theorem 5, we get the following characterisation of the translatability of those view updates that are expressible, as described, in FOL. , let V R and j= ren eV .

Under the assumptions of the above theorem, the view f is injective by Lemma 1. Hence, by Theorem 2 every translatable view update u has the unique translation f 1uf . However, we might not be able to actually compute f 1 unless R V, in which case Theorem 3 ensures that the inverse of f is the view from V to R induced by . When R V, V R and expresses a translatable view update u, we have that V ren(V) and ren(V) ren( ) ren(R), therefore the unique translation of u is the database update expressed by the set such that R ren(R), obtained by replacing in ren( ) every occurrence of ren(V ) with its de nition in terms of V and, in turn, every occurrence of V with its de nition in terms of R.

Given the V-embedding eV of a set of constraints over R [ V inducing an invertible view, and given a set of constraints expressing a view update u 2 UV , translat( ; eV ) is the problem of determining whether u is translatable, that is, from Theorem 6, whether eV [ j= ren( eV ). Note that a view update which is not translatable in general might still be translated when it is applied on a given view state. For example, the insertion of a speci c tuple of values is unlikely to be translatable for all possible view states, but it might be such for a given (legal) view state. This related problem, indicated with translat(t; ; eV ), of checking whether the update is translatable w.r.t. a view state t satisfying eV , that is, whether u(t) j= eV . Clearly, translat( ; eV ) amounts to checking translat(t; ; eV ) for each t 2 T such that t j= eV .

We conclude the section by brie y discussing the notion of complement and the principle of translation under constant complement introduced in [ 2 ]. Lack of injectivity in a view f causes loss of information, due to the fact that distinct database states are mapped to the same view state. A complement of f is a view g operating on the same domain of f and capable of distinguishing between distinct database states which f maps to the same view state. If g is a complement of f , then f is a complement of g (that is, the notion of complement is symmetric), therefore we sometimes simply say that two views f and g are \complementary".

A view complement provides additional information that, together with the original view, allows to reconstruct the entire database. Two views f and g under constraints and , respectively, can be combined in a natural way into a single view under [ , which we call the union of f and g, written as f ] g. It turns out that there is a close connection between complementarity and injectivity of views, given by the fact that two views under constraints and with the same domain are complementary if and only if their union is injective.

Thus, by means of a view complement we can recover information missing from a lossy view and gain injectivity, which gives us the possibility of using the results presented earlier. However, following the rationale that the only purpose for which a view complement is made available is that of allowing for a lossy view to be updatable, we demand that the information it provides be invariant during the update process. In other words, view updates must never modify, neither directly nor indirectly, any data that belongs to the view complement. For complementary views f and g, a view update on f is g-translatable (or translatable under constant complement g), if it is translatable (in the sense of De nition 4) and in addition does not modify the extension of the symbols belonging to the complement g. In general, there might be more than one complement of a given view, and an update is g-translatable or not depending on the particular complement g we consider. Therefore, the choice of a complement de nes an \update policy", assigning unambiguous semantics to the view updates.

Given updates u and v on f and g, respectively, with some abuse of notation we denote by u ] v the combined update on f ] g. Then, the following theorem establishes the relationship between translatability w.r.t. a view under constant complement and translatability w.r.t. the union of a view and its complement.

Theorem 7. Let f and g be complementary, let u 2 UV and let v be the identity.

Then, u is g-translatable w.r.t. f if and only if u ] v is translatable w.r.t. f ] g.

This essentially means that, in general, given an injective view f from R to V and a set C V of view symbols whose extension is required to remain constant, we need to check for the translatability of view updates u 2 UV such that V t = V u(t) for every V 2 C and every t 2 T. 4

Translatable Updates on Projective Views

In this section, we discuss in some detail a setting consisting of a single database relation and views de ned by projections. It turns out that, when the database constraints are full dependencies, the view mapping de ned by the projections is invertible i the database relation can be reconstructed by their natural join. We point out that invertibility of views under constraints is nitely controllable in this case, which is a generalisation of the setting studied in [ 6 ] where only two views are considered, and that our general criterion for translatability of updates w.r.t. an instance under egd's and full tgd's subsumes the conditions given in [ 6 ] for the case in which the database constraints are fd's only.

The general setting we consider here consists of a single database relation over a universal set of attributes U and views de ned by projections on subsets X1; : : : ; Xn of U . We assume w.l.o.g. that U is a totally ordered set and denote by apos(A) the position of attribute A within U . For a subset X of U , apos(X) denotes the set fapos(A) j A 2 Xg. Let R = fRg and V = fV1; : : : ; Vng, where R and each Vi 2 V have arities jU j and jXij, respectively. Each position p in R is associated with the (one and only) attribute A 2 U for which apos(A) = p. Then, a projection on X U is expressed by the open formula projectX (x) 9y R(w), where x, y and w are sequences of distinct variables such that var(x) \ var(y) = ?, var(w) = var(x) [ var(y) and jwj = jxj + jyj. In addition, all variables from var(x) are required to appear in w at positions apos(X) and in the same order in which they appear in x.

The set of global constraints we consider is = R [ RV , where R is a set of constraints over R and RV consists of a formula of the form 8x Vi(x) $ projectXi (x) for each Vi 2 V. Let f : S ! T be the view induced by and observe that, since there are no constraints on the view schema, every database state that satis es R is -consistent, therefore S coincides with the set of legal database states. Moreover, being a view induced by constraints, f is surjective, and it is invertible i impl-def(R; V; ).

We denote by pos(Vi; p) the position of R corresponding to the p-th position of Vi and pos(Vi) denotes the set fpos(Vi; p) j 1 p arity(Vi)g, that is, the set of positions of R on which Vi projects. As an example, for Vi(x1; x2) de ned as 9y1 R(y1; x1; x2), pos(Vi; 2) = 3 because the variable x2 in the second position of Vi occurs in R at position 3, and pos(Vi) = f2; 3g. We say that V is acyclic if the hypergraph with f1; : : : ; arity(R)g as set of nodes and fpos(Vi) j Vi 2 Vg as set of hyperegedes contains no cycles (see Section 6.4 in [ 1 ]).

Let us rst consider the case, studied in [ 6 ], in which there are only two view symbols, that is, V = fV1; V2g. Rephrasing the de nition given in [ 6 ], we say that the view symbols V1 and V2 are complementary if for every two legal nite database states s and s0 for which V1f(s) = V1f(s0) and V2f(s) = V2f(s0) it is the case that Rs = Rs0 . Note that the notion of complementarity is equivalent to the implicit de nability of R from V1 and V2 under when considering nite states only. In other words, V1 and V2 are complementary i impl-def n(R; V; ), where impl-def n is impl-def restricted to nite models. It is shown in [ 6 ] that, when R consists of functional and join dependencies, V1 and V2 are complementary if and only if R nitely implies the jd ./ [X1; X2], that is, the extension of R can always be reconstructed from the extensions of V1 and V2 by means of natural join. Now, since unrestricted and nite implication of a jd from a set of fd's and jd's coincide [ 1 ], complementarity in the nite case implies complementarity in the unrestricted case, and the same goes for implicit de nability. Therefore, when R consists only of fd's and jd's, impl-def(R; V; ) and impl-def n(R; V; ) coincide, that is, impl-def(R; V; ) is nitely controllable and, in turn, also invert(V; ).

The above results can be extended to the more general setting where V = fV1; : : : ; Vng with n 2 and R consists of full dependencies, provided that V is acyclic. Indeed, in [ 3 ] it is shown that under full dependencies the decomposition of a database relation into a set of acyclic projections is lossless if and only if the reconstruction operator is the natural join. Losslessness (of vertical decompositions) and complementarity (of projective views) are equivalent notions, hence the result in [ 3 ] properly generalizes the one in [ 6 ], as fd's and jd's are a special case of egd's and full tgd's, respectively, and two projections are always acyclic. Since for full dependencies nite and unrestricted implication coincide [ 1 ], impl-def(R; V; ) is nitely controllable also in this extended setting. Moreover, we know that whenever R is implicitly de ned by V under , the extension of R can be reconstructed from the extensions of the n symbols in V by natural join, that is, entails the equivalence 8x R(x) $ V1(x1) ^ ^ Vn(xn) where x and x1; : : : ; xn are sequences of variables such that var(x) = Sin=1 var(xi), xi[p] = xj [q] i pos(Vi; p) = pos(Vj ; q), and x[p] = xi[q] i p = pos(Vi; q). In other words, variables corresponding to the same position in R must coincide. Note that the above equivalence is well-de ned i f1; : : : ; arity(R)g = Sin=1 pos(Vi), that is, the projections cover the positions of R entirely.

We now turn to the problem of checking translatability under constant complement w.r.t. a view state in the extended setting with n complementary projective views. Thus, let V = fV1; : : : ; Vng with n 2 and let C V be the set of symbols constituting the complement, that is, whose extension must remain invariant during the update. In general, here R is a set of full dependencies. In our approach, testing whether a view update u is translatable w.r.t. a nite legal view state t can be done in PTIME in the size of u(t),3 provided that u(t) is also nite, by checking that u(t) satis es the V-embedding eV of , which is obtained by replacing every occurrence of R(x) in with its explicit de nition, that is, the formula V1(x1) ^ ^ Vn(xn).

For the special case when n = 2, necessary and su cient conditions for the translatability w.r.t. an instance of insertions, deletions and replacements in the extension of V1 while keeping the extension of V2 constant are given in [ 6 ], with the further restriction that R consists of fd's only. As an exercise, it is easy to check that the conditions given separately in [ 6 ] for the translatability w.r.t. an instance of insertions, deletions and replacements can be obtained by spelling out in each case our general criterion for translatability w.r.t. a view state, which subsumes all of them, modulo the fact that we allow for more general database constraints rather than just fd's and that we consider insertions (deletions) of possibly (non-)existing tuples and replacements of a tuple with possibly the same one.4 We give an idea of how our criterion corresponds to the conditions of [ 6 ] in the case of insertions by means of an example.

Example 2. Let U = fE; D; P; S; M g, where E stands for Employee, D for Department, P for Position, S for Salary and M for Manager. Let < be a total order on U s.t. E < D < P < S < M , thus apos(E) = 1, apos(D) = 2, apos(P ) = 3, apos(S) = 4 and apos(M ) = 5. Let V = fV1; V2g and RV consist of: that is, the two view symbols are de ned by projections on EDP and EDSM . Let R consists of the following constraints: 8x R(x1; x2; x3; x4; x5) ^ R(x1; x2; x03; x04; x05) ! x3 = x03 ; 8x R(x1; x2; x3; x4; x5) ^ R(x01; x02; x3; x04; x05) ! x4 = x04 ; 8x R(x1; x2; x3; x4; x5) ^ R(x01; x2; x03; x04; x05) ! x5 = x05 ; (5a) (5b) (6a) (6b) (6c) 3 This is the data complexity of testing whether a nite relational structure is a model of a FOL theory. 4 For instance, condition (b) of Theorem 3 in [ 6 ] is necessary only due to the assumption that the tuple to be inserted is not already present in the view extension. where x is the sequence of all the variables appearing in each case. Equations (6a), (6b) and (6c) express the fd's ED ! P , P ! S and D ! M , respectively. It can be veri ed that = R [ RV implies the jd ./ [EDP; EDSM ], that is: 8x R(x1; x2; x3; x4; x5) $ V1(x1; x2; x3) ^ V2(x1; x2; x4; x5) : By substituting every occurrence of R(x1; x2; x3; x4) in (5a), (5b), (6a), (6b) and (6c) with the explicit de nition V1(x1; x2; x3) ^ V2(x1; x2; x4; x5) we obtain: together constituting the V-embedding eV of . Note that, while the fd's (6a) and (6c) on R are preserved as the fd's (8c) and (8e) on V1 and V2, respectively, the fd (6b) becomes a genuine egd, namely (8d), on V1 and V2.

Let a = he; d; p; si and consider the view update u, expressed by fnoopV1 ; insertV2 (a)g, that inserts the tuple a into the extension of V2 while the extension of V1 remains unchanged. Given a view state t satisfying eV , u is translatable w.r.t. t i u(t) satis es eV too, where u(t) is such that V2u(t) = V2t [ fag and V1u(t) = V1t. As V1 is invariant, u(t) trivially satis es (8a), but it satis es (8b) i V1t contains a tuple agreeing with a on the rst two elements. In other words, we can insert a into V2t only if there is a tuple he; d; pi, for some p, in the extension of V1. This corresponds to condition (a) of Theorem 3 in [ 6 ] for the translatability of insertions, while condition (b) is necessary only if we assume that a does not belong to V2t, that is, the tuple we want to insert is not already present in the extension of V2 before the update. Finally, checking that u(t) satis es all of the edg's in eV , namely (8c), (8d) and (8e), corresponds to condition (c).

It should appear clear that with 2V choices for the complement symbols, stating conditions a la [ 6 ] for the translatability w.r.t. an instance for each possible view update when jVj > 2 could be quite tedious. Fortunately such conditions are subsumed by our general criterion and, if needed, can be derived from it in each case.

Example 3. Let U and R as in Example 2, but let V = fV1; V2; V3g and RV consist of the formulae de ning V1, V2 and V3 as projections on EDP , P S and DM , respectively. It is easy to verify that V is acyclic and that implies the jd ./ [EDP; P S; DM ]. By substituting the explicit de nition of R in terms of V in , we obtain eV consisting of the inclusion dependencies V1[D] V3[D], V3[D] V1[D], V1[P ] V2[P ] and V2[P ] V1[P ], and of the fd's V1 : ED ! P , V2 : P ! S and V3 : D ! M .

Let C = fV3g. The update u1 expressed by finsertV1 (he; d; pi); insertV2 (hp; si); noopV3 g is translatable w.r.t. a legal view state t i there is a tuple hd; mi in V3t for some m (which corresponds to satisfying the ind V1[D] V3[D], while the other ones are trivially satis ed) and u1(t) satis es all the fd's in eV involving V1 and V2. The view update u2 expressed by finsertV1 (he0; d0; p0i); noopV2 ; noopV3 g is translatable w.r.t. t i there are tuples hp0; si 2 V2t and hd0; mi 2 V3t for some s and m, respectively, and u2(t) satis es all the fd's in eV involving V1. Note that the view update u1 in Example 3 requires the simultaneous insertion of tuples into the extension of both V1 and V2, which in practise (e.g., in SQL) would be achieved by means of a transaction consisting of two successive insertions.

Another di erence between our general criterion for translatability (w.r.t. a view state) and the approach followed in [ 6 ] is that, while the latter requires some tests on the view instance and some other at the database level, the former can be checked entirely at the view level.

We conclude the section with a note about the problem of checking translatability of view updates w.r.t. every view state, and not just a given one. This is indeed the problem on which Bancilhon and Spyratos were originally focus in [ 2 ], but it is ignored in [ 6 ]. The characterisation we gave in our Theorem 6 provides a method that, even though possibly incomplete, allows to check whether a view update is translatable w.r.t. every view state. Apart from the trivial update consisting of noopVi for each Vi 2 V, a view update which is always translatable in Example 3 is expressed by:

9x V1(x; d; p) ! insertV1 (e; d; p) ^ @x V1(x; d; p) ! noopV1 ; noopV2 ; noopV3 that is, insert tuple he; d; pi into the extension of V1 only if there exists already another tuple with the same value for attributes Department and Position, otherwise do nothing. 5

Conclusion and Future Work

We presented a framework, based on the notion of view under constraints, which is an instance of B&S' abstract one, in that we consider only view mappings that are expressible by means of FOL constraints. By using the notion of de nability, we gave a constructive characterisation of when and whether a view induced by a set of constraints is invertible, and we provided a general criterion, based on the idea of \embedding" of the constraints, for testing whether a FO-expressible view update is translatable. We studied an application setting, which extends the one considered in [ 6 ] and in which our framework is complete, and we compared our general criterion for translatability of updates w.r.t. an instance with the conditions given in [ 6 ] for insertions, deletions and replacements. Although our approach might not be suitable for every application setting, we believe that it can provide some guidance in a eld which remains still largely unexplored.

For what concerns future work, the following directions seem worth of further investigation:

References

1. Abiteboul , S. , Hull , R. , Vianu , V. : Foundations of Databases. Addison-Wesley ( 1995 )

2. Bancilhon , F. , Spyratos , N.: Update semantics of relational views . ACM Transactions on Database Systems 6 ( 4 ), 557 {575 (Dec 1981 )

3. Beeri , C. , Vardi , M.Y.: On acyclic database decompositions . Information and Control 61 ( 2 ), 75 { 84 ( 1984 )

4. Beth , E.W. : On Padoa's method in the theory of de nition . Indagationes Mathematicae 15 , 330 { 339 ( 1953 )

5. Cal , A. , Gottlob , G. , Lukasiewicz , T. : Datalog : a uni ed approach to ontologies and integrity constraints . In: Proceedings of the 12th International Conference on Database Theory . pp. 14 { 30 . ICDT '09, ACM , New York, NY, USA ( 2009 )

6. Cosmadakis , S.S. , Papadimitriou , C.H. : Updates of relational views . Journal of the Association for Computing Machinery 31 ( 4 ), 742 {760 (Oct 1984 )

7. Franconi , E. , Guagliardo , P. : On the translatability of view updates . Tech. Rep. KRDB12-1 , KRDB Research Centre, Free University of Bozen-Bolzano ( Mar 2012 ), http://www.inf.unibz.it/krdb/pub/TR/KRDB12-2.pdf

8. Franconi , E. , Kerhet , V. , Ngo , N.: Exact query reformulation with expressive ontologies and databases . Tech. Rep. 12158 , KRDB Tech research group, Free University of Bozen-Bolzano ( Mar 2012 ), http://www.inf.unibz.it/krdb/pub/TR/ KRDB-Tech- 12158 .pdf

9. Gottlob , G. , Paolini , P. , Zicari , R.: Properties and update semantics of consistent views . ACM Transactions on Database Systems 13 ( 4 ), 486 {524 (Dec 1988 )

10. Gurevich , Y. : Toward logic tailored for computational complexity . In: Computation and Proof Theory, Lecture Notes in Mathematics , vol. 1104 , pp. 175 { 216 . Springer Berlin / Heidelberg ( 1984 )

11. Huang , G. : Constructing Craig interpolation formulas . In: Computing and Combinatorics, Lecture Notes in Computer Science , vol. 959 , pp. 181 { 190 . Springer Berlin / Heidelberg ( 1995 )

12. Lechtenborger, J.: The impact of the constant complement approach towards view updating . In: Proceedings of PODS 2003 . pp. 49 { 55 . San Diego, CA ( Jun 2003 )