数据库管理系统 第2版PDF|Epub|txt|kindle电子书版本网盘下载

数据库管理系统 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Part Ⅰ BASICS1

1 INTRODUCTION TO DATABASE SYSTEMS3

1.1 Overview4

1.2 A Historical Perspective5

1.3 File Systems versus a DBMS7

1.4 Advantages ofa DBMS8

1.5 Describing and Storing Data in a DBMS9

1.5.1 The Relational Model10

1.5.2 Levels of Abstraction in a DBMS11

1.5.3 Data Independence14

1.6 Queries in a DBMS15

1.7 Transaction Management15

1.7.1 Concurrent Execution of Transactions16

1.7.2 Incomplete Transactions and System Crashes17

1.7.3 Points to Note18

1.8 Structure of a DBMS18

1.9 People Who Deal with Databases20

1.10 Points to Review21

2 THE ENTITY-RELATIONSHIP MODEL24

2.1 Overview of Database Design24

2.1.1 Beyond the ER Model25

2.2 Entities,Attributes,and Entity Sets26

2.3 Relationships and Relationship Sets27

2.4 Additional Features of the ER Model30

2.4.1 Key Constraints30

2.4.2 Participation Constraints32

2.4.3 Weak Entities33

2.4.4 Class Hierarchies35

2.4.5 Aggregation37

2.5 Conceptual Database Design With the ER Model38

2.5.1 Entity versus Attribute39

2.5.2 Entity versus Relationship40

2.5.3 Binary versus Ternary Relationships41

2.5.4 Aggregation versus Ternary Relationships43

2.6 Conceptual Design for Large Enterprises44

2.7 Points to Review45

3 THE RELATIONAL MODEL51

3.1 Introduction to the Relational Model52

3.1.1 Creating and Modifying Relations Using SQL-9255

3.2 Integrity Constraints over Relations56

3.2.1 Key Constraints57

3.2.2 Foreign Key Constraints59

3.2.3 General Constraints61

3.3 Enforcing Integrity Constraints62

3.4 Querying Relational Data64

3.5 Logical Database Design:ER to Relational66

3.5.1 Entity Sets to Tables67

3.5.2 Relationship Sets(without Constraints)to Tables67

3.5.3 Translating Relationship Sets with Key Constraints69

3.5.4 Translating Relationship Sets with Participation Constraints71

3.5.5 Translating Weak Entity Sets73

3.5.6 Translating Class Hierarchies74

3.5.7 Translating ER Diagrams with Aggregation75

3.5.8 ER to Relational:Additional Examples76

3.6 Introduction to Views78

3.6.1 Views,Data Independence,Security79

3.6.2 Updates on Views79

3.7 Destroying/Altering Tables and Views82

3.8 Points to Review83

Part Ⅱ RELATIONAL QUERIES89

4 RELATIONAL ALGEBRA AND CALCULUS91

4.1 Preliminaries91

4.2 Relational Algebra92

4.2.1 Selection and Projection93

4.2.2 Set Operations94

4.2.3 Renaming96

4.2.4 Joins97

4.2.5 Division99

4.2.6 More Examples of Relational Algebra Queries100

4.3 Relational Calculus106

4.3.1 Tupie Relational Calculus107

4.3.2 Domain Relational Calculus111

4.4 Expressive Power of Algebra and Calculus114

4.5 Points to Review115

5 SQL:QUERIES,PROGRAMMING,TRIGGERS119

5.1 About the Examples121

5.2 The Form of a Basic SQL Query121

5.2.1 Examples of Basic SQL Queries126

5.2.2 Expressions and Strings in the SELECT Command127

5.3 UNION,INTERSECT,and EXCEPT129

5.4 Nested Queries132

5.4.1 Introduction to Nested Queries132

5.4.2 Correlated Nested Queries134

5.4.3 Set-Comparison Operators135

5.4.4 More Examples of Nested Queries136

5.5 Aggregate Operators138

5.5.1 The GROUP BY and HAVING Clauses140

5.5.2 More Examples of Aggregate Queries143

5.6 Null Values147

5.6.1 Comparisons Using Null Values147

5.6.2 Logical Connectives AND,OR,and NOT148

5.6.3 Impact on SQL Constructs148

5.6.4 Outer Joins149

5.6.5 Disallowing Null Values150

5.7 Embedded SQL150

5.7.1 Declaring Variables and Exceptions151

5.7.2 Embedding SQL Statements152

5.8 Cursors153

5.8.1 Basic Cursor Defmition and Usage153

5.8.2 Properties of Cursors155

5.9 Dynamic SQL156

5.10 ODBC and JDBC157

5.10.1 Architecture158

5.10.2 An Example Using JDBC159

5.11 Complex Integrity Constraints in SQL-92161

5.11.1 Constraints over a Single Table161

5.11.2 Domain Constraints162

5.11.3 Assertions:ICs over Several Tables163

5.12 Triggers and Active Databases164

5.12.1 Examples of Triggers in SQL165

5.13 Designing Active Databases166

5.13.1 Why Triggers Can Be Hard to Understand167

5.13.2 Constraints versus Triggers167

5.13.3 Other Uses of Triggers168

5.14 Points to Review168

6 QUERY-BY-EXAMPLE(QBE)177

6.1 Introduction177

6.2 Basic QBE Queries178

6.2.1 Other Features:Duplicates,Ordering Answers179

6.3 Queries over Multiple Relations180

6.4 Negation in the Relation-Name Column181

6.5 Aggregates181

6.6 The Conditions Box183

6.6.1 And/Or Queries184

6.7 Unnamed Columns185

6.8 Updates185

6.8.1 Restrictions on Update Commands187

6.9 Division and Relational Completeness187

6.10 Points to Review189

Part Ⅲ DATA STORAGE AND INDEXING193

7 STORING DATA:DISKS AND FILES195

7.1 The Memory Hierarchy196

7.1.1 Magnetic Disks197

7.1.2 Performance Implications of Disk Structure199

7.2 RAID200

7.2.1 Data Striping200

7.2.2 Redundancy201

7.2.3 Levels of Redundancy203

7.2.4 Choice of RAID Levels206

7.3 Disk Space Management207

7.3.1 Keeping Track of Free Blocks207

7.3.2 Using OS File Systems to Manage Disk Space207

7.4 Buffer Manager208

7.4.1 Buffer Replacement Policies211

7.4.2 Buffer Management in DBMS versus OS212

7.5 Files and Indexes214

7.5.1 Heap Files214

7.5.2 Introduction to Indexes216

7.6 Page Formats218

7.6.1 Fixed-Length Records218

7.6.2 Variable-Length Records219

7.7 Record Formats221

7.7.1 Fixed-Length Records222

7.7.2 Variable-Length Records222

7.8 Points to Review224

8 FILE ORGANIZATIONS AND INDEXES230

8.1 Cost Model231

8.2 Comparison of Three File Organizations232

8.2.1 Heap Files232

8.2.2 Sorted Files233

8.2.3 Hashed Files235

8.2.4 Choosing a File Organization236

8.3 Overview of Indexes237

8.3.1 Alternatives for Data Entries in an Index238

8.4 Properties of Indexes239

8.4.1 Clustered versus Unclustered Indexes239

8.4.2 Dense versus Sparse Indexes241

8.4.3 Primary and Secondary Indexes242

8.4.4 Indexes Using Composite Search Keys243

8.5 Index Specification in SQL-92244

8.6 Points to Review244

9 TREE-STRUCTURED INDEXING247

9.1 Indexed Sequential Access Method(ISAM)248

9.2 B+ Trees:A Dynamic Index Structure253

9.3 Format of a Node254

9.4 Search255

9.5 Insert257

9.6 Delete260

9.7 Duplicates265

9.8 B+Trees in Practice266

9.8.1 Key Compression266

9.8.2 Bulk-Loading a B+Tree268

9.8.3 The Order Concept271

9.8.4 The Effect of Inserts and Deletes on Rids272

9.9 Points to Review272

10 HASH-BASED INDEXING278

10.1 Static Hashing278

10.1.1 Notation and Conventions280

10.2 Extendible Hashing280

10.3 Linear Hashing286

10.4 Extendible Hashing versus Linear Hashing291

10.5 Points to Review292

Part Ⅳ QUERY EVALUATION299

11 EXTERNAL SORTING301

11.1 A Simple Two-Way Merge Sort302

11.2 External Merge Sort305

11.2.1 Minimizing the Number of Runs308

11.3 Minimizing I/O Cost versus Number of I/Os309

11.3.1 Blocked I/O310

11.3.2 Double Buffering311

11.4 Using B+Trees for Sorting312

11.4.1 Clustered Index312

11.4.2 Unclustered Index313

11.5 Points to Review315

12 EVALUATION OF RELATIONAL OPERATORS319

12.1 Introduction to Query Processing320

12.1.1 Access Paths320

12.1.2 Preliminaries:Examples and Cost Calculations321

12.2 The Selection Operation321

12.2.1 No Index,Unsorted Data322

12.2.2 No Index,Sorted Data322

12.2.3 B+ Tree Index323

12.2.4 Hash Index,Equality Selection324

12.3 General Selection Conditions325

12.3.1 CNF and Index Matching325

12.3.2 Evaluating Selections without Disjunction326

12.3.3 Selections with Disjunction327

12.4 The Projection Operation329

12.4.1 Projection Based on Sorting329

12.4.2 Projection Based on Hashing330

12.4.3 Sorting versus Hashing for Projections332

12.4.4 Use of Indexes for Projections333

12.5 The Join Operation333

12.5.1 Nested Loops Join334

12.5.2 Sort-Merge Join339

12.5.3 Hash Join343

12.5.4 General Join Conditions348

12.6 The Set Operations349

12.6.1 Sorting for Union and Difference349

12.6.2 Hashing for Union and Difference349

12.7 Aggregate Operations350

12.7.1 Implementing Aggregation by Using an Index351

12.8 The Impact of BufIering352

12.9 Points to Review353

13 INTRODUCTION TO QUERY OPTIMIZATION359

13.1 Overview of Relational Query Optimization360

13.1.1 Query Evaluation Plans361

13.1.2 Pipelined Evaluation362

13.1.3 The Iterator Intefface for Operators and Access Methods363

13.1.4 The System R Optimizer364

13.2 System Catalog in a Relational DBMS365

13.2.1 Information Stored in the System Catalog365

13.3 Alternative Plans:A Motivating Example368

13.3.1 Pushing Selections368

13.3.2 Using Indexes370

13.4 Points to Review373

14 A TYPICAL RELATIONAL QUERY OPTIMIZER374

14.1 Translating SQL Queries into Algebra375

14.1.1 Decomposition of a Query into Blocks375

14.1.2 A Query Block as a Relational Algebra Expression376

14.2 Estimating the Cost of a Plan378

14.2.1 Estimating Result Sizes378

14.3 Relational Algebra Equivalences383

14.3.1 Selections383

14.3.2 Projections384

14.3.3 Cross-Products and Joins384

14.3.4 Selects,Projects,and Joins385

14.3.5 Other Equivalences387

14.4 Enumeration of Alternative Plans387

14.4.1 Single-Relation Queries387

14.4.2 Multiple-Relation Queries392

14.5 Nested Subqueries399

14.6 Other Approaches to Query Optimization402

14.7 Points to Review403

Part Ⅴ DATABASE DESIGN415

15 SCHEMA REFINEMENT AND NORMAL FORMS417

15.1 Introduction to Schema Refinement418

15.1.1 Problems Caused by Redundancy418

15.1.2 Use of Decompositions420

15.1.3 Problems Related to Decomposition421

15.2 Functional Dependencies422

15.3 Examples Motivating Schema Refinement423

15.3.1 Constraints on an Entity Set423

15.3.2 Constraints on a Relationship Set424

15.3.3 Identifying Attributes of Entities424

15.3.4 Identifying Entity Sets426

15.4 Reasoning about Functional Dependencies427

15.4.1 Closure of a Set of FDs427

15.4.2 Attribute Closure429

15.5 Normal Forms430

15.5.1 Boyce-Codd Normal Form430

15.5.2 Third Normal Form432

15.6 Decompositions434

15.6.1 Lossless-Join Decomposition435

15.6.2 Dependency-Preserving Decomposition436

15.7 Normalization438

15.7.1 Decomposition into BCNF438

15.7.2 Decomposition into 3NF440

15.8 Other Kinds of Dependencies444

15.8.1 Multivalued Dependencies445

15.8.2 Fourth Normal Form447

15.8.3 Join Dependencies449

15.8.4 Fifth Normal Form449

15.8.5 Inclusion Dependencies449

15.9 Points to Review450

16 PHYSICAL D ATA BASE DESIGN AND TUNING457

16.1 Introduction to Physical Database Design458

16.1.1 Database Workloads458

16.1.2 Physical Design and Tuning Decisions459

16.1.3 Need for Database Tuning460

16.2 Guidelines for Index Selection460

16.3 Basic Examples of Index Selection463

16.4 Clustering and Indexing465

16.4.1 Co-clustering Two Relations468

16.5 Indexes on Multiple-Attribute Search Keys470

16.6 Indexes that Enable Index-Only Plans471

16.7 Overview of Database Tuning474

16.7.1 Tuning Indexes474

16.7.2 Tuning the Conceptual Schema475

16.7.3 Tuning Queries and Views476

16.8 Choices in Tuning the Conceptual Schema477

16.8.1 Settling for a Weaker Normal Form478

16.8.2 Denormalization478

16.8.3 Choice of Decompositions479

16.8.4 Vertical Decomposition480

16.8.5 Horizontal Decomposition481

16.9 Choices in Tuning Queries and Views482

16.10 Impact of Concurrency484

16.11 DBMS Benchmarking485

16.11.1 Well-Known DBMS Benchmarks486

16.11.2 Using a Benchmark486

16.12 Points to Review487

17 SECURITY497

17.1 Introduction to Database Security497

17.2 Access Control498

17.3 Discretionary Access Control499

17.3.1 Grant and Revoke on Views and Integrity Constraints506

17.4 Mandatory Access Control508

17.4.1 Multilevel Relations and Polyinstantiation510

17.4.2 Covert Channels,DoD Security Levels511

17.5 Additional Issues Related to Security512

17.5.1 Role of the Database Administrator512

17.5.2 Security in Statistical Databases513

17.5.3 Encryption514

17.6 Points to Review517

Part Ⅵ TRANSACTION MANAGEMENT521

18 TRANSACTION MANAGEMENT OVERVIEW523

18.1 The Concept of a Transaction523

18.1.1 Consistency and Isolation525

18.1.2 Atomicity and Durability525

18.2 Transactions and Schedules526

18.3 Concurrent Execution of Transactions527

18.3.1 Motivation for Concurrent Execution527

18.3.2 Serializability528

18.3.3 Some Anomalies Associated with Interleaved Execution528

18.3.4 Schedules Involving Aborted Transactions531

18.4 Lock-Based Concurrency Control532

18.4.1 Strict Two-Phase Locking(Strict 2PL)532

18.5 Introduction to Crash Recovery533

18.5.1 Stealing Frames and Forcing Pages535

18.5.2 Recovery-Related Steps during Normal Execution536

18.5.3 Overview of ARIES537

18.6 Points to Review537

19 CONCURRENCY CONTROL540

19.1 Lock-Based Concurrency Control Revisited540

19.1.1 2PL,Serializability,and Recoverability540

19.1.2 View Serializability543

19.2 Lock Management543

19.2.1 Implementing Lock and Unlock Requests544

19.2.2 Deadlocks546

19.2.3 Performance of Lock-Based Concurrency Control548

19.3 Specialized Locking Techniques549

19.3.1 Dynamic Databases and the Phantom Problem550

19.3.2 Concurrency Control in B+ Trees551

19.3.3 Multiple-Granularity Locking554

19.4 Transaction Support in SQL-92555

19.4.1 Transaction Characteristics556

19.4.2 Transactions and Constraints558

19.5 Concurrency Control without Locking559

19.5.1 Optimistic Concurrency Control559

19.5.2 Timestamp-Based Concurrency Control561

19.5.3 Multiversion Concurrency Control563

19.6 Points to Review564

20 CRASH RECOVERY571

20.1 Introduction to ARIES571

20.1.1 The Log573

20.1.2 Other Recovery-Related Data Structures576

20.1.3 The Write-Ahead Log Protocol577

20.1.4 Checkpointing578

20.2 Recovering from a System Crash578

20.2.1 Analysis Phase579

20.2.2 Redo Phase581

20.2.3 Undo Phase583

20.3 Media Recovery586

20.4 Other Algorithms and Interaction with Concurrency Control587

20.5 Points to Review588

Part Ⅶ ADVANCED TOPICS595

21 PARALLEL AND DISTRIBUTED DATABASES597

21.1 Architectures for Parallel Databases598

21.2 Parallel Query Evaluation600

21.2.1 Data Partitioning601

21.2.2 Parallelizing Sequential Operator Evaluation Code601

21.3 Parallelizing Individual Operations602

21.3.1 Bulk Loading and Scanning602

21.3.2 Sorting602

21.3.3 Joins603

21.4 Parallel Query Optimization606

21.5 Introduction to Distributed Databases607

21.5.1 Types of Distributed Databases607

21.6 Distributed DBMS Architectures608

21.6.1 Client-Server Systems608

21.6.2 Collaborating Server Systems609

21.6.3 Middleware Systems609

21.7 Storing Data in a Distributed DBMS610

21.7.1 Fragmentation610

21.7.2 Replication611

21.8 Distributed Catalog Management611

21.8.1 Naming Objects612

21.8.2 Catalog Structure612

21.8.3 Distributed Data Independence613

21.9 Distributed Query Processing614

21.9.1 Nonjoin Queries in a Distributed DBMS614

21.9.2 Joins in a Distributed DBMS615

21.9.3 Cost-Based Query Optimization619

21.10 Updating Distributed Data619

21.10.1 Synchronous Replication620

21.10.2 Asynchronous Replication621

21.11 Introduction to Distributed Transactions624

21.12 Distributed Concurrency Control625

21.12.1 Distributed Deadlock625

21.13 Distributed Recovery627

21.13.1 Normal Execution and Commit Protocols628

21.13.2 Restart after a Failure629

21.13.3 Two-Phase Commit Revisited630

21.13.4 Three-Phase Commit632

21.14 Points to Review632

22 INTERNET DATABASES642

22.1 The World Wide Web643

22.1.1 Introduction to HTML643

22.1.2 Databases and the Web645

22.2 Architecture645

22.2.1 Application Servers and Server-Side Java647

22.3 Beyond HTML651

22.3.1 Introduction to XML652

22.3.2 XML DTDs654

22.3.3 Domain-Specific DTDs657

22.3.4 XML-QL:Querying XML Data659

22.3.5 The Semistructured Data Model661

22.3.6 Implementation Issues for Semistructured Data663

22.4 Indexing for Text Search663

22.4.1 Inverted Files665

22.4.2 Signature Files666

22.5 Ranked Keyword Searches on the Web667

22.5.1 An Algorithm for RankingWeb Pages668

22.6 Points to Review671

23 DECISION SUPPORT677

23.1 Introduction to Decision Support678

23.2 Data Warehousing679

23.2.1 Creating and Maintaining a Warehouse680

23.3 OLAP682

23.3.1 Multidimensional Data Model682

23.3.2 OLAP Queries685

23.3.3 Database Design for OLAP689

23.4 Implementation Techniques for OLAP690

23.4.1 Bitmap Indexes691

23.4.2 Join Indexes692

23.4.3 File Organizations693

23.4.4 Additional OLAP Implementation Issues693

23.5 Views and Decision Support694

23.5.1 Views,OLAP,and Warehousing694

23.5.2 Query Modification695

23.5.3 View Materialization versus Computing on Demand696

23.5.4 Issues in View Materialization698

23.6 Finding Answers Quickly699

23.6.1 Top N Queries700

23.6.2 Online Aggregation701

23.7 Points to Review702

24 DATA MINING707

24.1 Introduction to Data Mining707

24.2 Counting Co-occurrences708

24.2.1 Frequent Itemsets709

24.2.2 Iceberg Queries711

24.3 Mining for Rules713

24.3.1 Association Rules714

24.3.2 An Algorithm for Finding Association Rules714

24.3.3 Association Rules and ISA Hierarchies715

24.3.4 Generalized Association Rules716

24.3.5 Sequential Patterns717

24.3.6 The Use of Association Rules for Prediction718

24.3.7 Bayesian Networks719

24.3.8 Classification and Regression Rules720

24.4 Tree-Structured Rules722

24.4.1 Decision Trees723

24.4.2 An Algorithm to Build Decision Trees725

24.5 Clustering726

24.5.1 A Clustering Algorithm728

24.6 Similarity Search over Sequences729

24.6.1 An Algorithm to Find Similar Sequences730

24.7 Additional Data Mining Tasks731

24.8 Points to Review732

25 OBJECT-DATABASE SYSTEMS736

25.1 Motivating Example737

25.1.1 New Data Types738

25.1.2 Manipulating the New Kinds of Data739

25.2 User-Defined Abstract Data Types742

25.2.1 Defining Methods of an ADT743

25.3 Structured Types744

25.3.1 Manipulating Data of Structured Types745

25.4 Objects,Object Identity,and Reference Types748

25.4.1 Notions of Equality749

25.4.2 Dereferencing Reference Types750

25.5 Inheritance750

25.5.1 Defining Types with Inheritance751

25.5.2 Binding of Methods751

25.5.3 Collection Hierarchies,Type Extents,and Queries752

25.6 Database Design for an ORDBMS753

25.6.1 Structured Types and ADTs753

25.6.2 Object Identity756

25.6.3 Extending the ER Model757

25.6.4 Using Nested Collections758

25.7 New Challenges in Implementing an ORDBMS759

25.7.1 Storage and Access Methods760

25.7.2 Query Processing761

25.7.3 Query Optimization763

25.8 OODBMS765

25.8.1 The ODMG Data Model and ODL765

25.8.2 OQL768

25.9 Comparing RDBMS with OODBMS and ORDBMS769

25.9.1 RDBMS versus ORDBMS769

25.9.2 OODBMS versus ORDBMS:Similarities770

25.9.3 OODBMS versus ORDBMS:Differences770

25.10 Points to Review771

26 SPATIAL DATA MANAGEMENT777

26.1 Types of Spatial Data and Queries777

26.2 Applications Involving Spatial Data779

26.3 Introduction to Spatial Indexes781

26.3.1 Overview of Proposed Index Structures782

26.4 Indexing Based on Space-Filling Curves783

26.4.1 Region Quad Trees and Z-Ordering:Region Data784

26.4.2 Spatial Queries Using Z-Ordering785

26.5 Grid Files786

26.5.1 Adapting Grid Files to Handle Regions789

26.6 R Trees:Point and Region Data789

26.6.1 Queries790

26.6.2 Insert and Delete Operations792

26.6.3 Concurrency Control793

26.6.4 Generalized Search Trees794

26.7 Issues in High-Dimensional Indexing795

26.8 Points to Review795

27 DEDUCTIVE DATABASES799

27.1 Introduction to Recursive Queries800

27.1.1 Datalog801

27.2 Theoretical Foundations803

27.2.1 Least Model Semantics804

27.2.2 Safe Datalog Programs805

27.2.3 The Fixpoint Operator806

27.2.4 Least Model=Least Fixpoint807

27.3 Recursive Queries with Negation808

27.3.1 Range-Restriction and Negation809

27.3.2 Stratification809

27.3.3 Aggregate Operations812

27.4 Efficient Evaluation of Recursive Queries813

27.4.1 Fixpoint Evaluation without Repeated Inferences814

27.4.2 Pushing Selections to Avoid Irrelevant Inferences816

27.5 Points to Review818

28 ADDITIONAL TOPICS822

28.1 Advanced Transaction Processing822

28.1.1 Transaction Processing Monitors822

28.1.2 New Transaction Models823

28.1.3 Real-Time DBMSs824

28.2 Integrated Access to Multiple Data Sources824

28.3 Mobile Databases825

28.4 Main Memory Databases825

28.5 Multimedia Databases826

28.6 Geographic Information Systems827

28.7 Temporal and Sequence Databases828

28.8 Information Visualization829

28.9 Summary829

A DATABASE DESIGN CASE STUDY:THE INTERNET SHOP831

A.1 Requirements Analysis831

A.2 Conceptual Design832

A.3 Logical Database Design832

A.4 Schema Refinement835

A.5 Physical Database Design836

A.5.1 Tuning the Database838

A.6 Security838

A.7 Application Layers840

B THE MINIBASE SOFTWARE842

B.1 Whats Available842

B.2 Overview of Minibase Assignments843

B.2.1 Overview of Programming Projects843

B.2.2 Overview of Nonprogramming Assignments844

B.3 Acknowledgments845

REFERENCES847

SUBJECT INDEX879

AUTHOR INDEX896