分布式数据库系统原理 英文本PDF电子书下载

1 INTRODUCTION 1

1．1 DISTRIBUTED DATA PROCESSING 2

1．2 WHAT IS A DISTRIBUTED DATABASE SYSTEM? 4

1．3 PROMISES OF DDBSs 7

1．3．1 Transparent Management of Distributed and Replicated Data 8

1．3．2 Reliability Through Distributed Transactions 15

1．3．3 Improved Performance 16

1．3．4 Easier System Expansion 18

1．4 COMPLICATING FACTORS 19

1．5．2 Distributed Query Processing 20

1．5 PROBLEM AREAS 20

1．5．1 Distributed Database Design 20

1．5．3 Distributed Directory Management 21

1．5．4 Distributed Concurrency Control 21

1．5．5 Distributed Deadlock Management 21

1．5．6 Reliability of Distributed DBMS 21

1．5．7 Operating System Support 22

1．5．8 Heterogeneous Databases 22

1．5．9 Relationship among Problems 22

1．6 BIBLIOGRAPHIC NOTES 24

2 OVERVIEW OF RELATIONAL DBMS 25

2．1 RELATIONAL DATABASE CONCEPTS 26

2．2 NORMALIZATION 27

2．2．1 Dependency Structures 29

2．2．2 Normal Forms 32

2．3 INTEGRITY RULES 34

2．4 RELATIONAL DATA LANGUAGES 35

2．4．1 Relational Algebra 35

2．4．2 Relational Calculus 43

2．4．3 Interface with Programming Languages 46

2．5 RELATIONAL DBMS 49

2．6 BIBLIOGRAPHIC NOTES 51

3 REVIEW OF COMPUTER NETWORKS 52

3．1 DATA COMMUNICATION CONCEPTS 53

3．2 TYPES OF NETWORKS 55

3．2．1 Topology 56

3．2．2 Communication Schemes 59

3．2．3 Scale 61

3．3 PROTOCOL STANDARDS 63

3．4 BROADBAND NETWORKS 67

3．5 WIRELESS NETWORKS 69

3．6 INTERNET 70

3．7 CONCLUDING REMARKS 71

3．8 BIBLIOGRAPHIC NOTES 74

4 DISTRIBUTED DBMS ARCHITECTURE 75

4．1 DBMS STANDARDIZATION 76

4．2 ARCHITECTURAL MODELS FOR DISTRIBUTED DBMSs 82

4．2．1 Autonomy 82

4．2．4 Architectural Alternatives 84

4．2．3 Heterogeneity 84

4．2．2 Distribution 84

4．3 DISTRIBUTED DBMS ARCHITECTURE 87

4．3．1 Client/Server Systems 88

4．3．2 Peer-to-Peer Distributed Systems 90

4．3．3 MDBS Architecture 94

4．4 GLOBAL DIRECTORY ISSUES 97

4．5 CONCLUSION 100

4．6 BIBLIOGRAPHIC NOTES 100

5 DISTRIBUTED DATABASE DESIGN 102

5．1．1 Top-Down Design Process 104

5．1 ALTERNATIVE DESIGN STRATEGIES 104

5．1．2 Bottom-Up Design Process 106

5．2 DISTRIBUTION DESIGN ISSUES 107

5．2．1 Reasons for Fragmentation 107

5．2．2 Fragmentation Alternatives 108

5．2．3 Degree of Fragmentation 110

5．2．4 Correctness Rules of Fragmentation 110

5．2．5 Allocation Alternatives 111

5．2．6 Information Requirements 111

5．3．1 Horizontal Fragmentation 112

5．3 FRAGMENTATION 112

5．3．2 Vertical Fragmentation 131

5．3．3 Hybrid Fragmentation 146

5．4 ALLOCATION 147

5．4．1 Allocation Problem 147

5．4．2 Information Requirements 150

5．4．3 Allocation Model 151

5．4．4 Solution Methods 154

5．5 CONCLUSION 155

5．6 BIBLIOGRAPHIC NOTES 157

5．7 EXERCISES 158

6 SEMANTIC DATA CONTROL 161

6．1 VIEW MANAGEMENT 162

6．1．1 Views in Centralized DBMSs 162

6．1．2 Updates through Views 164

6．1．3 Views in Distributed DBMSs 165

6．2 DATA SECURITY 167

6．2．1 Centralized Authorization Control 167

6．2．2 Distributed Authorization Control 170

6．3 SEMANTIC INTEGRITY CONTROL 171

6．3．1 Centralized Semantic Integrity Control 173

6．3．2 Distributed Semantic Integrity Control 179

6．4 CONCLUSION 184

6．5 BIBLIOGRAPHIC NOTES 185

6．6 EXERCISES 186

7 OVERVIEW OF QUERY PROCESSING 188

7．1 QUERY PROCESSING PROBLEM 189

7．2 OBJECTIVES OF QUERY PROCESSING 192

7．3 COMPLEXITY OF RELATIONAL ALGEBRA OPERATIONS 193

7．4 CHARACTERIZATION OF QUERY PROCESSORS 194

7．4．2 Types of Optimization 195

7．4．1 Languages 195

7．4．3 Optimization Timing 196

7．4．4 Statistics 196

7．4．5 Decision Sites 196

7．4．6 Exploitation of the Network Topology 197

7．4．7 Exploitation of Replicated Fragments 197

7．4．8 Use of Semijoins 197

7．5 LAYERS OF QUERY PROCESSING 198

7．5．1 Query Decomposition 199

7．5．3 Global Query Optimization 200

7．5．2 Data Localization 200

7．5．4 Local Query Optimization 201

7．6 CONCLUSION 201

7．7 BIBLIOGRAPHIC NOTES 202

8 QUERY DECOMPOSITION AND DATA LOCALIZATION 203

8．1 QUERY DECOMPOSITION 204

8．1．1 Normalization 204

8．1．2 Analysis 205

8．1．3 Elimination of Redundancy 208

8．1．4 Rewriting 210

8．2 LOCALIZATION OF DISTRIBUTED DATA 214

8．2．1 Reduction for Primary Horizontal Fragmentation 215

8．2．2 Reduction for Vertical Fragmentation 218

8．2．3 Reduction for Derived Fragmentation 220

8．2．4 Reduction for Hybrid Fragmentation 221

8．3 CONCLUSION 224

8．4 BIBLIOGRAPHIC NOTES 224

8．5 EXERCISES 225

9 OPTIMIZATION OF DISTRIBUTED QUERIES 228

9．1 QUERY OPTIMIZATION 229

9．1．1 Search Space 229

9．1．2 Search Strategy 232

9．1．3 Distributed Cost Model 233

9．2 CENTRALIZED QUERY OPTIMIZATION 239

9．2．1 INGRES Algorithm 239

9．2．2 System R Algorithm 243

9．3 JOIN ORDERING IN FRAGMENT QUERIES 247

9．3．1 Join Ordering 247

9．3．2 Semijoin Based Algorithms 249

9．3．3 Join versus Semijoin 252

9．4 DISTRIBUTED QUERY OPTIMIZATION ALGORITHMS 254

9．4．1 Distributed INGRES Algorithm 254

9．4．2 R* Algorithm 259

9．4．3 SDD-1 Algorithm 263

9．5 CONCLUSION 269

9．6 BIBLIOGRAPHIC NOTES 271

9．7 EXERCISES 271

10 INTRODUCTION TO TRANSACTION MANAGEMENT 274

10．1 DEFINITION OF A TRANSACTION 276

10．1．1 Termination Conditions of Transactions 278

10．1．2 Characterization of Transactions 280

10．1．3 Formalization of the Transaction Concept 281

10．2．1 Atomicity 283

10．2 PROPERTIES OF TRANSACTIONS 283

10．2．2 Consistency 284

10．2．3 Isolation 285

10．2．4 Durability 288

10．3 TYPES OF TRANSACTIONS 288

10．3．1 Flat Transactions 290

10．3．2 Nested Transactions 290

10．3．3 Workflows 292

10．4 ARCHITECTURE REVISITED 295

10．6 BIBLIOGRAPHIC NOTES 297

10．5 CONCLUSION 297

11 DISTRIBUTED CONCURRENCY CONTROL 299

11．1 SERIALIZABILITY THEORY 300

11．2 TAXONOMY OF CONCURRENCY CONTROL MECHANISMS 306

11．3 LOCKING-BASED CONCURRENCY CONTROL ALGORITHMS 308

11．3．1 Centralized 2PL 318

11．3．2 Primary Copy 2PL 322

11．3．3 Distributed 2PL 322

11．4 TIMESTAMP-BASED CONCURRENCY CONTROL ALGORITHMS 324

11．4．1 Basic TO Algorithm 325

11．4．2 Conservative TO Algorithm 329

11．4．3 Multiversion TO Algorithm 331

11．5 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS 332

11．6 DEADLOCK MANAGEMENT 335

11．6．1 Deadlock Prevention 337

11．6．2 Deadlock Avoidance 337

11．6．3 Deadlock Detection and Resolution 339

11．7 RELAXED CONCURRENCY CONTROL 342

11．7．1 Non-Serializable Schedules 342

11．7．2 Nested Distributed Transactions 343

11．8 CONCLUSION 345

11．9 BIBLIOGRAPHIC NOTES 349

11．10 EXERCISES 350

12 DISTRIBUTED DBMS RELIABILITY 352

12．1 RELIABILITY CONCEPTS AND MEASURES 353

12．1．1 System, State, and Failure 353

12．1．2 Reliability and Availability 356

12．1．3 Mean Time between Failures/Mean Time to Repair 357

12．2 FAILURES AND FAULT TOLERANCE IN DISTRIBUTED SYSTEMS 358

12．2．1 Reasons for Failures 358

12．2．2 Basic Fault Tolerance Approaches and Techniques 360

12．3 FAILURES IN DISTRIBUTED DBMS 363

12．3．1 Transaction Failures 363

12．3．2 Site（System）Failures 363

12．3．3 Media Failures 364

12．3．4 Communication Failures 364

12．4 LOCAL RELIABILITY PROTOCOLS 365

12．4．1 Architectural Considerations 365

12．4．2 Recovery Information 369

12．4．3 Execution of LRM Commands 373

12．4．5 Handling Media Failures 378

12．4．4 Checkpointing 378

12．5 DISTRIBUTED RELIABILITY PROTOCOLS 379

12．5．1 Components of Distributed Reliability Protocols 380

12．5．2 Two-Phase Commit Protocol 381

12．5．3 Variations of 2PC 388

12．6 DEALING WITH SITE FAILURES 390

12．6．1 Termination and Recovery Protocols for 2PC 390

12．6．2 Three-Phase Commit Protocol 396

12．7 NETWORK PARTITIONING 401

12．7．2 Voting-based Protocols 403

12．7．1 Centralized Protocols 403

12．7．3 Replication and Replica Control Protocols 406

12．7．4 Strict Replica Control Protocols 406

12．7．5 Lazy Replication Protocols 410

12．8 ARCHITECTURAL CONSIDERATIONS 411

12．9 CONCLUSION 412

12．10 BIBLIOGRAPHIC NOTES 413

12．11 EXERCISES 414

13 PARALLEL DATABASE SYSTEMS 416

13．1．1 Database Server Approach 417

13．1 DATABASE SERVERS 417

13．1．2 Database Servers and Distributed Databases 419

13．2 PARALLEL ARCHITECTURES 420

13．2．1 Objectives 420

13．2．2 Functional Aspects 422

13．2．3 Parallel System Architectures 424

13．3 PARALLEL DBMS TECHNIQUES 430

13．3．1 Data Placement 430

13．3．2 Query Parallelism 435

13．3．3 Parallel Data Processing 436

13．3．4 Parallel Query Optimization 444

13．4 PARALLEL EXECUTION PROBLEMS 449

13．4．1 Initialization 449

13．4．2 Interferences and Convoy Effect 449

13．4．3 Load Balancing 450

13．5 PARALLEL EXECUTION FOR HIERARCHICAL ARCHITECTURE 452

13．5．1 Problem Formulation 453

13．5．2 Basic Concepts 454

13．5．3 Load Balancing Strategy 457

13．5．4 Performance Evaluation 458

13．6 CONCLUSION 458

13．7 BIBLIOGRAPHIC NOTES 459

13．8 EXERCISES 460

14 DISTRIBUTED OBJECT DATABASE MANAGEMENT SYSTEMS 462

14．1 FUNDAMENTAL OBJECY CONCEPTS AND MODELS 464

14．1．1 Object 464

14．1．2 Abstract Data Types 467

14．1．3 Composition（Aggregation） 468

14．1．4 Class 469

14．1．5 Collection 469

14．1．6 Subtyping and Inheritance 470

14．2 OBJECT DISTRIBUTION DESIGN 471

14．2．1 Horizontal Class Partitioning 472

14．2．2 Vertical Class Partitioning 474

14．2．3 Path Partitioning 474

14．2．4 Class Partitioning Algorithms 475

14．2．5 Allocation 476

14．2．6 Replication 476

14．3 ARCHITECTURAL ISSUES 477

14．3．1 Alternative Ciient/Server Architectures 477

14．3．2 Cache Consistency 482

14．4．1 Object Identifier Management 484

14．4 OBJECT MANAGEMENT 484

14．4．2 Pointer Swizzling 486

14．4．3 Object Migration 487

14．5 DISTRIBUTED OBJECT STORAGE 488

14．6 OBJECT QUERY PROCESSING 491

14．6．1 Object Query Processor Architectures 493

14．6．2 Query Processing Issues 495

14．6．3 Query Execution 500

14．7 TRANSACTION MANAGEMENT 504

14．7．1 Correctness Criteria 505

14．7．2 Transaction Models and Object Structures 510

14．7．3 Transactions Management in Object DBMSs 511

14．7．4 Transactions as Objects 520

14．8 CONCLUSION 522

14．9 BIBLIOGRAPHIC NOTES 522

14．10 EXERCISES 523

15 DATABASE INTEROPERABILITY 525

15．1 DATABASE INTEGRATION 525

15．1．1 Schema Translation 528

15．1．2 Schema Integration 529

15．2 QUERY PROCESSING 537

15．2．1 Query Processing Layers in Distributed Multi-DBMSs 539

15．2．2 Query Optimization Issues 541

15．3 TRANSACTION MANAGEMENT 545

15．3．1 Transaction and Computation Model 545

15．3．2 Multidatabase Concurrency Control 548

15．3．3 Multidatabase Recovery 552

15．4 OBJECT ORIENTATION AND INTEROPERABILITY 553

15．4．1 Object Management Architecture 555

15．4．2 CORBA and Database Interoperability 559

15．4．3 Distributed Component Object Model 562

15．4．4 COM/OLE and Database Interoperability 564

15．5 CONCLUSION 565

15．6 BIBLIOGRAPHIC NOTES 566

15．7 EXERCISES 567

16 CURRENT ISSUES 571

16．1 DATA DELIVERY ALTERNATIVES 573

16．2 DATA WAREHOUSING 575

16．2．1 Architectures 575

16．2．2 OLAP Data Model 577

16．2．3 OLAP Servers 579

16．2．4 Research Issues 580

16．3 WORLD WIDE WEB 581

16．3．1 Architecture and Protocols 581

16．3．2 Database Access 582

16．3．3 Semistructured Data 583

16．3．4 Architectures for Information Integration 585

16．3．5 Research Projects and Open Issues 586

16．4 PUSH-BASED TECHNOLOGIES 588

16．4．1 Delivery Schedule Generation 589

16．4．2 Client Cache Management 592

16．4．3 Propagating Updates 595

16．5 MOBILE DATABASES 596

16．5．1 Directory Management 598

16．5．2 Caching 599

16．5．3 Broadcast Data 600

16．5．4 Query Processing and Optimization 600

16．5．5 Transaction Management 601

16．6 BIBLIOGRAPHIC NOTES 602

BIBLIOGRAPHY 605

SUBJECT INDEX 658