(
`
`-"( ~ J l ( . ( ' J ) l l I <. ll
`ScJl('Jl-l<'l ·
`I {<,J<ll J()fl<·ll
`I )<ll<·ll><·l~('
`I )c~i~Jl
`
`'
`Second Edition
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 1
`
`

`
`Relati(())na' atahase
`Design
`
`Second Edition
`
`TERRY HALPIN
`
`PRENTICE HALL AUSTRALIA
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 2
`
`

`
`Contents
`
`Foreword
`viii
`Preface to second edition
`
`IX
`
`1
`
`Introduction 1
`
`1.1 Why study database design?
`1.2 Why study object-role modeling? 5
`Some historical background
`12
`1.3
`14
`1.4
`The relevant skills
`Summary
`14
`1.5
`
`2
`
`Information levels 16
`
`2.1
`2.2
`2. 3
`2.4
`
`External, conceptual, logical and internal levels
`The conceptual level 20
`Relational database schemas
`Summary 36
`
`31
`
`16
`
`3 Developing an information system 38
`
`Information systems life cycle
`3.1
`38
`3.2 Overview of conceptual schema design procedure 42
`3.3
`CSDP step 1: From examples to elementary facts
`43
`CSDP step 2: Draw fact types, and populate 59
`3.4
`CSDP step 3: Trim schema; note basic derivations 69
`3.5
`Summary 76
`3.6
`
`4 Uniqueness constraints 79
`
`4.1
`CSDP step 4: Uniqueness constraints; arity check 79
`80
`4.2 Uniqueness constraints on unaries and binaries
`4.3
`Uniqueness constraints on longer fact types
`92
`External uniqueness constraints 98
`4 .4
`4. 5 Key length check 106
`4.6
`Projection-join check 117
`4.7
`Summary 121
`
`v
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 3
`
`

`
`© 1995 by Prentice Hall of Australia Pty Ltd
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval
`system, or transmitted in any form or by any means, electronic, mechanical, photocopying,
`recording, or otherwise, without written permission of the publisher.
`
`Acquisitions Editor: Kaylie Smith
`Cover design: David Weston
`
`Printed in Australia by Ligare Pty Ltd
`
`2 3 4 5 99 98 97 96 95
`
`ISBN 0 13 355702 2
`
`Prentice Hall of Australia Pty Ltd, Sydney
`Prentice Hall, Inc., Englewood Cliffs, New Jersey
`Prentice Hall International, Inc., London
`Prentice Hall Canada, Inc., Toronto
`Prentice Hall Hispanoamericana, SA, Mexico
`Prentice Hall of India Private Ltd, New Delhi
`Prentice Hall of Japan, Inc., Tokyo
`Prentice Hall Southeast Asia Pty Ltd, Singapore
`Editora Prentice Hall do Brasil Ltda, Rio de Janeiro
`
`~~ PRENTICE HALL
`
`-
`
`A division of Simon & Schuster
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 4
`
`

`
`vi Contents
`
`5 Mandatory roles
`
`123
`
`Introduction to CSDP step 5
`5.1
`5.2 Mandatory and optional roles
`5.3
`136
`Logical derivation check
`5.4
`141
`Reference schemes
`5.5
`Case study: a compact disk retailer
`5.6
`158
`Summary
`
`123
`125
`
`154
`
`6 Value, set comparison and subtype constraints 161
`
`CSDP step 6: value, set and subtype constraints
`6.1
`6.2 Value constraints and lazy objects
`162
`6. 3
`168
`Basic set theory
`6.4
`Subset, equality and exclusion constraints
`6.5
`188
`Subtyping
`6.6 Generalization of object types
`6.7
`Summary 210
`
`203
`
`172
`
`161
`
`7 Other constraints and final checks 213
`
`CSDP step 7: other constraints; fmal checks
`7.1
`7.2 Occurrence frequencies 213
`Ring constraints 219
`7.3
`7.4 Other constraints 228
`Final checks 236
`7.5
`Summary 242
`7.6
`
`213
`
`8 Relational implementation 244
`
`8.1
`8.2
`8.3
`8.4
`8.5
`8.6
`8.7
`
`Implementing a conceptual schema 244
`Relational schemas 245
`Relational mapping procedure 251
`Advanced mapping aspects 280
`Relational algebra 292
`Relational database systems
`Summary 319
`
`317
`
`9 Conceptual schema transformations 322
`
`Conceptual schema equivalence 322
`9.1
`9.2
`Predicate specialization and generalization 324
`336
`9.3
`Nesting, co-referencing and flattening
`9.4 Other transformations 355
`9.5
`Conceptual schema optimization 359
`9.6
`Lower level optimization 373
`9. 7
`Re-engineering 375
`9.8
`Summary 383
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 5
`
`

`
`Contents vii
`
`10 Other design methods, issues and trends 385
`
`Introduction 385
`10.1
`10.2 Normalization 386
`10.3 Schema abstraction and ER modeling 400
`10.4 Operation modeling and external design 405
`413
`10.5 Object-oriented databases and other trends
`10.6 Meta-modeling 424
`10.7 Summary 427
`
`Appendix A: Hardware and software generations
`
`431
`
`Appendix B: Subtype matrices 435
`
`Appendix C:
`
`Introduction to SQL 442
`
`Appendix D: CASE tool support 490
`
`493
`
`Selected answers
`Bibliography
`531
`ORM glossary
`536
`Index
`544
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 6
`
`

`
`1
`
`Introduction
`
`1 . 1 Why study database design?
`
`This book provides a modem introduction to database systems, with the emphasis on
`information modeling. A database is basically a collection of related facts (e.g. a
`company's personnel records, or a bus timetable). Discovering the essential kinds of
`facts that underlie an application, and the conditions that apply to them, is both
`interesting and illuminating. The quality of the database design used for these facts and
`conditions is important. Just as a house built from a good architectural plan is more
`likely to be safe and convenient for living, a well-designed database simplifies the task
`of ensuring that its facts are correct and easy to get at. This section motivates the study
`of data-base design methods by indicating the nature and importance of database
`systems, and then showing how things can go wrong if the database design is poor.
`Each database is used to model some application, typically a part of the real world.
`Consider a library database. As changes occur in the library (e.g. a book is borrowed,
`or a new book is purchased) the database is updated to reflect these changes. This task
`could be performed manually (e.g. using a card-catalog) or be automated (e.g. an on(cid:173)
`line catalog), or both. We focus our attention on automated databases. Sometimes these
`are implemented by means of special-purpose computer programs, coded in a general(cid:173)
`purpose programming language (e.g. C). More often, database applications are
`developed using a database management system (DBMS): this is a software system for
`maintaining databases and answering queries about them (e.g. Access, DB2, dBase,
`lngres, Oracle, Paradox, Sybase). The same DBMS may handle many different data(cid:173)
`bases. Although the design methods we discuss are relevant to special-purpose database
`programs, our implementation focus is on DBMSs.
`If an application requires maintenance and retrieval of large amounts of data, a
`DBMS offers many advantages over manual record-keeping systems. Operations on data
`may often be performed faster. Data may be stored compactly on disk, and redundancy
`
`J
`
`BLUE COAT SYSTEMS - Exhibit 1022 Page 7