Database System Concepts. 7 Ed

Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

 Title Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2

 Copyright Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

 Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

 About the Authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6

 Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8

 Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16

 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

 Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30

    1.1 Database-System Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30

    1.2 Purpose of Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34

    1.3 View of Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

    1.4 Database Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42

    1.5 Database Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46

    1.6 Database Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47

    1.7 Database and Application Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50

    1.8 Database Users and Administrators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53

    1.9 History of Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54

    1.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58

    Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60

    Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62

 PART ONE RELATIONAL LANGUAGES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64

    Chapter 2 Introduction to the Relational Model . . . . . . . . . . . . . . . . . . . . . . . . . . .66

        2.1 Structure of Relational Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66

        2.2 Database Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70

        2.3 Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72

        2.4 Schema Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75

        2.5 Relational Query Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .76

        2.6 The Relational Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77

        2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92

    Chapter 3 Introduction to SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94

        3.1 Overview of the SQL Query Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94

        3.2 SQL Data Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95

        3.3 Basic Structure of SQL Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100

        3.4 Additional Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108

        3.5 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .114

        3.6 Null Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118

        3.7 Aggregate Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .120

        3.8 Nested Subqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .127

        3.9 Modification of the Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .137

        3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153

    Chapter 4 Intermediate SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154

        4.1 Join Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154

        4.2 Views . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .166

        4.3 Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172

        4.4 Integrity Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .174

        4.5 SQL Data Types and Schemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182

        4.6 Index Definition in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193

        4.7 Authorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .194

        4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209

    Chapter 5 Advanced SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212

        5.1 Accessing SQL from a Programming Language . . . . . . . . . . . . . . . . . . . . .212

        5.2 Functions and Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .227

        5.3 Triggers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .235

        5.4 Recursive Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242

        5.5 Advanced Aggregation Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .248

        5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .260

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .261

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .267

 PART TWO DATABASE DESIGN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .268

    Chapter 6 Database Design Using the E-R Model . . . . . . . . . . . . . . . . . . . . . . . . . . .270

        6.1 Overview of the Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .270

        6.2 The Entity-Relationship Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .273

        6.3 Complex Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .278

        6.4 Mapping Cardinalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .281

        6.5 Primary Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .285

        6.6 Removing Redundant Attributes in Entity Sets . . . . . . . . . . . . . . . . . .290

        6.7 Reducing E-R Diagrams to Relational Schemas . . . . . . . . . . . . . . . . . . .293

        6.8 Extended E-R Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300

        6.9 Entity-Relationship Design Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . .308

        6.10 Alternative Notations for Modeling Data . . . . . . . . . . . . . . . . . . . . . .314

        6.11 Other Aspects of Database Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . .320

        6.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .321

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .329

    Chapter 7 Relational Database Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .332

        7.1 Features of Good Relational Designs . . . . . . . . . . . . . . . . . . . . . . . . . . .332

        7.2 Decomposition Using Functional Dependencies . . . . . . . . . . . . . . . . . . .337

        7.3 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .342

        7.4 Functional-Dependency Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .349

        7.5 Algorithms for Decomposition Using Functional Dependencies . . . .359

        7.6 Decomposition Using Multivalued Dependencies . . . . . . . . . . . . . . . . . .365

        7.7 More Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .370

        7.8 Atomic Domains and First Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . .371

        7.9 Database-Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372

        7.10 Modeling Temporal Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .376

        7.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .380

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .382

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .389

 PART THREE APPLICATION DESIGN AND DEVELOPMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .392

    Chapter 8 Complex Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .394

        8.1 Semi-structured Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .394

        8.2 Object Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .405

        8.3 Textual Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .411

        8.4 Spatial Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .416

        8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .423

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .426

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .430

    Chapter 9 Application Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .432

        9.1 Application Programs and User Interfaces . . . . . . . . . . . . . . . . . . . . . .432

        9.2 Web Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .434

        9.3 Servlets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .440

        9.4 Alternative Server-Side Frameworks . . . . . . . . . . . . . . . . . . . . . . . . . . . .445

        9.5 Client-Side Code and Web Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . .450

        9.6 Application Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .458

        9.7 Application Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .463

        9.8 Application Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .466

        9.9 Encryption and Its Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .476

        9.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .482

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .484

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .491

 PART FOUR BIG DATA ANALYTICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .494

    Chapter 10 Big Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .496

        10.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .496

        10.2 Big Data Storage Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .501

        10.3 The MapReduce Paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .512

        10.4 Beyond MapReduce: Algebraic Operations . . . . . . . . . . . . . . . . . . . . . . .523

        10.5 Streaming Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .529

        10.6 Graph Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .537

        10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .540

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .542

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .545

    Chapter 11 Data Analytics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .548

        11.1 Overview of Analytics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .548

        11.2 Data Warehousing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .550

        11.3 Online Analytical Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .556

        11.4 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .569

        11.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .579

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .581

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .584

 PART FIVE STORAGE MANAGEMENT AND INDEXING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .586

    Chapter 12 Physical Storage Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .588

        12.1 Overview of Physical Storage Media . . . . . . . . . . . . . . . . . . . . . . . . . . .588

        12.2 Storage Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .591

        12.3 Magnetic Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .592

        12.4 Flash Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .596

        12.5 RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .599

        12.6 Disk-Block Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .606

        12.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .609

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .611

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .613

    Chapter 13 Data Storage Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .616

        13.1 Database Storage Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .616

        13.2 File Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .617

        13.3 Organization of Records in Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . .624

        13.4 Data-Dictionary Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .631

        13.5 Database Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .633

        13.6 Column-Oriented Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .640

        13.7 Storage Organization in Main-Memory Databases . . . . . . . . . . . . . . . .644

        13.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .646

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .648

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .650

    Chapter 14 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .652

        14.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .652

        14.2 Ordered Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .654

        14.3 B+-Tree Index Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .663

        14.4 B+-Tree Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .679

        14.5 Hash Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .687

        14.6 Multiple-Key Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .690

        14.7 Creation of Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .693

        14.8 Write-Optimized Index Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . .694

        14.9 Bitmap Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .699

        14.10 Indexing of Spatial and Temporal Data . . . . . . . . . . . . . . . . . . . . . . .701

        14.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .706

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .708

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .712

 PART SIX QUERY PROCESSING AND OPTIMIZATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .716

    Chapter 15 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .718

        15.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .718

        15.2 Measures of Query Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .721

        15.3 Selection Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724

        15.4 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .730

        15.5 Join Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .733

        15.6 Other Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .748

        15.7 Evaluation of Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .753

        15.8 Query Processing in Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .760

        15.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .763

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .765

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .769

    Chapter 16 Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .772

        16.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .772

        16.2 Transformation of Relational Expressions . . . . . . . . . . . . . . . . . . . . .776

        16.3 Estimating Statistics of Expression Results . . . . . . . . . . . . . . . . . .786

        16.4 Choice of Evaluation Plans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .795

        16.5 Materialized Views . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .807

        16.6 Advanced Topics in Query Optimization . . . . . . . . . . . . . . . . . . . . . . . .812

        16.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .816

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .818

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .823

 PART SEVEN TRANSACTION MANAGEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .826

    Chapter 17 Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .828

        17.1 Transaction Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .828

        17.2 A Simple TransactionModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .830

        17.3 Storage Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .833

        17.4 Transaction Atomicity and Durability . . . . . . . . . . . . . . . . . . . . . . . . .834

        17.5 Transaction Isolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .836

        17.6 Serializability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .841

        17.7 Transaction Isolation and Atomicity . . . . . . . . . . . . . . . . . . . . . . . . . .848

        17.8 Transaction Isolation Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .850

        17.9 Implementation of Isolation Levels . . . . . . . . . . . . . . . . . . . . . . . . . . .852

        17.10 Transactions as SQL Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .855

        17.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .857

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .860

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .863

    Chapter 18 Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .864

        18.1 Lock-Based Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .864

        18.2 Deadlock Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .878

        18.3 Multiple Granularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .882

        18.4 Insert Operations, Delete Operations, and Predicate Reads . . . .886

        18.5 Timestamp-Based Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .890

        18.6 Validation-Based Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .895

        18.7 Multiversion Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .898

        18.8 Snapshot Isolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .901

        18.9 Weak Levels of Consistency in Practice . . . . . . . . . . . . . . . . . . . . . . .909

        18.10 Advanced Topics in Concurrency Control . . . . . . . . . . . . . . . . . . . . . .912

        18.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .923

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .928

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .933

    Chapter 19 Recovery System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .936

        19.1 Failure Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .936

        19.2 Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .937

        19.3 Recovery and Atomicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .941

        19.4 Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .951

        19.5 Buffer Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .955

        19.6 Failure with Loss of Non-Volatile Storage . . . . . . . . . . . . . . . . . . . .959

        19.7 High Availability Using Remote Backup Systems . . . . . . . . . . . . . . . .960

        19.8 Early Lock Release and Logical Undo Operations . . . . . . . . . . . . . . .964

        19.9 ARIES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .970

        19.10 Recovery in Main-Memory Databases . . . . . . . . . . . . . . . . . . . . . . . . . . .976

        19.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .977

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .981

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .985

 PART EIGHT PARALLEL AND DISTRIBUTED DATABASES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .988

    Chapter 20 Database-System Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .990

        20.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .990

        20.2 Centralized Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .991

        20.3 Server System Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .992

        20.4 Parallel Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .999

        20.5 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015

        20.6 Transaction Processing in Parallel and Distributed Systems . . .1018

        20.7 Cloud-Based Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1019

        20.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1024

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1027

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1030

    Chapter 21 Parallel and Distributed Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1032

        21.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1032

        21.2 Data Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1033

        21.3 Dealing with Skew in Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . .1036

        21.4 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1042

        21.5 Parallel Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1046

        21.6 Distributed File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1048

        21.7 Parallel Key-Value Stores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1052

        21.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1061

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1062

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1065

    Chapter 22 Parallel and Distributed Query Processing . . . . . . . . . . . . . . . . . . . .1068

        22.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1068

        22.2 Parallel Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1070

        22.3 Parallel Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1072

        22.4 Other Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1077

        22.5 Parallel Evaluation of Query Plans . . . . . . . . . . . . . . . . . . . . . . . . . . .1081

        22.6 Query Processing on Shared-Memory Architectures . . . . . . . . . . . . . .1090

        22.7 Query Optimization for Parallel Execution . . . . . . . . . . . . . . . . . . . .1093

        22.8 Parallel Processing of Streaming Data . . . . . . . . . . . . . . . . . . . . . . . .1099

        22.9 Distributed Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1105

        22.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1115

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1118

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1122

    Chapter 23 Parallel and Distributed Transaction Processing . . . . . . . . . . . . . .1126

        23.1 Distributed Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1127

        23.2 Commit Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1129

        23.3 Concurrency Control in Distributed Databases . . . . . . . . . . . . . . . . .1140

        23.4 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1150

        23.5 Extended Concurrency Control Protocols . . . . . . . . . . . . . . . . . . . . . . .1158

        23.6 Replication with Weak Degrees of Consistency . . . . . . . . . . . . . . . . .1162

        23.7 Coordinator Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1175

        23.8 Consensus in Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1179

        23.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1191

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1194

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1197

 PART NINE ADVANCED TOPICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1202

    Chapter 24 Advanced Indexing Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1204

        24.1 Bloom Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1204

        24.2 Log-Structured Merge Tree and Variants . . . . . . . . . . . . . . . . . . . . . . .1205

        24.3 Bitmap Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1211

        24.4 Indexing of Spatial Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1215

        24.5 Hash Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1219

        24.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1232

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1234

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1235

    Chapter 25 Advanced Application Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1238

        25.1 Performance Tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1239

        25.2 Performance Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1259

        25.3 Other Issues in Application Development . . . . . . . . . . . . . . . . . . . . . .1263

        25.4 Standardization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1266

        25.5 Distributed Directory Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1269

        25.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1272

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1274

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1277

    Chapter 26 Blockchain Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1280

        26.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1281

        26.2 Blockchain Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1283

        26.3 Achieving Blockchain Properties via Cryptographic Hash Functions .1288

        26.4 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1292

        26.5 Data Management in a Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1296

        26.6 Smart Contracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1298

        26.7 Performance Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1303

        26.8 Emerging Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1305

        26.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1308

        Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1309

        Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1311

 PART TEN APPENDIX A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1314

 Appendix A Detailed University Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1316

 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1328

It will not come with online access code. Online Access code (should only be purchased when required by an instructor ) sold separately at other ISBN. The content of of this title on all formats are the same. Database System Concepts by Silberschatz, Korth and Sudarshan is now in its 7th edition and is one of the cornerstone texts of database education. It presents the fundamental concepts of database management in an intuitive manner geared toward allowing students to begin working with databases as quickly as possible. The text is designed for a first course in databases at the junior/senior undergraduate level or the first year graduate level. It also contains additional material that can be used as supplements or as introductory material for an advanced course. Because the authors present concepts as intuitive descriptions, a familiarity with basic data structures, computer organization, and a high-level programming language are the only prerequisites. Important theoretical results are covered, but formal proofs are omitted. In place of proofs, figures and examples are used to suggest why a result is true.