Contents

• Contents
• Introduction
  • Motivation
  • Research Goal
  • Synopsis
• Temporal Databases
  • Introduction
  • Basic Concepts and Notations
  • Temporal and Conventional Databases
  • Temporal Databases and Data Warehousing
• Join Processing
  • Definition of the Join
  • Role of the Join Operation
    • The Significance of the Join in Relation Query Processing
    • Join Performance Issues
  • Types of Joins
  • Sequential Join Algorithms
    • Brute Force Nested-Loops Joins
    • Sort-Merge Joins
    • Hash Joins
    • Data-Structure-Assisted Joins
  • Parallel Joins
    • Fragment-And-Replicate Technique
    • Symmetric Partitioning Technique
  • Classification of Join Algorithms
• Temporal Join Processing
  • Definition and Types of Temporal Joins
  • Significance of Temporal Joins
  • Non-Explicit-Partitioning Techniques
    • Overview
    • Nested-Loop Temporal Joins
    • Sort-Merge Joins
    • Data-Structure-Assisted Joins
  • Explicit-Partitioning Join Algorithms
    • Overview
    • Simple Temporal Hash Join
    • Improved Temporal Hash Join
    • Partitioned Temporal Join for Sequential Processing
    • Spatially Partitioned Temporal Join
  • A Short Summary
  • Temporal-Specific Join Optimisation Issues
• The Interval Partitioning Problem
  • Introduction
  • Preliminaries
  • Problem Definition
  • Search Space
  • Optimal Partitioning
    • Algorithm for Optimal Partitioning
    • Example
    • Correctness
  • Alternative: Reducing IP to a Graph-Theoretic Problem
    • Sequential Graph Partitioning
    • Reducing IP to SGP
    • Example
    • Correctness
    • Optimal Solution for SGP
    • Example
    • Run-Time Complexity Analysis
• Optimisation of Partitioned Temporal Joins
  • Optimisation Process
  • Integration into a Query Optimiser
• IP-Tables
  • Motivation
  • Definition
  • Size Considerations
    • The Size of an IP-Table
    • Realistic Examples
    • Condensation of IP-Tables
    • Endpoint IP-Tables
  • Maintaining IP-Tables
    • Maintaining Complete IP-Tables
    • Maintaining Condensed IP-Tables
    • Maintaining Endpoint IP-Tables
  • Merging IP-Tables
    • Merging Complete IP-Tables
    • Merging Incomplete IP-Tables
    • Merging Complete and Incomplete IP-Tables
  • Histograms and IP-Tables
• Performance Model
  • Outline
  • The Architectural Model
    • Introduction
    • Summary of the Architectural Discussion
    • A Hybrid Architecture
  • Temporal Join Processing Model
    • Preliminaries
    • Temporal Join Processing
    • Stage 1: Repartitioning
    • Stage 2: Joining
  • Cost Model
    • The Basic Issues
    • Stage 1: Repartitioning
    • Stage 2: Joining
  • Evaluation of Characteristics
    • Uniform Workloads
    • Experiments
    • Conclusions
• Partitioning Strategies
  • Uniform Strategies
    • Uniform Lifespan Partitioning
    • Uniform Range Partitioning
    • Uniform Startpoints' Span Partitioning
    • Conclusions
  • Underflow Strategies
    • Basic Strategy
    • Variations
  • Minimum-Overlaps Strategies
    • Basic Strategy
    • Variations
  • Black-Out Preprocessing Strategy
• Experimental Evaluation
  • The Test Data
    • Introduction
    • The Basic Data Set
  • A General Comparison between the Strategies
  • Dependency on m
  • Dependency on X_R and X_Q
  • Dependency on
  • Dependency on |R| and |Q|
  • The Architectural Influence
  • Influence of the Condensation Factor a
  • Impact of Black-Out Preprocessing
  • Summary
    • Experiments on the Parallel Architecture
    • Experiments on the Single-Processor Architecture
• Using IP-Tables for Selectivity Estimation
  • Introduction
  • Temporal Join Conditions
    • Elementary Conditions
    • Composite Conditions
  • Size and Selectivity Calculations
    • Elementary Joins
    • Composite Joins
    • Parallel and Other Partitioned Joins
  • Summary
• Summary, Conclusions and Future Work
  • Summary
  • Conclusions
  • Future Work
• Summary of the Cost Model
• Test Data Creation
  • Timestamps for R
  • Timestamps for Q
• Manipulation of Interval Lengths
• Profiles of the and
• References
• Index