WIXLIB

xviDatabase Management Systems19.119.219.319.419.519.6Lock-Based Concurrency Control Revisited19.1.1 2PL, Serializability, and Recoverability19.1.2 View SerializabilityLock Management19.2.1 Implementing Lock and Unlock Requests19.2.2 Deadlocks19.2.3 Performance of Lock-Based Concurrency ControlSpecialized Locking Techniques19.3.1 Dynamic Databases and the Phantom Problem19.3.2 Concurrency Control in B Trees19.3.3 Multiple-Granularity LockingTransaction Support in SQL-92 *19.4.1 Transaction Characteristics19.4.2 Transactions and ConstraintsConcurrency Control without Locking19.5.1 Optimistic Concurrency Control19.5.2 Timestamp-Based Concurrency Control19.5.3 Multiversion Concurrency ControlPoints to Review20 CRASH RECOVERY20.120.220.320.420.5Part VIIIntroduction to ARIES20.1.1 The Log20.1.2 Other Recovery-Related Data Structures20.1.3 The Write-Ahead Log Protocol20.1.4 CheckpointingRecovering from a System Crash20.2.1 Analysis Phase20.2.2 Redo Phase20.2.3 Undo PhaseMedia RecoveryOther Algorithms and Interaction with Concurrency ControlPoints to ReviewADVANCED TOPICS21 PARALLEL AND DISTRIBUTED DATABASES21.121.221.3Architectures for Parallel DatabasesParallel Query Evaluation21.2.1 Data Partitioning21.2.2 Parallelizing Sequential Operator Evaluation CodeParallelizing Individual Operations21.3.1 Bulk Loading and 7588595597598600601601602602

221.1321.1421.3.2 Sorting21.3.3 JoinsParallel Query OptimizationIntroduction to Distributed Databases21.5.1 Types of Distributed DatabasesDistributed DBMS Architectures21.6.1 Client-Server Systems21.6.2 Collaborating Server Systems21.6.3 Middleware SystemsStoring Data in a Distributed DBMS21.7.1 Fragmentation21.7.2 ReplicationDistributed Catalog Management21.8.1 Naming Objects21.8.2 Catalog Structure21.8.3 Distributed Data IndependenceDistributed Query Processing21.9.1 Nonjoin Queries in a Distributed DBMS21.9.2 Joins in a Distributed DBMS21.9.3 Cost-Based Query OptimizationUpdating Distributed Data21.10.1 Synchronous Replication21.10.2 Asynchronous ReplicationIntroduction to Distributed TransactionsDistributed Concurrency Control21.12.1 Distributed DeadlockDistributed Recovery21.13.1 Normal Execution and Commit Protocols21.13.2 Restart after a Failure21.13.3 Two-Phase Commit Revisited21.13.4 Three-Phase CommitPoints to Review22 INTERNET DATABASES22.122.222.3The World Wide Web22.1.1 Introduction to HTML22.1.2 Databases and the WebArchitecture22.2.1 Application Servers and Server-Side JavaBeyond HTML22.3.1 Introduction to XML22.3.2 XML DTDs22.3.3 Domain-Specific DTDs22.3.4 XML-QL: Querying XML 642643643645645647651652654657659

xviiiDatabase Management Systems22.422.522.622.3.5 The Semistructured Data Model22.3.6 Implementation Issues for Semistructured DataIndexing for Text Search22.4.1 Inverted Files22.4.2 Signature FilesRanked Keyword Searches on the Web22.5.1 An Algorithm for Ranking Web PagesPoints to Review23 DECISION SUPPORT23.123.223.323.423.523.623.7Introduction to Decision SupportData Warehousing23.2.1 Creating and Maintaining a WarehouseOLAP23.3.1 Multidimensional Data Model23.3.2 OLAP Queries23.3.3 Database Design for OLAPImplementation Techniques for OLAP23.4.1 Bitmap Indexes23.4.2 Join Indexes23.4.3 File Organizations23.4.4 Additional OLAP Implementation IssuesViews and Decision Support23.5.1 Views, OLAP, and Warehousing23.5.2 Query Modification23.5.3 View Materialization versus Computing on Demand23.5.4 Issues in View MaterializationFinding Answers Quickly23.6.1 Top N Queries23.6.2 Online AggregationPoints to Review24 DATA MINING24.124.224.3Introduction to Data MiningCounting Co-occurrences24.2.1 Frequent Itemsets24.2.2 Iceberg QueriesMining for Rules24.3.1 Association Rules24.3.2 An Algorithm for Finding Association Rules24.3.3 Association Rules and ISA Hierarchies24.3.4 Generalized Association Rules24.3.5 Sequential 7707708709711713714714715716717

xixContents24.424.524.624.724.824.3.6 The Use of Association Rules for Prediction24.3.7 Bayesian Networks24.3.8 Classification and Regression RulesTree-Structured Rules24.4.1 Decision Trees24.4.2 An Algorithm to Build Decision TreesClustering24.5.1 A Clustering AlgorithmSimilarity Search over Sequences24.6.1 An Algorithm to Find Similar SequencesAdditional Data Mining TasksPoints to Review25 OBJECT-DATABASE ing Example25.1.1 New Data Types25.1.2 Manipulating the New Kinds of DataUser-Defined Abstract Data Types25.2.1 Defining Methods of an ADTStructured Types25.3.1 Manipulating Data of Structured TypesObjects, Object Identity, and Reference Types25.4.1 Notions of Equality25.4.2 Dereferencing Reference TypesInheritance25.5.1 Defining Types with Inheritance25.5.2 Binding of Methods25.5.3 Collection Hierarchies, Type Extents, and QueriesDatabase Design for an ORDBMS25.6.1 Structured Types and ADTs25.6.2 Object Identity25.6.3 Extending the ER Model25.6.4 Using Nested CollectionsNew Challenges in Implementing an ORDBMS25.7.1 Storage and Access Methods25.7.2 Query Processing25.7.3 Query OptimizationOODBMS25.8.1 The ODMG Data Model and ODL25.8.2 OQLComparing RDBMS with OODBMS and ORDBMS25.9.1 RDBMS versus ORDBMS25.9.2 OODBMS versus ORDBMS: Similarities25.9.3 OODBMS versus ORDBMS: 6757758759760761763765765768769769770770

xxDatabase Management Systems25.10 Points to Review26 SPATIAL DATA MANAGEMENT26.126.226.326.426.526.626.726.8Types of Spatial Data and QueriesApplications Involving Spatial DataIntroduction to Spatial Indexes26.3.1 Overview of Proposed Index StructuresIndexing Based on Space-Filling Curves26.4.1 Region Quad Trees and Z-Ordering: Region Data26.4.2 Spatial Queries Using Z-OrderingGrid Files26.5.1 Adapting Grid Files to Handle RegionsR Trees: Point and Region Data26.6.1 Queries26.6.2 Insert and Delete Operations26.6.3 Concurrency Control26.6.4 Generalized Search TreesIssues in High-Dimensional IndexingPoints to Review27 DEDUCTIVE DATABASES27.127.227.327.427.5Introduction to Recursive Queries27.1.1 DatalogTheoretical Foundations27.2.1 Least Model Semantics27.2.2 Safe Datalog Programs27.2.3 The Fixpoint Operator27.2.4 Least Model Least FixpointRecursive Queries with Negation27.3.1 Range-Restriction and Negation27.3.2 Stratification27.3.3 Aggregate OperationsEfficient Evaluation of Recursive Queries27.4.1 Fixpoint Evaluation without Repeated Inferences27.4.2 Pushing Selections to Avoid Irrelevant InferencesPoints to Review28 ADDITIONAL TOPICS28.128.2Advanced Transaction Processing28.1.1 Transaction Processing Monitors28.1.2 New Transaction Models28.1.3 Real-Time DBMSsIntegrated Access to Multiple Data 814816818822822822823824824

27828829829DATABASE DESIGN CASE STUDY: THE INTERNET831SHOPA.1A.2A.3A.4A.5A.6A.7BMobile DatabasesMain Memory DatabasesMultimedia DatabasesGeographic Information SystemsTemporal and Sequence DatabasesInformation VisualizationSummaryRequirements AnalysisConceptual DesignLogical Database DesignSchema RefinementPhysical Database DesignA.5.1 Tuning the DatabaseSecurityApplication Layers831832832835836838838840THE MINIBASE SOFTWARE842B.1B.2842843843844845B.3What’s AvailableOverview of Minibase AssignmentsB.2.1 Overview of Programming ProjectsB.2.2 Overview of Nonprogramming AssignmentsAcknowledgmentsREFERENCES847SUBJECT INDEX879AUTHOR INDEX896

PREFACEThe advantage of doing one’s praising for oneself is that one can lay it on so thickand exactly in the right places.—Samuel ButlerDatabase management systems have become ubiquitous as a fundamental tool for managing information, and a course on the principles and practice of database systems isnow an integral part of computer science curricula. This book covers the fundamentalsof modern database management systems, in particular relational database systems.It is intended as a text for an introductory database course for undergraduates, andwe have attempted to present the material in a clear, simple style.A quantitative approach is used throughout and detailed examples abound. An extensive set of exercises (for which solutions are available online to instructors) accompanieseach chapter and reinforces students’ ability to apply the concepts to real problems.The book contains enough material to support a second course, ideally supplementedby selected research papers. It can be used, with the accompanying software and SQLprogramming assignments, in two distinct kinds of introductory courses:1. A course that aims to present the principles of database systems, with a practicalfocus but without any implementation assignments. The SQL programming assignments are a useful supplement for such a course. The supplementary Minibasesoftware can be used to create exercises and experiments with no programming.2. A course that has a strong systems emphasis and assumes that students havegood programming skills in C and C . In this case the software can be usedas the basis for projects in which students are asked to implement various partsof a relational DBMS. Several central modules in the project software (e.g., heapfiles, buffer manager, B trees, hash indexes, various join methods, concurrencycontrol, and recovery algorithms) are described in sufficient detail in the text toenable students to implement them, given the (C ) class interfaces.Many instructors will no doubt teach a course that falls between these two extremes.xxii

PrefacexxiiiChoice of TopicsThe choice of material has been influenced by these considerations:To concentrate on issues central to the design, tuning, and implementation of relational database applications. However, many of the issues discussed (e.g., bufferingand access methods) are not specific to relational systems, and additional topicssuch as decision support and object-database systems are covered in later chapters.To provide adequate coverage of implementation topics to support a concurrentlaboratory section or course project. For example, implementation of relationaloperations has been covered in more detail than is necessary in a first course.However, the variety of alternative implementation techniques permits a widechoice of project assignments. An instructor who wishes to assign implementationof sort-merge join might cover that topic in depth, whereas another might chooseto emphasize index nested loops join.To provide in-depth coverage of the state of the art in currently available commercial systems, rather than a broad coverage of several alternatives. For example,we discuss the relational data model, B trees, SQL, System R style query optimization, lock-based concurrency control, the ARIES recovery algorithm, thetwo-phase commit protocol, asynchronous replication in distributed databases,and object-relational DBMSs in detail, with numerous illustrative examples. Thisis made possible by omitting or briefly covering some related topics such as thehierarchical and network models, B tree variants, Quel, semantic query optimization, view serializability, the shadow-page recovery algorithm, and the three-phasecommit protocol.The same preference for in-depth coverage of selected topics governed our choiceof topics for chapters on advanced material. Instead of covering a broad range oftopics briefly, we have chosen topics that we believe to be practically importantand at the cutting edge of current thinking in database systems, and we havecovered them in depth.New in the Second EditionBased on extensive user surveys and feedback, we have refined the book’s organization.The major change is the early introduction of the ER model, together with a discussionof conceptual database design. As in the first edition, we introduce SQL-92’s datadefinition features together with the relational model (in Chapter 3), and wheneverappropriate, relational model concepts (e.g., definition of a relation, updates, views, ERto relational mapping) are illustrated and discussed in the context of SQL. Of course,we maintain a careful separation between the concepts and their SQL realization. Thematerial on data storage, file organization, and indexes has been moved back, and the

xxivDatabase Management Systemsmaterial on relational queries has been moved forward. Nonetheless, the two parts(storage and organization vs. queries) can still be taught in either order based on theinstructor’s preferences.In order to facilitate brief coverage in a first course, the second edition contains overviewchapters on transaction processing and query optimization. Most chapters have beenrevised extensively, and additional explanations and figures have been added in manyplaces. For example, the chapters on query languages now contain a uniform numberingof all queries to facilitate comparisons of the same query (in algebra, calculus, andSQL), and the results of several queries are shown in figures. JDBC and ODBCcoverage has been added to the SQL query chapter and SQL:1999 features are discussedboth in this chapter and the chapter on object-relational databases. A discussion ofRAID has been added to Chapter 7. We have added a new database design case study,illustrating the entire design cycle, as an appendix.Two new pedagogical features have been introduced. First, ‘floating boxes’ provide additional perspective and relate the concepts to real systems, while keeping the main discussion free of product-specific details. Second, each chapter concludes with a ‘Pointsto Review’ section that summarizes the main ideas introduced in the chapter andincludes pointers to the sections where they are discussed.For use in a second course, many advanced chapters from the first edition have beenextended or split into multiple chapters to provide thorough coverage of current topics. In particular, new material has been added to the chapters on decision support,deductive databases, and object databases. New chapters on Internet databases, datamining, and spatial databases have been added, greatly expanding the coverage ofthese topics.The material can be divided into roughly seven parts, as indicated in Figure 0.1, whichalso shows the dependencies between chapters. An arrow from Chapter I to Chapter Jmeans that I depends on material in J. The broken arrows indicate a weak dependency,which can be ignored at the instructor’s discretion. It is recommended that Part I becovered first, followed by Part II and Part III (in either order). Other than these threeparts, dependencies across parts are minimal.Order of PresentationThe book’s modular organization offers instructors a variety of choices. For example, some instructors will want to cover SQL and get students to use a relationaldatabase, before discussing file organizations or indexing; they should cover Part IIbefore Part III. In fact, in a course that emphasizes concepts and SQL, many of theimplementation-oriented chapters might be skipped. On the other hand, instructorsassigning implementation projects based on file organizations may want to cover Part

xxvPreface417Relational Algebraand CalculusIntroduction,Data Storage265QBESQL Queries, etc.IVVVIVII8ER ModelConceptual DesignIntroduction toFile Organizations3III12External SortingEvaluation ofRelational OperatorsPhysical DBDesign, TuningConcurrencyControlTransaction Figure 0.110Hash Indexes14Parallel andDistributed DBs2220CrashRecovery26SpatialDatabasesA TypicalRelational Introduction toQuery Optimization1615Schema Refinement,FDs, NormalizationTree IndexesIIIRelational ModelSQL ionalTopicsChapter Organization and DependenciesIII early to space assignments. As another example, it is not necessary to cover all thealternatives for a given operator (e.g., various techniques for joins) in Chapter 12 inorder to cover later related material (e.g., on optimization or tuning) adequately. Thedatabase design case study in the appendix can be discussed concurrently with theappropriate design chapters, or it can be discussed after all design topics have beencovered, as a review.Several section headings contain an asterisk. This symbol does not necessarily indicatea higher level of difficulty. Rather, omitting all asterisked sections leaves about theright amount of material in Chapters 1–18, possibly omitting Chapters 6, 10, and 14,for a broad introductory one-quarter or one-semester course (depending on the depthat which the remaining material is discussed and the nature of the course assignments).

xxviDatabase Management SystemsThe book can be used in several kinds of introductory or second courses by choosingtopics appropriately, or in a two-course sequence by supplementing the material withsome advanced readings in the second course. Examples of appropriate introductorycourses include courses on file organizations and introduction to database managementsystems, especially if the course focuses on relational database design or implementation. Advanced courses can be built around the later chapters, which contain detailedbibliographies with ample pointers for further study.Supplementary MaterialEach chapter contains several exercises designed to test and expand the reader’s understanding of the material. Students can obtain solutions to odd-numbered chapterexercises and a set of lecture slides for each chapter through the Web in Postscript andAdobe PDF formats.The following material is available online to instr

x Database Management Systems 5.13.2 Constraints versus Triggers 167 5.13.3 Other Uses of Triggers 168 5.14 Points to Review 168 6 QUERY-BY-EXAMPLE (QBE) 177 6.1 Introduction 177 6.2 Basic QBE Queries 178 6.2.1 Other Features: Duplicates, Ordering Answers 179 6.3 Queries over Multiple R