Centralized Databases

Database Features

  • Controlled redundancy
  • Data normalization (normal form)
  • Data consistency
  • Integrity constraints
  • Query languages
  • Effective/secure data sharing
  • Backup/recovery

Database characteristics

  • Well-structuredness (catalog)
  • Efficient manipulation (DDL, DML, physical tuning, indexing, optimized query plan)
  • Isolation between application and data (data models, conceptual model)
  • Data independence (physical, logical, ANSI-SPARC)
  • Views (security, virtual data, materialized views)
  • Data sharing
  • Atomic multi-user transactions (concurrency control)
  • ACID transaction

Query processing

  • Constraints for query processing
    • Low response time (minimize computation time)
    • High query throughput
    • Efficient hardware usage (minimize disk access)
  • Centralized query processing workflow
    • Parser
    • Query translator
    • Query optimizer
    • Physical optimizer
    • Query execution

Query parser and query translator

  • Task: Translate query from query language to internal representation
  • Internal representation: Naive query plan in relational algebra

Query optimizer

  • Task: Find good plan, avoid very bad plans
  • Use statistics
    • Table size
    • Indexes
    • Physical speed
  • Optimize query
    • Algebraic optimization
      • Heuristic-based optimization (break selections, push projection, push selection, force joins)
      • Cost-based query optimization (join order optimization, use a cost model, e.g. dynamic programming)
      • Statistical query optimization
    • Physical optimization
      • Find efficient algorithms for operations
      • Join algorithms (block-nested loop join, hash join, merge join)
      • Selection algorithms (index scan, linear scan)
      • Pipelining (iterator interface)
      • Use physical relational algebra

Transaction processing

  • Transaction
    • Finite set of operations (certain order, ensure properties)
    • Interface contract (e.g., start, commit, rollback)
  • Properties: ACID
    • Consistency (structural, semantic)
  • Types:
    • Flat transaction: Single start/commit
    • Nested transaction: Multiple start/commits (subtransactions)
  • Possible problems:
    • Atomicity: Dirty read
    • Consistency: Inconsistent read
    • Isolation: Lost update
    • Durability: Data loss
  • Solution: Transaction protocols
  • Schedule
    • Order/sequence of operations (with locks)
    • Serial schedule: No mixing of transaction of other transactions (no parallelization)
  • Locks
    • Flat attached to data item
    • Indicates whether it may be used or not
    • Read locks/write locks
    • Lock promotion if required
  • Optimistic protocols: Assume no errors
  • Pessimistic protocols
    • Assume errors (e.g., 2PL)
    • Use locks to avoid transactional inconsistency
  • Two-phase locking:
    • Lock phase + Unlock phase
    • Lock point
    • Generate (serializable schedules)
    • Deadlocks possible
    • Conservative locking: (aquire all locks before transaction starts, very un-concurrent)
    • Strict two-phase locking (hold locks until commit, commonly used)