PREFACE
Part I  FOUNDATIONS
1   OVERVIEW OF DATABASE SYSTEMS
 1.1   Managing Data
 1.2   A Historical Perspective
 1.3   File Systems versus a DBMS
 1.4   Advantages of a DBMS
 1.5   Describing and Storing Data in a DBMS
 1.5.1  The Relational Model
 1.5.2   Levels of Abstraction in a DBMS
 1.5.3   Data Independence
 1.6   Queries in a DBMS
 1.7   Transaction Management
 1.7.1  Concurrent Execution of Transactions
 1.7.2   Incomplete Transactions and System Crashes
 1.7.3   Points to Note
 1.8   Structure of a DBMS
 1.9   People Who Work with Databases
 1.10  Review Questions
2      INTRODUCTION TO DATABASE DESIGN
 2.1   Database Design and ER Diagrams
 2.1.1   Beyond ER Design
 2.2   Entities, Attributes, and Entity Sets
 2.3   Relationships and Relationship Sets
 2.4   Additional Features of the ER Model
 2.4.1   Key Constraints
 2.4.2   Participation Constraints
 2.4.3  Weak Entities
 2.4.4   Class Hierarchies
 2.4.5   Aggregation
 2.5  Conceptual Design With the ER Model
 2.5.1  Entity versus Attribute
 2.5.2  Entity versus Relationship
 2.5.3  Binary versus Ternary Relationships
 2.5.4  Aggregation versus Ternary Relationships
 2.6  Conceptual Design for Large Enterprises
 2.7  The Unified Modeling Language
 2.8  Case Study: The Internet Shop
 2.8.1  Requirements Analysis
 2.8.2  Conceptual Design
 2.9  Review Questions
3  THE RELATIONAL MODEL
 3.1  Introduction to the Relational Model
 3.1.1  Creating and Modifying Relations Using SQL
 3.2  Integrity Constraints over Relations
 3.2.1  Key Constraints
 3.2.2  Foreign Key Constraints
 3.2.3  General Constraints
 3.3  Enforcing Integrity Constraints
 3.3.1  Transactions and Constraints
 3.4  Querying Relational Data
 3.5  Logical Database Design: ER to Relational
 3.5.1  Entity Sets to Tables
 3.5.2  Relationship Sets (without Constraints) to Tables
 3.5.3  Translating Relationship Sets with Key Constraints
 3.5.4  Translating Relationship Sets with Participation Constraints
 3.5.5  Translating Weak Entity Sets
 3.5.6  Translating Class Hierarchies
 3.5.7  Translating ER Diagrams with Aggregation
 3.5.8  ER to Relational: Additional Examples
 3.6  Introduction to Views
 3.6.1  Views, Data Independence, Security
 3.6.2  Updates on Views
 3.7  Destroying/Altering Tables and Views
 3.8  Case Study: The Internet Store
 3.9  Review Questions
4      RELATIONAL ALGEBRA AND CALCULUS
 4.1  Preliminaries
 4.2  Relational Algebra
 4.2.1  Selection and Projection
 4.2.2  Set Operations
 4.2.3  Renaming
 4.2.4  Joins
 4.2.5  Division
 4.2.6  More Examples of Algebra Queries
 4.3   Relational Calculus
 4.3.1  Tuple Relational Calculus
 4.3.2  Domain Relational Calculus
 4.4   Expressive Power of Algebra and Calculus
 4.5   Review Questions
5    SQL: QUERIES, CONSTRAINTS, TRIGGERS
 5.1   Overview
 5.1.1  Chapter Organization
 5.2   The Form of a Basic SQL Query
 5.2.1  Examples of Basic SQL Queries
 5.2.2  Expressions and Strings in the SELECT Command
 5.3   UNION, INTERSECT, and EXCEPT
 5.4   Nested Queries
 5.4.1  Introduction to Nested Queries
 5.4.2  Correlated Nested Queries
 5.4.3  Set-Comparison Operators
 5.4.4  More Examples of Nested Queries
 5.5   Aggregate Operators
 5.5.1  The GROUP BY and HAVING Clauses
 5.5.2  More Examples of Aggregate Queries
 5.6   Null Values
 5.6.1  Comparisons Using Null Values
 5.6.2  Logical Connectives AND, OR, and NOT
 5.6.3  Impact on SQL Constructs
 5.6.4  Outer Joins
 5.6.5  Disallowing Null Values
 5.7   Complex Integrity Constraints in SQL
 5.7.1  Constraints over a Single Table
 5.7.2  Domain Constraints and Distinct Types
 5.7.3  Assertions: ICs over Several Tables
 5.8   Triggers and Active Databases
 5.8.1  Examples of Triggers in SQL
 5.9   Designing Active Databases
 5.9.1  Why Triggers Can Be Hard to Understand
 5:9.2  Constraints versus Triggers
 5.9.3  Other Uses of Triggers
 5.10   Review Questions
Part II    APPLICATION DEVELOPMENT
6      DATABASE APPLICATION DEVELOPMENT
 6.1   Accessing Databases from Applications
 6.1.1  Embedded SQL
 6.1.2  Cursors
 6.1.3  Dynamic SQL
 6.2   An Introduction to JDBC
 6.2.1  Architecture
 6.3   JDBC Classes and Interfaces
 6.3.1  JDBC Driver Management
 6.3.2  Connections
 6.3.3  Executing SQL Statements
 6.3.4  ResultSets
 6.3.5  Exceptions and Warnings
 6.3.6  Examining Database Metadata
 6.4  SQLJ
 6.4.1  Writing SQLJ Code
 6.5   Stored Procedures
 6.5.1  Creating a Simple Stored Procedure
 6.5.2  Calling Stored Procedures
 6.5.3  SQL/PSM
 6.6   Case Study: The Internet Book Shop
 6.7   Review Questions
7      INTERNET APPLICATIONS
 7.1   Introduction
 7.2   Internet Concepts
 7.2.1  Uniform Resource Identifiers
 7.2.2  The Hypertext Transfer Protocol (HTTP)
 7.3   HTML Documents
 7.4   XML Documents
 7.4.1  Introduction to XML
 7.4.2  XML DTDs
 7.4.3  Domain-Specific DTDs
 7.5   The Three-Tier Application Architecture
 7.5.1  Single-Tier and Client-Server Architectures
 7.5.2  Three-Tier Architectures
 7.5.3  Advantages of the Three-Tier Architecture
 7.6   The Presentation Layer
 7.6.1  HTML Forms
 7.6.2  JavaScript
 7.6.3  Style Sheets
 7.7   The Middle Tier
 7.7.1  CGI: The Common Gateway Interface
 7.7.2  Application Servers
 7.7.3  Servlets
 7.7.4  JavaServer Pages
 7.7.5  Maintaining State
 7.8   Case Study: The Internet Book Shop
 7.9   Review Questions
Part III  STORAGE AND INDEXING
8      OVERVIEW OF STORAGE AND INDEXING
 8.1   Data on External Storage
 8.2   File Organizations and Indexing
 8.2.1  Clustered Indexes
 8.2.2  Primary and Secondary Indexes
 8.3   Index Data Structures
 8.3.1  Hash-Based Indexing
 8.3.2  Tree-Based Indexing
 8.4   Comparison of File Organizations
 8.4.1  Cost Model
 8.4.2  Heap Files
 8.4.3  Sorted Files
 8.4.4  Clustered Files
 8.4.5  Heap File with Unclustered Tree Index
 8.4.6  Heap File With Unclustered Hash Index
 8.4.7  Comparison of I/O Costs
 8.5   Indexes and Performance Tuning
 8.5.1  Impact of the Workload
 8.5.2  Clustered Index Organization
 8.5.3  Composite Search Keys
 8.5.4  Index Specification in SQL:1999
 8.6   Review Questions
9  STORING DATA: DISKS AND FILES
 9.1   The Memory Hierarchy
 9.1.1  Magnetic Disks
 9.1.2  Performance Implications of Disk Structure
 9.2   Redundant Arrays of Independent Disks
 9.2.1  Data Striping
 9.2.2  Redundancy
 9.2.3  Levels of Redundancy
 9.2.4  Choice of RAID Levels
 9.3   Disk Space Management
 9.3.1  Keeping Track Of Free Blocks
 9.3.2  Using OS File Systems to Manage Disk Space
 9.4   Buffer Manager
 9.4.1  Buffer Replacement Policies
 9.4.2  Buffer Management in DBMS versus OS
 9.5   Files of Records
 9.5.1  Implementing Heap Files
 9.6   Page Formats
 9.6.1  Fixed-Length Records
 9.6.2  Variable-Length Records
 9.7   Record Formats
 9.7.1  Fixed-Length Records
 9.7.2  Variable-Length Records
 9.8   Review Questions
10    TREE-STRUCTURED INDEXING
 10.1  Intuition For Tree Indexes
 10.2  Indexed Sequential Access Method (ISAM)
 10.2.1  Overflow Pages, Locking Considerations
 10.3  B+ Trees: A Dynamic Index Structure
 10.3.1  Format of a Node
 10.4  Search
 10.5  Insert
 10.6  Delete
 10.7  Duplicates
 10.8  B+ Trees in Practice
 10.8.1  Key Compression
 10.8.2  Bulk-Loading a B+ Tree
 10.8.3  The Order Concept
 10.8.4  The Effect of Inserts and Deletes on Rids
 10.9  Review Questions
11    HASH-BASED INDEXING
 11.1  Static Hashing
 11.1.1  Notation and Conventions
 11.2  Extendible Hashing
 11.3  Linear Hashing
 11.4  Extendible vs. Linear Hashing
 11.5  Review Questions
Part IV  QUERY EVALUATION
12   OVERVIEW OF QUERY EVALUATION
 12.1  The System Catalog
 12.1.1  Information in the Catalog
 12.2  Introduction to Operator Evaluation
 12.2.1  Three Common Techniques
 12.2.2  Access Paths
 12.3  Algorithms for Relational Operations
 12.3.1  Selection
 12.3.2  Projection
 12.3.3  Join
 12.3.4  Other Operations
 12.4  Introduction to Query Optimization
 12.4.1  Query Evaluation Plans
 12.4.2  Multi-operator Queries: Pipelined Evaluation
 12.4.3  The Iterator Interface
 12.5  Alternative Plans: A Motivating Example
 12.5.1  Pushing Selections
 12.5.2  Using Indexes
 12.6  What a Typical Optimizer Does
 12.6.1  Alternative Plans Considered
 12.6.2  Estimating the Cost of a Plan
 12.7  Review Questions
13   EXTERNAL SORTING
 13.1  When Does a DBMS Sort Data?
 13.2  A Simple Two-Way Merge Sort
 13.3  External Merge Sort
 13.3.1 Minimizing the Number of Runs
 13.4  Minimizing IlO Cost versus Number of I/Os
 13.4.1  Blocked I/O
 13.4.2  Double Buffering
 13.5  Using B+ Trees for Sorting
 13.5.1  Clustered Index
 13.5.2  Unclustered Index
 13.6  Review Questions
14    EVALUATING RELATIONAL OPERATORS
 14.1  The Selection Operation
 14.1.1  No Index, Unsorted Data
 14.1.2  No Index, Sorted Data
 14.1.3  B+ Tree Index
 14.1.4  Hash Index, Equality Selection
 14.2  General Selection Conditions
 14.2.1  CNF and Index Matching
 14.2.2  Evaluating Selections without Disjunction
 14.2.3  Selections with Disjunction
 14.3  The Projection Operation
 14.3.1  Projection Based on Sorting
 14.3.2  Projection Based on Hashing
 14.3.3  Sorting Versus Hashing for Projections
 14.3.4  Use of Indexes for Projections
 14.4  The Join 'Operation
 14.4.1  Nested Loops Join
 14.4.2  Sort-Merge Join
 14.4.3  Hash Join
 14.4.4  General Join Conditions
 14.5  The Set Operations
 14.5.1  Sorting for Union and Difference
 14.5.2  Hashing for Union and Difference
 14.6  Aggregate Operations
 14.6.1  Implementing Aggregation by Using an Index
 14.7  The Impact of Buffering
 14.8  Review Questions
15   A TYPICAL RELATIONAL QUERY OPTIMIZER
 15.1  Translating SQL Queries into Algebra
 15.1.1  Decomposition of a Query into Blocks
 15.1.2  A Query Block as a Relational Algebra Expression
 15.2  Estimating the Cost of a Plan
 15.2.1  Estimating Result Sizes
 15.3  Relational Algebra Equivalences
 15.3.1  Selections
 15.3.2  Projections
 15.3.3  Cross-Products and Joins
 15.3.4  Selects, Projects, and Joins
 15.3.5  Other Equivalences
 15.4  Enumeration of Alternative Plans
 15.4.1  Single-Relation Queries
 15.4.2  Multiple-Relation Queries
 15.5  Nested Subqueries
 15.6  The System R Optimizer
 15.7  Other Approaches to Query Optimization
 15.8  Review Questions
Part V  TRANSACTION MANAGEMENT
16    OVERVIEW OF TRANSACTION MANAGEMENT
 16.1  The ACID Properties
 16.1.1  Consistency and Isolation
 16.1.2  Atomicity and Durability
 16.2  Transactions and Schedules
 16.3  Concurrent Execution of Transactions
 16.3.1  Motivation for Concurrent Execution
 16.3.2  Serializability
 16.3.3  Anomalies Due to Interleaved Execution
 16.3.4  Schedules Involving Aborted Transactions
 16.4  Lock-Based Concurrency Control
 16.4.1  Strict Two-Phase Locking (Strict 2PL)
 16.4.2  Deadlocks
 16.5  Performance of Locking
 16.6  Transaction Support in SQL
 16.6.1  Creating and Terminating Transactions
 16.6.2  What Should We Lock?
 16.6.3  Transaction Characteristics in SQL
 16.7  Introduction to Crash Recovery
 16.7.1  Stealing Frames and Forcing Pages
 16.7.2  Recovery-Related Steps during Normal Execution
 16.7.3  Overview of ARIES
 16.7.4  Atomicity: Implementing Rollback
 16.8  Review Questions
17   CONCURRENCY CONTROL
 17.1  2PL, Serializability, and RecoVerability
 17.1.1  View Serializability
 17.2  Introduction to Lock Management
 17.2.1  Implementing Lock and Unlock Requests
 17.3  Lock Conversions
 17.4  Dealing With Deadlocks
 17.4.1  Deadlock Prevention
 17.5  Specialized Locking Techniques
 17.5.1  Dynamic Databases and the Phantom Problem
 17.5.2  Concurrency Control in B+ Trees
 17.5.3  Multiple-Granularity Locking
 17.6  Concurrency Control without Locking
 17.6.1  Optimistic Concurrency Control
 17.6.2  Timestamp-Based Concurrency Control
 17.6.3  Multiversion Concurrency Control
 17.7  Review Questions
18   CRASH RECOVERY
 18.1  Introduction to ARIES
 18.2  The Log
 18.3  Other Recovery-Related Structures
 18.4  The Write-Ahead Log Protocol
 18.5  Checkpointing
 18.6  Recovering from a System Crash
 18.6.1  Analysis Phase
 18.6.2  Redo Phase
 18.6.3  Undo Phase
 18.7  Media Recovery
 18.8  Other Approaches and Interaction with Concurrency Control
 18.9  Review Questions
Part VI  DATABASE DESIGN AND TUNING
19   SCHEMA REFINEMENT AND NORMAL FORMS
 19.1  Introduction to Schema Refinement
 19.1.1  Problems Caused by Redundancy
 19.1.2  Decompositions
 19.1.3  Problems Related to Decomposition
 19.2  Functional Dependencies
 19.3  Reasoning about FDs
 19.3.1  Closure of a Set of FDs
 19.3.2  Attribute Closure
 19.4  Normal Forms
 19.4.1  Boyce-Codd Normal Form
 19.4.2  Third Normal Form
 19.5  Properties of Decompositions
 19.5.1  Lossless-Join Decomposition
 19.5.2  Dependency-Preserving Decomposition
 19.6  Normalization
 19.6.1  Decomposition into BCNF
 19.6.2  Decomposition into 3NF
 19.7  Schema Refinement in Database Design
 19.7.1  Constraints on an Entity Set
 19.7.2  Constraints on a Relationship Set
 19.7.3  Identifying Attributes of Entities
 19.7.4  Identifying Entity Sets
 19.8  Other Kinds of Dependencies
 19.8.1  Multivalued Dependencies
 19.8.2  Fourth Normal Form
 19.8.3  Join Dependencies
 19.8.4  Fifth Normal Form
 19.8.5  Inclusion Dependencies
 19.9  Case Study: The Internet Shop
 19.10 Review Questions
20   PHYSICAL DATABASE DESIGN AND TUNING
 20.1  Introduction to Physical Database Design
 20.1.1  Database Workloads
 20.1.2  Physical Design and Tuning Decisions
 20.1.3  Need for Database Tuning
 20.2  Guidelines for Index Selection
 20.3  Basic Examples of Index Selection
 20.4  Clustering and Indexing
 20.4.1  Co-clustering Two Relations
 20.5  Indexes that Enable Index-Only Plans
 20.6  Tools to Assist in Index Selection
 20.6.1  Automatic Index Selection
 20.6.2  How Do Index Tuning Wizards Work?
 20.7  Overview of Database Tuning
 20.7.1  Tuning Indexes
 20.7.2  Tuning the Conceptual Schema
 20.7.3  Tuning Queries and Views
 20.8  Choices in Tuning the Conceptual Schema
 20.8.1  Settling for a Weaker Normal Form
 20.8.2  Denormalization
 20.8.3  Choice of Decomposition
 20.8.4  Vertical Partitioning of BCNF Relations
 20.8.5 Horizontal Decomposition
 20.9  Choices in Tuning Queries and Views
 20.10 Impact of Concurrency
 20.10.1  Reducing Lock Durations
 20.10.2  Reducing Hot Spots
 20.11  Case Study: The Internet Shop
 20.11.1  Tuning the Database
 20.12  DBMS Benchmarking
 20.12.1  Welt-Known DBMS Benchmarks
 20.12.2  Using a Benchmark
 20.13 Review Questions
21    SECURITY AND AUTHORIZATION
 21.1  Introduction to Database Security
 21.2  Access Control
 21.3  Discretionary Access Control
 21.3.1  Grant and Revoke on Views and Integrity Constraints
 21.4  Mandatory Access Control
 21.4.1  Multilevel Relations and Polyinstantiation
 21.4.2  Covert Channels, DoD Security Levels
 21.5  Security for Internet Applications
 21.5.1  Encryption
 21.5.2  Certifying Servers: The SSL Protocol
 21.5.3  Digital Signatures
 21.6  Additional Issues Related to Security
 21.6.1  Role of the Database Administrator
 21.6.2  Security in Statistical Databases
 21.7  Design Case Study: The Internet Store
 21.8  Review Questions
Part VII  ADDITIONAL TOPICS
22    PARALLEL AND DISTRIBUTED DATABASES
 22.1  Introduction
 22.2  Architectures for Parallel Databases
 22.3  Parallel Query Evaluation
 22.3.1  Data Partitioning
 22.3.2  Parallelizing Sequential Operator Evaluation Code
 22.4  Parallelizing Individual Operations
 22.4.1  Bulk Loading and Scanning
 22.4.2  Sorting
 22.4.3  Joins
 22.5  Parallel Query Optimization
 22.6  Introduction to Distributed Databases
 22.6.1  Types of Distributed Databases
 22.7  Distributed DBMS Architectures
 22.7.1  Client-Server Systems
 22.7.2  Collaborating Server Systems
 22.7.3  Middleware Systems
 22.8  Storing Data in a Distributed DBMS
 22.8.1  Fragmentation
 22.8.2  Replication
 22.9  Distributed Catalog Management
 22.9.1  Naming Objects
 22.9.2  Catalog Structure
 22.9.3  Distributed Data Independence
 22.10  Distributed Query Processing
 22.10.1  Nonjoin Queries in a Distributed DBMS
 22.10.2  Joins in a Distributed DBMS
 22.10.3  Cost-Based Query Optimization
 22.11 Updating Distributed Data
 22.11.1  Synchronous Replication
 22.11.2  Asynchronous Replication
 22.12 Distributed Transactions
 22.13 Distributed Concurrency Control
 22.13.1  Distributed Deadlock
 22.14 Distributed Recovery
 22.14.1  Normal Execution and Commit Protocols
 22.14.2  Restart after a Failure
 22.14.3  Two-Phase Commit Revisited
 22.14.4  Three-Phase Commit
 22.15 Review Questions
23    OBJECT-DATABASE SYSTEMS
 23.1  Motivating Example
 23.1.1  New Data Types
 23.1.2  Manipulating the New Data
 23.2  Structured Data Types
 23.2.1  Collection Types
 23.3  Operations on Structured Data
 23.3.1  Operations on Rows
 23.3.2  Operations on Arrays
 23.3.3  Operations on Other Collection Types
 23.3.4  Queries Over Nested Collections
 23.4  Encapsulation and ADTs
 23.4.1  Defining Methods
 23.5  Inheritance
 23.5.1  Defining Types with Inheritance
 23.5.2  Binding Methods
 23.5.3 Collection Hierarchies
 23.6  Objects, OIDs, and Reference Types
 23.6.1  Notions of Equality
 23.6.2  Dereferencing Reference Types
 23.6.3  URLs and OIDs in SQL:1999
 23.7  Database Design for an ORDBMS
 23.7.1  Collection Types and ADTs
 23.7.2  Object Identity
 23.7.3  Extending the ER Model
 23.7.4  Using Nested Collections
 23.8  ORDBMS Implementation Challenges
 23.8.1  Storage and Access Methods
 23.8.2  Query Processing
 23.8.3  Query Optimization
 23.9  00DBMS
 23.9.1  The ODMG Data Model and ODL
 23.9.2  0QL
 23.10  Comparing RDBMS, OODBMS, and ORDBMS
 23.10.1  RDBMS versus ORDBMS
 23.10.2  OODBMS versus ORDBMS: Similarities
 23.10.3  00DBMS versus ORDBMS: Differences
 23.11 Review Questions
24   DEDUCTIVE DATABASES
 24.1  Introduction to Recursive Queries
 24.1.1  Datalog
 24.2  Theoretical Foundations
 24.2.1  Least Model Semantics
 24.2.2  The Fixpoint Operator
 24.2.3  Safe Datalog Programs
 24.2.4  Least Model -- Least Fixpoint
 24.3  Recursive Queries with Negation
 24.3.1  Stratification
 24.4  From Datalog to SQL
 24.5  Evaluating Recursive Queries
 24.5.1  Fixpoint Evaluation without Repeated Inferences
 24.5.2  Pushing Selections to Avoid Irrelevant Inferences
 24.5.3  The Magic Sets Algorithm
 24.6  Review Questions
25    DATA WAREHOUSING AND DECISION SUPPORT
 25.1  Introduction to Decision Support
 25.2  OLAP: Multidimensional Data Model
 25.2.1  Multidimensional Database Design
 25.3  Multidimensional Aggregation Queries
 25.3.1  ROLLUP and CUBE in SQL:1999
 25.4  Window Queries in SQL:1999
 25.4.1  Framing a Window
 25.4.2  New Aggregate Functions
 25.5  Finding Answers Quickly
 25.5.1  Top N Queries
 25.5.2  Online Aggregation
 25.6  Implementation Techniques for OLAP
 25.6.1  Bitmap Indexes
 25.6.2  Join Indexes
 25.6.3  File Organizations
 25.7  Data Warehousing
 25.7.1  Creating and Maintaining a Warehouse
 25.8  Views and Decision Support
 25.8.1  Views, OLAP, and Warehousing
 25.8.2  Queries over Views
 25.9  View Materialization
 25.9.1  Issues in View Materialization
 25.10 Maintaining Materialized Views
 25.10.1  Incremental View Maintenance
 25.10.2  Maintaining Warehouse Views
 25.10.3  When Should We Synchronize Views?
 25.11 Review Questions
26   DATA MINING
 26.1  Introduction to Data Mining
 26.1.1  The Knowledge Discovery Process
 26.2  Counting Co-occurrences
 26.2.1  Frequent Itemsets
 26.2.2  Iceberg Queries
 26.3  Mining for Rules
 26.3.1  Association Rules
 26.3.2  An Algorithm for Finding Association Rules
 26.3.3  Association Rules and ISA Hierarchies
 26.3.4  Generalized Association Rules
 26.3.5  Sequential Patterns
 26.3.6  The Use of Association Rules for Prediction
 26.3.7  Bayesian Networks
 26.3.8  Classification and Regression Rules
 26.4  Tree-Structured Rules
 26.4.1  Decision Trees
 26.4.2  An Algorithm to Build Decision Trees
 26.5  Clustering
 26.5.1  A Clustering Algorithm
 26.6  Similarity Search over Sequences
 26.6.1  An Algorithm to Find Similar Sequences
 26.7  Incremental Mining and Data Streams
 26.7.1 Incremental Maintenance of Frequent Itemsets
 26.8  Additional Data Mining Tasks
 26.9  Review Questions
27   INFORMATION RETRIEVAL AND XML DATA
 27.1  Colliding Worlds: Databases, IR, and XML
 27.1.1  DBMS versus IR Systems
 27.2  Introduction to Information Retrieval
 27.2.1  Vector Space Model
 27.2.2  TF/IDF Weighting of Terms
 27.2.3  Ranking Document Similarity
 27.2.4  Measuring Success: Precision and Recall
 27.3  Indexing for Text Search
 27.3.1  Inverted Indexes
 27.3.2  Signature Files
 27.4  Web Search Engines
 27.4.1  Search Engine Architecture
 27.4.2  Using Link Information
 27.5  Managing Text in a DBMS
 27.5.1  Loosely Coupled Inverted Index
 27.6  A Data Model for XML
 27.6.1  Motivation for Loose Structure
 27.6.2  A Graph Model
 27.7  XQuery: Querying XML Data
 27.7.1  Path Expressions
 27.7.2  FLWR Expressions
 27.7.3  Ordering of Elements
 27.7.4  Grouping and Generation of Collection Values
 27.8  Efficient Evaluation of XML Queries
 27.8.1  Storing XML in RDBMS
 27.8.2  Indexing XML Repositories
 27.9  Review Questions
28    SPATIAL DATA MANAGEMENT
 28.1  Types of Spatial Data and Queries
 28.2  Applications Involving Spatial Data
 28.3  Introduction to Spatial Indexes
 28.3.1  Overview of Proposed Index Structures
 28.4  Indexing Based on Space-Filling Curves
 28.4.1  Region Quad Trees and Z-Ordering: Region Data
 28.4.2  Spatial Queries Using Z-Ordering
 28.5  Grid Files
 28.5.1  Adapting Grid Files to Handle Regions
 28.6  R Trees: Point and Region Data
 28.6.1  Queries
 28.6.2  Insert and Delete Operations
 28.6.3  Concurrency Control
 28.6.4  Generalized Search Trees
 28.7  Issues in High-Dimensional Indexing
 28.8  Review Questions
29   FURTHER READING
 29.1  Advanced Transaction Processing
 29.1.1  Transaction Processing Monitors
 29.1.2  New Transaction Models
 29.1.3  Real-Time DBMSs
 29.2  Data Integration
 29.3  Mobile Databases
 29.4  Main Memory Databases
 29.5  Multimedia Databases
 29.6  Geographic Information Systems
 29.7  Temporal Databases
 29.8  Biological Databases
 29.9  Information Visualization
 29.10 Summary
 30   THE MINIBASE SOFTWARE
 30.1  What Is Available
 30.2  Overview of Minibase Assignments
 30.3  Acknowledgments
REFERENCES
SUBJECT INDEX