Computer Data-base Organization

Description

COMPUTER DATA-BASE ORGANIZATION A James Martin Book James Martin IBM Systems Research Institute PRENTICE-HALL, INC., Englewood Cliffs, New Jersey Prentice-Hall Series in Automatic Computation Library of Congress Cataloging in Publication Data MARTIN, JAMES Computer data·base organization (Prentice-Hall series in automatic computation) Bibliography: p. 1. Data base management. T. Title. QA76.M324 001.6'442 74-13981 ISBN 0-13-165506-X © 1975 by Prentice-Hall , Inc. Englewood Cliffs, N. J. CONTENTS xiii ... Preface xv ... Index of Basic Concepts PROLOGUE 2 ... (1) Introduction 8 ... (2) Basic Terminology Part I: LOGICAL ORGANIZATION 19 ... (3) What is a Data Base? 31 ... (4) What should be the Objectives of a Data Base Organization? 44 ... (5) Entities and Attributes 53 ... (6) Schemas and Subschemas 66 ... (7) Data Base Management Systems 79 ... (8) Tree Structures 89 ... (9) Plex Structures 100 ... (10) Data Description Languages 112 ... (11) The CODASYL Data Description Language 129 ... (12) IBM's Data Language/1 149 ... (13) Relational Data Bases 169 ... (14) Third Normal Form 179 ... (15) Varieties of Data Independence 188 ... (16) Operations Systems versus Information Systems Part II: PHYSICAL ORGANIZATION 198 ... (17) Criteria Affecting Physical Organization 207 ... (18) Differences Between Physical and Logical Organization 219 ... (19) Pointers 227 ... (20) Chains and Ring Structures 249 ... (21) Addressing Techniques 267 ... (22) Indexed Sequential Organizations 291 ... (23) Hashing 312 ... (24) Physical Representation of Tree Structures 332 ... (25) Physical Representation of Plex Structures 345 ... (26) Multiple-Key Retrieval 365 ... (27) Index Organization 379 ... (28) A Comparison of Multiple-Key Organizations 391 ... (29) Separating Data and Relationships 402 ... (30) Index Searching Techniques 433 ... (31) Data Compaction 449 ... (32) Virtual Memory and Storage Hierarchies 478 ... (33) Inverted File Systems 492 ... (34) Volatile Files 504 ... (35) Fast Response Systems 516 ... (36) Associative Memory Appendix A 525 ... The Mean Number of Probes in a Binary Search Appendix B 528 ... Sample Logical Data Descriptions 536 ... Class Questions 552 ... Index