A FIRST COURSE IN DATABASE SYSTEMS SECOND EDITIONPDF电子书下载

1 The Worlds of Database Systems 1

1.1 The Evolution of Database Systems 2

1.1.1 Early Database Management Systems 2

1.1.2 Relational Database Systems 4

1.1.3 Smaller and Smaller Systems 5

1.1.4 Bigger and Bigger Systems 6

1.1.5 Client-Server and Multi-Tier Architectures 7

1.1.6 Multimedia Data 8

1.1.7 Information Integration 8

1.2 Overview of a Database Management System 9

1.2.1 Data-Denition Language Commands 10

1.2.2 Overview of Query Processing 10

1.2.3 Storage and Buffer Management 12

1.2.4 Transaction Processing 13

1.2.5 The Query Processor 14

1.3 Outline of Database-System Studies 15

1.3.1 Database Design 16

1.3.2 Database Programming 17

1.3.3 Database System Implementation 17

1.3.4 Information Integration Overview 19

1.4 Summary of Chapter 1 19

1.5 References for Chapter 1 20

2 The Entity-Relationship Data Model 23

2.1 Elements of the E/R Model 24

2.1.1 Entity Sets 24

2.1.2 Attributes 25

2.1.3 Relationships 25

2.1.4 Entity-Relationship Diagrams 25

2.1.5 Instances of an E/R Diagram 27

2.1.6 Multiplicity of Binary E/R Relationships 27

2.1.7 Multiway Relationships 28

2.1.8 Roles in Relationships 29

2.1.9 Attributes on Relationships 31

2.1.10 Converting Multiway Relationships to Binary 32

2.1.11 Subclasses in the E/R Model 33

2.1.12 Exercises for Section 2.1 36

2.2 Design Principles 39

2.2.1 Faithfulness 39

2.2.2 Avoiding Redundancy 39

2.2.3 Simplicity Counts 40

2.2.4 Choosing the Right Relationships 40

2.2.5 Picking the Right Kind of Element 42

2.2.6 Exercises for Section 2.2 44

2.3 The Modeling of Constraints 47

2.3.1 Classication of Constraints 47

2.3.2 Keys in the E/R Model 48

2.3.3 Representing Keys in the E/R Model 50

2.3.4 Single-Value Constraints 51

2.3.5 Referential Integrity 51

2.3.6 Referential Integrity in E/R Diagrams 52

2.3.7 Other Kinds of Constraints 53

2.3.8 Exercises for Section 53

2.4 Weak Entity Sets 54

2.4.1 Causes of Weak Entity Sets 54

2.4.2 Requirements for Weak Entity Sets 56

2.4.3 Weak Entity Set Notation 57

2.4.4 Exercises for Section 58

2.5 Summary of Chapter 2 59

2.6 References for Chapter 2 60

3 The Relational Data Model 61

3.1 Basics of the Relational Model 61

3.1.1 Attributes 62

3.1.2 Schemas 62

3.1.3 Tuples 62

3.1.4 Domains 63

3.1.5 Equivalent Representations of a Relation 63

3.1.6 Relation Instances 64

3.1.7 Exercises for Section 64

3.2 From E/R Diagrams to Relational Designs 65

3.2.1 From Entity Sets to Relations 66

3.2.2 om E/R Relationships to Relations 67

3.2.3 Combining Relations 70

3.2.4 Handling Weak Entity Sets 71

3.2.5 Exercises for Section 75

3.3 Converting Subclass Structures to Relations 76

3.3.1 E/R-Style Conversion 77

3.3.2 An Object-Oriented Approach 78

3.3.3 Using Null Values to Combine Relations 79

3.3.4 Comparison of Approaches 79

3.3.5 Exercises for Section 80

3.4 Functional Dependencies 82

3.4.1 Denition of Functional Dependency 83

3.4.2 Keys of Relations 84

3.4.3 Superkeys 86

3.4.4 Discovering Keys for Relations 87

3.4.5 Exercises for Section 88

3.5 Rules About Functional Dependencies 90

3.5.1 The Splitting/ Combining Rule 90

3.5.2 Trivial Functional Dependencies 92

3.5.3 Computing the Closure of Attributes 92

3.5.4 Why the Closure Algorithm Works 95

3.5.5 The Transitive Rule 96

3.5.6 Closing Sets of Functional Dependencies 98

3.5.7 Projecting Functional Dependencies 98

3.5.8 Exercises for Section 100

3.6 Design of Relational Database Schemas 102

3.6.1 Anomalies 103

3.6.2 Decomposing Relations 103

3.6.3 Boyce-Codd Normal Form 105

3.6.4 Decomposition into BCNF 107

3.6.5 Recovering Information from a Decomposition 112

3.6.6 Third Normal Form 114

3.6.7 Exercises for Section 117

3.7 Multivalued Dependencies 118

3.7.1 Attribute Independence and Its Consequent Redundancy 118

3.7.2 Denition of Multivalued Dependencies 119

3.7.3 Reasoning About Multivalued Dependencies 120

3.7.4 Fourth Normal Form 122

3.7.5 Decomposition into Fourth Normal Form 123

3.7.6 Relationships Among Normal Forms 124

3.7.7 Exercises for Section 126

3.8 Summary of Chapter 127

3.9 References for Chapter 129

4 Other Data Models 131

4.1 Review of Object-Oriented Concepts 132

4.1.1 The Type System 132

4.1.2 Classes and Objects 133

4.1.3 Object Identity 133

4.1.4 Methods 133

4.1.5 Class Hierarchies 134

4.2 Introduction to ODL 135

4.2.1 Object-Oriented Design 135

4.2.2 Class Declarations 136

4.2.3 Attributes in ODL 136

4.2.4 Relationships in ODL 138

4.2.5 Inverse Relationships 139

4.2.6 Multiplicity of Relationships 140

4.2.7 Methods in ODL 141

4.2.8 Types in ODL 144

4.2.9 Exercises for Section 146

4.3 Additional ODL Concepts 147

4.3.1 Multiway Relationships in ODL 148

4.3.2 Subclasses in ODL 149

4.3.3 Multiple Inheritance in ODL 150

4.3.4 Extents 151

4.3.5 Declaring Keys in ODL 152

4.3.6 Exercises for Section 4.3 155

4.4 From ODL Designs to Relation Designs 155

4.4.1 From ODL Attributes to Relation Attributes 156

4.4.2 Nonatomic Attributes in Classes 157

4.4.3 Representing Set-Valued Attributes 158

4.4.4 Representing Other Type Constructors 160

4.4.5 Representing ODL Relationships 162

4.4.6 What If There Is No Key? 164

4.4.7 Exercises for Section 4.4 164

4.5 The Object-Relational Model 166

4.5.1 From Relations to Object-Relations 166

4.5.2 Nested Relations 167

4.5.3 References 169

4.5.4 Object-Oriented Versus Object-Relation 170

4.5.5 From ODL Designs to Object-Relation Designs 172

4.5.6 Exercises for Section 4.5 172

4.6 Semistructured Data 173

4.6.1 Motivation for the Semistructured-Data Model 173

4.6.2 Semistructured Data Representation 174

4.6.3 Information Integration Via Semistructured Data 175

4.6.4 Exercises for Section 177

4.7 XML and Its Data Model 178

4.7.1 Semantic Tags 178

4.7.2 Well-Formed XML 179

4.7.3 Document Type Denitions 180

4.7.4 Using a DTD 182

4.7.5 Attribute Lists 183

4.7.6 Exercises for Section 185

4.8 Summary of Chapter 186

4.9 References for Chapter 4 187

5 Relational Algebra 189

5.1 An Example Databe Schema 190

5.2 An Algebra of Relational Operations 191

5.2.1 Basics of Relational Algebra 192

5.2.2 Set Operations on Relations 193

5.2.3 Projection 195

5.2.4 Selection 196

5.2.5 Cartesian Product 197

5.2.6 Natural Joins 198

5.2.7 Theta-Joins 199

5.2.8 Combining Operations to Form Queries 201

5.2.9 Renaming 203

5.2.10 Dependent and Independent Operations 205

5.2.11 A Linear Notation for Algebraic Expressions 206

5.2.12 Exercises for Section 207

5.3 Relational Operations on Bags 214

5.3.1 Why Bags? 214

5.3.2 Union, Intersection, and Difference of Bags 215

5.3.3 Projection of Bags 216

5.3.4 Selection on Bags 217

5.3.5 Product of Bags 218

5.3.6 Joins of Bags 219

5.3.7 Exercises for Section 220

5.4 Extended Operators of Relational Algebra 221

5.4.1 Duplicate Elimination 222

5.4.2 Aggregation Operators 222

5.4.3 Grouping 223

5.4.4 The Grouping Operator 224

5.4.5 Extending the Projection Operator 226

5.4.6 The Sorting Operator 227

5.4.7 Outerjoins 228

5.4.8 Exercises for Section 230

5.5 Constraints on Relations 231

5.5.1 Relational Algebra as a Constraint Language 231

5.5.2 Referential Integrity Constraints 232

5.5.3 Additional Constraint Examples 233

5.5.4 Exercises for Section 235

5.6 Summary of Chapter 5 236

5.7 References for Chapter 5 237

6 The Database Language SQL 239

6.1 Simple Queries in SQL 240

6.1.1 Projection in SQL 242

6.1.2 Selection in SQL 243

6.1.3 Comparison of Strings 245

6.1.4 Dates and Times 247

6.1.5 Null Values and Comparisons Involving NULL 248

6.1.6 The Truth-Value UNKNOWN 249

6.1.7 Ordering the Output 251

6.1.8 Exercises for Section 252

6.2 Queries Involving More Than One Relation 254

6.2.1 Products and Joins in SQL 254

6.2.2 Disambiguating Attributes 255

6.2.3 Tuple Variables 256

6.2.4 Interpreting Multirelation Queries 258

6.2.5 Union, Intersection, and Dierence of Queries 260

6.2.6 Exercises for Section 262

6.3 Subqueries 264

6.3.1 Subqueries that Produce Scalar Values 264

6.3.2 Conditions Involving Relations 266

6.3.3 Conditions Involving Tuples 266

6.3.4 Correlated Subqueries 268

6.3.5 Subqueries in FROM Clauses 270

6.3.6 SQL Join Expressions 270

6.3.7 Natural Joins 272

6.3.8 Outerjoins 272

6.3.9 Exercises for Section 6.3 274

6.4 Full-Relation Operations 277

6.4.1 Eliminating Duplicates 277

6.4.2 Duplicates in Unions, Intersections, and Dierences 278

6.4.3 Grouping and Aggregation in SQL 279

6.4.4 Aggregation Operators 279

6.4.5 Grouping 280

6.4.6 HAVING Clauses 282

6.4.7 Exercises for Section 284

6.5 Database Modications 286

6.5.1 Insertion 286

6.5.2 Deletion 288

6.5.3 Updates 289

6.5.4 Exercises for Section 6.5 290

6.6 Dening a Relation Schema in SQL 292

6.6.1 Data Types 292

6.6.2 Simple Table Declarations 293

6.6.3 Modifying Relation Schemas 294

6.6.4 Default Values 295

6.6.5 Indexes 295

6.6.6 Introduction to Selection of Indexes 297

6.6.7 Exercises for Section 300

6.7 View Denitions 301

6.7.1 Declaring Views 302

6.7.2 Querying Views 302

6.7.3 Renaming Attributes 304

6.7.4 Modifying Views 305

6.7.5 Interpreting Queries Involving Views 308

6.7.6 Exercises for Section 6.7 310

6.8 Summary of Chapter 6 312

6.9 References for Chapter 6 313

7 Constraints and Triggers 315

7.1 Keys and Foreign Keys 316

7.1.1 Declaring Primary Keys 316

7.1.2 Keys Declared With UNIQUE 317

7.1.3 Enforcing Key Constraints 318

7.1.4 Declaring Foreign-Key Constraints 319

7.1.5 Maintaining Referential Integrity 321

7.1.6 Deferring the Checking of Constraints 323

7.1.7 Exercises for Section 7.1 326

7.2 Constraints on Attributes and Tuples 327

7.2.1 Not-Null Constraints 328

7.2.2 Attribute-Based CHECK Constraints 328

7.2.3 Tuple-Based CHECK Constraints 330

7.2.4 Exercises for Section 7.2 331

7.3 Modication of Constraints 333

7.3.1 Giving Names to Constraints 334

7.3.2 Altering Constraints on Tables 334

7.3.3 Exercises for Section 7.3 335

7.4 Schema-Level Constraints and Triggers 336

7.4.1 Assertions 337

7.4.2 Event-Condition-Action Rules 340

7.4.3 Triggers in SQL 340

7.4.4 Instead-Of Triggers 344

7.4.5 Exercises for Section 7.4 345

7.5 Summary of Chapter 7 347

7.6 References for Chapter 7 348

8 System Aspects of SQL 349

8.1 SQL in a Programming Environment 349

8.1.1 The Impedance Mismatch Problem 350

8.1.2 The SQL/Host Language Interface 352

8.1.3 The DECLARE Section 352

8.1.4 Using Shared Variables 353

8.1.5 Single-Row Select Statements 354

8.1.6 Cursors 355

8.1.7 Modications by Cursor 358

8.1.8 Protecting Against Concurrent Updates 360

8.1.9 Scrolling Cursors 361

8.1.10 Dynamic SQL 361

8.1.11 Exercises for Section 363

8.2 Procedures Stored in the Schema 365

8.2.1 Creating PSM Functions and Procedures 365

8.2.2 Some Simple Statement Forms in PSM 366

8.2.3 Branching Statements 368

8.2.4 Queries in PSM 369

8.2.5 Loops in PSM 370

8.2.6 For-Loops 372

8.2.7 Exceptions in PSM 374

8.2.8 Using PSM Functions and Procedures 376

8.2.9 Exercises for Section 377

8.3 The SQL Environment 379

8.3.1 Environments 379

8.3.2 Schemas 380

8.3.3 Catalogs 381

8.3.4 Clients and Servers in the SQL Environment 382

8.3.5 Connections 382

8.3.6 Sessions 384

8.3.7 Modules 384

8.4 Using a Call-Level Interface 385

8.4.1 Introduction to SQL/CLI 385

8.4.2 Processing Statements 388

8.4.3 Fetching Data From a Query Result 389

8.4.4 Passing Parameters to Queries 392

8.4.5 Exercises for Section 8.4 393

8.5 Java Database Connectivity 393

8.5.1 Introduction to JDBC 393

8.5.2 Creating Statements in JDBC 394

8.5.3 Cursor Operations in JDBC 396

8.5.4 Parameter Passing 396

8.5.5 Exercises for Section 8.5 397

8.6 Transactions in SQL 397

8.6.1 Serializability 397

8.6.2 Atomicity 399

8.6.3 Transactions 401

8.6.4 Read-Only Transactions 403

8.6.5 Dirty Reads 405

8.6.6 Other Isolation Levels 407

8.6.7 Exercises for Section 409

8.7 Security and User Authorization in SQL 410

8.7.1 Privileges 410

8.7.2 Creating Privileges 412

8.7.3 The Privilege-Checking Process 413

8.7.4 Granting Privileges 414

8.7.5 Grant Diagrams 416

8.7.6 Revoking Privileges 417

8.7.7 Exercises for Section 421

8.8 Summary of Chapter 422

8.9 References for Chapter 8 424

9 Object-Orientation in Query Languages 425

9.1 Introduction to OQL 425

9.1.1 An Object-Oriented Movie Example 426

9.1.2 Path Expressions 426

9.1.3 Select-From-Where Expressions in OQL 428

9.1.4 Modifying the Type of the Result 429

9.1.5 Complex Output Types 431

9.1.6 Subqueries 431

9.1.7 Exercises for Section 9.1 433

9.2 Additional Forms of OQL Expressions 436

9.2.1 Quantier Expressions 437

9.2.2 Aggregation Expressions 437

9.2.3 Group-By Expressions 438

9.2.4 HAVING Clauses 441

9.2.5 Union, Intersection, and Dierence 442

9.2.6 Exercises for Section 442

9.3 Object Assignment and Creation in OQL 443

9.3.1 Assigning Values to Host-Language Variables 444

9.3.2 Extracting Elements of Collections 444

9.3.3 Obtaining Each Member of a Collection 445

9.3.4 Constants in OQL 446

9.3.5 Creating New Objects 447

9.3.6 Exercises for Section 9.3 448

9.4 User-Dened Types in SQL 449

9.4.1 Dening Types in SQL 449

9.4.2 Methods in User-Dened Types 451

9.4.3 Declaring Relations with a UDT 452

9.4.4 References 452

9.4.5 Exercises for Section 454

9.5 Operations on Object-Relational Data 455

9.5.1 Following References 455

9.5.2 Accessing Attributes of Tuples with a UDT 456

9.5.3 Generator and Mutator Functions 457

9.5.4 Ordering Relationships on UDTs 458

9.5.5 Exercises for Section 460

9.6 Summary of Chapter 9 461

9.7 References for Chapter 9 462

10 Logical Query Languages 463

10.1 A Logic for Relations 463

10.1.1 Predicates and Atoms 463

10.1.2 Arithmetic Atoms 464

10.1.3 Datalog Rules and Queries 465

10.1.4 Meaning of Datalog Rules 466

10.1.5 Extensional and Intensional Predicates 469

10.1.6 Datalog Rules Applied to Bags 469

10.1.7 Exercises for Section 471

10.2 from Relational Algebra to Datalog 471

10.2.1 Intersection 471

10.2.2 Union 472

10.2.3 Dierence 472

10.2.4 Projection 473

10.2.5 Selection 473

10.2.6 Product 476

10.2.7 Joins 476

10.2.8 Simulating Multiple Operations with Datalog 477

10.2.9 Exercises for Section 479

10.3 Recursive Programming in Datalog 480

10.3.1 Recursive Rules 481

10.3.2 Evaluating Recursive Datalog Rules 481

10.3.3 Negation in Recursive Rules 486

10.3.4 Exercises for Section 490

10.4 Recursion in SQL 492

10.4.1 Dening IDB Relations in SQL 492

10.4.2 Stratied Negation 494

10.4.3 Problematic Expressions in Recursive SQL 496

10.4.4 Exercises for Section 10.4 499

10.5 Summary of Chapter 500

10.6 References for Chapter 501

Index 503