# The abstraction process in the relational model

Nicolas Spyratos, Francois Bancilhon

► To cite this version:

Nicolas Spyratos, Francois Bancilhon. The abstraction process in the relational model. [Research Report] IRIA-RR-342, IRIA. 1979, pp.16. hal-04716615

HAL Id: hal-04716615

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

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_1.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

Bibliothèque
IRIA

# THE ABSTRACTION PROCESS
IN THE RELATIONAL MODEL

Nicolas SPYRATOS
François BANCILHON

Rapport de Recherche N° 342

Janvier 1979

<figure><img src="image_2.png" /></figure>
# THE ABSTRACTION PROCESS IN THE RELATIONAL MODEL

Nicolas Spyratos, François Bancilhon

## Résumé :

Nous étudions ici le problème de la traduction d'une base de données d'une représentation relationnelle en une représentation entité/relation (modèle de Chen). La méthode utilisée est celle de l'abstraction qui consiste à construire des objets complexes à partir des relations. On caractérise les traductions sans perte d'information puis les «bonnes» traductions. On donne aussi les algorithmes permettant de décider si une traduction est bonne dans certains cas spécifiques.

## Abstract :

The objective of this paper is to study means for translating a relational representation of data into an entity/relationship one. An abstraction process is described which does this translation. Requirements for «good» abstractions are proposed and criteria for their characterization are discussed.
# 1. INTRODUCTION

It is generally accepted that the relational model is simple to understand, mathematically well defined and it can achieve a high degree of data independance. However, the relational model gives no indication about the way in which the world is to be represented by a collection of relations. As a consequence, much depends on what relations are initially chosen to represent the world. More specifically, important semantic information may be hidden or lost [8], because complex characteristics are split up into attributes. For example, initial choice of the relation R(STREET, LAST-NAME, HOUSE #, SALARY, FIRST-NAME, EMPL #, DATE, CITY) will hide important semantic information which is better understood in the relation R'(FULL-NAME, ADDRESS, SALARY-HISTORY).

Thus, FULL-NAME is a complex characteristic described by FIRST-NAME and LAST-NAME. Similarly, ADDRESS is described by CITY, STREET and HOUSE #; and SALARY-HISTORY by SALARY and DATE.

The entity/relationship model [2] provides a solution to this deficiency of the relational model : it utilizes semantic information to organize data in entity/relationship relations. Roughly speaking, the relation R above, is the relational model representation and the relation R' is the entity/relationship representation of the same information. In the entity/relationship representation, more of the structure of data is shown explicitly and connections between attributes, are seen more easily.

The purpose of this paper is to study the abstraction process in the relational model. We call *abstraction* of a relation the process which (a) Groups together attribute names of a relation into new attribute names, e.g., FIRST-NAME and LAST-NAME above into FULL-NAME.

(b) Describes the real relationship between the new attribute names, e.g., the relationship between FULL-NAME, ADDRESS and SALARY-HISTORY.

(c) Defines the values of the new attribute names.
Abstractions of relations are useful when we deliberately wish to omit certain details. The objective is to allow the users of a system to concentrate on details which are relevant to their application and to ignore other details [ 9 ]. To do so, we often need to translate a relational representation of data into an entity/relationship one (for example, R above into $R'$. Of course, additional semantic information is needed, during the process, to guide the grouping of attribute names. It is, interesting, however, to know how far one can go into this translation, with only the information available in the relational representation. In other words, it is interesting to know how much of this translation process can be automated. In this paper, we study the following questions concerning the abstraction process :

(1) How to specify an abstraction (items (a), (b) and (c) above).

(2) What is a "good" abstraction.

(3) How can one decide whether an abstraction is "good".

First, we recall briefly the basic definitions from the relational model and introduce our notation (Section 2). Then we proceed to discuss the abstraction process, first by example (Section 3) and then through formal definitions (Section 4). We consider as "good" those abstractions that are both *lossless* and *well-defined*. In Section 5, we discuss lossless abstractions : an abstraction is lossless, if information is preserved during the process, i.e., if one can recompute the original relation. In Section 6, we discuss well-defined abstractions : an abstraction is well-defined if, within a name specification for the new attributes, one can update the abstraction independently, of names. Criteria for lossless and well-defined abstractions are also presented.

## 2. BASIC DEFINITIONS AND NOTATION

In this section we recall the main definitions from the relational model and we introduce our notation.
Central in the relational model is the notion of a relation. A relation is specified through a relation descriptor of the form R($A_1$ : $D_1$, ..., $A_i$ : $D_i$, ..., $A_n$ : $D_n$). R is the relation (variable), the $A_i$'s are the attribute names and $D_i$ is the domain associated with $A_i$. When clear from context, we shall ignore domains thus denoting the descriptor by $(R(A_1,A_2, ..., A_n))$. The set of attribute names will be denoted by U, i.e., $U = \{A_1, A_2, ..., A_n\}$; the relation descriptor is then denoted by $R(U)$. A U-tuple is a mapping $x : \{A_1, A_2, ..., A_n\} \rightarrow D_1 \cup ... \cup D_n$ such that $x(A_i) \in D_i$; it is denoted by $(A_1 : x_1, A_2 : x_2, ..., A_n : x_n)$, where $x_i = x(A_i)$; when clear from context, we simply write $(x_1, x_2, ..., x_n)$ or $x_1x_2...x_n$. The values of the relation (variable) R are finite sets of U-tuples. The values of a relation are denoted by subscripting the relation by a letter, e.g., $R_t$. Relation values are represented in the usual tabular form, where rows represent tuples and columns represent attributes.

The projection of a U-tuple $x$ on attribute set $A \subset U$, denoted $x(A)$, is the restriction of $x$ to $A$. Let $x$ be a X-tuple and $y$ a Y-tuple, such that $x(X \cap Y) = y(X \cap Y)$. Then the join of $x$ and $y$, denoted $x*y$, is the XUY-tuple $z$ such that $z(X) = x$ and $z(Y) = y$. The notions of projection and join can be extended to relation values. Let $R_t$ be a relation value; its projection over $X \subset U$, denoted $R_t[X]$, is defined by $R_t[X] = \{x(X) | x \in R_t\}$, i.e., it is the set projections of all tuples in $R_t$. Let $R_1(U_1)$ and $R_2(U_2)$ be two relation descriptors and let $R_{1t}$ and $R_{2t}$ be two values of $R_1$, $R_2$, respectively. The join of $R_{1t}$ and $R_{2t}$, denoted by $R_{1t} * R_{2t}$, is defined by $R_{1t} * R_{2t} = \{x*y | x \in R_{1t}, y \in R_{2t}, x(U_1 \cap U_2) = y(U_1 \cap U_2)\}$.

Note that when $U_1 \cap U_2 = \emptyset$ then the cardinality of the join is equal to that of the cartesian product of the two relation values.

A data base consists of one or more relations specified by their descriptors. The set of possible values that these relations can take is the data base schema denoted by S. The schema is usually specified by a set of properties that the relation values must satisfy (in order to belong to the schema). These are the data base integrity constraints. In the absence of
integrity constraints the schema is called free, denoted by $S_F$. Examples of integrity constraints are functional dependencies [3] and multi-valued dependencies [4], that we shall now define. Let $R(U)$ be a relation descriptor, $R_t$ a value of $R$ and $X, Y \in U$. We say that $Y$ is *functionally dependent* on $X$ in $R_t$, denoted $X \rightarrow^{R_t} Y$ (or, simply, $X \rightarrow Y$ when no confusion is possible), iff $\forall x, y \in R_t, x(X) = y(X) \Rightarrow x(Y) = y(Y)$. In order to define multivalued dependencies, we define first the following mapping :

$$f_{X,Y} : R_t[X] \rightarrow 2^{R_t[Y]} \\ x \rightarrow \bar{y} = \{y | x \star y \in R_t[X,Y]\}$$

This mapping associates to each tuple $x \in R_t[X]$ the set of all tuples $y \in R_t[Y]$ related to it in $R_t$. Let now $X, Y$ and $Z$ be three subsets of $U$ which form a partition of $U$ (we denote this by writing $U=XYZ$). We say that there is a multivalued dependency from $X$ into $Y$ in $R_t$, denoted $X \rightarrow^{R_t} Y$ (or, simply, $X \rightarrow Y$ when no confusion is possible), iff $\forall xyz \in R_t$, $f_{XZ,Y}(xz) = f_{X,Y}(x)$. That is, the set of tuples from $R_t[Y]$ associated with a tuple $xz$ from $R_t[XZ]$, depends only on the projection $x$ of that tuple on $X$. Now that we have defined functional and multivalued dependencies let us see an example of schema definition. Consider a data base which consists of only one relation with descriptor $R(U)$. Suppose that we are interested in those values of the relation which satisfy $X \rightarrow Y$, where $X, Y \in U$. Then the data base schema is defined as follows : $S = \{R_t | X \rightarrow Y\}$.

### 3. THE ABSTRACTION PROCESS

In this section we explain the abstraction process using examples.

**Example 1.** Consider the following relation which describes student registration :

$R(STUDENT, COURSE #, COURSE-DESCRIPTION, YEAR)$
A different way of viewing this relation is to group together the attribute names `COURSE #` and `COURSE-DESCRIPTION` into the new attribute name `SUBJECT`. In this way we obtain a new relation descriptor `R'(STUDENT, SUBJECT, YEAR)`.

The relationship between `COURSE #` and `COURSE-DESCRIPTION` in `R` is now regarded as the higher level object `SUBJECT` ("horizontal aggregation"). This implies that the `SUBJECT` domain is the cartesian product of the `COURSE #` - domain and the `COURSE-DESCRIPTION`-domain. And this also suggests how to define the `SUBJECT-attributes`: in each tuple of a given value $R_t$ (Figure 1), group together the `COURSE #` and `COURSE-DESCRIPTION` attributes to obtain the corresponding value $R'_t$. The relation `R` is the abstraction of `R`.

The `SUBJECT-attributes` in $R'_t$ are composite objects, i.e., $R'$ is not in first normal form [ 3]. We can normalize $R'$ by introducing simple names for the `SUBJECT-attributes`. In Figure 1, $R_{1t}$ is a normalized version of $R'_t$ and $R_{2t}$ is the description of the simple names that allowed this normalization.

□

<table><caption>ORIGINAL RELATION</caption><thead><tr><th>R<sub>t</sub></th><th>STUDENT</th><th>COURSE #</th><th>COURSE-DESCR</th><th>YEAR</th></tr></thead><tbody><tr><td>Jones</td><td></td><td>112</td><td>Algebra</td><td>77</td></tr><tr><td>Smith</td><td></td><td>197</td><td>Mechanics</td><td>78</td></tr><tr><td>Smith</td><td></td><td>123</td><td>Electricity</td><td>78</td></tr><tr><td>Jones</td><td></td><td>201</td><td>Topology</td><td>77</td></tr><tr><td>Jones</td><td></td><td>104</td><td>Analysis</td><td>77</td></tr></tbody></table>

<table><caption>UNNORMALIZED ABSTRACTION</caption><thead><tr><th>R'<sub>t</sub></th><th>STUDENT</th><th>SUBJECT</th><th>YEAR</th></tr></thead><tbody><tr><td>Jones</td><td></td><td>(112, Algebra)</td><td>77</td></tr><tr><td>Smith</td><td></td><td>(197, Mechanics)</td><td>78</td></tr><tr><td>Smith</td><td></td><td>(123, Electricity)</td><td>78</td></tr><tr><td>Jones</td><td></td><td>(201, Topology)</td><td>77</td></tr><tr><td>Jones</td><td></td><td>(104, Analysis)</td><td>77</td></tr></tbody></table>

<table><caption>A NORMALIZED ABSTRACTION</caption><thead><tr><th>R<sub>1t</sub></th><th>STUDENT</th><th>SUBJECT</th><th>YEAR</th></tr></thead><tbody><tr><td>Jones</td><td></td><td>M1</td><td>77</td></tr><tr><td>Smith</td><td></td><td>P1</td><td>78</td></tr><tr><td>Smith</td><td></td><td>P2</td><td>78</td></tr><tr><td>Jones</td><td></td><td>M2</td><td>77</td></tr><tr><td>Jones</td><td></td><td>M3</td><td>77</td></tr></tbody></table>

<table><caption>DESCRIPTION OF SIMPLE ATTRIBUTES</caption><thead><tr><th>R<sub>2t</sub></th><th>COURSE #</th><th>COURSE-DESCR.</th><th>SUBJECT</th></tr></thead><tbody><tr><td></td><td>112</td><td>Algebra</td><td>M1</td></tr><tr><td></td><td>197</td><td>Mechanics</td><td>P1</td></tr><tr><td></td><td>123</td><td>Electricity</td><td>P2</td></tr><tr><td></td><td>201</td><td>Topology</td><td>M2</td></tr><tr><td></td><td>104</td><td>Analysis</td><td>M3</td></tr></tbody></table>

**Figure 1.** Abstracting a relation : Horizontal aggregation of attributes.
**Example 2.** Consider again the relation *R* of Example 1. Suppose that now we are interested in the set of subjects (i.e., COURSE #, COURSE-DESCRIPTON pairs) each student takes, i.e., his curriculum. In order to define this new view of *R* we must first group together the attribute names COURSE # and COURSE-DESCRIPTION into the new attribute name CURRICULUM. In this way we obtain the new relation descriptor

$R'(\text{STUDENT}, \text{CURRICULUM}, \text{YEAR})$

The relationship between COURSE # and COURSE-DESCRIPTION in *R*, is now regarded as the higher level object CURRICULUM (horizontal aggregation). To define the CURRICULUM-attributes, recall that what we want to see in *R'* is the set of subjects, i.e., the set of COURSE #, COURSE-DESCRIPTION pairs, that each student takes. This implies that the CURRICULUM domain is the power set of the cartesian product of the COURSE # and COURSE-DESCRIPTION domains. So, given a value R<sub>t</sub> of *R*, the corresponding value R'<sub>t</sub> of *R'* can be computed as follows (Figure 2) :

(1) Group together all pairs of COURSE # and COURSE-DESCRIPTION attributes that correspond to the same STUDENT-attribute in R<sub>t</sub> ("vertical aggregation").

(2) In each tuple of R<sub>t</sub>, replace the COURSE # and COURSE-DESCRIPTION pair with the set of pairs from (1) to which it belongs.

The set of tuples resulting from this procedure is the value $R_t'$. Again we can normalize $R_t'$ by introducing simple names for the composite CURRICULUM-attributes. In Figure 2, $R_{1t}$ is a normalized version of $R_t'$ and $R_{2t}$ is the description of the simple names that allowed this normalization. [ ]
<table><caption>ORIGINAL RELATION</caption><thead><tr><th>R<sub>t</sub></th><th>STUDENT</th><th>COURSE #</th><th>COURSE-DESCR.</th><th>YEAR</th></tr></thead><tbody><tr><td></td><td>Jones</td><td>112</td><td>Algebra</td><td>77</td></tr><tr><td></td><td>Smith</td><td>197</td><td>Mechanics</td><td>78</td></tr><tr><td></td><td>Smith</td><td>123</td><td>Electricity</td><td>78</td></tr><tr><td></td><td>Jones</td><td>201</td><td>Topology</td><td>77</td></tr><tr><td></td><td>Jones</td><td>104</td><td>Analysis</td><td>77</td></tr></tbody></table>

<table><caption>UNNORMALIZED ABSTRACTION</caption><thead><tr><th>R'<sub>t</sub></th><th>STUDENT</th><th>CURRICULUM</th><th>YEAR</th></tr></thead><tbody><tr><td></td><td>Jones</td><td>{(112, Algebra), (201, Topology), (104, Analysis)}</td><td>77</td></tr><tr><td></td><td>Smith</td><td>{(197, Mechanics), (123, Electricity)}</td><td>78</td></tr></tbody></table>

<table><caption>NORMALIZED ABSTRACTION</caption><thead><tr><th>R<sub>1t</sub></th><th>STUDENT</th><th>CURRICULUM</th><th>YEAR</th></tr></thead><tbody><tr><td></td><td>Jones</td><td>Math</td><td>77</td></tr><tr><td></td><td>Smith</td><td>Physics</td><td>78</td></tr></tbody></table>

<table><caption>DESCRIPTION OF SIMPLE ATTRIBUTES</caption><thead><tr><th>R<sub>2t</sub></th><th>COURSE#</th><th>COURSE-DESCR.</th><th>CURRICULUM</th></tr></thead><tbody><tr><td></td><td>112</td><td>Algebra</td><td>Math</td></tr><tr><td></td><td>197</td><td>Mechanics</td><td>Physics</td></tr><tr><td></td><td>123</td><td>Electricity</td><td>Physics</td></tr><tr><td></td><td>201</td><td>Topology</td><td>Math</td></tr><tr><td></td><td>104</td><td>Analysis</td><td>Math</td></tr></tbody></table>

**Figure 2.** Abstracting a relation : Horizontal aggregation of attribute names and vertical aggregation of tuples.

Several remarks can be made at this point. In both examples, we start with the same original relation R and we group together the same attribute names but, depending on the meaning we attach to the grouping each time, we obtain different values of R'. Following the "unnormalization" suggested in [ 6 ] we can only obtain the unnormalized relation R' of Example 2. This is due to a difference in scope. In [ 6 ] unnormalized relations are used in order to remedy certain storage operation anomalies encountered with third normal form relations. Our objective is different : we are interested in the possible translations of a relational representation of data into an entity/ relationship one.

In the previous examples, we chose simple familiar names for the composite attributes in R'. Actually, any names would do provided that different attributes get different names. It is important to note, however, that two diffe-
rent sets of names for the composite attributes in R' will lead to two
different pairs of values in the (R<sub>1</sub>, R<sub>2</sub>)-representation.

4. THE FORMAL DEFINITION OF ABSTRACTION

In the previous section, we explained abstraction using examples. The
process explained in those examples can be summarized as follows :

(1) We start with the descriptor of a relation R and we define the des-
criptor of a new relation R'.

(2) We define a rule which, given a value R<sub>t</sub>, computes the corresponding value R'<sub>t</sub>.

(3) We rename the composite attributes in R' to obtain a normalized version
R<sub>1t</sub> (and the accompanying description R<sub>2t</sub>).

We now proceed to formally define this process. First, we define the abstrac-
tion of a given relation descriptor R(U). For convenience, we shall write
U=ABC, whenever A, B and C form a partition of U. Then for any U-tuple x
we write x=abc, where a, b, c are the projections of x on A, B, C, respec-
tively.

**Definition 1.** Let R(U) be a relation descriptor. Let X, Y be subsets of U.
The *unnormalized abstraction* (u-abstraction, for short) of R(U) with respect to the pair (X,Y) is a relation descriptor R'(U') where U' is defined as follows :

(1) Define a new attribute name Y/X with domain the power set of the carte-
sian product of the domains in Y.

(2) Define U' = X {Y/X}Z, where Z = U - (X u Y). □

Note that Y/X denotes a single attribute name. Also, that X, {Y/X} and Z
form a partition of U' so that we can write U' = X{Y/X}Z.

The next thing to do is to give a rule for computing the value of R' cor-
responding to a given value of R.
**Definition 2.** Let R(U) be a relation descriptor and R'(U') its abstraction with respect to the pair (X,Y). Let $R_t$ be a value of R. Then the corresponding value $R'_t$ of R' is defined by

$$ 
\begin{array}{lclcl}
x \bar{y} z \in R'_t & \iff & (i) & \exists y \in \bar{y} \text{ such that } xyz \in R_t & \\
& & (ii) & f_{X,Y}(x) = \bar{y} & \Box
\end{array}
$$

The value $R'_t$ just defined is not in first normal form, as the Y/X-attributes are composite objects. If we are to study abstraction in purely relational terms, we must normalize this value. We do that by (i) naming the Y/X-attributes using the integers as names and (ii) describing the objects thus named.

**Definition 3.** Let R'(U') be the abstraction of R(U) with respect to the pair (X,Y).

(i) The *normalized abstraction* (n-abstraction, for short) of R(U) with respect to the pair (X,Y) is a relation descriptor $R_1(U_1)$, such that : $U_1 = \{Y|X\}Z$ with the set N of integers as Y/X-domain.

(ii) The *normalized description* (n-description, for short) of R(U) with respect to the pair (X,Y) is a relation descriptor $R_2(U_2)$, such that : $U_2 = \{Y|X\}Y$ with the set N of integers as Y/X-domain. $\Box$

Note that the only difference between $R'(U')$ and $R_1(U_1)$ is in the domain associated with the attribute name Y/X.

Finally, we give the rules for computing the values of $R_1$ and $R_2$ corresponding to a given value of $R'$.

**Definition 4.** Let $R'(U')$ be the u-abstraction of R(U) with respect to the pair (X,Y). Let $R_1(U_1)$ be the n-abstraction of R(U) and $R_2(U_2)$ the n-description. Let $R'_t$ be a value of the u-abstraction. Let $e : R'_t[Y/X] \to N$ be an injective mapping. Then the values $R_{1t}$ and $R_{2t}$ corresponding to $R'_t$ and $e$ are defined as follows :
$$ 
\begin{array}{l@{\qquad}l}
x \, n \, z \in R'_{1t} & <\Rightarrow x'e^{-1}(n)z \in R'_{t} \\
\\
ny \in R_{2t} & <\Rightarrow y \in e^{-1}(n) \quad \Box
\end{array}
 $$

Note that given a value $R'_t$ we can define an infinity of pairs of values $(R_{1t}, R_{2t})$, depending on the mapping $e$. We shall use a superscript to indicate the mapping used for the normalization, e.g., $R_{1t}^e, R_{2t}^e$.

Now that we have formally defined abstraction, the question is: how can one tell "good" abstractions. When we look at a complex relation and decide to simplify it, by means of abstraction, we are guided by our knowledge of semantics and also by our intuition. Thus, we "feel" that some abstractions are good while others are not. But can we formally state requirements for good abstractions? In the remaining of this paper we propose two requirements as fundamental for a good abstraction.

## 5. LOSSLESS ABSTRACTIONS

The first requirement for a good abstraction is preservation of information. The following example shows that information is not always preserved during the abstraction process.

Let $R(STUDENT, SUBJECT, GRADE)$ be a relation descriptor and consider the abstraction: $CURRICULUM = SUBJECT / STUDENT$. The $u$-abstraction of $R$ is $R'(STUDENT, CURRICULUM, GRADE)$. Figure 3 shows a value of $R$ and the corresponding value of $R'$. Note that we lost information in going from $R'_t$ to $R'_t$ as we can no longer tell the grades of John in Latin and Math (i.e., we are not able to recompute $R'_t$). Therefore, this is not a good abstraction. We shall state preservation of information as a requirement for a good abstraction.

Let us consider a relation descriptor $R(U)$ and a schema $S$ of $R$. Consider the abstraction $R'(U')$ defined by two subsets $X$ and $Y$ of $U$. Let us now extend the descriptor $R(U)$ to a new descriptor $\bar{R}(\bar{U})$ as follows:
**Definition 5.** Let $R(U)$, $S$, $X$, $Y$ be as above. Define the descriptor $\bar{R}(\bar{U})$ by

(i) $U = \{Y/X\} \cup U$

(ii) $\bar{yxyz} \in \bar{R}_t \iff xyz \in R_t$ and $\bar{y} = f_{X,Y}(x), \forall R_t \in S$ ☐

In this way we generate a schema $\bar{S}$ of $\bar{R}$, the extension of $S$, which is equivalent to $S$, i.e., $S$ and $\bar{S}$ are in one-to-one correspondence. This schema has the following property :

$$ \bar{R}_t [U] = R_t \text{ and } \bar{R} [X\{Y/X\}Z] = R'_t, \quad \forall \bar{R}_t \in \bar{S} $$

That is, the projection of $\bar{R}_t$ over $U$ is the original value $R_t$ and the projection of $\bar{R}_t$ over $X\{Y/X\}Z$ is the u-abstraction $R'_t$ (Figure 3). Therefore, we can recompute $R_t$ from $R'_t$, if we can recompute $\bar{R}_t$ from $R'_t$. And this is ensured if we require that $\bar{R}_t$ equal the join of its projections over $Y \{Y/X\}$ and $X\{Y/X\}Z$. Hence the following definition.

<table><caption>ORIGINAL RELATION</caption><thead><tr><th>R<sub>t</sub></th><th>STUDENT</th><th>SUBJECT</th><th>GRADE</th></tr></thead><tbody><tr><td></td><td>John</td><td>Latin</td><td>A</td></tr><tr><td></td><td>Peter</td><td>Latin</td><td>B</td></tr><tr><td></td><td>Mary</td><td>Latin</td><td>A</td></tr><tr><td></td><td>John</td><td>Math</td><td>B</td></tr></tbody></table>

<table><caption>u-ABSTRACTION</caption><thead><tr><th>R'<sub>t</sub></th><th>STUDENT</th><th>CURRICULUM</th><th>GRADE</th></tr></thead><tbody><tr><td></td><td>John</td><td>{Latin,Math}</td><td>A</td></tr><tr><td></td><td>Peter</td><td>{Latin}</td><td>B</td></tr><tr><td></td><td>Mary</td><td>{Latin}</td><td>A</td></tr><tr><td></td><td>John</td><td>{Latin,Math}</td><td>B</td></tr></tbody></table>

<table><caption>THE EXTENSION OF R<sub>t</sub></caption><thead><tr><th>R&#773;<sub>t</sub></th><th>CURRICULUM</th><th>STUDENT</th><th>SUBJECT</th><th>GRADE</th></tr></thead><tbody><tr><td></td><td>{Latin,Math}</td><td>John</td><td>Latin</td><td>A</td></tr><tr><td></td><td>{Latin}</td><td>Peter</td><td>Latin</td><td>B</td></tr><tr><td></td><td>{Latin}</td><td>Mary</td><td>Latin</td><td>A</td></tr><tr><td></td><td>{Latin,Math}</td><td>John</td><td>Math</td><td>B</td></tr></tbody></table>
$$ \bar{R}_t[Y\{Y/X\}] * \bar{R}_t[X\{Y/X\}Z] = \begin{array}{|c|c|c|c|} \hline \text{CURRICULUM} & \text{STUDENT} & \text{COURSE} & \text{GRADE} \\ \hline \{Latin, Math\} & John & Latin & A \\ \{Latin, Math\} & John & Math & A \\ \{Latin\} & Peter & Latin & B \\ \{Latin\} & Mary & Latin & A \\ \{Latin, Math\} & John & Latin & B \\ \{Latin, Math\} & John & Math & B \\ \hline \end{array} \neq \bar{R}_t $$

$X = \{STUDENT\}$

$Y = \{SUBJECT\}$

$Y/X = \text{CURRICULUM}$

**Figure 3.** An abstraction with loss of information.

**Definition 6.** Let $R(U)$ be a relation descriptor, $S$ a schema of $R$ and $X, Y \in U$. Let $\bar{R}(\bar{U})$ be the extension of $R(U)$ and $\bar{S}$ the corresponding extension of $S$. The abstraction $Y/X$ is **lossless** iff $\bar{R}_t = \bar{R}_t[Y\{Y/X\}] * \bar{R}_t[X, Y/X, Z]$. $\square$

The question which arises now is the following : given a relation descriptor $R(U)$ and a schema $S$ of $R$, can we decide whether an abstraction $Y/X$ is lossless just by looking at the schema $S$? The answer is yes and in what follows we derive a criterion for lossless abstractions.

It follows from Definition 5, that the necessary and sufficient condition for an abstraction to be lossless is : $Y/X \twoheadrightarrow Y$ in $\bar{S}$ [5]. The following lemma shows that this multivalued dependency holds iff $X \twoheadrightarrow Y$ in $S$.

**Lemma 1.** The multivalued dependency $Y/X \twoheadrightarrow Y$ holds in $\bar{S}$ iff the multivalued dependency $X \twoheadrightarrow Y$ holds in $S$. $\square$

**Proof :** 1) Suppose first that $Y/X \twoheadrightarrow Y$ in $\bar{S}$. It follows that the set $\{y | \bar{y}xyz \in \bar{R}_t\}$ depends only on $\bar{y}$, i.e., only on $x$ (because $\bar{y} = f_{X,Y}(x) = \{y | x*y \in \bar{R}_t[XY]\}$). According to Definition 5, this implies that the set $\{y | xyz \in \bar{R}_t\}$ depends only on $x$, i.e., that $X \twoheadrightarrow Y$ holds in $S$.

2) Suppose now that $X \twoheadrightarrow Y$ holds in $S$ and let $\bar{R}_t \in S$. It follows [5] that
$$ xy_1z_1, xy_2z_2 \in R_t \Rightarrow xy_2z_1, xy_1z_2 \in R_t \quad (1) $$

Let $\bar{y}x_1y_1z_1, \bar{y}x_2y_2z_2 \in \bar{R}_t$ where $\bar{y} = f_{X,Y}(x_1) = f_{X,Y}(x_2)$. We have to show that $\bar{y}x_2y_1z_1, \bar{y}x_1y_2z_2 \in \bar{R}_t$.

It follows from Definition 5 that

$$ x_1y_1z_1, x_2y_2z_2 \in R_t \quad (2) $$

and, as $f_{X,Y}(x_1) = f_{X,Y}(x_2)$, we obtain : $x_1y_2, x_2y_1 \in R_t[XY]$.

Therefore,

$$ x_1y_2z_2, x_2y_1z_1 \in R_t \quad (3) $$

It follows from (1), (2) and (3) that the tuples $\bar{y}x_2y_1z_1$ and $\bar{y}x_1y_2z_2$ both belong to $\bar{R}_t$, Q.E.D. □

As an immediate consequence of Lemma 1 we obtain the following theorem which provides the criterion for a lossless abstraction.

**Theorem 1.** Let R(U) be a relation descriptor. Let X and Y be subsets of U. Let S be a schema of R. Then Y/X is a lossless abstraction iff $X \to Y$ in S. □

## 6. WELL DEFINED ABSTRACTION

Consider again a relation descriptor R(U) and its abstraction R'(U') with respect to a pair (X,Y) of subsets of U. Let S be a schema of R and let $R_t \in S$. In section 4, we defined the abstraction $R'_t$ and we saw how this abstraction can be put into first normal form using an injective function $e : R'_t[Y/X] \to N$. As a result of this normalization we obtained a pair of values $R_{1t}^e$ and $R_{2t}^e$, the n-abstraction and the n-description, respectively. Of course, for each $R_t \in S$ we can define an infinity of such pairs if we consider all possible e's. Thus, we obtain the following schemata

$$ S_1 = \{R_{1t}^e | R_t \in S, e : R'[Y/X] \to N \text{ is injective}\} $$

$$ S_2 = \{R_{2t}^e | R_t \in S, e : R'[Y/X] \to N \text{ is injective}\} $$
For each $R_t \in S$ we have : $R_{1t}^e \in S_1$ and $R_{2t}^e \in S_2$ and, if the abstraction is lossless, we also have : $R_t = (R_{1t}^e * R_{2t}^e)[U]$. Suppose next that we update the n-abstraction $R_{1t}^e$, i.e., change it to a new value $R_{1t}^f \in S_1$, such that $R_{1t}^e[Y/X] = R_{1t}^f[Y/X]$. Does there exist a value in $S$ with n-abstraction $R_{1t}^f$ and n-description $R_{2t}^e$ ? In other words, is it always true that $(R_{1t}^f * R_{2t}^e)[U] \in S$ ?

If this is the case, then we can update n-abstractions without worrying about the n-descriptions. We, therefore, state this property as a second requirement for a good abstraction.

**Definition 6.** Let $R(U)$, $X$, $Y$, $S$, $S_1$, $S_2$ be as above. The abstraction $Y/X$ is well-defined iff $R_t \in S \iff R_{1t}^e \in S_1$ and $R_{2t}^e \in S_2$. $\square$

We now turn into the question of characterizing "good" abstractions, i.e., abstractions that are both lossless and well-defined. Let us consider again the relation descriptor $\bar{R}(\bar{U})$, defined in the previous section. Define a new descriptor $\hat{R}(\hat{U})$ as follows : $\hat{U} = \bar{U}$, but the $Y/X$-domain in $U$ is the set of integers. Let now $\bar{R}_t \in \bar{S}$ and let $e : \bar{R}_t[Y/X] \to N$ be an injective function. Define $\hat{R}_t^e$ by : $nxyz \in \hat{R}_t^e \iff e^{-1}(n)xyz \in \bar{R}_t$ and observe that $\hat{R}_t^e$ is the normalized version of $\bar{R}_t$, using $e$. Thus we have :

$$ \hat{R}_t^e[X\{Y/X\}Z] = R_{1t}^e \quad \text{and} \quad \hat{R}_t^e[Y\{Y/X\}] = R_{2t}^e. $$

Define also the schema $\hat{S} = \{\hat{R}_t^e | \bar{R}_t \in \bar{S} \text{ and } e : \bar{R}_t[Y/X] \to N \text{ injective}\}$.

If the schema $\hat{S}$ is characterized by a set of functional dependencies then, we can use Rissanen's result [7] to decide whether the abstraction is good i.e., lossless and well-defined. This is done as follows : Define $F_i = \{f \in F | f$ holds in $S_i\}$, $i=1,2$. Let $(F_1 \cup F_2)^*$ denote the full family of functional dependencies [1] generated by $F_1 \cup F_2$. Then Theorem 2 in [6] implies the following theorem.

**Theorem 2.** Let $F$, $F_1$, $F_2$ be as above. The abstraction is lossless and well-defined iff

$$ (1) \qquad F = (F_1 \cup F_2)^* $$

$$ (2) \qquad \text{either } Y/X \to Y \text{ or } Y/X \to XZ \text{ is in } F \quad \square $$
# 7. CONCLUDING REMARKS

We have seen a method for translating relations of the relational model into entity/relationship relations. The process by which this is done was called abstraction. Abstraction is done in two levels

(i) starting from a given relation we define its unnormalized abstraction

(ii) using the integers as names, we put this abstraction into first normal form.

We have argued that not all abstractions are good as abstraction may lead to loss of information and/or update anomalies. We have thus introduced loss-less and well-defined abstractions. Good abstractions are only those which possess both these properties. We have also seen criteria to check these properties in a given abstraction.

# REFERENCES

1. Armstrong W.W., Dependency Structures of Data Base Relationships, Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 580-583.

2. Chen P., The Entity-Relationship Model-Toward a Unified View of Data, ACM Trans. on Database Systems, Vol. 1, N° 1, March 1976, pp. 9-36.

3. Codd E.F., A Relational Model for Large Shared Data Banks, Communications of the ACM, Vol. 13, N° 6, June 1970, pp. 377-387.

4. Codd E.F., Further Normalization of the Data Base Relational Model, Courant Comp. Sc. Symp. 6 : Data Base Systems, Prentice Hall, N.I., May 1971, pp. 65-98.

5. Fagin R., Multivalued Dependencies and a New Normal Form for Relational Databases, ACM Trans. on Database Systems, Vol. 2, N° 3, Sept. 1977, pp. 262-278.

6. Makinouchi A., A consideration on Normal Form of Not-necessarily Normalized Relation in the Relational Data Model, Proceedings very Large Data Bases Third International Conf. Tokyo, Japan, October 6-8, 1977, pp. 447-453.

7. Rissanen J., Independent Components of Relations, ACM Trans. on Database Systems, Vol. 2, N°4, Dec. 1977.

8. Schmid H.A. and Swenson H.A., On the Semantics of the Relational Data Model, Proc. ACM SIGMOD Conf. Wif. King, Ed., San Jose, Cal., May 1975, pp. 211-223.

9. Smith J.M. and Smith D.C.P., Database Abstractions : Aggregation and Generalization, ACM Trans. on Database Systems, Vol. 2, N° 2, June 1977, pp. 105-133.

10. Spyratos N. and Bancilhon F., Name Independence in Relational Data Bases, ICMOD Conference 78, Milan, Italy, June 1978.