# Name independence in relational data bases

Nicolas Spyratos, Francois Bancilhon

► To cite this version:

Nicolas Spyratos, Francois Bancilhon. Name independence in relational data bases. [Research Report] IRIA-RR-241, IRIA. 1977, pp.44. hal-04716426

HAL Id: hal-04716426

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

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

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

NAME INDEPENDENCE
IN RELATIONAL
DATA BASES

Nicolas SPYRATOS
François M. BANCILHON

Rapport de Recherche N° 241

Août 1977
NAME INDEPENDENCE IN RELATIONAL
DATA BASES

Nicolas Spyratos*, François Bancilhon**

Résumé :

Dans un système de bases de données «purement» relationnel, les contraintes d’intégrité (donc la définition du schéma) doivent être spécifiées en terme de propriétés des relations et ceci indépendamment des noms ou valeurs des objets participant à ces relations. Cette propriété, que nous appelons «l’indépendance des noms», a été discuté de manière intuitive par plusieurs auteurs. Cependant aucune approche formelle n’a été proposée.

D'autre part, il a été remarqué que l'indépendance des noms ne s'applique pas à tous les types de données. Ceci est dû au fait que certaines relations (que nous appelerons «connues») dépendent en fait de la valeur des noms des objets qu'elles relient.

Dans cet article, nous proposons un modèle qui nous permet de définir rigoureusement les notions de relations indépendantes des noms et des relations connues. En outre, une caractérisation équivalente de l'indépendance des noms est donnée en termes de probabilités, en utilisant la notion de l'estimation qu'a un usager de la base de données.

Pour définir cette estimation, la base est représentée comme un ensemble de propositions. Ces propositions (et leurs valeurs) décrivent le contenu en information de la base.

Abstract :

In a «pure» relational system, integrity constraints should be specified by properties of relations and independently of the names of the objects participating in these relations. This property, that we shall call «name independence», has been intuitively discussed by several authors. However, no formal approach has been proposed. Also, it has been pointed out in the litterature, that name independence does not apply to all types of data. This is due to the fact that some relations, that we shall call «known», do depend on the names of the objects that they relate. In this paper, a model is proposed that allows us to rigorously define the concept of a name independent relation and that of a known relation. Also an equivalent characterization of name independence is obtained in terms of probabilities. This is done using the notion of a «user's estimate» of the data base.

In order to define user's estimation, the data base is represented by a set of propositions. These propositions along with their truth values describe the information content of the data base. As the truth values of certain propositions may be declared confidential, this approach seems to be also suitable for studying protection of information in relational data bases.

<footnote>* Post Doctoral Fellow of the National Research Council of Canada.</footnote>

<footnote>** IRIA/LABORIA.</footnote>
<figure><img src="image_3.png" /></figure>

# 1 - INTRODUCTION

In the data base relational model the state of a data base (we shall call it a *configuration*) is represented by a set of relations over a finite set of objects. It is very important to distinguish between the notion of a state (i.e. the instantaneous description of the data base) and that of the set of possible states. This set (we shall call it the *schema*) plays an important role in the modeling of data bases.

Schemata can be specified in two different ways :

(i) By people who really use them and know what they are. These are programmers, users and Data Base Administrators (DBA's).

(ii) By people who never use them and, most likely, have never even seen one. And these are theoreticians.

Practicioners have a neat and simple way of defining schemata : they use the Data Definition Language (DDL) provided in their Data Base Management System (DBMS). This language describes clearly the possible schemata that a programmer, a user or a DBA can define. However, the DDL's provided by the various systems vary widely in their capabilities (i.e. in the kind of schemata they allow one to define). It is possible to show what are the limits of a DDL by demonstrating some properties that it cannot express. For instance [BARBOSA 76] demonstrates some capabilities missing from SOCRATE [ABRIAL 72] and suggests some modifications (i.e. some improvements) of the DDL.

For theoreticians, life is a little harder. It is widely accepted that a schema is defined by the properties that its configurations must satisfy. Some types of properties are now accepted as necessary in a DDL. This is the case of functional dependencies [CODD 71a]. Other properties known as "integrity constraints" are presently subject to discussion [ABRIAL 74, ESWARAN 74, HAMMER 75, STONEBRAKER 75]. In any case, no one, to our own knowledge, has given a general definition of a schema.
Note that in other areas of computer science, general definitions of some practical concepts have been given and have found practical application. For instance, programs have been modeled by recursive functions and Turing machines. This has provided the capability to establish whether a programming language is sufficient to write all programs (i.e., whether it is complete).

A similar contribution of the relational model would be a general definition of a schema, from which one could decide whether a DDL is complete. As a first step in this direction, we propose in this paper the study of one property of schemata that we call *name independance*.

In section 2, we recall the main definitions from the relational model and we introduce our notation. In section 3, we study the concept of a query as defined in the relational model. Section 4 is an informal discussion of name independance that leads to the formal definition of this concept. The notion of user's knowledge is introduced in section 5. This yields our alternative definition of name independence in section 6. The equivalence of the two definitions, which is the main result of the paper, is shown in section 7. Finally, we extend our model to a more realistic one in section 8.

## 2 - THE RELATIONAL MODEL

In the relational model, the state of a data base at any given moment in time is represented by a set of relations (between certain objects). The set of possible states is the data base schema.

The basic notion of this model is that of a relation. A relation is defined by means of a relation descriptor and can take values in specified sets, called domains. Let us define formally these concepts.
**Definition 2.1 :**

A relation descriptor consists of a relation name r and a set of n attribute names $A_1, A_2, \dots, A_n$. It is denoted by

$$r(A_1, A_2, \dots, A_n)$$

The integer n is called the relation order and it is denoted by $||r||$.

The order in which the attribute names appear is immaterial. ■

An example of a relation descriptor is the following

is-child-of (Child, Parent)

The relation name in this descriptor is : "is-child-of", and the attribute names are : "Child" and "Parent". As there are two attribute names, the relation order is 2, that is : $||is-child-of|| = 2$. Let us note here that a relation of order 2 is usually refered to as a binary relation ; a relation of order 1 as unary.

Let us now define the value of a relation. In the strict mathematical sense of the word, the value of an n-ary relation over the domains $D_1, D_2, \dots, D_n$ is a set of n-tuples $(x_1, x_2, \dots, x_n)$ where each $x_i$ is in $D_i$ i.e., value (r) $\subset D_1 \times D_2 \times \dots \times D_n$. In the relational model the value of a relation $r(A_1, A_2, \dots, A_n)$ over the domains $D_1, D_2, \dots, D_n$ is a finite set of n-tuples. But now, the elements of an n-tuple, that we shall call attributes, are not distinguished by their position but by their names. In order to simplify matters we shall assume, for the moment, that we have a single domain D. This leads to the following definition.

**Definition 2.2 :**

Let $r(A_1, A_2, \dots, A_n)$ be a relation descriptor. Let D be a domain. A value of r on D is a finite set of n-tuples. The attributes of each n-tuple are elements of D and they are associated with the $A_i$'s. ■
Since we are dealing with data which can be coded into a computer, all domains will be assumed countable.

We shall represent the value of a relation by a table in which rows represent tuples and columns represent attributes. As each column is indexed by one attribute name the order of the rows and of the columns is irrelevant.

As an example consider the value of the relation "is-child-of" shown in Figure 1. In the pair (John, William) of this value, John is the Child-attribute and William is the Parent-attribute. Similarly, in the pair (Mary, William), Mary is the Child-attribute and William is the Parent-attribute. The domain D in this example is the set of all given names which is a subset of the set of character strings. In what follows, we shall not explicitly mention the domain D whenever it is clearly understood from the context.

A relation in a data base is created by declaring a relation name, the attribute names, and a domain name, and then defining the domain and the values of the relation. Note that domain and relation names are unique with respect to a data base and that attribute names are unique with respect to a relation.

The domain D of a relation r is defined at the time the data base is created ("compile time"). There is a number of ways to define a domain. For instance, a high level non-procedural language can be used. We shall not discuss domain definition here. A detailed discussion on the subject can be found in [McLEOD 76]. What is important to remember here, is that the domain D, once defined at "compile time", will not change during the day-to-day operation of the data base system ("run time"). What is normally changed during "run-time" is the value of the relation r. Thus, suppose that at a
given instant of time $\tau$, the value of the relation $r$ is a set of tuples,
say, the set $\tau(r)$. At a different instant of time $\tau'$, this set of tuples may
be changed (e.g. by the addition of new tuples) to a new set $\tau'(r)$. This new
set of tuples is the value of the relation $r$ at time $\tau'$.

Now, a data base usually consists of more than one relation. The
set of all relation descriptors in a data base is the alphabet.

**Definition 2.3 :**

Any *finite* set of relation descriptors is called a *relational alphabet*.

As an example, consider the following set of relation descriptors

$$R = \{\text{is-male (Male), is-female (Female), is-child-of (Child, Parent), is-married-to (Spouse 1, Spouse 2)}\}$$

This is a relational alphabet that consists of two unary and
two binary relations. In what follows, we shall refer to the data base described
by this alphabet as the "family data base". Note that the domain of every
relation in this alphabet is the same subset of the set of character strings,
namely, the set of all given names. It is not necessary that the domains of
all relations in an alphabet be the same. However, in order to simplify matters,
we shall assume that all relations in an alphabet take their values in the
same domain $D$. This assumption is not necessary and it will be removed later
GLOSSARY FOR DEFINING RELATIONAL ALPHABETS
*(section 8).*

A relational alphabet describes a data base in the following sense :
At any given instant of time $\tau$, the values of the relations of the alphabet
represent the state of the data base at that time, i.e., they represent the
configuration of the data base at time $\tau$.
**Definition 2.4 :**

Let $R$ be a relational alphabet. Let $D$ be the (common) domain in which the relations of $R$ take their values. A **data base configuration** on $R$ and $D$ is a function $\tau$ that associates a value, $\tau(r)$ in $D$ with every relation $r$ of the alphabet $R$. ■

Thus, in order to define a configuration $\tau$ we must define $\tau(r)$ for every relation $r \in R$. The following is an example configuration of the family data base.

$\tau(\text{is-male}) = \{\text{John, Peter, William}\}$

$\tau(\text{is-male}) = \{\text{Mary, Susan}\}$

$\tau(\text{is-child-of}) = \{(\text{John, William}), (\text{Mary, William})\}$

$\tau(\text{is-married-to}) = \{(\text{Susan, William}), (\text{William, Susan})\}$

The set of objects of the domain $D$ that appear in this configuration is the following

$\{\text{John, Peter, William, Mary, Susan}\}$

This set will be referred to as the object set of the configuration and it will play an important role in our discussion later.

**Definition 2.5 :**

Let $\tau$ be a configuration on $R$ and $D$. The set of objects of $D$ that appear in at least one value $\tau(r)$, $r \in R$, is called the **object set** of $\tau$. It will be denoted by $X_\tau$. ■

Let us recall again that a configuration on $R$ and $D$ represents a state of the data base. And, unless a constraint is imposed to the data base, any conceivable configuration on $R$ and $D$ can represent a possible state. Of course, in the presence of constraints, some configurations on $R$ and $D$ do not represent possible states of the data base. For instance, in the family data base, the fact that a person is either male or female (but not both) is a
constraint. As a consequence of this constraint, any configuration $\tau'$ on $R$ and $D$ such that

$$ \tau'(\text{is-male}) \cap \tau'(\text{is-female}) \neq \emptyset $$

is not a possible configuration of the family data base.

The set of possible configurations of a data base is the data base schema.

**Definition 2.6 :**

Let $R$ be a relational alphabet. Let $D$ be the (common) domain in which the relations of $R$ take their values. Let $S_F(R, D)$ denote the set of all configurations on $R$ and $D$. Then, any subset of $S_F(R, D)$ is called a **data base schema** on $R$ and $D$. In particular, the set $S_F(R, D)$ is called the **free schema** on $R$ and $D$. ■

For convenience, the alphabet and the domain of a configuration or a schema will not be mentioned when they are clearly understood from the context.

How does one specify a schema? In general, a subset of a given set is specified in two ways :

(i) By a property (or a set of properties) that characterizes all its members.

(ii) In a "constructive way" whereby, we are given an "initial (or starting) member" of the subset and a rule for generating new members from old.

Both these ways can be applied in specifying a schema as a subset of a given free schema. For instance, the family data base schema is a subset
of the free schema on the alphabet R and domain D that we saw earlier. The
properties that characterize a configuration τ of the family data base
schema, i.e., the properties that define this schema, are the following :

1 - Every person is either male or female but not both,

2 - "is-married-to" is a symmetric relation,

3 - If (x, y) ∈ τ(is-married-to), then one of x, y is a male and
the other is a female.

4 - If (x, y) ∈ τ(is-married-to) then there is no z different
than y such that (x, z) ∈ τ(is-married-to),

5 - If (x, y) ∈ τ(is-child-of) and if (y, z) ∈ τ(is-married-to)
then (x, z) ∈ τ(is-child-of) and there is no w different than y
and different than z such that (x, w) ∈ τ(is-child-of),

6 - If any $x_1, x_2, \dots, x_n$ are such that $(x_2, x_1) \in \tau(\text{is-child-of})$, $(x_3, x_2) \in \tau(\text{is-child-of})$, \dots, $(x_n, x_{n-1}) \in \tau(\text{is-child-of})$, then all $x_1, x_2, \dots, x_n$ are distinct.

Alternatively, the family data base schema can be generated by the
example configuration if we apply to it the following transformations :

1 - A person can die.

2 - Two married persons can divorce.

3 - Two unmarried persons, a male and a female (that do not belong to the same family), can get married.

4 - New persons can be born. Each new person is either male or female (but not both) and has at most one parent from each sex.
By the way, the integrity problem in data bases consists of showing
that the two types of schema definition yield the same set of configurations.

It is important to note that in our example of the family data
base, the schema is defined through the properties of its relations. The
properties of the objects that these relations relate are not important for
the definition of the schema. It is precisely this observation that we wish
to explore further in this paper.

## 3 - COMPUTING NEW RELATIONS

In [CODD 71b] a query language is introduced for relational
data bases. The basic idea is that any query on a data base can be viewed as
the *definition* of a relation of the data base. The answer to the query is the
*value* of this relation. In this section, we shall be interested in the way
one defines relations.

Let us recall that when defining relations we have been very
careful to distinguish between the *name* and the *value* of a relation. We are
going to apply the same distinction here. First, we shall define a relational
calculus, similar to that of [CODD 71b] (we shall discuss the differences
later).

### *Definition 3.1 :*

Let $R$ be a relational alphabet. The *Relational Calculus Vocabulary*
on $R$ consists of the following :

Object variables : $x_1, x_2, x_3, ...$

Relational Names : $\{r_1, r_2, ..., r_n\} = R, =, \ne$

Attribute Names : $A_1, A_2, ...$

Logical Symbols : $∃, ∀, Λ, V, \setminus$

Delimiters : (, ), :

■
### Definition 3.2:

Let $R$ be a relational alphabet. The relational calculus on $R$ (denoted as $C(R)$) is a language of well formed formulae (wff) defined as follows:

1. Let $r(A_1, A_2, ..., A_n)$ be a relation descriptor in $R$. Let $x_1, x_2, ..., x_n$ be a set of n object variables. Then, $r(A_1:x_1, A_2:x_2, ..., A_n:x_n)$ is a wff.

2. Let $x_1$ and $x_2$ be two object variables. Then, $(x_1 \neq x_2)$ and $(x_1 = x_2)$ are wff's.

3. Let $\Gamma$ be a wff; then $\Gamma$ is a wff.

4. Let $\Gamma_1$ and $\Gamma_2$ be two wff's; then $\Gamma_1 \wedge \Gamma_2$ and $\Gamma_1 \vee \Gamma_2$ are wff's.

5. Let $\Gamma$ be a wff in which $x$ is a free variable (according to the usual definition); then, $\forall x(\Gamma)$ and $\exists x(\Gamma)$ are wff's.

6. No other formulae are wff's. ■

Note that up to now we have merely defined a language. In some cases, we shall write $r(x_1, x_2, ..., x_n)$ instead of $r(A_1:x_1, A_2:x_2, ..., A_n:x_n)$. It is then to be understood that the attributes are ordered as they were declared. We shall also write $x$ $r$ $y$ instead of $r(x, y)$ when $r$ is binary.

Examples of wff's from the family data base schema are:

$$ \Gamma_1 = \exists x_1 (\exists x_2 (\exists x_3 (x \text{ is child of } x_1 \wedge x_1 \text{ is-child-of } x_2 \wedge x_3 \text{ is-child-of } x_2 \wedge y \text{ is-child-of } x_3 \wedge x_1 \neq x_3))) $$
$$ \Gamma_2 = \exists x_1 (x \text{ is-child-of } x_1 \land x_1 \text{ is-child-of } y) $$

$$ \Gamma_3 = \forall x_1 (\neg x_1 \text{ is-child-of } y). $$

Let us now define the semantics of these expressions.

**Definition 3.3 :**

Let $R$ be a relational alphabet. Let $\Gamma \in C(R)$ be a wff in which the free variables are $x_1, x_2, \dots, x_n$. Let $r(A_1, A_2, \dots, A_n)$ be a relation descriptor *not* in $R$ (i.e. $r$ and $A_i$'s are new names). Then the expression

$$ r(A_1:x_1, A_2:x_2, \dots, A_n:x_n) : \Gamma $$

is called a *Relation Definition Expression (RDE)*. ■

Examples of RDE in the family data base are the following:

Cousin(Cousin 1:x, Cousin 2:y) : Γ₁

Grandparent(Grandp:x, Granchild:y) : Γ₂

Orphan(Orphan:x) : Γ₃

By looking at $\Gamma_1$, it should be clear that the cousin RDE specifies a relation between x and y which is true iff x and y are cousins. The Grandparent RDE specifies a relation between x and y which is true iff x is a grandparent of y, and the Orphan RDE specifies a unary relation which is true for x iff x is an orphan. This is how a RDE can be interpreted. For the reader interested in formal definitions, we now state formally how a wff should be interpreted.
**Définition 3.4 :**

Let $\tau$ be a configuration on $R$ and $D$. Let $\Gamma$ be a wff of $C(R)$ with free variables $x_1, x_2, \dots, x_n$. Then $\Gamma$ is interpreted by a predicate(*) $p(x_1, \dots, x_n)$ on $D^n$ defined recursively as follows :

$$ (1) \qquad r(A_1 : x_1, A_2 : x_2, \dots, A_n : x_n) $$

is interpreted by the predicate $p(x_1, \dots, x_n)$ which is true iff
$(x_1, x_2, \dots, x_n) \in \tau(r)$.

$$ (2) \qquad (x_1 = x_2) $$

is interpreted by the predicate $p(x_1, x_2)$ which is true iff $x_1 = x_2$ ; ($x_1 \neq x_2$)
is interpreted by the predicate $p(x_1, x_2)$ which is true iff $x_1 \neq x_2$.

(3) Let $\Gamma$ be interpreted by the predicate $p(\bar{x})$. Then $\Gamma'$ is interpreted by the predicate $p'(\bar{x})$ defined by

$$ \begin{align*} p'(\bar{x}) &= \text{True, if } p(\bar{x}) \text{ is false and } \bar{x} \in X_{\tau}^{n} \\ &= \text{False, otherwise} \end{align*} $$

(4) Let $\Gamma$ be interpreted by $p(x_1, x_2, \dots, x_m)$. Let $\Gamma'$ be interpreted by $p'(x'_1, x'_2, \dots, x'_n)$. Define,

$$ \{y_1, y_2, \dots, y_r\} = \{x_1, x_2, \dots, x_n\} \cup \{x'_1, x'_2, \dots, x'_m\} $$

Then $\Gamma \land \Gamma'$ is interpreted by $p_1(y_1, y_2, \dots, y_r)$ defined by

$$ p_1(\bar{y}) \text{ True} \iff p(\bar{x}) \text{ True and } p(\bar{x}') \text{ true,} $$

and $\Gamma \lor \Gamma'$ is interpreted by $p_2(y_1, \dots, y_r)$ defined by :

$$ p_2(\bar{y}) \text{ True} \iff p(\bar{x}) \text{ True or } p(\bar{x}') \text{ True} $$

<footnote>(*) Recall that a predicate on $D^n$ is a function from $D^n$ into $\{\text{True, False}\}$</footnote>
(5) Let Γ be interpreted by $p(x, x_1, ..., x_n)$. Then $\Box x(Γ)$ is interpreted by $p_1(x_1, x_2, ..., x_n)$ defined by :

$p_n(x_1, x_2, ..., x_n)$ True $\Leftrightarrow$ $\Box x p(x, x_1, ..., x_n)$ True

where $\Box$ represents $\forall$ or $\exists$. ■

Let now $r(A_1:x_1, ..., A_n:x_n) : Γ$ be a RDE. $x_1, x_2, ..., x_n$ are the free variables of Γ. Therefore, given a configuration $τ$, Γ is interpreted by a predicate $p(x_1, ..., x_n)$; we shall say that the value of $r$ in the configuration $τ$ is the set of tuples for which $p$ is true.

The set of all new relation names that we can define by RDE's will be denoted by $R^*$.

## 4 - NAME INDEPENDENCE

In recent years, a great deal of effort was invested in the definition of a "conceptual model" (see, for instance, [NIJSEN 76]). This model should provide a unified view of data whereby all semantic constraints could be stated.

Most suggestions for such a model have a relational flavor, that is, data is structured in a set of relations whose attributes take values in specified domains. Most authors [ABRIAL 74, BRACCHI 76, HALL 75] agree on the necessity of having a special domain, the internal domain, which has some strange characteristics. Probably the best definition of this domain is in [BRACCHI 76], which we quote here :

"... The internal type has the following characteristics :
a) The values of an internal domain do not have any meaning by themselves.

b) An element of an internal domain acquires a meaning when it is related (via relations) to values of different domains.

c) As a consequence of point a), it is not allowed to specify a subset of an internal domain through a listing of the values belonging to it (...)

f) The only predicate meaningfully applicable to an internal value is to test its equality with another internal value...".

We could summarize this definition by saying that the only structure on the internal domain is the one defined by the data base relations on that domain and the relation of equality. Moreover, one cannot name the elements of that domain. In [BANCILHON 76] a notion of "name independence" was introduced. The basic idea was that in a "pure" relational system, everything should be stated in terms of relations. In particular, schemata should be specified by properties of relations and independently of the values of the elements in the object sets of these relations. It turns out that name independence, in the sense just described, includes the notion of the internal domain.

As explained in section 2, a data base is usually defined on multiple domains. However we have chosen to present the notion of name independence assuming first a single domain. In section 8, we shall see how different domains can be introduced.

We mentioned earlier that a schema should be defined by properties of relations and independently of properties of the elements in the object sets of these relations. In other words, if two configurations have the same "relational structure" (whatever that means) then, even if they have different object sets, they should both belong (or not belong) to the schema. Let us
illustrate this point using the example configuration $\tau$ of the family data base (Figure 1). The object set of this configuration is the following

$$X_{\tau} = \{John, Peter, William, Mary, Susan\}$$

Suppose now that we "rename" all these people by giving them, say, French names. We obtain the set

$$X'_{\tau} = \{Jean, Pierre, Guillaume, Marie, Susanne\}$$

This renaming implies also renamings of the relation values, as shown in Figure 1.

Thus, as a result of renaming the object set of the configuration $\tau$, we obtained a new configuration $\tau'$. The new configuration also belongs to the family data base schema. This can be easily checked by looking at any of the two definitions of this schema given in section 2. This observation will lead to our definition of name independence. First, let us formalize the renaming process.

**Definition 4.1 :**

Given a domain $D$ and a finite subset $X \subset D$, a renaming of $X$ is an injective mapping from $X$ into $D$.■

Let now $\bar{x} = (x_1, x_2, \dots, x_n)$ be an $n$-tuple of $X^n$ and let $\alpha$ be a renaming of $X$. We define

$$\alpha(\bar{x}) = (\alpha(x_1), \alpha(x_2), \dots, \alpha(x_n))$$

and we call $\alpha(\bar{x})$ the renaming of $\bar{x}$ by $\alpha$. Let us now see what is the effect of a renaming on a configuration.
## Definition 4.2

Let $R$ be a relational alphabet and let $D$ be a domain. Let $\tau$ be a configuration of $S$ ($R$, $D$) and let $X_\tau$ be its object set. Let $\alpha$ be a renaming of $X_\tau$. The renaming of $\tau$ by $\alpha$, denoted by $\tau_\alpha$, is a configuration defined as follows:

$$ \bar{x} \in \tau(r) \Leftrightarrow \alpha(\bar{x}) \in \tau_\alpha(r) \quad \blacksquare $$

This definition implies that: $X_{\tau_\alpha} = \alpha(X_\tau)$ and, as $\alpha$ is an injective mapping, we obtain that: $|X_{\tau_\alpha}| = |X_\tau|$. Note that in fact, $\tau$ and $\tau_\alpha$ are isomorphic (under the isomorphism $\alpha$).

It is our thesis that a schema should be defined only in terms of properties of relations an independently of their object sets. This can be stated as follows:

## Definition 4.3:

Let $S$ be a schema on $R$ and $D$. $S$ is a *name independent schema* iff:

$$ \forall \tau, \tau \in S, \forall \alpha, \alpha \text{ renaming of } X_\tau, \tau \in S. \blacksquare $$

This definition simply states that every renaming of every configuration of $S$ is also in $S$. In other words, that $S$ is closed under renaming.

# 5 - USER'S ESTIMATION

At any given point in time, a user of a data base does not know what configuration is actually there. However, the user knows (at least) what
the data base schema is. That is, the user knows what are the invariant properties of the configurations.

Using this knowledge, the user can estimate the chances that a statement (concerning the data base) has to be true or false. Or, the user can estimate the average value that a certain attribute can take, and so on. For instance, in a data base concerning a set of persons and their ages, a user can estimate that the statement : "John is older than 25", has 60 % chances to be true. We shall be interested first in determining how such a probability can be established. To do this, let us first define formally the notion of a "statement".

**Definition 5.1 :**

Let R be a relational alphabet and let D be a domain. A proposition on R and D is a pair

$$p = (r, \bar{x})$$

where $r \in R^*$ and $\bar{x} \in D \|r\|$. ■

For instance, in the family data base,

$p_1 = (\text{is-married-to}, (\text{Susan, William}))$

$p_2 = (\text{is-male}, \text{Mary})$

$p_3 = (\text{cousin}, (\text{Susan, William}))$

are propositions.

Let P denote the set of all propositions on R and D. We shall consider the usual logical structure on P, defined by the operators :
A, V, and $\supset$. Also, given a proposition p = (r, $\bar{x}$) and a configuration $\tau$ on R and D, we shall say that p is true in $\tau$, if $\bar{x} \in \tau(r)$; otherwise, we shall say that p is false in $\tau$. For instance, in the family data base, the proposition p₁ defined earlier, is true in the example configuration $\tau$ (Figure 1). On the other hand, the proposition p₂ is false in that same configuration.

Now that we have defined what we mean by a proposition, let us see how we can evaluate the probability of a proposition to be true. To do this, we need a sample space $\Omega$, an event space $\mathcal{A}$ on $\Omega$, and a probability measure prob on $\mathcal{A}$. We shall discuss first the case of a finite schema. Then, we shall extend our model to any schema.

## The finite schema

We shall consider here a schema on a finite domain $D_0$. Since the domain is finite, the free schema $S_F(R, D_0)$ is finite, that is,

$$|S_F(R, D_0)| < \infty$$

Therefore, any schema S on R and $D_0$ is finite.

Now, think of a user being on the one side of a "wall" (Figure 2) that "hides" from him the actual data base configuration $\tau_0$. Moreover, suppose that the only thing that the user knows about any configuration $\tau$, is that it belongs to the schema S (that is, suppose that the user knows only the invariant properties of the configurations of S). To such a user, the actual configuration $\tau_0$ is one of the possible values (outcomes) that $\tau$ can take. The set of all possible values for $\tau$ is precisely the schema S. Therefore, the sample space $\Omega$ is the schema S, i.e., $\Omega = S$.
As this is a finite sample space, we shall associate to it its power set as an event space, i.e.,

$$A = P(\Omega)$$

Finally, we wish to define a probability measure prob on A that reflects the knowledge of the user. As the only thing that the user knows about a configuration τ is that it belongs to S, every outcome of τ is equally likely. Therefore, we shall define the probability measure as follows :

$$prob(\tau) = 1/|S|$$

Note that we can define this probability measure only because $|S| < \infty$.

A proposition p on R and D₀ defines a mapping

$$p : \Omega \rightarrow \{\text{True, False}\}$$

such that, for each τ ∈ Ω,

$p(\tau) = \text{True, if p is true in } \tau$

$= \text{False, if p is not true in } \tau$

Therefore, p can be regarded as a random variable. Its distribution function is defined by the probability that p is true. This probability, that we shall denote as : prob(p is true), can be computed as follows :

$$prob(p \text{ is true}) = \frac{|\{\tau | \tau \in S \text{ and } p(\tau) = \text{True}\}|}{|S|}$$

It is simply the probability that p is true, as estimated by the user. Thus, we can represent the user's estimate of a data base configuration by a mapping
$E : P \to [0, 1]$

from the set P of all propositions on R and $D_0$ into the interval $[0, 1]$. This mapping associates with each proposition p $\in$ P, the probability of this proposition to be true. That is,

$$E(p) = \text{prob}(p \text{ is true}), \forall p \in P$$

We would like now to extend this definition of the user's estimate to an infinite schema.

**The infinite schema :**

In an infinite schema S, on alphabet R and domain D, where all configurations are equally likely, we have : $prob(\tau) = 0, \forall \tau \in S$. This, certainly won't help us to express the user's knowledge. Instead of defining a new probability measure, we choose to consider a family of conditional measures on finite schemata. That is, we define

$$prob(\tau | X_{\tau} \subset D_0)$$

which is the probability of the configuration $\tau$, given that its object set is included in some finite domain $D_0$ (of course, $D_0 \subset D$). As the schema

$$S_{D_0} = \{\tau | \tau \in S \text{ and } X_{\tau} \subset D_0\}$$

is a finite schema we can proceed in the manner already described to obtain the (conditional) user's estimate $E_{D_0}$.

The sample space is now $\Omega_{D_0} = S_{D_0}$ and every proposition p on R and D defines, as before, the mapping
$p : \Omega_{D_0} \rightarrow \{\text{True, False}\}$

The (conditional) probability of a configuration $\tau \in S_{D_0}$ is

$$ \text{prob}(\tau | X_{\tau} \subset D_0) = 1 / |S_{D_0}| $$

The (conditional) distribution function of a proposition p on R and D is
defined by the following probability

$$ \text{prob}(\text{p is true} | S_{D_0}) = \frac{|\{\tau \mid \tau \in S_{D_0} \text{ and } p(\tau) = \text{True}\}|}{|S_{D_0}|} $$

The (conditional) user's estimate of a data base configuration is
now represented by the mapping

$E_{D_0} : P \rightarrow [0, 1]$

from the set P of all proposition on R and D into the interval $[0, 1]$. This
mapping associates with each proposition p $\in$ P, the (conditional) probability
of this proposition to be true. That is,

$$ E_{D_0}(p) = \text{prob}(p \text{ is true} | S_{D_0}), \forall p \in P $$

If we let $D_0$ run through all finite subsets of D, we obtain a family of
functions $E_{D_0}$. Each function represents the user's (conditional) estimates
of the propositions on R and D.

## 6 - EQUAL EXPECTATION SCHEMA

Now that we have formally defined the user's estimate, let us
discuss again name independence in terms of this notion. What name independence
implies is that every property of the schema can be stated in terms of the
properties of its relations, and independently of properties of the objects participating in these relations.

We saw in the previous section that the user's knowledge of a proposition $p = (r, \bar{x})$, on an alphabet $R$ and a domain $D$, can be represented by the following set of estimates

$$ \{E_{D_0}(p) | D_0 \text{ is finite and } D_0 \subset D\} $$

The proposition $p$ consists of two parts, a relation name $r \in R^*$ and a list $\bar{x}$ of parameters. In a name independent schema, it seems natural to say that user's estimate is independent of the list of parameters. In the next section we shall see that this is indeed the case. First, however, let us introduce some notation and definitions.

**Definition 6.1 :**

Let $D$ be a domain. Two $n$-tuples $\bar{x}$ and $\bar{x}'$ of $D^n$ are said to be equivalent (we denote this as : $\bar{x} \equiv \bar{x}'$), iff there exists a renaming $\alpha$ of $\bar{x}$ such that $\alpha(\bar{x}) = \bar{x}'$. ■

It is easy to check that this relation is indeed an equivalence relation on the set $D^n$. Examples of equivalent tuples are

(John, Peter) and (Bruce, William)

(William, Peter, William) and (Bruce, John, Bruce)

An example of two non-equivalent tuples is the following

(John, Peter) and (Bruce, Bruce)

These tuples are not equivalent as there can be no bijection between their attributes.
From the user's point of view, the only thing that distinguishes two equivalent tuples of a schema is the value of their attributes. Therefore, in a name independent schema, two equivalent tuples should be indistinguishable by the user.

**Definition 6.2 :**

A schema S on alphabet R and domain D is an equal expectation schema, iff $\forall r, r \in R^* ; \forall D_0 \subset D$ such that $D_0$ is finite ; $\forall \bar{x}$ and $\bar{x}'$ in $D_0 \|r\|$ such that $\bar{x} \equiv \bar{x}'$ we have

$$E_{D_0}((r, \bar{x})) = E_{D_0}((r, \bar{x}')) \blacksquare$$

That is, in an equal expectation schema the user's estimate of a proposition $p = (r, \bar{x})$ remains the same under any renaming of the parameters in the list $\bar{x}$. As an example, consider the following propositions of the family data base

$$p_1 = (r = \text{is-child-of}, \bar{x}, = (\text{John}, \text{Peter}))$$

$$p_2 = (r = \text{is-child-of}, \bar{x}_2 = (\text{Bruce}, \text{William}))$$

$$p_3 = (r = \text{is-child-of}, \bar{x}_3 = (\text{Bruce}, \text{Bruce}))$$

The user's estimate of $p_1$ is the same as that of $p_2$. This is so because $p_2$ can be obtained from $p_1$ through a renaming of the list $\bar{x}_1$ (i.e., $\bar{x}_1 = \bar{x}_2$). However, the user's estimate of $p_3$ is not the same as that of $p_1$ as there is no renaming of the list $\bar{x}_1$ that can generate the list $\bar{x}_3$ (i.e., $\bar{x}_3 \neq \bar{x}_1$). Loosely speaking, to a user who knows only the invariant properties of the family data base configurations, John has as many chances to be a child of Peter (proposition $p_1$) as Bruce has to be a child of William (proposition $p_2$). However, John's chances of being a child of Peter are not the same as Bruce's being a child of Bruce (proposition $p_3$).
We shall now proceed to present the main result of this paper, namely, that name independence and equal expectation are equivalent properties of schemata.

# 7 - EQUIVALENCE

In this section we show the equivalence between name independence and equal expectation. In order to do so we need to establish some preliminary facts.

First, recall that given a schema S, on alphabet R and domain D, and a subset $D_0 \subset D$, the subset $S_{D_0}$ of S is defined as follows

$$S_{D_0} = \{\tau | \tau \in S \text{ and } X_{\tau} \subset D_0\}$$

Note that $S_{D_0}$ is a schema on R and $D_0$ and that any renaming $\alpha_0 : X_{\tau} \to D_0$ is also a renaming in D.

Suppose that S is a name independent schema, on alphabet R and domain D, and let $D_0$ be any subset of D. Let $\tau$ be a configuration of $S_{D_0}$ and let $\alpha_0$ be a renaming of $X_{\tau}$ in $D_0$. The mapping $\alpha_0$ is also a renaming of $X_{\tau}$ in D. As S is name independent, the configuration $\tau_{\alpha_0}$ (i.e., the renaming of $\tau$ under $\alpha_0$) belongs to S. As $X_{\tau_{\alpha_0}} = \alpha_0(X_{\tau}) \subset D_0$, the configuration $\tau_{\alpha_0}$ belongs to $S_{D_0}$. This implies that the schema $S_{D_0}$ is name independent. This is true for any choice of the subset $D_0 \subset D$.

Suppose next that the schema $S_{D_0}$ is name independent for any choice of a finite subset $D_0 \subset D$. Let $\tau$ be a configuration of S and let $\alpha$ be a renaming of $X_{\tau}$ in D. The mapping $\alpha$ is also a renaming of $X_{\tau}$ in the following subset of D
$$D_0 = X_\tau \cup \alpha(X_\tau)$$

As $X_\tau \subseteq D_0$, the configuration $\tau$ belongs to $S_{D_0}$. On the other hand, as $X_\tau$ is a finite set, so is $D_0$. Then, by our assumption, $S_{D_0}$ is name independent. This implies that $\tau_\alpha$ belongs to $S_{D_0}$ and, therefore, to $S$. We have thus proved the following theorem.

**Theorem 7.1** : Let $S$ be a schema on alphabet $R$ and domain $D$.

(i) If $S$ is name independent, then so is $S_{D_0}$ for any subset $D_0 \subseteq D$.

(ii) If $S_{D_0}$ is name independent, for every finite subset $D_0 \subseteq D$, then $S$ is name independent. ■

To prove our main theorem, we shall make use of the following lemma.

**Lemma 7.2** : Let $S_F$ denote the free schema on alphabet $R$ and domain $D$. Let $\tau$ be a configuration in $S_F$. Then, for any non-negative integer $n$ and any $\bar{x} \in X_\tau^n$, there exists a relational name $r(\tau, \bar{x}) \in R^*$ such that

$$(i) \quad \bar{x} \in \tau(r(\tau, \bar{x}))$$

(ii) if there exists $\bar{x} \in D^n$ and $\tau' \in S_F$, such that : $\bar{x}' \in \tau'(r(\tau, \bar{x}))$, then, there exists renaming $\alpha$ of $X_\tau$ such that : $\bar{x}' = \alpha(\bar{x})$ and $\tau' = \tau_\alpha$.

What this lemma essentially says, is that given a configuration $\tau$ and a tuple $\bar{x}$ that belongs to the configuration, we can always find a formula $\varphi$ in $R^*$ which describes $\tau$ up to a renaming. That is, $(\varphi, \bar{x})$ is true in $\tau$, and if it is
also true in another configuration $\tau'$ then $\tau'$ is a renaming of $\tau$. The proof of this lemma is given in [BANCILHON 76], page 165.

**Theorem 7.3** : Let S be a schema on alphabet R and domain D. Let $D_0$ be a finite subset of D. Then, $S_{D_0}$ is name independent, if and only if, for any relation name $r \in R^*$ and any two equivalent tuples $\bar{x}, \bar{x}' \in D_0 \|_0^r$, we have :

$$ (1) \qquad E_{D_0}((r, \bar{x})) = E_{D_0}((r, \bar{x}')) \quad \blacksquare $$

**Proof :**

A) Let us assume first that $S_{D_0}$ is name independent. Recall (Section 5) that equation (1) can be written as follows :

$$ (2) \qquad \text{prob}((r, \bar{x}) \text{ is true} | S_{D_0}) = \text{prob}((r, \bar{x}') \text{ is true} | S_{D_0}) $$

If we define

$$ (3) \qquad S_{D_0}, r, \bar{x} = \{\tau | \tau \in S_{D_0} \text{ and } \bar{x} \in \tau(r)\} $$

then equation (2) is equivalent to the following equation (see Section 5)

$$ (4) \qquad |S_{D_0}, r, \bar{x}| = |S_{D_0}, r, \bar{x}'| $$

We shall prove this last equality by showing that there exists an injection from the set $S_{D_0}, r, \bar{x}$ into the set $S_{D_0}, r, \bar{x}'$, and conversely.

As $\bar{x}$ and $\bar{x}'$ are equivalent, there exists a renaming $\alpha$ of $\bar{x}$ in D such that : $\bar{x}' = \alpha(\bar{x})$. Consider now a configuration $\tau \in S_{D_0}, r, \bar{x}$. As S. is name independent, it follows that : $\tau_\alpha \in S$. On the other hand, as $\bar{x} \in \tau(r)$, it follows that : $\bar{x}' \in \tau_\alpha(r)$. Thus, we obtain that : $\tau_\alpha \in S_{D_0}, r, \bar{x}'$.
This allows us to associate with every configuration $\tau \in S_{D_0}, r, \bar{x}$ its renaming $\tau_\alpha \in S_{D_0}, r, \bar{x}'$.

Consider now a configuration $\tau' \in S_{D_0}, r, \bar{x}$ such that $\tau' \neq \tau$. We want to show that $\tau'_\alpha \neq \tau_\alpha$. The fact that $\tau' \neq \tau$, implies one of the following two cases

(i) $X_\tau \neq X_{\tau'}$. In this case we have : $\alpha(X_\tau) \neq \alpha(X_{\tau'})$.

This implies that $\tau'_\alpha \neq \tau_\alpha$.

(ii) There exists $r \in R$ such that : $\tau'(r) \neq \tau(r)$. If follows that $\tau'_\alpha(r) \neq \tau_\alpha(r)$. This implies again that $\tau'_\alpha \neq \tau_\alpha$.

Thus, we have shown that there exists an injection from $S_{D_0}, r, \bar{x}$ into $S_{D_0}, r, \bar{x}'$. In a similar way, we can show that the renaming under $\alpha^{-1}$ of each configuration $\tau' \in S_{D_0}, r, \bar{x}'$ is in $S_{D_0}, r, \bar{x}$. And, that the mapping that associates $\tau'_\alpha$ with $\tau'$ is an injection from $S_{D_0}, r, \bar{x}'$ into $S_{D_0}, r, \bar{x}$. Therefore, equation (4) holds true, QED.

B) Let us assume now that equation (1), or its equivalent equation (4), holds. We want to show that $S_{D_0}$ is a name independent schema. Consider any configuration $\tau \in S_{D_0}$ and any renaming $\alpha$ of $X_\tau$ in $D_0$. We want to show that $\tau_\alpha \in S_{D_0}$.

Let $X_\tau = \{x_1, x_2, \dots, x_n\}$. Define $\bar{x} = (x_1, x_2, \dots, x_n)$. As $\bar{x} \in X_\tau^n$, it follows from Lemma 7.2 that there exists a relational name $r(\tau, \bar{x}) \in R^*$ such that $\bar{x} \in \tau(r(\tau, \bar{x}))$. As $X_\tau \subset D_0$, it follows that $\tau \in S_{D_0}, r(\tau, \bar{x}), \bar{x}$. Therefore,

$$ (5) \qquad |S_{D_0}, r(\tau, \bar{x}), \bar{x}| \neq 0 $$
Define now $\bar{x}' = \alpha(\bar{x})$. As the tuples $\bar{x}$ and $\bar{x}'$ are equivalent points of $D_0 \| r(\tau, \bar{x}) \|$ it follows from (4) and (5) that $|S_{D_0}; r(\tau, \bar{x}), \bar{x}'| \neq 0$. This implies that there exists a configuration $\tau'$ such that $\bar{x}' \in \tau'(r(\tau, \bar{x}))$. It follows from Lemma 7.2 that there exists a renaming $\beta$ of $\bar{x}$ such that : $\bar{x}' = \beta(\bar{x})$ and $\tau' = \tau_{\beta}$. Now, as $\tau_1' = \beta(x_1)$, $i=1, 2, ..., n$, we obtain that $\beta = \alpha$, i.e., that $\tau' = \tau_{\alpha}$. This implies that $\tau_{\alpha} \in S_{D_0}$, QED.

We are now ready to state and prove the main theorem.

**Theorem 7.4** : Let S be a schema on alphabet R and domain D. Then, S is a name independent schema, if and only if, S is an equal expectation schema.

**Proof :**

A) Assume first that S is a name independent schema. It follows from Theorem 7.1 that the schema $S_{D_0}$ is also name independent, for any finite subset $D_0 \subset D$. Then, Theorem 7.3 implies that S is an equal expectation schema.

B) Assume now that S is an equal expectation schema. Then, Theorem 7.3 implies that $S_{D_0}$ is a name independent schema, for every finite subset $D_0 \subset D$. It follows from Theorem 7.1 that S is a name independent schema.

One remark is in order at this point. The proof of Theorem 7.4 is based on Lemma 7.2. In this lemma it is required that $r$ be a member of $R^*$.

The question is : can we prove Theorem 7.4 if we require that $r$ be a member of $R$ instead of $R^*$ ? The answer is no as the following example shows.

Let $D = \{a, b, c\}$ and let $R = \{r\}$ with $||r|| = 1$. Consider the schema S on R and D consisting of the configurations $\tau^1, \tau^2, \tau^3, \tau^4$ and $\tau^5$ defined as follows
$$ \tau^1(r) = \{c\} $$

$$ \tau^2(r) = \{b\} $$

$$ \tau^3(r) = \{a, c\} $$

$$ \tau^4(r) = \{a, b\} $$

$$ \tau^5(r) = \{a, b, c\} $$

The mapping $\alpha : D \to D$ such that

$$ \alpha(a) = b, \quad \alpha(b) = c, \quad \alpha(c) = a $$

is a renaming in D of each $X_{\tau^i}$, $i=1, 2, 3, 4, 5$. We have :

$$ \tau_{\alpha}^{1}(r) = \{\alpha(c)\} = \{a\} $$

As $\tau_{\alpha}^1$ does not belong to S, this schema is not name independent. On the other hand, any two elements of D are equivalent and one can easily verify that

$$ |S_{D, r, a}| = |S_{D, r, b}| = |S_{D, r, c}| $$

Hence, the schema S is an equal expectation schema. This example shows that if we merely require that r be a member of R then Theorem 7.4 is not true. It would be interesting to demonstrate, in the context of this example, a relation name in $R^*$ that destroys the equal expectation property of S.

Consider the relation name $r'$ defined as follows :

$$ \forall x, y \in D; (x, y) \in r' \iff x \in r \text{ and } y \notin r $$

This relation name belongs to $R^*$ and it is such that $||r'|| = 2$. Using the definition of $r'$ we find
$$ \tau^1(r') = \{(c, a), (c, b)\} $$

$$ \tau^2(r') = \{(b, a), (b, b)\} $$

$$ \tau^3(r') = \{(a, b), (c, b)\} $$

$$ \tau^4(r') = \{(a, c), (b, c)\} $$

$$ \tau^5(r') = \emptyset $$

Now, the tuples $\bar{x} = (b, a)$ and $\bar{x}' = (c, b)$ are $\alpha$-equivalent points of $D^*$. It is easy to check that

$$ |S_{D, r'}, \bar{x}| = 1 \text{ and } |S_{D, r'}, \bar{x}'| = 2 $$

That is, the schema S is not an equal expectation schema. Thus, the constraint : $r \in R^*$, cannot be relaxed.

So far, we have discussed two notions in the context of relational schemata, namely, name independence and equal expectation. These notions provided us with two different views of the same thing, namely, the user's estimate of a proposition concerning a relational data base. It was reasonable to expect that these two notions were equivalent and, in this section, we saw that they indeed are.

However, we have assumed so far that the domain D has no given structure, i.e., that the only structure on D are the relations of R. In some cases though, the domains used to define data bases do have a structure (integers, for instance). So, let us now take this fact into consideration in an effort to provide a more realistic model.
## 8 - A MORE REALISTIC MODEL

Name independence and equal expectation are properties of schemata in which the domain D has no other structure than that provided by the data base relations. However, there are data base schemata in which the domain has some additional structure. Such schemata need not be name independent.

As an example, consider a data base concerning a set of people and their ages. The data base is defined on the following alphabet :

$$R = \{\text{is-age}(\text{Age}), \text{is-person}(\text{Person}), \text{has-age}(\text{Person}, \text{Age}), \\ \text{greater}(\text{Age}, \text{Age})\}$$

where,

$$||\text{is-age}|| = ||\text{is-person}|| = 1, ||\text{has-age}|| = ||\text{greater}|| = 2$$

The domain consists of the set P of all given names and the set N of positive integers. That is, $D = P \cup N$. The invariant properties of the configurations are :

$$1) \tau(\text{is-age}) \subset N$$

$$2) \tau(\text{is-person}) \subset P$$

$$3) \text{A person has one and only one age}$$

$$4) \tau(\text{has-age}) \subset \tau(\text{person}) \times \tau(\text{is-age})$$

$$5) (x, y) \in \tau(\text{greater}) \Leftrightarrow x, y \in \tau(\text{is-age}) \text{ and } x \ge y$$

This is simply the formal statement of the properties describing a set of persons and their ages. We shall refer to the schema that these properties define as the "age (data base) schema". An example configuration $\tau$ of this schema is shown in Figure 3. Note that what property (5) says is that the domain D has a structure that we *know* : it is the usual ordering of the integers.
Consider now the example configuration $\tau$ (Figure 3). Its object set is :

$$X_{\tau} = \tau(\text{is-person}) \cup \tau(\text{is-age})$$

Define a renaming $\alpha : X_{\tau} \to D$ as follows :

$$\alpha(\text{Mary}) = 25$$

$$\alpha(\text{Sue}) = \text{Mary}$$

$$\alpha(1) = \text{Bruce}$$

$$\alpha(x) = x, \text{ otherwise}$$

The renaming $\tau_{\alpha}$ of $\tau$ is shown in Figure 3. It is easy to check that $\tau_{\alpha}$ does not belong to the age schema (it violates property (1), for instance). This implies that the age schema is not name independent (nor equal expectation). Let us consider the proposition

$$p = (\text{has-age}, (\text{John}, 25))$$

According to the equal expectation property, the probability that $p$ is true, is independent of the list of parameters. That is, if we replace the tuple $(\text{John}, 25)$ with its equivalent tuple $(\text{Bruce}, \text{Sue})$, the probability that the proposition

$$p' = (\text{has-age}, (\text{Bruce}, \text{Sue}))$$

is true, must be the same as that of $p$ being true. However, as we *know* that Sue being Bruce's age makes no sense, the probability of $p'$ being true is equal to zero. As yet another example, consider the propositions :

$$p_1 = (\text{greater}, (5,2))$$

$$p_2 = (\text{greater}, (2,5))$$
The probability of $p_1$ being true is equal to 1. The probability of $p_2$ being true is equal to zero. And yet, the tuples $(5,2)$ and $(2,5)$ are equivalent !

Let us now have a closer look at what is happening. When we define a schema S on R and D, we do so by defining the properties that a configuration $\tau$ must satisfy in order to be in S. Suppose now that these properties concern only relations and tell us nothing about the objects that participate in these relations. Then, knowing the objects in a list $\bar{x}$, tells us nothing about the chances of a proposition $p = (r, \bar{x})$ to be true, for no matter which $r \in R^*$ (we have called this property of a schema "name-independence" or, "equal expectation"). This is true when we really do not know anything about the objects of a configuration. In the age schema, however, we do know things about the objects. For instance, given the object "75" we know that it represents an age ; given the object "John" we know that it is a name and not an age ; given two ages we are able to tell which one is greater. As a result of this "knowledge" we can tell whether certain propositions are true. For instance, consider a configuration $\tau$ of the age schema and suppose that the objects "25" and "32" are in $X_{\tau}$. We know then that these two objects are ages. As a result of this knowledge we conclude that the proposition

$$p = (\text{greater}, (32, 25))$$

is true in $\tau$. What makes this conclusion possible is the fact that the relation "greater" is a known relation, namely, the usual ordering of the integers. Hence, the following definition :

**Definition 8.1 :**

Let S be a schema on alphabet R and domain D. Let $\tau$ be a relational name in R. Then, $r$ is **known** in S iff for every $\bar{x} \in D$ $||r||$ the value (True or False) of the proposition $(r, \bar{x})$ is constant, over all configurations $\tau$ such that $\bar{x} \in X_{\tau}$. ■
Thus, a relation $\bar{r}$ is known in a schema S, if knowledge of the objects alone in any given list $\bar{x} \in X_{\tau}^{\|r\|}$, is sufficient to determine the value of the proposition $(\bar{r}, \bar{x})$. In the age schema, for instance, the relations : "greater", "is-age", "is-person", are all known. On the other hand, the relation "has-age" is not known. This is so, because the value of the proposition : $(\text{has-age}, \bar{x})$ does not depend on the objects in the list $\bar{x}$. That is, the relation "has-age" is a name-independent relation.

The notion of a known relation, in the sense defined here, is implicit in the definition of a schema given in [CODD 70]. In the relational model, the known relations are of two kinds :

1) Unary relations, that define the domains of unary attribute names (e.g., the relations : "is-age", "is-person", in the age schema)

2) Binary relations, that are order relations on some domain (e.g., the relation "greater" of the age schema).

Besides these, all other kinds of relations are name-independent relations. Therefore, we propose a model in which the relational alphabet $\mathcal{R}$ is decomposed into two parts : one consisting of those relations that are known, the other of those that are name-independent. In what follows, we shall set up formally this model and we shall define name independence and equal expectation taking into account known relations.

Consider a schema S on alphabet $\mathcal{R}$ and domain $D$. Recall that a configuration $\tau \in S$ is a mapping defined on the alphabet $\mathcal{R}$. Consider next a set $R_1 \subset \mathcal{R}$ and the corresponding restriction $\tau/R_1$ of the mapping $\tau$. The restriction of $S$ to $R_1$, denoted by $S/R_1$, is defined as follows

$$S/R_1 = \{\tau/R_1 | \tau \in S\}$$
**Definition 8.2 :**

Let S be a schema on alphabet R and domain D. Let $\alpha$ be a renaming in D. Let $R_1 \subset R$. We say that $\alpha$ **respects** $R_1$, iff $\forall \tau \in S/R_1, \tau_\alpha \in S/R_1$. ■

Note that if S is a name independent schema then so is the schema $S/R_1$, for every $R_1 \subset R$. Hence, every renaming $\alpha$ respects every subset $R_1 \subset R$. If the schema S is not name independent, then there may be renamings that do not satisfy this property. Consider, for instance, the age schema and let

$$R_1 = \{\text{has-age}\}$$

Consider next the example configuration $\tau$ of this schema (Figure 3) and its renaming $\tau_\alpha$. Observe that although the configuration $\tau/R_1$ belongs to the restricted schema $S/R_1$, its renaming $\tau_\alpha/R_1$ does not. Therefore, the renaming $\alpha$ does not respect $R_1$. In generalizing the concept of name-independence, we shall require that every renaming respect the set of all known relations in the schema.

**Definition 8.3 :**

Let S be a schema on alphabet R and domain D. Let $R_K$ be the set of all known relations of R. Then, S is **name independent** with respect to $R_K$ iff for every renaming $\alpha$ that respects $R_K$, we have : $\tau \in S \Rightarrow \tau_\alpha \in S$. ■

Let us now define equal expectation in a schema that contains known relations. To do so, we need first a new definition of equivalence between two n-tuples.

**Definition 8.4 :**

Let S be a schema on alphabet R and domain D. Let $R_1 \subset R$. Then, two n-tuples $\bar{x}, \bar{x}' \in D^n$ are said to be $R_1$-equivalent (denoted by $\bar{x} \equiv_{R_1} \bar{x}'$), iff
there exists a renaming $\alpha$ of $\bar{x}$ that respects $R_1$ and such that $\alpha(\bar{x}) = \bar{x}'$. ■

It is easy to check that this relation is indeed an equivalence relation on the set $D^n$. To illustrate equivalence, consider the age schema and let

$$R_1 = \{\text{has-age}\}$$

Then, the tuples

$$\bar{x} = (\text{John, 20}) \text{ and } \bar{x}' = (\text{Peter, Bruce})$$

are not $R_1$-equivalent as every renaming of $\bar{x}$ that respects $R_1$ must transform a name to another name and a number to another number.

We can now define equal expectation, considering only tuples that are equivalent with respect to the set of all known relations of the schema.

**Definition 8.5:**

Let $S$ be a schema on alphabet $R$ and domain $D$. Let $R_K$ be the set of all known relations of $R$. Then, $S$ is an equal expectation schema with respect to $R_K$ iff, $\forall r \in R^*; \forall D_0 \subset D$ such that $D_0$ is finite; $\forall \bar{x}, \bar{x}' \in D_0 \|r\|$ such that $\bar{x} = \bar{x}'$ we have

$$E_{D_0}((r, \bar{x})) = E_{D_0}((r, \bar{x}'))$$

A schema that is name independent with respect to the set of all known relations it is also of equal expectation, and vice versa. This can be shown in the same way as it was done in the previous section. Thus, we have the following Theorem.
**Theorem 8.1** : Let S be a schema on alphabet R and domain D. Let $R_K$ be the set of all known relations of R. Then, S is a name independent schema with respect to $R_K$ iff S is an equal expectation schema with respect to $R_K$.

In conclusion, we have set up a model that takes into account the fact that some data base relations are known. We have then defined name independence and equal expectations in the context of such a model. When none of the data base relations is known (i.e., when $R_K = \emptyset$), these notions reduce to those defined earlier in this paper.

## 9 - CONCLUSIONS

We have seen a formal approach to name independence in relational data bases. The model proposed allowed us to rigorously define the concept of a name independent relation and that of a known relation. We have also presented an equivalent characterization of name independence in terms of probabilities. This was done using the notion of "user's estimate" of the data base.

In order to define user's estimation we represented the data base by a set of propositions. These propositions along with their truth values describe the information content of the data base. As the truth values of certain propositions may be declared confidential, this approach seems to be also suitable for studying protection of information in relational data bases.
Configuration $\tau$

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

Configuration $\tau'$

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

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

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

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

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

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

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

Figure 1

The example configuration $\tau$ of the family data base
and its "French" renaming $\tau'$.
<figure><img src="image_12.png" /><figcaption>Figure 2</figcaption></figure>

The only knowledge of the user is the data base schema S:

The user does not know the actual configuration $\tau_0$.
Configuration $\tau$

$$ \tau(\text{is-person}) = $$

<table><tr><td>Person</td></tr><tr><td>Peter</td></tr><tr><td>Mary</td></tr><tr><td>Paul</td></tr><tr><td>Bruce</td></tr><tr><td>Mike</td></tr><tr><td>Sue</td></tr></table>

Configuration $\tau_\alpha$

$$ \tau_\alpha(\text{is-person}) = $$

$$ \tau(\text{is-age}) = $$

<table><tr><td>Age</td></tr><tr><td>1</td></tr><tr><td>2</td></tr><tr><td>...</td></tr><tr><td>79</td></tr><tr><td>80</td></tr></table>

$$ \tau_\alpha(\text{is-age}) = $$

$$ \tau(\text{has-age}) = $$

<table><tr><td>Person</td><td>Age</td></tr><tr><td>Peter</td><td>20</td></tr><tr><td>Mary</td><td>21</td></tr><tr><td>Paul</td><td>25</td></tr><tr><td>Bruce</td><td>1</td></tr><tr><td>Mike</td><td>65</td></tr><tr><td>Sue</td><td>52</td></tr></table>

$$ \tau_\alpha(\text{has-age}) = $$

<caption>Figure 3</caption>

The example configuration $\tau$ of the "age schema" and the renaming $\tau_\alpha$ (The values $\tau(\text{greater})$ and $\tau_\alpha(\text{greater})$ were omitted).
CODD 71b

Codd E.F. - "A Data Base Sublanguage Founded on the Relational Calculus" -
Proceedings of ACM SIGFIDET Workshop on Data Description, Access and
Control - San Diego - CA - 1971.

ESWARAN 74

Eswaran K.P., Gray J.N. and Traiger I.L. - "The Notions of Consistency and Predicate Locks in a Data Base System" - IBM Research Report RI1487 - San Jose CA - 30 December 1974.

HALL 75

Hall P.A.V., Todd S.J.P. and Hitchcock P. - "An Algebra of Relations for Machine Computation, IBM Scientific Centre Report UKSC0066 - Peterlee - England - January 1975.

HAMMER 75

Hammer M.M. and McLeod - "Semantic Integrity in a Relational Data Base System" -
Proceedings of International Conference on Very Large Data Bases - Framingham MA -
22-24 September 1975.

McLEOD 76

McLeod D.I. - 'High Level Expression of Semantic Integrity Specifications in a Relational Data Base System' - MIT Laboratory for Computer Science - Technical Report 165 - September 1976.

NIJSSEN 76

Nijssen G.M. - "Data Structuring in the DDL and Relational Data Model" -
Proceedings of IFIP TC-2 Working Conference on Data Base Management Systems -
Cargese - Corsica - 1-5 April 1974 - North-Holland 1974.

STONEBRAKER 75

Stonebraker M. - "Implementation of Integrity Constraints and Views by Query Modification" - Proceedings of ACM SIGMOD International Conference on the Management of Data - San Jose CA - 14-16 May 1975.
REFERENCES

ABRIAL 72

Abrial J.R. - "Projet SOCRATE" - Cours avancés sur l'Architecture des Systèmes - Alpe d'Huez - December 72.

ABRIAL 74

Abrial J.R. - "Data Semantics" - Data Base Management - North-Holland 1974.

BANCILHON 76

Bancilhon F.M. - "Data Structures : Specification and Realization" - Ph.D. Thesis - University of Michigan - January 1976.

BARBOSA 76

Barbosa R. - "Contribution à l'étude sémantique des bases de données : application au système SOCRATE" - Thèse de docteur-Ingénieur - Université de Grenoble - 1976.

BRACCHI 76

Bracchi G., Paolini P., Pelagatti G. - "Mappings in Data Base Systems" - Rapporto Interno n° 76-11 - Instituto di Elettrotecnica ed Elettronica del Politecnical di Milano - November 1976.

CODD 70

Codd E.F. - "A Relational Model for Large Shared Data Banks" - Communications of the ACM - Volume 13 - Number 6 - June 1970.

CODD 71a

Codd E.F. - "Further Normalization of the Data Base Relational Model" - Courant Computer Science Symposium, 6 - New York NY - 24-25 May 1971. - in Data Base Systems - Prentice Hall 1971.