DVD Contents: Database Design, 2nd Edition 
HomeC  Welcome
contentsC  Contents
  tois  TOIS
  toit  TOIT
  adc  ADC
  apccm  APCCM
  codasyl  CODASYL
  interview  Interview
  books  Books
  dblp  DBLP
authorsC  Author List
(Reprinted from http://www-db.stanford.edu/pub/gio/dbd/acm/toc.html.)

Gio Wiederhold: Database Design, 2nd Edition. 
Table of Contents

© 1995, 1997, 2001 (Copyright Notice) by Gio Wiederhold
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.


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.


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

Chapter Title (click for the .pdf  file) page numbers (click for overview) status |
0 Table of Contents -- this file pages vii-x html |
0 Preface pages x1-xvi pdf |
Part I Physical Design and Performance
1 Introduction and Definitions pages 1-26 pdf |
2 Hardware and its Parameters pages 27-81 pdf |
3 File Structures pages 73-198 pdf |
4 Hybrid Files pages 167-248 pdf |
5 Overall File-System Evaluation pages 249-290 pdf |
6 Techniques pages 291-349 pdf |
Part II Database Structures and Design
7 Database Structure pages 345-405 pdf |
8 Schemas pages 405-448 pdf |
9 Database Implementation pages 449-520 pdf |
10 Query Languages pages 521-542 pdf |
Part III Security and Operation
11 Methods to Gain Reliability pages 543-578 pdf |
12 Protection of Privacy pages 579-612 pdf |
13 Integrity of Databases pages 613-645 pdf |
14 Coding pages 645-668 pdf |
15 Database Operation and Management pages 669-678 pdf |
A Appendix A: Index for Alternate Technology pages 679-688 pdf |
B Appendix B: Database Systems pages 689-698 pdf |
C Appendix C: Symbols used pages 699-701 pdf |
Bib Bibliography pages 703-729 pdf, but incomplete |
Bib source Bibliography source annotated BibTex source Copied from Html Master at Stanford |
Index Comprehensive Index pages 735-751 pdf
Answers Answers to the Exercises were separate. not yet available

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

0: Preface, pages iv-ix

Part I: Physical Design and Performance

Chapter 1: Introduction and Definitions, pages 1-26

1-0 Introduction (definitions) 1|
1-1Files(the basis for databases) 2|
1-2Computations on a Database(definitions) 5|
1-3A Hierarchical View of Data(conceptual layers) 8|
1-4Current Practice(data before databases) 12|
1-5Descriptions(data and control flow) 15|
1-6Binding(getting it all to execute) 17|
1-7Classification of Operating Systems(support for database transactions) 19|
1-8Applications(why we need databases) 23 |
1-9Review 24|
1--Background and References(listed in the bibliography) 25|
1--Exercises 26|

Chapter 2: Hardware and its Parameters, pages 27-81.

2-0Introduction(hardware components) 27|
2-1Basic Hardware Choices(tapes, disks, etc) 28|
2-2Basic Hardware Parameters(computing device performance) 38|
2-3Blocks and Buffers(units for moving data) 53|
2-4Summary of Hardware Parameters(commonality and differences among devices) 65|
2-5Storage and Architecture(combining the components and its effects) 66|
2--Background and References (listed in the bibliography) 79|
2--Exercises 80|

Chapter 3: File Structures, pages 73-198

3-0Introduction (defining file techniques) 73|
3-1The Pile (fundamental, like data on your desk) 82|
3-2The Sequential File (for tapes and ordered stuff) 89|
3-3 The Indexed-Sequential File(adding fast access) 98 |
3-4The Indexed File(giving up on keeping order) 119|
3-5The Direct File(hashing) 135|
3-6The MultiRing File(providing navigation) 163|
3-7Sorting(an important function) 182|
3-8Review of Files(this was a big chapter) 187|
3--Background and References (listed in the bibliography) 190|
3--Exercises 192|

Chapter 4: Hybrid File Organizations, pages 167-248

4-0Introduction(adaptions and combinations) 167|
4-1Simple Files (simple versions of fundamental techniques) 169|
4-2 Multilevel Index Structures(fancy and special indexes) 178|
4-3An Implementation of an Ind.Seq. File (details of IBM VSAM) 430|
4-4Tree-Structured Files (making indexes meaningful) 440|
4-5Hierarchically Structured Data (files that are nearly databases, MUMPS) 209|
4-6 Methods based on Direct Access(fancy hashing) 220|
4-7Options of the Complex Ring-Rrganization (fancy navigation) 231|
4-8Files Using Virtual Storage (using operating system capabilities) 239|
4-9Phantom Files(keeping only the indexes) 242|
4--Background and References (listed in the bibliography) 243|
4--Exercises 245|

Chapter 5: Overall File-System Evaluation, pages 249-290

5-0Introduction (predicting system performance) 249|
5-1Estimation of System Usage (performance depends in how its used) 251|
5-2Analysis of System Benefits (faster is how much better) 254|
5-3Database Storage Requirements (size and number of disks) 262|
5-4Access 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 290|

Chapter 6: Techniques, pages 291-349

6-0Introduction (Analysis for large systems) 291|
6-1Statistical Techniques (dealing with large numbers and their variation) 292|
6-2Simulation(when analysis is inadequate) 311|
6-3Queues and Scheduling Techniques (getting the most from a system) 314|
6-4 Operations Reserach in Database Design (a useful tool set) 325|
6-5Storage Allocation (where data are put is important) 335|
6-- Background and References (listed in the bibliography) 341|
6-- Exercises 342|

Part II: Database Structures and Design

Chapter 7: Database Structure, pages 345-405

7-iIntroduction(why model) 345|
7-0Structure Definition(modeling concepts) 346|
7-1View Models(modeling for the user, normalization) 349|
7-2Semantics of Relations(references among data) 344|
7-3Building Blocks for Models(entity types) 361|
7-5Operations on Relations(the algebra and its effects) 377|
7-6The Design of a Database Models (putting it all together) 389|
7--Background and References (listed in the bibliography) 446|
7--Exercises 448|

Chapter 8: Schemas, pages 405-448

8-0Introduction(a schema is the crucial component) 405|
8-1Defining the Elements for a Database (data dictionaries) 406|
8-2The Schema and its Used (examples and pseudo-code) 414|
8-3Defining the Structure of a Database (connecting multiple relations) 421|
8-4 Manipulation of the Schema(DBMS program flow) 433|
8-5Subschemas(returning views to the user) 439|
8-6Structure, Schema. and Usage(review) 443|
8--Background and References (listed in the bibliography) 446|
8--Exercises 448|

Chapter 9: Database Implementation, pages 449-520

9-0Introduction (DB systems versus file systems) 449|
9-1Issues in Database Implementation (DBMS functionality and concepts) 451|
9-2Relational Calculus Implementation  (RDBMS: SQL and examples) 456|
9-3Relational Algebra Implementation (base operations: Union, Join, Project, etc.) 470|
9-4Hierarchical databases (implementing trees, system examples) 477|
9-5Databases with Network Capability (the CODASYL specification) 489|
9-6Interlinked Hierarchies (The IBM IMS system) 505|
9-7Advances in Implementation (distribution and performance) 514|
9--Background and References (listed in the bibliography) 517|
9--Exercises 970|

Chapter 10: Query Languages, pages 521-541

10-0Introduction(information retrieval) 521|
10-1Data Constellations(data and results) 522|
10-2Categories of Information Retrival (complete or interactive) 525|
10-3Query 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 1542|

Part III: Security and Operation

Chapter 11: Methods to Gain Reliability, pages 543-578

11-0Definitions (reliability precedes protection and security) 543|
11-1Reliability(measures) 544|
11-2Redundancy (needed for error correction) 547|
11-3Transaction Reliability (definitions to make it work) 555|
11-4Activity logging (implemeting data redundancy) 562|
11-5A Scenario for Recovery (restoring the good, undoing the bad) 538|
11--Background and References (listed in the bibliography) 576|
11--Exercises 577|

Chapter 12: Protection of Privacy, pages 579-612

12-0Introduction (what can we expect in terms of privacy) 579|
12-1Components of the Privacy Pr. Problem (data versus accessors) 581|
12-2The Accessor (types of good guys and bad guys) 584|
12-3Types of Data Access (read, read and write, append only) 587|
12-4The Objects to be Locked (organizing the data) 590|
12-5The Envelope of Protection (defining the firewall) 592|
12-6Access Key Organization (organizing the rights for the good guys) 593|
12-7Cryptography (the primary tool to keep bad guys out) 600|
12-8Anonymity and Pollution (unconventional methods) 608|
12--Background and References (listed in the bibliography) 1550|
12--Exercises 1560|

Chapter 13: Integrity of Databases, pages 613-645

13-0Introduction(defining correctness) 613|
13-1Locking (to prevent damaging interference) 615|
13-2Hibernation and Deadlock (excessive prevention) 628|
13-3Maintenance of Integrity (working to keep data correct) 641|
13---Background and References (listed in the bibliography) 644|
13---Exercises 645|

Chapter 14: Coding, pages 645-668

14-0Introduction (coding is crucial to make data useful) 645|
14-1Representation of Knowledge (translating findings into computers) 646|
14-2Machine Representation (capabilities and alternatives) 647|
14-3Compression of Data (saves space and increases throughput) 657|
14--Background and References (listed in the bibliography) 666|
14--Exercises 667|

Chapter 15: Database Operation and Management, pages 669-678

15-0Introduction (getting started and keping it going) 669|
15-1Development of a Database (planning and analysis) 670|
15-2Maintenance of a Database (the biggest cost: operations and evolution) 672|
15-3The Database Adminstrator (what can be expected) 676|
15--Background and References (listed in the bibliography) 678|

Appendix A: Index For Alternate Terminology, pages 679-688

Cross references for terms with overlapping meaning used by manufacturers and other authors.

Appendix B: Appendix B: Database Systems, pages 689-698

Comprehensive listing of (then) current prototype or commercial DBMSes.

Appendix C: Appendix C: Symbols used, pages 699-701

Bibliography: Bibliography, pages 703-734

A selected subset of a very comprehensive bibliography.

Index: Comprehensive Index, was pages 735-751.

Answers : Answers to Exercises, was separate.

  Copyright © 2007 by the Association for Computing Machinery, Inc. (ACM)
E-mail contributions, questions, comments and corrections to anthology@acm.org