1 The Worlds of Database Systems 1
1.1 The Evolution of Database Systems 1
1.1.1 Early Database Management Systems 2
1.1.2 Relational Database Systems 3
1.1.3 Smaller and Smaller Systems 3
1.1.4 Bigger and Bigger Systems 4
1.1.5 Information Integration 4
1.2 Overview of a Database Management System 5
1.2.1 Data-Definition Language Commands 5
1.2.2 Overview of Query Processing 5
1.2.3 Storage and Buffer Management 7
1.2.4 Transaction Processing 8
1.2.5 The Query Processor 9
1.3 Outline of Database-System Studies 10
1.4 References for Chapter 1 12
Ⅰ Relational Database Modeling 15
2 The Relational Model of Data 17
2.1 An Overview of Data Models 17
2.1.1 What is a Data Model？ 17
2.1.2 Important Data Models 18
2.1.3 The Relational Model in Brief 18
2.1.4 The Semistructured Model in Brief 19
2.1.5 Other Data Models 20
2.1.6 Comparison of Modeling Approaches 21
2.2 Basics of the Relational Model 21
2.2.1 Attributes 22
2.2.2 Schemas 22
2.2.3 Tuples 22
2.2.4 Domains 23
2.2.5 Equivalent Representations of a Relation 23
2.2.6 Relation Instances 24
2.2.7 Keys of Relations 25
2.2.8 An Example Database Schema 26
2.2.9 Exercises for Section 2.2 28
2.3 Defining a Relation Schema in SQL 29
2.3.1 Relations in SQL 29
2.3.2 Data Types 30
2.3.3 Simple Table Declarations 31
2.3.4 Modifying Relation Schemas 33
2.3.5 Default Values 34
2.3.6 Declaring Keys 34
2.3.7 Exercises for Section 2.3 36
2.4 An Algebraic Query Language 38
2.4.1 Why Do We Need a Special Query Language？ 38
2.4.2 What is an Algebra？ 38
2.4.3 Overview of Relational Algebra 39
2.4.4 Set Operations on Relations 39
2.4.5 Projection 41
2.4.6 Selection 42
2.4.7 Cartesian Product 43
2.4.8 Natural Joins 43
2.4.9 Theta-Joins 45
2.4.10 Combining Operations to Form Queries 47
2.4.11 Naming and Renaming 49
2.4.12 Relationships Among Operations 50
2.4.13 A Linear Notation for Algebraic Expressions 51
2.4.14 Exercises for Section 2.4 52
2.5 Constraints on Relations 58
2.5.1 Relational Algebra as a Constraint Language 59
2.5.2 Referential Integrity Constraints 59
2.5.3 Key Constraints 60
2.5.4 Additional Constraint Examples 61
2.5.5 Exercises for Section 2.5 62
2.6 Summary of Chapter 2 63
2.7 References for Chapter 2 65
3 Design Theory for Relational Databases 67
3.1 Functional Dependencies 67
3.1.1 Definition of Functional Dependency 68
3.1.2 Keys of Relations 70
3.1.3 Superkeys 71
3.1.4 Exercises for Section 3.1 71
3.2 Rules About Functional Dependencies 72
3.2.1 Reasoning About Functional Dependencies 72
3.2.2 The Splitting/Combining Rule 73
3.2.3 Trivial Functional Dependencies 74
3.2.4 Computing the Closure of Attributes 75
3.2.5 Why the Closure Algorithm Works 77
3.2.6 The Transitive Rule 79
3.2.7 Closing Sets of Functional Dependencies 80
3.2.8 Projecting Functional Dependencies 81
3.2.9 Exercises for Section 3.2 83
3.3 Design of Relational Database Schemas 85
3.3.1 Anomalies 86
3.3.2 Decomposing Relations 86
3.3.3 Boyce-Codd Normal Form 88
3.3.4 Decomposition into BCNF 89
3.3.5 Exercises for Section 3.3 92
3.4 Decomposition：The Good，Bad，and Ugly 93
3.4.1 Recovering Information from a Decomposition 94
3.4.2 The Chase Test for Lossless Join 96
3.4.3 Why the Chase Works 99
3.4.4 Dependency Preservation 100
3.4.5 Exercises for Section 3.4 102
3.5 Third Normal Form 102
3.5.1 Definition of Third Normal Form 102
3.5.2 The Synthesis Algorithm for 3NF Schemas 103
3.5.3 Why the 3NF Synthesis Algorithm Works 104
3.5.4 Exercises for Section 3.5 105
3.6 Multivalued Dependencies 105
3.6.1 Attribute Independence and Its Consequent Redundancy 106
3.6.2 Definition of Multivalued Dependencies 107
3.6.3 Reasoning About Multivalued Dependencies 108
3.6.4 Fourth Normal Form 110
3.6.5 Decomposition into Fourth Normal Form 111
3.6.6 Relationships Among Normal Forms 113
3.6.7 Exercises for Section 3.6 113
3.7 An Algorithm for Discovering MVD’s 115
3.7.1 The Closure and the Chase 115
3.7.2 Extending the Chase to MVD’s 116
3.7.3 Why the Chase Works for MVD’s 118
3.7.4 Projecting MVD’s 119
3.7.5 Exercises for Section 3.7 120
3.8 Summary of Chapter 3 121
3.9 References for Chapter 3 122
4 High-Level Database Models 125
4.1 The Entity/Relationship Model 126
4.1.1 Entity Sets 126
4.1.2 Attributes 126
4.1.3 Relationships 127
4.1.4 Entity-Relationship Diagrams 127
4.1.5 Instances of an E/R Diagram 128
4.1.6 Multiplicity of Binary E/R Relationships 129
4.1.7 Multiway Relationships 130
4.1.8 Roles in Relationships 131
4.1.9 Attributes on Relationships 134
4.1.10 Converting Multiway Relationships to Binary 134
4.1.11 Subclasses in the E/R Model 135
4.1.12 Exercises for Section 4.1 138
4.2 Design Principles 140
4.2.1 Faithfulness 140
4.2.2 Avoiding Redundancy 141
4.2.3 Simplicity Counts 142
4.2.4 Choosing the Right Relationships 142
4.2.5 Picking the Right Kind of Element 144
4.2.6 Exercises for Section 4.2 145
4.3 Constraints in the E/R Model 148
4.3.1 Keys in the E/R Model 148
4.3.2 Representing Keys in the E/R Model 149
4.3.3 Referential Integrity 150
4.3.4 Degree Constraints 151
4.3.5 Exercises for Section 4.3 151
4.4 Weak Entity Sets 152
4.4.1 Causes of Weak Entity Sets 152
4.4.2 Requirements for Weak Entity Sets 153
4.4.3 Weak Entity Set Notation 155
4.4.4 Exercises for Section 4.4 156
4.5 From E/R Diagrams to Relational Designs 157
4.5.1 From Entity Sets to Relations 157
4.5.2 From E/R Relationships to Relations 158
4.5.3 Combining Relations 160
4.5.4 Handling Weak Entity Sets 161
4.5.5 Exercises for Section 4.5 163
4.6 Converting Subclass Structures to Relations 165
4.6.1 E/R-Style Conversion 166
4.6.2 An Object-Oriented Approach 167
4.6.3 Using Null Values to Combine Relations 168
4.6.4 Comparison of Approaches 169
4.6.5 Exercises for Section 4.6 171
4.7 Unified Modeling Language 171
4.7.1 UML Classes 172
4.7.2 Keys for UML classes 173
4.7.3 Associations 173
4.7.4 Self-Associations 175
4.7.5 Association Classes 175
4.7.6 Subclasses in UML 176
4.7.7 Aggregations and Compositions 177
4.7.8 Exercises for Section 4.7 179
4.8 From UML Diagrams to Relations 179
4.8.1 UML-to-Relations Basics 179
4.8.2 From UML Subclasses to Relations 180
4.8.3 From Aggregations and Compositions to Relations 181
4.8.4 The UML Analog of Weak Entity Sets 181
4.8.5 Exercises for Section 4.8 183
4.9 Object Definition Language 183
4.9.1 Class Declarations 184
4.9.2 Attributes in ODL 184
4.9.3 Relationships in ODL 185
4.9.4 Inverse Relationships 186
4.9.5 Multiplicity of Relationships 186
4.9.6 Types in ODL 188
4.9.7 Subclasses in ODL 190
4.9.8 Declaring Keys in ODL 191
4.9.9 Exercises for Section 4.9 192
4.10 From ODL Designs to Relational Designs 193
4.10.1 From ODL Classes to Relations 193
4.10.2 Complex Attributes in Classes 194
4.10.3 Representing Set-Valued Attributes 195
4.10.4 Representing Other Type Constructors 196
4.10.5 Representing ODL Relationships 198
4.10.6 Exercises for Section 4.10 198
4.11 Summary of Chapter 4 200
4.12 References for Chapter 4 202
Ⅱ Relational Database Programming 203
5 Algebraic and Logical Query Languages 205
5.1 Relational Operations on Bags 205
5.1.1 Why Bags？ 206
5.1.2 Union，Intersection，and Difference of Bags 207
5.1.3 Projection of Bags 208
5.1.4 Selection on Bags 209
5.1.5 Product of Bags 210
5.1.6 Joins of Bags 210
5.1.7 Exercises for Section 5.1 212
5.2 Extended Operators of Relational Algebra 213
5.2.1 Duplicate Elimination 214
5.2.2 Aggregation Operators 214
5.2.3 Grouping 215
5.2.4 The Grouping Operator 216
5.2.5 Extending the Projection Operator 217
5.2.6 The Sorting Operator 219
5.2.7 Outerjoins 219
5.2.8 Exercises for Section 5.2 222
5.3 A Logic for Relations 222
5.3.1 Predicates and Atoms 223
5.3.2 Arithmetic Atoms 223
5.3.3 Datalog Rules and Queries 224
5.3.4 Meaning of Datalog Rules 225
5.3.5 Extensional and Intensional Predicates 228
5.3.6 Datalog Rules Applied to Bags 228
5.3.7 Exercises for Section 5.3 230
5.4 Relational Algebra and Datalog 230
5.4.1 Boolean Operations 231
5.4.2 Projection 232
5.4.3 Selection 232
5.4.4 Product 235
5.4.5 Joins 235
5.4.6 Simulating Multiple Operations with Datalog 236
5.4.7 Comparison Between Datalog and Relational Algebra 238
5.4.8 Exercises for Section 5.4 238
5.5 Summary of Chapter 5 240
5.6 References for Chapter 5 241
6 The Database Language SQL 243
6.1 Simple Queries in SQL 244
6.1.1 Projection in SQL 246
6.1.2 Selection in SQL 248
6.1.3 Comparison of Strings 250
6.1.4 Pattern Matching in SQL 250
6.1.5 Dates and Times 251
6.1.6 Null Values and Comparisons Involving NULL 252
6.1.7 The Truth-Value UNKNOWN 253
6.1.8 Ordering the Output 255
6.1.9 Exercises for Section 6.1 256
6.2 Queries Involving More Than One Relation 258
6.2.1 Products and Joins in SQL 259
6.2.2 Disambiguating Attributes 260
6.2.3 Tuple Variables 261
6.2.4 Interpreting Multirelation Queries 262
6.2.5 Union，Intersection，and Difference of Queries 265
6.2.6 Exercises for Section 6.2 267
6.3 Subqueries 268
6.3.1 Subqueries that Produce Scalar Values 269
6.3.2 Conditions Involving Relations 270
6.3.3 Conditions Involving Tuples 271
6.3.4 Correlated Subqueries 273
6.3.5 Subqueries in FROM Clauses 274
6.3.6 SQL Join Expressions 275
6.3.7 Natural Joins 276
6.3.8 Outerjoins 277
6.3.9 Exercises for Section 6.3 279
6.4 Full-Relation Operations 281
6.4.1 Eliminating Duplicates 281
6.4.2 Duplicates in Unions，Intersections，and Differences 282
6.4.3 Grouping and Aggregation in SQL 283
6.4.4 Aggregation Operators 284
6.4.5 Grouping 285
6.4.6 Grouping，Aggregation，and Nulls 287
6.4.7 HAVING Clauses 288
6.4.8 Exercises for Section 6.4 289
6.5 Database Modifications 291
6.5.1 Insertion 291
6.5.2 Deletion 292
6.5.3 Updates 294
6.5.4 Exercises for Section 6.5 295
6.6 Transactions in SQL 296
6.6.1 Serializability 296
6.6.2 Atomicity 298
6.6.3 Transactions 299
6.6.4 Read-Only Transactions 300
6.6.5 Dirty Reads 302
6.6.6 Other Isolation Levels 304
6.6.7 Exercises for Section 6.6 306
6.7 Summary of Chapter 6 307
6.8 References for Chapter 6 308
7 Constraints and Triggers 311
7.1 Keys and Foreign Keys 311
7.1.1 Declaring Foreign-Key Constraints 312
7.1.2 Maintaining Referential Integrity 313
7.1.3 Deferred Checking of Constraints 315
7.1.4 Exercises for Section 7.1 318
7.2 Constraints on Attributes and Tuples 319
7.2.1 Not-Null Constraints 319
7.2.2 Attribute-Based CHECK Constraints 320
7.2.3 Tuple-Based CHECK Constraints 321
7.2.4 Comparison of Tuple- and Attribute-Based Constraints 323
7.2.5 Exercises for Section 7.2 323
7.3 Modification of Constraints 325
7.3.1 Giving Names to Constraints 325
7.3.2 Altering Constraints on Tables 326
7.3.3 Exercises for Section 7.3 327
7.4 Assertions 328
7.4.1 Creating Assertions 328
7.4.2 Using Assertions 329
7.4.3 Exercises for Section 7.4 330
7.5 Triggers 332
7.5.1 Triggers in SQL 332
7.5.2 The Options for Trigger Design 334
7.5.3 Exercises for Section 7.5 337
7.6 Summary of Chapter 7 339
7.7 References for Chapter 7 339
8 Views and Indexes 341
8.1 Virtual Views 341
8.1.1 Declaring Views 341
8.1.2 Querying Views 343
8.1.3 Renaming Attributes 343
8.1.4 Exercises for Section 8.1 344
8.2 Modifying Views 344
8.2.1 View Removal 345
8.2.2 Updatable Views 345
8.2.3 Instead-Of Triggers on Views 347
8.2.4 Exercises for Section 8.2 349
8.3 Indexes in SQL 350
8.3.1 Motivation for Indexes 350
8.3.2 Declaring Indexes 351
8.3.3 Exercises for Section 8.3 352
8.4 Selection of Indexes 352
8.4.1 A Simple Cost Model 352
8.4.2 Some Useful Indexes 353
8.4.3 Calculating the Best Indexes to Create 355
8.4.4 Automatic Selection of Indexes to Create 357
8.4.5 Exercises for Section 8.4 359
8.5 Materialized Views 359
8.5.1 Maintaining a Materialized View 360
8.5.2 Periodic Maintenance of Materialized Views 362
8.5.3 Rewriting Queries to Use Materialized Views 362
8.5.4 Automatic Creation of Materialized Views 364
8.5.5 Exercises for Section 8.5 365
8.6 Summary of Chapter 8 366
8.7 References for Chapter 8 367
9 SQL in a Server Environment 369
9.1 The Three-Tier Architecture 369
9.1.1 The Web-Server Tier 370
9.1.2 The Application Tier 371
9.1.3 The Database Tier 372
9.2 The SQL Environment 372
9.2.1 Environments 373
9.2.2 Schemas 374
9.2.3 Catalogs 375
9.2.4 Clients and Servers in the SQL Environment 375
9.2.5 Connections 376
9.2.6 Sessions 377
9.2.7 Modules 378
9.3 The SQL/Host-Language Interface 378
9.3.1 The Impedance Mismatch Problem 380
9.3.2 Connecting SQL to the Host Language 380
9.3.3 The DECLARE Section 381
9.3.4 Using Shared Variables 382
9.3.5 Single-Row Select Statements 383
9.3.6 Cursors 383
9.3.7 Modifications by Cursor 386
9.3.8 Protecting Against Concurrent Updates 387
9.3.9 Dynamic SQL 388
9.3.10 Exercises for Section 9.3 390
9.4 Stored Procedures 391
9.4.1 Creating PSM Functions and Procedures 391
9.4.2 Some Simple Statement Forms in PSM 392
9.4.3 Branching Statements 394
9.4.4 Queries in PSM 395
9.4.5 Loops in PSM 396
9.4.6 For-Loops 398
9.4.7 Exceptions in PSM 400
9.4.8 Using PSM Functions and Procedures 402
9.4.9 Exercises for Section 9.4 402
9.5 Using a Call-Level Interface 404
9.5.1 Introduction to SQL/CLI 405
9.5.2 Processing Statements 407
9.5.3 Fetching Data From a Query Result 408
9.5.4 Passing Parameters to Queries 410
9.5.5 Exercises for Section 9.5 412
9.6 JDBC 412
9.6.1 Introduction to JDBC 412
9.6.2 Creating Statements in JDBC 413
9.6.3 Cursor Operations in JDBC 415
9.6.4 Parameter Passing 416
9.6.5 Exercises for Section 9.6 416
9.7 PHP 416
9.7.1 PHP Basics 417
9.7.2 Arrays 418
9.7.3 The PEAR DB Library 419
9.7.4 Creating a Database Connection Using DB 419
9.7.5 Executing SQL Statements 419
9.7.6 Cursor Operations in PHP 420
9.7.7 Dynamic SQL in PHP 421
9.7.8 Exercises for Section 9.7 422
9.8 Summary of Chapter 9 422
9.9 References for Chapter 9 423
10 Advanced Topics in Relational Databases 425
10.1 Security and User Authorization in SQL 425
10.1.1 Privileges 426
10.1.2 Creating Privileges 427
10.1.3 The Privilege-Checking Process 428
10.1.4 Granting Privileges 430
10.1.5 Grant Diagrams 431
10.1.6 Revoking Privileges 433
10.1.7 Exercises for Section 10.1 436
10.2 Recursion in SQL 437
10.2.1 Defining Recursive Relations in SQL 437
10.2.2 Problematic Expressions in Recursive SQL 440
10.2.3 Exercises for Section 10.2 443
10.3 The Object-Relational Model 445
10.3.1 From Relations to Object-Relations 445
10.3.2 Nested Relations 446
10.3.3 References 447
10.3.4 Object-Oriented Versus Object-Relational 449
10.3.5 Exercises for Section 10.3 450
10.4 User-Defined Types in SQL 451
10.4.1 Defining Types in SQL 451
10.4.2 Method Declarations in UDT’s 452
10.4.3 Method Definitions 453
10.4.4 Declaring Relations with a UDT 454
10.4.5 References 454
10.4.6 Creating Object ID’s for Tables 455
10.4.7 Exercises for Section 10.4 457
10.5 Operations on Object-Relational Data 457
10.5.1 Following References 457
10.5.2 Accessing Components of Tuples with a UDT 458
10.5.3 Generator and Mutator Functions 460
10.5.4 Ordering Relationships on UDT’s 461
10.5.5 Exercises for Section 10.5 463
10.6 On-Line Analytic Processing 464
10.6.1 OLAP and Data Warehouses 465
10.6.2 OLAP Applications 465
10.6.3 A Multidimensional View of OLAP Data 466
10.6.4 Star Schemas 467
10.6.5 Slicing and Dicing 469
10.6.6 Exercises for Section 10.6 472
10.7 Data Cubes 473
10.7.1 The Cube Operator 473
10.7.2 The Cube Operator in SQL 475
10.7.3 Exercises for Section 10.7 477
10.8 Summary of Chapter 10 478
10.9 References for Chapter 10 480
Ⅲ Modeling and Programming for Semistructured Data 481
11 The Semistructured-Data Model 483
11.1 Semistructured Data 483
11.1.1 Motivation for the Semistructured-Data Model 483
11.1.2 Semistructured Data Representation 484
11.1.3 Information Integration Via Semistructured Data 486
11.1.4 Exercises for Section 11.1 487
11.2 XML 488
11.2.1 Semantic Tags 488
11.2.2 XML With and Without a Schema 489
11.2.3 Well-Formed XML 489
11.2.4 Attributes 490
11.2.5 Attributes That Connect Elements 491
11.2.6 Namespaces 493
11.2.7 XML and Databases 493
11.2.8 Exercises for Section 11.2 495
11.3 Document Type Definitions 495
11.3.1 The Form of a DTD 495
11.3.2 Using a DTD 499
11.3.3 Attribute Lists 499
11.3.4 Identifiers and References 500
11.3.5 Exercises for Section 11.3 502
11.4 XML Schema 502
11.4.1 The Form of an XML Schema 502
11.4.2 Elements 503
11.4.3 Complex Types 504
11.4.4 Attributes 506
11.4.5 Restricted Simple Types 507
11.4.6 Keys in XML Schema 509
11.4.7 Foreign Keys in XML Schema 510
11.4.8 Exercises for Section 11.4 512
11.5 Summary of Chapter 11 514
11.6 References for Chapter 11 515
12 Programming Languages for XML 517
12.1 XPath 517
12.1.1 The XPath Data Model 518
12.1.2 Document Nodes 519
12.1.3 Path Expressions 519
12.1.4 Relative Path Expressions 521
12.1.5 Attributes in Path Expressions 521
12.1.6 Axes 521
12.1.7 Context of Expressions 522
12.1.8 Wildcards 523
12.1.9 Conditions in Path Expressions 523
12.1.10 Exercises for Section 12.1 526
12.2 XQuery 528
12.2.1 XQuery Basics 530
12.2.2 FLWR Expressions 530
12.2.3 Replacement of Variables by Their Values 534
12.2.4 Joins in XQuery 536
12.2.5 XQuery Comparison Operators 537
12.2.6 Elimination of Duplicates 538
12.2.7 Quantification in XQuery 539
12.2.8 Aggregations 540
12.2.9 Branching in XQuery Expressions 540
12.2.10 Ordering the Result of a Query 541
12.2.11 Exercises for Section 12.2 543
12.3 Extensible Stylesheet Language 544
12.3.1 XSLT Basics 544
12.3.2 Templates 544
12.3.3 Obtaining Values From XML Data 545
12.3.4 Recursive Use of Templates 546
12.3.5 Iteration in XSLT 549
12.3.6 Conditionals in XSLT 551
12.3.7 Exercises for Section 12.3 551
12.4 Summary of Chapter 12 553
12.5 References for Chapter 12 554
Index 555