
Chapter 1

The Worlds of Database

Systems

Databases today are essential to every business. They are used to maintain

internal records, to present data to customers and clients on the World-Wide-

Web, and to support many other commercial processes. Databases are likewise

found at the core of many scienti?c investigations. They represent the data

gathered by astronomers, by investigators of the human genome, and by bio-

chemists exploring the medicinal properties of proteins, along with many other

scientists.

The power of databases comes from a body of knowledge and technology

that has developed over several decades and is embodied in specialized soft-

ware called a database management system, or DBMS, or more colloquially a

\database system." A DBMS is a powerful tool for creating and managing large

amounts of data e?ciently and allowing it to persist over long periods of time,

safely. These systems are among the most complex types of software available.

The capabilities that a DBMS provides the user are:

1. Persistent storage. Like a ?le system, a DBMS supports the storage of

very large amounts of data that exists independently of any processes that

are using the data. However, the DBMS goes far beyond the ?le system in

providing 
exibility, such as data structures that support e?cient access

to very large amounts of data.

2. Programming interface. A DBMS allows the user or an application pro-

gram to access and modify data through a powerful query language.

Again, the advantage of a DBMS over a ?le system is the 
exibility to

manipulate stored data in much more complex ways than the reading and

writing of ?les.

3. Transaction management. A DBMS supports concurrent access to data,

i.e., simultaneous access by many distinct processes (called \transac-

1



2 CHAPTER 1. THE WORLDS OF DATABASE SYSTEMS

tions") at once. To avoid some of the undersirable consequences of si-

multaneous access, the DBMS supports isolation, the appearance that

transactions execute one-at-a-time, and atomicity, the requirement that

transactions execute either completely or not at all. A DBMS also sup-

ports durability, the ability to recover from failures or errors of many

types.

1.1 The Evolution of Database Systems

What is a database? In essence a database is nothing more than a collection of

information that exists over a long period of time, often many years. In common

parlance, the term database refers to a collection of data that is managed by a

DBMS. The DBMS is expected to:

1. Allow users to create new databases and specify their schema (logical

structure of the data), using a specialized language called a data-de?nition

language.

2. Give users the ability to query the data (a \query" is database lingo for

a question about the data) and modify the data, using an appropriate

language, often called a query language or data-manipulation language.

3. Support the storage of very large amounts of data | many gigabytes or

more | over a long period of time, keeping it secure from accident or

unauthorized use and allowing e?cient access to the data for queries and

database modi?cations.

4. Control access to data from many users at once, without allowing the

actions of one user to a?ect other users and without allowing simultaneous

accesses to corrupt the data accidentally.

1.1.1 Early Database Management Systems

The ?rst commercial database management systems appeared in the late 1960's.

These systems evolved from ?le systems, which provide some of item (3) above;

?le systems store data over a long period of time, and they allow the storage of

large amounts of data. However, ?le systems do not generally guarantee that

data cannot be lost if it is not backed up, and they don't support e?cient access

to data items whose location in a particular ?le is not known.

Further, ?le systems do not directly support item (2), a query language for

the data in ?les. Their support for (1) | a schema for the data | is limited to

the creation of directory structures for ?les. Finally, ?le systems do not satisfy

(4). When they allow concurrent access to ?les by several users or processes,

a ?le system generally will not prevent situations such as two users modifying

the same ?le at about the same time, so the changes made by one user fail to

appear in the ?le.



1.1. THE EVOLUTION OF DATABASE SYSTEMS 3

The ?rst important applications of DBMS's were ones where data was com-

posed of many small items, and many queries or modi?cations were made. Here

are some of these applications.

Airline Reservations Systems

In this type of system, the items of data include:

1. Reservations by a single customer on a single 
ight, including such infor-

mation as assigned seat or meal preference.

2. Information about 
ights | the airports they 
y from and to, their de-

parture and arrival times, or the aircraft 
own, for example.

3. Information about ticket prices, requirements, and availability.

Typical queries ask for 
ights leaving around a certain time from one given

city to another, what seats are available, and at what prices. Typical data

modi?cations include the booking of a 
ight for a customer, assigning a seat, or

indicating a meal preference. Many agents will be accessing parts of the data

at any given time. The DBMS must allow such concurrent accesses, prevent

problems such as two agents assigning the same seat simultaneously, and protect

against loss of records if the system suddenly fails.

Banking Systems

Data items include names and addresses of customers, accounts, loans, and their

balances, and the connection between customers and their accounts and loans,

e.g., who has signature authority over which accounts. Queries for account

balances are common, but far more common are modi?cations representing a

single payment from, or deposit to, an account.

As with the airline reservation system, we expect that many tellers and

customers (through ATMmachines or the Web) will be querying and modifying

the bank's data at once. It is vital that simultaneous accesses to an account not

cause the e?ect of a transaction to be lost. Failures cannot be tolerated. For

example, once the money has been ejected from an ATM machine, the bank

must record the debit, even if the power immediately fails. On the other hand,

it is not permissible for the bank to record the debit and then not deliver the

money if the power fails. The proper way to handle this operation is far from

obvious and can be regarded as one of the signi?cant achievements in DBMS

architecture.

Corporate Records

Many early applications concerned corporate records, such as a record of each

sale, information about accounts payable and receivable, or information about

employees | their names, addresses, salary, bene?t options, tax status, and



4 CHAPTER 1. THE WORLDS OF DATABASE SYSTEMS

so on. Queries include the printing of reports such as accounts receivable or

employees' weekly paychecks. Each sale, purchase, bill, receipt, employee hired,

?red, or promoted, and so on, results in a modi?cation to the database.

The early DBMS's, evolving from ?le systems, encouraged the user to visu-

alize data much as it was stored. These database systems used several di?erent

data models for describing the structure of the information in a database, chief

among them the \hierarchical" or tree-based model and the graph-based \net-

work" model. The latter was standardized in the late 1960's through a report

of CODASYL (Committee on Data Systems and Languages).

1

A problem with these early models and systems was that they did not sup-

port high-level query languages. For example, the CODASYL query language

had statements that allowed the user to jump from data element to data ele-

ment, through a graph of pointers among these elements. There was consider-

able e?ort needed to write such programs, even for very simple queries.

1.1.2 Relational Database Systems

Following a famous paper written by Ted Codd in 1970,

2

database systems

changed signi?cantly. Codd proposed that database systems should present

the user with a view of data organized as tables called relations. Behind the

scenes, there might be a complex data structure that allowed rapid response to

a variety of queries. But, unlike the user of earlier database systems, the user of

a relational system would not be concerned with the storage structure. Queries

could be expressed in a very high-level language, which greatly increased the

e?ciency of database programmers.

We shall cover the relational model of database systems throughout most

of this book, starting with the basic relational concepts in Chapter 3. SQL

(\Structured Query Language"), the most important query language based on

the relational model, will be covered starting in Chapter 6. However, a brief

introduction to relations will give the reader a hint of the simplicity of the

model, and an SQL sample will suggest how the relational model promotes

queries written at a very high level, avoiding details of \navigation" through

the database.

Example 1.1 : Relations are tables. Their columns are headed by attributes,

which describe the entries in the column. For instance, a relation named

Accounts, recording bank accounts, their balance, and type might look like:

accountNo balance type

12345 1000.00 savings

67890 2846.92 checking

? ? ? ? ? ? ? ? ?

1

CODASYL Data Base Task Group April 1971 Report, ACM, New York.

2

Codd, E. F., \A relational model for large shared data banks," Comm. ACM, 13:6,

pp. 377{387.



1.1. THE EVOLUTION OF DATABASE SYSTEMS 5

Heading the columns are the three attributes: accountNo, balance, and type.

Below the attributes are the rows, or tuples. Here we show two tuples of the

relation explicitly, and the dots below them suggest that there would be many

more tuples, one for each account at the bank. The ?rst tuple says that account

number 12345 has a balance of one thousand dollars, and it is a savings account.

The second tuple says that account 67890 is a checking account with $2846.92.

Suppose we wanted to know the balance of account 67890. We could ask

this query in SQL as follows:

SELECT balance

FROM Accounts

WHERE accountNo = 67890;

For another example, we could ask for the savings accounts with negative bal-

ances by:

SELECT accountNo

FROM Accounts

WHERE type = 'savings' AND balance < 0;

We do not expect that these two examples are enough to make the reader an

expert SQL programmer, but they should convey the high-level nature of the

SQL \select-from-where" statement. In principle, they ask the DBMS to

1. Examine all the tuples of the relation Accounts mentioned in the FROM

clause,

2. Pick out those tuples that satisfy some criterion indicated in the WHERE

clause, and

3. Produce as an answer certain attributes of those tuples, as indicated in

the SELECT clause.

In practice, the system must \optimize" the query and ?nd an e?cient way to

answer the query, even though the relations involved in the query may be very

large. 2

By 1990, relational database systems were the norm. Yet the database ?eld

continues to evolve, and new issues and approaches to the management of data

surface regularly. In the balance of this section, we shall consider some of the

modern trends in database systems.

1.1.3 Smaller and Smaller Systems

Originally, DBMS's were large, expensive software systems running on large

computers. The size was necessary, because to store a gigabyte of data required

a large computer system. Today, many gigabytes ?t on a single disk, and



6 CHAPTER 1. THE WORLDS OF DATABASE SYSTEMS

it is quite feasible to run a DBMS on a personal computer. Thus, database

systems based on the relational model have become available for even very small

machines, and they are beginning to appear as a common tool for computer

applications, much as spreadsheets and word processors did before them.

1.1.4 Bigger and Bigger Systems

On the other hand, a gigabyte isn't much data. Corporate databases often

occupy hundreds of gigabytes. Further, as storage becomes cheaper people

?nd new reasons to store greater amounts of data. For example, retail chains

often store terabytes (a terabyte is 1000 gigabytes, or 10

12

bytes) of information

recording the history of every sale made over a long period of time (for planning

inventory; we shall have more to say about this matter in Section 1.1.7).

Further, databases no longer focus on storing simple data items such as

integers or short character strings. They can store images, audio, video, and

many other kinds of data that take comparatively huge amounts of space. For

instance, an hour of video consumes about a gigabyte. Databases storing images

from satellites can involve petabytes (1000 terabytes, or 10

15

bytes) of data.

Handling such large databases required several technological advances. For

example, databases of modest size are today stored on arrays of disks, which are

called secondary storage devices (compared to mainmemory, which is \primary"

storage). One could even argue that what distinguishes database systems from

other software is, more than anything else, the fact that database systems

routinely assume data is too big to ?t in main memory and must be located

primarily on disk at all times. The following two trends allow database systems

to deal with larger amounts of data, faster.

Tertiary Storage

The largest databases today require more than disks. Several kinds of tertiary

storage devices have been developed. Tertiary devices, perhaps storing a tera-

byte each, require much more time to access a given item than does a disk.

While typical disks can access any item in 10-20 milliseconds, a tertiary device

may take several seconds. Tertiary storage devices involve transporting an

object, upon which the desired data item is stored, to a reading device. This

movement is performed by a robotic conveyance of some sort.

For example, compact disks (CD's) or digital versatile disks (DVD's) may

be the storage medium in a tertiary device. An arm mounted on a track goes

to a particular disk, picks it up, carries it to a reader, and loads the disk into

the reader.

Parallel Computing

The ability to store enormous volumes of data is important, but it would be

of little use if we could not access large amounts of that data quickly. Thus,

very large databases also require speed enhancers. One important speedup is



1.1. THE EVOLUTION OF DATABASE SYSTEMS 7

through index structures, which we shall mention in Section 1.2.2 and cover

extensively in Chapter 13. Another way to process more data in a given time

is to use parallelism. This parallelism manifests itself in various ways.

For example, since the rate at which data can be read from a given disk is

fairly low, a few megabytes per second, we can speed processing if we use many

disks and read them in parallel (even if the data originates on tertiary storage,

it is \cached" on disks before being accessed by the DBMS). These disks may

be part of an organized parallel machine, or they may be components of a

distributed system, in which many machines, each responsible for a part of the

database, communicate over a high-speed network when needed.

Of course, the ability to move data quickly, like the ability to store large

amounts of data, does not by itself guarantee that queries can be answered

quickly. We still need to use algorithms that break queries up in ways that

allow parallel computers or networks of distributed computers to make e?ective

use of all the resources. Thus, parallel and distributed management of very large

databases remains an active area of research and development; we consider some

of its important ideas in Section 15.9.

1.1.5 Client-Server and Multi-Tier Architectures

Many varieties of modern software use a client-server architecture, in which

requests by one process (the client) are sent to another process (the server) for

execution. Database systems are no exception, and it has become increasingly

common to divide the work of a DBMS into a server process and one or more

client processes.

In the simplest client/server architecture, the entire DBMS is a server, ex-

cept for the query interfaces that interact with the user and send queries or

other commands across to the server. For example, relational systems generally

use the SQL language for representing requests from the client to the server.

The database server then sends the answer, in the form of a table or relation,

back to the client. The relationship between client and server can get more

complex, especially when answers are extremely large. We shall have more to

say about this matter in Section 1.1.6.

There is also a trend to put more work in the client, since the server will

be a bottleneck if there are many simultaneous database users. In the recent

proliferation of system architectures in which databases are used to provide

dynamically-generated content for Web sites, the two-tier (client-server) archi-

tecture gives way to three (or even more) tiers. The DBMS continues to act

as a server, but its client is typically an application server, which manages

connections to the database, transactions, authorization, and other aspects.

Application servers in turn have clients such as Web servers, which support

end-users or other applications.



8 CHAPTER 1. THE WORLDS OF DATABASE SYSTEMS

1.1.6 Multimedia Data

Another important trend in database systems is the inclusion of multimedia

data. By \multimedia" we mean information that represents a signal of some

sort. Common forms of multimedia data include video, audio, radar signals,

satellite images, and documents or pictures in various encodings. These forms

have in common that they are much larger than the earlier forms of data |

integers, character strings of ?xed length, and so on | and of vastly varying

sizes.

The storage of multimedia data has forced DBMS's to expand in several

ways. For example, the operations that one performs on multimedia data are

not the simple ones suitable for traditional data forms. Thus, while one might

search a bank database for accounts that have a negative balance, comparing

each balance with the real number 0.0, it is not feasible to search a database of

pictures for those that show a face that \looks like" a particular image.

To allow users to create and use complex data operations such as image-

processing, DBMS's have had to incorporate the ability of users to introduce

functions of their own choosing. Often, the object-oriented approach is used

for such extensions, even in relational systems, which are then dubbed \object-

relational." We shall take up object-oriented database programming in various

places, including Chapters 4 and 9.

The size of multimedia objects also forces the DBMS to modify the storage

manager so that objects or tuples of a gigabyte or more can be accommodated.

Among the many problems that such large elements present is the delivery of

answers to queries. In a conventional, relational database, an answer is a set of

tuples. These tuples would be delivered to the client by the database server as

a whole.

However, suppose the answer to a query is a video clip a gigabyte long. It is

not feasible for the server to deliver the gigabyte to the client as a whole. For

one reason it takes too long and will prevent the server from handling other

requests. For another, the client may want only a small part of the ?lm clip,

but doesn't have a way to ask for exactly what it wants without seeing the

initial portion of the clip. For a third reason, even if the client wants the whole

clip, perhaps in order to play it on a screen, it is su?cient to deliver the clip at

a ?xed rate over the course of an hour (the amount of time it takes to play a

gigabyte of compressed video). Thus, the storage system of a DBMS supporting

multimedia data has to be prepared to deliver answers in an interactive mode,

passing a piece of the answer to the client on request or at a ?xed rate.

1.1.7 Information Integration

As information becomes ever more essential in our work and play, we ?nd that

existing information resources are being used in many new ways. For instance,

consider a company that wants to provide on-line catalogs for all its products, so

that people can use the World Wide Web to browse its products and place on-



1.2. OVERVIEW OF A DATABASE MANAGEMENT SYSTEM 9

line orders. A large company has many divisions. Each division may have built

its own database of products independently of other divisions. These divisions

may use di?erent DBMS's, di?erent structures for information, perhaps even

di?erent terms to mean the same thing or the same term to mean di?erent

things.

Example 1.2 : Imagine a company with several divisions that manufacture

disks. One division's catalog might represent rotation rate in revolutions per

second, another in revolutions per minute. Another might have neglected to

represent rotation speed at all. A division manufacturing 
oppy disks might

refer to them as \disks," while a division manufacturing hard disks might call

them \disks" as well. The number of tracks on a disk might be referred to as

\tracks" in one division, but \cylinders" in another. 2

Central control is not always the answer. Divisions may have invested large

amounts of money in their database long before information integration across

divisions was recognized as a problem. A division may have been an inde-

pendent company, recently acquired. For these or other reasons, these so-called

legacy databases cannot be replaced easily. Thus, the company must build some

structure on top of the legacy databases to present to customers a uni?ed view

of products across the company.

One popular approach is the creation of data warehouses, where information

from many legacy databases is copied, with the appropriate translation, to a

central database. As the legacy databases change, the warehouse is updated,

but not necessarily instantaneously updated. A common scheme is for the

warehouse to be reconstructed each night, when the legacy databases are likely

to be less busy.

The legacy databases are thus able to continue serving the purposes for

which they were created. New functions, such as providing an on-line catalog

service through the Web, are done at the data warehouse. We also see data

warehouses serving needs for planning and analysis. For example, company an-

alysts may run queries against the warehouse looking for sales trends, in order

to better plan inventory and production. Data mining, the search for interest-

ing and unusual patterns in data, has also been enabled by the construction

of data warehouses, and there are claims of enhanced sales through exploita-

tion of patterns discovered in this way. These and other issues of information

integration are discussed in Chapter 20.

1.2 Overview of a Database Management

System

In Fig. 1.1 we see an outline of a complete DBMS. Single boxes represent system

components, while double boxes represent in-memory data structures. The solid

lines indicate control and data 
ow, while dashed lines indicate data 
ow only.



10 CHAPTER 1. THE WORLDS OF DATABASE SYSTEMS

Since the diagram is complicated, we shall consider the details in several stages.

First, at the top, we suggest that there are two distinct sources of commands

to the DBMS:

1. Conventional users and application programs that ask for data or modify

data.

2. A database administrator : a person or persons responsible for the struc-

ture or schema of the database.

1.2.1 Data-De?nition Language Commands

The second kind of command is the simpler to process, and we show its trail

beginning at the upper right side of Fig. 1.1. For example, the database ad-

ministrator, or DBA, for a university registrar's database might decide that

there should be a table or relation with columns for a student, a course the

student has taken, and a grade for that student in that course. The DBA

might also decide that the only allowable grades are A, B, C, D, and F. This

structure and constraint information is all part of the schema of the database.

It is shown in Fig. 1.1 as entered by the DBA, who needs special authority

to execute schema-altering commands, since these can have profound e?ects

on the database. These schema-altering DDL commands (\DDL" stands for

\data-de?nition language") are parsed by a DDL processor and passed to the

execution engine, which then goes through the index/?le/record manager to

alter the metadata, that is, the schema information for the database.

1.2.2 Overview of Query Processing

The great majority of interactions with the DBMS follow the path on the left

side of Fig. 1.1. A user or an application program initiates some action that

does not a?ect the schema of the database, but may a?ect the content of the

database (if the action is a modi?cation command) or will extract data from

the database (if the action is a query). Remember from Section 1.1 that the

language in which these commands are expressed is called a data-manipulation

language (DML) or somewhat colloquially a query language. There are many

data-manipulation languages available, but SQL, which was mentioned in Ex-

ample 1.1, is by far the most commonly used. DML statements are handled by

two separate subsystems, as follows.

Answering the query

The query is parsed and optimized by a query compiler. The resulting query

plan, or sequence of actions the DBMS will perform to answer the query, is

passed to the execution engine. The execution engine issues a sequence of

requests for small pieces of data, typically records or tuples of a relation, to a

resource manager that knows about data ?les (holding relations), the format



OVERVIEW OF A DATABASE MANAGEMENT SYSTEM 11

Buffers

Storage

Index/file/rec?

Storage

ord manager

Execution
engine

Transaction
manager

manager

Logging and
recovery

Database
administrator

table

Query
compiler compiler

Concurrency
control

Lock

manager
Buffer

DDL

User/application

queries,
updates

query
plan

index, file, and
record requests

commands
page

read/write
pages

transaction
commands

statistics
metadata,

log
pages

commands
DDL

data,
metadata,

indexes

metadata

Figure 1.1: Database management system components



12 CHAPTER 1. THE WORLDS OF DATABASE SYSTEMS

and size of records in those ?les, and index ?les, which help ?nd elements of

data ?les quickly.

The requests for data are translated into pages and these requests are passed

to the bu?er manager. We shall discuss the role of the bu?er manager in

Section 1.2.3, but brie
y, its task is to bring appropriate portions of the data

from secondary storage (disk, normally) where it is kept permanently, to main-

memory bu?ers. Normally, the page or \disk block" is the unit of transfer

between bu?ers and disk.

The bu?er manager communicates with a storage manager to get data from

disk. The storage manager might involve operating-system commands, but

more typically, the DBMS issues commands directly to the disk controller.

Transaction processing

Queries and other DML actions are grouped into transactions, which are units

that must be executed atomically and in isolation from one another. Often each

query or modi?cation action is a transaction by itself. In addition, the execu-

tion of transactions must be durable, meaning that the e?ect of any completed

transaction must be preserved even if the system fails in some way right after

completion of the transaction. We divide the transaction processor into two

major parts:

1. A concurrency-control manager, or scheduler, responsible for assuring

atomicity and isolation of transactions, and

2. A logging and recovery manager, responsible for the durability of trans-

actions.

We shall consider these components further in Section 1.2.4.

1.2.3 Storage and Bu?er Management

The data of a database normally resides in secondary storage; in today's com-

puter systems \secondary storage" generally means magnetic disk. However, to

perform any useful operation on data, that data must be in main memory. It

is the job of the storage manager to control the placement of data on disk and

its movement between disk and main memory.

In a simple database system, the storage manager might be nothing more

than the ?le system of the underlying operating system. However, for e?ciency

purposes, DBMS's normally control storage on the disk directly, at least under

some circumstances. The storage manager keeps track of the location of ?les on

the disk and obtains the block or blocks containing a ?le on request from the

bu?er manager. Recall that disks are generally divided into disk blocks, which

are regions of contiguous storage containing a large number of bytes, perhaps

2

12

or 2

14

(about 4000 to 16,000 bytes).

The bu?er manager is responsible for partitioning the available main mem-

ory into bu?ers, which are page-sized regions into which disk blocks can be



OVERVIEW OF A DATABASE MANAGEMENT SYSTEM 13

transferred. Thus, all DBMS components that need information from the disk

will interact with the bu?ers and the bu?er manager, either directly or through

