Charles William Bachman Jr. (born Dec. 11, 1924) was an American co...
In 1758 the general prohibition against works promoting heliocentri...
Tab machine is short for Tabulating machine. A Tabulating machine w...
The important thing to remember is that when using magnetic tape (o...
Airline reservations was actually a very early application of compu...
The ideas described here by Bachman were largely standardized by th...
It’s important to remember that database technology was completely ...
1973 ACM Turing
Award
Lecture
The Turing Award citation read by Richard G. Canning, chair-
man of the 1973 Turing Award Committee, at the presentation of
this lecture on August 28 at the ACM Annual Conference in
Atlanta:
A significant change in the computer field in the last five to
eight years has been made in the way we treat and handle data.
In the early days of our field, data was intimately tied to the ap-
plication programs that used it. Now we see that we want to break
that tie. We want data that is independent of the application
programs that use it--that is, data that is organized and structured
to serve many applications and many users. What we seek is the
data base.
This movement toward the data base is in its infancy. Even
so, it appears that there are now between 1,000 and 2,000 true
data base management systems installed worldwide. In ten years
very likely, there will be tens of thousands of such systems. Just
from the quantities of installed systems, the impact of data bases
promises to be huge.
This year's recipient of the A.M. Turing Award is one of the
real pioneers of data base technology. No other individual has
had the influence that he has had upon this aspect of our field. 1
single out three prime examples of what he has done. He was the
creator and principal architect of the first commercially available
data base management system--the Integrated Data Store--orig-
inally developed from 1961 to 1964.1,~,'~.4 I-D-S is today one of the
three most widely used data base management systems. Also, he
.was one of the founding members of the CODASYL Data Base Task
Group, and served on that task group from 1966 to 1968. The
specifications of that task group are being implemented by many
suppliers in various parts of the world) ,e Indeed, currently these
specifications represent the only proposal of stature for a common
architecture for data base management systems. It is to his credit
that these specifications, after extended debate and discussion,
embody much of the original thinking of the Integrated Data
Store. Thirdly, he was the creator of a powerful method for dis-
playing data relationships--a tool for data base designers as well
as application system designers7 .s
His contributions have thus represented the union of imagin-
ation and practicality. The richness of his work has already had,
and will continue to have, a substantial influence upon our field.
I am very pleased to• present the 1973 A.M. Turing Award to
Charles W. Bachman.
l'he Programmer
as Navigator
by Charles W. Bachman
This year the whole world celebrates the five-hun-
dredth birthday of Nicolaus Copernicus, the famous
Polish astronomer and mathematician. In 1543, Coper-
nicus published his book,
Concerning the Revolutions of
Celestial Spheres,
which described a new theory about
the relative physical movements of the earth, the plan-
ets, and the sun. It was in direct contradiction with
the earth-centered theories which had been established
by Ptolemy 1400 years earlier.
Copernicus proposed the heliocentric theory, that
planets revolve in a circular orbit around the sun. This
theory was subjected to tremendous and persistent
criticism. Nearly 100 years later, Galileo was ordered
Copyright O 1973, Association for Computing Machinery, Inc.
General permission to republish, but not for profit, all or part
of this material is granted provided that ACM's copyright notice
is given and that reference is made to the publication, to its date
of issue, and to the fact that reprinting privileges were granted
by permission of the Association for Computing Machinery.
Author's address: Honeywell Information Systems. Inc., 200
Smith Street, Waltham, MA 02154.
The abstract, key words, etc., are on page 654.
1-s Footnotes are on page 658.
653
to appear before the Inquisition in Rome and forced
to state that he had given up his belief in the Copernican
theory. Even this did not placate his inquisitors, and
he was sentenced to an indefinite prison term, while
Copernicus's book was placed upon the Index of Pro-
hibited Books, where it remained for another 200 years.
1 raise the example of Copernicus today to illustrate
a parallel that I believe exists in the computing or, more
properly, the information systems world. We have
spent the last 50 years with almost Ptolemaic informa-
tion systems. These systems, and most of the thinking
about systems, were based on a "computer centered"
concept. (I choose to speak of 50 years of history rather
than 25, for I see today's information systems as dating
from the beginning of effective punched card equip-
ment rather than from the beginning of the stored
program computer.)
Just as the ancients viewed the earth with the sun
revolving around it, so have the ancients of our in-
formation systems viewed a tab machine or computer
with a sequential file flowing through it. Each was an
Communications November 1973
of Volume 16
the ACM Number I 1
adequate model for its time and place. But after a while,
each has been found to be incorrect and inadequate
and has had to be replaced by another model that more
accurately portrayed the real world and its behavior.
Copernicus presented us with a new point of view
and laid the foundation for modern celestial mechan-
ics. That view gave us the basis for understanding the
formerly mysterious tracks of the sun and the planets
through the heavens. A new basis for understanding is
available in the area of information systems. It is
achieved by a shift from a computer-centered to the
database-centered point of view. This new understand-
ing will lead to new solutions to our database problems
and speed our conquest of the n-dimensional data
structures which best model the complexities of the
real world.
The earliest databases, initially implemented on
punched cards with sequential file technology, were not
significantly altered when they were moved, first from
punched card to magnetic tape and then again to mag-
netic disk. About the only things that changed were
the size of the files and the speed of processing them.
In sequential file technology, search techniques are
well established. Start with the value of the primary
data key, of the record of interest, and pass each record
in the file through core memory until the desired record,
or one with a higher key, is found. (A primary data key
is a field within a record which makes that record
unique within the file.) Social security numbers, pur-
chase order numbers, insurance policy numbers, bank
account numbers are all primary data keys. Almost
without exception, they are synthetic attributes spe-
cifically designed and created for the purpose of unique-
ness. Natural attributes, e.g. names of people and
places, dates, time, and quantities, are not assuredly
unique and thus cannot be used.
The availability of direct access storage devices laid
the foundation for the Copernican-like change in view-
point. The directions of"in" and
"out"
were reversed.
Where the input notion of the sequential file world
meant "into the computer from tape," the new input
notion became "into the database." This revolution in
thinking is changing the programmer from a stationary
viewer of objects passing before him in core into a
mobile navigator who is able to probe and traverse a
database at will.
Direct access storage devices also opened up new
ways of record retrieval by primary data key. The first
was called randomizing, calculated addressing, or hash-
ing. It involved processing the primary data key with a
specialized algorithm, the output of which identified a
preferred storage location for that record. If the record
sought was not found in the preferred location, then an
overflow algorithm was used to search places where the
record alternately would have been stored, if it existed
at all. Overflow is created when the preferred location
is full at the time the record was originally stored.
As an alternative to the randomizing technique, the
654
Copernicus completely reoriented our view of astro-
nomical phenomena when he suggested that the earth
revolves about the sun. There is a growing feeling that
data processing people would benefit if they were to
accept a radically new point of view, one that would
liberate the application programmer's thinking from the
centralism of core storage and allow him the freedom to
act as a navigator within a database. To do this, he
must first learn the various navigational skills; then he
must learn the "rules of the road" to avoid conflict
with other programmers as they jointly navigate the
database information space.
This reorientation will cause as much anguish among
programmers as the heliocentric theory did among
ancient astronomers and theologians.
Key Words and Phrases: access method, attributes,
calculated addressing, celestial mechanics, clustering,
contamination, database, database key, database set,
deadlock, deadly embrace, entity, hash addressing,
overflow, owner, member, primary data key, Ptolemy,
relationship, retrieval, secondary data key, sequential
file, set, shared access, update, Weyerhaeuser
CR Categories: 3.74, 4.33, 4.34, 5.6, 8.1
index sequential access technique was developed. It
also used the primary data key to control the storage
and retrieval of records, and did so through the use of
multilevel indices.
The programmer who has advanced from sequential
file processing to either index sequential or randomized
access processing has greatly reduced his access time
because he can now probe for a record without sequen-
tially passing all the intervening records in the file.
However, he is still in a one-dimensional world as he is
dealing with only one primary data key, which is his
sole means of controlling access.
From this point, I want to begin the programmer's
training as a full-fledged navigator in an n-dimensional
data space. However, before I can successfully describe
this process, I want to review what "database manage-
ment" is.
It involves all aspects of storing, retrieving, modify-
ing, and deleting data in the files on personnel and pro-
duction, airline reservations, or laboratory experiments
--data which is used repeatedly and updated as new
information becomes available. These files are mapped
through some storage structure onto magnetic tapes or
disk packs and the drives that support them.
Database management has two main functions. First
is the inquiry or retrieval activity that reaccesses previ-
ously stored data in order to determine the recorded
status of some real world entity or relationship. This
data has previously been stored by some other job,
seconds, minutes, hours, or even days earlier, and has
been held in trust by the database management system.
A database management system has a continuing re-
Communications November 1973
of Volume 16
the ACM Number 1 !