INSTRUCTOR’S MANUAL
TO ACCOMPANY
40th Anniversary Edition
DATABASE PROCESSING
Fundamentals, Design, and Implementation
15th Edition
Appendix G
Physical Database Design and Data Structures for
Database Processing
David M. Kroenke | David J. Auer | Scott L. Vandenberg | Robert C. Yoder
❖ CHAPTER OBJECTIVES
• To understand the basic isssues in physical database design
• To define the term data structures.
• To define and illustrate the terms flat file, sequential list, linked list, and index.
• To define and illustrate B-Tree multilevel indexes.
❖ ERRATA
There are no known errors at this time. Any errors that are discovered in the future will
❖ TEACHING SUGGESTIONS
• The material in this appendix defines and illustrates physical data structures that
support the relational (and other) DBMSs. Before E.F. Codd developed the
relational model, flat file, hierarchical, and network DBMSs also used these
structures.
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-3
• Review Questions G.21-G26 are more complex, and ask the students to apply
the concepts by developing processing algorithms based on the structures. You
should use these questions if you believe that your students having a thorough
understanding of these structures is essential to your database class. In most
courses, however, the first twenty Review Questions should be sufficient.
• Of course, even in a relational DBMS, understanding these tradeoffs can be very
useful, so any DBA concerned with perfomance of queries and updates can
benefit from this material.
❖ ANSWERS TO REVIEW QUESTIONS
G.1. Define a flat file. Give an example (other than one in this text) of a flat file and an
example of a file that is not flat.
A flat file is a file in which the records have no repeating groups. Examples will vary with
students, but one might be an Employee file containing no repeating groups; a non-flat file might
be an Employee file containing repeating fields for employee deductions.
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-4
G.2. Show how sequential lists can be used to maintain the file in Review Question G.1 in two
different orders simultaneously.
Two files are required, one sorted on Emp#, the other on Name:
Emp#
Name
Title
107
Ahalt
Instructor
109
Wampler
Instructor
215
Meyers
Professor
350
Professor
Emp#
Name
Title
107
Ahalt
Instructor
350
Professor
215
Meyers
Professor
109
Wampler
Instructor
Savings 45
Savings 50
215
Meyers
350
Savings 50
Appendix G – Physical Database Design and Data Structures for Database Processing
G.3. Show how linked lists can be used to maintain the file in Review Question G.1 in two
different orders simultaneously.
Store the file in any order, and use linked lists to keep the file in order by Emp# and Name:
Relative
Record
Number
Emp#
Name
Emp#
Link
Name
Link
1
107
Ahalt
Instructor
2
4
2
109
Wampler
Instructor
3
0
3
215
Meyers
Professor
4
2
4
350
Professor
0
3
G.4. Show how inverted lists (indexes) can be used to maintain the file in Review Question
G.1 in two different orders simultaneously.
The data would be stored as in Question G.3, but there would be no link fields. There would be
Emp#
Relative
Record
Name
Relative
Record
107
1
Ahalt
1
109
2
4
215
3
Meyers
3
350
4
Wampler
2
G.5. Define the term tree. Offer an example tree structure (other than one in this text).
A tree is a set of records and one-to-many relationships in which a child can have at most one
parent. An example is a checking account (parent) that has many deposits (children) and many
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-6
G.6. Give an occurrence of the tree in Review Question G.5.
One occurrence of the tree would be:
G.7. Represent the occurrence in Review Question G.6 using linked lists.
Relative
Record
Number
Record Contents
Deposit
Link
Field
Check
Link
Field
2
DEP
02 SEP 13
5
0
3
05 SEP 14
0
4
4
23 SEP 14
0
0
5
DEP
05 OCT 14
0
0
G.8. Represent the occurrence in Review Question G.6 using indexes.
Relative
Record
Number
Record Contents
1
ACCOUNT 1234
2
DEP
02 SEP 13
3
05 SEP 14
4
23 SEP 14
5
DEP
05 OCT 14
Record
Record
Record
2
1
3
5
1
4
ACCOUNT 1234
DEP | 188 | 02 SEP 13 | $500.00
CHK | 455 | 05 SEP 14 | $35.00
DEP | 189 | 05 OCT 14 | $250.00
CHK | 456 | 23 SEP 14 | $125.00
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-7
G.9. Define a simple network and give an example structure (other than one in this text).
A simple network is a set of records and relationships in which all relationships are one-to-many,
G.10. Give an occurrence of the simple network in Review Question G.9.
An occurrence of the simple network would be:
In# 00389
In# 00386
In# 00387
In# 00388
S02
C0015
C0016
In# 00385
C0012
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-8
G.11. Represent the occurrence in Review Question G.10 using linked lists.
Relative
Record
Number
Record Contents
Salesperson
Link
Field
Customer
Link
Field
1
S01
6
G.12. Represent the occurrence in Review Question G.10 using indexes.
Relative
Record
Number
Record Contents
Salesperson
Link
Field
Customer
Link
Field
1
S01
6
2
S02
7
3
C0012
7
4
C0015
6
5
C0016
8
6
In# 00385
8
9
7
In# 00386
0
8
In# 00387
9
9
In# 00388
0
0
In# 00389
0
0
6
3
7
8
4
6
9
4
9
7
5
8
5
2
S02
7
3
C0012
7
4
C0015
6
5
C0016
8
6
In# 00385
8
9
7
In# 00386
0
8
In# 00387
9
In# 00389
0
0
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-9
G.13. Define complex network. Offer an example of a complex network structure (other than
one in this text).
A complex network is a set of records and relationships in which all relationships are many–to–
G.14. Give an occurrence of the complex network in Review Question G.13.
One occurrence of the complex network would be:
A02
P02
P03
A03
P04
G.15. Decompose the complex network in Review Question G.14 into a simple network and
represent an occurrence of it using indexes.
A01
P01
ACTOR
PLAY
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-10
A03
A03P04
A03P01
A03P02
A03P03
Relative
Record
Number
Record Contents
1
A01
2
A02
3
A02
4
P01
5
P02
6
P03
7
P04
8
A01P01
9
A01P02
A01P04
A02P01
A02P03
A02P04
A03P01
A03P02
A03P03
A03P04
A01P01
P01
A02P03
A02
P04
A02P04
A01
A01P02
A01P04
A02P01
P02
P03
Appendix G – Physical Database Design and Data Structures for Database Processing
Page G-11
Actor
Record
Actor-Play
Record
Play
Record
Actor-Play
Record
1
8
4
8
1
9
4
11
G.16. Explain the difference between primary and secondary keys.
A primary key is normally used to determine where a record is stored. The primary key is the key
G.17. Explain the difference between unique and nonunique keys.
With a unique key only one record can have a specific key value; each key value must be unique
G.18. Give an example of a file containing a unique secondary key (other than one in this text).
Represent an occurrence of that file using an index on the secondary key.
Relative
Record
Number
Number
Name
Major
1
1234
Joanie Wampler
Acct
2
2311
Jon Miley
Comp
3
3451
Jersey Eng
Acct
4
3561
Sandy Merrow
Comp
5
4566
Bob Adams
Acct
1
10
4
14
2
11
5
9
2
12
5
15
2
13
6
12
3
14
6
16
3
15
7
10
3
16
7
13
3
17
7
17
Appendix G – Physical Database Design and Data Structures for Database Processing
Unique secondary key represented via inverted list:
Name
Relative
Record
Number
Bob Adams
5
Jersey Eng
3
Sandy Merrow
4
Jon Miley
2
Joanie Wampler
1
G.19. Define a nonunique secondary key for the file in Review Question G.18. Represent an
occurrence of that file using a linked list on the secondary key.
The nonunique secondary key is Major.
Relative
Record
Number
Number
Name
Major
Major
Link
1
1234
Joanie Wampler
Acct
3
2
2311
Jon Miley
Comp
4
3
3451
Jersey Eng
Acct
5
4
3561
Sandy Merrow
Comp
0
5
4566
Bob Adams
Acct
0
G.20. Perform the same task as in Review Question G.19, but use an index to represent the
secondary key.
Major
Acct
1234
3451
4566
Comp
2311
3561