> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/databases.md).

# databases

## Basic idea

Database systems organize durable state while supporting efficient queries, concurrent updates, and recovery after failure. Their design joins data structures, operating systems, distributed protocols, and transaction theory.

## Key formulas

* I/O cost is often modeled in transferred pages rather than individual instructions.
* Write amplification: $WA=\text{bytes written to storage}/\text{logical bytes written}$.
* Serializability requires an execution equivalent to some serial ordering of transactions.
* Write-ahead logging rule: the log record reaches stable storage before the corresponding data page.
* MVCC selects visible versions from a snapshot; OCC validates speculative work before commit.
* Distributed commit, timestamp ordering, and deterministic ordering coordinate transactions across nodes.
* Cost-based optimizers choose join orders and algorithms using estimated cardinality and machine cost.