FUNDAMENTALS OF
`
`DATABASE SYSTEMS
`
`- - ELMASRI / NAVATHE -
`
`SECOND EDI T ION
`
` PALO ALTO NETWORKS Exhibit 1021 Page 1
`
`

`
`FUNDAMENTALS
`OF DATABASE
`SYSTEMS
`
`SECOND EDITION
`
`Ramez Elmasri
`Department of Computer Sctence Engmeenng
`Umverstty of Texas at Arlmgton
`
`Shamkant B. Navathe
`College of Computing
`Georgia Institute of Technology
`
`A ••
`
`Addison-Wesley Pub! shlng Company
`Menlo Park, Caltfornta • Readmg, Massachusetts • New York
`Don Mtlls, Ontano • Wokmgham, UK. • Amsterdam • Bonn
`Sydney • Paris • Mllan • Seoul • Tatpei • Smgapore • Tokyo
`Madml • San Juan, Puerto Rtco • Mexico Ctty
`
` PALO ALTO NETWORKS Exhibit 1021 Page 2
`
`

`
`Executive Editor: Dan Joraanstad
`Editorial Assistant: Laura Cheu
`Production Editor: George Calmenson, The Book Company
`Production Coordinator: Teri Holden
`Marketing Manager: Mary Tudor
`Manufacturing Coordinator: Janet Weaver
`Text Design: Hal Lockwood
`Cover Design: Yvo Riezebos
`Copy Editor: Steven Gray
`Proofreader: Martha Ghent
`Composition and Illustrations: GTS Graphics, Inc.
`
`Cover Art: "Bloom" -Original hand-pulled limited edition serigraph by Tetsuro Sawada. Exclu(cid:173)
`sive Sawada publisher and distributor: Buschlen/Mowatt Fine Arts Ltd., Main Floor, 1445 West
`Georgia Street, Vancouver, Canada V6G 2T3 (604) 682-1234.
`
`Copyright© 1994 by Ramez Elmasri and Shamkant B. Navathe
`
`All rights reserved. No part of this publication may be reproduced, or stored in a database
`retrieval system, distributed, or transmitted, in any form or by any other means, electronic,
`mechanical, photocopying, recording, or otherwise, without the prior written permission of the
`publisher and authors. Printed in the United States of America.
`
`Library of Congress CatalogiO:g-in-Publication Data
`Elmasri, Ramez.
`Fundamentals of database systems / Ramez Elmasri, Shamkant B.
`Navathe.
`em.
`p.
`Includes bibliographical references and index.
`ISBN 0-8053-17 48-1
`1. Data base management. 2. Data base design.
`II. Title.
`QA76.9.D3E57
`005.74-dc20
`
`I. Navathe, Sham.
`
`93-36697
`
`1994
`
`ISBN 0-8053-1748-1
`
`9 10-00-98 97
`
`Addison-Wesley Publishing Company
`2725 Sand Hill Road
`Menlo Park, CA 94025
`
` PALO ALTO NETWORKS Exhibit 1021 Page 3
`
`

`
`ABOUT THE AUTHORS
`
`BRIEF CONTENTS
`
`Ramez A. Blmasri 1s an associate professor of computer sctence at the Uruverstty of
`Texas at Arhngton HIS research mterests include ob)ect-onented databases and dlStnb(cid:173)
`uted systems, data modehng and query languages, and temporal databases. Well known
`for hiS research ln extendmg the entlry-relatlonshtp model, Professor Elmasn 's current
`work focuses on mcorporatmg time in database systems. In the 1980s as a prmctpal
`research sctentlst at Honeywell's Computer Sctences Center tn Minnesota, he worked
`on the design and tmplementatlon of a prototype dtstrtbuted database management sys(cid:173)
`temt DOTS He IS a contnbutmg author to Temporal Databases · Theory Destgn and Impk(cid:173)
`mentanon and has published over 40 papers on database theory and destgn,
`
`Shamkant B. Navathe ts a professor of computmg at the Oeorgta lnsutute of Technol(cid:173)
`ogy. Hts research contnbuttons mclude database modelmg, database conversion, logtcal
`database design, distnbuted database destgn, and database mtegratton. He has been a
`consultant to maJor computer vendors mcludlng Honeywell, Stemens, and DEC Professor
`Navathe ts an assoctate edt tor of the Assoctatton for Computtng Machmery's Computmg
`Surueys, and IS the edttor of Ben)amtn/Cummmgs' Senes on Database Systems and
`Apphcattons. Wtdely pubhshed, he ts also the coauthor of Conceptual Database De.ngn·
`An Enttty-Relanoruhip Approach
`
`PART I
`
`BASIC CONCEPTS
`CHAPTER 1 Databases and Database Users
`CHAPTER 2 Database System Concepts and Archttecture 23
`CHAPTER J Data Modehng Using the Entity·Relationshtp
`Approach 39
`CHAPTER 4 Record Storage and Primary Ftle Organtzattons 69
`Index Structures for Files 103
`CHAPTER 5
`
`PART II RELATIONAL MODEL, LANGUAGES, AND
`SYSTEMS
`CHAPTER 6 The Relattonal Data Model and Relattonal Algebra 137
`CHAPTER 7 SQL-A Relattonal Database Language 185
`CHAPTER 8 The Relattonal Calculus, QUEL, and QBE 231
`CHAPTER 9 A Relanonal Database Management System-DB2 259
`
`PART III CONVENTIONAL DATA MODELS AND SYSTEMS
`CHAPTER 10 The Network Data Model and the !OMS System 287
`CHAPTER 11 The Hterarchtcal Data Model and the lMS System 343
`
`xiii
`
` PALO ALTO NETWORKS Exhibit 1021 Page 4
`
`

`
`xiv
`
`BRIEF CXlNTENTS
`
`PART IV DATABASE DESIGN
`CHAPTER 12 Functional Dependenc1es and Normaltzauon for
`Relauonal Databases 391
`C HAPTER 13 Relational lJdtabase Destgn Algonthrns and Further
`DependencieS 423
`C HAPTER 14 Overv~ew of the Database Destgn Process 447
`
`PART V
`
`SYSTEM IMPLEMENTATION TECHNIQUES
`CHAPTER IS The System Catalog 479
`CHAPTER 16 Query Processmg and Opumlzanon 491
`CHAPTER 11 Transaction Processing Concepts 527
`CHAPTER 18 Concurrency Control Techniques 555
`CHAPTER 19 Recovery Techn1ques 577
`CHAPTER 20 Database Secunty and Authomauon 595
`
`PART VI ADVANCED DATA MODELS AND EMERGING
`TRENDS
`CHAPTER 21 Advanced Data Modelmg Concepts 611
`CHAI'TER 22 Object-Onented Databases 663
`CHAI'TER 23 DlStrtbuted Databases and Chent- Server
`Architecture 703
`CHAPTER 24 Deductive Databases 729
`* CHAI'TER 25 Emergmg Database Technologtes and Apphcattons 761
`
`APPENDIX A Alternative Dtagrammattc Notauon.s 801
`APPENDIX B Parameters of Dtslcs 805
`APPENDIX c CompariSOn of Data Models and Systems 809
`
`Btbhogr-•phy 817
`Index 849
`
`* represents that thts chapter may be omitted for an Introductory course
`
`CONTENTS
`
`PART I BASIC CONCEPTS
`
`CHAPTER I Databases and Database Users
`l.l Introduction
`l
`1.2 An Example 4
`1.3 Charactensucs of the Database Approach
`1.4 Actors on the Scene 8
`1.5 Workers Behmd the Scene
`11
`* 1.6
`II
`Intended Uses of a DBMS
`* 1.7
`lmphcat10ns of the Database Approach 15
`*1.8 When Not to Use a DBMS 16
`1.9 Summary 17
`
`Review Questions
`Exerctses
`18
`Selected B1bhography
`
`18
`
`19
`
`CHAPTER 2 Database System Concepts and Architecture 23
`2.1 Data Models, Schemas, and Instances 23
`2.2 DBMS Architecture and Data Independence 26
`2.3 Database Languages and Interfaces 29
`
`* 2.4 The Database System Envtronment 3 1
`* 2.5 Classlficauon of Database Management Systems 34
`2.6 Summary 36
`* represents sections that may be left out for a less detailed treatment of the chapter
`
` PALO ALTO NETWORKS Exhibit 1021 Page 5
`
`

`
`xvi
`
`CONTIN1S
`
`Rev1ew Questions 36
`Exemses 37
`Selected B1bhography
`
`3 7
`
`CHAPTER 3 Data Modelmg Usmg the Entity-Relatwnship Model 39
`3.1 High-level Conceptual Data Models for Database Design 40
`3.2 An Example 42
`3.3 ER Model Concepts 42
`3.4 Notation for Entity-Relationship (ER) Diagrams 57
`
`* 3.5 Proper Nammg of Schema Constructs 60
`
`*3.6 Relationship Types of Degree Higher Than Two 60
`3. 7 Summary 63
`
`Rev1ew Questions 64
`65
`Exerc.ses
`Selected Bibliography 68
`
`CHAPTER 4 Record Storage and Pnmary File Orgamzatlons 69
`4.1
`Introduction 70
`4.2 Secondary Storage Dev1ces 71
`4.3 Buffenng of Blocks 75
`4.4 Placmg F1le Records on Disk 76
`4.5 Operations on F.les 80
`4.6 F1les of Unordered Records (Heap F1les) 83
`4.7 F1les of Ordered Records (Sorted F1les) 84
`4.8 Hashmg Techniques 87
`*4.9 Other Pnmary F1le Organizations 97
`4.10 Summary 98
`
`Rev1ew Questions 99
`ExerciSes
`99
`Selected Bibliography
`
`102
`
`CHAPTER 5 Index Structures for Files 103
`5.1 Types of Smgle-Level Ordered Indexes 103
`5.2 Multilevel Indexes 113
`5.3 Dynamtc Mulnleveiindexes Using B-Trees and B+ -Trees 116
`*5.4 Other Types of Indexes 128
`5.5 Summary 131
`
`Rev1ew Questions
`132
`ExerciSes
`Selected Btbhography
`
`131
`
`135
`
`PART II RELATIONAL MODEL, LANGUAGES AND
`SYSTEMS
`'
`
`CONTEN1S
`
`xvii
`
`CHAPTER 6 The Relational Data Model and Relational Algebra 137
`6.1 Relational Model Concepts 138
`6.2 Relational Model Constramts 143
`
`* 6.3 Update Operations on Relations 149
`
`*6.4 Defimng Relatwru 151
`6.5 The Relational Algebra 153
`*6.6 Addmonal Relational Operations 165
`6. 7 Examples of Quenes m the Relational Algebra 170
`* 6.8 Relational Database Des1gn Usmg ER-to-Relanonal Mappmg 172
`6.9 Summary 177
`
`Review Questions
`I 80
`Exerc•ses
`Selected Bibliography
`
`179
`
`184
`
`CHAPTER 7 SQL-A RelatiOnal Database Language 185
`7.1 Data Definmon m SQL 186
`7.2 Quenes m SQL 192
`7.3 Update Statements in SQL 212
`7.4 Views m SQL 215
`* 7.5 Spectfymg Additional Constramts as Assertions 219
`* 7.6 Spectfymg Indexes 220
`
`*7.7 Embedded SQL 222
`7.8 Summary 225
`
`Rev1ew Questioru 227
`Exerc1ses
`22 7
`Selected Btbhography 230
`
`CHAPTER 8 The Relational Calculus, QUEL, and QBE 23 1
`8.1 Tuple Relational Calculus 232
`
`* 8.2 The QUEL Language 240
`* 8.3 Domam Relational Calculus 24 7
`* 8.4 Overview of the QBE Language 249
`
`8.5 Summary 255
`Revtew Questions 256
`256
`Exerc1ses
`Selected Bibhography 258
`
`CHAPTER 9 A Relational Database Management System- OB2 259
`9.1
`Introduction to Relational Database Management Systems 259
`9.2 Basic Architecture of OB2 260
`
` PALO ALTO NETWORKS Exhibit 1021 Page 6
`
`

`
`xviii
`
`CONTENTS
`
`9.3
`9.4
`* 9.5
`.9.6
`9.7
`
`Data Defimt1on m DB2 265
`Data Mampulanon m DB2 267
`Storage of Data In DB2 273
`Internal Features of DB2 276
`Summary 283
`
`Appendix to Chapter 9
`Selected Btbhography
`
`283
`285
`
`PART III CONVENTIONAL DATA MODELS AND SYSTEMS
`
`CHAPTER 10 The Network Data Model and the IDMS System 287
`10.1 Network Database Structures 288
`10.2 Constraints m the Network Model 298
`10.3 Data Defimuon m the Network Model 302
`* 10.4 Network Database Destgn Usmg ER·to-Network Mappmg 308
`* 10.5 Programmmg a Network Database 311
`* 10.6 A Network Database System-IDMS 328
`10.7 Summary 337
`
`Review Questions 338
`ExerCises
`339
`Selected Btbhography
`
`342
`
`CHAPTER 11 The H1erarch1cal Data Model and the IMS System 343
`J 1.1 H1erarch1cal Database Structures 344
`11.2 Virtual Parent-Chtld Relanonshtps 350
`11.3
`lntegnry Constramts m the H1erarducal Model 354
`
`* 11.4 Data Defimuon m the Hteratchtcal Model 354
`* 11.5 H1erarch1cal Database Destgn Usmg ER·to-H1erarchical Mapping 355
`
`* 11.6 Data Mampu1anon Language for the H1erarch1cal Model 361
`* 11.7 Overvtew of the IMS H1erarclucal Database System 370
`l 1.8 Summary 386
`
`Revtew Questions 387
`Exetc1ses 388
`Selected B1bhography 389
`
`PART IV DATABASE DESIGN
`
`CHAPTER 12 Funcuonal Dependenctes and Normahzanon for Relanonal Databases
`391
`Informal Design GUidelmes for Relation Schemas 392
`
`12.1
`
`12.2
`12.3
`12.4
`*12.5
`12.6
`
`Funcuonal Dependencies 401
`Normal Forms Based on Pnmary Keys 407
`General DefimtiOns of Second and Third Normal Forms 413
`Boyce-Codd Nonnal Form (BCNF) 41 6
`Summary 417
`
`CONTENTS
`
`xix
`
`41 8
`
`Revtew QuestiOns
`Exen:tses 419
`421
`Selected Btbhography
`CHAPTER 13 Relational Database Destgn Algot~thms a d F h De
`13.1 Algomhms for Relattonal Database Schema ~~:t e~24 pendenctes 423
`* :~·; JMuluvalued Dependenctes and Fourth Normal Form 435
`* 13.4
`om Dependenctes and Ftfth Normal Form 440
`•
`IncluSion Dependenctes 441
`* !3.5 Other DependenCies and Normal Forms 442
`
`13.6 Summary 443
`
`Rev1ew Questions 443
`Exerc1ses
`444
`Selected B1bhography 445
`
`CHAPTER 14 Overvtew of the Database Design Process 44 7
`14.1 Role of lnfonnation Systems m Orgaruzatlons 448
`I4.Z The Database Destgn Process 45 1
`* 14.3 Phystcal Database Destgn GUidelmes 467
`* 14.4 A utomated Design Tools 474
`14.5 Summary 475
`
`Rev1ew Questions 4 75
`Selected Btbltography 476
`
`PART V SYSTEM IMPLEMENTATION TECHNIQUES
`CHAPTER 15 The System Catalog 479
`15.1 Catalogs for Relanonal DBMSs 480
`15.2 Catalogs for Network DBMSs 484
`1155.43 Other Catalog Informatton Accessed by DBMS Software Mod I
`u es 486
`.
`Summary 488
`
`Review Questions 488
`Exerctses 488
`
`CHAPTER 16 Query Processmg and Optlmtzatlon 491
`16 I BaSic Algomhms for Executmg Q uery Operanons 493
`
` PALO ALTO NETWORKS Exhibit 1021 Page 7
`
`

`
`CONTENTS
`
`16.2 Usmg Heunsucs m Query Opnmtzation 503
`*16.3 Usmg Cost Esumates tn Query Optimtzation 516
`* 16.4 Semantic Query Opttmtzatton 522
`16.5 Summary 522
`
`Revtew Questions
`ExerctSes
`523
`Selected Bibliography 524
`
`523
`
`CHAPTER 11 T raru;acuon Processmg Concepts 52 7
`lntroductton to Transacuon Processing 527
`17.1
`17.2 Transaction and System Concepts 534
`17.3 DeSirable Properties ofTransacttons 537
`17.4 Schedules and Recoverabthty 538
`17.5 Senaltzability of Schedules 541
`17.6 Summary 551
`
`Revtew Questtons
`Exerctses 552
`Selected Btbhography 553
`
`551
`
`CHAPTER IB Concurrency Control Techmques 555
`18.1 Lockmg Techmques for Concurrency Control 556
`* 18.2 Concurrency Control Based on Timestamp Ordering 564
`* 18.3 Multtverston Concurrency Control Techmques 567
`* 18.4 Validation (OpttmtSttc) Concurrency Control Techmques 569
`
`18.5 Granulanty of Data Items 571
`18.6 Some Other Concurrency Control Issues 572
`18.7 Summary 573
`
`Revtew Questions 573
`Exerctses 574
`Selected Bibliography
`
`575
`
`CHAPTER 19 Recovery Techmques 577
`19.1 Recovery Concepts 578
`19.2 Recovery Techmques Based on Deferred Update 582
`* 19.3 Recovery Techniques Based on Immediate Update 587
`* 19.5 Recovery m Muludatabase Transactions 590
`*19.4 Shadow Pagmg 588
`
`19.6 Database Backup and Recovery from Catastrophic Failures 591
`19.7 Summary 591
`
`Revtew Questions 592
`Exerctses
`593
`Selected Btbliography 594
`
`CONTENTS
`
`xxi
`
`CHAPTER 20 Database Security and Authorizauon 595
`20.1
`Introduction to Database Secunry Issues 595
`20.2 Dtscreuonary Access Control Based on Pnvtleges 598
`
`* 20.3 Mandatory Access Control for Mululevel Securtty 603
`* 20.4 Stausucal Database Secunty 606
`
`20.5 Summary 607
`
`Revtew Questtons 608
`Exerctses 608
`Selected Bibliography 609
`
`PART VI ADVANCED DATA MODELS AND EMERGING
`TRENDS
`
`CHAPTER 21 Advanced Data Modcltng Concepts 611
`21.1 Enhanced-ER (EER) Model Concepts 612
`21.2 EER-to-Relauonal Mapping 629
`*21.3 Data Abstraction and Knowledge Representatton Concepts 633
`lntegn ty Constramts m Data Modelmg 638
`
`* 21.4
`* 21.5 EER Update Operauons and T ransacuon Spectficauon 643
`* 21.6 Overview of Other Data Models 64 7
`21.7 Summary 656
`
`Revtew Questions 657
`Exerctses 658
`Selected Bibltography 660
`
`CHAPTER 22 Object-Onented Databases 663
`22.1 Overvtew of Object-Onenred Concepts 664
`22.2 Object Identtty, ObjeCt Structure, and Type Constructors 666
`22.3 Encapsulation of Operattons, Methods, and Perststence 672
`22.4 Type and Class Hterarchtes and lnherttance 675
`*22.5 Complex Objects 678
`
`* 22.6 Other 00 Concepts 680
`* 22.7 Examples of OODBMSS 683
`* 22.8 00 Database Destgn by EER-to-ClO Mappmg 697
`
`22.9 Summary 699
`
`Revtew Questions
`Exerctses 700
`Selected Bibliography
`
`700
`
`701
`
`CHAPTER 23 Dtstnbuted Databases and Chcnt-Server Architecture 703
`23.1
`Introduction to Dtsttlbuted DBMS Concepts 704
`
` PALO ALTO NETWORKS Exhibit 1021 Page 8
`
`

`
`xxii
`
`CONTENTS
`
`23.2 Overview of Client- Server Architecture 706
`23.3 Data Fragmentation, Replication, and Allocation Techniques for
`Distributed Database Design 709
`23.4 Types of Distributed Database Systems 715
`
`* 23.5 Query Processing in Distributed Databases 716
`
`* 23.6 Overview of Concurrency Control and Recovery in Distributed Databases
`721
`23.7 Summary 724
`
`Review Questions
`726
`Exercises
`Selected Bibliography
`
`725
`
`726
`
`CHAPTER 24 Deductive Databases 729
`24.1
`Introduction to Deductive Databases 730
`24.2 Prolog/Datalog Notation 731
`24.3
`Interpretation of Rules 736
`*24.4 Basic Inference Mechanisms for Logic Programs 738
`*24.5 Datalog Programs and Their Evaluation 741
`*24.6 The LDL System 752
`*24.7 Other Deductive Database Systems 756
`24.8 Summary 757
`
`758
`Exercises
`Selected Bibliography
`
`760
`
`*CHAPTER 25 Emerging Database Technologies and Applications 761
`25.1 Progression of'Database Technology 762
`25.2 Emerging Database Applications 769
`25.3 · Next Generation of Databases and Database Management Systems 778
`25.4
`Interfaces with Other Technologies and Future Research 794
`
`Selected Bibliography
`
`798
`
`APPENDIX A
`APPENDIX B
`APPENDIXC
`Bibliography
`Index 849
`
`Alternative Diagrammatic Notations 801
`805
`Parameters of Disks
`Comparison of Data Models and Systems 809
`817
`
` PALO ALTO NETWORKS Exhibit 1021 Page 9
`
`

`
`2
`
`CHAPTER 1/ DATABASES AND DATABASE USERS
`
`A database is a collection of related data.* By data, we mean known facts that can
`be recorded and that have implicit meaning. For example, consider the names, telephone
`numbers, and addresses of the people you know. You may have recorded this data in an
`indexed addres~ book, or you may have stored it on a diskette, using a personal computer
`and software such as DBASE IV or v, PARADOX, or EXCEL. This is a collection of related
`data with an implicit meaning and hence is a database.
`The preceding definition of database is quite general; for example, we may consider
`the collection of words that make up this page of text to be related data and hence to
`constitute a database. However, the common use of the term database is usually more
`restricted. A database has the following implicit properties:
`
`• A database represents some aspect of the real world, sometimes called the mini·
`world or the Universe of Discourse (UoD). Changes to the miniworld are
`reflected in the database.
`• A database is a logically coherent collection of data with some inherent meaning.
`A random assortment of data cannot correctly be referred to as a database.
`• A database is designed, built, and populated with data for a specific purpose. It
`has an intended group of users and some preconceived applications in which these
`users are interested.
`
`In other words, a database has some source from which data are derived, some degree of
`interaction with events in the real world, and an audience that is actively interested in
`the contents of the database.
`A database can be of any size and of varying complexity. For example, the list of
`names and addresses referred to earlier may consist of only a few hundred records, each
`with a simple structure. On the other hand, the card catalog of a large library may con(cid:173)
`tain half a million cards stored under different categories-by primary author's last name,
`by subject, by book title-with each category organized in alphabetic order. A database
`of even greater size and complexity is maintained by the Internal Revenue Service to
`keep track of the tax forms filed by taxpayers of the United States. If we assume that
`there are 100 million taxpayers and if each taxpayer files an average of five forms with
`approximately 200 characters of information per form, we would get a database of
`100*(106)*200*5 characters (bytes) of information. Assuming that the IRS keeps the
`past three returns for each taxpayer in addition to the current return, we would get a
`database of 4*(1011
`) bytes. This huge amount of information must be organized and
`managed so that u~ers can search for, retrieve, and update the data as needed.
`A database may be generated and maintained manually or by machine. The library
`card catalog is an example of a database that may be manually created and maintained.
`A computerized database may be created and maintained either by a group of application
`programs written specifically for that task or by a database management system.
`A database management system (DBMS) is a collection of programs that enables
`users to create and maintain a database. The DBMS is hence a general-purpose software
`
`*We will use the word data in both singular and plural, which is common in database literature. Context will
`determine whether it is singular or plural. In standard English, data is used only as the plural; datum is used
`as the singular.
`
` PALO ALTO NETWORKS Exhibit 1021 Page 10