Chapter 9

Data Management
Systems0

PREVIEW

Bibliographic information retrieval systems have a good deal in common withother information systems, such as question-answering and data base manage­
ment systems. Information retrieval and question answering share a common
interest in natural language processing. The bond between information retrieval
and data base management is provided by the common storage structures—
both types of systems use inverted file directories— and the common pro­cessing strategies. The design and operations of data base management systems
are examined in this chapter.
The main characteristics of the several types of information systems are
summarized first, followed by a description of the principal features of database management systems. The three well-known data base models known as
the relational, hierarchical, and network models are introduced. Certain query­processing strategies are then examined that may help in extracting relevant
information from the data base in answer to incoming user queries. Finally, theuse of data base management systems for the preservation of data quality is
described, including the data security and integrity provisions that are often
used, and the restart and recovery techniques that can be invoked when system
failures occur.
354

DATA MANAGEMENT SYSTEMS

355

The chapter closes with a brief discussion of the problems arising whenseveral users are allowed to use a data base management system concurrently,
and when the stored files are distributed among several cooperating, remotely
located sites.
1

TYPES OF INFORMATION SYSTEMSAInformation Retrieval and Question Answering

The previous chapters dealt primarily with document retrieval systems, de­signed to retrieve bibliographic references in answer to queries submitted by
the user population. In that context, the term “information” receives the spe­cialized interpretation of data derived from texts or bibliographic items. Ide­ally, information retrieval systems can retrieve many different kinds of prod­
ucts for the user, including full bibliographic citations for the retrieved items,
abstracts, lists of assigned keywords, contract and project numbers, references
to other documents, or even full document texts. The expectation is that manyof the retrieved documents will contain elements that directly respond to theuser’s information needs. Indeed, the success of the existing bibliographic re­trieval systems indicates that these systems are used as an important source of
information by many users.
Unfortunately the existing systems are restricted in many ways: most im­
portantly, users are not given direct facts in answer to any question, but rather
obtain information that may lead to answers; second, the existing systems con­fine themselves to the retrieval of document citations or document excerpts
only. That is, following the document retrieval step, most systems do not pro­vide additional automatic aids to process or interpret the retrieved data. In­
stead, the users are left entirely to their own devices when it comes to interpret­
ing and utilizing the retrieved information.
In actual fact, many user queries require data from a variety of sources.
This may include normal bibliographic references and also nonbibliographic
data of many kinds such as product information, marketing data, technology
forecasts, business data, information about federal rules and regulations, legal
decisions, and industrial or manufacturing summaries. As it happens, databases covering these and many other classes of information already exist in thefield, but the methods needed to coordinate the various data sources and to pro­vide simple and compatible accessing procedures are not available [1].
It is likely that most information system users are interested in facts, rather
than in documents that need to be studied before the needed information can beextracted. One possibility for simplifying the user’s task in this respect consists
in breaking up each document into small pieces— for example, individual chap­ters, pages, paragraphs, or even sentences— and in retrieving the individual
pieces rather than full documents only. The work on passage retrieval that was
briefly mentioned in Chapter 7 constitutes a step in that direction. If this ap­
proach were to be effective, it might become necessary to analyze the docu­
ment content sufficiently deeply to be able to characterize the various text

CHAPTER 9356

portions and to point out differences and relationships between them. Further­more, the full document texts must also be stored to provide the needed passage
retrieval capability.
Passage retrieval is attractive because the basic retrieval process used forfull document retrieval, including the file organization, query formulation, anduser-system interaction methods, may remain unchanged. On the other hand,
the information input and analysis tasks are now vastly more complicated, andthe resulting system may be too expensive to use. In the final analysis, passage
retrieval may constitute a step in the right direction so far as the user is con­cerned, but the ability to answer questions by citing specific facts included in
the data base is still lacking.
The question-answering systems mentioned in Chapter 7 are specificallydesigned to provide direct answers to questions; however, the earlier discus­
sion indicated that the construction of unrestricted question-answering systems
was not a likely prospect for the visible future. Not all relevant facts could pos­sibly be stored in any particular system, nor could all the needed relationships
between stored facts be identified in advance. Necessarily then, a viable ques­tion-answering system would operate with a restricted data base using proce­dures for refining the available information as needed by deducing new facts
from already available information and supplementing the description of in­completely specified items by extraneous knowledge.
Simple deductive systems can be built that are capable of answering manyquestions for which the direct answer is not initially contained in the data base.
Thus, given the facts that “Joe Smith is an employee” and that “All employees
are at least 18 years old,” an answer generating system could be built to handle
correctly a question such as “Is Joe Smith at least 18 years old?” However,more complicated situations are easy to imagine where even sophisticated sys­
tems would soon become stymied. Consider, for example, a knowledge baseconsisting of the following sentences:
Joe Smith is an employee.
87 percent of all employees are union members.
Joe Smith voted in the last election.
It is obvious that the question “Is Joe Smith a union member?” cannot be an­swered unequivocally. However, if one knew that Smith’s job classification en­
tails compulsory union membership, an answer might be provided. Alterna­
tively, if it were known that a union election had recently been held, the system
could answer “ yes” with reasonable confidence, assuming that information
was available to the system about labor unions and elections and the interac­tions between them.
In the earlier examples, potential ambiguities— for example, the distinc­tion between political elections and union elections— were deliberately disre­garded. Unfortunately, linguistic ambiguities are unavoidable and effective dis­
ambiguation or interpretation methods are not readily available. It is not
surprising then that practical question-answering systems have been based on

DATA MANAGEMENT SYSTEMS

357

highly simplified world pictures where only a small number of facts are used,the description of all items is unambiguous and complete, and the relationships
between the items are prespecified. In such situations, direct answers can beprovided to a wide variety of questions. The so-called data base management
systems are the most widely used and most successful systems in this class.
They are examined in the remainder of this chapter.
B

Data M anagem ent S ystem s

Data management systems exhibit many similarities with standard information
retrieval systems: a stored data base is generated and maintained, and informa­tion searches are conducted resulting in the retrieval of portions of the stored
data in answer to user queries. The distinguishing characteristic in data man­agement systems is the definite structure of the stored information: instead of
dealing with natural language texts as in document retrieval, or with arbitrary
facts as in question answering, uncertainties and ambiguities are eliminated byusing only information items whose structure is severely restricted and com­pletely specified. In particular, data management systems normally process
files of data described by a small set of prespecified attributes. For example, afile of personnel records may be identified by the names of the people involved,
the addresses, the age of each person, the job classifications, and the yearlysalaries for each person. Each attribute may be expected to carry only one of asmall number of specific values— for example, the age attribute may range invalue from 18 to 65 for the employees in question. A particular record in the file
can then be described by citing the specific values taken on by the attributes forthat particular record. Thus the person named Smith might be specified as(NAME = Smith; ADDRESS = 110 Main St.; AGE = 25;
JOB CLASS = 123; SALARY = 19,500)
It is obvious that in such an environment many of the most difficult re­trieval problems can be bypassed, including in particular the choice of the in­dexing language, and the content analysis and indexing operations themselves.
Furthermore, by assuming that each item is completely and unambiguously de­scribed by the chosen attribute values (the values of the available attributes),
the type of processing to be carried out is also limited. In particular, one would
want to compare the attribute values specified in a user query with the attributevalues characterizing the stored data in the hope of retrieving all records whose
attribute values match a given set of query attribute values, or all records
whose attribute values fall within a certain range (for example, all persons
whose age is between 25 and 35). In addition, data base management systems
may be designed to perform simple numeric processing tasks, such as deter­mining counts of the number of records obeying a particular specification— forexample, the number of books published in a given year, or by a particular pub­lisher; or obtaining averages, such as the average cost of the books published ina given year.

358

CHAPTER 9

It is easy to see that systems exhibiting the capabilities outlined above ful­
fill many immediate needs in a variety of different circumstances: it becomes
possible to choose rapidly from a list of employees all those qualified for a given
job, or from a set of military personnel all those currently present in a given
geographic area and able to take on a particular task. Similarly, one can obtain
manufacturing components from a parts inventory obeying particular specifica­
tions, or identify mail items that need to be routed in a given direction, or air­line flights scheduled for specified routes.
Systems capable of performing tasks of that kind are known as data basemanagement systems (DBMS). They are enjoying great popularity and wide­
spread use at the present time [2-5]. Certain data base systems have been
adapted for specialized use by particular user classes. Management informa­tion systems (MIS) are essentially data base management systems that include
additional computational features thought to be of interest to managers. Thus,
given sales figures covering certain periods of time, a trend analysis could be
carried out using an MIS that would project these figures into the future [6-9].
Management information systems extend the processing capabilities ofstandard data base management systems in a direction useful to management
personnel. In the so-called decision support systems (DSS) the aim has been toextend the basic file processing routines by adding capabilities from other areasof computer application including, for example, graphic data processing, pat­tern matching, and artificial intelligence. The aim in this case is to provide in aneasily accessible form the large diversity of resources normally thought to beneeded for decision making purposes.
Consider as an example the person responsible for the design of school bus
routes in a given community. Such a person requires information about the
number of school-age children living in particular areas, the number and type ofavailable school buses, the distances between various points on prospective
routes, and the schedules followed in various schools. In addition to this stan­
dard information that could be provided by conventional data base manage­
ment systems, other less tangible, but potentially equally important data mightalso be used to solve the routing problem. This could include information aboutpeak traffic loads, icy road conditions, and traffic light placement. Information
might also be useful concerning the composition of voting districts in the com­munity, and the expected opposition from the parents to some of the proposed
bus routes. Once a particular routing is tentatively chosen, the ideal decision
support system would provide simulation capabilities, complete with graphic
output displays, through which the progress of the various buses could be mon­itored in a dry-run situation in the hope of detecting problem areas before final
decisions are actually reached.
Completely flexible decision support systems are not currently used inpractice, but beginnings have been made in many application areas including
medicine, banking, and airline management [10-15]. Most existing systems
lack the ability to use information from many different sources, and in addition
provide only limited processing aids. The chart of Fig. 9-1 exhibits relation-

359

DATA MANAGEMENT SYSTEMSDECISIONSUPPORT
MANAGEMENTINFORMATION
Processing
abilityfollowing
retrieval

DATA BASE
MANAGEMENTPERSONAL
RECORD SYSTEMSINFORMATIONRETRIEVAL

Heterogeneity of users

Figure 9-1

Characteristics of several information systems.

hipsjbetween various types of information systems based on the type of userthat is likely to be attracted to the system and the processing ability following
an initial retrieval action. Whereas normal bibliographic retrieval systems must
serve many different user types but provide little processing support beyond
retrieval, the reverse is true of management information systems. Decision sup­port systems are demanding on both accounts, which explains why such sys­
tems are not yet widely used.
The data base management systems, by constrast, are widely used andhave achieved great sophistication with considerable theoretical background.
They share the main file structures and search methodologies with biblio­
graphic retrieval, and they provide processing facilities that are also of interestin the bibliographic retrieval environment. The data base management systems
will be studied in the remainder of this chapter.
2

THE STRUCTURE OF DATA BASE MANAGEMENT SYSTEMS

A

Basic C oncepts

It was mentioned earlier that many of the harder problems arising in informa­tion retrieval are avoided in data base management because of the simpler,
more structured nature of the data being manipulated. On the other hand, themissing content analysis and other text processing operations are replaced in
the DBMS by a greater concern for user friendliness and data quality, and by
the inclusion of sophisticated methods for processing and updating the database. In a typical bibliographic retrieval system, ordinary users are not allowed
to change the stored data. This contrasts with a DBMS, where much of the de­sign complexity is associated with the data manipulations and the available
methods for introducing changes to the stored information. Furthermore, database systems are designed to be used by nonexperts, and great care is taken to
insulate the users from the details of the processing system, and by extension toensure that users cannot interfere with each other. This implies that in addition
to providing the normal search and retrieval capability, the system is also

360

CHAPTER 9

charged with various access control tasks and with the preservation of data in­tegrity and correctness.
A data base management system exhibits three main components: first a
data base consisting of a variety of files broken down into individual records
together with the accessing and file maintenance operations performed on thefiles; second, a communications system that provides the interface between thesystem users and the automatic system, including also the message handling,
editing, and output display functions; and finally, a transaction management
system that is charged with the scheduling of jobs received from the various
users, the access control to the files, the handling of concurrent operations fortasks that may be carried out simultaneously, and the implementation of restartand recovery procedures following system failure.
The following features, which are present in most data base management
implementations, render such systems attractive to the user populations [1621]:

1 The user application programs can normally be written without detailed
know-how of the methods used to represent and organize the data in storage,
and without regard to the particular procedures used to access the data. In
other words the user programs exhibit physical data independence because
they do not depend on the actual implementation methods used by the database management system.
2 Attempts are also made to provide logical data independence in thesense that the user programs may effectively be independent of the internal
structure of the data base objects and of the various relationships which may be
defined between objects.
3 High-level language facilities are often provided to help the users insubmitting queries to the system and in specifying the required file processing
operations.
4 Data quality may be maintained by having the user supply validation
statements concerning the characteristics of files and data items— for example,
a specification of the range of values that may be acceptable for specific attri­butes— and letting the system automatically provide error checks designed toverify the validation assertions.
5 Restart facilities are provided charged with maintaining correct pro­cessing sequences when failures occur by having the system record the statusof current conditions at appropriate intervals and using backup facilities to re­sume the programs after corrections based on the recorded status information.
6 Security provisions may be incorporated in the form of privacy trans­
formations and access controls to ensure that the stored information is not mis­used or misappropriated.
To translate the high-level process specifications into specific machine op­
erations and to provide the data independence mentioned earlier, it is neces­sary to store a detailed description of the file structures actually used and of thestructure of the individual records included in each file. This description of thedata and file representations is known as a schema. Various schema types may

DATA MANAGEMENT SYSTEMS

Figure 9-2

361

Environment for typical data base management system. (A d a p te d fro m re fe re n ce

21 .)be distinguished, including the external or user schema utilized by individual
customers to specify the structure of their own data, a conceptual schema
which is common for all users and serves to supply the required data indepen­
dence, and finally a machine or internal schema used to represent the actual
physical data structures that are needed by the system to carry out the file pro­cessing operations.
Normally high-level “data description” languages are provided by the database management system to help the system users in specifying the individualuser schemas. Once a schema is specified by the user, the translation of theexternal schema into the internal form used by the programs is then completely
left to the system. In performing the program setup and translation operations>Figure 9-3

Levels of data base representation.

CHAPTER 9362

the system normally uses a stored data dictionary which records the descrip­tion of all objects in the system, including the files and corresponding file
schemas, the user terminals and their identifications and characteristics, the in­dividual users and their status and file access authorizations, and the particulartransactions or file manipulations that actually need to be carried out.
The structure of a typical data base management system from the user’s
viewpoint is shown in Fig. 9-2, and the relationship between the various filedescriptions is summarized in Fig. 9-3.
B

Structure of Information Items

To describe the individual operations of a data base management system, it isnecessary to consider in more detail the structure of the information whichneeds to be manipulated. The utilization of special information structures con­stitutes in fact a principal characteristic distinguishing conventional biblio­
graphic retrieval from data base management: specifically, the information
used in bibliographic information retrieval is normally assumed to be unstruc­tured, and the data elements are often self-describing in the sense that it is easy
to distinguish author names from publishers or document titles. In a data basemanagement environment the individual record elements are not self-describ­
ing, and a definite record structure is either assumed or implied.
Consider as an example the components of a typical bibliographic record
used by the INSPEC retrieval service and represented in Table 9-1. This record
includes three types of identifiers, including the objective terms such as author,
journal, or page numbers; the content identifiers consisting in Table 9-1 offreely chosen terms and terms extracted from a controlled vocabulary arrange­
ment; and finally the title and abstract of the document. In addition to the struc­ture implied by this list, a great deal of syntactic and semantic structure is in­herent in the language of the title and abstract; furthermore, the chronologicalrelationship which exists between the actual article and the bibliographic refer­ences attached to the item can be used to define explicit hierarchical relations
between articles.
In actual fact, the linguistic structure built into a bibliographic record is notnormally used in information retrieval. The terms and keywords are nearly alTable 9-1 Com ponents of Bibliographic Record
Used by INSPEC Service
Title of item
Author name(s)Author affiliation(s)Publication identification
Volume, issue, or part number
Date of publication
Page numbers
Language of publication
Full text of abstract

Number of references
Classification codes
Controlled index terms
Free index terms
Type of article or treatment(for example, bibliography
or literature survey,
general or review article)

DATA MANAGEMENT SYSTEMS

363

ways assumed to be independent of each other, and the language analysis
methods needed to exhibit the linguistic structure of title and abstract are ex­pensive to carry out and not sufficiently reliable for practical use. In data basemanagement the situation is very different because structure is deliberately
built into the records and used in retrieval.
To describe the structure of the information items in a data base system, it
is convenient to distinguish the entities being manipulated from the attributes
characterizing the entities. The normal distinction between the two depends on
the role they play in a particular retrieval environment: entities are data objects
that have an independent life of their own, and as such they constitute the ele­ments of principal interest for the user of the retrieval system; attributes, on the
Angela Colefemale60

Charles Smithmale
42

Mamie Younger
female40

Alan Smithmale
13Bill Younger
male
10

Arlene Smith
female
10

(a)

(b)

Figure 9-4 Sample PERSON data base, (a) PERSON entities identified by attributes NAME,
SEX, AGE. (b) PERSON entities with specified parent-child relations.

364

CHAPTER 9

other hand, exist only because they are assigned as identifiers to the defined
entities. The choice of appropriate entities and attributes to be used in a given
data base system is a matter of substantial difficulty for the data base designer,and data elements used as attributes in one context may well be defined as enti­
ties in another. For example, the entity STUDENT may be characterized by
the attribute TEACHER who is responsible for a particular class in which thestudent is registered; on the other hand, a TEACHER may constitute a sepa­
rate entity identified by separate attributes. A typical entity class consisting of
persons identified by attributes NAME, SEX, and AGE is shown in Fig. 9-4a.
The actual values of the attributes characterizing the individual persons are in­cluded in Fig. 9-4.
It is customary in DBMS environments to define two types of relationships
between entities, including the generic or hierarchical inclusion relationships
where some entities are general or governing types of entities and others are
narrower and thus dependent on the more general ones. In that case, a hierar­
chical, tree-type arrangement can be used to represent the relationships suchthat the governing entities are placed above the corresponding descendants in a
two-dimensional graph. Typical hierarchical relationships are whole/part andparent/child relationships. The parent/child relationships defined for the database of Fig. 9-4a are identified in Fig. 9-4b by vertical pointers (arrows) to thehierarchically inferior child.
The other type of relationship between entities includes the nonhierarchical relationships for which an unambiguous governing-descendant characteri­zation cannot be used. Many different types of nonhierarchical relationships
may be used in particular cases, including, for example, cause/effect relation­
ships (as between “poison” and “ death”) and actor/acted upon relationships (asbetween “pilot” and “plane”). To represent nonhierarchical relationships,
networks instead of tree structures must normally be used where the pointers
once again represent connections between related entities. A typical example isshown in Fig. 9-5 for the entity types PILOTS, EMPLOYEES, PLANES, and
DEPARTURES. The pilots have a flight capability, being certified to fly certain
planes; at the same time the pilots are also employees of an airline company.
The airline assigns certain employees to particular departures, each departure
representing a flight leaving at a certain time and date with a particular routing.
Obviously a plane must also be assigned to each departure. Relationships suchas those illustrated in Fig. 9-5 cannot be represented by a hierarchical tree ar­rangement [22,23].
For efficient implementation, relationships between entities are often clas­sified according to how many entities of one type may be associated with theentities of another type. Thus there may be one-to-one (1:1) relationships as
between PLANES and DEPARTURES, a particular unique plane being nor­mally assigned to each given departure. Alternatively the relationship may be
many-to-one (n:l) as between STUDENTS and CLASSROOM, where many
students are assigned to a given class, or many-to-many (n:m) as between
PROJECTS and EMPLOYEES, where one project occupies many employees
but one employee may be assigned to many projects.

365

DATA MANAGEMENT SYSTEMSPILOTSEMPLOYEESPLANES

DEPARTURES

Figure 9-5 Typical nonhierarchical relationship in data base.

In the data base, the relationships between entities are normally repre­
sented by pointers included as identifiers for a given entity, and representing
the addresses of the related entities. Thus in the example of Fig. 9-4, the recordfor Mamie Younger includes three pointers, one each to specify the addresses
used to store the record for Alan Smith, Arlene Smith, and Bill Younger. The
use of physical address pointers simplifies the handling of information requests
in which entity relationships play a role, such as, for example, “Give the nameand age of all descendants of Mamie Younger” or “Are there any pilots lessthan 30 years old that earn over $50,000?”
Only relationships between entities have been discussed up to now. How­ever, explicit or implied relationships can also be recognized between attri­butes of entities. Thus semantic relations of many kinds are definable between
attributes, such as, for example, the relationship between a person’s age and his
occupation (elementary school children are normally less than 15 years old,
whereas plumbers or welders are over 15). Another type of relationship be­
tween attributes depends on whether the values of certain attributes may or
may not be the same for distinct records of a collection. Consider, for example,
a personnel file and assume that the social security (SS) number uniquely iden­tifies each person in the file. In these circumstances, it is clear that if two rec­ords happen to be identified by the same SS number, then necessarily the age
attribute must also be the same, because the two records then represent thesame person. Technically speaking, one says that a functional dependency
exists between the social security number of a person and the age of that per­son, or the SS number functionally determines the age.
Semantic relationships and functional dependencies between attributes areusable in file design and to verify the correctness of the data, as will be seen
later.
*C The Relational Data B ase Model

Depending on the kind of relationships that are explicitly used in the data ma­nipulations, it is customary to distinguish three abstract data base models,
known, respectively as the relational, the hierarchical, and the network

366

CHAPTER 9

models. As the names indicate, the hierarchical and network retrieval models
are based, respectively, on hierarchical and network types of relationships be­
tween the entities. In the relational data base model no explicit relationships
are defined between entity types, and no pointers are actually stored. Instead,the relationships between the entities must be derived before they can be usedin answering the queries. Because of the absence of directly specified relation­
ships, the relational model is conceptually easy to deal with, but the processing
needed to retrieve the records wanted in response to a given query may bequite complex [24,25].
A relation is simply a table representing the records in a given file in such a
way that each record, also known as a tuple, is identified by an ordered set of
attribute values. In other words, each record corresponds to a particular row of
the table, and all rows are assumed to be distinct and of the same length. The
order in which the rows appear in the table is immaterial and so is the order ofthe columns. Each column corresponds to a particular attribute characterizing
the records, the column entries being the values of that attribute for the various
records. A sample relation is shown in Table 9-2 representing a collection of
students.
Each relation is characterized by its relation scheme, which is simply theordered list of attribute names used to identify the records. The relation scheme
for the sample relation of Table 9-2 is RELSCHEME (NAME, NUMBER,
CLASS, CREDITS, ADDRESS, CITY). Some attributes or subsets of attri­butes can be used uniquely to identify the records included in a given relation.
These are known as candidate keys or simply keys. Normally, one of the candi­date keys, known as the primary key, is actually selected to represent the rec­ords. For the relation of Table 9-2 all the attributes except for CLASS are can­didate keys. The student number (which certainly uniquely identifies a given
student) could be used as the primary key.
A particular data base normally includes relations corresponding to a num­
ber of different relation schemes. The list of relation schemes characterizing agiven database is known as a relational data base scheme. A typical example isshown in Fig. 9-6 for a data base dealing with employees, managers, andprojects. When a query is processed which requires information from morethan one relation, it must be possible to relate the record information included
Table 9-2

A Sam ple Relation

Name

NumberClass

Credits

Address

City

BrindleCaminoDanielKatzer
McGillNoreault
SaltonWaldstein

01764
25611
43799
77084
37340
19450
30981
47592

SOPH
FRESH
SENIOR
GRAD
SOPH
SOPH
GRAD
JUNIOR

60
20
100
130
45
48
110
90

264 First St.
11 A St.
1011 Main St.
2146 Meadowbrook1819 Edgemont
12 Ackerman.
2365 Meadowlark
12 Woodsy Ave.

New York
Kansas City
Kingston
Philadelphia
Washington
Syracuse
Cambridge
IthacaDATA MANAGEMENT SYSTEMS

367

EMPLOYEE NUMBER

EMPLOYEE NAMEEMPLOYEE NUMBER

MANAGER

3. MANAGER

PROJECT NUMBER

SALARYADDRESS

DEPARTMENT NUMBER

PROJECT NAME

Figure 9-6 Sample relational data base scheme.

in one relation with the information contained in some other relation. In theabsence of pointers to relate corresponding records, the record relationships
are obtainable indirectly if some of the attributes characterizing the records areincluded in more than one of the relation schemes that make up a given database. In other words, the pointer structures used in the hierarchical and net­
work data base models are replaced in the relational model by redundancy inthe stored attributes.
For the sample relational data base scheme of Fig. 9-6 the EMPLOYEENUMBER is included in both the first and the second relation schemes, and theattribute MANAGER is included in the second and third relation schemes.
Thus by choosing entries in the first and second relations corresponding to acommon employee number, one can identify the manager corresponding to agiven employee. An additional search in the third relation for the manager rec­ord corresponding to a given manager included in the second relation deter­
mines the project to which a given employee is assigned.
In addition to interrogating a data base, typical relational database opera­
tions include the insertion of records into a relation, as well as the deletion andthe modification of stored records. The required operations may be sum­
marized by use of a relational algebra that manipulates relations [25], The fol­lowing operations are of main interest:
1 Given two homogeneous relations in which the records are identified
by the same number and the same types of attributes, the union of the two rela­tions is a new relation containing all the distinct tuples contained in either of theoriginal ones. Given relations R and S shown in Fig. 9-7a and b, respectively,
the union R U S is shown in Fig. 9-7c. The record (Adams, 25, New York) ap­
pears only once in the union, even though it is contained in both R and S, be­cause duplicated tuples are not allowed in a relation.
2 The difference between two homogeneous relations contains all tuples
from the first relation that are not also contained in the second one. The differ­ence R - S appears in Fig. 9-7d.
3 A selection operation can be used to choose certain rows of a relation,
depending on conditions imposed on the values of certain attributes. The gen­eral notation used to choose certain tuples from a relation R is SELECTOR),
where F is a formula expressing a condition. Figure 9-7e shows the relation SELECT(NAME= adams,(R) consisting of all records in R whose NAME attribute is“Adams.”CHAPTER 9

368

Adams
Adams
Brown

New York
New York'New York

22
25
22

Adams
Smith

25
25
(b)

(a)

Adams
Adams
Brown
Smith

New York
New York
New York
Chicago

22
25
22
25

New York
Chicago

Adams
Brown

22
22

New York
New York

Id)

Adams
Adams

22
25

New York
New York

New York
New York
(e)

Adams
Adams
Adams
Adams
Brown
Brown

22
22
25
25
22
22

Adams
Brown
(f)

New York
New York
New York
New York
New York
New York

Adams
Smith
Adams
Smith
Adams
Smith

25
25
25
25
25
25

New York
ChicagoNew York
ChicagoNew York
Chicago(g)

Figure 9-7 Relational algebra, (a) Relation R. (b) Relation S. (c) Relation R u S. (d) Relation
R - S. (e) Relation SEL(name = ADAMs>(R)- (f) Relation PROJ3>1(R). (g) Relation R x S.

4 The converse of a select operation is known as a projection. In aprojection, certain columns are chosen from an original relation to form a new
relation, care being taken as usual to eliminate any row duplications that may
result. The order in which the columns appear in the projected relation may bealtered as part of the project operation. Figure 9-7f contains a relation
PROJECT3>1(R) obtained by taking column 3 followed by column 1 from theoriginal relation R. The deletion of the second attribute eliminates the distinc­tion between the first two tuples of R; a single tuple (New York, Adams) thus
replaces the two original tuples in the projected relation. Project operations areuseful to break down large complex relations into several smaller and simpler
ones.
5 The Cartesian product R x S of two relations R and S is a new relationconsisting of all possible unique tuples obtained by taking a tuple from R fol­
lowed by a tuple from S. The length of the rows in R x S is equal to the sum of
the length of tuples in R plus the length of tuples in S. Relation R x S is shownin Fig. 9-7g. Unless duplicate tuples are generated, the number of rows inDATA MANAGEMENT SYSTEMS

369

R x S is equal to the product of the number of tuples in R and S. The Cartesian
product operation can be used to construct a single large relation from two or
more smaller ones.
The five basic operations of the relational algebra can be used to generate
additional operations that may be useful. Thus the intersection of two relations
R (T S is defined as R - (R - S); that is, it consists of all tuples in R that are not
only in R. Of particular interest is the join operation in which a single relation isformed from two initially given relations based on certain conditions of equality
or inequality among the attribute values included in the relations. Two types ofjoin operators may be distinguished known as the natural (or unrestricted) join
and the restricted (Conditional) join. Both of these operations are effectively
special cases of the Cartesian product operation, and they are used to constructlarger relations from smaller ones.
The restricted join is a product operation where conditions are imposed on
the values of attributes from the original relations. The notation T JOIN V
used in Fig. 9-8f implies that the joined relation consists of the tuples which
result by taking a tuple from relation T followed by a tuple from relation V withthe added condition that the value of attribute B in relation T be smaller thanthe value of attribute D in relation V. A restricted join is then equivalent to a
Cartesian product followed by a select operation. The restricted join is illus­
trated in Fig. 9-8f for the relations T and V shown in Figs. 9-8d and e. The firsttuple in the joined relation (1,2,3,3,1) is obtained by juxtaposing the first tuple
c

D

A

B

c

D

1
1
4
1

2
2
5
2

3
3
6
6

1
3
2
2

3

1

6

2

3

3

D

E

A

B

C

D

E

3
6
3

1
2
3

1
1
1
4
1
1
1

2
2
2
5
2
2
2

3
3
3
6
6
6
6

3
6
3
6
3
6
3

1
2
3
2
1
2
3

(f)
Join operations, (a) Relation T. (b) Relation U. (c) Natural join (unrestricted)
T JOIN U. (d) Relation T. (e) Relation V. (f) Relation join T JOIN V.
Figure 9-8

370

CHAPTER 9

from T and the first tuple from V [(1,2,3) and (3,1), respectively]. In that case,the value of attribute B in relation T (2) is clearly smaller than the value of at­tribute D in V (3).
For the unrestricted or natural join, the assumption is that certain attrib­
utes in the relations to be joined cover the same domain of values, that is, cer­tain columns in the two relations represent values for the same attribute. Such asituation exists for relations T and U of Fig. 9-8a and b where attribute C isrepeated in both relations. The unrestricted join is then similar to the restrictedjoin except that the join condition is assumed to be the equality of the compo­
nents for the columns representing identical attributes. For the example ofFig. 9-8 the operation T JOIN U is then equivalent to the restricted join
T JOIN U . In addition one copy of each duplicated column resulting from thejoin operation is eliminated in the natural join. In the example of Fig. 9-8c only
one copy of column C is maintained instead of the two produced by the normal
join operation.
The natural join is used when items are wanted for which the components
are initially stored in different relations. Thus given the relational data basescheme of Fig. 9-6, a natural join of relations 1 and 2 produces a list of employ­
ees together with the corresponding managers. Similarly a natural join of rela­tions 2 and 3 produces a list of managers followed by the corresponding em­
ployee numbers, project numbers and project names.
Sample retrieval operations using the relational model are examined laterin this chapter.
*D The Hierarchical Data Base Model

The relational data base model is conceptually very simple, because each file isrepresented by a table with homogeneous rows consisting of a specified numberof attribute values. To obtain answers to information requests, a great deal ofwork may, however, become necessary to manipulate the relations, including,for example, the previously mentioned join and Cartesian product operations.
In addition, large relations may have to be maintained in which certain attributevalues are repeated many times. This last solution reduces the number ofneeded join operations but entails substantially increased storage costs. Thusby maintaining a single relation consisting of the list of managers together withthe corresponding employee names one avoids the join between relations 1 and
2 of Fig. 9-6. In the large, single relation, the name of the manager is repeatedonce for each corresponding employee.
The choice between operational complexity and increased storage cost in­herent in the relational model may be avoided by complicating the storage
structures through the introduction of pointers connecting different types ofrecords. In the hierarchical model the assumption is that a natural hierarchy isdefinable where a large number of narrow entities can conveniently be related
to a small number of broader entities, that are in turn relatable to still broader
entities, and so on, until a single global entity remains at the top of the hierar­chy. For example, individual citizens live in cities that are grouped into coun-

371

DATA MANAGEMENT SYSTEMS

ties which in turn are located in states, and so on. A typical hierarchical ar­
rangement of record types is shown in Fig. 9-9a. When a many-to-one
relationship exists between a given type of record (record type) A and a second
record type B, the records of type A are considered hierarchically inferior tothose of type B. Hence in the hierarchical arrangement type A would be listed
below type B .
In the example of Fig. 9-9, the assumption is made that each postal region
contains many post offices each of which in turn serves as a center for many
postmen; furthermore each postman services many postal patrons. In the ac­tual file arrangement a hierarchically superior entity can be stored together withall the inferior entities to which it is related. This is suggested in the illustrationof Fig. 9-9b. One possible physical implementation for such a system is thepointer chain of Fig. 9-9c, where the record for postman A points to (gives theaddress of) the record of patron a, which in turn points to the next patron ser­

ial

(c)
(b)

Figure 9-9 Hierarchical data base system, (a) Hierarchical arrangem ent of record types, (b)Many-to-one relationship between record types, (c) Pointer chain arrangement.

3 72

CHAPTER 9

viced by the same postman (patron b), and so on, down to the last patron,
whose record then points back to postman A to complete the chain.
Obviously such an arrangement makes it easy to retrieve the set of postal
patrons corresponding to a given postman. More generally, in the hierarchicaldata base system the file structure is accessed in a top-down manner by startingat the top of the hierarchy and proceeding downward in the tree structure until
all desired items are found.
When a tree structure is usable to represent the relationships between rec­ord types in a natural way, a hierarchical data base system affords an efficient
implementation of the search and retrieval problem. Unfortunately, hierarchies
appear restrictive in many situations. Consider, for example, the data base of
Fig. 9-6 used earlier as an example. If one assumes that each manager handles
many projects and many employees, one obtains the structure shown in Fig.
9-10a. The structure of Fig. 9-10a makes it difficult to relate employees andprojects. If one were interested in the set of employees assigned to the various
projects, one could create a second set of employee records placed below the
project information, as shown in Fig. 9-10b. In that case, some of the employee
information would be duplicated in the file system.
Suppose now that some employees are assigned to many projects. In thatcase, a many-to-one relation exists between projects and managers as well as
between projects and employees, corresponding to the structure of Fig. 9-10c.
Such a structure is not allowed in a hierarchy because the PROJECT records
now have two hierarchically superior record types. This can be avoided by cre­ating a second tree to be added to the tree of Fig. 9-10b. Such a tree is shown in
Fig. 9-10d. The combination of the two trees of Fig. 9-10b and d is now usable
to represent all the necessary relationships for the original data base of Fig. 9-6.
For obvious reasons a solution which consists in the use of several partly over­lapping hierarchies is not ideal, because a great deal of the stored informationmust be duplicated and jumps are necessary from one tree to another to gain
access to appropriate portions of the data base.
Much duplication in the stored data can be avoided by introducing addi­
tional pointer systems to be used together with the normal physical pointers.
Consider, for example, the tree structure of Fig. 9-10a, and assume that it be­comes necessary to add data indicating that some employees are assigned tomany projects. In other words, the projects records are considered to be hierar­
chically inferior not only to the manager records but also to the employee rec­ords. This could be done by adding as a new tree the structure of Fig. 9-10d
necessitating the duplication of certain project as well as certain employee in­formation. The duplication can, however, be avoided by using a new set of socalled logical pointers connecting employees to the projects to which they are
assigned. The PROJECT file then becomes a logical child (logically inferior) to
the logically superior employee file. This is shown in Fig. 9-1 la, where the logi­
cal pointers are symbolized by dashed connections.
The logical pointer system effectively introduces nonhierarchical relation­
ships into the data base system without abandoning the basic hierarchical struc-

DATA MANAGEMENT SYSTEMS

373

(a)

(b)

One

Many

(c)

(d)

Figure 9-10 Relationships between record types, (a) Sample hierarchical structure for database of Fig. 9-6. (b) Altered structure accounting for many-one relation between employees
and projects, (c) Hypothetical relationship between record types, (d) Structure reflecting as­signment of employees to many projects.

ture. In the example of Fig. 9-1 lb the dual pointer system provides two kinds ofsiblings for the PROJECT file: the physical siblings consisting of sets ofprojects directed by the same manager, and the logical siblings consisting of
projects to which a given employee is assigned in common. An example of thissituation is shown in Fig. 9-lib , where projects a, b, and c are physical siblings
since they are all managed by the same manager, whereas projects a and d are
logical siblings because employee 1 is assigned to both projects.
One more problem must be mentioned concerning the representation of
many-to-many relationships between types of records. It was seen earlier thatthe normal hierarchical arrangement accommodates only many-to-one and oneto-one relationships. Many-to-many relationships do occur in many situations,and provisions must be made for them in an effective data base system. Con-CHAPTER 9

374

MANAGERPROJECT NUMBER

PROJECT NAMEEMPLOYEE NUMBERS ALAR Y

EMPLOYEE NAME

ADDRESS

DEPT NUMBER

Logical pointers fromlogical child to logical parent
(a)

(b)

Figure 9-11 Logical pointer structure, (a) Hierarchical data base with logical pointer ar­
rangement. (b) Pointer arrangement illustrating physical and logical connections.

sider again the sample data base of Fig. 9-10b, where the many-to-one relation­
ship between employees and projects is represented by physical pointers. If thelogical pointers already used in Fig. 9-1 la to relate the PROJECT and EM­
PLOYEE records were added to the structure of Fig. 9-10b, a method would be
provided to represent the many-to-many relationship between projects and em­
ployees. In that case, the many-to-many relationship is replaced by two manyto-one relationships, one of them being implemented by logical pointers asshown in Fig. 9-12a.
An alternative, more direct way for implementing many-to-many relation­
ships between two record types consists in creating a third record type repre­
senting the intersection between the two original types of records. The manyto-many relationship can then be represented by conventional many-to-one
pointers between each of the original record types and the newly defined inter­
section records. For the example under discussion, the intersection records
could specify the percentage of time each employee spends on a particular
project. The logical structure of the resulting data base is shown in Fig. 9-12b

375

DATA MANAGEMENT SYSTEMS

(a)

(c)

Figure 9-12 Im plem entation of many-to-many relationships in hierarchical systems, (a) Im­
plem entation of many-to-many relationship using logical pointers, (b) Use of intersection rec­ords. (c) Sample data base fo r structure of part b.

where TIME records are used to represent the intersection. A short example,
showing the pointer structure used for two projects and three employees, is in­cluded in Fig. 9-12c.
The use of logical in addition to physical (hierarchical) pointers and of in­tersection record types adapts the hierarchical data base model to most pro­cessing requirements. The usefulness of the hierarchical structure is not dimin­
ished by the alterations because the hierarchy always controls the record
access. Specifically, each record is stored together with its descendants (theother records to which it is related by a many-to-one relationship), and eachdescendant is stored in turn with its own descendants. Access to the tree struc­ture is obtainable by using the records located at the root of the tree, that is, atthe top of the tree in the illustrations. For the hierarchy shown in Fig. 9-9a,
access must be obtained by first looking at the file of postal regions, which inturn gives access to certain post office records from where one can get to indi­vidual postmen or postal employee records. An example of an access imple­
mentation is shown in Fig. 9-13.
In the illustration of Fig. 9-13 an index is provided to access the records
constituting the root, that is, the records of type A. The descendants of eachparticular record of type A, say a(, are then stored sequentially after ^ in tree
accessing order. The accessing order used in the example of Fig. 9-13 is known

376

CHAPTER 9

as “preorder,” where the root is listed first for each subtree, followed by theleftmost child which is in turn followed by its leftmost child if there is one.
When no further children are available, the next sibling to the right of the mostrecent child is taken up, and so on until the tree is exhausted. For the subtree
starting at the root record a10, the preorder list contains in order a10-b1-b2-d1-d2C j-C 2 .

To find a particular record in the tree the index is first consulted to find aparticular record among the root records. From there the pointers are followed
to the corresponding list of child records. This list is then scanned until thewanted record is found. Since the number of child records may be variable, andthe initial ordered arrangement may change as records are added and deleted, it
is prudent to provide overflow storage in addition to the primary storage area
for the lists of records. Records that do not fit into the primary area are thenpushed into the overflow area, which is connected to the primary storage by
pointers as shown in Fig. 9-13c.
The access arrangement illustrated in Fig. 9-13 is known as the hierarchicalindexed sequential access method (HISAM). It is used in the well-known Infor­
mation Management System (IMS) implemented by IBM [16,26,27]. In the
HISAM access method, immediate access is obtained only to certain records ofthe root of the tree; the remaining records are then located by a sequential scan­ning process. A faster (but more expensive) accessing method consists in pro­viding pointers to access the individual descendants of each root record. This isdone in the hierarchical direct access method (HIDAM). In the HIDAM organi­zation, individual pointers would thus connect each pair of adjacent records in

Figure 9-13 Typical hierarchical indexed sequential access method (HISAM). (a) Basicstructure, (b) Sample data base, (c) Indexed sequential storage arrangement.

DATA MANAGEMENT SYSTEMS

377

the access path (for example, in the data base of Fig. 9-13 from a10to bx, from bx
to b2, from b2 to dx, and so on). A hashing method could also be used to accessthe records located at the root of the tree instead of the special index shown in
Fig. 9-13. In that case, one obtains a direct hierarchical access system(HDAM). Because the popular IMS data management system is based on hier­archical data structures, the hierarchical model has been widely accepted as abasis for data base operations.
*E The Network Data Base Model

The network data base model has been intensively studied over many years andhas been sanctioned by official groups charged with the standardization of auto­mated data processing activities [28-30]. More specifically, a special group of
experts known as the Data Base Task Group (DBTG) was set up some years
ago by the Conference on Data Systems Languages (CODASYL) in order tostudy and propose standards for data base processing. Since the parent CODA­SYL committee had earlier been responsible for the development of the wellknown Common Business Oriented Language (COBOL), the DBTG eventually
proposed a model for data base management, known as the DBTG proposal,
which is designed to operate with COBOL. The DBTG proposal uses a network
data structure and has served as the basis for the design of several network database systems; the IDS/II system designed by Honeywell Information Systems
is a typical example [31].
The underlying idea behind both the hierarchical and the network database models is the need for easy manipulation of different types of records. The
pointer systems are designed to make it easy to “travel” from a particular rec­ord occurrence to the set of related records. It was seen earlier that the princi­
pal relationship between different record types used in the hierarchical model
was a many-to-one correspondence between a set of records of some particular
type and a single record of some other type. The simple many-to-one relation­
ship also forms the basis for the network model, but in that model the allowable
patterns of many-to-one relations are more flexible than in the hierarchicalcase. For example, in a network model, several different many-to-one relation­
ships can be defined from a single record type, say, A, to various other record
types B, C, D, etc. The structure of Fig. 9-10c that is disallowed in the hierar­
chical model is specifically permitted in a network implementation. On theother hand, the direct use of many-to-many relationships is still prohibited be­cause of the resulting complications in the pointer structures. Intersection rec­ord types may again be used for the substitution of many-to-one relationships
for the original many-to-many relationship, as explained earlier.
The greater complexity of the allowable relationships in the network model
simplifies the navigation in the data base, that is, the movement from one rec­ord type to another as required to generate answers to certain queries. On theother hand, the file access becomes more complicated. Consider, as an exam­
ple, a set of suppliers of certain goods, and a set of clients that order thesegoods. A many-to-many relationship is definable between the supplier records

378

CHAPTER 9

and the goods records because one supplier may furnish many different items,
while a single item may be obtained from several suppliers. Analogously, amany-to-many relationship also exists between the client records and the goods
records because once again a client buys many items while one item may bebought by many clients. This situation is represented schematically in Fig. 914a.
Since the many-to-many relationships are not directly representable, two
new record types can be introduced: the first one, labeled “ quantity,” provides
the quantity of a certain item ordered by a particular client; and the second,
known as “price,” can state the price for an item obtained from a particularsupplier. Using the three basic record types and the two intersection record
types, the two many-to-many relationships of Fig. 9-14a are now replaceable byfour many-to-one relationships as shown in Fig. 9-14b.
The structure of Fig. 9-14b is obviously not a hierarchy and could nottherefore be directly used in a hierarchical system. In a hierarchical system it
would be necessary to break up the structure into several trees following dupli­
cation of the intersection records. In a network system, a direct implementa­tion is possible by using, for example, pointer chains of the kind shown in Fig.
9-9c to represent the many-to-one relationships. In the terminology used by the
Data Base Task Group, the set of records included in a particular pointer chain,consisting of a particular single record of type A and of the number of related
records of type B, is known as a “data base set.” (The term “ set” as used here
is not to be confused with the conventional mathematical meaning of that
term.) The single record of type A to which the other records in a data base set
are related is a member of the owner type of records, the other records of type
B are included in the member record type. In Fig. 9-14b, the intersection record
types (that is, quantity and price) are “member” types, whereas clients, goods,
and suppliers are “ owner” types.
A typical implementation using pointer chains to represent the data basesets is shown in Fig. 9-14c for the earlier example of Fig. 9-14b. It is easy to seethat the pointer chains can be followed from any particular record to any otherrelated record. However, the structure is substantially more complicated than acomparable hierarchical implementation. To avoid errors in a search, it is nec­
essary to control the traversal process when using the overlapping pointerstructures. In the DBTG proposal this is done by means of so-called currency
pointers which identify the last record of each record type that was accessed ateach particular point, as well as the last accessed record in each data base set.
A detailed evaluation of the effectiveness and efficiency of the various database models is not possible at present. Some general remarks may suffice. The
relational system appears superior from the viewpoint of the casual user. Onlya single construct must be understood, and that construct consists of simple
tables. Furthermore, high-level languages are available to manipulate thetables. For small data base problems, the relational model appears obviously
preferable.
On the other hand, as the data base grows in size, the efficiency of the pro-

DATA MANAGEMENT SYSTEMS

379

Many-to-many

Many-to-many
(a)

(b)

(c)

Figure 9-14 Netw ork data base im plem entation, (a) Two many-to-many relationships, (b)Four many-to-one relationships for data base of part a. (c) Pointer chain im plem entation for
relationships of part b.

CHAPTER 9

380

cessing operations becomes important. In that case, the explicit relationship in­
dicators (pointers) or the use of separate indexes affording access to various
groups of records may become essential. In particular, in the hierarchical andnetwork systems, the pointers allow direct access to sets of related records,
whereas in the relational system these relationships and the corresponding ac­
cess paths may first have to be established before they can be used. Unfortu­
nately, the pointer structures and the implementation of complex many-tomany relationships between record types are more difficult to deal with than asimple table; as a result a substantial burden is placed on the programming staff
charged with setting up the data base system.
At the present time, most commercial applications are based on the hierar­
chical or network data base models. The conceptually simpler relational modelhas, however, been studied intensively in recent years, and various theoreticaladvantages have been claimed for that model [32], Furthermore the slow se­quential scan of all the records included in a given relation may be avoided byproviding auxiliary indexes that offer access to groups of related records. Be­
cause of its greater conceptual simplicity and ease of use, one may expect thatthe relational model will become solidly established as a tool for data base ma­nipulations in the visible future.
3 QUERY PROCESSING*A

Query Language Types

A great deal of work has been devoted to the construction of data base querylanguages. Since data base systems are designed for use by business-oriented
persons rather than by computer experts, a main consideration is user friendli­
ness and transparency of the operations. In particular, great importance is at­tached to the use of high-level query languages which reflect the overall user’s
intent rather than the computer operations that may be required to obtain any
particular result. Unhappily, the use of high-level query languages entails agood deal of extra work in transforming the user statements into programs ac­
ceptable by the computer. Furthermore, the efficiency of the programs result­ing from such a transformation may leave something to be desired. A tradeoff
thus exists between the use of low-level programming-type query statementsthat may be hard to formulate but lead to efficient search and retrieval specifi­
cations, and the use of high-level user-friendly query formulations that may
lead to slower, more expensive retrieval processes.
The query languages used in data base environments must provide formore processing alternatives that those commonly used in bibliographic re­trieval. Whereas the latter need only specify how to retrieve documents, a
DBMS query language also permits the user to ask for calculations on thestored numerical data and for the retrieval of computed information derived
from the originally stored data. In principle, it might be useful to provide thefull scope of the unrestricted natural language for the formulation of data basequeries. For reasons outlined earlier, a natural language analysis system is still

DATA MANAGEMENT SYSTEMS

381

too complex and expensive for use in most commercial applications. However,restricted natural language features are being included in some data base querylanguages, as will be seen [33-39],
In some situations, the problem of whether a high-level (user-friendly) or alow-level (programming-type) query language is to be used never arises. Only avery high-level querying capability can, for example, serve in a department
store to provide information to masses of untrained customers about the loca­
tion of various kinds of merchandise. In principle, a game of “twenty ques­
tions” might be played by confronting the customers with question sequencesin the hope of eventually leading them to the desired information. Specifically,
as each question is proposed, the user provides a yes/no answer which thentriggers the next query. A typical query sequence of this kind is shown in Table
9-3.
Since it is difficult to design efficient sequences of simple yes/no queries
that will lead to correct final responses in a small number of steps, a faster pro­
cess is the so-called menu approach, where the user is confronted with an enu­
meration of different available alternatives. The choice of a particular alterna­
tive will then lead to a further display containing a more refined list of
possibilities. Eventually, the user obtains the desired information without fur­ther question. The menu approach serves as a basis for the operation of certain
electronic news services where news items are displayed at individual user sta­tions to specific customers upon demand [40].
A typical menu display suitable for a department store information system
is illustrated in Fig. 9-15. In that case, the user first chooses item 3 (women’swear) from the number of alternatives offered, followed in the next display
frame by item 4 (shoes), eventually leading to a response locating the shoe de­partment on floor 2 section C. It should be pointed out that while the menu ap­
proach may rapidly lead to a final answer, the system is not foolproof. In fact,users may find it difficult to make a proper choice among the offered alterna­
tives; and once the wrong path is followed, all subsequent displays in the cur­rent sequence will be unhelpful. Consider, for example, a user interested in
fluids used to wash automobiles. This user might decide to follow the sequence
Table 9-3

Sample Query Sequence
Query

User response

Purchase item?

Yes/noClothing?

Yes/noAppliances?

Yes/noKitchen appliances?

Yes/noMajor kitchen appliancessuch as stoves, dishwashers?
Answer: Floor 5 Section B ,Yes/no

/

/
J

J

/

382

CHAPTER 9

Figure 9-15

Menu display suitable for department store inquiry system.

starting with automobile supplies only to find later that cleaning agents wereactually classified under household rather than automobile supplies. The designof transparent classification systems leading to unambiguous menu sequences
is not a task that is currently well understood.
The menu approach is most successful when it is used by people who may
be expert in a particular subject area without, however, being knowledgeable incomputer processing. In that case the kind of erroneous choice previously illus­
trated can be avoided and proper responses may be obtained without training
the users in the formulation of queries or the search methodologies. Typicalexamples that come to mind are populations of medical doctors where the re­trieval system might furnish diagnostic aids based on menu displays of symp­
tom lists. Alternatively, the menu system could be used by lawyers for statuteor case law searching, by chemists dealing with the properties of chemical com­pounds, and by other professional groups operating in restricted topic areas
with a well-defined terminology.
The use of tabular querying methods is related to menu querying but pro­vides somewhat greater flexibility in the permissible query formulations and in
the specification of processing sequences. In that case an electronic question­
naire properly filled in and submitted through the automatic display equipment
replaces the normal query formulation process. A sample tabular query is con­tained in Table 9-4 for a data base dealing with hazardous chemicals. The user
in this case is interested in the chemical names and the manufacturers of toxic
Table 9-4 Sample Tabular Query
Property or
specification
CHEMICAL FORMLETHAL DOSE FOR 50%
PRODUCTION
1, 2
4, 3
CHEMICAL NAMECOMPANY NAMECOMPANY ADDRESS

Relation
>
>
AND
AND

Value

OutputGAS
10 PARTS/MILLION
1000 KG/YEAR

Operation
number
1
2
3
4
5

PRINT
PRINT
PRINT

DATA MANAGEMENT SYSTEMS

383

gases for which the lethal dose to 50 percent of the exposed population is atleast 10 parts per million and the production is at least 1,000 kilograms per year.
In the formulation of Table 9-4 the three basic requirements (that is, the chemi­
cal form, the lethal dose, and the production amount) are effectively “anded”
together to produce the final query.
The well-known Query-by-Example (QBE) system is a commercial tabular
querying system specially adapted to the relational data base model [41]. In
QBE, a relation (file) to be operated upon during the search process must firstbe displayed in raw form on the user console by drawing a table showing therelation name at the head of column 1 and the attribute names identifying that
relation as heads of subsequent columns. A typical frame for the display of agiven relation is shown in Table 9-5. In a real case, the first row of the table
would be automatically filled in with the correct relation and attribute names.
To operate on a displayed relation, the user fills in the various columns of
the table with appropriate instructions and values of attributes. In QBE, twokinds of values are distinguished: those taken literally, where the value shownis directly used as an operand, and those used as samples to designate unknown
values of corresponding attributes. In the examples that follow, sample values
are underlined, whereas actual values are written without underline.
To retrieve the name and employee numbers for all records contained in
the EMPLOYEES file, one first requests a display of the EMPLOYEES rela­tion and then fills in the attribute columns corresponding to employee name andnumber with the command PRINT (P.) followed by a dummy value. The resultis shown in Table 9-6a. When the query formulation involves more than one
relation, the frames for all required relations must be displayed, and the rela­tionships between the values of corresponding attributes must be appropriately
specified. Consider as an example, the query formulation shown in Table 9-6b.
This display involves the EMPLOYEES and the MANAGER relations. The
first part of Table 9-6b is identical to Table 9-6a. The second part qualifies thenames of the employees actually wanted to those whose manager is “ Smith.”
Relation

A ttrib u te specifications mentioned
in queries

Table 9-5

Display of relation framework in the query-by-example system.

CHAPTER 9384

EMPLOYEES

EMP. NUMBER

EMP. NAME

P. 123

P. BROOKSS ALAR Y

ADDRESS

DEPT. NUMBERS ALAR Y

ADDRESS

DEPT. NUMBER

ADDRESS

DEPT. NUMBER(a)

EMPLOYEESMANAGER

EMP. NUMBER

EMP. NAME

P. 123

P. BROOKSEMP. NUMBER

MANAGER NAME

123

SMITH

(b)

EMPLOYEES

EMP. NUMBER

P. 123

EMP. NAMES ALAR Y

SMITH

X

P. BROOKS

> X

(c)

Table 9-6 Query-by-example query formulations, (a) Print the names and numbers of all em­
ployees. (b) Print the names and numbers of all employees whose manager is Smith, (c) Print
the names and numbers of employees whose salary exceeds Smith’s.

Note that the name “ Smith” is to be taken literally which accounts for the lackof underlining in the table. In Table 9-6b, the same dummy employee number(namely, 123) is used in the EMPLOYEES and the MANAGER relations toindicate that the employee names to be retrieved are precisely those managed
by “ Smith.” Relationships between attribute values other than equality can be
specified by using appropriate quantifiers as shown in the example of Table
9-6c, where the request covers the names and numbers of all employees whosesalary is at least as large as some unknown value x, x being specified as Smith’ssalary. Even though the QBE system can be used to formulate queries of sub­stantial complexity, the basic features can be mastered rapidly by untrainedusers.
In addition to the table languages, several higher-level query languages
have been proposed in which English keywords are used to specify the role offiles and attributes. The SEQUEL language is a typical example which is also
designed to operate in a relational framework [42,43]. The basic construct in
SEQUEL is the SELECT-FROM-WHERE specification, where the SELECTDATA MANAGEMENT SYSTEMS

385

part specifies the attributes actually wanted, the FROM portion identifies therelation in which these attributes occur, and the WHERE clause introduces anexpression characterizing the attribute values previously named. In manycases, a SEQUEL formulation can be immediately understood without further
clarification or instruction. Thus the formulation
SELECT EMP. NAME, EMP. NUMBERFROM
EMPLOYEESWHERE SALARY > 10,000
AND
DEPT = 123
requests names and numbers of employees included in the EMPLOYEE rela­tion such that the value of the SALARY attribute equals at least 10,000 and the
DEPARTMENT is specified as department 123.
Attributes from several relations can be used by nesting the SELECTFROM-WHERE clauses. In particular, the expression following the WHERE
statement can itself introduce a new relation. Thus, the names of employees
whose manager is SMITH may be requested in the following way:
SELECT EMP. NAME, EMP. NUMBERFROM
EMPLOYEESWHERE EMP. NUMBER IS IN
SELECT EMP. NUMBER
FROMMANAGER
WHERE MANAGER NAME = ‘SMITH’
The keywords “IS IN ” introduce a second relation, which restricts the valuesof the employee numbers to only those managed by Smith.
A language such as SEQUEL uses linguistic constructs for query specifi­
cation. The English words are, however, used in a specialized sense with un­
ambiguous syntactic and semantic properties. Higher-level query languages
also exist in which the English-like specifications are replaced by mathematicalformulas. The so-called relational calculus is a case in point, where the wanted
records are identified by a given variable name, and a mathematical expression
involving the variable is then used to characterize the records actually wanted[44], Thus, if the variable t is used to identify the records under consideration,
and R and S are names of relations, the specification {t | R(t) v S(t)} requests
the retrieval of all records that are contained either in relation R or in relation S.
In addition to the higher-level nonprocedural languages, it is of course also
possible to use lower-level programming-type languages where the actual pro­cedures needed to carry out the retrieval operations are directly specified. The
relational algebra previously introduced in Fig. 9-7 is an example where join,
project, and select operations correspond directly to particular relational oper­
ations. For example, given two relations containing attributes A and B and at­tributes C and D, respectively, the following expression in the relational alge-

386

CHAPTER 9

bra is used to obtain the values of attribute A for all the records for which thevalue of attribute B in the first relation equals the value of attribute C in thesecond, and the value of attribute D is “ Smith.”
PROJECTa(SELECT b=cand d=‘sm!tH’(AB x CD))

(1)

Assuming that the two relations are the previously used EMPLOYEES andMANAGER relations, and the four attributes A, B, C, D correspond, respec­tively, to employee names, employee numbers, employee numbers, and man­ager names, the query of expression (1) once again requests the names of all
employees whose manager is “ Smith.” The difference between the procedural
formulation of expression (1) and the previous formulations is the direct opera­
tional specification of expression (1), consisting in this case of a Cartesian prod­
uct joining the two relations, followed by a selection, which is followed in turnby a projection.
In some operational environments, several different query facilities areprovided to serve different user classes. This is the case, for example, in the
Laboratory Animal Data Bank available through the National Library of Medi­cine which is searchable by experimental scientists with a menu approach or by
information professionals with programming knowledge using a programmingtype query language [45,46]. The idea is that the information professionals
charged with operating the system will find it worthwhile to study the file struc­ture and the relationships between attributes in order to be able to propose effi­
cient query formulations. On the other hand, the file search itself constitutes
only an incidental part of the activities for the experimental scientist. In thatcase there is no immediate need to learn the command structure of the retrieval
system or the file organization actually used to store the characteristics of labo­
ratory animals.
The use of a high-level nonprocedural query manipulation language is par­ticularly important in management information systems and decision support
systems where few users have programming knowledge [47-49], In such situa­
tions English-like query languages are often considered to be essential because
the user is then removed from the details of the processing system to the great­
est possible extent. The same motivation lies behind the work in natural lan­
guage query formulations in some question-answering environments.
*B

Processing Strategies

All the data base query languages mentioned earlier contain features for pro­cessing, summarizing, maintaining, and updating the stored information files in
addition to the formulation of actual user queries. The following types of opera­
tions are particularly important:
1 File modification commands such as insert, delete, and modify
2 Arithmetic capabilities such as addition and subtraction
3 Assignment and print commands used to assign new or computed

DATA MANAGEMENT SYSTEMS

387

values to the attributes of certain records and to print out information con­tained in the records
4 Aggregate operations used to obtain global values for the records
stored in a given file, including average, sum, maximum, and minimum values
When the files to be processed are small and the contents remain static
over long periods of time, the search and updating processes are not of muchconsequence. In that case, a sequential scan through the whole file might beused to process each stored record sequentially in order to carry out the neces­sary operations. Unfortunately, in most real situations the files are neither
static nor small. As the number of records becomes larger, the number of terms
needed to identify these records will also grow, and a sequential scan that pro­
cesses all records sequentially one at a time becomes too slow and too costly
for practical use. Typically, indexes are then created which can be used to iso­late certain portions of the file without touching the remainder of the stored in­formation. An inverted index similar to that introduced earlier for bibliographic
records can then be used to identify all the records containing particular valuesof certain attributes. The corresponding records can also be retrieved rapidly ifthey are clustered, that is, stored contiguously in the main file.
As the number of terms used to identify the stored records or the numberof clusters used to partition the collection grows, the single index can in turn be
broken down into a hierarchy of indexes including successively fewer entries.
The highest-level index is then used to provide access to a more detailed lowerlevel index which gives access in turn to still more detailed indexes, until intime some of the records stored in the main data file are eventually identified.
This is the method used in the cluster tree search where successively smallergroupings of records are determined until at the end a few records included in acommon low-level centroid are obtained.
The hierarchy of indexes and the main records file must be searched andmaintained efficiently under addition, deletion, and modification of the con­tents. When related records are connected by pointers, additions and deletions
can be handled by simple changes in the pointer arrangements as shown in Fig.
9-16a and b respectively. Eventually as more and more local changes are madea complete reorganization of the storage area becomes necessary. Such a reor­
ganization will “ compact” the space by storing in adjacent positions items that
actually belong together and by plugging the holes left by deleted records.
File reorganizations may involve alterations at the conceptual level that re­quire changes in the file schema. This is the case when the hierarchical or net­
work arrangement is altered or when changes are made to the attribute lists that
identify certain record types. Alternatively changes may be made at the physi­
cal level, for example, by creating a new level of indexing, or by changing theaccessing method used to retrieve the records from storage. In either case, thefile reorganization can be carried out by copying the data base to auxiliary stor­
age and performing the necessary modifications off-line. Eventually the cor­rected version is then reloaded into the main store following the updating oper-CHAPTER 9

388

(a)

(b)
Figure 9-16 Pointer changes used for record addition and deletion, (a) Addition of record j
between record i and record (i + I), (b) Deletion of record j from chain.

ation. Alternatively, the corrections can be performed in place, while otheroperations proceed normally. In that case, it becomes necessary to block ac­
cess to portions of the data base while the revisions are carried out. While spe­cial methods have been devised that minimize the difficulties inherent in database updating and maintenance, any reorganization may be expected to require
substantial resources especially when the size of the data base is large [50,51].
In addition to the file organization and file modification processes, atten­
tion must also be paid to the efficiency of the search and retrieval operations. A
good deal is known about the tradeoffs involved, for example, in creating andmaintaining an auxiliary index compared with the larger search cost incurred
when an index is not available. Unfortunately, it is not possible in the present
context to examine these efficiency problems in detail. Some observations re­lating to the search process used for the relational data base model will sufficefor present purposes [52-54],
The basic problem in query optimization consists in determining a reason­
able order for executing the operations necessary to retrieve the stored records
in response to a particular query formulation. The term “reasonable” implies
that the grossest inefficiencies should be eliminated whenever possible. The op­
timization problem is of special importance for relational data base queries be­cause the easy access paths provided by the pointer structures between records
are not always available in that system. In fact, unless special precautions aretaken, typical query language expressions may produce very inefficient pro­cessing sequences in a relational environment.
Consider, as an example, the query formulation of expression (1) involving
two relations consisting of employee name and employee number (attributes A
and B) on the one hand, and employee number and manager name (attributes C
and D) on the other. The first operation specified in expression (i) is the Carte­sian product (AB x CD). This involves a single scan of the first relation; how-

DATA MANAGEMENT SYSTEMS

389

ever, for each record in relation 1, all records in the second relation must be
scanned to generate the single relation involving the four attributes ABCD. As­
suming that the number of records in the two relations is nAB and nCD, respec­tively, the number of records that need to be scanned is thus equal tonAB(l + nCD). Obviously the generation of a Cartesian product such as the one
specified in expression (1) is expensive for large relations.
More generally, it is obvious that relational operations designed to gen­erate large relations from smaller ones should be avoided, whereas on the con­trary the transformation of large relations into small ones should be preferred.
This implies that Cartesian products as well as joins and relational union opera­
tions should be replaced whenever possible by select, project, or relational in­tersection; in any case, the expensive operations should be delayed in the hopeof reducing the scope of these operations.
It turns out that for the query of expression (1), the product operation is
totally unnecessary. Indeed only the attribute values corresponding to certain
employee numbers are to be retrieved in that case, rather than the complete setof records involving all attributes. More specifically, the following transforma­tions are possible for the query formulation of expression (1):1 Since the selection operation [SELECTd=.smith.(AB x CD)] involves
only the records in the second relation, the SELECT operation can be migrated
inside the product, thereby obtaining a reduced query specification as follows:
PROJECTa(SELECTb=c(AB x SELECTd=.smith.CD))(2)

The Cartesian product is now much less costly, since only a few of the CD rec­ords (those corresponding to manager Smith) are involved.
2 The condition SELECTB=c which follows the Cartesian product con­verts that product into a natural join operation between AB and the selectedrecords from CD. The new query statement thus becomes
PROJECTa ( a B JOIN (SELECTd=.smith,CD))
\

B=C

(3)

/

Various methods can be used to execute the join operation. A multiple
scan of the relations is always possible: typically for each element (record) ofrelation 1 it is necessary to scan the second relation in order to find all possible
elements that meet the join conditions. This requires as many complete scansof relation 2 as there are elements in relation 1. The multiple scanning can be
avoided by constructing an index for the attributes of the second relation thatare needed in the join operation. When an index is available, the elements ofrelation 2 corresponding to each element in relation 1 are immediately identi­
fied without further scanning. Another possibility consists in sorting the two
relations according to the values of the attributes needed in the join prior to theactual joining operation. This makes it possible to carry out the join operation

390

CHAPTER 9

by performing a single scan of both relations. Assuming that relation 1 has nentries and relation 1 has m entries, the multiple scan requires n x m file ac­cess operations. If the two relations were sorted and then merged, the numberof operations will be n log n and m log m for the sorting, and m + n for the final
merging. A comparison of n x m with n log n + m log m + n + m shows thatthe latter is preferable except when the file sizes are trivially small.
Whether it is worthwhile to construct an index on the join attributes or tosort the relations prior to joining depends on the size of the relations, the diffi­
culty of the indexing or sorting operations, the size of the internal memory usedin the system under consideration, and the frequency with which a given join
operation must be carried out.
The following general optimization rules are useful under most operational
conditions:
1 Perform all selection operations as early as possible since the effect is areduction in the size of the relations.
2 Preprocess the files before performing a join by creating an index on thejoin attributes, or by sorting where indicated.
3 Assemble sequences of selections or sequences of projection opera­
tions into a single selection or a single projection; a sequence of these opera­
tions can be executed in a single scan of the relation.
4 Combine projection operations with other binary operations involving
several relations to decrease the number of attributes that need to be pro­
cessed.
5 Combine selection operations with a prior Cartesian product to gen­erate a join, a natural join being generally less expensive to perform than a Car­tesian product.
A substantial effort has been devoted to the optimization of the query pro­cessing function in some of the modern relational data base systems [32,52—
54]. The alternative hierarchical and network systems which provide fast ac­cess paths for the most important record combinations may nevertheless be
preferred to an optimized relational system in many circumstances.
4

DATA QUALITY

A

Integrity and Security

The preservation of data correctness is considered of great important in many
data base environments. Several sources of errors are of interest: the acciden­
tal introduction of incorrect data resulting from clerical input errors or from
common programming errors, and the malicious modification of information.
The problem of data base protection takes on two main aspects: the security oraccess control mechanism which is designed to ensure that users will accessonly that portion of the data base which they are actually entitled to see, andthe preservation of data integrity, which is designed to protect the data fromnonmalicious errors such as the introduction of attribute values that are seman-

DATA MANAGEMENT SYSTEMS

391

tically inconsistent (such as EMPLOYEE AGE = 139), or the use of duplicate
key values for different records.
The security problem is normally attacked by assigning to each user apassword designed to identify all legitimate users for access purposes. The
passwords are presumed to be known only to individual users and to the systemitself. In addition to the compulsory use of passwords before obtaining systemaccess, each user is expected to identify those portions of the data base that are
actually needed for each particular application. This may be done by introduc­
ing a separate subschema for each user in which all system objects required bythat particular user are properly defined. The assignment of particular systemobjects to particular users implies that users receive their own view of the database. Furthermore by restricting the individual users to their own user views—
for example, managers to the records covering their own department only—
the data objects may be protected from involuntary misuse to some extent. In
particular, programming errors which force users to access portions of the database for which they have no use can then be easily detected.
Certain physical protection mechanisms also exist, including especiallydata encryption methods designed to transform the data into a form whichcannot be recognized by unauthorized persons. Encryption methods can beused prior to storing the data to ensure that the contents of a data base will not
be revealed to unauthorized users. On the other hand, encrypted files may bedifficult to sort and to access by means of standard index files.
Methods may also be available which provide authorization to individual
users to perform certain operations. In the query-by-example system, users
may be individually authorized to perform specific operations on particular files(relations), including insertion (I.), deletion (D.), updating (U.), and printing(P.). Tabular displays similar to those shown in Table 9-6 can be used to specify
the necessary authorizations. The first sample authorization of Table 9-7 allows
any user to read records for employees whose salary does not reach 10,000. In
Table 9-7b, a specific person (J. Doe) is authorized to update the salary of a
specific record.
The available security mechanisms may be expected to prevent many erro­
neous alterations of the data base. On the other hand, no currently available
security device will permanently foil a persistent transgressor with sufficient
imagination and know-how [55-57].
An important aspect of data base preservation is the preservation of data
integrity. In many situations restrictions can be placed on the characteristics orvalues of certain attributes that must be observed if the data environment is toappear “ sensible.” For example, the value of currently used postal zip codes in
the United States is less than 100,000 and greater than 00600; the length of em­
ployee names is less than 30 characters; and the age of active employees is lessthan 100. Integrity constraints of many kinds can be declared in advance to be
enforced by the system at convenient points in time. A given constraint may,for example, be verified each time an affected record is updated, or each time
the record is accessed.

CHAPTER 9392

EMPLOYEESAUTRIP.) BROOKSEMP. NUMBER

EMP. NAMES ALAR Y

123

SMITH

< 10,000

EMP. NUMBER

EMP. NAMES ALAR Y

123

SMITH

10,000(a)

EMPLOYEESA U TR IU .) J. DOE(b)Table 9-7 Authorization mechanism in query-by-example, (a) Authorization for anyone toread employee names and numbers provided salary is less than 10,000. (b) Authorization for
J. Doe to update the salary of employee Smith.

In the QBE system, integrity constraints are declared by means of tabular
displays similar to those used for authorizations. An example is shown in Table
9-8, which specifies that during record insertion and updating, the salary figure
for any employee must necessarily amount to at least $5,000.
In addition to using direct integrity constraints declared for specific record
attributes, the integrity of the data may also depend on preserving certain im­
plied relationships between attributes. A good deal of attention has been de­voted in recent years to the development of a data base design theory based on
the use of attribute relationships. This design theory is most developed for the
relational data base model, and depends in large measure on the specification
and use of dependencies of various kinds between attributes. The most impor­tant dependency type is the functional dependency, which guarantees that thevalues of certain attributes are identical for different records under the assump­tion that the values of certain other attributes are also the same. Formally one
says that attribute B functionally depends on attribute A (or A functionally de­termines B) if no two records can have a different value for attribute B, assum­
ing that the value is identical for attribute A. Functional dependency may bedenoted by drawing an arrow from the determining toward the functionally de­pendent element, that is, A —» B. It is clear that if an attribute is a candidate
key for a given relation, then necessarily the other attributes will be function­
ally dependent on that key.
Consider, as an example, a STUDENT relation whose relational scheme is(STUDENT NAME, STUDENT ADDRESS, COURSE, GRADE). If the stu­
dent names are all distinct, then the names may function as a key. It is thenclear that
STUDENT NAMESTUDENT ADDRESS

since the same student cannot have two different addresses. Similarly the com­bination of the student name and the course number in which the student is393

DATA MANAGEMENT SYSTEMS

EMP. NUMBER

EMPLOYEES

EMP. NAMECONSTRO.U.)

Table 9-8

S ALAR Y> = 5,000

Integrity declaration in query-by-example.

enrolled will determine a unique grade
STUDENT NAME, COURSE

GRADE

The functional dependencies, once determined, can be used directly for in­tegrity checking by verifying that all dependencies are valid at all times. In ad­
dition; the dependencies are useful for the generation and use of relations innormalized form. The normalization process is generally carried out by decom­
posing each relation into component parts that are conceptually simpler thanthe original. The simpler normalized form is attractive because certain difficul­
ties that may arise for nonnormalized relations as a result of data insertion ordeletion are absent for the normalized case [58-60].
Consider, as an example, the STUDENT file introduced earlier. Because
the values of all attributes must be specified for each record in the relationalmodel, it is impossible to enter into the file the names and addresses of students
who are not enrolled in a course. Alternatively, the names of students who drop
their only course are also lost. If the basic STUDENT relation were replacedby two smaller relations called NAME FILE and GRADE RECORD, respec­tively, the update problems mentioned earlier would not exist. Specifically if
the two new relations are defined as
NAME FILE(STUDENT NAME, STUDENT ADDRESS)GRADE RECORD(STUDENT NAME, COURSE, GRADE)
the original relation can be reconstructed and the names of unenrolled students
are preserved.
Three principal normal forms are described in the literature, known, re­spectively, as the first, second, and third normal forms (INF, 2NF, and 3 NF).
The first normal form characterizes a relation in which each component of eachrecord is not further decomposable; that is, each attribute represents a nondecomposable entity. The relation used as an example in Table 9-2 is certainly in
INF, assuming that the components of the address attribute (for example, thestreet number) are not meaningful by themselves.
A relation is in 2NF if it is in INF and if every attribute that is not a key isfully dependent on each key attribute. That is, the so-called partial dependen­cies are disallowed where a given attribute is dependent on a portion of a key
attribute. In the relation R identified by the scheme R(CITY, STREET, ZIP)the combination of (STREET, ZIP) is a key, but one actually observes that the394

CHAPTER 9

zip code by itself determines the city (although not vice versa). Hence the func­
tional dependency
ZIP -»> CITY
represents a partial dependency on a key attribute.
A relation is in 3NF if it is in 2NF and no nontrivial transitive dependencies
are present. A transitive dependency between attributes A, B, and C implies
that A -» B and B -*■ C, but B -/* A. (The latter condition is needed because if
A -* B and B -» A, then attributes A and B would be equivalent and the transi­
tivity property would become trivial.) For the previously used STUDENT rela­tion one observes
STUDENT, COURSE -* STUDENTSTUDENT—» ADDRESSSTUDENT-b STUDENT, COURSE(4)Hence the relation is certainly not in 3NF. Assuming that the combination(STUDENT, COURSE) is used as a key, the relation is also not in 2NF be­
cause of the partial dependency STUDENT -*■ ADDRESS. Update anomalies
can occur for nonnormalized relations, as previously illustrated for the STU­
DENT relation. This accounts for the interest in normalization and relational
decomposition.
The decomposition of relations into component parts would not be useful if
methods were not available for reconstructing the original by rejoining the com­ponents without loss of information. A so-called lossless join decomposition ofrelations is possible under well-defined conditions. In particular, it is known
that any relation has a lossless join decomposition into third normal form pre­serving all the original dependencies between attributes [20]. For example, therelation R(STUDENT, ADDRESS, COURSE, GRADE) has a lossless pair de­composition into RjfSTUDENT, ADDRESS) and R2(STUDENT, COURSE,
GRADE) because R may be recovered by the unrestricted join Rt JOIN R2
using the equivalence of the student names as a join condition.
Substantial advances are continually being made in the development ofdata base theories, for example through the introduction of new normal forms
such as the fourth or Boyce-Codd normal form (BCNF) and the use of new
types of dependencies between attributes such as the so-called multivalued de­pendencies [61]. One may expect that these theoretical activities will substan­tially affect the design characteristics of the data management systems in the
future.
**B

Concurrent Data Base Operations

It has been implicit in the foregoing exposition that the programs used to accessthe data base operate independently of each other and that provisions are madefor preventing interference between activities that may take place concur-

DATA MANAGEMENT SYSTEMS

395

rently. In most data base environments the concurrent execution of manytransactions (processes) is the rule rather than the exception. For example, anautomated airline reservations system simultaneously receives hundreds of dif­ferent inquiries all of which must be answered by consulting the same database. The main interference problem does not of course arise from reading thedata because in that case the integrity of the data is not normally compromised.
Problems do, however, arise when modifications are made to the stored infor­
mation in a multiuser environment. In the airline reservations system, methods
must thus be available to prevent the simultaneous sale by different agents ofthe same airplane seat to different prospective passengers.
The basic methodology used to prevent interference between different
transactions consists in applying a locking mechanism to a specific portion of
the data base before a given transaction is to introduce modifications to thedata. The lock is used to prevent other transactions from accessing the samedata until the lock is removed. A transaction involving a lock mechanism thus
consists of five basic steps:
Locking a portion of the data baseReading the original data
Modifying the data
Writing the modified data
Unlocking the data base1

A special lock manager serves in most data base systems to assign and record
all existing locks, and to prevent access to locked portions of the data base[62- 64].
When a locking mechanism is used to control access, special care must be
taken to avoid undesirable side effects. Assuming, for example, that severaltransactions are waiting to access a given locked portion of the data base, thenext transaction to be given access following release of the lock must not bechosen arbitrarily because some transactions could then be made to wait for­ever. Such a condition, known as “livelock,” can be avoided, for example, by
providing access on a first-come first-served basis.
A possibly more serious situation arises when two or more transactions aredeadlocked because they each demand access to data locked by other transac­
tions. The following order of operations leads to a deadlock situation:
1
2
3
4

Transaction 1 : lock data base A
Transaction 2 : lock data base B
Transaction 1 : request lock on data base B
Transaction 2 : request lock on data base A

In this example, the first two steps are carried out normally because different
portions of the data base are affected by the locking requests for the two trans­
actions. At step 3, transaction 1 is asked to wait because transaction 2 currently

396

CHAPTER 9

holds a lock on data base B. At step 4, transaction 2 will similarly come to rest
because another lock has already been placed on data base A. From this pointon, both transactions will obviously wait forever.
Various solutions are available for preventing deadlock. For example,
each transaction may be asked to request all the needed locks at the same time,at which point either the locks are all granted simultaneously or they are all
rejected. Alternatively, the locks affecting a particular set of data bases may all
have to be placed in some particular preestablished order. For example, if database A necessarily precedes data base B in the established order, then the lock
requests for transaction 2 are not admissible. Instead of preventing deadlock,the system can simply detect deadlock, and later roll back some of the transac­
tions involved and cancel their effect on the data base. Rollback and recovery
methods are mentioned later in this chapter. In general, rollback is less satisfac­
tory than deadlock prevention because some users may then be forced toreenter a transaction that had already been started.
Even when livelock and deadlock operations are successfully avoided, theconcurrent execution of different processes may still lead to unwanted interfer­
ence problems. In effect the concurrent transactions must be interleaved insuch a way that the end effect is the same as if the transactions were executed
separately and independently of each other. The latter condition is known as“ serializability.” In situations where several data base transactions can be exe­
cuted concurrently, a scheduler included in the data base system is charged
with the resolution of potential conflicts between transactions. More specifi­
cally, the scheduler imposes a protocol on each transaction restricting the se­quences of steps that a transaction may execute. Assuming that the establishedprotocols are followed by all transactions, the scheduler will then produce a
serializable schedule.
One kind of protocol which is known to guarantee serializability is the twophase locking protocol which specifies that for each transaction all locking op­
erations must precede all unlocking operations. The two-phase protocol may
lead to deadlock; however, assuming that deadlock prevention methods arealso used, the two-phase requirement will allow the scheduler to produce a pro­cessing order that is equivalent to that of a serial schedule. In a serial schedule,
the transactions are completely independent of each other.
An example of a serial schedule is shown in Table 9-9a, where all the oper­
ations for transaction 2 precede those for transaction 1. A serializable, but notserial, schedule is shown for the same operations in Table 9-9b. It may be seenthat for each transaction all locking operations precede all unlocking opera­
tions. However, the schedule of Table 9-9b is equivalent to the serial scheduleof Table 9-9a where all of transaction 2 precedes all of transaction 1. A nonserializable schedule for the transactions is given in Table 9-9c. In the example
of Table 9-9c, the locks on data base B cannot be placed in such a way that
operation 6 of transaction 1 may precede operation 7 of transaction 2. The ef­
fect of transaction 2 on data base B is in fact lost in the schedule of Table 9-9c,
because the old values for data base B are read at step 6 in Table 9-9c, whereas

DATA MANAGEMENT SYSTEMS

Table 9-9397

Illustration of Two-Phase Locking Protocol

Transaction 1
aTransaction 2

Serial schedule for two transactions
1. Read data base A
2. Perform operations on A
3. W rite m odified A
4. Read data base B
5. Perform operations on B
6. W rite m odified B

7. Read data base B
8. Perform operations on B
9. Write m odified B
10. Read data base C
11. M odify C
12. W rite m odified CbSerializable schedule for two transactions

1. |L o c k C[
2. | Lock A,B |3. Read data base C
4. Read data base B
5. Operate on C
6. Operate on B
7. W rite m odified C
8. W rite m odified B
9. |U n lock B|
10. | Lock b |11. Read data base B
12. Read data base A
13. Operate on B
14. Operate on A
15. Write m odified B
16. W rite m odified A
17. | Unlock B,C |18. |U nlock A |cNonserializable schedule for two transactions

1. Read data base C
2. Read data base B
3. M odify C
4. M odify data base B
5. W rite data base C
6. Read data base B
7. W rite data base B
8. Modify B
9. Read data base A
10. W rite m odified B
11. M odify A
12. W rite data base A

CHAPTER 9398

the new modified values are read at that point by transaction 1 in Table 9-9a
and b.
**C

Restart and Recovery Methods

It was seen earlier that deadlock conditions can be eliminated by “rollingback” or undoing certain transactions and letting others proceed normally. To
be able to go back in time and reverse the effect of certain transactions, it isnecessary to store information regarding the effect on the data base of the vari­
ous operations, and the order in which these operations are executed. The nor­mal method used for this purpose consists in maintaining ajournal or log which
records all the operations that may have to be undone or repeated in case oftrouble [65]. In particular, whenever an item in the data base is updated, in­serted, or deleted, a record describing the particular modification is added to
the log. When the system malfunctions, or crashes, for one reason or another,
the log can be consulted and the data base can be restored by rolling back thesystem to a consistent state existing at some point prior to the malfunction.
From that point on the various operations can then be repeated.
In general, the information in the log is used to undo the effect of transac­
tions that had affected the state of the data base prior to the crash. On the other
hand, incomplete transactions whose results had not yet been recorded in thedata base can be ignored during rollback and may simply be repeated when arestart of operations is ordered.
To limit the amount of information in the log that needs to be consulted
during the recovery process, it is customary to keep periodic summaries of thestate of the data base in the form of backup copies and journal checkpoints. A
backup copy of the data base is a complete copy produced at infrequent inter­vals representing a consistent data base state. Typically a backup copy might
be produced once a day. When all else fails, the backup copy can be read in andall operations may be resumed at that point. A journal checkpoint represents asummary of the state of the transactions at a given point in time. The check­point information consists of lists of active transactions together with appropri­ate status information for each transaction. Checkpoint information is recordedin the log with reasonable frequency. When a crash occurs, each entry in thelog is analyzed back to the last previous checkpoint to determine its effect. In
addition the checkpoint information identifies transactions that need to be un­done and/or repeated.
To simplify the restart and recovery operations it is customary to recog­
nize a commit point for each transaction when the transaction must be regarded
as being completed. This implies that all operations included in the transaction
are terminated and the results have been entered in the log. If a crash occurs
following commitment, the effects will survive the crash, even though the
newly altered information may not yet have been entered into the data base.
The log specifically distinguishes committed from uncommitted transactions.
Commitment of a transaction should be reflected to users who must know when

DATA MANAGEMENT SYSTEMS

399

they can safely assume that the transaction need not be reentered in case oflater trouble. Until the commit point is reached, a transaction can always beaborted by canceling or backing out of the transaction.
A so-called two-phase commit policy, not to be confused with the twophase locking protocol is often followed which minimizes the problems inher­
ent in crash recovery. Two main rules are followed:
1 No transaction can actually write into a data base before it has com­mitted.
2 No transaction can commit before all its effects on the items in the database have been entered into the log.
Assuming that the two-phase locking protocol is used in addition to this commit
policy, and that unlocking operations occur only following commitment, it be­comes impossible for any transaction to read values in the data base provided
by uncommitted transactions.
When the two-phase commit policy is followed, uncommitted transactions
may simply be disregarded in a crash situation because these transactions could
certainly not have affected the data. On the other hand, committed transactions
must be redone following the rollback operation. When the two-phase commit
or some equivalent policy is not used, the recovery process is much more diffi­
cult because uncommitted transactions might then have changed the data baseand other transactions might have read values written by these uncommitted
transactions. The original changes to the data base introduced by the uncom­
mitted transactions must then be undone, and so must the transactions that hadread values from these transactions. This effect can propagate indefinitely andrender the recovery process impossible to carry out in an effective manner.
Even when an appropriate commit policy is used to distinguish transactions
that must participate in the recovery process from others that can be ignored,
any crash recovery procedure is costly to implement and requires substantial
system resources.
**D

Distributed Data Bases

The assumption has been made up to this point that the data base under consid­
eration is centrally managed, although of course the users might be geographi­
cally dispersed and various transactions might be executed concurrently. In ac­tual fact many systems exist involving several different computers and anumber of different data bases located in a variety of different places. In such a
circumstance one speaks of a distributed data base system. Possibly the bestknown operating distributed data base system is the worldwide airline reserva­
tions system: each participating airline uses its own data base located near its
particular headquarters location; common protocols are, however, used which
control the operations when information involving more than one data base isneeded to answer a given query [66-70].

400

CHAPTER 9

The usefulness of distributed data base operations has become increas­
ingly obvious because of the popularity of the many small minicomputer sys­tems. These systems can obviously be used to control local data bases and to
perform operations of interest in local environments. Furthermore, when data
are needed that are not locally available, the local computers can address re­quests to a network of other machines and other data bases located in various
remote places.
A distributed data base environment complicates the systems organizationand the resulting data base operations. A decision must first be made about theallocation of the files to the various locations, or nodes, of the data base net­
work. A particular file could be kept in some unique, central place; alterna­
tively it could be partitioned by allocating the various file portions to several
different nodes. Finally, the file or certain file portions could be replicated bystoring copies in several places. The use of partitioned files may reduce thenumber of messages and requests circulating from node to node assuming thatthe file portions of interest at a particular site are locally stored. When the data
files are replicated, the message traffic between nodes may be substantially re­duced. In fact, a tradeoff exists between the extra storage used by the data rep­
lication and the increased speed of operations resulting from the reduced com­munications load between the nodes.
In a distributed data base system the need for the basic physical and logical
data independence is expanded to include also location and replica transpar­ency. Location transparency implies that the user programs are independent of
the particular location of the files, while replica transparency extends the trans­parency to the use of an arbitrary number of copies.
Once a particular file environment is created, procedures must be available
for executing the various transactions and furnishing results to the requesting
parties. A given transaction might be run locally; alternatively, various remote
points might be asked to carry out the operations followed by the routing of
responses to the originating points. The latter strategy involves a good deal ofoverhead in handling the message queues that may be formed at various points
in the network
It goes without saying that all operations must be carried out in a distrib­
uted environment in such a way that data integrity and consistency are main­tained. This implies that special locking and update strategies must be used toensure that all copies of a given data base are properly updated. Specifically, allfiles must be locked before updating, the locks must be held until the end of agiven transaction, and file alterations must be broadcast through the network to
all replicas before the end of the transaction. Special transaction commit poli­cies have been invented for this purpose in distributed systems. Specifically, atransaction coordinator is named for each transaction, and the coordinatoralone is empowered to commit a given transaction after querying the participat­
ing sites concerning their individual readiness to commit.
It is obvious from what has been said that the distributed data base en­
vironment creates a host of complications. Because of the current widespread

DATA MANAGEMENT SYSTEMS

401

use of computer networks and the increasing availability of on-line access tocomputational facilities by a wide range of users, the organization and opera­
tions of distributed data base systems have become popular areas of investiga­
tion for researchers in the computer field.

5 SUMMARY

The questions of interest in data base management coincide to a large extent
with those arising in all information retrieval environments: they involve themanagement of interactive multiuser systems including efficient accessing,search, and retrieval procedures, and user-friendly query formulation and out­
put display methods. By restricting the information to be processed in database management to well-defined, homogeneous entities, characterized by asmall number of unambiguous attribute values, the indexing and content-anal­
ysis problems met in other retrieval environments are avoided. The emphasis isplaced instead on the processing of mixed queries often involving partly nu­
meric data whose values need to be compared or manipulated arithmetically
before answers can be generated to the available queries. High-level proce­dures and languages may then be available in a data base management systemfor defining, organizing, processing and accessing the structured data. In addi­tion, a data base system normally maintains data quality and security, and en­sures that the user programs are insulated from the details of the logical andphysical system implementation.
The strength of the data management area is the wide applicability in manydifferent user environments, and the large number of utilities and system re­sources that are often furnished, including crash protection, deadlock detec­tion, automatic construction of secondary indexes and hashing systems, integ­
rity checks, access authorization management, and transaction concurrency
and distributed data facilities. The weaknesses of the existing systems arise
from the small number of well-defined operations that are implemented effi­
ciently often at the expense of complicating operations that do not fit the stan­
dard model. Efficient access paths are normally provided for programs that use
the available data structures, pointer systems, and record grouping propertiesof the files. When the existing facilities are not suited to the given processing
requirements, the execution of the operations becomes cumbersome and timeconsuming. In the relational system tradeoffs exist between the use of decom­
posed relations in normalized form where the integrity and correctness of thedata are easily ensured, and the extra work involved in rejoining the normalized
relations when necessary.
One may expect that increasing efforts will be made in the immediate fu­
ture to eliminate some of the restrictions inherent in existing data management
implementations. Eventually, the existing data base operations may be con­verted into truly flexible decision support and question-answering environ­ments.

402

CHAPTER 9

REFERENCES[1] R. N . Landau, J. W anger, and M . C. Berger, D irectory o f Online D atabases, V ol. 1,
N o . 3, Cuadra A sso cia tes, Santa M onica, California, Spring 1980, p. 72.
[2] C. Mader and R. Hagin, Information System s: T ech n ology, E con om ics, A pplica­
tions, S cien ce R esearch A sso cia tes, C hicago, Illinois, 1974.
[3] I. B enbasat and R. G oldstein, D ata B ase S ystem s for Sm all B u sin ess : M iracle or
Mirage, D ata B a se, V o l..9, N o . 1, Summ er 1977, pp. 5 - 8 .
[4] J. P. Fry and E. H . Sib ley, E volution o f D ata-B ase M anagem ent S ystem s, C om put­ing Surveys, V ol. 8, N o . 1, March 1976, pp. 7 -4 2 .
[5] R. A shany and M . A dam ow icz, D ata B ase S ystem s, IBM S y stem s Journal, V ol. 15,
N o . 3, 1976, pp. 2 5 3 -2 6 3 .
[6] W .M . Zani, Blueprint for M IS, Harvard B u sin ess R eview , V ol. 48, N o v e m b e r -D e cem ber 1970, pp. 9 5 -1 0 0 .
[7] G. B . D avis, M anagem ent Inform ation System s: C onceptual Foundations, Struc­ture and D evelopm ent, M cGraw-Hill B ook C om pany, N e w Y ork, 1974.
[8] J. C. E m ery, A n O verview o f M anagem ent Information S y stem s, D ata B a se, V ol.
5, N o . 2 - 4 , D ecem ber 1973, pp. 1 -1 1 .
[9] S. L. A lter, H o w E ffective M anagers U se Information S y stem s, Harvard B u sin ess
R eview , V ol. 54, N o v em b er-D ecem b er 1976, pp. 9 7 -1 0 4 .
[10] E . D . C arlson, J. L . B ennett, G. M . G iddings, and P. E . M antey, T he D esign and
Evaluation o f an Interactive G eo-D ata A nalysis and D isplay S ystem , Information
P rocessing ’74, N orth Holland Publishing Com pany, A m sterdam , 1974, pp. 10 5 7 1061.
[11] P. Berger and F. E delm an, IRIS: A Transaction B ased D S S for Hum an R esources
M anagem ent, D ata B a se, V ol. 8, N o . 3, W inter 1977, pp. 2 2 -2 9 .
[12] R. D avis, A D S S for D iagnosis and Therapy, D a ta B a se , V o l. 8 , N o . 3, W inter 1977,
pp. 5 8 -7 2 .
[13] C. F. Starmer and R. A . R osati, A D S S for M anaging Patients with a C hoice Illn ess,
D a ta B a se , V ol. 8, N o . 3, W inter 1977, pp. 5 1 -5 7 .
[14] E. R. M cL ean and T. R iesing, MAPP: A D SS for Financial Planning, Data B a se,
V ol. 8, N o . 3, W inter 1977, pp. 9 -1 4 .
[15] R. L. K laas, A D S S for Airline M anagem ent, D ata B a se, V ol. 8, N o . 3, W inter1977, pp. 3 - 8 .
[16] C. J. D ate, An Introduction to D ata B ase S ystem s, 3rd E dition, A ddison W esley
Publishing C om pany, Reading, M assachusetts, 1981.
[17] D . C. T sichritzis and F . H . L o ch o v sk y , D ata B ase M anagem ent S ystem s, A ca ­dem ic P ress, N e w Y ork, 1977.
[18] G. W iederhold, D atabase D esign , M cGraw-H ill B ook C om pany, N e w Y ork, 1977.
[19] D . K roenke, D atabase Processing: F undam entals, M odeling, A pplications, S cien ce
R esearch A sso cia tes In c., C hicago, Illin ois, 1977.
[20] J. D . U llm an, Principles o f D ata B ase S y stem s, Computer S cien ce Press, Potom ac,
Maryland, 1980.
[21] C. T. M eadow , A nalysis o f Inform ation S ystem s, 2nd E dition, John W iley andSon s, N e w Y ork, 1973.
[22] M . E. Senko, D ata Structures and D ata A ccessin g in D ata B a se System s: P ast, Pre­sent, Future, IBM S ystem s Journal, V ol. 16, N o . 3, 1977, pp. 2 0 8 -2 5 7 .
[23] M. E. Sen k o, Inform ation System s: R ecords, R elations, S ets, Entities and T hings,
Information S y stem s, V ol. 1, 1975, pp. 3 -1 3 .

DATA MANAGEMENT SYSTEMS

403[24] D . D . C ham berlin, Relational D ata-B ase M anagement S y stem s, Computing Sur­v e y s, V ol. 8, N o . 1, M arch 1976, pp. 4 3 -6 6 .
[25] E . F . C odd, A R elational M odel o f D ata for Large Shared D ata B anks, ACM C om ­m unications, V ol. 13, N o . 6, June 1970, pp. 37 7 -3 8 7 .
[26] IBM Corporation, Information M anagem ent S y stem — General Information M an­ual, IBM R eport G H 20-1260, W hite Plains, N e w Y ork, 1975.
[27] W . C. M cG ee, T he Information M anagem ent System IM S /V S , IBM S ystem s Jour­nal, V ol. 16, N o . 2, 1977, pp. 8 4 -1 6 8 .
[28] R. W . Taylor and R. L. Frank, C O D A S Y L D ata-B ase M anagem ent S ystem s, ACM
Computing S u rv ey s, V ol. 8, N o . 1, M arch 1976, pp. 6 7 -1 0 3 .
[29] C O D A SY L , D atabase T ask Group R eport, A ssociation for Computing M achinery,N e w Y ork, April 1971.
[30] T. W. O lle, T he C odasyl Approach to D ata B ase M anagem ent, John W iley andS o n s, N ew Y ork, 1978.
[31] C. W . B achm an, On a G eneralized Language for File Organization and M anipu­
lation, C om m unications o f the A C M , V ol. 9, N o . 3, March 1966, pp. 22 5 -2 2 6 .
[32] M. M . A strahan, M . W. B lasgen, D . D . Chamberlin, K . P. Esw aran, J. N . Gray, P.
P. Griffiths, W . F . K ing, R. A . L orie, P. R. M cJones, J. W . M ehl, G. R. P utzolu, I.
L. Traiger, B . W . W ade, and V . W atson, S ystem R: A R elational A pproach to D a­tabase M anagem ent, ACM Transactions on D atabase S y stem s, V ol. 1, N o . 2, June
1976, pp. 9 7 -1 3 7 .
[33] L. R. Harris, U ser Oriented Database Query with the ROBOT Natural Lan­guage Query System , International Journal o f M an-M achine Studies, V ol. 9, 1977,
pp. 6 9 7 -7 1 3 .
[34] D . L. W altz, A n E nglish Language Q uestion A nsw ering System for a Large R ela­tional D atabase, C om m unications o f the A CM , V ol. 21, N o . 7, July 1978, pp. 5 2 6 539.
[35] E. F. C odd, R. S., Arnold, J. M . C adiou, C. L. Chang, and N . R ou ssop ou los, R en­d ezvou s V ersion 1: A n Experim ental English-Language Query Form ulation System
for Casual U sers o f Relational D ata B a ses, IBM R esearch R eport RJ 2144, IBM R e­
search Laboratory, San Jose, California, January 1978.
[36] G. G. H endrix, E. D . Sacerdoti, D . Sagalow icz, and J. Slocu m , D eveloping a N a tu ­ral Language Interface to C om plex D ata, ACM T ransactions on D atabase S ystem s,
V ol. 3, N o . 2, June 1978, pp. 105-147.
[37] P. D ell ’O reo, V . N . Spadavecchia, and M . King, U sin g K n ow led ge o f a D ata B ase
W orld in Interpreting Natural Language Q ueries, Information P rocessing 77, N orthHolland Publishing C om pany, A m sterdam , 1977, pp. 139-144.
[38] J. M ylop ou los, P. A . Bernstein, and H . K . T. W ong, A Language F acility for D e ­signing D atabase-Intensive A pplications, ACM T ransactions on D atabase S ystem s,
V ol. 5, N o . 2, June 1980, pp. 185-207.
[39] S. C. Shapiro and S. C. K w asn y, Interactive C onsulting via Natural Language,
C om m unications o f the A CM , V ol. 18, N o . 8, A ugust 1975, pp. 45 9 -4 6 2 .
[40] J. Martyn, Prestel and Public Libraries: A n L A /A slib E xperim ent, A slib P roceed­
ings, V ol. 31, N o . 5, M ay 1979, pp. 2 1 6 -2 3 6 .
[41] M. M. Z loof, Q uery-by-Exam ple: A D atabase Language, IB M S ystem s Journal,
V ol. 16, N o . 4, 1977, pp. 3 2 4 -3 4 3 .
[42] D . D . C ham berlin, M . M . Astrahan, K . P. Esw aran, P. P. Griffiths, R. A . L orie, J.
W . M ehl, T. R eim er, and B. W. W ade, Sequel 2: A U nified Approach to D ata D efi­
nition, M anipulation and Control, IBM Journal o f R esearch and D evelopm ent, V ol.
20, N o . 6, N ovem b er 1976, pp. 5 6 0 -5 7 5 .

404

C H A P T E R

9[43] D . D . Chamberlin and R. F. B o y c e , SE Q U E L : A Structured E nglish Query L an­guage, Proceedings o f ACM SIG FID E T W orkshop, A nn Arbor, M ichigan, M ay
1974, pp. 2 4 9 -2 6 4 .
[44] E. F. C odd, R elational C om pleteness o f D atabase Sublanguages, in Proceedings o f
ACM /SIG M O D C onference on D ata M od els, R. R ustin, editor, A ssociation for
Computing M achinery, N e w Y ork, 1974, pp. 6 4 -9 8 .
[45] N ational Library o f M edicine, Instructions to the Laboratory Anim al D ata Bank,
M emorandum to L A D B U sers, B eth esd a, Maryland, January 14, 1980.
[46] N ational Library o f M edicine, Laboratory Animal D ata B ank— Fact S h eet, B e­
thesda, M aryland, A ugust 1980.
[47] K . D . E ason , U nderstanding the N a iv e Computer U ser, T he Computer Journal,
V ol. 19, N o . 1, February 1976, pp. 3 - 7 .
[48] T. P. Gerrity, Jr., D esign o f M an-M achine D ecision Support System s: A n A pplica­tion to Portfolio M anagem ent, Sloan M anagem ent R ev iew , V ol. 12, N o . 3, W inter1971, pp. 5 9 -7 5 .
[49] H . T. G ibson, D eterm ining U ser In volvem en t, Journal o f S ystem s M anagem ent,
A ugust 1977, pp. 2 0 -2 2 .
[50] N . C. Shu, B. C. H o u sel, R. W . T aylor, S. P. G hosh, and V . Y . Lum , Express: A
D ata E xtraction, P rocessing and Restructuring S ystem , A C M Transactions on D a­tabase S ystem s, V ol. 2, N o . 2, June 1977, pp. 134-174.
[51] G. H . Sockut and R . P. Goldberg, D atabase R eorganization— Principles and Prac­tice, ACM C om puting Surveys, V ol. 11, N o . 4, D ecem ber 1979, pp. 37 1 -3 9 5 .
[52] P. A . V . H all, Optim ization o f Single E xpressions in a R elational D ata B ase S y s ­tem , IBM Journal o f R esearch and D evelop m en t, V ol. 20, N o . 3, M ay 1976, pp.
244-257.
[53] J. M. Smith and P. Y . Chang, Optim izing the Performance o f a Relational Algebra
D atabase Interface, C om m unications o f the A CM , V ol. 18, N o . 10, O ctober 1975,
pp. 568-579.
[54] S. B . Y ao, Optim ization of Query E valuation A lgorithm s, A CM T ransactions on
D atabase S y stem s, V ol. 4, N o . 2, June 1979, pp. 133-155.
[55] C. W ood, E. B. Fernandez, and R. C. Sum m ers, D ata B ase Security: Requirem ents
Policies and M od els, IBM S ystem s Journal, V ol. 19, N o . 2, 1980, pp. 22 9 -2 5 2 .
[56] R. Fagin, On an A uthorization M echanism , ACM T ransactions on D ata B ase S y s ­tem s, V ol. 3, N o . 3, Septem ber 1978, pp. 31 0 -3 1 9 .
[57] D . D . Chamberlin, J. N . Gray, and I. L. Traiger, V iew s, A uthorization and L ocking
in a R elational D ata B ase S ystem , Proceedings N ational Computer C onference
1975, A FIPS P ress, M ontvale, N e w Jersey, 1975, pp. 4 2 5 -4 3 0 .
[58] E. F . Codd, Further N orm alization o f the D atabase Relational M odel, in Pro­
ceedings A C M /SIG M O D C onference on D ata M odels, R. R ustin, editor, A sso c ia ­tion for C om puting M achinery, N e w Y ork, 1974, pp. 3 3 -6 3 .
[59] C. D elobel and R. O. C asey, D ecom p osition o f a D ata B a se and the Theory o f B o o ­lean Sw itching F unctions, IBM Journal o f R esearch and D evelop m en t, V ol. 17, N o .
5, Septem ber 1973, pp. 37 4 -3 8 6 .
[60] C. D elob el, N orm alization and H ierarchical D ependencies in the Relational D ata
M odel, ACM T ransactions on D ata B a se S y stem s, V o l. 3, N o . 3, Septem ber 1978,
pp. 201-222.
[61] R. Fagin, M ultivalued D ep endencies and a N e w N orm al Form for Relational D ata­b ases, IBM T ransactions on D ata B ase S y stem s, V ol. 2, N o . 3, Septem ber 1977,
pp. 262-278.

DATA MANAGEMENT SYSTEMS

405[62] D . D . Chamberlin, R. F. B o y ce, and I. L. Traiger, A D eadlock Free Schem e for
R esource L ocking in a D atabase E nvironm ent, Information P rocessing 74, N orthHolland Publishing Com pany, A m sterdam , 1974, pp. 3 4 0 -3 4 3 .
[63] K . P. E sw aran, J. N . Gray, R. A . L orie, and I. L. Traiger, The N otion s o f C on sis­ten cy and Predicate L o ck s in a D atabase S ystem , C om m unications o f the A C M ,V ol. 19, N o . 11, N ovem b er 1976, pp. 6 2 4 -6 3 3 .
[64] R. H . T hom as, A Majority C onsensus A pproach to C oncurrency Control for M ulti­
ple C opy D atab ases, ACM Transactions on D atabase S y stem s, V ol. 4, N o . 2, June
1979, pp. 180-209.
[65] J. S. M. V erhofstad, R ecovery T echniques for D atabase S y stem s, Computing Sur­v e y s, V ol. 10, N o . 2, June 1978, pp. 167-195.
[66] H . Lorin, D istributed Processing: A n A ssessm en t, IBM S ystem s Journal, V ol. 18,
N o . 4, 1979, pp. 58 2 -6 0 3 .
[67] A . L . Scherr, D istributed D ata P rocessin g, IBM S ystem s Journal, V ol. 17, N o . 4,
1978, pp. 3 2 4 -3 4 3 .
[68] J. N . Gray, N o tes on D atabase Operating S y stem s, Operating S y stem s— An A d­vanced C ourse, R. B ayer, R. M . Graham, and G. Segm uller, editors, Springer Verlag, N ew Y ork, 1978, pp. 39 3 -4 8 1 .
[69] J. B. R othnie Jr., P. A . B ernstein, S. F o x , N . G oodm an, M . Ham mer, T. A .
Landers, C. R eev e, D . W . Shipm an, and E . W ong, Introduction to a System forDistributed D atabases (SD D -1), ACM Transactions on D atabase S ystem s, V ol. 5,
N o . 1, March 1980, pp. 1 -1 7 .
[70] P. A . B ernstein, D . W . Shipman and J. B . R othnie, Jr., C oncurrency Control in a
System for Distributed D atabases (SD D -1), ACM Transactions on D atabase S y s­
tem s, V ol. 5, N o . 1, March 1980, pp. 18 -5 1 .

BIBLIOGRAPHIC REMARKS:At the present time the data base area is very active. New texts appear every
year, new journals are created regularly, and the literature is rapidly expand­ing. The following texts cover the theory and practice of data base management
systems:
D . K roenke, D atabase Processing: Fundam entals, M odeling, A pplications, S cien ce R e­
search A sso cia te s, In c., C hicago, Illinois, 1977.
C. J. D ate, A n Introduction to D ata B ase S ystem s, 3rd E dition, A ddison W esley Pub­lishing C o ., Reading, M assach u setts, 1981.
J. D . U llm an, Principles o f Data B ase S y stem s, Computer S cien ce Press, Potom ac,
M aryland, 1980.

The text by Date emphasizes the hierarchical database systems, whereas Ull­man examines mainly the relational systems.
The following texts deal largely with data structures and file accessmethods:
E. H orow itz and S. Sahni, Fundam entals o f D ata Structures, Computer S cien ce P ress,
W oodland H ills, California, 1976.
G. W iederhold, D atabase D esign, M cG raw-H ill B ook C om pany, N e w Y ork, 1977.

C H A P T E R

406

9Several review articles cover the history and the general context of database management systems including:
J. P. Fry and E . H . S ib ley, E volution o f D ata-B ase M anagem ent S ystem s, Computing
Surveys, V ol. 8, N o . 1, M arch 1976, pp. 7 -4 2 .
M. E . Senko, D ata Structures and D ata A ccessin g in D ata B ase S ystem s: P ast, Present,
Future, IBM S y stem s Journal, V o l. 16, N o . 3, 1977, pp. 2 0 8 -2 5 7 .
I. Benbasat and R. G oldstein, D ata B ase S ystem s for Small B u sin ess: Miracle or M irage,
D ata B ase, V ol. 9, N o . 1, Summer 1977, pp. 5 - 8 .

The latter is a nontechnical general review addressed to business managers.
The following articles provide an introduction to the conceptual data basemodels:E . F. Codd, A R elational M odel o f D ata for Large Shared D ata B anks, ACM C om m uni­
cations, V ol. 13, N o . 6, June 1970, pp. 37 7 -3 8 7.
R. W . Taylor and R. L. Frank, C O D A S Y L D ata B ase M anagem ent S ystem s, ACM
Computing S u rv ey s, V ol. 8, N o . 1, M arch 1976, pp. 6 7 -1 0 3 .
T. W. O lle, The C O D A S Y L A pproach to D ata B ase M anagem ent, John W iley and S o n s,
N e w Y ork, 1978.
D . D . Chamberlin, R elational D ata-B ase M anagem ent S y stem s, Computing S u rveys,
V ol. 8, N o . 1, M arch 1976, pp. 4 3 -6 6 .

Many journals contain material in the data base management area, includ­ing periodicals covering the practical aspects addressed to relatively nontechni­
cal audiences such as:
Computerworld
D ata B ase
Datamation
Harvard B u sin ess R eview

Additional more technical and theoretical material is contained in the following
journals:
ACM Transactions on D atabase S ystem s
IBM S ystem s Journal
Information S ystem s
Information T echnology: R esearch and D evelop m en t
Journal o f S ystem s M anagement

EXERCISES
9-1

U se the chart o f Fig. 9-1 to place the follow ing types o f inform ation system s in ap­
propriate p osition s. Explain your ch o ice in each case,a Q uestion-answ ering system sb Public libraries
c Private industrial or special libraries

DATA MANAGEMENT SYSTEMS

407

d
9-2

9-3

P oison control centerse A utom ated inventory control system s
C onsider a data b ase m anagem ent system designed to maintain the student-course
records needed by the faculty and administration in a particular school. Specify thetypes o f records that must be included in the system and design a user (external)
data base schem a as w ell as the conceptual and the internal data b ase schem as.
G iven the tw o relations M and N , carry out the follow ing operations in the rela­tional algebra:

A

B

C

C

D

E

One
Two
Three
Seven

Sine
CosineTangent
Cotangent

Plus
Plus
Minus
Minus

Plus
Minus
Plus
Minus

Sine
Sine
Tangent
Cotangent

Seven
Two
Three
Two

Relation M
a

b
c

d

9-4

9-5

9-6

9-7

9-8

Relation N

T he Cartesian product N x M
T he natural join M JOIN N
T he restricted join N JO IN M
B^D

The projection PROJ3i1 N
L ist the advantages and disadvantages o f each o f the three main data b ase m odels
including the relational, hierarchical, and netw ork m odels. What m echanism s areavailable to obtain file a cc e ss to data bases organized according to the various
m odel specifications? H o w d o es o n e search the stored data in each m odel?
W hy is it useful to m ake special provisions to im plem ent m any-to-m any relation­
ships in som e data base system s? H ow are m any-to-m any relationships im plem entated in relational, hierarchical, and network system s?
D esign relational, hierarchical, and network data b ases that include the follow ing
relationships betw een record typesa M anagers responsible for m any projects
b M anagers responsible for m any em ployeesc E m ployees assigned to m any projects
d Projects carried out by m any em ployees
D escribe how the three data base organizations w ould be used to retrieve thenam es o f all em ployees that report to several m anagers, and the number o f manag­
ers responsible for m ore than on e project.
L ist the various circum stances that render n ecessary the protection o f data bases
against unauthorized a c c e ss. W hat m ethods can b e u sed to provide the required
protection, and h ow do th ese m ethods operate?
W hy is it n ecessary to protect the integrity o f the stored data in a data b ase m anage­
m ent system ? What m ethods are available for integrity preservation? In w hich w ay
are integrity considerations u sed in specifying the structure o f relational data basesystem s?