The first 5 pages, shown as text so search engines and readers can find this document.
Page 1
Information Retrieval P. BAXENDALE, Editor
A Relational Model of Data for
Large Shared Data Banks
E. F. CODD
IBM Research Laboratory, San Jose, California
Future users of large data banks must be protected from
having to know how the data is organized in the machine (the
internal representation). A prompting service which supplies
such information is not a satisfactory solution. Activities of users
at terminals and most application programs should remain
unaffected when the internal representation of data is changed
and even when some aspects of the external representation
are changed. Changes in data representation will often be
needed as a result of changes in query, update, and report
traffic and natural growth in the types of stored information.
Existing noninferential, formatted data systems provide users
with tree-structured files or slightly more general network
models of the data. In Section 1, inadequacies of these models
are discussed. A model based on n-ary relations, a normal
form for data base relations, and the concept of a universal
data sublanguage are introduced. In Section 2, certain opera-
tions on relations (other than logical inference) are discussed
and applied to the problems of redundancy and consistency
in the user’s model.
KEY WORDS AND PHRASES: data bank, data base, data structure, data
organization, hierarchies of data, networks of data, relations, derivability,
redundancy, consistency, composition, join, retrieval language, predicate
calculus, security, data integrity
CR CATEGORIES: 3.70, 3.73, 3.75, 4.20, 4.22, 4.29
1. Relational Model and Normal Form
1.I. INTR~xJ~TI~N
This paper is concerned with the application of ele-
mentary relation theory to systems which provide shared
accessto large banks of formatted data. Except for a paper
by Childs [l], the principal application of relations to data
systems has been to deductive question-answering systems.
Levein and Maron [2] provide numerous referencesto work
in this area.
In contrast, the problems treated here are those of data
independence-the independence of application programs
and terminal activities from growth in data types and
changesin data representation-and certain kinds of data
inconsistency which are expected to become troublesome
even in nondeductive systems.
Volume 13 / Number 6 / June, 1970
The relational view (or model) of data described in
Section 1 appears to be superior in several respects to the
graph or network model [3,4] presently in vogue for non-
inferential systems. It provides a means of describing data
with its natural structure only-that is, without superim-
posing any additional structure for machine representation
purposes. Accordingly, it provides a basis for a high level
data language which will yield maximal independence be-
tween programs on the one hand and machine representa-
tion and organization of data on the other.
A further advantage of the relational view is that it
forms a sound basis for treating derivability, redundancy,
and consistency of relations-these are discussedin Section
2. The network model, on the other hand, has spawned a
number of confusions, not the least of which is mistaking
the derivation of connections for the derivation of rela-
tions (seeremarks in Section 2 on the “connection trap”).
Finally, the relational view permits a clearer evaluation
of the scope and logical limitations of present formatted
data systems, and also the relative merits (from a logical
standpoint) of competing representations of data within a
single system. Examples of this clearer perspective are
cited in various parts of this paper. Implementations of
systems to support the relational model are not discussed.
1.2. DATA DEPENDENCIESIN PRESENTSYSTEMS
The provision of data description tables in recently de-
veloped information systems represents a major advance
toward the goal of data independence [5,6,7]. Such tables
facilitate changing certain characteristics of the data repre-
sentation stored in a data bank. However, the variety of
data representation characteristics which can be changed
without logically impairing some application programs is
still quite limited. Further, the model of data with which
users interact is still cluttered with representational prop-
erties, particularly in regard to the representation of col-
lections of data (as opposed to individual items). Three of
the principal kinds of data dependencies which still need
to be removed are: ordering dependence, indexing depend-
ence, and accesspath dependence. In some systems these
dependencies are not clearly separable from one another.
1.2.1. Ordering Dependence. Elements of data in a
data bank may be stored in a variety of ways, someinvolv-
ing no concern for ordering, some permitting each element
to participate in one ordering only, others permitting each
element to participate in several orderings. Let us consider
those existing systems which either require or permit data
elements to be stored in at least one total ordering which is
closely associated with the hardware-determined ordering
of addresses.For example, the records of a file concerning
parts might be stored in ascending order by part serial
number. Such systems normally permit application pro-
grams to assumethat the order of presentation of records
from such a file is identical to (or is a subordering of) the
Communications of the ACM 377
Page 2
stored ordering. Those application programs which take
advantage of the stored ordering of a file are likely to fail
to operate correctly if for some reason it becomes necessary
to replace that ordering by a different one. Similar remarks
hold for a stored ordering implemented by means of
pointers.
It is unnecessary to single out any system as an example,
because all the well-known information systems that are
marketed today fail to make a clear distinction between
order of presentation on the one hand and stored ordering
on the other. Significant implementation problems must be
solved to provide this kind of independence.
1.2.2. Indexing Dependence. In the context of for-
matted data, an index is usually thought of as a purely
performance-oriented component of the data representa-
tion. It tends to improve response to queries and updates
and, at the same time, slow down response to insertions
and deletions. From an informational standpoint, an index
is a redundant component of the data representation. If a
system uses indices at all and if it is to perform well in an
environment with changing patterns of activity on the data
bank, an ability to create and destroy indices from time to
time will probably be necessary. The question then arises:
Can application programs and terminal activities remain
invariant as indices come and go?
Present formatted data systems take widely different
approaches to indexing. TDMS [7] unconditionally pro-
vides indexing on all attributes. The presently released
version of IMS [5] provides the user with a choice for each
file: a choice between no indexing at all (the hierarchic se-
quential organization) or indexing on the primary key
only (the hierarchic indexed sequent,ial organization). In
neither case is the user’s application logic dependent on the
existence of the unconditionally provided indices. IDS
[8], however, permits the fle designers to select attributes
to be indexed and to incorporate indices into the file struc-
ture by means of additional chains. Application programs
taking advantage of the performance benefit of these in-
dexing chains must refer to those chains by name. Such pro-
grams do not operate correctly if these chains are later
removed.
1.2.3. Access Path Dependence. Many of the existing
formatted data systems provide users with tree-structured
files or slightly more general network models of the data.
Application programs developed to work with these sys-
tems tend to be logically impaired if the trees or networks
are changed in structure. A simple example follows.
Suppose the data bank contains information about parts
and projects. For each part, the part number, part name,
part description, quantity-on-hand, and quantity-on-order
are recorded. For each project, the project number, project
name, project description are recorded. Whenever a project
makes use of a certain part, the quantity of that part com-
mitted to the given project is also recorded. Suppose that
the system requires the user or file designer to declare or
define the data in terms of tree structures. Then, any one
of the hierarchical structures may be adopted for the infor-
mation mentioned above (see Structures l-5).
378 Communications of the ACM
Structure 1. Projects Subordinate to Parts
File Segment Fields
F PART part #
part name
part description
quantity-on-hand
quantity-on-order
PROJECT project #
project name
project description
quantity committed
Structure 2. Parts Subordinate to Projects
File Sqmeut Fields
F PROJECT project #
project name
project description
PART part #
part name
part description
quantity-on-hand
quantity-on-order
quantity committed
Structure 3. Parts and Projects as Peers
Commitment Relationship Subordinate to Projects
File Segment Fields
F PART part #
part name
part description
quantity-on-hand
quantity-on-order
G PROJECT project #
project name
project description
PART part #
quantity committed
Structure 4. Parts and Projects as Peers
Commitment Relationship Subordinate to Parts
File Segnren1 Fields
F PART part #
part description
quantity-on-hand
quantity-on-order
PROJECT project #
quantity committed
G PROJECT project #
project name
project description
Structure 5. Parts, Projects, and
Commitment Relationship as Peers
FCZC .%&-,,ZC,,t Ficlds
F PART part #
part name
part description
quantity-on-hand
quantity-on-order
G PROJECT project #
project name
project description
H COMMIT part #
project #
quantity committed
Volume 13 / Number 6 / June, 1970
Page 3
Now, consider the problem of printing out the part
number, part name, and quantity committed for every part
used in the project whose project name is “alpha.” The
following observations may be made regardless of which
available tree-oriented information system is selected to
tackle this problem. If a program P is developed for this
problem assuming one of the five structures above-that
is, P makes no test to determine which structure is in ef-
fect-then P will fail on at least three of the remaining
structures. More specifically, if P succeeds with structure 5,
it will fail with all the others; if P succeeds with structure 3
or 4, it will fail with at least 1,2, and 5; if P succeeds with
1 or 2, it will fail with at least 3, 4, and 5. The reason is
simple in each case. In the absence of a test to determine
which structure is in effect, P fails because an attempt is
made to exceute a reference to a nonexistent file (available
systems treat this as an error) or no attempt is made to
execute a reference to a file containing needed information.
The reader who is not convinced should develop sample
programs for this simple problem.
Since, in general, it is not practical to develop applica-
tion programs which test for all tree structurings permitted
by the system, these programs fail when a change in
&ructure becomes necessary.
Systems which provide users with a network model of
the data run into similar difficulties. In both the tree and
network cases, the user (or his program) is required to
exploit a collection of user access paths to the data. It does
not matter whether these paths are in close correspondence
with pointer-defined paths in the stored representation-in
IDS the correspondence is extremely simple, in TDMS it is
just the opposite. The consequence, regardless of the stored
representation, is that terminal activities and programs be-
come dependent on the continued existence of the user
access paths.
One solution to this is to adopt the policy that once a
user access path is defined it will not be made obsolete un-
til all application programs using that path have become
obsolete. Such a policy is not practical, because the number
of access paths in the total model for the community of
users of a data bank would eventually become excessively
large.
1.3. A RELATIONAL VIEW OF DATA
The term relation is used here in its accepted mathe-
matical sense.Given sets X1, S, , . . . , S, (not necessarily
distinct), R is a relation on these n sets if it is a set of n-
tuples each of which has its first element from S1, its
second element from Sz , and so on.’ We shall refer to Si as
the jth domain of R. As defined above, R is said to have
degreen. Relations of degree 1 are often called unary, de-
gree 2 binary, degree 3 ternary, and degree n n-ary.
For expository reasons, we shall frequently make use of
an array representation of relations, but it must be re-
membered that this particular representation is not an es-
sential part of the relational view being expounded. An ar-
1 More concisely, R is a subset of the Cartesian product 81 X
sz x *.* x 87%.
ray which represents an n-ary relation R has the following
properties :
(1) Each row represents an n-tuple of R.
(2) The ordering of rows is immaterial.
(3) All rows are distinct.
(4) The ordering of columns is significant-it corre-
sponds to the ordering S1, Sz , . . . , S, of the do-
mains on which R is defined (see, however, remarks
below on domain-ordered and domain-unordered
relations ) .
(5) The significance of each column is partially con-
veyed by labeling it with the name of the corre-
sponding domain.
The example in Figure 1 illustrates a relation of degree
4, called supply, which reflects the shipments-in-progress
of parts from specified suppliers to specified projects in
specified quantities.
supply (supplier part project quantity)
1 2 5 17
1 3 5 23
2 3 7 9
2 7 5 4
4 1 1 12
FIG. 1. A relation of degree 4
One might ask: If the columns are labeled by the name
of corresponding domains, why should the ordering of col-
umns matter? As the example in Figure 2 shows, two col-
umns may have identical headings (indicating identical
domains) but possessdistinct meanings with respect to the
relation. The relation depicted is called component. It is a
ternary relation, whose first two domains are called part
and third domain is called quantity. The meaning of com-
ponent (2, y, z) is that part x is an immediate component
(or subassembly) of part y, and z units of part 5 are needed
to assembleone unit of part y. It is a relation which plays
a critical role in the parts explosion problem.
component (part part quantity)
1 5 9
2 5 7
3 5 2
2 6 12
3 6 3
4 7 1
6 7 1
FIG. 2. A relation with-two identical domains
It is a remarkable fact that several existing information
systems (chiefly those based on tree-structured files) fail
to provide data representations for relations which have
two or more identical domains. The present version of
IMS/360 [5] is an example of such a system.
The totality of data in a data bank may be viewed as a
collection of time-varying relations. These relations are of
assorted degrees. As time progresses,each n-ary relation
may be subject to insertion of additional n-tuples, deletion
of existing ones, and alteration of components of any of its
existing n-tuples.
Volume 13 / Number 6 / June, 1970 Communications of the ACM 379
Page 4
In many commercial, governmental, and scientific data
banks, however, some of the relations are of quite high de-
gree (a degree of 30 is not at all uncommon). Users should
not normally be burdened with remembering the domain
ordering of any relation (for example, the ordering supplier,
then part, then project, then quantity in the relation supply).
Accordingly, we propose that users deal, not with relations
which are domain-ordered, but with relationships which are
their domain-unordered counterparts.2 To accomplish this,
domains must be uniquely identifiable at least within any
given relation, without using position. Thus, where there
are two or more identical domains, we require in each case
that the domain name be qualified by a distinctive role
name, which serves to identify the role played by that
domain in the given relation. For example, in the relation
component of Figure 2, the first domain part might be
qualified by the role name sub, and the second by super, so
that users could deal with the relationship component and
its domains-sub.part super.part, quantity-without regard
to any ordering between these domains.
To sum up, it is proposed that most usersshould interact
with a relational model of the data consisting of a collection
of time-varying relationships (rather than relations). Each
user need not know more about any relationship than its
name together with the names of its domains (role quali-
fied whenever necessary): Even this information might be
offered in menu style by the system (subject to security
and privacy constraints) upon request by the user.
There are usually many alternative ways in which a re-
lational model may be established for a data bank. In
order to discuss a preferred way (or normal form), we
must first introduce a few additional concepts (active
domain, primary key, foreign key, nonsimple domain)
and establish some links with terminology currently in use
in information systems programming. In the remainder of
this paper, we shall not bother to distinguish between re-
lations and relationships except where it appears advan-
tageous to be explicit.
Consider an example of a data bank which includes rela-
tions concerning parts, projects, and suppliers. One rela-
tion called part is defined on the following domains:
(1) part number
(2) part name
(3) part color
(4) part weight
(5) quantity on hand
(6) quantity on order
and possibly other domains as well. Each of these domains
is, in effect, a pool of values, some or all of which may be
represented in the data bank at any instant. While it is
conceivable that, at some instant, all part colors are pres-
ent, it is unlikely that all possible part weights, part
2 In mathematical terms, a relationship is an equivalence class of
those relations that are equivalent under permutation of domains
(see Section 2.1.1).
* Naturally, as with any data put into and retrieved from a com-
puter system, the user will normally make far more effective use
of the data if he is aware of its meaning.
names, and part numbers are. We shall call the set of
values represented at someinstant the active domain at that
instant.
Normally, one domain (or combination of domains) of a
given relation has values which uniquely identify each ele-
ment (n-tuple) of that relation. Such a domain (or com-
bination) is called a primary key. In the example above,
part number would be a primary key, while part color
would not be. A primary key is nonredundant if it is either
a simple domain (not a combination) or a combination
such that none of the participating simple domains is
superfluous in uniquely identifying each element. A rela-
tion may possessmore than one nonredundant primary
key. This would be the casein the example if different parts
were always given distinct names. Whenever a relation
has two or more nonredundant primary keys, one of them
is arbitrarily selected and called the primary key of that re-
lation.
A common requirement is for elements of a relation to
cross-reference other elements of the same relation or ele-
ments of a different relation. Keys provide a user-oriented
means (but not the only means) of expressing such cross-
references. We shall call a domain (or domain combma-
tion) of relation R a foreign key if it is not the primary key
of R but its elements are values of the primary key of some
relation S (the possibility that S and R are identical is not
excluded). In the relation supply of Figure 1, the combina-
tion of supplier, part, project is the primary key, while each
of these three domains taken separately is a foreign key.
In previous work there has been a strong tendency to
treat the data in a data bank as consisting of two parts, one
part consisting of entity descriptions (for example, descrip-
tions of suppliers) and the other part consisting of rela-
tions between the various entities or types of entities (for
example, the supply relation). This distinction is difficult
to maintain when one may have foreign keys in any rela-
tion whatsoever. In the user’s relational model there ap-
pears to be no advantage to making such a distinction
(there may be some advantage, however, when one applies
relational concepts to machine representations of the user’s
set of relationships).
So far, we have discussedexamples of relations which are
defined on simple domains-domains whose elements are
atomic (nondecomposable) values. Nonatomic values can
be discussedwithin the relational framework. Thus, some
domains may have relations as elements. These relations
may, in turn, be defined on nonsimple domains, and so on.
For example, one of the domains on which the relation em-
ployee is defined might be salary history. An element of the
salary history domain is a binary relation defined on the do-
main date and the domain salary. The salary history domain
is the set of all such binary relations. At any instant of time
there are as many instances of the salary history relation
in the data bank as there are employees. In contrast, there
is only one instance of the employeerelation.
The terms attribute and repeating group in present data
base terminology are roughly analogous to simple domain
380 Communications of the ACM Volume 13 / Number 6 / June, 1970
Page 5
and nonsimple domain, respectively. Much of the confusion
in present terminology is due to failure to distinguish be-
tween type and instance (as in “record”) and between
components of a user model of the data on the one hand
and their machine representation counterparts on the
other hand (again, we cite “record” as an example).
1.4. NORMAL FORM
A relation whose domains are all simple can be repre-
sented in storage by a two-dimensional column-homo-
geneous array of the kind discussed above. Some more
complicated data structure is necessary for a relation with
one or more nonsimple domains. For this reason (and others
to be cited below) the possibility of eliminating nonsimple
domains appears worth investigating! There is, in fact, a
very simple elimination procedure, which we shall call
normalization.
Consider, for example, the collection of relations ex-
hibited in Figure 3 (a). Job history and children are non-
simple domains of the relation employee.Salary history is a
nonsimple domain of the relation job history. The tree in
Figure 3 (a) shows just these interrelationships of the non-
simple domains.
employee
I
jobhistory
I
salaryhistory
children
employee (man#, name, birthdate, jobhistory, children)
jobhistory (jobdate, title, salaryhistory)
salaryhistory (salarydate, salary)
children (childname, birthyear)
FIG. 3(a). Unnormalized set
employee’ (man#, name, birthdate)
jobhistory’ (man#, jobdate, title)
salaryhistory’ (man#, jobdate, salarydate, salary)
children’ (man#, childname, birthyear)
FIG. 3(b). Normalized set
Normalization proceeds as follows. Starting with the re-
lation at the top of the tree, take its primary key and ex-
pand each of the immediately subordinate relations by
inserting this primary key domain or domain combination.
The primary key of each expanded relation consists of the
primary key before expansion augmented by the primary
key copied down from the parent relation. Now, strike out
from the parent relation all nonsimple domains, remove the
top node of the tree, and repeat the same sequence of
operations on each remaining subtree.
The result of normalizing the collection of relations in
Figure 3 (a) is the collection in Figure 3 (b). The primary
key of each relation is italicized to show how such keys
are expanded by the normalization.
4 M. E. Sanko of IBM, San Jose, independently recognized the
desirability of eliminating nonsimple domains.
If normalization as described above is to be applicable,
the unnormalized collection of relations must satisfy the
following conditions :
(1) The graph of interrelationships of the nonsimple
domains is a collection of trees.
(2) No primary key has a component domain which is
nonsimple.
The writer knows of no application which would require
any relaxation of these conditions. Further operations of a
normalizing kind are possible. These are not discussedin
this paper.
The simplicity of the array representation which becomes
feasible when all relations are cast in normal form is not
only an advantage for storage purposes but also for com-
munication of bulk data between systems which usewidely
different representations of the data. The communication
form would be a suitably compressedversion of the array
representation and would have the following advantages:
(1) It would be devoid of pointers (address-valued or
displacement-valued ) .
(2) It would avoid all dependence on hash addressing
schemes.
(3) It would contain no indices or ordering lists.
If the user’s relational model is set up in normal form,
names of items of data in the data bank can take a simpler
form than would otherwise be the case. A general name
would take a form such as
R (g).r.d
where R is a relational name; g is a generation identifier
(optional); r is a role name (optional); d is a domain name.
Since g is needed only when several generations of a given
relation exist, or are anticipated to exist, and r is needed
only when the relation R has two or more domains named
d, the simple form R.d will often be adequate.
1.5. SOME LINGUISTIC ASPECTS
The adoption of a relational model of data, as described
above, permits the development of a universal data sub-
language based on an applied predicate calculus. A first-
order predicate calculus s&ices if the collection of relations
is in normal form. Such a language would provide a yard-
stick of linguistic power for all other proposed data Ian-
guages, and would itself be a strong candidate for embed-
ding (with appropriate syntactic modification) in a variety
of host Ianguages (programming, command- or problem-
oriented). While it is not the purpose of this paper to
describe such a language in detail, its salient features
would be as follows.
Let us denote the data sublanguage by R and the host
language by H. R permits the declaration of relations and
their domains. Each declaration of a relation identifies the
primary key for that relation. Declared relations are added
to the system catalog for use by any members of the user
community who have appropriate authorization. H per-
mits supporting declarations which indicate, perhaps less
permanently, how these relations are represented in stor-
Volume 13 / Number 6 / June, 1970 Communications of the ACM 381