Database Systems Architecture (ULB)

• The course was taken in autumn 2013 at the ULB
• Taught by Stijn Vansummeren

Content

Query Processing

Logical Query Plan

• Relational Algebra
• Translating SQL to Relational Algebra
• Logical Query Plan Optimization: Heuristics and optimization of Conjunctive Queries

Physical Query Plan

• Physical Operators (databases)
• Physical Query Plan Optimization
  • Query Result Size Estimation to estimate the result size
  • Join Ordering to select the optimal way of ordering join operations
  • Greedy Algorithm to select the optimal plan

Indexing

Simple (Conventional) Indexes

• Dense Index
• Sparse Index
• Secondary Index

Tree-Based Indexes

• B-Tree

Hash-Based Indexes

• Open Hashing Index
• Extensible Hashing
• Linear Hashing

Multi-Dimensional Indexes

Conventional

• Multiple-Key Index

Tree-Based Indexes

• kd-Trees
• Quad Trees
• R-Tree

Hash-Based Indexes

• Grid File Index
• Partitioned Hash Function Index

Different Stuff

• Physical Data Organization (databases)
• Typical DB Architecture

Ensuring ACID

; A, C and D

• Crash Recovery
• Database Transaction Log
  • Undo Logging
  • Redo Logging
  • Undo/Redo Logging ; I
• Concurrency Control and Serializable Scheduling
• Schedulers:
  • Lock-Based Scheduler
  • Timestamp-Based Scheduler
  • Validation-Based Scheduler

Info

• Course Webpage http://cs.ulb.ac.be/public/teaching/infoh417
• Dropbox folder with all the materials https://www.dropbox.com/sh/r0zvy3zaycbevx8/yLvz9YdT-f