## 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)