Index Structures for Data Warehouses

"Data warehouses differ significantly from traditional transaction-oriented operational database applications. Indexing techniques and index structures applied in the transaction-oriented context are not feasible for data warehouses.
This work develops specific heuristic indexing techniques which process range queries on aggregated data more efficiently than those traditionally used in transaction-oriented systems. The book presents chapters on:
- the state of the art in data warehouse research
- data storage and index structures
- finding optimal tree-based index structures
- aggregated data in tree-based index structures
- performance models for tree-based index structures
- and techniques for comparing index structures."

1　Introduction
　1.1 Goals
　1.2 Outline
2　State of the Art of Data Warehouse Research
　2.1 Introduction
　2.2 Traditional Transaction-Oriented Systems
　2.3 Data Warehouses for Decision Support
　2.4 OLAP Vs.OLTP
　2.5 Accelerating Query Speed
　　2.5.1 Denormalized Schemas
　　2.5.2 Materialized Views
　　2.5.3 No Locking
　　2.5.4 On-line Aggregation
　　2.5.5 Index Structures
　2.6 Summary
3　Data Storage and Index Structures
　3.1 Introduction
　3.2 Memory Hierarchy
　3.3 Mechanics of Disks
　3.4 Data Space and Queries
　　3.4.1 Data Space
　　3.4.2 Queries
　3.5 Tree-Based Indexing
　　3.5.1 Top-Down, Bottom-Up, and Bulk Loading
　　3.5.2 Point Quadtrees
　　3.5.3 kd-tree
　　3.5.4 kdb-tree
　　3.5.5 R-tree
　　3.5.6 R*-tree
　　3.5.7 Other Relatives of the R-tree Family and Other Tree Structures
　　3.5.8 Generic Tree Structures
3.6 Bitmap Indexing
3.6.1 Standard Bitmap Indexing
3.6.2 Multi-component Equality Encoded Bitmap Index
3.6.3 Range-Based Encoding
3.6.4 Multi-component Range-Based Encoding
3.6.5 Other Compression Techniques/Combination of Bitmaps and Trees
　3.7 Arrays
　3.8 Summary
4　Mixed Integer Problems for Finding Optimal Tree-Based Index Structures
　4.1 Introduction
　4.2 Optimization Problem Parameters
　4.3 Mapping into a Mixed Integer Problem
　4.4 Problem Complexity
　4.5 Model Evaluation
　4.6 Summary
5　Aggregated Data in Tree-Based Index Structures
　5.1 Introduction
　5.2 “Fit for Aggregation” Access Method
　5.3 Materialization of Data
　5.4 Modified Operations
　　5.4.1 Insert Operation
5.4.2 Delete Operation
5.4.3 Update Operation
5.4.4 Creating Index Structures，Bottom-Up Index Structures
　　5.4.5 Point Query Algorithm
　　5.4.6 Range Query Algorithm
　5.5　Storage Cost
　5.6　Height of Tree
　5.7　Overlaps of Regions
　5.8　Experiments
　　5.8.1 Cost Model
　　5.8.2 Physical Index Structure
　　5.8.3 Implementation
　　5.8.4 Generation of Test Data
　　5.8.5 Query Profile
　　5.8.6 Results of Experiments
　5.9　Summary
6　Performance Models for Tree-Based Index Structures
7 Techniques for Comparing Index Structures
8 Conclusion and Outlook
A List of Symbols
B Approximation of PISA Model
Bibliography
Index