数据库与事务处理 面向应用的方法 英文本PDF电子书下载

PART One Introduction 1

1 Overview of Databases and Transactions 3

1.1 What Are Databases and Transactions? 3

1.2 Features of Modern Database and Transaction Processing Systems 5

1.3 Major Players in the Implementation and Support of Database and Transaction Processing Systems 9

1.4 Decision Support Systems OLAP and OLTP 10

1.5 Exercises 12

2 A Closer Look 15

2.1 Case Study:A Student Registration System 15

2.2 Introduction to Relational Databases 15

2.3 What Makes a Program a Transaction? 21

2.4 Bibliographic Notes 26

2.5 Exercises 26

3.1 Software Engineering Methodology 29

3 Case Study:Starting the Student Registration System 29

3.2 Requirements Document 31

3.3 Requirements Analysis New Issues 38

3.4 Application Generators 40

3.5 GUIs and Objects 40

3.6 Events and Procedures 44

3.7 Accessing Databases and Executing Transactions 46

3.8 Specifying the Student Registration System 48

3.9 Specification Document 49

3.10 Bibliographic Notes 50

3.11 Exercises 50

PART Two Database Management 53

4.1 What Is a Data Model? 55

4 The Relational Data Model 55

4.2 The Relational Model 58

4.2.1 Basic Concepts 59

4.2.2 Integrity Constraints 62

4.3 SQL Data Definition Sublanguage 69

4.3.1 Specifying the Relation Type 70

4.3.2 The System Catalog 70

4.3.3 Key Constraints 70

4.3.4 Dealing with Missing Information 71

4.3.5 Semantic Constraints 72

4.3.6 User-Defined Domains 75

4.3.7 Foreign Key Constraints 76

4.3.8 Reactive Constraints 78

4.3.9 Database Views 81

4.3.10 Modifying Existing Definitions 82

4.3.11 SQL-Schemas 84

4.3.12 Access Control 85

4.4 Bibliographic Notes 87

4.5 Exercises 87

5 Database Design Ⅰ:The Entity-Relationship Model 89

5.1 Conceptual Modeling with the E-R Approach 89

5.2 Entities and Entity Types 90

5.3 Relationships and Relationship Types 94

5.4 Advanced Features of the E-R Approach 99

5.4.1 Entity Type Hierarchies 99

5.4.2 Participation Constraints 103

5.5 A Brokerage Firm Example 106

5.6 Limitations of the E-R Approach 110

5.7 Case Study:A Design for the Student Registration System 114

5.8 Bibliographic Notes 119

5.9 Exercises 119

6 Query Languages Ⅰ:Relational Algebra and SQL 123

6.1 Relational Algebra:Under the Hood of SQL 124

6.1.1 Basic Operators 124

6.1.2 Derived Operators 133

6.2 The Query Sublanguage of SQL 140

6.2.1 Simple SQL Queries 140

6.2.2 Set Operations 146

6.2.3 Nested Queries 149

6.2.4 Aggregation over Data 154

6.2.5 A Simple Query Evaluation Algorithm 159

6.2.6 More on Views in SQL 161

6.2.7 The Null Value Quandary 166

6.3 Modifying Relation Instances in SQL 167

6.4 Bibliographic Notes 172

6.5 Exercises 172

7 Query Languages Ⅱ:Relational Calculus and Visual Query Languages 177

7.1 Tuple Relational Calculus 177

7.2 Understanding SQL through Tuple Relational Calculus 186

7.3 Domain Relational Calculus and Visual Query Languages 189

7.4 Visual Query Languages:QBE and PC Databases 193

7.5 The Relationship between Relational Algebra and the Calculi 200

7.6 Recursive Queries in SQL:1999 202

7.7 Bibliographic Notes 208

7.8 Exercises 208

8.1 The Problem of Redundancy 211

8 Database Design Ⅱ:Relational Normalization Theory 211

8.2 Decompositions 213

8.3 Functional Dependencies 215

8.4 Properties of Functional Dependencies 217

8.5 Normal Forms 222

8.6 Properties of Decompositions 225

8.6.1 Lossless and Lossy Decompositions 226

8.6.2 Dependency-Preserving Decompositions 228

8.7 An Algorithm for BCNF Decomposition 232

8.8 Synthesis of 3NF Schemas 234

8.8.1 Minimal Cover 234

8.8.2 3NF Decomposition through Schema Synthesis 237

8.8.3 BCNF Decomposition through 3NF Synthesis 238

8.9 The Fourth Normal Form 241

8.10 Advanced 4NF Design 245

8.10.1 MVDs and Their Properties 245

8.10.2 The Difficulty of Designing for 4NF 246

8.10.3 A 4NF Decomposition How-To 249

8.11 Summary of Normal Form Decomposition 251

8.12 Case Study:Schema Refinement for the Student Registration System 252

8.13 Tuning Issues:To Decompose or Not to Decompose? 254

8.14 Bibliographic Notes 256

8.15 Exercises 256

9 Triggers and Active Databases 261

9.1 Semantic Issues in Trigger Handling 261

9.2 Triggers in SQL:1999 264

9.3 Avoiding a Chain Reaction 271

9.4 Bibliographic Notes 272

9.5 Exercises 273

10 SQL in the Real World 275

10.1 Executing SQL Statements within an Application Program 275

10.2 Embedded SQL 276

10.2.1 Status Processing 279

10.2.2 Sessions,Connections,and Transactions 281

10.2.3 Executing Transactions 282

10.2.4 Cursors 284

10.2.5 Stored Procedures on the Server 288

10.3 More on Integrity Constraints 293

10.4 Dynamic SQL 294

10.4.1 Statement Preparation in Dynamic SQL 295

10.4.2 Prepared Statements and the Descriptor Area 297

10.4.3 Cursors 299

10.4.4 Stored Procedures on the Server 301

10.5 JDBC and SQLJ 301

10.5.1 JDBC Basics 301

10.5.2 Prepared Statements 304

10.5.3 Result Sets and Cursors 305

10.5.4 Obtaining Information about a Result Set 307

10.5.5 Status Processing 308

10.5.6 Executing Transactions 308

10.5.7 Stored Procedures on the Server 309

10.5.8 An Example 311

10.5.9 SQLJ:Statement-Level Interface to Java 311

10.6 ODBC 313

10.6.1 Prepared Statements 315

10.6.2 Cursors 316

10.6.3 Status Processing 318

10.6.4 Executing Transactions 318

10.6.5 Stored Procedures on the Server 319

10.6.6 An Example 319

10.7 Comparison 319

10.8 Bibliographic Notes 322

10.9 Exercises 322

11 Physical Data Organization and Indexing 325

11.1 Disk Organization 325

11.2 Heap Files 330

11.3 Sorted Files 334

11.4 Indices 336

11.4.1 Clustered versus Unclustered Indices 341

11.4.2 Sparse versus Dense Indices 343

11.4.3 Search Keys Containing Multiple Attributes 345

11.5 Multilevel Indexing 347

11.5.1 Index-Sequential Access 350

11.5.2 B+ Trees 352

11.6 Hash Indexing 359

11.6.1 Static Hashing 359

11.6.2 Dynamic Hashing Algorithms 362

11.7 Special-Purpose Indices 370

11.7.1 Bitmap Indices 370

11.7.2 Join Indices 371

11.8 Tuning Issues:Choosing Indices for an Application 372

11.10 Exercises 373

11.9 Bibliographic Notes 373

12 Case Study:Completing the Student Registration System 377

12.1 The Design Document 377

12.1.1 The Document Structure 378

12.1.2 Design Review 381

12.2 Test Plan 382

12.3 Project Planning 385

12.4 Coding 387

12.5 Incremental Development 389

12.6 Design and Code for the Student Registration System 390

12.6.1 Completing the Database Design:Integrity Constraints 391

12.6.2 Design of the Registration Transaction 392

12.6.3 Partial Code for the Registration Transaction 395

12.8 Exercises 398

12.7 Bibliographic Notes 398

13 The Basics of Query Processing 401

13.1 External Sorting 401

13.2 Computing Projection,Union,and Set Difference 405

13.3 Computing Selection 407

13.3.1 Selections with Simple Conditions 408

13.3.2 Access Paths 409

13.3.3 Selections with Complex Conditions 411

13.4 Computing Joins 413

13.4.1 Computing Joins Using Nested Loops 413

13.4.2 Sort-Merge Join 416

13.4.3 Hash Join 417

13.5 Multi-Relational Joins 418

13.7 Tuning Issues:Impact on Physical Database Design 420

13.6 Computing Aggregate Functions 420

13.8 Bibliographic Notes 421

13.9 Exercises 422

14 An Overview of Query Optimization 425

14.1 Overview of Query Processing 425

14.2 Heuristic Optimization Based on Algebraic Equivalences 426

14.3 Estimating the Cost of a Query Execution Plan 430

14.4 Estimating the Size of the Output 437

14.5 Choosing a Plan 439

14.6 Tuning Issues:Impact on Query Design 443

14.7 Bibliographic Notes 446

14.8 Exercises 446

15 An Overview of Transaction Processing 451

15.1 Isolation 451

15.1.1 Serializability 452

15.1.2 Two-Phase Locking 454

15.1.3 Deadlock 457

15.1.4 Locking in Relational Databases 458

15.1.5 Isolation Levels 459

15.1.6 Lock Granularity and Intention Locks 462

15.1.7 A Serializable Locking Strategy Using Intention Locks 464

15.1.8 Summary 465

15.2 Atomicity and Durability 465

15.2.1 The Write-Ahead Log 465

15.2.2 Recovery from Mass Storage Failure 468

15.3 Implementing Distributed Transactions 469

15.3.1 Atomicity and Durability The Two-Phase Commit Protocol 470

15.3.2 Global Serializability and Deadlock 471

15.3.3 Replication 472

15.3.4 Summary 474

15.4 Bibliographic Notes 474

15.5 Exercises 475

PART Three Advanced Topics in Databases 477

16 Object Databases 479

16.1 Shortcomings of the Relational Data Model 479

16.1.1 Object Databases versus Relational Databases 484

16.2 Historical Developments 485

16.3 The Conceptual Object Data Model 488

16.3.1 Objects and Values 488

16.3.2 Classes 489

16.3.3 Types 490

16.3.4 Object-Relational Databases 493

16.4 The ODMG Standard 494

16.4.1 ODL-The ODMG Object Definition Language 497

16.4.2 OQL-The ODMG Object Query Language 503

16.4.3 Transactions in ODMG 507

16.4.4 Object Manipulation in ODMG 508

16.4.5 Language Bindings 508

16.5 Objects in SQL:1999 512

16.5.1 Row Types 513

16.5.2 User-Defined Types 514

16.5.3 Objects 515

16.5.4 Querying User-Defined Types 516

16.5.5 Updating User-Defined Types 517

16.5.6 Reference Types 519

16.5.7 Collection Types 521

16.6 Common Object Request Broker Architecture 522

16.6.1 CORBA Basics 523

16.6.2 CORBA and Databases 528

16.7 Summary 533

16.8 Bibliographic Notes 533

16.9 Exercises 534

17 XML and Web Data 537

17.1 Semistructured Data 537

17.2 Overview of XML 540

17.2.1 XML Elements and Database Objects 543

17.2.2 XML Attributes 544

17.2.3 Namespaces 548

17.2.4 Document Type Definitions 551

17.2.5 Inadequacy of DTDs as a Data Definition Language 554

17.3 XML Schema 555

17.3.1 XML Schema and Namespaces 556

17.3.2 Simple Types 559

17.3.3 Complex Types 564

17.3.4 Putting It Together 571

17.3.5 Integrity Constraints 572

17.4 XML Query Languages 580

17.4.1 XPath:A Lightweight XML Query Language 581

17.4.2 XSLT:A Transformation Language for XML 588

17.4.3 XQuery:A Full-Featured Query Language for XML 599

17.4.4 Summary 617

17.5 Bibliographic Notes 617

17.6 Exercises 618

18 Distributed Databases 623

18.1 The Application Designer s View of the Database 624

18.2 Distributing Data among Different Databases 627

18.2.1 Fragmentation 627

18.2.2 Updates and Fragmentation 630

18.2.3 Replication 630

18.3 Query Planning Strategies 632

18.3.1 Global Query Optimization 633

18.3.2 Strategies for a Multidatabase System 638

18.3.3 Tuning Issues:Database Design and Query Planning in a Distributed Environment 639

18.4 Bibliographic Notes 640

18.5 Exercises 641

19 OLAP and Data Mining 643

19.1 OLAP and Data Warehouses Old and New 643

19.2 A Multi-Dimensional Model for OLAP Applications 645

19.3 Aggregation 648

19.3.1 Drilling,Slicing,Rolling,Dicing 649

19.3.2 The CUBE Operator 652

19.4 ROLAP and MOLAP 657

19.5 Implementation Issues 658

19.6 Data Mining 658

19.7 Populating a Data Warehouse 663

19.8 Bibliographic Notes 664

19.9 Exercises 665

PART Four Transaction Processing 667

20 ACID Properties of Transactions 669

20.1 Consistency 670

20.1.1 Checking Integrity Constraints 671

20.2 Atomicity 672

20.3 Durability 674

20.4 Isolation 675

20.5 The ACID Properties 678

20.6 Bibliographic Notes 680

20.7 Exercises 680

21 Models of Transactions 683

21.1 Flat Transactions 683

21.2 Providing Structure within a Transaction 685

21.2.1 Savepoints 685

21.2.2 Distributed Transactions 687

21.2.3 Nested Transactions 691

21.2.4 Multilevel Transactions 694

21.3.1 Chained Transactions 698

21.3 Structuring an Application into Multiple Transactions 698

21.3.2 Transaction Scheduling with Recoverable Queues 702

21.3.3 Extended Transactions 706

21.3.4 Workflows and Workflow Management Systems 709

21.4 Bibliographic Notes 713

21.5 Exercises 714

22 Architecture of Transaction Processing Systems 717

22.1 Transaction Processing in a Centralized System 717

22.1.1 Organization of a Single-User System 717

22.1.2 Organization of a Centralized Multiuser System 719

22.2 Transaction Processing in a Distributed System 720

22.2.1 Organization of a Distributed System 721

22.2.2 Sessions and Context 728

22.2.3 Queued Transaction Processing 730

22.3 Heterogeneous Systems and the TP Monitor 731

22.3.1 The Transaction Manager 732

22.3.2 The TP Monitor 734

22.4 The TP Monitor:Communication and Global Atomicity 737

22.4.1 Remote Procedure Call 738

22.4.2 Peer-to-Peer Communication 746

22.4.3 Handling Exceptional Situations within a Transaction 748

22.5 Transaction Processing on the Internet 752

22.5.1 Common Architectures 753

22.5.2 Organization of Transaction Systems on the Internet 754

22.6 Bibliographic Notes 757

22.7 Exercises 757

23 Implementing Isolation 761

23.1 Schedules and Their Equivalence 763

23.1.1 Serializability 767

23.1.2 Conflict Equivalence and View Equivalence 769

23.1.3 Serialization Graphs 770

23.2 Recoverability,Cascaded Aborts,and Strictness 772

23.3 Models for Concurrency Control 774

23.4 A Strategy for Immediate-Update Pessimistic Concurrency Controls 776

23.4.1 Conflict Avoidance 776

23.4.2 Deadlocks 779

23.5 Design of an Immediate-Update Pessimistic Concurrency Control 780

23.5.1 An Implementation Using Lock Sets and Wait Sets 780

23.5.2 Two-Phase Locking 782

23.5.3 Lock Granularity 783

23.6 Objects and Semantic Commutativity 784

23.6.1 Atomicity,Recoverability,and Compensating Operations 788

23.7 Isolation in Structured Transaction Models 790

23.7.1 Savepoints 790

23.7.2 Chained Transactions 791

23.7.3 Recoverable Queues 791

23.7.4 Nested Transactions 792

23.7.5 Multilevel Transactions 793

23.8 Other Concurrency Controls 797

23.8.1 Timestamp-Ordered Concurrency Controls 797

23.8.2 Optimistic Concurrency Controls 800

23.9 Bibliographic Notes 803

23.10 Exercises 803

24 Isolation in Relational Databases 809

24.1 Locking 809

24.1.1 Phantoms 810

24.1.2 Predicate Locking 811

24.2 Locking and the SQL Isolation Levels 814

24.2.1 Lost Updates,Cursor Stability,and Update Locks 820

24.2.2 Case Study:Correctness and NonSERIALIZABLE Schedules The Student Registration System 822

24.2.3 Serializable,SERIALIZABLE,and Correct 829

24.3 Granular Locking:Intention Locks and Index Locks 830

24.3.1 Index Locks:Granular Locking without Phantoms 832

24.3.2 Granular Locking in an Object Database 838

24.4 Improving System Performance 839

24.5 Multiversion Concurrency Controls 840

24.5.1 Read-Only Multiversion Concurrency Controls 842

24.5.2 Read-Consistency Multiversion Concurrency Controls 843

24.5.3 SNAPSHOT Isolation 844

24.7 Exercises 850

24.6 Bibliographic Notes 850

25 Atomicity and Durability 857

25.1 Crash,Abort,and Media Failure 857

25.2 Immediate-Update Systems and Write-Ahead Logs 859

25.2.1 Performance and Write-Ahead Logging 863

25.2.2 Checkpoints and Recovery 866

25.2.3 Logical and Physiological Logging 871

25.3 Recovery in Deferred-Update Systems 873

25.4 Recovery from Media Failure 874

25.5 Bibliographic Notes 877

25.6 Exercises 878

26 Implementing Distributed Transactions 881

26.1 Implementing the ACID Properties 881

26.2 Atomic Termination 883

26.2.1 The Two-Phase Commit Protocol 884

26.2.2 Dealing with Failures in the Two-Phase Commit Protocol 888

26.2.3 Formats and Protocols:The X/Open Standard 892

26.2.4 The Peer-to-Peer Atomic Commit Protocol 893

26.3 Transfer of Coordination 893

26.3.1 The Linear Commit Protocol 894

26.3.2 Two-Phase Commit without a Prepared State 895

26.4 Distributed Deadlock 895

26.5 Global Serialization 896

26.6 When Global Atomicity Cannot Be Guaranteed 898

26.6.1 Weaker Commit Protocols 899

26.7 Replicated Databases 900

26.7.1 Synchronous-Update Replication Systems 902

26.7.2 Asynchronous-Update Replication Systems 905

26.8 Distributed Transactions in the Real World 909

26.9 Bibliographic Notes 910

26.10 Exercises 910

27 Security and Internet Commerce 915

27.1 Authentication,Authorization,and Encryption 915

27.2 Encryption 916

27.3 Digital Signatures 919

27.4 Key Distribution and Authentication 921

27.4.1 The Kerberos Protocol:Tickets 923

27.4.2 Nonces 926

27.5 Authorization 927

27.6 Authenticated Remote Procedure Call 929

27.7 Internet Commerce 930

27.7.1 The Secure Sockets Layer Protocol:Certificates 931

27.7.2 The Secure Electronic Transaction Protocol:Dual Signatures 933

27.7.3 Goods Atomicity,Escrow,and Certified Delivery 937

27.7.4 Electronic Cash:Blind Signatures 941

27.8 Bibliographic Notes 947

27.9 Exercises 947

Appendix System Issues 951

A.1 Basic System Issues 951

A.1.1 Modules and Objects 951

A.1.2 Clients and Servers 954

A.2 Multiprogrammed Operating Systems 955

A.3 Threads 958

A.4 Communication 959

References 963

Index 979