The view update problem [
In the context of relational databases, the study of the invertibility of views
has focused on very restricted settings. Cosmadakis and Papadimitriou [
In this paper, we consider a setting where the view symbols are de ned by
conjunctive queries (CQs) and we show that, when the integrity constraints on
the database schema are strati ed embedded dependencies [
Outline. The rest of the paper is organised as follows: after some preliminaries
in Sec. 2, in Sec. 3 we recall and summarise the framework introduced in [
A schema is a nite set of relation symbols. Let dom be an arbitrary (possibly in nite) set of domain values. An instance I of a schema S maps each relation symbol S in S to a relation SI on dom of appropriate arity, called the extension of S under I. The set of elements of dom that occur in an instance I is called the active domain of I and is denoted by adom(I). An instance is nite when its active domain is, and we always assume instances to be nite. We consider a database schema R of database symbols and a view schema V of view symbols not occurring in R. A database state is an instance IR of R and a view state is an instance IV of V. The set of all database states (resp., view states) is denoted by R (resp., V). The disjoint union IR ] IV of a database state IR and a view state IV is the instance, called a global state, of the global schema R [ V, with active domain adom(IR) [ adom(IV ) and associating each relation symbol S in R [ V with SIR if S 2 R and with SIV otherwise.
We consider a satis able ( nite) set of global constraints over R [ V, consisting of a set R of database constraints over R and a set RV of interschema constraints over R [ V. The set RV consists of exactly one formula of the form 8x V (x) $ (x) for each V 2 V, where (x) mentions only database symbols and is called a de nition of V in terms of R. Note that, as R and V are disjoint, every instance of R [ V satisfying has the form IR ] IV where IR and IV are a database state and a view state, respectively. A view state IV (resp., database state IR) is -consistent (or globally consistent or consistent with the global constraints ) if there is a database state IR (resp., view state IV ) such that IR ] IV satis es the global constraints . Observe that every legal database state (i.e., one that satis es the database constraints R) is globally consistent. We denote the set of -consistent view states (resp., database states) by V (resp., R ).
We say that V determines R under (written V R) if, for every IV and IR; IR0, it is the case that IR = IR0 whenever IR ] IV j= and IR0 ] IV j= . In other words, models of that agree on the extension of the view symbols also agree on the extension of the database symbols, which means that in every model of the latter functionally depends on former. Clearly, under the assumptions we made on the global constraints , it is always the case that R V, and we refer to the corresponding functional mapping f : R ! V , associating each -consistent database state with a -consistent view state, as the view from R to V induced by . In the rest of the paper, unless speci ed otherwise, whenever we say \a view" we refer to the (one and only) view from R to V induced by a set of global constraints as above.
In this section we brie y recapitulate the general view update framework
previously introduced in [
De nition 1 (Updatability). A view is updatable if V
Note that a view in our sense is always surjective, and V R further implies
injectivity [
A translatable view update leads to view states in the image of the view f , which are therefore reachable from some database state by means of f . In such a case, when the view is updatable, the changes introduced into the view state IV by the view update u, resulting in the updated view state IV0 = u(IV ), can be univocally pushed back by updating the database to the new state f 1(IV0 ).
However, the fact that V determines R under , even though it ensures that a view is invertible, does not actually provide a constructive characterisation of its inverse. In other words, V R guarantees that the extension of the database symbols functionally depends on that of the view symbols, but it says nothing on how the former is to be obtained from the latter. In order to e ectively compute the inverse of a view, we must be able to explicitly express each database symbol R 2 R in terms of the view symbols V by means of a formula , called an exact rewriting of R in terms of V under , mentioning only view symbols and such that j= 8x R(x) $ (x) .
De nition 3. A view is e ectively updatable if each database symbol has an exact rewriting in terms of the view symbols under .
Whenever a view update results in a view state IV in V , if a view is e
ectively updatable the changes can be propagated to the database state f 1(IV ) by
computing the extension of each database symbol from its rewriting in terms of
the view symbols. But at this point, the question is: How do we ascertain whether
a view state belongs in fact to V ? The solution consists in constructing what
we call the V-embedding eV of , which is obtained from by replacing every
occurrence of each R 2 R with its rewriting in terms of V. The resulting set of
constraints mentions only view symbols and, as it turns out, is satis ed exactly
by all and only the view states in V . Thus, checking for the translatability of a
view update amounts to checking whether the updated view state satis es eV .
Theorem 1 ([
Summing up, for the above machinery to work it is essential to nd a rewriting of each database symbol in terms of the view symbols, in order to build the Vembedding of (and thus checking for the translatability of updates) and to propagate the changes introduced by translatable view updates (by computing the extension of the database symbols from that of the view symbols). Note that checking whether a view is invertible, and eventually computing its inverse, is an operation performed once for all o ine. 4
In this section, we settle the long-standing open issue pointed out in [
RV consist of the following view de nitions: R1(x; y; z ) R2(z; v; w) R1(x; y; z ) ^ R1(x0; y; z0 ) ! z = z0 ; R2(z; v; w) ^ R2(z; v0; w0) ! v = v0 : ! 9v; w R2(z; v; w) ; ! 9x; y R1(x; y; z ) ; V1(x; y) $ 9z R1(x; y; z) ; V2(y; z; v) $ 9x; w R1(x; y; z) ^ R2(z; v; w) ; V3(z; w) $ 9v
R2(z; v; w) : (1a) (1b) (1c) (1d) (2a) (2b) (2c)
The embedded dependencies we consider are required to satisfy the condition
known as strati cation [
Our main result establishes that, when the embedded dependencies over the database schema are strati ed, the view is invertible precisely if each database symbol has an exact rewriting as a conjunctive query over the view schema. 1 Universal quanti ers are omitted. Algorithm 1 Theorem 2. Let = R [ RV , where R consists of strati ed embedded dependencies and each V 2 V is de ned in RV by a CQ. Then, V R if and only if each R 2 R has an exact CQ rewriting in terms of V under .
The Chase and Backchase (C&B) [
We can use the C&B to look for the rewritings we are interested in. For each R 2 R, consider the atomic query q(x) = R(x) and proceed as follows: Chase. Chase q with until no further chase step applies. The resulting query is the so-called universal plan U .
Backchase. Every subquery of U over V (i.e., a set of V-atoms from U mentioning all of q's free variables) is a candidate rewriting of q. Chase each candidate q0 with step-by-step until no further chase step applies, and at each new step in the chase sequence check whether a containment mapping from the original query q can be found. If that is the case, then q0 is a rewriting of q.
The above is described in more detail in Algorithm 1 and illustrated in our running example.
Example 2. Chasing the query q(x; y; z) = R1(x; y; z) with the following universal plan: of Example 1 gives U (x; y; z) = 9v; w R1(x; y; z) ^ R2(z; v; w) ^ V1(x; y) ^ V2(y; z; v) ^ V3(z; w) : A candidate rewriting of R(x; y; z) in terms of V is the subquery q0(x; y; z) = 9v V1(x; y) ^ V2(y; z; v), that chased with the left-to-right TGDs from (2a) and (2b) yields the following: q00(x; y; z) = 9v; z0; x0; w
V1(x; y) ^ V2 (y ; z; v) ^ R1(x; y; z0) ^ R1(x0; y; z) ^ R2(z; v; w) : A further chase step with (1c) gives z0 = z, and therefore we can nd a containment mapping (the identity) from the original query q to q00. Thus, the rewriting of R1(x; y; z) is 9v V1(x; y) ^ V2(y; z; v). Similarly, we also have that R2(z; v; w) can be rewritten in terms of V as 9y V2(y; z; v) ^ V3(z; w).
As it turns out, the constraints considered in Theorem 2 are strati ed, and this ensures that if an exact CQ-rewriting of R(x) cannot be found by means of Algorithm 1, then R cannot be expressed at all in terms of the view symbols. Theorem 3. Let be as in Theorem 2. Then, the procedure Rewrite of Algorithm 1 is sound and complete for nding the exact rewriting of each database symbol in terms of the view symbols under . Moreover, V R if and only if Rewrite(q; ; V) 6= ? for every atomic query q over R.
The results presented above extend the setting of [
We conclude by pointing out and brie y discussing possible research directions
that would be interesting to pursue and investigate further.
{ Consider views de ned by queries expressed in languages beyond CQs. A rst
natural candidate is the class of unions of conjunctive queries.
{ Consider di erent constraints on the database schema. Several su cient
conditions for chase termination have been proposed, e.g., super-weak acyclicity [