数据库管理系统原理与设计 第3版PDF电子书下载

Part ⅠFOUNDATIONS 1

1 OVERVIEW OF DATABASE SYSTEMS 3

1.1 Managing Data 4

1.2 A Historical Perspective 6

1.3 File Systems versus a DBMS 8

1.4 Advantages of a DBMS 9

1.5 Describing and Storing Data in a DBMS 10

1.5.1The Relational Model 11

1.5.2Levels of Abstraction in a DBMS 12

1.5.3Data Independence 15

1.6 Queries in a DBMS 16

1.7 Transaction Management 17

1.7.1Concurrent Execution of Transactions 17

1.7.2Incomplete Transactions and System Crashes 18

1.7.3Points to Note 19

1.8 Structure of a DBMS 19

1.9 People Who Work with Databases 21

1.10 Review Questions 22

2 INTRODUCTION TO DATABASE DESIGN 25

2.1 Database Design and ER Diagrams 26

2.1.1Beyond ER Design 27

2.2 Entities，Attributes，and Entity Sets 28

2.3 Relationships and Relationship Sets 29

2.4 Additional Features of the ER Model 32

2.4.1Key Constraints 32

2.4.2Participation Constraints 34

2.4.3Weak Entities 35

2.4.4Class Hierarchies 37

2.4.5Aggregation 39

2.5 Conceptual Design With the ER Model 40

2.5.1Entity versus Attribute 41

2.5.2Entity versus Relationship 42

2.5.3Binary versus Ternary Relationships 43

2.5.4Aggregation versus Ternary Relationships 45

2.6 Conceptual Design for Large Enterprises 46

2.7 The Unified Modeling Language 47

2.8 Case Study：The Internet Shop 49

2.8.1Requirements Analysis 49

2.8.2Conceptual Design 50

2.9 Review Questions 51

3 THE RELATIONAL MODEL 57

3.1 Introduction to the Relational Model 59

3.1.1Creating and Modifying Relations Using SQL 62

3.2 Integrity Constraints over Relations 63

3.2.1Key Constraints 64

3.2.2Foreign Key Constraints 66

3.2.3General Constraints 68

3.3 Enforcing Integrity Constraints 69

3.3.1Transactions and Constraints 72

3.4 Querying Relational Data 73

3.5 Logical Database Design：ER to Relational 74

3.5.1Entity Sets to Tables 75

3.5.2Relationship Sets （without Constraints） to Tables 76

3.5.3Translating Relationship Sets with Key Constraints 78

3.5.4Translating Relationship Sets with Participation Constraints 79

3.5.5Translating Weak Entity Sets 82

3.5.6Translating Class Hierarchies 83

3.5.7Translating ER Diagrams with Aggregation 84

3.5.8ER to Relational： Additional Examples 85

3.6 Introduction to Views 86

3.6.1Views，Data Independence，Security 87

3.6.2Updates on Views 88

3.7 Destroying/Altering Tables and Views 91

3.8 Case Study：The Internet Store 92

3.9 Review Questions 94

4 RELATIONAL ALGEBRA AND CALCULUS 100

4.1 Preliminaries 101

4.2 Relational Algebra 102

4.2.1Selection and Projection 103

4.2.2Set Operations 104

4.2.3Renaming 106

4.2.4Joins 107

4.2.5Division 109

4.2.6More Examples of Algebra Queries 110

4.3 Relational Calculus 116

4.3.1Tuple Relational Calculus 117

4.3.2Domain Relational Calculus 122

4.4 Expressive Power of Algebra and Calculus 124

4.5 Review Questions 126

5 SQL：QUERIES，CONSTRAINTS，TRIGGERS 130

5.1 Overview 131

5.1.1Chapter Organization 132

5.2 The Form of a Basic SQL Query 133

5.2.1Examples of Basic SQL Queries 138

5.2.2Expressions and Strings in the SELECT Command 139

5.3 UNION， INTERSECT，and EXCEPT 141

5.4 Nested Queries 144

5.4.1Introduction to Nested Queries 145

5.4.2Correlated Nested Queries 147

5.4.3Set-Comparison Operators 148

5.4.4More Examples of Nested Queries 149

5.5 Aggregate Operators 151

5.5.1The GROUP BY and HAVING Clauses 154

5.5.2More Examples of Aggregate Queries 158

5.6 Null Values 162

5.6.1Comparisons Using Null Values 163

5.6.2Logical Connectives AND，OR，and NOT 163

5.6.3Impact on SQL Constructs 163

5.6.4Outer Joins 164

5.6.5Disallowing Null Values 165

5.7 Complex Integrity Constraints in SQL 165

5.7.1Constraints over a Single Table 165

5.7.2Domain Constraints and Distinct Types 166

5.7.3Assertions： ICs over Several Tables 167

5.8 Triggers and Active Databases 168

5.8.1Examples of Triggers in SQL 169

5.9 Designing Active Databases 171

5.9.1Why Triggers Can Be Hard to Understand 171

5.9.2Constraints versus Triggers 172

5.9.3Other Uses of Triggers 172

5.10 Review Questions 173

Part ⅡAPPLICATION DEVELOPMENT 183

6DATABASE APPLICATION DEVELOPMENT 185

6.1 Accessing Databases from Applications 187

6.1.1Embedded SQL 187

6.1.2Cursors 189

6.1.3Dynamic SQL 194

6.2 An Introduction to JDBC 194

6.2.1Architecture 196

6.3 JDBC Classes and Interfaces 197

6.3.1JDBC Driver Management 197

6.3.2Connections 198

6.3.3Executing SQL Statements 200

6.3.4ResultSets 201

6.3.5Exceptions and Warnings 203

6.3.6Examining Database Metadata 204

6.4 SQLJ 206

6.4.1Writing SQLJ Code 207

6.5 Stored Procedures 209

6.5.1Creating a Simple Stored Procedure 209

6.5.2Calling Stored Procedures 210

6.5.3SQL/PSM 212

6.6 Case Study：The Internet Book Shop 214

6.7 Review Questions 216

7 INTERNET APPLICATIONS 220

7.1 Introduction 220

7.2 Internet Concepts 221

7.2.1Uniform Resource Identifiers 221

7.2.2The Hypertext Transfer Protocol（HTTP） 223

7.3 HTML Documents 226

7.4 XML Documents 227

7.4.1Introduction to XML 228

7.4.2XML DTDs 231

7.4.3Domain-Specific DTDs 234

7.5 The Three-Tier Application Architecture 236

7.5.1Single-Tier and Client-Server Architectures 236

7.5.2Three-Tier Architectures 239

7.5.3Advantages of the Three-Tier Architecture 241

7.6 The Presentation Layer 242

7.6.1HTML Forms 242

7.6.2JavaScript 245

7.6.3Style Sheets 247

7.7 The Middle Tier 251

7.7.1CGI：The Common Gateway Interface 251

7.7.2Application Servers 252

7.7.3Servlets 254

7.7.4JavaServer Pages 256

7.7.5Maintaining State 258

7.8 Case Study：The Internet Book Shop 261

7.9 Review Questions 264

Part Ⅲ STORAGE AND INDEXING 271

8 OVERVIEW OF STORAGE AND INDEXING 273

8.1 Data on External Storage 274

8.2 File Organizations and Indexing 275

8.2.1Clustered Indexes 277

8.2.2Primary and Secondary Indexes 277

8.3 Index Data Structures 278

8.3.1Hash-Based Indexing 279

8.3.2Tree-Based Indexing 280

8.4 Comparison of File Organizations 282

8.4.1Cost Model 283

8.4.2Heap Files 284

8.4.3Sorted Files 285

8.4.4Clustered Files 287

8.4.5Heap File with Unclustered Tree Index 288

8.4.6Heap File With Unclustered Hash Index 289

8.4.7Comparison of I/O Costs 290

8.5 Indexes and Performance Tuning 291

8.5.1Impact of the Workload 292

8.5.2Clustered Index Organization 292

8.5.3Composite Search Keys 295

8.5.4Index Specification in SQL：1999 299

8.6 Review Questions 299

9 STORING DATA：DISKS AND FILES 304

9.1 The Memory Hierarchy 305

9.1.1Magnetic Disks 306

9.1.2Performance Implications of Disk Structure 308

9.2 Redundant Arrays of Independent Disks 309

9.2.1Data Striping 310

9.2.2Redundancy 311

9.2.3Levels of Redundancy 312

9.2.4Choice of RAID Levels 316

9.3 Disk Space Management 316

9.3.1Keeping Track of Free Blocks 317

9.3.2Using OS File Systems to Manage Disk Space 317

9.4 Buffer Manager 318

9.4.1Buffer Replacement Policies 320

9.4.2Buffer Management in DBMS versus OS 322

9.5 Files of Records 324

9.5.1Implementing Heap Files 324

9.6 Page Formats 326

9.6.1Fixed-Length Records 327

9.6.2Variable-Length Records 328

9.7 Record Formats 330

9.7.1Fixed-Length Records 331

9.7.2Variable-Length Records 331

9.8 Review Questions 333

10 TREE-STRUCTURED INDEXING 338

10.1 Intuition For Tree Indexes 339

10.2 Indexed Sequential Access Method（ISAM） 341

10.2.1Overflow Pages， Locking Considerations 344

10.3 B+Trees： A Dynamic Index Structure 344

10.3.1Format of a Node 346

10.4 Search 347

10.5 Insert 348

10.6 Delete 352

10.7 Duplicates 356

10.8 B+Trees in Practice 358

10.8.1 Key Compression 358

10.8.2 Bulk-Loading a B+Tree 360

10.8.3 The Order Concept 363

10.8.4 The Effect of Inserts and Deletes on Rids 364

10.9 Review Questions 364

11 HASH-BASED INDEXING 370

11.1 Static Hashing 371

11.1.1 Notation and Conventions 373

11.2 Extendible Hashing 373

11.3 Linear Hashing 379

11.4 Extendible vs.Linear Hashing 384

11.5 Review Questions 385

Part Ⅳ QUERY EVALUATION 391

12 OVERVIEW OF QUERY EVALUATION 393

12.1 The System Catalog 394

12.1.1Information in the Catalog 395

12.2 Introduction to Operator Evaluation 397

12.2.1Three Common Techniques 398

12.2.2Access Paths 398

12.3 Algorithms for Relational Operations 400

12.3.1Selection 401

12.3.2Projection 401

12.3.3Join 402

12.3.4Other Operations 404

12.4 Introduction to Query Optimization 404

12.4.1Query Evaluation Plans 405

12.4.2Multi-operator Queries：Pipelined Evaluation 407

12.4.3The Iterator Interface 408

12.5 Alternative Plans：A Motivating Example 409

12.5.1Pushing Selections 409

12.5.2Using Indexes 411

12.6 What a Typical Optimizer Does 414

12.6.1Alternative Plans Considered 414

12.6.2Estimating the Cost of a Plan 416

12.7 Review Questions 417

13 EXTERNAL SORTING 421

13.1 When Does a DBMS Sort Data? 422

13.2 A Simple Two-Way Merge Sort 423

13.3 External Merge Sort 424

13.3.1Minimizing the Number of Runs 428

13.4 MinimizingI/OCost versus Number ofI/Os 430

13.4.1Blocked 1/O 430

13.4.2Double Buffering 432

13.5Using B+ Trees for Sorting 433

13.5.1 Clustered Index 433

13.5.2 Unclustered Index 434

13.6Review Questions 436

14 EVALUATING RELATIONAL OPERATORS 439

14.1 The Selection Operation 441

14.1.1No Index，Unsorted Data 441

14.1.2No Index，Sorted Data 442

14.1.3B+Iree Index 442

14.1.4Hash Index， Equality Selection 444

14.2 General Selection Conditions 444

14.2.1 CNF and Index Matching 445

14.2.2 Evaluating Selections without Disjunction 445

14.2.3 Selections with Disjunction 446

14.3The Projection Operation 447

14.3.1 Projection Based on Sorting 448

14.3.2 Projection Based on Hashing 449

14.3.3 Sorting Versus Hashing for Projections 451

14.3.4 Use of Indexes for Projections 452

14.4The Join Operation 452

14.4.1 Nested Loops Join 454

14.4.2 Sort-Merge Join 458

14.4.3 Hash Join 463

14.4.4 General Join Conditions 467

14.5The Set Operations 468

14.5.1 Sorting for Union and Difference 469

14.5.2 Hashing for Union and Difference 469

14.6Aggregate Operations 469

14.6.1 Implementing Aggregation by Using an Index 471

14.7The Impact of Buffering 471

14.8Review Questions 472

15 A TYPICAL RELATIONAL QUERY OPTIMIZER 478

15.1Translating SQL Queries into Algebra 479

15.1.1 Decomposition of a Query into Blocks 479

15.1.2 A Query Block as a Relational Algebra Expression 481

15.2Estimating the Cost of a Plan 482

15.2.1 Estimating Result Sizes 483

15.3Relational Algebra Equivalences 488

15.3.1 Selections 488

15.3.2 Projections 488

15.3.3 Cross-Products and Joins 489

15.3.4 Selects，Projects，and Joins 490

15.3.5 Other Equivalences 491

15.4Enumeration of Alternative Plans 492

15.4.1 Single-Relation Queries 492

15.4.2 Multiple-Relation Queries 496

15.5Nested Subqueries 504

15.6The System R Optimizer 506

15.7Other Approaches to Query Optimization 507

15.8Review Questions 507

Part V TRANSACTION MANAGEMENT 517

16 OVERVIEW OF TRANSACTION MANAGEMENT 519

16.1The ACID Properties 520

16.1.1 Consistency and Isolation 521

16.1.2 Atomicity and Durability 522

16.2Transactions and Schedules 523

16.3Concurrent Execution of Transactions 524

16.3.1 Motivation for Concurrent Execution 524

16.3.2 Serializability 525

16.3.3 Anomalies Due to Interleaved Execution 526

16.3.4 Schedules Involving Aborted Transactions 529

16.4Lock-Based Concurrency Control 530

16.4.1 Strict Two-Phase Locking （Strict 2PL） 531

16.4.2 Deadlocks 533

16.5Performance of Locking 533

16.6Transaction Support in SQL 535

16.6.1 Creating and Terminating Transactions 535

16.6.2 What Should We Lock? 537

16.6.3 Transaction Characteristics in SQL 538

16.7Introduction to Crash Recovery 540

16.7.1 Stealing Frames and Forcing Pages 541

16.7.2 Recovery-Related Steps during Normal Execution 542

16.7.3 Overview of ARIES 543

16.7.4 Atomicity：Implementing Rollback 543

16.8Review Questions 544

17 CONCURRENCY CONTROL 549

17.12PL，Serializability，and Recoverability 550

17.1.1 View Serializability 553

17.2Introduction to Lock Management 553

17.2.1 Implementing Lock and Unlock Requests 554

17.3Lock Conversions 555

17.4Dealing With Deadlocks 556

17.4.1 Deadlock Prevention 558

17.5Specialized Locking Techniques 559

17.5.1 Dynamic Databases and the Phantom Problem 560

17.5.2 Concurrency Control in B+ Trees 561

17.5.3 Multiple-Granularity Locking 564

17.6Concurrency Control without Locking 566

17.6.1 Optimistic Concurrency Control 566

17.6.2 Timestamp-Based Concurrency Control 569

17.6.3 Multiversion Concurrency Control 572

17.7Review Questions 573

18 CRASH RECOVERY 579

18.1Introduction to ARIES 580

18.2The Log 582

18.3Other Recovery-Related Structures 585

18.4The Write-Ahead Log Protocol 586

18.5Checkpointing 587

18.6Recovering from a System Crash 587

18.6.1 Analysis Phase 588

18.6.2 Redo Phase 590

18.6.3 Undo Phase 592

18.7Media Recovery 595

18.8Other Approaches and Interaction with Concurrency Control 596

18.9Review Questions 597

Part Ⅵ DATABASE DESIGN AND TUNING 603

19 SCHEMA REFINEMENT AND NORMAL FORMS 605

19.1Introduction to Schema Refinement 606

19.1.1 Problems Caused by Redundancy 606

19.1.2 Decompositions 608

19.1.3 Problems Related to Decomposition 609

19.2Functional Dependencies 611

19.3Reasoning about FDs 612

19.3.1 Closure of a Set of FDs 612

19.3.2 Attribute Closure 614

19.4Normal Forms 615

19.4.1 Boyce-Codd Normal Form 615

19.4.2 Third Normal Form 617

19.5Properties of Decompositions 619

19.5.1 Lossless-Join Decomposition 619

19.5.2 Dependency-Preserving Decomposition 621

19.6Normalization 622

19.6.1 Decomposition into BCNF 622

19.6.2 Decomposition into 3NF 625

19.7Schema Refinement in Database Design 629

19.7.1 Constraints on an Entity Set 630

19.7.2 Constraints on a Relationship Set 630

19.7.3 Identifying Attributes of Entities 631

19.7.4 Identifying Entity Sets 633

19.8Other Kinds of Dependencies 633

19.8.1 Multivalued Dependencies 634

19.8.2 Fourth Normal Form 636

19.8.3 Join Dependencies 638

19.8.4 Fifth Normal Form 638

19.8.5 Inclusion Dependencies 639

19.9 Case Study：The Internet Shop 640

19.10 Review Questions 642

20 PHYSICAL DATABASE DESIGN AND TUNING 649

20.1 Introduction to Physical Database Design 650

20.1.1 Database Workloads 651

20.1.2 Physical Design and Tuning Decisions 652

20.1.3 Need for Database Muning 653

20.2 Guidelines for Index Selection 653

20.3 Basic Examples of Index Selection 656

20.4 Clustering and Indexing 658

20.4.1 Co-clustering Two Relations 660

20.5 Indexes that Enable Index-Only Plans 662

20.6 Tools to Assist in Index Selection 663

20.6.1 Automatic Index Selection 663

20.6.2 How Do Index Muning Wizards Work? 664

20.7 Overview of Database Tuning 667

20.7.1 Tuning Indexes 667

20.7.2 Tuning the Conceptual Schema 669

20.7.3 Tuning Queries and Views 670

20.8 Choices in Tuning the Conceptual Schema 671

20.8.1 Settling for a Weaker Normal Form 671

20.8.2 Denormalization 672

20.8.3 Choice of Decomposition 672

20.8.4 Vertical Partitioning of BCNF Relations 674

20.8.5 Horizontal Decomposition 674

20.9 Choices in Muning Queries and Views 675

20.10 Impact of Concurrency 678

20.10.1 Reducing Lock Durations 678

20.10.2 Reducing Hot Spots 679

20.11 Case Study：The Internet Shop 680

20.11.1 Mining the Database 682

20.12 DBMS Benchmarking 682

20.12.1 Well-Known DBMS Benchmarks 683

20.12.2 Using a Benchmark 684

20.13 Review Questions 685

21 SECURITY AND AUTHORIZATION 692

21.1 Introduction to Database Security 693

21.2 Access Control 694

21.3 Discretionary Access Control 695

21.3.1 Grant and Revoke on Views and Integrity Constraints 704

21.4Mandatory Access Control 705

21.4.1 Multilevel Relations and Polyinstantiation 707

21.4.2 Covert Channels， DoD Security Levels 708

21.5Security for Internet Applications 709

21.5.1 Encryption 709

21.5.2 Certifying Servers：The SSL Protocol 712

21.5.3 Digital Signatures 713

21.6Additional Issues Related to Security 714

21.6.1 Role of the Database Administrator 714

21.6.2 Security in Statistical Databases 715

21.7Design Case Study：The Internet Store 716

21.8Review Questions 718

Part Ⅶ ADDITIONAL TOPICS 723

22 PARALLEL AND DISTRIBUTED DATABASES 725

22.1Introduction 726

22.2Architectures for Parallel Databases 727

22.3Parallel Query Evaluation 728

22.3.1 Data Partitioning 730

22.3.2 Parallelizing Sequential Operator Evaluation Code 730

22.4Parallelizing Individual Operations 731

22.4.1 Bulk Loading and Scanning 731

22.4.2 Sorting 732

22.4.3 Joins 732

22.5Parallel Query Optimization 735

22.6Introduction to Distributed Databases 736

22.6.1 Types of Distributed Databases 737

22.7Distributed DBMS Architectures 737

22.7.1 Client-Server Systems 738

22.7.2 Collaborating Server Systems 738

22.7.3 Middleware Systems 739

22.8Storing Data in a Distributed DBMS 739

22.8.1 Fragmentation 739

22.8.2 Replication 741

22.9Distributed Catalog Management 741

22.9.1 Naming Objects 741

22.9.2 Catalog Structure 742

22.9.3 Distributed Data Independence 743

22.10 Distributed Query Processing 743

22.10.1 Nonjoin Queries in a Distributed DBMS 744

22.10.2 Joins in a Distributed DBMS 745

22.10.3 Cost-Based Query Optimization 749

22.11 Updating Distributed Data 750

22.11.1 Synchronous Replication 750

22.11.2 Asynchronous Replication 751

22.12 Distributed Transactions 755

22.13 Distributed Concurrency Control 755

22.13.1 Distributed Deadlock 756

22.14 Distributed Recovery 758

22.14.1 Normal Execution and Commit Protocols 758

22.14.2 Restart after a Failure 760

22.14.3 Two-Phase Commit Revisited 761

22.14.4 Three-Phase Commit 762

22.15 Review Questions 763

23 OBJECT-DATABASE SYSTEMS 772

23.1Motivating Example 774

23.1.1 New Data Types 775

23.1.2 Manipulating the New Data 777

23.2Structured Data Types 779

23.2.1 Collection Types 780

23.3Operations on Structured Data 781

23.3.1 Operations on Rows 781

23.3.2 Operations on Arrays 781

23.3.3 Operations on Other Collection Types 782

23.3.4 Queries Over Nested Collections 783

23.4Encapsulation and ADTs 784

23.4.1 Defining Methods 785

23.5Inheritance 787

23.5.1 Defining Types with Inheritance 787

23.5.2 Binding Methods 788

23.5.3 Collection Hierarchies 789

23.6Objects，OIDs，and Reference Types 789

23.6.1 Notions of Equality 790

23.6.2 Dereferencing Reference Types 791

23.6.3 URLs and OIDs in SQL：1999 791

23.7Database Design for an ORDBMS 792

23.7.1 Collection Types and ADTs 792

23.7.2 Object Identity 795

23.7.3 Extending the ER Model 796

23.7.4 Using Nested Collections 798

23.8ORDBMS Implementation Challenges 799

23.8.1 Storage and Access Methods 799

23.8.2 Query Processing 801

23.8.3 Query Optimization 803

23.9 OODBMS 805

23.9.1 The ODMG Data Model and ODL 805

23.9.2 OQL 807

23.10 Comparing RDBMS，OODBMS，and ORDBMS 809

23.10.1 RDBMS versus ORDBMS 809

23.10.2 OODBMS versus ORDBMS：Similarities 809

23.10.3 OODBMS versus ORDBMS：Differences 810

23.11 Review Questions 811

24 DEDUCTIVE DATABASES 817

24.1 Introduction to Recursive Queries 818

24.1.1 Datalog 819

24.2 Theoretical Foundations 822

24.2.1 Least Model Semantics 823

24.2.2 The Fixpoint Operator 824

24.2.3 Safe Datalog Programs 825

24.2.4 Least Model=Least Fixpoint 826

24.3 Recursive Queries with Negation 827

24.3.1 Stratification 828

24.4 From Datalog to SQL 831

24.5 Evaluating Recursive Queries 834

24.5.1 Fixpoint Evaluation without Repeated Inferences 835

24.5.2 Pushing Selections to Avoid Irrelevant Inferences 837

24.5.3 The Magic Sets Algorithm 838

24.6 Review Questions 841

25 DATA WAREHOUSING AND DECISION SUPPORT 846

25.1Introduction to Decision Support 848

25.2OLAP： Multidimensional Data Model 849

25.2.1 Multidimensional Database Design 853

25.3Multidimensional Aggregation Queries 854

25.3.1 ROLLUP and CUBE in SQL：1999 856

25.4Window Queries in SQL：1999 859

25.4.1 Framing a Window 861

25.4.2 New Aggregate Functions 862

25.5Finding Answers Quickly 862

25.5.1 Top N Queries 863

25.5.2 Online Aggregation 864

25.6Implementation Techniques for OLAP 865

25.6.1 Bitmap Indexes 866

25.6.2 Join Indexes 868

25.6.3 File Organizations 869

25.7 Data Warehousing 870

25.7.1 Creating and Maintaining a Warehouse 871

25.8 Views and Decision Support 872

25.8.1 Views， OLAP， and Warehousing 872

25.8.2 Queries over Views 873

25.9 View Materialization 873

25.9.1 Issues in View Materialization 874

25.10 Maintaining Materialized Views 876

25.10.1 Incremental View Maintenance 876

25.10.2 Maintaining Warehouse Views 879

25.10.3 When Should We Synchronize Views? 881

25.11 Review Questions 882

26 DATA MINING 889

26.1 Introduction to Data Mining 890

26.1.1 The Knowledge Discovery Process 891

26.2 Counting Co-occurrences 892

26.2.1 Frequent Itemsets 892

26.2.2 Iceberg Queries 895

26.3 Mining for Rules 897

26.3.1 Association Rules 897

26.3.2 An Algorithm for Finding Association Rules 898

26.3.3 Association Rules and ISA Hierarchies 899

26.3.4 Generalized Association Rules 900

26.3.5 Sequential Patterns 901

26.3.6 The Use of Association Rules for Prediction 902

26.3.7 Bayesian Networks 903

26.3.8 Classification and Regression Rules 904

26.4 Tree-Structured Rules 906

26.4.1 Decision Trees 907

26.4.2 An Algorithm to Build Decision Trees 908

26.5 Clustering 911

26.5.1 A Clustering Algorithm 912

26.6 Similarity Search over Sequences 913

26.6.1 An Algorithm to Find Similar Sequences 915

26.7 Incremental Mining and Data Streams 916

26.7.1 Incremental Maintenance of Frequent Itemsets 918

26.8 Additional Data Mining Tasks 920

26.9 Review Questions 920

27 INFORMATION RETRIEVAL AND XML DATA 926

27.1 Colliding Worlds：Databases，IR，and XML 927

27.1.1 DBMS versus IR Systems 928

27.2 Introduction to Information Retrieval 929

27.2.1 Vector Space Model 930

27.2.2 TF/IDF Weighting of Terms 931

27.2.3 Ranking Document Similarity 932

27.2.4 Measuring Success： Precision and Recall 934

27.3 Indexing for Text Search 934

27.3.1 Inverted Indexes 935

27.3.2 Signature Files 937

27.4 Web Search Engines 939

27.4.1 Search Engine Architecture 939

27.4.2 Using Link Information 940

27.5 Managing Text in a DBMS 944

27.5.1 Loosely Coupled Inverted Index 945

27.6 A Data Model for XML 945

27.6.1 Motivation for Loose Structure 945

27.6.2 A Graph Model 946

27.7 XQuery：Querying XML Data 948

27.7.1 Path Expressions 948

27.7.2 FLWR Expressions 949

27.7.3 Ordering of Elements 951

27.7.4 Grouping and Generation of Collection Values 951

27.8 Efficient Evaluation of XML Queries 952

27.8.1 Storing XML in RDBMS 952

27.8.2 Indexing XML Repositories 956

27.9 Review Questions 959

28 SPATIAL DATA MANAGEMENT 968

28.1Types of Spatial Data and Queries 969

28.2 Applications Involving Spatial Data 971

28.3 Introduction to Spatial indexes 973

28.3.1 Overview of Proposed Index Structures 974

28.4 Indexing Based on Space-Filling Curves 975

28.4.1 Region Quad Trees and Z-Ordering：Region Data 976

28.4.2 Spatial Queries Using Z-Ordering 978

28.5 Grid Files 978

28.5.1 Adapting Grid Files to Handle Regions 981

28.6 R Trees：Point and Region Data 982

28.6.1 Queries 983

28.6.2 Insert and Delete Operations 984

28.6.3 Concurrency Control 986

28.6.4 Generalized Search Trees 987

28.7 Issues in High-Dimensional Indexing 988

28.8 Review Questions 988

29 FURTHER READING 992

29.1Advanced Transaction Processing 993

29.1.1 Transaction Processing Monitors 993

29.1.2New Transaction Models 994

29.1.3 Real-Time DBMSs 994

29.2Data Integration 995

29.3Mobile Databases 995

29.4Main Memory Databases 996

29.5Multimedia Databases 997

29.6Geographic Information Systems 998

29.7Temporal Databases 999

29.8Biological Databases 999

29.9Information Visualization 1000

29.10 Summary 1000

30 THE MINIBASE SOFTWARE 1002

30.1What Is Available 1002

30.2Overview of Minibase Assignments 1003

30.3Acknowledgments 1004

REFERENCES 1005

SUBJECT INDEX 1045