Updating a database by means of a set of views is a classical problem in database research, known as the view update problem. It consists in \pushing back" the changes introduced into view relations by an update to the underlying database relations over which the view relations are de ned. In very recent years, the view update problem has received renewed interest and attention [7,5,9,8,4]. View updates can be consistently and univocally propagated under the condition that the mapping between database and view relations is lossless, that is, the views provide the same amount of information as the database itself. Clearly, this is quite a strong requirement, as in common practical scenarios user views are created with the aim of allowing access only to speci c portions of the database and thus, being lossy by design, such views are not directly updatable. The solution to this problem consists in using additional information, transferred by a so-called view complement, that is missing from the original view but needed to propagate the updates. However, under what is known as the constant complement principle [3], this complementary information must be invariant during the update process, that is, it must not be modi ed { directly or indirectly { by the view update. Therefore, the amount of information transferred by the view complement should be kept as small as possible. To the best of our knowledge, in the relational setting, the only case studied in the literature is the one where the initial view consists of a single projection and the complement to be constructed is also restricted to a single projection [6]. A natural extension of the above, not investigated so far, is the case in which we are given a view as a set of projections and we want to construct a complement that consists of a set of projections too. The goal of our work is to initiate the generalization of the study of view complements in this direction.
1 KRDB Research Centre, Free University of Bozen-Bolzano 2 Vienna University of Technology
Contribution and Outline. To properly choose a \good" view complement,
we need a measure of how much information a complement provides w.r.t.
another, together with an appropriate notion of minimality. In [
In Section 4, we restrict our attention to a setting where functional dependencies (FDs) are given on the source data and views are de ned as sets of projections. We study in depth the information transferred by such views. For views de ned by a single projection, the information transfer order between two views is easily reduced to the subset-relation between the sets of attributes of the two projections. To generalize this result to sets of projections , we present an algorithm that, in general, allows us to augment the set of attributes of the involved projections by taking the interaction between them into account.
Finally, in Section 5, we investigate the complement of a set of projections.
To this end, we show that it may be bene cial to split a complement
consisting of a single projection, as 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). All instances in this paper are nite, that is, have a nite active domain.
A view from R to V is a function associating instances of a database schema R with instances of a view schema V disjoint with R. A view is speci ed in a query language L when each view symbol V 2 V is de ned by an L-query over R. For a set of integrity constraints on the database schema R, we denote by R the set of instances of R satisfying , and we refer to such instances as legal. Then, a view under associates legal instances of R with instances of V.
In what follows, unless otherwise speci ed, views are assumed to be from the
same database schema to distinct view schemas disjoint with each other, e.g., f
and g are from R to V and from R to W, respectively, with V and W disjoint
with each other (and with R). The amount of information that a view transfers
from the source database w.r.t. another view can be measured as follows:
De nition 1 ([
A view loses information when it associates distinct database instances with the same view instance. This loss of information can be recovered by a view that \complements" the original one by separating instances the latter does not.
g is a complement of f if, for every distinct I; I0 2 R , g(I) 6= g(I0) whenever f (I) = f (I0). Moreover, g is minimal if, for every complement h of f , g h whenever h g.
Note that the above notion is symmetric, in that if g is a complement of f , then f is a complement of g. For this reason, sometimes we simply say that two views f and g are complementary. 3
In this section we present some general results about the minimality of complements, without committing to any particular language for specifying views. First, we show that a minimal complement complements the original view only when needed, as formally stated below.
Proposition 1. Let f be a view under , and let g be a minimal complement of f . Then, for every distinct I; I0, g(I) 6= g(I0) if and only if f (I) = f (I0).
This characterisation allows us to prove that there always exists a unique (up to information-transfer equivalence) minimal complement of any given view.
h be minimal complements of f . Then, g h.
In general, the unique minimal complement might not be expressible in the concrete language used for specifying views. In this case, we are interested in complements which are minimal among those expressible within the language. For a class C of views speci ed in a language L, minimal complements within C are referred to as C-minimal. A unique C-minimal complement might no longer exist, as we show below for projective views, that is, views speci ed by projections. Proposition 2. Let C be the class of projective views. There exist constraints and views f , g and h in C under such that g and h are C-minimal complements of f which are incomparable under .
Proof. Let R be a relation symbol on attributes A; B; C, and let consist of the FDs A ! C and B ! C. Let the view symbols V1, V2 and V3 be de ned by projections on AB, BC and AC, respectively, and for i 2 f1; 2; 3g let fi be the corresponding views under from R = fRg to Vi = fVig. Then, f2 and f3 are both complements of f1 because R is equivalent to the natural join of V1 with V2 and of V1 with V3, due to the FDs in . The projection on ABC is obviously not minimal since it includes the attributes of V2 and V3, and no other projection is a complement. Hence, f2 and f3 are minimal. Let I = fR(a; b; c)g, I0 = fR(a0; b; c)g and I00 = fR(a; b0; c)g. Since f2(I) = f2(I0) and f3(I) 6= f3(I0), we have that f3 6 f2 and, as f3(I) = f3(I00) and f2(I) 6= f2(I00), we also have that f3 6 f2. Therefore, f2 and f3 are incomparable under . 4
In the rest of the paper, we consider a database schema consisting of only one relation symbol R on a set U of attributes, view symbols de ned by projections on subsets of U and database constraints given by FDs. W.l.o.g. we assume the FDs to be of the form X ! A, with X U and A 2 U . We denote by fX1;:::;Xn the view under speci ed by the n projections on the sets of attributes X1; : : : ; Xn. For ease of notation, we omit the superscript whenever there is no need to explicitly mention the set of FDs under consideration.
First we observe that, when views are single projections, the order can be characterised in terms of inclusion between the sets of attributes in the projections.
fY if and only if X
Y .
To compare the information transferred by several views de ned by sets of projections it su ces to consider a single projection on the left-hand side.
fY1;:::;Ym i fXi fY1;:::;Ym for each i 2 f1; : : : ; ng.
Towards an e ective criterion for checking , let us examine S = ./im=1 Yi (I) for some instance I. In particular, the join can be computed by (1) picking m tuples t1; : : : ; tm from I, (2) projecting them on the respective Yi, i.e., Y1 (t1); : : :, m Ym (tn) and (3) checking the join conditions. Let k = j[i=1Yij, then
S = f (s1; : : : ; sk) j 9t1; : : : ; tm 2 I s.t. 8 Yi; Aj : Aj 2 Yi =) ti[Aj ] = sj g The above characterisation of S in terms of the equalities between a result tuple (s1; : : : ; sk) and the attributes of the ti's motivates Algorithm 1, which has the following property.
Theorem 2. Let fY1 ; : : : ; Ymg = Saturate(fY1; : : : ; Ymg; ). If for every i 2 f1; : : : ; ng there is a j 2 f1; : : : ; mg s.t. Xi Yj , then fX1;:::;Xn fY1;:::;Ym . As a corollary of the preceding theorem, it follows that Algorithm 1 preserves the information-transfer order.
Corollary 1. Let fY1 ; : : : ; Ymg = Saturate(fY1; : : : ; Ymg; ). Then it holds that fY1 ;:::;Ym fY1;:::;Ym .
Note that Theorem 2 corresponds to the soundness of Algorithm 1. Yet, we conjecture that the following holds: Conjecture 1. fX fY1;:::;Ym if and only if, for every legal instance I holds
X (I)
X
Y1 (I) ./ : : : ./ Ym (I) (1) This would amount to the completeness of Algorithm 1. We have a proof of Conjecture 1 for the special case m = 2, i.e., the right-hand side is given by two projections. The general form of Conjecture 1 as given above is an open question for future work. 5
Checking whether a view fX1;:::;Xn is lossless under a set of full dependencies
(that is, EGDs and full TGDs) amounts to checking whether entails the join
dependency ./ [X1; : : : ; Xn] (we use the notation of [
Proposition 5. When view complements are restricted to a single projection, a minimal complement of a view fX1;:::Xn under full dependencies can be found in polynomial time.
Proof. The algorithm is the same as for nding a minimal one-projection
complement of a one-projection view [
The following example shows the bene t of splitting a complement into smaller pieces w.r.t. the propagation of updates.
Example 1. Let R be on ABCDE, let consist of the FDs B ! C and D ! E,
and consider the view fABD. It can be checked that fBCDE and fBC;DE are
both complements of fABD. Let I be the instance such that RI = f(a; b; c; d; e);
(a; b0; c0; d0; e0)g. The insertion of (a; b; d0) into ABD(I) can be propagated back
only by inserting (a; b; c; d0; e0) into I, for which BC (I) and DE (I) remain
unchanged, but BCDE (I) is required to include (b; c; d0; e0). Hence, under the
constant complement principle, the insertion of (a; b; d0) into ABD(I) is
translatable [
Algorithm 2 re nes a view complement consisting of a single projection by computing one that consists of multiple projections and, although not minimal in general, transfers less (or the same) information.
Theorem 3. Let fX1;:::;Xn and fY be complementary views and let fY1; : : : ; Ymg be the result of Re ne(fX1; : : : ; Xng; Y; ) according to Algorithm 2. Then, (1) fY1;:::;Ym is a complement of fX1;:::;Xn ; and (2) fY1;:::;Ym fY .
Intuitively, Algorithm 2 works as follows: rst, the set Y of attributes is recursively split into smaller sets according to the FDs in ; then, all the redundant sets, contained in one of the input sets X1; : : : ; Xn, are discarded. The two steps are combined into a single one for e ciency reasons, in order to discard redundant sets at an earlier stage and so avoid unnecessary splittings. In the situation of Example 1, Re ne(fABDg,BCDE, ) returns the sets of attributes BC and DE as expected.
For views de ned by a single projection, we have established an easy correspondence between the information transfer order and the subset-relationship between the sets of attributes onto which the projections are de ned. For sets of projections, we have shown with our new Saturation algorithm in Section 4 how the sets of attributes may possibly be augmented without changing the information transfer. Theorem 2 can be seen as stating the soundness of the Saturation algorithm. We conjecture that the opposite direction in Theorem 2 also holds, which amounts to claiming the completeness of the Saturation algorithm. Proving this conjecture remains as an open problem for future work.
Similarly, the Re ne complement algorithm in Section 5 aims at transforming a complement given by one or several projections into another set of projections with smaller information transfer. Actually, one could easily further strengthen the algorithm by rst applying the Saturation algorithm to the sets X1; : : : ; Xn, which possibly increases these sets and thus may allow the deletion of more sets by the if-statements in the Re ne complement algorithm. We conjecture that the resulting algorithm would then be guaranteed to return a view de ned by a set of projections which is minimal w.r.t. information transfer. Again, the proof of this claim remains as an open problem for future work.