Gio Wiederhold: Database Design, 2nd Edition.
Table of Contents
Copyright was re-assigned by McGraw-Hill 7 April 1995 from their 1988 copyright
to Gio Wiederhold.
Recreated August 2000-Feb 2001.
This material can be freely used as long as the copyright is acknowledged.
Notes for the Recreated Version
This version, for distribution by ACM, was recreated in part from the original
TEX source files and macros, and in part, where the original files could
not be recovered from archive tapes, from a planned, but unpublished 3rd
edition. The figures, originally drawn at McGraw-Hill, were scanned
in and converted into MAC Pict formats. The sizes vary somewhat from the
orignals. The typesetting was redone using
TEXTURES (by Blue Sky Software, Portland OR) and converted to PDF format
with Adobe Distiller.
Because of these changes, and changes in font standards over the
intervening years, this version is not a literal image of the original
source as published by McGraw-Hill in 1983. It does contain all
the material originally published. A small number of typos were
corrected and there is some additional material from the third
edition. All chapters start with their original page numbers, and all
figure numbers and most equation, example, and table numbers remain
identical. Some chapters have grown in size and will have overlapping
page numbers with their successor chapters.
The index could not
be automatically recreated and was retyped by Voy Wiederhold. However,
because of the changes in the text some of the reference page numbers
in the index will not match the page for the referenced entry in this
text as it now is distributed. Since the text has grown somewhat
in size, referenced topics may appear later in the text than indicated
in the index. The corrected section numbers below can help in matching
index pages numbers to actual chapter pages.
Relevance
Although the first edition of this book appeared
in 1977, and the second edition in 1983, there is still much relevant
material here which does not appear in subsequent works. A small
number of copies are still being sold every year by McGraw-Hill.
Specifically, this book follows a bottom-up approach, starting with
hardware and file parameters. These parameters are utilized
throughout. It hence allows the reader to predict the
performance of alternative designs for new databases and database
systems with good -- engineering precision -- accuracy. The need for
such analyses has diminished since most databases are now built on
commercial database system software. Use of large packages allows few
alternatives, little insight, but easier experimentation. This book
has continued to serve the small market where performance is a
concern, novel methods or large scale operations are envisaged,
full-scale experiments are difficult, and
simplistic assumptions will fail.
Another feature of this book is conceptually helpful. We do not
present the structural features of relational, hierarchical, and network databases
as competing which other, but rather consider them in a continuum of increased
binding choices. This approach is again helpful when complex systems
are to be analyzed, since the tradeoffs made in binding choices are crucial
when performance and long-term maintenance issues must be balanced.
There has been, of course, much progress since this book has
appeared. Databases are now part of everyone's computing
concepts, and their use does not require a deep technological
competence. My own subsequent research has focused on intelligent
technology to exploit databases for decision-making. Much
remains to be done do make atabases a true service for
end-users. Some references can be found on my webpages,
at http://www-db.stanford.edu/people/gio.html.
Support
Partial support for recreation of this book was
provided by NSF, through their Digital Library II program. Dan
Siroker scanned the pictures in, for subsequent integration into the
text. Arthur Keller provided directions for the resetting process on
the Macintosh, and Donnel Gray converted and inserted the figures.
Richard Snodgrass and Michael Ley provided motivation and advice on
how to do the conversion right. The remaining errors are my
responsibility; as Donald Knuth once told me `one cannot write without
making errors'; do let me know about any errors and problems with the
material.
Gio Wiederhold (gio@cs.stanford.edu), Feb. 2001.
Brief Table of Contents with HTML pointers
Detailed Table of Contents
The current version (January 2001) does not
have internal anchor points into the chapters.
Hence, any clicks will get you to the beginning of a chapter.
Chapter / section, Topic (annotation), Page numbers
Part I: Physical Design and Performance
1-0 |
Introduction |
(definitions) |
1 | | |
1-1 | Files | (the basis for databases) |
2 | | |
1-2 | Computations on a Database | (definitions) |
5 | | |
1-3 | A Hierarchical View of Data | (conceptual layers) |
8 | | |
1-4 | Current Practice | (data before databases) |
12 | | |
1-5 | Descriptions | (data and control flow) |
15 | | |
1-6 | Binding | (getting it all to execute) |
17 | | |
1-7 | Classification of Operating Systems | (support for database transactions) |
19 | | |
1-8 | Applications | (why we need databases) |
23 |
| |
1-9 | Review | |
24 | | |
1-- | Background and References | (listed in the bibliography) |
25 | | |
1-- | Exercises | (answers for most problems) |
26 | | |
2-0 | Introduction | (hardware components) |
27 | | |
2-1 | Basic Hardware Choices | (tapes, disks, etc) |
28 | | |
2-2 | Basic Hardware Parameters | (computing device performance) |
38 | | |
2-3 | Blocks and Buffers | (units for moving data) |
53 | | |
2-4 | Summary of Hardware Parameters | (commonality and differences among devices) |
65 | | |
2-5 | Storage and Architecture | (combining the components and its effects) |
66 | | |
2-- | Background and References |
(listed in the bibliography) |
79 | | |
2-- | Exercises |
(answers for most problems) |
80 | | |
3-0 | Introduction |
(defining file techniques) |
73 | | |
3-1 | The Pile |
(fundamental, like data on your desk) |
82 | | |
3-2 | The Sequential File |
(for tapes and ordered stuff) |
89 | | |
3-3 |
The Indexed-Sequential File | (adding fast access) |
98 |
| |
3-4 | The Indexed File | (giving up on keeping order) |
119 | | |
3-5 | The Direct File | (hashing) |
135 | | |
3-6 | The MultiRing File | (providing navigation) |
163 | | |
3-7 | Sorting | (an important function) |
182 | | |
3-8 | Review of Files | (this was a big chapter) |
187 | | |
3-- | Background and References |
(listed in the bibliography) |
190 | | |
3-- | Exercises |
(answers for most problems) |
192 | | |
4-0 | Introduction | (adaptions and combinations) |
167 | | |
4-1 | Simple Files |
(simple versions of fundamental techniques) |
169 | | |
4-2 |
Multilevel Index Structures | (fancy and special indexes) |
178 | | |
4-3 | An Implementation of an Ind.Seq. File |
(details of IBM VSAM) |
430 | | |
4-4 | Tree-Structured Files |
(making indexes meaningful) |
440 | | |
4-5 | Hierarchically Structured Data |
(files that are nearly databases, MUMPS) |
209 | | |
4-6 |
Methods based on Direct Access | (fancy hashing) |
220 | | |
4-7 | Options of the Complex Ring-Rrganization |
(fancy navigation) |
231 | | |
4-8 | Files Using Virtual Storage |
(using operating system capabilities) |
239 | | |
4-9 | Phantom Files | (keeping only the indexes) |
242 | | |
4-- | Background and References |
(listed in the bibliography) |
243 | | |
4-- | Exercises |
(answers for most problems) |
245 | | |
5-0 | Introduction |
(predicting system performance) |
249 | | |
5-1 | Estimation of System Usage |
(performance depends in how its used) |
251 | | |
5-2 | Analysis of System Benefits |
(faster is how much better) |
254 | | |
5-3 | Database Storage Requirements |
(size and number of disks) |
262 | | |
5-4 | Access Load and Capability of a File System |
(Transaction performance) |
265 | | |
5-5 |
Cost-Benefit Comparison | (it's a business) |
289 | | |
5-- |
Background and References |
(listed in the bibliography) |
289 | | |
5-- |
Exercises | (answers for most problems) |
290 | | |
Chapter 6: Techniques,
pages 291-349
6-0 | Introduction |
(Analysis for large systems) |
291 | | |
6-1 | Statistical Techniques |
(dealing with large numbers and their variation) |
292 | | |
6-2 | Simulation | (when analysis is inadequate) |
311 | | |
6-3 | Queues and Scheduling Techniques |
(getting the most from a system) |
314 | | |
6-4 |
Operations Reserach in Database Design |
(a useful tool set) |
325 | | |
6-5 | Storage Allocation |
(where data are put is important) |
335 | | |
6-- |
Background and References |
(listed in the bibliography) |
341 | | |
6-- |
Exercises |
(answers for most problems) |
342 | | |
Part II: Database Structures and Design
7-i | Introduction | (why model) |
345 | | |
7-0 | Structure Definition | (modeling concepts) |
346 | | |
7-1 | View Models | (modeling for the user, normalization) |
349 | | |
7-2 | Semantics of Relations | (references among data) |
344 | | |
7-3 | Building Blocks for Models | (entity types) |
361 | | |
7-5 | Operations on Relations | (the algebra and its effects) |
377 | | |
7-6 | The Design of a Database Models |
(putting it all together) |
389 | | |
7-- | Background and References |
(listed in the bibliography) |
446 | | |
7-- | Exercises | (answers for most problems) |
448 | | |
Chapter 8: Schemas, pages
405-448
8-0 | Introduction | (a schema is the crucial component) |
405 | | |
8-1 | Defining the Elements for a Database |
(data dictionaries) |
406 | | |
8-2 | The Schema and its Used |
(examples and pseudo-code) |
414 | | |
8-3 | Defining the Structure of a Database |
(connecting multiple relations) |
421 | | |
8-4 |
Manipulation of the Schema | (DBMS program flow) |
433 | | |
8-5 | Subschemas | (returning views to the user) |
439 | | |
8-6 | Structure, Schema. and Usage | (review) |
443 | | |
8-- | Background and References |
(listed in the bibliography) |
446 | | |
8-- | Exercises |
(answers for most problems) |
448 | | |
9-0 | Introduction |
(DB systems versus file systems) |
449 | | |
9-1 | Issues in Database Implementation |
(DBMS functionality and concepts) |
451 | | |
9-2 | Relational Calculus Implementation |
(RDBMS: SQL and examples) |
456 | | |
9-3 | Relational Algebra Implementation |
(base operations: Union, Join, Project, etc.) |
470 | | |
9-4 | Hierarchical databases |
(implementing trees, system examples) |
477 | | |
9-5 | Databases with Network Capability |
(the CODASYL specification) |
489 | | |
9-6 | Interlinked Hierarchies |
(The IBM IMS system) |
505 | | |
9-7 | Advances in Implementation |
(distribution and performance) |
514 | | |
9-- | Background and References |
(listed in the bibliography) |
517 | | |
9-- | Exercises |
(answers for most problems) |
970 | | |
10-0 | Introduction | (information retrieval) |
521 | | |
10-1 | Data Constellations | (data and results) |
522 | | |
10-2 | Categories of Information Retrival |
(complete or interactive) |
525 | | |
10-3 | Query Formulation |
(language and interaction choices) |
529 | | |
10-4) | Dynamics of Information-retrieval Systems |
(search interaction modes) |
538 | | |
10-- | Background and References |
(listed in the bibliography) |
540 | | |
10-- | Exercises |
(answers for most problems) |
1542 | | |
Part III: Security and Operation
11-0 | Definitions |
(reliability precedes protection and security) |
543 | | |
11-1 | Reliability | (measures) |
544 | | |
11-2 | Redundancy |
(needed for error correction) |
547 | | |
11-3 | Transaction Reliability |
(definitions to make it work) |
555 | | |
11-4 | Activity logging |
(implemeting data redundancy) |
562 | | |
11-5 | A Scenario for Recovery |
(restoring the good, undoing the bad) |
538 | | |
11-- | Background and References |
(listed in the bibliography) |
576 | | |
11-- | Exercises |
(answers for most problems) |
577 | | |
12-0 | Introduction |
(what can we expect in terms of privacy) |
579 | | |
12-1 | Components of the Privacy Pr. Problem |
(data versus accessors) |
581 | | |
12-2 | The Accessor |
(types of good guys and bad guys) |
584 | | |
12-3 | Types of Data Access |
(read, read and write, append only) |
587 | | |
12-4 | The Objects to be Locked |
(organizing the data) |
590 | | |
12-5 | The Envelope of Protection |
(defining the firewall) |
592 | | |
12-6 | Access Key Organization |
(organizing the rights for the good guys) |
593 | | |
12-7 | Cryptography |
(the primary tool to keep bad guys out) |
600 | | |
12-8 | Anonymity and Pollution |
(unconventional methods) |
608 | | |
12-- | Background and References |
(listed in the bibliography) |
1550 | | |
12-- | Exercises |
(answers for most problems) |
1560 | | |
13-0 | Introduction | (defining correctness) |
613 | | |
13-1 | Locking |
(to prevent damaging interference) |
615 | | |
13-2 | Hibernation and Deadlock |
(excessive prevention) |
628 | | |
13-3 | Maintenance of Integrity |
(working to keep data correct) |
641 | | |
13--- | Background and References |
(listed in the bibliography) |
644 | | |
13--- | Exercises |
(answers for most problems) |
645 | | |
Chapter 14: Coding, pages
645-668
14-0 | Introduction |
(coding is crucial to make data useful) |
645 | | |
14-1 | Representation of Knowledge |
(translating findings into computers) |
646 | | |
14-2 | Machine Representation |
(capabilities and alternatives) |
647 | | |
14-3 | Compression of Data |
(saves space and increases throughput) |
657 | | |
14-- | Background and References |
(listed in the bibliography) |
666 | | |
14-- | Exercises |
(answers for most problems) |
667 | | |
15-0 | Introduction |
(getting started and keping it going) |
669 | | |
15-1 | Development of a Database |
(planning and analysis) |
670 | | |
15-2 | Maintenance of a Database |
(the biggest cost: operations and evolution) |
672 | | |
15-3 | The Database Adminstrator |
(what can be expected) |
676 | | |
15-- | Background and References |
(listed in the bibliography) |
678 | | |
Cross references for terms with overlapping meaning used by manufacturers
and other authors.
Comprehensive listing of (then) current prototype or commercial DBMSes.
Bibliography: Bibliography,
pages 703-734
A selected subset of a very comprehensive bibliography.
Full BIBLIOGRAPHY in HTML.