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

HAL
open science

# On the completeness of query languages for relational data bases

François Bancilhon

► To cite this version:

Francois Bancilhon. On the completeness of query languages for relational data bases. [Research Report] IRIA-RR-297, IRIA. 1978, pp.26. hal-04716546

HAL Id: hal-04716546

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Dw-04129

AR297

RIA

laboria

laboratoire de recherche
en informatique
et automatique

ON THE COMPLETENESS
OF QUERY LANGUAGES
FOR RELATIONAL
DATA BASES

François BANCILHON

Rapport de Recherche N° 297

Mai 1978

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
ON THE COMPLETENESS OF QUERY LANGUAGES FOR RELATIONAL
DATA BASES
François Bancilhon

Résumé :

Nous étudions ici le problème de la complétude d'un langage de requêtes pour une base de données relationnelle. Depuis les premiers travaux de Codd, pour établir la complétude d'un langage, on montre ce langage équivalent à un langage «étalon», le calcul relationnel du premier ordre. Aucune justification théorique du choix de cet étalon n'a cependant été fournie. Nous essayons donc ici de définir la complétude de manière intrinsèque. A partir d'une description informelle de cette notion, justifiée par des exemples, nous aboutissons à un critère de complétude. Nous démontrons ensuite que le calcul relationnel du premier ordre satisfait ce critère, établissant ainsi solidement la définition usuelle de complétude.

Abstract :

In this paper we address the problem of completeness in relational query languages. Since Codd's early work, a language is said to be complete if it is equivalent to a «standard» language, namely, the first order relational calculus. However, the choice of this standard was never justified. In this paper, we define completeness intrinsically. Starting from an informal description of the notion (that we justify through examples), we define a formal criterion of completeness. We then show that the first order relational calculus satisfies this criterion, thus establishing the soundness Codd's definition of completeness.
The relation name is "is-child-of", the two attribute names are "child" and "parent" and their assigned domain is the set of people. The order of the relation is two. In the relational model the value of a relation r(A₁, A₂, ..., Aₙ) over the domains D₁, D₂, ..., Dₙ is a **finite** set of n-tuples. The elements of an n-tuple, are not distinguished by their position but by their names.

**Definition**: Let r(A₁:D₁, A₂:D₂, ..., Aₙ:Dₙ) be a relation descriptor. A **value** of r is a **finite** set of n-tuples from D₁ × D₂ × ... × Dₙ. Values of r will be denoted by τ(r) i.e. :

$$ \tau(r) \subseteq D_1 \times D_2 \times \dots \times D_n \quad \square $$

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

The fact that (x₁, x₂, ..., xₙ) ∈ τ(r) will sometimes be denoted by τ(r)(A₁:x₁, A₂:x₂, ..., Aₙ:xₙ). When clear from context, we shall drop the letter τ. For instance in the value of figure 1 we have : is-child-of (child:Mary, parent: William)

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 an 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. In what follows, we shall not explicitly mention the domain D whenever it is clearly understood from the context.

<table><caption>Figure 1</caption><thead><tr><th></th><th>Child</th><th>Parent</th></tr></thead><tbody><tr><td>John</td><td>William</td><td></td></tr><tr><td>Mary</td><td>William</td><td></td></tr><tr><td>John</td><td>Susan</td><td></td></tr><tr><td>Mary</td><td>Susan</td><td></td></tr></tbody></table>
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**: Any *finite* set of relation descriptors is called a *relational alphabet*.

As an example consider the following set :

$$R = \{\text{is-male (Male:People), is-female (Female:People),} \\ \text{is-child-of (child:people, parent:people),} \\ \text{is-married-to (spouse 1:people, spouse 2:people)}\}$$

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

A relational alphabet describes a data base in the following sense. At any given instant in 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**: Let $R$ be a relational alphabet. A *data base configuration* on $R$ 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$.
$$ \tau(\text{is-male}) = \begin{array}{|c|} \text{Male} \\ \hline \begin{array}{l} \text{John} \\ \text{Peter} \\ \text{William} \end{array} \\ \hline \end{array} $$

$$ \tau(\text{is-child-of}) = \begin{array}{|c|} \text{Child} \\ \hline \begin{array}{l} \text{John} \\ \text{Mary} \\ \text{John} \\ \text{Mary} \end{array} \\ \hline \text{Parent} \\ \hline \begin{array}{l} \text{William} \\ \text{William} \\ \text{Susan} \\ \text{Susan} \end{array} \\ \hline \end{array} $$

$$ \tau(\text{is-female}) = \begin{array}{|c|} \text{Female} \\ \hline \begin{array}{l} \text{Mary} \\ \text{Susan} \\ \text{Lola} \end{array} \\ \hline \end{array} $$

$$ \tau(\text{is-married-to}) = \begin{array}{|c|} \text{Spouse 1} \\ \hline \begin{array}{l} \text{Susan} \\ \text{William} \\ \text{Peter} \\ \text{Lola} \end{array} \\ \hline \text{Spouse 2} \\ \hline \begin{array}{l} \text{William} \\ \text{Susan} \\ \text{Lola} \\ \text{Peter} \end{array} \\ \hline \end{array} $$

<caption>Figure 2</caption>

Figure 2 describes a configuration of the family data base.

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

{John, Peter, William, Mary, Susan, Lola}

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**: Let $\tau$ be a configuration on $R$ and $D$. The set of objects of $D_1 \cup D_2 \cup \dots \cup D_n$ 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}$. []

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

**Definition**: Let $R$ be a relational alphabet. Let $S_F(R)$ denote the set of all configurations on $R$. Then, any subset of $S_F(R)$ is called a **data base schema** on $R$. In particular, the set $S_F(R)$ is called the **free schema** on $R$. []
After defining the data model we now turn to the problem of query definition. Let us first see how new relations can be defined on a data base.

For instance, on the family data base we can define the "grand-parent" relation; this is done by choosing a name "grand-parent" and then explaining how to define (or "compute") that new relation from the original ones.

Let $R = \{r_1, r_2, \dots, r_n\}$ be a relational alphabet and let $S_F(R)$ be the free schema over $R$.

A relational operator $\Delta$ on $R$ is a mapping

$$ \Delta : S_F(R) \rightarrow \mathcal{P}(D_1 \times D_2 \times \dots \times D_n) \quad (\text{where } \mathcal{P}(\cdot) \text{ denotes the power set of}) $$

such that $\forall \tau, \Delta(\tau) \in X_{\tau}^n$ i.e. it is a mapping which, with a configuration $\tau$ of $S_F$, associates a relation on its object set.

Let $r(A_1:D_1, A_2:D_2, \dots, A_n:D_n)$ be a new relational descriptor ($r \notin R$). We say that $(\Delta, r)$ specifies a new relation on the data base by assigning in each configuration $\tau$ the value $\Delta(\tau)$ to the descriptor $r$, i.e. $\tau(r) = \Delta(\tau)$.

For instance let $R = \{"is-male", "is-female", "is-child-of", "is-married-to"\}$ be the family relational alphabet. Let "is-father-of" (father, child) be the new descriptor. We specify it by :

`is-father-of (father:x, child:y) <=> is-parent-of (parent:x, child:y)`

`^ is-male (male:x)`

In this example, we suggested one way (calculus oriented) of describing $\Delta$, but is should be clear that there are other ways that we shall discuss later.
Before defining a query, let us introduce two final notations. Let $r(A_1:D_1, \dots, A_n:D_n)$ be a relation descriptor; an *r-tuple* is an element from $D_1 \times D_2 \times \dots \times D_n$.

An *r-list* is an element from $(D_1 \cup \{?\}) \times (D_2 \cup \{?\}) \times \dots \times (D_n \cup \{?\})$

**Definition**: Let $R$ be a relational alphabet of a data base. Let $(\Delta, r)$ be a relation specification. Let $\bar{x}$ be an r-list. We say that $(\Delta, r, \bar{x})$ is a query on the data base.□

Let us demonstrate by an example that this definition adequately models queries on data bases.
The query : "who are John's grand-parents ?" can be described by :

i) is-grand-parent-of (GP:people, GC:people)

ii) is-grand-parent-of (GP:x, GC:y) <=> 
    z (is-parent-of (parent:x, child:z) A
    is-parent-of (parent:z, child:y))

iii) is-grand-parent-of (GP:?, GC:John).

Part (i) defines a new relational descriptor, part (ii) specifies it, and part (iii) asks the question.

An r-tuple *matches* an r-list if they agree in every position where the list does not have a question-mark. The formal interpretation of the query is given by the following definition:

**Definition**: Let $q = (\Delta, r, \bar{x})$ be a query on a data base defined of the alphabet R.
The answer to query $q$ in configuration $\tau$ is the set of r-tuples of $\tau(r)$ which match
the r-list. $\square$

The definition of a query language follows from that of a query : a query
language is one in which each sentence specifies a query (Δ, r, x̄); it is clear
that the only thing that distinguishes languages is the type of operator Δ they can
describe. Therefore we shall consider from now on that a *query language is one in
which each sentence specifies a relational operator Δ*. Now there are two ways one
can look at an operator Δ : a dynamic and static one. In the dynamic way we say that
Δ is a *mapping* from the schema in the set of relations over D₁ × D₂ × ... × Dn; in
the static way we consider the data base at a given time in configuration τ and
we say that Δ defines a new *relation* Δ(τ) on that configuration.
# AN INFORMAL STUDY OF COMPLETENESS

We can now see a little more clearly what is the property of completeness : a query language will be complete if it can express *all possible relational operators*. We should of course explicit what is meant by "all possible". As we just mentioned a relational operator $\Delta$ can be interpreted either statically or dynamically. This yields two definitions of completeness :

i) A query language L is complete in the dynamic sense if for any relational alphabet R, for any mapping $\Delta$ from $S_F(R)$ into the set of relations over the domains of R, there exists a sentence in L which describes that mapping.

ii) A query language L is complete in the static sense if for any relational alphabet R, for any configuration $\tau$ on R, for any new relation that can be defined on $X_\tau$ there is a sentence in L which describes that new relation.

In this paper we shall restrict ourself to the static case. Before proceeding any further we must look a little more closely at domains over which relations are defined.

By looking at examples of existing data bases one can get a fairly good idea of what types of domains are of practical interest. Some of these domains are well known mathematical sets : finite sets, integers, subsets of the integers, free monoids generated by some finite alphabet, etc.

However besides these, most authors [Abrial 74, Bracchi 76] agree on the necessity of having a special domain, the internal domain, which has some "strange" characteristics. Probably the best description of the practical characteristics 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 struc-
ture 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 ele-
ments of that domain.

It is the presence of such domains in the field of data bases that
makes the completeness problem specific. So let us concentrate somehow on
these domains.

In the static case, we have a configuration τ on R, with a finite
object set X<sub>τ</sub>. We want to see if all the possible relations we can specify on
X<sub>τ</sub> from τ are expressible in the query language.

For a given order n and a given finite set X, there is a finite
number of n - any relation over X, namely 2^{|X|^n}. One can wonder why all of them
would not be definable. The reason is of course that if D is an internal domain,
to define this relation we are not allowed to use the names of the objects in
X<sub>τ</sub>. Let us look at some examples to precise these notions.

We first consider a configuration in which _every_ relation is effec-
tively definable. Let X_τ = {a,b,c,d,e} (we name the elements of X_τ just for the
sake of the argument), and let R consist of a single binary relation r described
by its graphical representation in Fig. 3

<figure><img src="image_4.png" /><figcaption>Figure 3</figcaption></figure>

This binary relation is a successor function. In this particular exam-
ple, each element of X_T can be described (named) by a sentence which uses only
the relation $r$. This naming can be done in the following way :

The element $a$ can be named by : "The element $x$ in $X_T$ such that
there is no $y$ in $X$ such that $r(y,x)$".

The element $b$ can be named by : "The element $x$ in $X$ such that $r(a,x)$", etc.

Since every element in $X$ can be named, then every relation on $X$ can be defined (just enumerate the tuples of the relation). Therefore, the configuration of Figure 3 is such that every relation on $X$ is computable from $R$.

Let us now consider another example. Let $X = \{a,b,c,d,e,f,g,h,i,j\}$ and let $R$ consist of a single symmetric binary relation, graphically represented by Fig. 4.

<figure><img src="image_5.png" /><figcaption>Figure 4</figcaption></figure>

Let us now see if as in the preceding example every object of $X$ can be described from $R$.

The object $a$ can be described by :

"The element $x$ of $X$ such that for all $y$ in $X$, $r(x,y)$ is false".

Now, can we name $b$? if we could, this means that we could distinguish it from $c$. But in this graph $b$ and $c$ are indistinguishable since every property satisfied by $b$ is also satisfied by $c$. It follows that the unary rela-
tion containing b and not c is not definable. As a final example let $X_T = \{a,b,c,d,e\}$ and let $R = \{r\}$ consist of a single binary relation represented by the complete graph of Figure 5

<figure><img src="image_6.png" /><figcaption>Figure 5</figcaption></figure>

It should be clear that without naming $X_T$, the only binary relation we can define on $X_T$ are : $\{=, \ne, X_T \times X_T, \emptyset\}$. These examples have demonstrated that not all relations are definable on $X_T$ from $T$. We shall now try to find a characterization of these definable relations.

Considerable attention has been given to the problem of defining computable functions from integer to integer.

It is Church's Thesis that recursive function represent the widest class of computable
functions. As in the dynamic case we are interested in defining mappings from relations to relations, we might want to know if this method is applicable or not.

Let us first emphasize the differences between recursive functions and relational operators.

Recursive functions, or Turing machine computable functions, are either integer to integer functions or string to string functions. Since relations are not integer or strings, the only way to apply recursive function theory to our case is to define a bijective mapping :

$$h : \mathcal{R} \to \Sigma^*$$

where $\mathcal{R}$ is the set of relations and $\Sigma^*$ the set of strings over $\Sigma$. Once such a mapping is defined, we can define a computable relational operator as follows :

"A relational operator $\Delta$ is computable iff the string to string function $h^{-1} \circ \Delta \circ h$ is a computable function".

This is illustrated by the following commutative diagram :

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

Let us study this type of approach. Let $R$ consist of a single n-ary relation $r$, given $X_r = \{x_1, x_2, \dots, x_p\}$, we can associate with $\tau(r)$ a multidimensional boolean array $\bar{r}$ defined as follows :

$$\bar{r}_{i_1 i_2 \dots i_n} = \begin{cases} 1 & \text{if } r(x_{i_1}, x_{i_2}, \dots, x_{i_n}) \text{ is true} \\ 0 & \text{otherwise} \end{cases}$$

With that boolean tensor $\bar{r}$ we can unambiguously associate a string $h(r)$ of zeros and ones describing $\bar{r}$ row by row. For instance if $X = \{x_1, x_2, x_3\}$ and $\tau(r)$ is the binary relation graphically represented by Fig. 6,

<figure><img src="image_8.png" /><figcaption>Figure 6</figcaption></figure>
then

$$ \bar{r} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} $$

$$ \text{and } h(r) = 010110100. $$

Consider now the string to string function defined by :

$$ f(w0) = w1, \quad w \in \{0,1\} $$

$$ f(w1) = w0, \quad w \in \{0,1\} $$

This function is clearly recursive, therefore if we adopt the suggested method we can say that :

$$ \Delta = h^{-1} \circ f \circ h $$

is a computable relational operator.

Let us now consider :

$$ X = \{x_1, x_2, x_3, x_4\} $$

And let $\tau(r)$ be the *empty* binary relation on $X : \tau(r) = \emptyset$.

From the preceding definitions :

$$ h(\tau(r)) = 0000000000000000 $$

$$ f(h(\tau(r))) = 0000000000000001 $$

$$ h^{-1}f(h(\tau(r))) = \{(x_4, x_4)\} $$

But since $\tau(r)$ is empty, $x_4$ is indistinguishable by $\tau$ from all other objects in $X_\tau$. Therefore $(x_4, x_4)$ is *not* definable on $X_\tau$ from $\tau$ in other words. $\Delta(\tau(r))$ is *not* computable from $\tau(r)$ and $\Delta$ is not a computable operator. This yields a contradiction.

This example shows that this method is not acceptable to define computability. Let us briefly explain why. To define the $h$ mapping, we had to index the $X$ set, i.e. we have said : "Let $X = \{x_1, x_2, ...\}$".
This actually introduced a new relation s on X (the successor function of the index). Therefore the h mapping does not take as relation set {r},but {r,s}, and therefore we obtain all relations computable from {r,s}.

To summarize this section, we have given a definition of static com-
putability which states that a language is complete if on any configuration $\tau$, it can define any new definable relation; we have shown than not all relations are definable in general because of the existence of internal domains in which elements cannot be named. Our next step will be to find a criterion for "definable relations", but before doing so let us look at an example of a query language.

A QUERY LANGUAGE

We now define formally a language similar to that of Codd :

Definition Let R be a relational alphabet the First Order R-calculus is
defined as follows

(1) The vocabulary of the calculus consists of :

i) object variables x, y, z, ... with or without subscripts or
superscripts

ii) relation constants r for all r's in R

iii) attribute names A for all attributes in R

iv) Logical symbols $\exists$, $\forall$, $^A$, $v$, $\lceil$

v) delimiters ) , (

(2) A term of the calculus is of the form

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

where $r(A_1 : D_1, ..., A_n : D_n)$ is a relational descriptor from R and the $x_i$'s are object variables.

(3) A well formed formula (wff) of the first order R-calculus is defined recur-
sively as follows :
i) every term is a wff

ii) if $\Gamma$ and $\Gamma'$ are wffs, then so are :

($\Gamma \wedge \Gamma'$), ($\Gamma \vee \Gamma'$) and $\vdash \Gamma'$.

iii) if $\Gamma$ is a wff in which $x$ occurs as a free variable then :

$\forall x \Gamma$ and $\exists x \Gamma$ are wff's. $\Box$

The interpretation of the calculus is specified as follows :

**Definition** Let $R$ be a relational alphabet. Let $\tau$ be a configuration on $R$. Every formula of the first order $R$-calculus is interpreted over $\tau$ by a relation on $X_\tau$ as follows :

Every wff with free variables $x_1, x_2, \dots, x_p$ is interpreted by an $n$-ary relation over $X$, according to the following rules :

i) $r(A_1 : x_1, \dots, A_n : x_n)$ is interpreted by the relation $\tau(r)$.

ii) if $\Gamma$ and $\Gamma'$ are interpreted by the relations $r$ and $r'$ then :

$\Gamma \wedge \Gamma'$ is interpreted by $r \cap r'$

$\Gamma \vee \Gamma'$ is interpreted by $r \cup r'$

$\vdash \Gamma$ is interpreted by $\vdash r$.

$\forall x \Gamma$ is interpreted by $\forall x r$

$\exists x \Gamma$ is interpreted by $\exists x r$. $\Box$

We shall denote by First(R) the set of relations defined by the first order $R$-calculus.

For readers familiar with Codd's work [CODD.71] we want to point out the main differences between this calculus and Codd's :

i) This calculus is based on object variables instead of tuple variables which is a simple notational difference with no theoretical consequences

ii) No object names are given in this calculus, since we clearly distinguish in a query $q = (r, \Delta, \bar{x})$ between the list of parameters $x$ and the operator $\Delta$, and since we have shown that names should not be used to define relations when considering internal domains.
iii) Finally we have not introduced the relation $≥, ≤, >$ and $<$ as Codd does. This is because in this model, all relations are already described in $R$. For instance if we have a data base concerning people and their salary, it is described by

$$R = \{\text{has-salary (name : people, salary : integer), greater than (g : integer, s : integer)}\}$$

With such a relational alphabet, questions such as "who makes more than Peter?" can be asked using only $R$ and without any background convention about the $≥$ relation on the integers. Let us now see if we can evaluate the power of this calculus i.e. characterize the set of relations it can define on a configuration. As we intuitively demonstrated in the previous section, not all relations are definable. If our argument is true there should then be some relations that this calculus _cannot_ define. We shall exhibit some of these after introducing some preliminary definition. Let $R$ be a relational alphabet and let $\tau$ be a configuration on $R$. Let $a : X_{\tau} \to X_{\tau}$ be a permutation of the objects of $\tau$. Let $\bar{x} \in X_{\tau}^{\|r\|}$ be an $r$-tuple; the _renaming_ of $\bar{x} = (x_1, x_2, \dots, x_{\|r\|})$ by $a$ is the $r$-tuple

$$a(\bar{x}) = (a(x_1), a(x_2), \dots, a(x_{\|r\|}))$$

This notion of renaming can be generalized to a configuration as follows: The _renaming_ of $\tau$ by $a$ is the configuration $\tau_a$ defined by:

$$\bar{x} \in \tau(r) \iff a(\bar{x}) \in \tau_a(r) \quad \forall \bar{x} \in X_2^{\|r\|}, \forall r \in R.$$

One can see that the renaming of the configuration is simply obtained by permuting in $\tau$ the elements of $X_{\tau}$ according to $a$. Note that $X_{\tau} = X_{\tau_a}$.

**Definition** Let $\tau$ be a configuration on $R$, let $a : X_{\tau} \to X_{\tau}$ be a permutation of $X_{\tau}$; it is _automorphism_ of $\tau$ if $\tau_a = \tau$. □

Thus an automorphism is a renaming of $X_{\tau}$ which leaves the configuration invariant

**Definition** Let $\tau$ be a configuration on $R$; the _stabilizer_ of $\tau$, $S(\tau)$ is the set of automorphism of $\tau$. □
It is clear that $S(\tau)$ under the law of composition is a sub-group of the symmetric group of $X_τ$, $S_{X_τ}$. The relationship between the stabilizer and the first order R-calculus is given by the following result:

**Theorem:** Let $\tau$ be a configuration on $R$ and let $S(\tau)$ be its stabilizer. Let $\Gamma$ be a wff from the first order R-calculus defining a relation $r$ on $X_τ$ then $\tau(r)$ is invariant by $S(\tau)$. $\square$

**Proof:** To see this, first note that all relations $\tau(r)$, for all $r \in R$ are invariant by $S(\tau)$. Then all we have to check is that the set of relations which are invariant by $S(\tau)$ is closed under all the operations of the calculus. This follows directly from the definition of the calculus Q.E.D. This property is illustrated by Figure 6.

<figure><img src="image_9.png" /><figcaption>Figure 6</figcaption></figure>

## COMPLETENESS

The stabilizer consists of the renaming of the object set $X_τ$ of $\tau$ which leave $\tau$ invariant. But let us go back to the internal domains idea that we introduced before. We said that the only knowledge we had of $X_τ$ was the structure put on it by the relations $\tau(r)$ for all $r$'s in $R$ and that in defining new relations on $X_τ$ we could use only these $\tau(r)$ and not the names of the elements of $X_τ$. Therefore if we start from a set of relations $\tau(R)$ invariant by $S(\tau)$, all the relations we build from these without naming $X_τ$ should also be invariant by $S(\tau)$ since $S(\tau)$ measures the "uncertainty" we have about $X_τ$. It then appears that the best we can define are all the relations invariant by $S(\tau)$, hence the following definition:
**Definition** Let $\tau$ be a configuration on $R$ and let $S(\tau)$ be its stabilizer.
We say that a relation $r$ on $X_\tau$ is **definable** from $\tau$ if it is invariant by $S(\tau)$.
We say that a query language is **complete** if it can define all definable relations. []

We now give the main result of this paper :

**Main theorem** : The first order R-calculus is complete. []

The rest of the paper is devoted to the proof of that theorem.
One of the reasons why the theorem holds is that we can, in first order cal-
culus, write a formula which describes a configuration up to an isomorphism.
One important part of the proof is the construction of this formula. Let us
first introduce some notations for formulae :

Let $x_1, x_2, \dots, x_n$ be a set of variable names. The $\underline{\text{Dif}}$ formula is
defined by :

$$
\underline{\text{Dif}} (x_1, \dots, x_n) = \widehat{\bigwedge_{i=1,2,\dots,n} (x_i \neq x_j)} \quad \widehat{\bigwedge_{j=1,2,\dots,n} (x_i = x_j)}
$$

For instance, $\underline{\text{Dif}} (x_1,x_2,x_3) = (x_1 \neq x_2) \wedge (x_1 \neq x_3) \wedge (x_2 \neq x_3)$.
The goal of this formula is to establish that the objects $x_1, \dots, x_n$ are all
different.

We now define the *Atmost* formula by :

$$
\underline{\text{Atmost}} (x_1, x_2, \dots, x_n) = (\forall x)
  \left(
    \widehat{
      \bigwedge_{i=1,2,\dots,n} (x = x_i)
    }
  \right)
$$

For instance, $\underline{\text{Atmost}} (x_1,x_2,x_3) = \forall x (x = x_1 \lor x = x_2 \lor x = x_3)$.
Therefore, the $\underline{\text{Atmost}}$ formula establishes that the "universe" we consider consists
only of the objects $\{x_1, \dots, x_n\}$.

Let $\tau$ be a configuration. Let $h$ be a bijection from $X_\tau$ to $\{x_1, x_2, \dots, x_n\}$,
$(|X_\tau| = n)$. We define the formula Rel $(\tau, h)$ by :
$$ \underline{\mathrm{Rel}} (\tau, h) (x_1, \dots, x_n) = \left[ \bigwedge_{r \in R} \left( \overline{x} \in \{x_1, x_2, \dots, x_n\} \;\|\; r \right) \right] r(\bar{x}) $$

such that $r(h^{-1}(\bar{x}))$ is true.

$$ \wedge \quad \left[ \bigwedge_{r \in R} \left( \overline{x} \in \{x_1, x_2, \dots, x_n\} \;\|\; r \right) \right] \quad \neg r(\bar{x}) $$

such that $r(h^{-1}(\bar{x}))$ is false.

What $\underline{\mathrm{Rel}}$ does is the following : It "assigns" the variables $x_1, x_2, \dots, x_n$ to $X_\tau$, according to the H mapping, it then establishes which relations hold between these variables in $\tau$.

For instance, consider the configuration of Figure 7 defined on $R = \{a,b\}$ with $||a|| = ||b|| = 2$

<figure><img src="image_10.png" /><figcaption>Figure 7</figcaption></figure>

The h mapping has been directly indicated on the figure. We can write :

$$ \begin{align*} \underline{\mathrm{Rel}} (\tau, h) &= a (x_3, x_1) \wedge a (x_1, x_2) \\ &\wedge b (x_2, x_3) \wedge b (x_2, x_1) \\ &\wedge \neg a (x_1, x_3) \wedge \neg a (x_2, x_1) \\ &\wedge \neg a (x_3, x_2) \wedge \neg a (x_2, x_3) \\ &\wedge \neg b (x_1, x_2) \wedge \neg b (x_3, x_2) \\ &\wedge \neg b (x_3, x_1) \wedge \neg b (x_1, x_3) \end{align*} $$

We can now define the notion of an identifying formula.
**Definition** Let $\tau$ be a configuration. Let $X' \subseteq X_\tau$. Let $|X_\tau| = n$ and $|X'| = m$. An identifying formula of $\tau$ from $X'$ is a formula : IF $(\tau, X')$ defined by :

$$
\begin{align*}
\text{IF } (\tau, X') & (x_1, x_2, \ldots, x_m) \\
&= (\exists x_{m+1}) (\exists x_{m+2}) \ldots (\exists x_n) \\
\llap{\underline{\text{Dif}}} (x_1, \ldots, x_n) &\land \llap{\underline{\text{Atmost}}} (x_1, \ldots, x_n) \land \\
\llap{\underline{\text{Rel}}} (\tau, h) & (x_1, \ldots, x_n)
\end{align*}
$$

where $h$ is such that $h(X') = \{x_1, \dots, x_m\}$. $\square$

It is important to keep in mind that all these formulae are simply syntactical forms. We can now interpret them as formulae from the 1st Order R-Calculus.

Let us now look at an example. Consider the configuration $\tau$ with $R = \{a,b\}$, $|a| = ||b|| = 2$ represented by the graph of Figure 8

<figure><img src="image_11.png" /><figcaption>Figure 8</figcaption></figure>

Let $h$ be the mapping defined by $h(y_1) = x_1$, $h(y_2) = x_2$ and $h(y_3) = x_3$. An identifying formula of $\tau$ from $\{y_1\}$ is :

$$
\begin{align*}
\text{IF}(\tau, \{y_1\}) (x_1) & = (\exists x_2)(\exists x_3) \llap{\underline{\text{Dif}}} (x_1, x_2, x_3) \\
& \land \llap{\underline{\text{Atmost}}} (x_1, x_2, x_3) \\
& \land \llap{\underline{\text{Rel}}} (\tau, h) (x_1, x_2, x_3)
\end{align*}
$$
where :

$$ \underline{\text{Dif}} (x_1, x_2, x_3) = (x_1 \neq x_2) \wedge (x_1 \neq x_3) \wedge (x_2 \neq x_3) $$

$$ \underline{\text{Atmost}} (x_1, x_2, x_3) = \exists x (x = x_1 \lor x = x_2 \lor x = x_3) $$

$$ \begin{align*} \underline{\text{Rel}} (\tau, h) (x_1, x_2, x_3) &= a (x_1, x_3) \wedge a (x_2, x_3) \\ &\qquad \wedge b (x_1, x_2) \wedge b (x_3, x_2) \\ &\qquad \wedge \neg a (x_3, x_1) \wedge \neg a (x_3, x_2) \\ &\qquad \wedge \neg a (x_1, x_2) \wedge \neg a (x_2, x_1) \\ &\qquad \wedge \neg b (x_1, x_3) \wedge \neg b (x_2, x_3) \\ &\qquad \wedge \neg b (x_1, x_2) \wedge \neg b (x_2, x_1) \end{align*} $$

The formula IF (X,R, {y₁}) has only one free variable x₁. It is, therefore, interpreted over τ by a unary relation. That unary relation is true for y₁, true for y₂ and false for y₃.

As we hinted earlier, the formula IF was introduced because it describes (τ,X') up to an automorphism. Let us see this on our example. The stabilizer of τ is : S(τ) = {e,σ} where e is the identity mapping, and σ is defined by :

$$ \sigma(y_1) = y_2 ; \quad \sigma(y_2) = y_1 ; \quad \sigma(y_3) = y_3 . $$

IF is true for y₁ and y₂ and there is an automorphism of τ such that σ(y₁) = y₂. Therefore, the property holds for the example. Let us now prove it.

**Lemma 1.** Let τ be a configuration. Let X' ⊆ X_τ. Let ||X'|| = p. Let IF(τ,X') be an identifying formula of τ from X'. Let r be the p-ary relation on X that interprets IF on τ. Then :

$$ \begin{align*} & \forall \bar{x}, \bar{x} \in X_{\tau}^{p} ; \quad \bar{x}', \bar{x}' \in X_{\tau}^{p} ; \quad r(\bar{x}) \text{ true and } r(\bar{x}') \text{ true} \\ & \Rightarrow \exists \sigma, \sigma \in S(\tau) \text{ such that } \bar{x} = \sigma(\bar{x}'). \end{align*} $$

**Proof :** We just have to go through the formula IF and see that it unambiguously describes the configuration (X,τ) (up to an isomorphism, of course !). Let $\bar{x} = (x_1,x_2,\dots,x_n)$. By hypothesis we have :

$$ \text{IF } (\tau, X') (\bar{x}) \text{ is true.} $$

Let us now examine that formula. We have :
**Lemma 3** : Let $\tau$ be a configuration. Let $\equiv$ be the equivalence relation defined above. Let $X_{\tau}^{P}/\equiv$ be the quotient set of $X_{\tau}^{P}$ by $\equiv$.

∀ b, b ∈ X_{\tau}^{P}/\equiv \exists r_{b} \text{ a first order p-ary relation } r_{b} \text{ such that :}

$$
r_b (\bar{x}) \text{ true } \Leftarrow \bar{x} \in b.
$$

**Proof :** Let $b \in X_{\tau}^{P}/\equiv$, let $b' \neq b$ another block of $X_{\tau}^{P}/\equiv$. Since $b \neq b'$, we

have :

$$
\forall \bar{x} \in b, \forall \bar{x} \in b', \bar{x}' \text{ is } \underline{\text{not}} \text{ equivalent to } \bar{x}.
$$

By definition of the equivalence relation :

There exists a first order relation $r_{bb}$, such that :

$$
r_{bb}, (\bar{x}) \text{ is true and } r_{bb'}, (\bar{x}') \text{ is not true.}
$$

Consider now the relation $r_b$ defined by :

$$
r_b = \widehat{b' \in X^P / \equiv}^{r_{bb'}} b' \neq b
$$

It clearly satisfies the properties of the lemma. Q.E.D.

**Lemma 4** : Let $\tau$ be a configuration. Let $\bar{x}$ and $\bar{x}'$ be two p-tuples from $X_{\tau}^{P}$. Then, $\bar{x} \equiv \bar{x}'$ if, and only if, there exists an automorphism $a \in S(\tau)$ such that :

$$
a(\bar{x}) = \bar{x}'.
$$

**Proof** : (1) Assume that there exists a ∈ S(τ) such that : a (x̄) = x̄' .

Then, since all relations in First(R) are invariant by S(τ) we have :

$$
\forall r \in \text{First}(R) : r(\bar{x}) \text{ true} \Rightarrow r(a(\bar{x}) \text{ true.}) \quad \text{Q.E.D.}
$$

Therefore, $\bar{x} \equiv \bar{x}'$.

(2) Assume $\bar{x} \equiv \bar{x}'$. Then by definition :

$$
\forall r, r \text{ first order, } \|r\| = p, \text{ we have :}
$$

$$
r(\bar{x}) \text{ true} \Rightarrow r(\bar{x}') \text{ true.}
$$
Let $r_o$ be the relation defined by IF ($\tau, X'$) where $X'$ is the set of coordinates of $\bar{x}$. From Lemma 2, $r_o$ is a first order relation. By construction of IF ($\tau, X'$), $r_o(\bar{x})$ is true. And since $\bar{x} \equiv \bar{x}'$, $r_o(\bar{x}')$ is true.

From Lemma 1, there must exist a in S($\tau$) such that $a(\bar{x}) = \bar{x}'$. Q.E.D.

**Lemma 5** : Let $\tau$ be a configuration. Let $r$ be a p-ary definable relation over $\tau$. Let $\bar{x}$ and $\bar{x}'$ be two p-tuples from $X_{\tau}^p$. Then:

$$r(\bar{x}) \neq r(\bar{x}') \Rightarrow \bar{x} \neq \bar{x}'$$

**Proof** : Assume that $\bar{x} \equiv \bar{x}'$. By Lemma 4 there exists an automorphism $a \in S(\tau)$ such that :

$$a(\bar{x}) = \bar{x}'$$

Therefore, $r(\bar{x}) \neq r(a(\bar{x}'))$. Hence $r$ is not invariant by $a$, therefore, not computable. We have reached a contradiction.

Q.E.D.

We can now prove the Main Theorem. We must show that given a computable relation on $\tau$, we can find a first order formula describing it.

Let $r$ be a p-ary computable relation on $\tau$. Consider the set :

$$A = \{\bar{x} \mid \bar{x} \in X_{\tau}^{p} \text{ and } r(\bar{x}) \text{ true}\}.$$

From Lemma 5 we know that this set is the union of some equivalence classes of $X^p$. Let $b_1, b_2, ..., b_q$ be those classes. From Lemma 3, we know that for each $b_i$ there is a first order $r_{b_i}$ such that :

$$\bar{x} \in b_i \iff r_{b_i}(\bar{x}) \text{ true.}$$

Therefore, we can write :

$$\begin{align*}
r(\bar{x}) \text{ true} &\iff \bar{x} \in A \\
&\iff \bar{x} \in b_1 \cup b_2 \cup \dots \cup b_q \\
&\iff (\bar{x} \in b_1) \cup \dots \cup (\bar{x} \in b_q) \\
&\iff (r_{b_1}(\bar{x}) \cup \dots \cup r_{b_q}(\bar{x})) \\
&\iff \bigcup_i r_{b_i}(\bar{x})
\end{align*}$$

And $\bigcup_i r_{b_i}(\bar{x})$ is clearly a first order relation, which completes the proof of the theorem.
## CONCLUSION

In this paper, we have studied the problem of completeness of relational query languages. We have established a criterion for completeness and argued through examples that it was satisfactory. It was also shown that the classical notions of computability do not apply to our problem because of the existence of unstructured sets (the internal domains). Finally a query language was proved to be complete. Since this language is the one used as a standard for completeness this results gives strong theoretical basis to Codd's definition of completeness.

There are however some limitations to this notion of completeness : for instance there is no first order formula describing the transitive closure $r^*$ of a binary relation r ! While this seems at first to be a contradiction, one should recall that the notion of completeness we have introduced *is static*. Therefore, for any configuration $\tau$ consisting of a binary relation r there exists a formula $r_\tau$ of the first order calculus describing the transitive closure of r, but this formula depends on $\tau$ and there is no formula describing the *mapping* which associates with a binary relation its transitive closure.

## ACKNOWLEDGEMENTS

The author wishes to express his gratitude to Nicolas Spyratos for his invaluable help.
REFERENCES

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.

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

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

CODD 71
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.

CODD 72
Codd E.F. - "Relational Completeness of Data Base Sublanguages", in Data Base Systems, (Rustin Ed), Prentice Hall 1972.