<figure><img src="image_1.png" /></figure>

HAL
open science

Update semantics of relational views

François Bancilhon, Nicolas Spyratos

► To cite this version:

Francois Bancilhon, Nicolas Spyratos. Update semantics of relational views. [Research Report] IRIA-RR-329, IRIA. 1978, pp.34. hal-04716541

HAL Id: hal-04716541

https://inria.hal.science/hal-04716541v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

UPDATE SEMANTICS
OF RELATIONAL VIEWS

<figure><img src="image_3.png" /></figure>

François BANCILHON
Nicolas SPYRATOS

Rapport de Recherche N° 329

Octobre 1978

34P.
# UPDATE SEMANTICS OF RELATIONAL VIEWS

François Bancilhon*, Nicolas Spyratos**

## Résumé :

La plupart des systèmes de gestion de base de données existants offrent à l'usager la possibilité de définir sa propre vue de la base. Ces vues ne sont pas implémentées mais simplement définies par l'usager, les requêtes sur une vue étant «traduites» en requêtes sur la base originelle. Toutefois le problème de la répercussion des mises à jour est plus délicat et on se propose de l'étudier ici dans le contexte du modèle relationnel.

On définit tout d'abord les notions de vue, de mise à jour et de traduction d'une mise à jour. Ensuite on propose une méthode de traduction : on définit outre la vue usager une vue complémentaire telle qu'à partir de ces deux vues la base originelle puisse être recalculée. La mise à jour est ensuite traduite de telle façon que seule la vue usager est modifiée pendant que son complément reste inchangé. On donne les conditions dans lesquelles une telle traduction génère une mise à jour sémantiquement cohérente.

Ensuite, on montre que chaque vue peut avoir (en théorie et en pratique) plusieurs compléments et que c'est le choix de ce complément qui détermine une politique de mise à jour.

Enfin, on montre que cette méthode de traduction est universelle ; en effet, pour toute traduction il existe un complément qui la génère.

## Abstract :

A data base view is a portion of the data base structured in a way which is relevant to the user's application. However, such views are not actually implemented; they are simply «defined» by the user. Therefore, update requests issued by the user within the context of his view must be translated into updates on the underlying data base. It is the purpose of this paper to formalize the notion of view and view update and study the translation process. This is done in the context of the relational model for data bases.

We first define formally the notion of a view and that of a view update and its translation into a data base update. We then propose a method for translating view updates: together with the user defined view, we define a «complementary» view such that the data base can be computed from the view and its complement; a view update is then translated in such a way that only the view is changed while its complement remains unchanged («translation under constant complement»); conditions are given for this translation to be semantically consistent. Next, we show that a view can have many different complements and that the choice of a complement determines an update policy. Finally, we establish ge generality of our method by showing that any translation of a view update is a translation under some constant complement.

<footnote>* IRIA/LABORIA, B.P. 105 - 78150 Le Chesnay (France)</footnote>

<footnote>**Université d'Orléans, Département de Mathématiques, Orléans (France)</footnote>
Key words : Update, Relational View, View update, update translation,
data base semantics, Relational Model.
# I - INTRODUCTION

A data base is generally used by a community of users. Most of these users are actually interested in only a small part of this data base and they do not necessarily want to see this part of data named and structured as the data base administrator has decided. To meet these two user requirements most data base management systems provide a facility known as the "user view". That user view defines the specific subset the user is interested in together with the structuring he desires.

As long as the user interaction with the data base consists only of queries, it is fairly easy to support this facility : the view definition function is used to translate the user's queries from view queries into queries on the actual data base. However things get more complex when the user is allowed to update his view. It is this specific problem that we address in this paper. We restrict our attention to the case of the relational model. After briefly reminding the basic definitions from that model, we define formally the notion of a view and an update. This allows us to formulate the view update problem. Then we introduce a mathematical model that permits the specification of a method to handle view updates. Finally we show that there can be different manners of handling updates and that more information is needed about the view definition to choose among these different alternatives. The extra information needed is characterised as another view, "complementary" to the user's view. Finally the generality of the view update handling method is demonstrated. However, the actual implementation of the method and the study of the necessary algorithms are not presented here and are under current study.

# II - THE RELATIONAL MODEL.

In this section, we review the basic definitions from the relational model and we introduce our notation. Central to the relational model is the notion of a relation. A relation is specified by a relational descriptor of the form :

$$R(A_1:D_1, \dots, A_i:D_i, \dots, A_n:D_n)$$
R is the relation name, the Aᵢ's are the attribute names and the Dᵢ's
are the associated domains. We shall not be too concerned with domains
and they will be left implicit, thus denoting the descriptor by
R(A₁,A₂,...,Aₙ). The attribute set {A₁,...,Aₙ} is usually denoted by U.

With the relational descriptor R(A₁:D₁,...,Aₙ:Dₙ), we can
associate specific values, that are finite subsets of the cartesian pro-
duct D₁ × D₂ × ... × Dₙ. Values of the descriptor will in general be
denoted by subscripting the relation name R, i.e :

$$
R_{\tau} \subseteq D_{1} \times D_{2} \times \dots \times D_{n}
$$

Relation values are represented in the usual tabular form, where rows
represent tuples and columns attributes.

A data base consists of one or several relations taking at each
instant specific values. Thus a data base is defined by a set R = (R₁, R₂, ..., Rₚ)
of relational descriptors that we call the data base descriptor.
With that descriptor, at each instant t, we can associate a data base
value R<sub>t</sub> = (R<sub>1t</sub>, R<sub>2t</sub>, ..., R<sub>pt</sub>) by assigning a value R<sub>it</sub> to each relation
R<sub>i</sub> of the data base. The set of values that the data base can take is
the data base schema, denoted S. That schema is in general specified by
a set of integrity constraints that the values must satisfy. In the absence
of integrity constraints, the schema is called the free schema, denoted by
S<sub>F</sub>(R). It consists of all the possible values that the data base descriptor
can take. Examples of integrity constraints are functional dependencies as
defined in [Codd 72]. The reader will be assumed familiar with the notions
of projection and join of relations : the projection of the relation
value R<sub>τ</sub> on the attribute subset X is denoted R<sub>τ</sub>(X) and the join of the
two relation values R<sub>Iτ</sub>' and R<sub>Iτ</sub> is denoted R<sub>Iτ</sub> * R<sub>Iτ</sub>.'
### III - THE VIEW UPDATE PROBLEM

A data base usually consists of a number of relations shared by different users. It has been structured by the data base administrator, and this structuring can be done in many different ways (even third or fourth normal forms are not unique). It is therefore very conceivable that a given user on one side is not interested in the entire data base and on the other side would like to see his data structured in a different manner. The notion of the user's view was specifically introduced to meet these two requirements : It allows the user to define exactly what part of the data he is interested in and to name and structure his data as he desires, thus creating his own virtual data base.

Consider for instance the data base descriptor :

$R_1(\text{EMPLOYEE,DEPARTMENT})$

$R_2(\text{DEPARTMENT,MANAGER})$

and an associated schema specified by the two functional dependencies :

<figure><img src="image_4.png" /></figure>

A user of this data base might be concerned only with the relationship between employees and managers. Consequently he would like to view the data as a single base relation

$R_3(\text{EMPLOYEE,MANAGER})$

defined from the original ones by joins and projections. How are we going to give the user the ability to operate on $R_3$? It is of course not practical to build the actual $R_3$ relation : for each new user's view we would have to implement a new relation. Therefore, we simply want to give the user the feeling that the $R_3$ relation is available to him. When the user wants to query his relation, we translate his query on $R_3$ into a query on $R_1$ and $R_2$. For instance :
"List all employees working under manager Jones"

Will be translated into:

"List all employees working in a department whose manager is Jones"

As one can see, queries can be handled in a fairly straightforward manner; this paper is concerned with the problem of handling updates which happens to be much more complex.

Let us summarize the study of the previous example by saying that there are three concepts involved:

(i) the view descriptor $R_3$

(ii) the view value, i.e. the actual value taken to be the user's view at a given instant and,

(iii) the view definition function, i.e. the process by which we can compute the view value from the data base value.

Let us now state this formally.

**Definition III-1.**

Let $R = (R_1, R_2, ..., R_n)$ be a data base descriptor and let $S$ be a schema defined on $R$. Let $r = (r_1, r_2, ..., r_p)$ be another data base descriptor called the *view descriptor*. A *view* is a mapping $f: S \to S_F(r)$. [ ]

That is, the view $f$ associates with each data base value $R_T$ of $S$ a view value $r_T=f(R_T)$ of $S_F(r)$. In general we shall use uppercase letters for variables concerning the data base and lower case letters for variables concerning the user's view. Usually not all values of $S_F(r)$ are view values. The set $f(S)$ which consists of all the values that the view descriptor can take is the *view schema*. It can also be specified by a set of integrity constraints (In ANSI/SPARC terminology it is the user's subschema).
We shall denote by M(S) the set of view mappings that can be defined on S. These mappings are usually specified through a set of computation rules. We shall not specify here what set of computation rules is adopted, since the theory we present is independent of the type of rules chosen. Only when we want to implement actual algorithms should we worry about that problem. Throughout the paper, all examples will involve well known rules from relational algebra and arithmetic. For instance, the projection mapping is defined as follows :

Let $R = (R_1, R_2, ..., R_n)$ be the data base descriptor. The projection mapping $\Pi R_i(X)$ is the function that associates with the data base value $R_T = (R_{t1}, ..., R_{i1}, ..., R_{n1})$ the view value $R_{i1}(X)$, i.e. $\Pi R_i(X)(R_T) = R_{i1}(X), \forall R_T \in S$.

From now on, we shall make the following abuse of notation : we shall write $R_i(X)$ for the *mapping* $\Pi R_i(X)$. It should however be kept in mind that by $R_i(X)$ we do not mean the descriptor nor the actual view value but the mapping.

Let us now review the example presented at the beginning of this section to clarify these definitions :

The data base descriptor is :

$$R = (R_1(EMP, DEPT), R_2(DEPT, MGR))$$

And the associated schema is specified by the functional dependancies :

$$R_1 : EMP \to DEPT \quad ; \quad R_2 : DEPT \to MGR$$

The view descriptor is :

$r(\text{emp}, \text{mgr})$

The view definition function is the mapping $f$ defined by :

$$r_T(\text{emp}, \text{mgr}) = (R_{1T}(\text{EMP}, \text{DEPT}) * R_{2T}(\text{DEPT}, \text{MGR})) (\text{EMP}, \text{MGR})$$
This defines a view schema specified by :

$r : \text{emp} \rightarrow \text{mgr}$

We now turn to the definition of updates. An update U on a schema S is a function from S into S, that associates with each data base value R<sub>τ</sub> ∈ S, its updated version U(R<sub>τ</sub>). Actually updates can be defined as sequences of tuple-insertions, tuple-deletions and tuple-modifications and whenever we consider examples they will appear under that form. However, to discuss the problem of update semantics it is sufficient to stay at the level of generality where an update is just any mapping U : S → S.

This definition implies that all updates are well defined, i.e. that U(S) ⊆ S. In other words, by taking any data base value R<sub>τ</sub> ∈ S and applying update U we get a new value U(R<sub>τ</sub>) that satisfies the integrity constraints of the schema, i.e. U(R<sub>τ</sub>) ∈ S.

As an example consider the data base described by

$R(PART, PRICE)$

and the associated schema specified by the integrity constraints :

$PART \rightarrow PRICE \quad \text{and} \quad \forall x \in R_T, x.PRICE \ge 0.$

The function U defined by "Decrease the price of part Bolt by $5" is not an update since it might lead to a semantic inconsistency (a negative price if the price of a bolt is less than $5). While the function U' defined by "Decrease the price of part Bolt by $5 if that price is greater than $6" is an update.

We have now described in formal terms a view as a mapping $f : S \rightarrow f(S)$ and a view update as a mapping $u : f(S) \rightarrow f(S)$. Let us look into the view update problem.

At a given time $\tau$, the data base is in the state $R_{\tau}$; the user's view is in the state $r_{\tau} = f(R_{\tau})$. The user wants to update his view by $u$, i.e. change from state $r_{\tau}$ to state $r'_{\tau} = u(r_{\tau})$. The problem is that $r_{\tau}$
does not physically exist (at least in the general case). Therefore, if we want to update something it must be $R_{\tau}$. Hence we must change from state $R_{\tau}$ to a new state $R'_{\tau} = U(R_{\tau})$. That new state must of course be such that the view that stems from it is what the user expects i.e. $r'_{\tau}$. Therefore we can write

$$f(U(R_{\tau})) = u(f(R_{\tau}))$$

This is represented by fig. III-1.

<figure><img src="image_5.png" /><figcaption>Fig. III-1 : Updating a view</figcaption></figure>

Since this property must be true for all $R_{\tau} \in S$ we have $f \circ U = u \circ f$. We can also say that the following diagram commutes :

<figure><img src="image_6.png" /></figure>

This leads us to the following definition :

### Definition III-2.

Let S be a schema, let f be a view on S and let u be an update of $f(S)$. We say that update $U : S \to S$ is a translation of u iff $f \circ U = u \circ f$. □

As anybody familiar with the problem knows, there might be several possible translations of a given update u. For instance we can think about
changing in the data base things which are totally unrelated to the
view. It is also clear that some of these translations are meaningless.
In order to restrict our attention to meaningful ones we introduce the
notion of admissibility :

**Définition III-3.**

Let S be a schema, let f be a view on S, let u be an update on
that view and let U : S → S be a translation of u. We say that U is
admissible iff $u^n(f(R_τ)) = f(R_τ) \Rightarrow U^n(R_τ) = R_τ$, $\forall R_τ \in S, \forall n \ge 0$. □

The admissibility condition simply states that if the user
does a sequence of updates on his view that leaves this view invariant
$(u^n(f(R_τ)) = f(R_τ))$ then the original data base should remain unchanged.
For instance if the user asks for the insertion of some tuple in his
view and that this tuple is already present the view is going to remain
unchanged. It is only natural to require that the original data base
won't be modified either. Or if the user inserts a tuple then deletes
it, it should be expected that nothing has changed.

From now on we shall restrict our attention to admissible trans-
lation and by "translation" we shall mean "admissible translation".

Now, given a schema S, a view f and an update u of this view there
are four basic questions that one must ask to solve the update problem :

(i) Does there exist a translation U of u ?

(ii) Is it unique ?

(iii) If it is not, how can we choose among the candidates ?

(iv) How can we effectively compute the translation U.

This paper essentially deals with the three first questions. We
do recognize that the fourth one is very important but it has seemed to
us that a good understanding of the three first was necessary to
answer the fourth.
In the literature the first ones to tackle this problem were the designers of relational systems. In INGRES [Stonebraker 75] and in System R [Chamberlin et al 75] views are implemented by query modification and in the case of system R they are also used for protection. For view updates the approach generally taken is to simply forbid them.

The first formalisation of the problem is in [Paolini and Pelagati 77] where it is studied in the context of mapping several user's views into one single conceptual schema. In [Furtado and Sevcik 78] the effect of specific update operations (insert, delete and modify) on views obtained by operations from a relational algebra is studied together with the problem of preserving semantic consistency. Finally, in [Dayal and Berstein 78] a formal criterion for translation is given and algorithms, to do the actual translation in the case where schemas are specified by functional dependencies are presented. This last paper is more oriented toward the computational aspect of the problem and we shall discuss it in more detail later.

## IV - THE MATHEMATICAL MODEL

In this section we develop the mathematical framework needed to solve the update problem. Our first task is to study the set M(S) of views that can be defined on schema S. As mentioned in the previous section we do not worry about the content of M(S) but rather about its structure.

### Definition IV.

Let S be a schema. Let f and g be two mappings of M(S). We say that f is **greater** than g or that f **determines** g (denoted $f \geq g$), iff

$$f(R_1) = f(R_2) \Rightarrow g(R_1) = g(R_2) \quad \forall R_1, R_2 \in S \quad \square$$

**Example 1:** Let the data base be described by a single descriptor R(U) and let X and Y be two subsets of the set of attributes U, then :

$$Y \subseteq X \Rightarrow R(Y) \leq R(X)$$
For instance in R(EMPLOYEE, DEPARTMENT, MANAGER) :

$$R(EMPLOYEE) \leq R(EMPLOYEE, MANAGER)$$

Example : Let the data base be described by :

$$R_1(EMPLOYEE, DEPARTMENT), R_2(DEPARTMENT, MANAGER, NUMBER OF EMPS)$$

Let the associated schema be specified by :

$$R_1 : EMPLOYEE \rightarrow DEPARTMENT$$

$$R_2 : DEPARTMENT \rightarrow MANAGER, NUMBER-OF-EMPS$$

and the "NUMBER-OF-EMPS" attribute represent the actual number of employees per department.

Then we have :

$$R_1(EMPLOYEE, DEPARTMENT) \geq R_2(DEPARTMENT, NUMBER-OF-EMPS)$$

Example : Let the data base be described by :

$$R(PART \#, COST, SALEPRICE, PROFIT)$$

Let the associated schema be specified by :

$$PART \# \rightarrow COST, SALEPRICE, PROFIT$$

$$\text{and } \forall x, x \in R_{\tau}, x.\text{PROFIT} = x.SALEPRICE - x.COST.$$

Then we have :

$$R(PART \#, COST, SALEPRICE) \geq R(PART \#, PROFIT)$$

As these examples indicate, $f \geq g$ means that whenever we know the value $f(R_{\tau})$ we also know (i.e., we can compute from $f(R_{\tau})$) the value $g(R_{\tau})$. Note however, that this is a relation between mappings and not between relation values.
This relation can be interpreted as follows: Let $S/f$ and $S/g$ be the quotient sets of $S$ by $f$ and $g$, respectively. Recall that $S/f$ is the partition induced by $f$ on $S$ (where two relation values $R_1$ and $R_2$ belong to the same bloc of the partition iff $f(R_1) = f(R_2)$). Also recall that the partition $S/f$ is said to be a refinement of the partition $S/f$ iff each block of $S/f$ is contained in a block of $S/g$. The following theorem is a consequence of definition IV-2.

**Theorem IV-1.**

$f \ge g$ iff $S/f$ is a refinement of $S/g$. $\square$

And an immediate consequence is that :

**Theorem IV-2.**

The relation $\ge$ is reflexive, transitive but not antisymmetric.

<figure><img src="image_7.png" /></figure>

Theorem IV-1 implies that the only information we need for ordering $f$ and $g$ is the partitions $S/f$ and $S/g$. As the relation $\ge$ is not antisymmetric, we introduce the equivalence relation associated with it.

**Definition IV-3.**

Let $f$ and $g$ be two mappings of $M(S)$. We say that $f$ and $g$ are equivalent (denoted $f \equiv g$) iff $f \ge g$ and $g \ge f$. $\square$

<figure><img src="image_8.png" /></figure>

It follows from Theorem 2 that $f \equiv g$ iff $S/f = S/g$ i.e., iff $f$ and $g$ induce the same partition on $S$.

We denote by $l_S$ the identity mapping on $S$ and by $O_S$ the "always true" mapping on $S$ that associates with any value $R \in S$ the value "true". The partition induced by $l_S$ is the one where each block consists of a single element (i.e., $l_S$ is equivalent to any injective mapping of $M(S)$). The partition induced by $O_S$ consists of only one block equal to $S$ (i.e. $O_S$ is equivalent to any constant mapping). The following theorem is an immediate consequence of definition IV-2.
**Theorem IV-3.**

$$ \forall f \in M(S), O_S \le f \le l_S \quad \Box $$

We now give an example of equivalence :

Let us consider again the data base described by :

$R_1(EMP, DEPT)$

$R_2(DEPT, MGR, NUMB-OF-EMP)$

We define the mapping $f$ by :

$$ f(R_{1\tau}, R_{2\tau}) = R_{1\tau}(EMP, DEPT) * R_{2\tau}(DEPT, MGR) $$

and we have $f \equiv l_S$. This simply means that the new view is equivalent to the original schema in the sense that we can recompute the original relations from the view.

In summary, two mappings $f$ and $g$ are equivalent if knowing the value $f(R_\tau)$ we can compute the value $g(R_\tau)$ and conversely (for every $R_\tau$ in the schema). Note again that this notion of equivalence applies only to mappings and not to relation values.

We now define a binary law on $M(S)$ :

**Definition IV-4 :**

Let $f$ and $g$ be mappings from $M(S)$. Their product $f \times g$ is a mapping of $M(S)$ defined by $f \times g(R_\tau) = (f(R_\tau), g(R_\tau))$, $\forall R_\tau \in S$. $\Box$

**Example :** Let the data base be described by $R(EMP, DEPT, MGR)$ and the schema be specified by the functional dependencies: $EMP \rightarrow DEPT$ and $DEPT \rightarrow MGR$.

Then $l_S \equiv R(EMP, DEPT) \times R(DEPT, MGR)$. This is a classical result from decomposition theory. Note, however, that it has nothing to do with joins : the mapping $f \times g$ simply represents the juxtaposition of view $f$ and view $g$. When this juxtaposition of views produces a schema equivalent to $S$ then the views are "complementary".
**Definition IV-5 :**

Let $f$ be a mapping of $M(S)$. A *complement* of $f$ is a mapping $g$ of $M(S)$ such that $f \times g \equiv l_S$ $\square$

Of course, if $g$ is a complement of $f$ then $f$ is a complement of $g$.
Note that $l_S$ is a complement of $O_S$

**Example :** Let the database be described by $R(NAME,ADDRESS,TEL)$, let the schema be specified by the functional dependency : $NAME \to ADDRESS,TEL$ and let $f = R(NAME,ADDRESS)$. Then $g = R(NAME,TEL)$ is a complement of $f$.

Intuitively the complement $g(R_τ)$ of $f(R_τ)$ is the "extra information" that we must give together with $f(R_τ)$ to be able to recompute $R_τ$. It should be noted that $l_S$ is the complement of any $f$ in $M(S)$. This shows that any mapping has at least one complement.

# V - TRANSLATING UNDER A CONSTANT COMPLEMENT

Let us now discuss the view update problem in intuitive terms.
At a given time $τ$ the data base has some value $R_τ$. The user is interested only in his own data $r_τ = f(R_τ)$ and he wants to update it by changing it to some $r'_τ = u(r_τ)$. Our problem is to translate that change u in $f(S)$ into a change U from $R_τ$ to some $R'_τ$ in S. One simple way to do such a translation is to consider the user's view $r_τ$ as a "subset" of the data base and to update that subset while leaving the rest of the database unchanged. Such a method is fairly natural at first view. Consider for instance a data base described by :

$$R_1(EMP,AGE,SAL,DEPT), R_2(DEPT,MGR)$$

and consider the view defined by

$$R_1(EMP,AGE,SAL,DEPT)$$

i.e. by restricting our attention to one single relation.
If we want to update an employee record, this can be done easily while leaving the value of R₂ unchanged. In this case the notion of the "rest" of the data base is fairly straightforward since it can be partitionned into two "independent" parts. However, in the general case it might be more difficult to define the "rest" and it might also be more difficult to update one part while leaving the other constant.

Consider the data base described by :

$R_1 (EMP, DEPT), R_2 (DEPT, MGR, NUMB-OF-EMP)$

and the view defined by $R_3 (EMP, MGR)$.

What is the "rest" of the data base ? (i.e., what is left out of $R_3$ ?
It could be $R_1 (EMP, DEPT)$ or $R_2 (DEPT, MGR)$ or $R_2 (DEPT, MGR, NUMB-OF-EMP)$.

At this point it is appropriate to make use of the notion of complement as defined in the previous section. For instance the view

$R_1 (EMP, DEPT)$

is a complement of $R_3$ and it indeed represents what we intuitively understand as the "rest" of the data base.

Now that we have a view f and its complement g, the translation problem can be restated as follows : In the state $R_T$ of the data base, the user's view has value $r_T = f(R_T)$. The user wants to move from value $r_T$ to $r'_T$. Since g is a complement of f, we can replace the data base value $R_T$ by the equivalent couple $(f(R_T), g(R_T))$. Under this equivalent representation, if we want to change $r_T$ to $r'_T$ while leaving g constant, all we have to do is move to the new representation $(r'_T, g(R_T))$. Then, since $f \times g = l_S$, we can recompute $U(R_T)$ from $(r'_T, g(R_T))$ by applying $(f \times g)^{-1}$. This process is illustrated by Figure V-1.
<figure><img src="image_9.png" /><figcaption>Figure V-1</figcaption></figure>

On the left hand side of the figure, we have the data base schema S and a data base value $R_T$. On the right hand side, we have an equivalent representation obtained by replacing $R_T$ by $(f(R_T), g(R_T))$. To modify the view value $f(R_T)$ while leaving $g(R_T)$ constant, we simply move along a line parallel to the f-axis. Then we come back to the original schema, through $(f \times g)^{-1}$ (which exist because $f \times g \equiv I_S$).
This leads us to the following definition :

**Definition V-1 :**

Let S be a schema, let $f \in M(S)$ be a view and let $u$ be an update of that view. Let $g$ be a complement of $f$. The translation of $u$ under constant $g$ (or the g-translation of $u$) is the mapping $U$ defined on S by :

$$U(R_T) = (f \times g)^{-1} (u(f(R_T)), g(R_T)), \forall R_T \in S) \quad \square$$

The following Theorem is an immediate consequence of this definition :

**Theorem V-1.**

Let S be a schema, let $f \in M(S)$ be a view, let $u$ be an update of $f(S)$, let $g$ be a complement of $f$ and let $U$ be the translation of $u$ under
constant g then :

$$
(i) \quad f(U(R_{\tau})) = u(f(R_{\tau})), \quad \forall R_{\tau} \in S
$$

$$
(ii) \quad g(U(R_{\tau})) = g(R_{\tau}), \quad \forall R_{\tau} \in S \quad \Box
$$

Part (i) of the theorem states that U is indeed a translation of u
and part (ii) states that this translation is done under constant g.

U has been defined as a mapping on S. However we should worry
about the fact that U must be an update of S. When we defined updates,
we insisted on the fact that an update should always lead to a semanti-
cally consistent new state i.e. :

$$
\forall R_{\tau} \in S, U(R_{\tau}) \in S \text{ or } U(S) \subseteq S.
$$

Let us now see if the translation of U under constant g satisfies
this condition : For U(R ) to belong to S we must have

$$
(u(f(R_{\tau})), g(R_{\tau})) \in f \times g(S)
$$

or $R_1 \in S$ such that :

$$
(u(f(R_{\tau})), g(R_{\tau})) = f \times g(R_1)
$$

or $u(f(R_{\tau})) = f(R_1)$ and $g(R_{\tau}) = g(R_1)$.

Since this must be true for any $R_{\tau} \in f^{-1}(r)$ it must be the case that :

$$
g(f^{-1}(r)) \subseteq g(f^{-1}(u(r))) \quad \forall r, r \in f(S) .
$$

This condition is illustrated by Figure V-2.

Figure V-2-a, shows the case where U(R) ∈ S and Figure V-2-b, shows the
case where U(R) ∉ S .
<figure><img src="image_10.png" /><figcaption>Figure V-2</figcaption></figure>

These remarks can be summarized by the following definition :

**Definition V-2 :**

Let S be a schema, $f \in M(S)$ be a view, u be an update of that view, and g be a complement of f. u is **consistently translatable under constant g iff** :

$$g(f^{-1}(r)) \subseteq g(f^{-1}(u(r))), \quad \forall r, r \in f(S) \quad \Box$$

And as an immediate consequence we can state the following theorem :

**Theorem V-2 :**

Let S, f, u and g be as above. If u is consistently translatable under constant g, then the g-translation U of u is an update on S. In that case we say that U is the **consistent g-translation of u**. $\Box$

In general, when taking any S, f, u, and g, u is not consistently g-translatable. Let us investigate some examples to see what different cases we can encounter :
**Example** : Let the data base be described by :

$R_1(EMP,DEPT); R_2(PART #,PRICE)$

Let the view f be defined by $f = R_1$ and its complement g be $R_2$. Then in this case *any update u on* $R_1$ *is consistently R*-**_translatable_**. This is generally the case when the view and its complement are fully independent.

**Example** : Consider the data base described by :

$R(STUDENT,EXAM,HOUR)$

And an associated schema specified by :

STUDENT,HOUR → EXAM and EXAM → HOUR.

Let the view f be $R(STUDENT,EXAM)$. Then $g = R(EXAM,HOUR)$ is a complement of R.

Consider the update u on f defined by :

"Student Smith drops Math exam"

This update is consistently g-tranla table (i.e. we can **in all cases** update R(STUDENT,EXAM) while keeping R(EXAM,HOUR) unchanged and stay in a semantically consistent state).

On the contrary consider update u' defined by :

"Student Smith registers to Latin exam"

u' is **not** consistently $R_2$-translatable since in some cases this update would lead us to a semantically inconsistent state (a violation of $STUDENT,HOUR \rightarrow EXAM$, i.e. a timetable conflict).
Finally, we are unable to exhibit any practical example of a
couple (f,g) where no update but the identity (which is of course
always consistently g-translatable for any g) is consistently g-trans-
latable. However the case cannot be theoretically excluded. We end
this section by presenting a complete example of an update translation.

Consider a data base described by :

$R_1 (EMP, SAL, DEPT)$

$R_2 (DEPT, MGR, \# EMP)$

Because we do not want to burden this presentation with lengthy
notation, we shall assume that we have defined a *count* mapping that
computes the number of attribute values related to another attribute
value. Then the associated schema can be specified by the following
integrity constraints :

(1) $R_1 : EMP \to SAL, DEPT$

(2) $R_2 : DEPT \to MGR, \# EMP$

(3) $R_{2T}(DEPT, \# EMP) = \underline{\underline{\text{count}}}(R_{1T}(DEPT, EMP))$

Now, we define the following view descriptor :

`r(EMP,DEPT,MGR)`

And the view mapping $f$ :

$r_T(EMP, DEPT, MGR) = R_{1T}(EMP, DEPT) * R_{2T}(DEPT, MGR)$

The view $g = R_1(EMP, SAL)$ is a complement of $f$. Consider now, the data
base value $R_T = (R_{1T}, R_{2T})$ given by :

<table><thead><tr><th>R<sub>1T</sub></th><th>EMP</th><th>SAL</th><th>DEPT</th></tr></thead><tbody><tr><td></td><td>Smith</td><td>10000</td><td>Car</td></tr><tr><td></td><td>Martin</td><td>12000</td><td>Car</td></tr><tr><td></td><td>Jones</td><td>11000</td><td>Sales</td></tr><tr><td></td><td>Doe</td><td>10000</td><td>Sales</td></tr><tr><td></td><td>Adams</td><td>12000</td><td>Sales</td></tr></tbody></table>

<table><thead><tr><th>R<sub>2T</sub></th><th>DEPT</th><th>MGR</th><th>#EMP</th></tr></thead><tbody><tr><td></td><td>Car</td><td>Martin</td><td>2</td></tr><tr><td></td><td>Sales</td><td>Adams</td><td>3</td></tr></tbody></table>
It yields the view value represented by :

<table><thead><tr><th>r<sub>τ</sub></th><th>EMP</th><th>DEPT</th><th>MGR</th></tr></thead><tbody><tr><td></td><td>Smith</td><td>Car</td><td>Martin</td></tr><tr><td></td><td>Martin</td><td>Car</td><td>Martin</td></tr><tr><td></td><td>Jones</td><td>Sales</td><td>Adams</td></tr><tr><td></td><td>Doe</td><td>Sales</td><td>Adams</td></tr><tr><td></td><td>Adams</td><td>Sales</td><td>Adams</td></tr></tbody></table>

Consider the update on that view defined by:

"Move Jones to the car department"

This would yield (in the user's mind) the new view value :

<table><thead><tr><th>r'<sub>τ</sub></th><th>EMP</th><th>DEPT</th><th>MGR</th></tr></thead><tbody><tr><td></td><td>Smith</td><td>Car</td><td>Martin</td></tr><tr><td></td><td>Martin</td><td>Car</td><td>Martin</td></tr><tr><td></td><td>Jones</td><td>Car</td><td>Martin</td></tr><tr><td></td><td>Doc</td><td>Sales</td><td>Adams</td></tr><tr><td></td><td>Adams</td><td>Sales</td><td>Adams</td></tr></tbody></table>

The complement $g$, in the original data base value, takes the following value :

<table><thead><tr><th>g(R<sub>τ</sub>)</th><th>EMP</th><th>SAL</th></tr></thead><tbody><tr><td></td><td>Smith</td><td>10000</td></tr><tr><td></td><td>Martin</td><td>12000</td></tr><tr><td></td><td>Jones</td><td>11000</td></tr><tr><td></td><td>Doc</td><td>10000</td></tr><tr><td></td><td>Adams</td><td>12000</td></tr></tbody></table>

Now we must recompute $U(R)$ by applying the mapping $(f \times g)^{-1}$ to the new data base value $(r'_τ, g(R_τ))$. The inverse mapping $(f \times g)^{-1}$ is defined by :
$$R_{1T}(EMP, SAL, DEPT) = (r_{T}(EMP, DEPT) * R_{T}(EMP, SAL))$$

$$R_{2T}(DEPT, MGR, \#EMP) = r_{T}(EMP, MGR) * R_{4}(DEPT, \#EMP)$$

$$\text{where } R_{4}(DEPT, \#EMP) = \text{count}(r_{T}(EMP, DEPT))$$

The application of this inverse mapping yields the following new data base value :

<table><thead><tr><th>R<sub>1</sub></th><th>EMP</th><th>SAL</th><th>DEPT</th></tr></thead><tbody><tr><td></td><td>Smith</td><td>10000</td><td>Car</td></tr><tr><td></td><td>Martin</td><td>12000</td><td>Car</td></tr><tr><td></td><td>Jones</td><td>11000</td><td>Car</td></tr><tr><td></td><td>Doc</td><td>10000</td><td>Sales</td></tr><tr><td></td><td>Adams</td><td>12000</td><td>Sales</td></tr></tbody></table>

<table><thead><tr><th>R<sub>2</sub></th><th>DEPT</th><th>MGR</th><th>#EMP</th></tr></thead><tbody><tr><td></td><td>Car</td><td>Martin</td><td>3</td></tr><tr><td></td><td>Sales</td><td>Adams</td><td>2</td></tr></tbody></table>

We do not suggest by this example to use this method for computing the new data base value ! We are only interested here in the semantics of the update process.

## VI - THE MULTIPLICITY OF COMPLEMENTS

In the preceding section, we proposed a translation scheme for view updating. This scheme is based on the separation of the data base into the user's view f(R<sub>T</sub>) and its complement g(R<sub>T</sub>). The question immediately arises whether this complement is unique. The answer is no, as the following theorem shows.

### Theorem VI-1.

Let $f \in M(S)$. Let $g$ be a complement of $f$. If $g' \ge g$ then $g'$ is a complement of $f$, $\forall g' \in M(S)$. □

<figure><img src="image_11.png" /></figure>
**Proof :** As $g' \ge g$, $g'(R_1) = g'(R_2) \Rightarrow g(R_1) = g(R_2)$, $\forall R_1, R_2 \in S$.
Therefore, $(f(R_1), g'(R_1)) = (f(R_2), g'(R_2)) \Rightarrow (f(R_1), g(R_1)) = (f(R_2), g(R_2))$, $\forall R_1, R_2 \in S$. That is, $f \times g'(R_1) = f \times g'(R_2) \Rightarrow f \times g(R_1) = f \times g(R_2)$, $\forall R_1, R_2$. It follows from Definition 2 that $f \times g' \ge f \times g$. As $g$ is a complement of $f$ we have $f \times g \equiv l_S$, hence $f \times g' \ge l_S$. It follows from Theorem 2 that $f \times g' \le l_S$. Therefore, $f \times g' \equiv l_S$, and $g'$ is a complement of $f$. Q.E.D.

This result is intuitively satisfactory : It means that if we can reconstruct the original data base by adding $g$ to $f$ then we can certainly do so by adding to $f$ anything "bigger" than $g$.

Now that we know that there can be different choices for the complement, let us see how these choices might affect the translation process.

**Theorem VI-2.**

Let $f \in M(S)$. Let $g$ and $g'$ be two complements of $f$ such that $g' \ge g$. Let $u$ be an update of $f(S)$. If $u$ is consistently $g'$-translatable then (1) $u$ is consistently $g$-translatable and (2) the $g'$-translation of $u$ is equal to the $g$-translation of $u$. $\square$

**Proof :** (1) We have to show that : $g(f^{-1}(r)) \subseteq g(f^{-1}(u(r)))$, $\forall r \in f(S)$.
As $u$ is $g'$-translatable, we have : $g'(f^{-1}(r)) \subseteq g'(f^{-1}(u(r)))$, $\forall r \in f(S)$.

This implies that $\forall R_1 \in f^{-1}(r)$ there exists $R_2 \in f^{-1}(u(r))$ such that $g'(R_1) = g'(R_2)$. Since $g' \ge g$, it follows that $g(R_1) = g(R_2)$. That is, $\forall R_1 \in f^{-1}(r)$ there exists $R_2 \in f^{-1}(u(r))$ such that $g(R_1) = g(R_2)$. Therefore, $g(f^{-1}(r)) \subseteq g(f^{-1}(u(r)))$, $\forall r \in f(S)$. Q.E.D.

(2) Let $U$ be the $g'$-translation of $u$. Then $U(R) = (f \times g')^{-1}(u(f(R)), g'(R))$, $\forall R \in S$, and $g'(U(R)) = g'(R)$. Since $g' \ge g$, it follows from (1) that $g(U(R)) = g(R)$ i.e., $U(R) = (f \times g)^{-1}(u(f(R)), g(R))$. Q.E.D.
**Example :** Let the data base be described by :

$R_1(EMP,SAL,DEPT)$ and $R_2(DEPT,MGR,\#EMP)$

with the usual meaning attached to these relations.

Let the view be $f = R_1(EMP,SAL,DEPT)$. A complement of $f$ is
$g_1 = R_2(DEPT,MGR,\#EMP)$. But another one is $g_2 = R_2(DEPT,MGR)$.

Consider for instance the problem of translating the update
$u = \text{"raise all employees salaries by 5%"}$. $u$ is consistently trans-
latable under $g_1$ and $g_2$ constant and clearly both translations have
the same result. However if we think of the update :

$u' = \text{"hire employee Jones with salary 10000 in the}$
$\text{car department"}$

$u'$ is consistently $g_2$ translatable, but it is _not_ consistently $g_1$ translatable.

Theorem VI-2 implies that as the complement $g$ (of a view $f$) becomes smaller the set of $g$-translatable updates becomes larger. Thus, given a view $f$, we have interest in choosing the smallest possible complement of $f$ for the translation process. This fact leads to the notion of a minimal complement.

**Definition VI-1.**

Let $f \in M(S)$. A _minimal complement_ of $f$ is a mapping $g \in M(S)$ such that (i) $g$ is a complement of $f$ and (ii) if $g'$ is a complement of $f$ and $g' \le g$ then $g' \equiv g$. $\square$

We saw earlier that the complement of a view $f$ is not unique.
we now ask the question : is the minimal complement unique ? The
answer is again no, as the following theorem shows.
**Theorem VI-3.**

A mapping $f \in M(S)$ has a unique minimal complement iff $f \equiv 1_S$ or $f \equiv 0_S$.

Before proving this theorem let us emphasize that we consider uniqueness up to an equivalence.

*Proof.* Assume $f \not\equiv 1_S$ and $f \not\equiv 0_S$. Let $g$ be a minimal complement of $f$. We want to exhibit a minimal complement $g'$ of $f$ such that $g' \neq g$. Since $S/f$ is neither $S/0_S$ nor $S/1_S$, it must contain two distinct blocks $B_1$ and $B_2$ such that $|B_1| \ge 1$ and $|B_2| \ge 2$.

Let $a \in B_1$ and assume that $g(a) \neq g(x)$, $\Psi x \in B$. Then we can define a mapping $g_1$ such that (i) $g_1(x) = g(x)$, $\Psi x \neq a$, (ii) $g_1(a) = g(b)$ for some $b \in B_2$.

We have : $g_1 \times f = 1_S$, $g_1 \le g$ and $g_1 \ne g$, i.e. a contradiction, as $g$ is a minimal complement. Therefore, there exists $b \in B_2$ such that $g(x) = g(b)$.

Since $|B_2| \ge 2$ if follows that there exists $c \in B_2$ such that $c \neq b$. As $f \times g \equiv 1_S$ and $f(b) = f(c)$, it follows that $g(b) \neq g(c)$. Define now a mapping $g'$ such that (i) $g'(x) = g(x)$, $\Psi x \neq a$ (ii) $g'(a) = g(c)$. Since $g$ is a minimal complement so is $g'$ and $g' \neq g$. Thus, if the mapp- ing $f$ has a unique minimal complement then $f \equiv 1_S$ of $f \equiv 0_S$. The converse of this result is trivial. Q.E.D.

It follows from this theorem that there can be an infinity of even minimal complements of a given view. Then, according to our translation scheme there is an infinity of ways to translate an update. Do all these different ways have a practical meaning ? In other words, can we find examples of "realistic" $f$, $g_1$ and $g_2$ such that (i) $g_1$ and $g_2$ are distinct complements and (ii) the $g_1$-translation and the $g_2$-translation of a "realistic" update of $f$ are meaningful? The answer is yes and we shall present such examples later. First, let us discuss further the multiplicity of complements and its practical consequences.
In [Dayal and Berstein 78] it is argued that "... an update u on a view f(S) is translatable if there is a *unique* update U on S producing the desired update on f(S) such that ...". Then, later, the authors argue that the uniqueness criterion is controversial : "... We do not feel comfortable with this choice but could not find more attractive alternatives [...] admittedly, our correctness criteria have weaknesses. However, these weaknesses are due to gaps in our understanding of update semantics in the relational model...".

Indeed, it appears that the uniqueness criterion is the best choice in case, when the only information available is the description of the view. However, as the authors observe, "...the view definition function [...] is often not sufficient to express the semantics of the relationship between update operations on the view and on the [original] schema...". Our conclusion here is that the extra information we need is exactly the description of a complement of the view.

We present now some examples of views and multiple complements.

**Example :** Let the data base be described by :

R(PRODUCT, COST, SALE-PRICE, PROFIT, PROFIT-RATE)

and an associated schema specified by :

(i) PRODUCT → COST, SALEPRICE, PROFIT, PROFIT-RATE

(ii) ∀ x ∈ R<sub>U</sub> , x.COST ≥ 0 and x.PROFIT ≥ 0
x.PROFIT = x.SALEPRICE - x.COST
x.PROFIT-RATE = x.PROFIT/x.COST.

Now define a view r(PRODUCT, COST) by the f mapping

r<sub>U</sub>(PRODUCT, COST) = R<sub>U</sub>(PRODUCT, COST)

and consider the update u described by

"Decrease the cost of all products by 5%"
The three mappings

$g_1 = R(PRODUCT, SALEPRICE)$

$g_2 = R(PRODUCT, PROFIT)$

$g_3 = R(PRODUCT, PROFIT-RATE)$

are all complements of f, and u is $g_1$-translatable for i=1,2,3. These three translations correspond to three different update policies: in the $g_1$-translation the saleprice will remain constant while profit and profit rate will increase, in the $g_2$-translation the profit will remain constant, the sale price will decrease and the profit rate will increase and in the $g_3$-translation the profit rate will remain constant while the saleprice and the profit will decrease. These three translations are all acceptable policies and neither practical nor theoretical arguments can allow us to disregard one or another. This is simply because the view definition function is not sufficient information to decide on the update policy, while for instance $(f,g_1)$ is a full description of the view f. It is up to the user to decide which update policy is appropriate for his application.

**Example :** Let the data base be described by

$R_1(EMP, DEPT)$

$R_2(DEPT, MGR, MGR-SAL, SECRETARY)$

and the associated schema be specified by

$R_1 : EMP \to DEPT$

$R_2 : DEPT \leftrightarrow MGR$

$R_2 : MGR \to MGR \ SAL, SECRETARY$

Consider the view :

$f = R_2(DEPT, MGR)$

and the update

u : "permute the managers of departments A and B".
The following mappings are three different complements of f

$$g_1 = R_1(\text{EMP,DEPT}) \times R_2(\text{DEPT,MGR SAL,SECRETARY})$$

$$g_2 = R_1(\text{EMP,DEPT}) \times R_2(\text{MGR,MGR SAL,SECRETARY})$$

$$g_3 = R_1(\text{EMP,DEPT}) \times R_2(\text{MGR,MGR SAL}) \times R_2(\text{DEPT,SECRETARY})$$

In all three cases the translation U of u permutes the managers of departments A and B. But this is done under a different "policy" each time. For instance, in the first case the managerial salary of the department remains unchanged. Also, the secretary stays with the department. In the second case, neither the salary nor the secretary of the manager change. In the third case the salary of the manager remains unchanged and the secretary stays in the department. Thus, the three complements of f correspond to three different "realistic policies" under which a permutation of managers can be done in a company.

## VII - UNIVERSALITY OF TRANSLATION UNDER CONSTANT COMPLEMENT.

To summarize the previous section, we have first defined the translation of an update u on view f as an update U on schema S such that:

$$(i) \quad f \circ U = u \circ f$$

$$(ii) \quad u^n(f(R_t)) = f(R_t) \Rightarrow U^n(R_t) = R_t, \quad \forall R_t \in S.$$

This defined a set $T_f(u)$ of translations of u. Then we studied a specific translation scheme : the translation U under a constant complement g defined by :

$$U(R_t) = (f \times g)^{-1} (u(f(R_t)), g(R_t))$$

It was then shown that for a given f there was no unique g but a multiplicity, which defined a set $T_f^c(u)$ of translations of u under all constant complement i.e. :

$$T_f^c(u) = \{U \mid \exists \text{ complement } g \text{ of } f \text{ such that } U \text{ is the consistent } g\text{-translation of } u\}$$

The first question to ask is whether the g-translation of u is indeed an admissible translation as defined in section III, i.e. whether $T_f^c(u) \subseteq T_f(u)$.
**Theorem VII-1.**

Let S be a schema, let f be a view and u an update of that view, let g be a complement of f. The consistent g-translation of u is an admissible translation of u. □

**Proof.** It was shown in theorem V-1, that the g-translation of u is indeed a translation. So all we have to show is that it is admissible. Assume

$$u^n(f(R_τ)) = f(R_τ).$$

$$ \begin{aligned} U^n(R_τ) &= (f \times g)^{-1} (U^n(f(R_τ)), g(R_τ)) \\ &= (f \times g)^{-1} (f(R_τ), g(R_τ)) \\ &= (f \times g)^{-1} (f \times g(R_τ)) \\ &= R_τ \end{aligned} $$

Q.E.D.

The next question concerns the generality of the translation scheme that we presented: Does there exist other ways of translating updates ? Fortunately the answer is no, i.e. any translation of u is its translation under some constant complement $\tilde{g}$ of f as we now state :

**Theorem VII-3.**

Let S be a schema, let f be a view, let u be an update of that view and let U be an admissible translation of u. Then there exists a complement g of f such that U is the g-translation of u. In other words

$$T_f(u) \subseteq T_f^c(u).$$

□

**Proof.** We define on S, a binary relation by :

$$ \begin{aligned} R_τ \equiv R'_τ & \quad \text{iff} \quad \exists n \ge 0 \text{ such that } U^n(R_τ) = R'_τ \\ \text{or} \quad \exists n \ge 0 \text{ such that } U^n(R') = R_τ \end{aligned} $$

It is clear that $\equiv$ is an equivalence relation. We can therefore define the quotient set $S/\equiv$ and the induced mapping $g : S \to S/\equiv$, that associates with each $R_τ$ its equivalence class $[R_τ]$, i.e.

$$g(R_τ) = [R_τ] , \quad \forall R_τ .$$
**Claim :** g is a complement of f.

To show this, we must prove that $f \times g \equiv I_S$, i.e. that $f \times g$ is
injective or in other words :

$$
f \times g(R_1) = f \times g(R_2) \Rightarrow R_1 = R_2, \quad \forall R_1 \text{ et } R_2 \text{ in } S.
$$

Let $R_1$ and $R_2$ be two values such that $f \times g(R_1) = f \times g(R_2)$
Then by definition of $f \times g$ we have

$$
f(R_1) = f(R_2) \tag{1}
$$

and

$$
g(R_1) = g(R_2) \tag{2}
$$

$$
(2) \Rightarrow \exists n \ge 0 \text{ such that } R_2 = U^n(R_1) \quad (3)
$$

The fact that U is a translation of u implies that :

$$
u^n(f(R_1)) = f(U^n(R_1)) \quad (4)
$$

$$
(3) \text{ and } (4) \Rightarrow u^n(f(R_1)) = R_2 \qquad (5)
$$

$$
(5) \text{ and } (1) \Rightarrow u^n(f(R_1)) = f(R_1) \quad (6)
$$

$$
(6) \text{ and the fact that } U \text{ is an admissible translation of } u \text{ imply that :} \\
U^n(R_1) = R_1 \qquad (7)
$$

$$
(7) \text{ and } (3) \Rightarrow R_1=R_2 \qquad \text{Q.E.D.}
$$

We have shown that g is a complement of f. By the definition of
g we have :

$$
g(U(R)) = g(R), \quad \forall R \in S
$$

which shows that U is a g-translation. Q.E.D.

This theorem shows that every translation is a translation under
some constant complement g of f. Therefore the translation under constant
complement is a totally general method of translation.
# VIII - CONCLUSIONS

In this paper we have studied the problem of updating relational views. We have defined a view as a mapping $f : S \rightarrow f(S)$ and an update as a mapping $u : f(S) \rightarrow f(S)$.

The view update problem consists in translating $u$ into an update $U : S \rightarrow S$. The usual definition of the update translation, i.e. $f \circ U = u \circ f$ was adopted and we introduced an admissibility condition, stating that if a sequence of updates leaves the view unchanged then their translation should leave the data base unchanged too.

Then we presented a specific "method" for update translation : Together with a view $f$, we defined a complementary view $g$, such that from the couple $(f(R_τ), g(R_τ))$ the original data base value $R_τ$ can be re-computed. The translation under constant $g$ consists of modifying the $f(R_τ)$ component, while the $g(R_τ)$ component remains unchanged. Conditions for this translation to be well defined were exhibited. It was then argued that different complementary views could be chosen and that their choice would correspond to the choice of an update policy of the data base.

Finally this translation method was proved universal, by showing that every admissible translation can be done by this method.

The main contributions of this paper consist of showing :

(i) that all update translations are translations under some complement $g$

(ii) there is no unique better way of translating an update but just different update policies

(iii) the choice of a policy is the choice of a complementary view $g$.

These three points suggest the following approach for handling updates

1. choose a complement $g$

2. check that it is a minimal complement of $f$

3. whenever update $u$ is attempted, check whether $u$ is $g$-translatable

4. translate $u$ by the formula $(f \times g)^{-1}(u(f(R), g(R)))$
In this paper we have not dealt at all with the problem of the
practical implementation of these four steps. Steps (1) (2) and (3) are
very much dependent on the schema S,i.e. on the type of integrity cons-
traints that we want to consider. This seems to imply that many decisions
will be taken by humans (the DBA) at these steps. Obviously step 4 must
be realized by a program and the brute force application of the formula
is unacceptable. So efforts for further research should go in that direc-
tion.
REFERENCES

[Chamberlain et al 75] Chamberlain, D.D., J.N. Gray, and D.D. Traiger, "views, authorization and locking in a relational data base system", Proceedings of AFIPS NCC, Vol 44, 1975.

[Codd 72] Codd, E.F., "Further Normalization of the database relational model", in Data Base Systems, Courant Computer Science Symposium 6, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, 1972, pp. 33-64.

[Codd 74] Codd, E.F., "Recent investigations in a Relational data base systems", information Processing 74, Noth Holland Pub. Co, Amsterdam 74, p.p. 1017-1021.

[Dayal and Bernstein 78] Dayal, U. and P.A. Bernstein, "On the updatability of Relational views", Proceedings of the 4th International Conference on very Large data bases, West Berlin 78.

[Furtado and Sevcik 78] Furtado A.L., and K.C. Sevcik, "Permitting updates through views of data bases", To appear 78

[Paolini and Pelagatti 77] Paolini, P., and G. Pelagatti, "Formal definitions of mappings in a data base", ACM SIGMOD, Proceedings of the Int. Conf. on Management of Data, Aug. 1977, pp. 40-46.

[Stonebraker 75] Stonebraker, M. "Implementation of integrity constraints and views by query modification", Proc. 1975 SIGMOD Conf., ACM, N.Y., pp. 65-78.