Data and Data Models

2 Data and Data Models

2.1 INTRODUCTION

In this chapter, we introduce more concepts that are essential to our presentation

of the design of a database. We defined a database as a collection

of related facts (related data). In this chapter, we explore database models

and introduce the relational database model. While there are many kinds

of database models, most of the databases in use today are relational; our

focus in this book is to design a good relational database. In the next chapter,

we introduce the concept of functional dependencies to define what is a

good (and a not-so-good) relational database. The purpose of this chapter is

mostly historical; it engenders an appreciation for the simplicity and power

of the relational model.

2.2 FILES, RECORDS, AND DATA ITEMS

Data has to be stored in some fashion in a file to be useful. Suppose there

were no computers—think back to a time when files were paper documents.

A business kept track of its customers and products. A doctor’s

office kept track of patients. A sports team kept statistics on its players. In

all of these cases, data was recorded on paper. The files with data in them

could be referred to as a “database.” A database is most simply a repository

of data about some specific entity. A customer file might be as plain and

minimal as a list of people that did business with a merchant. There are

two aspects to filing: storage and retrieval. Some method of storing data

that will facilitate retrieval is most desirable.

Suppose we have a file of customer records. The whole file might be

called the customer file, whereas the individual customer’s information

12 • Database Design Using Entity-Relationship Diagrams

is kept in a customer record. Files consist of records. More than likely,

more information than a list of just customer’s names would be stored.

Most likely, at the very least a customer’s name, address, and phone number

would constitute a customer record. Each of these components of the

record is called a data item or field. The customer file contains customer

records that consist of fields of data.

Here is an example of some data (you can imagine each line as a 3 × 5

card, with the three cards making up a file):

CUSTOMER File

Record 1: Jones, J 123 4th St Mobile, AL

Record 2: Smith, S 452 Main St Pensacola, FL

Record 3: Harris, H 92 Adams Lane Elberta, AL

This file contains three records. There is one record for each customer.

The records each consist of four fields: record number, name, address,

city. As more customers are added, they also are assigned a 3 × 5 card,

and these records are placed in the file. Several interesting questions and

observations arise:

1. The merchant who keeps this file may well want to add information

in the future. Suppose that the merchant wanted to add a telephone

number. Would the merchant add a number to all 3 × 5 cards, or

would the adding be done “as necessary”? If it were done as necessary,

then some customers would have telephone numbers, and

some would not. If a customer had no phone number, then the phone

number for that customer would be “null” (unknown).

2. How will the file be organized? Imagine not three customers, but 300 or

3,000. Would the 3 × 5 cards be put in alphabetical order? Perhaps, but

what happens if you get another J. Jones or S. Smith? The field on which

the file is organized is called a key. Perhaps the file should be organized

by telephone number, which might not have a duplicate value?

3. Suppose the file were organized by telephone number. What if the

telephone number for some customer was not recorded? If there were

no telephone number, the common terminology is that we say the

telephone field for that record is null. It would make no sense to have

the file organized by telephone number if some values were null.

Clearly, the key of a file cannot be null. Also, if telephone number

were the key, then the person finding a record in the file would have

to know the phone number to find the appropriate record efficiently.

Data and Data Models • 13

4. The format of the file given is

CUSTOMER(record_number, name, address, city)

The format of the file dictates the order of the fields in any record. In this

record, record_number is first, followed by a name, and so on. The file

design could have the fields in some other order, but once defined, the

order of the fields stays constant.

If a telephone number field were added, then the file format could be

CUSTOMER (record_number, name, address, city, telephone)

This shorthand format notation is referred to as the file design. If the file

were set up to find data by name and name were the key, then the name

would be underlined, as follows:

CUSTOMER (record_number, name, address, city, telephone)

5. You might ask, “Why not use the record number to organize the

file?” On one hand, it is unique (which is desirable for a key), but on

the other hand, you would have to know the record number to find

a customer. The example is organized by record number; however,

imagine 300 or more customers. You want to find Smith’s address—

you would have to know the record number. It makes more sense to

organize this file of 3 × 5 cards by name. Taking some of these points

into consideration, here is an enhanced version of the customer file

in which each line represents a 3 × 5 card:

CUSTOMER File

Record 1: Adams, A 77 A St Pensacola

FL

555-5847

Record 2: Charles,

X

365

Broad St

Mobile AL 555-8214

Record 3: Harris,

H

92 Adams

Lane

Elberta,

AL

555-1234

Record 4: Jones, A 22 Pine

Forest

Pensacola

FL

null

Record 5: Jones, J 123 4th

St

Mobile, AL 555-9978

Record 6: Morris, M 932

Dracena

Way

Gulf

Breeze FL

555-1111

Record 7: Smith, S 452 Main

St

Pensacola,

FL

555-0003

14 • Database Design Using Entity-Relationship Diagrams

CHECKPOINT 2.1

1. What does it mean to say a field has unique values?

2. Why is it desirable to have a key be unique?

3. Why does a file have to be organized by a key field?

4. What does null mean?

5. Consider this customer file:

Record 1: 77 A St Adams, A Pensacola

FL

555-5847

Record 2: Charles,

X

365 Broad

St

555-8214 Mobile AL

Record 3: 555-1234 Harris, H 92 Adams

Lane

Elberta,

AL

What is wrong here?

2.3 MOVING FROM 3 × 5 CARDS TO COMPUTERS

Let us return to our example of a merchant who kept his customer file on

3 × 5 cards. As time passed, the customer base grew and the merchant

probably desired to keep more information about customers. From a

data-processing standpoint, we would say that the techniques for storing

and retrieval led to enhanced forms or cards, more fields, and perhaps better

ways to store and find individual records. Were customer records kept

in alphabetical order? Were they stored by telephone number or record

number (which might be a customer number)? What happened if a new

field was required that was not on existing forms or cards? Such was a

data-processing dilemma of the past.

When computers began to be used for businesses, data was stored on

magnetic media. The magnetic media were mostly disks and tapes. The

way data was stored and retrieved on a computer started out like the 3

× 5 cards, but the data was virtual; it did not physically exist where you

could touch it or see it without some kind of software to load and find

records and some kind of display device to see what the “3 × 5 card”

had on it. The most common way data was fed into a computer was via

punched cards. Punched card systems for handling data were in use as

early as the 1930s; sorters were capable of scanning and arranging a pile

of cards. Using punched cards to input data into computers did not blossom

until the 1960s. The output or “display device” was typically a line

printer.

Data and Data Models • 15

As data was placed on a computer, and software could be developed to

handle the data, filing techniques evolved. In the very early days of databases,

the files kept on computers basically replicated the 3 × 5 cards. There

were many problems with computers and databases in the “early days.”

(Generally, early days in terms of computers and databases means roughly

early to mid-1960s.) Some problems involved input (how the data got into

the computer), output (how the data was to be displayed), and file maintenance

(for example, how the data was to be stored and kept up to date; how

records were to be added and deleted; how fields were to be added, deleted,

or changed). A person using a computer for keeping track of data could

buy a computer and hire programmers, operators, and data entry personnel.

In the early days, computers were expensive and large. Most small

businesses did not have the resources to obtain a computer, much less hire

people whose jobs were solely “on the computer.” Early attempts at filing

data and retrieving them were the purview of large businesses and large

organizations. One thing was clear: Many more virtual customer records

than the 300 or so we envisioned were possible.

In the early days, imagine that some company had a computer, and the

departments within the company wanted to keep files on the computer.

Suppose further that the company made some product and had several

departments (e.g., sales, accounting, production). Now, suppose that

each department wanted to keep data about customers. Each department

had a different view of customers. The sales department wanted

to know the name, address, telephone number, and some data related to

the propensity to buy the product. The accounting department wanted

to know roughly the same information, but wanted to keep track of billing

and payments. Production also wanted some of the same information,

but wanted to know what the customer wanted in the product and

how many they should make. Each department wanted about the same

thing, but each approached the problem in a different way. What actually

happened in the early days was that each department shared the

expensive computer but hired its own programming staff to keep “their

database.” While the sense of sharing the expensive computer was there,

the sense of sharing data was not. The idea of a “software package” to

store and retrieve data was not there either. Programmers used computer

languages like COBOL, RPG, ALGOL, PL/1, and FORTRAN to

store and retrieve data. Each department created its own records and its

own storage and retrieval methods, kept its own programs, and had its

own data entry groups.

16 • Database Design Using Entity-Relationship Diagrams

The earliest databases were filing systems maintained by some computer

language. For example, a programmer wrote a COBOL program to gather

input data on punched cards and to store the data in a computer file. Then,

the programmer wrote another set of programs to retrieve the data and

display it in whatever way a user wanted to see it. Early computer filing

systems were simple sequential files. The data on punched cards was read

and stored. Reconsider the customer file we introduced previously:

CUSTOMER File

Record 1: Adams, A 77 A St Pensacola

FL

555-5847

Record 2: Charles,

X

365

Broad St

Mobile AL 555-8214

Record 3: Harris, H 92 Adams

Lane

Elberta, AL 555-1234

Record 4: Jones, A 22 Pine

Forest

Pensacola

FL

null

Record 5: Jones, J 123 4th

St

Mobile, AL 555-9978

Record 6: Morris, M 932

Dracena

Way

Gulf Breeze

FL

555-1111

Record 7: Smith, S 452 Main

St

Pensacola,

FL

555-0003

If you could look at the data on a disk, it might look like this:

Adams, A 77 A St Pensacola

FL

555-5847

Charles, X 365 Broad

St

Mobile AL 555-8214

Harris, H 92 Adams

Lane

Elberta, AL 555-1234

Jones, A 22 Pine

Forest

Pensacola

FL

null

Jones, J 123 4th St Mobile, AL 555-9978

Morris, M 932 Dracena

Way

Gulf Breeze

FL

555-1111

Smith, S 452 Main St Pensacola,

FL

555-0003

Data and Data Models • 17

The records as addressed by COBOL had a structure like this:

01 CUSTOMER

05 NAME CHARACTER(20)

05 ADDRESS CHARACTER(20)

05 CITY-STATE CHARACTER(25)

05 PHONE CHARACTER(7)

The file was referred to as a “sequential file.” If a person wanted to see a

listing of data by address rather than name, the file had to be sorted and

the data redisplayed. If data was added to the file, it had to be put in its

proper place according to the sequential key, which in this example is the

name field.

Two other principal filing systems evolved in the 1960s: indexed and the

direct access filing systems. Indexed systems were based on the maintenance

of indexes for records rather than a strict sequential ordering of the records

themselves. Look again at the customer example in a different light:

CUSTOMER File

Record 1: Adams, A 77 A St. Pensacola

FL

555-5847

Record 2: Charles, X 365 Broad

St

Mobile AL 555-8214

...

In this case, suppose that Record 1 were not a numerical record but

rather a disk address. Then, suppose there was an index to the records

themselves that consisted of names and disk addresses like this:

Name Disk address

Adams, A 1

Charles, X 2

Harris, H 3

and so forth.

Now, suppose you added a customer called Baker, B. In a sequential filing

system, you would have to put Baker between Adams and Charles,

but in an indexed system, you could put Baker anywhere on the disk and

simply change the index to find Baker:

18 • Database Design Using Entity-Relationship Diagrams

Name Disk address

Adams, A 1

Baker, B 8

Charles, X 2

Harris, H 3

Disks were arranged by their geometry. A disk usually consisted of

an arrangement of platters that looked like flat, brown phonograph

records with a spindle in the center. The disk rapidly rotated, and data

was arranged on the plate concentrically and written and read magnetically.

If all of this sounds like an old phonograph system, that is likely

where the idea of stacking disks originated. If you could look at the data

on a specific plate, it would be arranged in a circle, and there would be

many circles, getting larger as you moved out on the plate. Each circle

was called a track. Data on a disk was thought to be located in a relative

position on some track and imaginary overlaid tracks called cylinders.

Here is a simplified example: If the tracks were designated as 1, 2, 3,

… starting from the data circle nearest the spindle, and the cylinders

were designated 1, 2, 3, … starting from the top of the disk, then a data

address would be referenced as follows, for example: cylinder 4, track 3,

record 24. This would mean that the data was on the 4th plate from the

top, on the 3rd track from the spindle, and in the 24th position on that

track.

The indexed systems became quite elaborate. The one illustrated was

called a relative record indexed system. In the relative record system, one

needed to know only which cylinders a file occupied, and then the position

of the record could be calculated relative to the starting position of

the file. Originally, relative record systems were not popular, whereas there

was a common indexed system used primarily on IBM computers that was

based on disk geometry (cylinders, tracks, and records) called an indexedsequential

system.

Whatever the index system, one had to keep indexes to store and find

records. Imagine not 30 or 300 customers, but 300,000. Now, suppose

that someone wanted to find customers by their address rather than

their name. You would have to have another index, or you would have

to look at each record in the filing system until you found the address

you needed. One other less-common way to manage early data access and

retrieval was to base the index on an exact location of data on a disk: the

direct access filing system. The popular indexed-sequential system was

Data and Data Models • 19

probably the best amalgamation of the properties of all filing systems in

that it efficiently handled record additions, deletions, and updating as well

as providing reasonable data access speeds. Early filing systems involved

choices: elaborate indexes or elaborate programs to sort and find data (or

both). Regardless of the choice of index, there were always problems with

maintaining the index (or indexes); adding, updating, or deleting records;

finding and displaying records and reprogramming all of these items for

new applications or hardware.

In the late 1960s, software packages called database systems began to

emerge. Database systems were purchasable programs that stored and

retrieved data as well as performed maintenance (adding, deleting, and

modifying fields and records). With a database system, one did not have

to write COBOL programs to handle data directly but rather relied on the

database program to handle data. With these systems, each department

could share data and resources. Instead of each department having its own

programmers and perhaps its own computer, there could be one central

computer to store data, one programming staff, and one database software

package. Data could be shared, with each department having its own

view of the data. All this sounds great, but in reality it took several years

to break away from the “my data” mold. In addition, there were hybrid

systems that emerged that focused mainly on retrieval of data that delayed

the move to a totally relational environment because of the investment

companies had in software and programmers.

Why was sharing data a good thing? It not only used expensive resources

more efficiently but also reduced redundancy. Redundancy means storing

the same information in different places. If each department stored its

own version of data, its own view of customers, then the customer name,

address, telephone number, and so on were recorded by each department.

Suppose the customer moved. Then, each department changed its data

when it found out the customer moved, and at some point the customer’s

address could be stored inconsistently: The accounting department had

one address, the sales department had another. The root problem here is

the lack of data sharing, and sharing was a central goal of the early database

systems.

The early database software evolved into two main data models: the

hierarchical and the network models. Although the relational model for

a database was recognized as a desirable technique in the early 1970s, the

relational model was treated as a really good theoretical technique for

which computers were not fast enough to implement.

20 • Database Design Using Entity-Relationship Diagrams

The database models (hierarchical, network, and relational) were logical

models—ways of logically perceiving the arrangement of data in a file structure.

One perceived how the data was to be logically stored, and the database

physically implemented the logical model. As we shall see, there is a close relationship

between the logical and physical implementations of the hierarchical

and network models. Since there were no practical relational implementations

on other than what was then supercomputers at research centers, the world of

commercial databases in the 1970s involved choosing between the hierarchical

and network models. The next sections give a little insight into each of

these three main models and an introduction to the relational model.

CHECKPOINT 2.2

1. What is a sequential file?

2. What is COBOL?

3. Why is ordering important in a sequential filing system?

4. What is a database program?

5. In the early days, how was data put into a file?

2.4 DATABASE MODELS

We now take a look back at database models as they were before the relational

database was practical. The look back shows why the “old systems”

are considered obsolete and why the relational model is the de facto standard

in databases today. The old systems were classified as two main types:

hierarchical and network. These two models defined a database before the

1980s. Although they might be considered “old fashioned,” there are systems

still in use today that depend on these models.

2.4.1 The Hierarchical Model

In hierarchical database models, all data are arranged in a top-down

fashion in which some records have one or more “dependent” or “child”

records, and each child record is tied to one and only one “parent.” The

parent-child relationship is not meant to infer a human familial relationship.

The terms parent and child are historical and are meant to conjure

up a picture of one type of data as dependent on another. As is illustrated

here, the child will be sports played by a parent-person. Another terminology

for the parent-child relationship is owner and objects owned, but

parent-child is more common.

Data and Data Models • 21

In this section, we present some versions of the hierarchical model for

several reasons: (a) to illustrate how older models were constructed from

file systems; (b) to show why file-based databases became outdated when

relational databases became practical; and (c) to see the evolution of filebased

systems.

We begin with an example of a hierarchical file situation. Suppose you

have a database of people who play a sport at some location. A sample

record might consist of Brenda who plays tennis at city courts and who

plays golf at the municipal links. The person, Brenda, would be at the top

of the hierarchy, and the sport-location would be the second layer of the

hierarchy. Usually, the connection between the layers of the hierarchy is

referred to as a parent-child relationship.

Each parent person may be related to many child sport-locations, but

each sport-location (each child) is tied back to the one person (one parent)

it “is played by.” You may be thinking, “Suppose the same sport is played

by two people at the same location?” That is a good question, but it is not

a situation that can be handled by hierarchical file systems in a direct way.

If, for example, Richard also plays golf at the municipal links, then golf at

municipal links will be recorded twice as a child for each parent. If the

same sport-location occurs, then it is recorded redundantly.

The one person, many sports tie may be called a one-to-many relationship.

Some more data might look like the following, with a person’s name

followed by the sport and location:

The model:

Person: sport, location; sport, location; sport,

location ...

The data itself:

Brenda: tennis, city courts; golf, municipal links

Richard: golf, municipal links; snorkeling, Pensacola

bay; running, UWF track

Abbie: downhill skiing, Ski Beech

Now this data could be stored in a database in many ways. You could

imagine information on each person on a 3 × 5 card with the person,s

data. You could also store the data on separate cards in a sequential file

like this:

Brenda

tennis, city courts

golf, municipal links

22 • Database Design Using Entity-Relationship Diagrams

Richard

golf, municipal links

snorkeling, Pensacola bay

running, UWF track

Abbie

downhill skiing, Ski Beech

The first thing you notice is that there is a series of text records (or 3 ×

5 cards), but it is hard to distinguish between person and sports without

semantics (you can tell the difference between person and sports by looking

at the entry, but the computer cannot do this unless you give the line of text

a meaning: semantics). For the computer, it is helpful to identify whether a

record is a person (P) or a sport (S). Hence, the sequential file could be

P Brenda

S tennis, city courts

S golf, municipal links

P Richard

S golf, municipal links

S snorkeling, Pensacola bay

S running, UWF track

P Abbie

S downhill skiing, Ski Beech

In actuality, this sequential file would be useful only if a person wanted

to list all the people followed by the sport-locations for that person.

Furthermore, the relationship of person to sport-location is one of position

in the file. The arrangement was sometimes called a header-trailer format;

persons are header records, sports are trailer records. If one wanted to

know all the people who played golf, they would have to read the entire file

and pick out those individuals. A better organization of the data would

be to have two files, one for person, one file for sport-locations. For the

two-file model to make sense (i.e., to have the files “related”), there would

have to be pointers or references of some kind from one file to the other.

One way to implement a pointer scheme would be a pointer from the sport

(child) to the person (parent) like this:

PERSON(record_number, name)

With data:

1. Brenda

2. Richard

3. Abbie

Data and Data Models • 23

SPORTS(sport, location, reference to person)

With data:

tennis, city courts, 1

golf, municipal links,1

golf, municipal links, 2

snorkeling, Pensacola bay, 2

running, UWF track, 2

downhill skiing, Ski Beech, 3

A diagram of this relationship is shown in Figure 2.1.

The actual location of the records on a disk could be arbitrary. The sense

of the data is not lost if the locations are disk addresses and if you imagine

that there are thousands of persons and sports:

PERSON(record address, name)

With data:

A45C. Brenda

C333. Abbie

B259. Richard

SPORTS(sport, location, reference to person)

With data:

golf, municipal links, B259

running, UWF track, B259

downhill skiing, Ski Beech, C333

snorkeling, Pensacola bay, B259

tennis, city courts, A45C

golf, municipal links, A45C

This system has a parent-child link. Here, we assume that the primary

key of the person file is the record_number. The “reference to person” in

the sports file refers to the primary key of the person file and is called a

Person (Parent record)

Sport Sport Sport

(Child Records)

FIGURE 2.1

A hierarchy of persons and sports with parent pointers.

24 • Database Design Using Entity-Relationship Diagrams

foreign key (FK) because it is a primary key of another file. The FK references

a primary key, hence completing the essential relationship of one

file to the other. If there were no relationship, then you would have two

independent files with no connection—the system would make no sense.

While we have established the relationship of child to parent in the

discussion, the database has some drawbacks. To answer a question like,

“Who plays golf at municipal links?” you start looking at the Sports file,

look for “golf at municipal links,” and see what parent records there are. If

your question were, “What sports does Richard play?” you would first find

Richard in the Person file, then look through the Sports file to find links

back to Richard.

If you were actually implementing this model, you could enhance the

system a bit. An improvement to this model would be to reference each

sport from within each parent record (let us go back to simple numbers

for this):

PERSON(record address, name, (sport address))

With data:

1. Brenda, (101, 102)

2. Richard (103, 104, 105)

3. Abbie (106)

SPORTS(sport, location, reference to person)

With data:

101, tennis, city courts, 1

102, golf, municipal links, 1

103, golf, municipal links, 2

104, snorkeling, Pensacola bay, 2

105, running, UWF track, 2

106, downhill skiing, Ski Beech, 3

Figure 2.2 depicts the relationship between parent and child records in

both directions. When viewed from the parent, this link is called a multiple-

child pointer (MCP). When viewed from the child the link is called a

parent pointer.

In this model, the relationship between parent and child records is done

two ways. The “reference to person” in the Sports file is a link (the FK) from

child to parent. The reference to multiple children in the parent records is

called an MCP scheme. While it is true that the MCP is redundant to the

relationship, it does two practical things: (a) It allows questions to be asked

Data and Data Models • 25

of the system that are easier to answer than with just parent pointers; and

(b) it allows the file system to be audited with a computer program. For

example, if you want to ask the system, “How many sports does Richard

play?” you need only look at the person file and count MCP references.

We have illustrated two ways to construct a relationship between two

files: the FK parent pointer and the MCP. Both of the linking techniques

are viable relationship implementations. The second one, the MCP system,

was actually implemented more often than the FK system. This is perhaps

because from a hierarchical standpoint it is easier to see the hierarchy.

You could implement either (or both) relationships to make this a hierarchical

database. Please remember that this illustration is just skeletal. In

real life, there would likely be far more fields in the records for the person

and for the sport or location. Also in real databases, one expects thousands,

if not millions, of records. If you could implement the relationship

between person and sports only one way, which of these systems (MCP or

FK) would work best if there were 1 million person-sport combinations?

The answer to this would likely depend on how many sports each person

played and how variable the number of sports was. For example, if no person

played more than five sports, the MCP system would work quite well.

If, on the other hand, the number of sports played was highly variable

(one person plays 1 or 2 sports, and some play 100), then the FK system

might be better because the FK system only keeps a parent reference, and

the MCP system with this high variability of pointers in the parent might

become cumbersome.

2.4.1.1 The Hierarchical Model with a Linked List

Having used the MCP/FK system to construct a hierarchical set of data,

we now present a second hierarchical model. The MCP system has some

drawbacks regardless of which direction one approaches the relationship

Person (Parent record)

Sport Sport Sport

(Child Records)

FIGURE 2.2

A hierarchy of persons and sports with parent and child pointers.

26 • Database Design Using Entity-Relationship Diagrams

(as MCP, FK, or both). For example, suppose you implemented the system

with the child pointers in the parent record (MCP), and there were more

child records than were planned. Suppose the system was not person and

sports, but students at a school and absences. The student would be the

parent, and the absence records would be the child. Now, suppose you

designed this system with an MCP relationship so that a student could

have up to 20 absences. What happens when the student is absent for the

21st time? One of two things has to happen: (a) The MCP system would

have to be modified to include some kind of overflow; or (b) some other

hierarchical system would have to be used. We could, of course, implement

this as an FK system and ignore the MCP part entirely. Or, we could

implement a different system, and that is what we illustrate now.

The following file system uses a “linked list” or “chain” system to implement

the relationship between parent and child. This system is similar to

both of the schemes discussed. With the same data, the records would set

up like this:

Parent (link to 1st child)

and within the child records:

Child (link to next child)

Here is the data from above with this type of arrangement:

PERSON(record address, name, first sport)

With data:

1. Brenda (101)

2. Richard (103)

3. Abbie (106)

SPORTS(sport, location, link to next sport for that person)

With data:

101, tennis, city courts, 102

102, golf, municipal links, 999

103, golf, municipal links, 104

104, snorkeling, Pensacola bay, 105

105, running, UWF track, 999

106, downhill skiing, Ski Beech, 999

Here, 999 means “no next link.”

Figure 2.3 illustrates a linked list parent-to-child pointing scheme. In

this system, we have a link from parent to child that we did not have with

the FK system alone. Furthermore, the records in both the parent and the

Data and Data Models • 27

child are uniform. Both the parent and the child records contain only one

pointer. Also in this system, it would not matter whether a person played

1 sport or 100—the system works well if the number of child records is

unknown or highly variable. If you would argue that finding a specific

child record among 200,000 sport records might be time consuming, you

are 100% correct. If you argue that the system is fragile and that if one link

is lost the whole thing goes down, you are correct again. While this linked

list system may look somewhat fragile, it formed the basis for several of

the most successful commercial databases. As you might expect, enhancements

to the basic linked list included things like direct links back to the

parent, forward and backward links, links that skipped along the chain in

one direction and not in the other (coral rings). All these enhancements

were the fodder of databases in the 1970s.

2.4.1.2 Relationship Terminology

Having seen how to implement relationships in hierarchical databases,

we need to tighten some language about how relationships are formed.

Relationships in all database models have what are called structural

constraints. A structural constraint consists of two notions: cardinality

and optionality. Cardinality is a description of how many of one record

type relate to the other and vice versa. Suppose we implement a database

about the personnel of a company. We have an employee (parent) and the

employee’s dependents (child). In our company, if an employee can have

multiple dependents and the dependent can have only one employee parent,

we would say the cardinality of the relationship is one to many: One

employee relates to many dependents, abbreviated 1:M. If the company

were such that employees might have multiple dependents and a dependent

might be claimed by more than one employee, then the cardinality

Person

(Parent record)

Sport Sport Sport (Child Records)

FIGURE 2.3

A hierarchy of persons and sports with a parent-to-child linked list.

28 • Database Design Using Entity-Relationship Diagrams

would be many to many: Many employees relate to many dependents,

abbreviated M:N (as in M of one side relates to N on the other side, and M

and N are generally not equal).

Optionality refers to whether one record may or must have a corresponding

record in the other file. If the employee may or may not have dependents,

then the optionality of the employee-to-dependent relationship is

optional or partial. If the dependents must be “related to” employee(s) (and

every employee must have dependents), then the optionality of dependent

to employee is mandatory or full.

Further, relationships are always stated in both directions in a database

description. We would say

Employees may have zero or more dependents,

and

Dependents must be associated with one and only one employee.

Note the employee-to-dependent, one-to-many cardinality and the

optional/mandatory nature of the relationship. We return to this language,

but it is easy to see that the way a database is designed depends on

the description of it. If the description is clear and unambiguous, then the

likely outcome of database design is far more predictable.

2.4.1.3 Drawbacks of the Hierarchical Model

All relationships between records in a hierarchical model have a cardinality

of one to many or one to one, but never many to one or many to many.

So, for a hierarchical model of employee and dependent, we can only have

the employee-to-dependent relationship as one to many or one to one; an

employee may have zero or more dependents. In the hierarchical model,

you could not have dependents with multiple parent-employees (unless we

introduce redundant recording of dependents).

As we illustrated, the original way hierarchical databases were implemented

involved choosing some way of physically “connecting” the parent

and the child records. Imagine you have looked up information on an

employee in an employee filing cabinet and you want to find the dependent

records for that employee in a dependent filing cabinet. One way to implement

the employee-dependent relationship would be to have an employee

record point to a dependent record and have that dependent record point

to the next dependent (a linked list of child records). For example, you

find employee Jones. In Jones’s record there is a notation that Jones’s first

Data and Data Models • 29

dependent is found in the dependent filing cabinet, file drawer 2, record

17. The “file drawer 2, record 17” is called a pointer and is the connection

or relationship between the employee and the dependent. Now, to take

this example further, suppose the record of the dependent in file drawer

2, record 17, points to the next dependent in file drawer 3, record 38, then

that dependent points to the next dependent in file drawer 1, record 82.

As we pointed out in the person-sports model, the linked list approach

to connecting parent and child records has advantages and disadvantages.

For example, some advantages would be that each employee has to maintain

only one pointer, and that the size of the linked list of dependents

is theoretically unbounded. Drawbacks would include the fragility of

the system in that if one dependent record is destroyed, then the chain

is broken. Further, if you wanted information about only one of the child

records, you might have to look through many records before you found

the one you were looking for.

There are, of course, several other ways of implementing the parentchild

link. The point here is that some system has to be chosen to be implemented

in the underlying database software. Once the linking system is

chosen, it is fixed by the software implementation; the way the link is done

has to be used to link all child records to parents regardless of how inefficient

it might be for one situation.

There are three major drawbacks to the hierarchical model:

1. Not all situations fall into the one-to-many, parent-child format.

2. The choice of the way in which the files are linked has an impact on

performance both positively and negatively.

3. The linking of parents and child records is done physically. If the

dependent file were reorganized, then all pointers would have to be

reset.

2.5 THE NETWORK MODEL

Each of the methods presented for the hierarchical database has advantages

and disadvantages. Since the network model allows M:N relationships,

we want to implement a system of pointers for multiple parents for

each child record. How would this be handled? You would most likely

have to have multiple child-forward links with either a linked list or an

MCP system in the parent, parent pointers in the child records (perhaps

30 • Database Design Using Entity-Relationship Diagrams

more than one), and possibly some other enhancement to a pointer

scheme. The network model alleviated a major concern of the hierarchical

model because in the network model, one was not restricted to having

one parent per child; a many-to-many relationship or a many-to-one

relationship was acceptable. To give an example of a network approach,

let us revisit the Person-Sports example but now allow a sports record

to be connected to more than one person. Here is some sample data like

those presented with more persons and more sports and using an MCP

system in both directions:

First, the data:

Brenda: tennis, city courts; golf, municipal links

Richard: golf, municipal links; snorkeling, Pensacola

bay; running, UWF track

Abbie: downhill skiing, Ski Beech

David: snorkeling, Pensacola bay; golf, municipal

links

Kaitlyn: curling, Joe’s skating rink; downhill skiing,

Ski Beech

Chrissy: cheerleading, Mountain Breeze High; running,

UWF track

Now, suppose we diagram this conglomeration of data with pointers (we

use record numbers in each “file”):

PERSON(record_number, name, (sports))

SPORTS(record_number, sport, location, (who plays))

In each case, the part of the file description in parentheses that looks like

(who plays) is called a repeating group, meaning that it can have multiple

values. Our small, albeit perplexing, database looks like this:

PERSON (record_number, name, (sports))

With data:

1. Kaitlyn (107, 106)

2. Abbie (106)

3. Brenda (102, 101)

4. Chrissy (108, 105)

5. Richard (103, 104, 105)

6. David (104, 102)

SPORTS (record_number, sport, location, (who plays))

With data:

Data and Data Models • 31

101 tennis, city courts (3)

102 golf, municipal links (3, 6)

103 golf, municipal links (5)

104 snorkeling, Pensacola bay (5, 6)

105 running, UWF track (4, 5)

106 downhill skiing, Ski Beech (2, 1)

107 curling, Joe’s skating rink (1)

108 cheerleading, Mountain Breeze High (4)

The network with pointers in both directions is illustrated in Figure 2.4.

The complexity of the network database is exponentially greater than

that of the hierarchical one. The database just illustrated could have been

implemented as a series of linked child/parents or some other combination

of links and pointers. The second and third drawbacks of hierarchical

databases spill over to network databases. If one were to design a file-based

database system from scratch, one would have to choose some method of

physically connecting or linking records. This choice of record connection

then locks us into the same problem as before: a hardware-implemented

connection that has an impact on performance both positively and negatively.

Further, as the database becomes more complicated, the paths of

connections and the maintenance problems become exponentially more

difficult to manage.

As a project, you could create the Person-Sports database with a few more

records than given in the example using linked lists. At first, you might

think this to be a daunting exercise, but one of the most popular database

systems in the 1970s used a variant of this system. The parent and child

records were all linked with linked lists going in two directions—forward

and backward. The forward/backward idea was to speed up finding child

records such that one could search for children by going either way. An

enhancement of this system would be to use forward-pointing linked lists

with a backward-pointing chain of links, but with the backward chain

PersonA PersonB

SportW SportX SportY SportZ

FIGURE 2.4

A network of persons and sports with MCP and parent pointers.

32 • Database Design Using Entity-Relationship Diagrams

skipping every n records, where the optimal n turns out to be the square

root of the number of entries in the chain.

2.6 THE RELATIONAL MODEL

Codd (1970) introduced the relational model to describe a database that

did not suffer the drawbacks of the hierarchical and network models (i.e.,

physical links and hardware-bound restrictions). Codd’s premise was that

if we ignore the way data files are connected and arrange our data into simple

two-dimensional, unordered tables, then we can develop a calculus for

queries (questions posed to the database), and we can focus on the data as

data, not as a physical realization of a logical model. Codd’s idea was truly

logical in that one was no longer concerned with how data was physically

stored. Rather, data sets were simply unordered, two-dimensional tables

of data. To arrive at a workable way of deciding which pieces of data went

into which table, Codd proposed “normal forms.” To understand normal

forms, we must first introduce the notion of functional dependencies. After

we understand functional dependences, normal forms follow.

As a historical note, when Codd introduced his relational model, it

was deemed by most people as “theoretical only.” At the time, a typical

mainframe computer might have 64K of internal memory, and a good

set of hard disks might have as much as several megabytes of storage. To

top that off, the computer typically took up a large room that required

separate air handling, special architectural features like raised floors,

and enhanced power grids. Remember that all the “computing power”

was shared by everyone who had to have computing. In a company, users

might include accounting, purchasing, personnel, finance, and so on.

For even one of those units to be able to run the relational model in the

early 1970s would have required vast dedicated resources. As computers

became more ubiquitous, less expensive, smaller, and so on, the amount

of memory available both internally and externally became cheaper and

had far greater capacity. The relational model “grew up” with the evolution

of computers in the 1980s. We expand the notion of relational database

in the next chapter.

Data and Data Models • 33

CHECKPOINT 2.3

1. What are the three main data models we have discussed?

2. Which data model is mostly used today? Why?

3. What are some of the disadvantages of the hierarchical data model?

4. What are some of the disadvantages of the network data model?

5. How are all relationships (mainly the cardinalities) described in the hierarchical

data model? How can these be a disadvantage of the hierarchical

data model?

6. How are all relationships (mainly the cardinalities) described in the

network data model? Would you treat these as advantages or disadvantages

of the network data model?

7. What are structural constraints?

8. Why was Codd’s promise of the relational model better?

2.7 CHAPTER SUMMARY

In this chapter, we covered concepts that are essential to the understanding

and design of a database. We also covered data models from a historical

perspective—the hierarchical and network models and then introduction

of the relational model. This chapter should serve more as background to

the material for the rest of the book.

BIBLIOGRAPHY

Codd, E. F. 1970. A relational model of data for large shared data banks. Communications

of the ACM, 13(6): 377–387.