Jin Hyun Park / Qual Exam Prep / Databases

Databases

Keys, transactions, indexes, and normalization. The questions are mostly definitions.

Primary key vs. foreign key

A primary key uniquely identifies a row within its own table. A foreign key is a column that refers to the primary key of another table; it is how tables are linked. In the example below, each order belongs to one customer, so the Orders table stores the customer's ID as a foreign key.

Orders	Customers
Order_ID (primary key) Customer_ID (foreign key → Customers) Product	Customer_ID (primary key) Name Address

Transaction log

Also called the database log or write-ahead log (WAL).

• It records every change made to the data, in order. If the system crashes halfway through a transaction, the log is what lets the database roll back or redo the work.
• The log is what gives a transaction atomicity and durability. The other two ACID properties come from elsewhere: isolation from the concurrency-control mechanism (locking, timestamps), and consistency from integrity constraints and correct application code. ACID is the set of properties that make a transaction safe:
  • Atomicity: a transaction is all-or-nothing. It never stops halfway with some of its changes applied.
  • Consistency: a transaction moves the database from one valid state to another; data can only be changed in ways that respect the defined rules and constraints.
  • Isolation: concurrent transactions do not interfere with each other. Each one behaves as if it were running alone.
  • Durability: once a transaction commits, its changes survive crashes and power loss.

ER (entity–relationship) model

• (To be added.)

NoSQL

• "Not only SQL": databases that are not relational and do not define relationships between tables.
• The simplest kind stores data as (key, value) pairs and supports reads and writes by key only. There are no joins, no fixed schema, and it scales to very large amounts of data. The trade-off is weaker consistency guarantees (typically eventual consistency rather than ACID transactions), no joins or ad-hoc queries, and the loss of SQL's query flexibility.

Normalization

• Normalization is the process of organizing tables during relational database design so that each fact is stored in one place, which minimizes redundancy.
• In practice it means splitting large, loosely organized tables into smaller, well-structured ones.

Clustered vs. non-clustered index

• Clustered index
  • Determines the physical order in which the rows are stored on disk. The table is the index.
  • Analogy: a dictionary, where the entries are physically sorted by the word.
• Non-clustered index
  • A separate structure that stores the key and a pointer to where the row actually lives.
  • Analogy: the index at the back of a book, which points you to the page.
• Consequences:
  • A table can have only one clustered index, because the rows can only be physically sorted one way.
  • A table can have many non-clustered indexes.
  • Reading through a clustered index is faster, since there is no extra lookup step.

Normal forms

• First normal form (1NF): every attribute holds a single atomic value. No lists inside a cell, no repeating groups of columns.
• Second normal form (2NF): 1NF plus no partial dependencies. This only matters when the primary key is composite (made of several columns): no non-key column may depend on just part of the key. If a column depends on only one piece of the key, it belongs in its own table. A table with a single-column primary key is automatically in 2NF.
• Third normal form (3NF): 2NF plus no transitive dependencies. Every non-key column must depend on the primary key directly, not on some other non-key column. If column C depends on column B, which depends on the key, move B and C into a separate table.
• Boyce–Codd normal form (BCNF): for every non-trivial functional dependency X → A, X must be a superkey. It is slightly stricter than 3NF, which also allows the case where A is part of a candidate key.

Overview · Useful materials · Sample questions · Algorithms · Architecture · OS · Networking · Automata · AI / ML · Things to remember