DBMS and Database Design Lecture Notes

This set of vocabulary flashcards covers Database Management Systems (DBMS) topics including file organization, indexing costs, transaction ACID properties, concurrency control anomalies, locking protocols (Strict 2PL), and normalization theory (3NF, BCNF, etc.).

A DBMS buffer manager is responsible for which of the following tasks?

Responsible for fetching pages from disk into main memory for processing.

Clustered Index

An index where the ordering of data records is the same as or close to the ordering of data entries in the index.

B+ Tree Doubly-linked list

A structure at the leaf level used to facilitate the retrieval of qualifying entries during a range search.

Heap File

An unordered file that supports efficient retrieval of all records but does not optimize searches based on specific field values; generally the least efficient for range searches.

Sorted File Equality Search Cost

The I/O cost is defined as $D ext{log}_2B$, where B is the number of data pages and D is the I/O time.

Primary Index

An index on a set of fields that includes the primary key and is guaranteed not to contain duplicate data entries.

Hash-based Index

An index structure excellent for equality searches ($ext{key} = ext{value}$) but generally ineffective for range searches ( ext{key} > ext{value}).

Atomicity

An ACID property ensuring that if a transaction's actions are interrupted by a crash, the partial effects are undone.

Dirty Read (WR conflict)

Occurs when transaction $T_2$ reads an object modified by $T_1$ before $T_1$ has committed.

Serializable Schedule

A schedule guaranteed to produce the same result as some serial execution of the transactions.

Strict Two-Phase Locking (Strict 2PL)

A protocol where all locks (shared and exclusive) held by a transaction are released only after the transaction has committed or aborted.

Unrepeatable Read

An anomaly where a transaction reads an object, a second transaction overwrites it and commits, and the first transaction reads the same object again to find a different value.

Write-Ahead Logging (WAL)

A protocol requiring all log records for a transaction to be written to disk before the corresponding data pages are written to disk.

Deadlock

A cycle of transactions where each is waiting for a lock held by another in the cycle.

Durability

A transaction property typically guaranteed by the Recovery Manager using the Log.

Recoverable Schedule

A schedule where transactions commit only after all transactions whose changes they have read successfully commit.

Thrashing

Occurs in a database when the system spends more time managing lock contention (transactions waiting for each other) than doing actual work.

Phantom Problem

A situation where the set of rows satisfying a query changes during execution due to concurrent inserts or updates, even if row-level shared locks are used.

Steal Approach

A buffer manager policy that allows changes made by an uncommitted transaction to be written to disk.

Functional Dependency ($X \rightarrow Y$)

A constraint where if two tuples agree on the values in attributes X, they must also agree on the values in attributes Y.

Third Normal Form (3NF)

A relation is in this form if for every non-trivial FD $X \rightarrow A$, either X is a superkey or A is part of some candidate key.

Lossless-Join Decomposition

A decomposition of relation R into $R_1$ and $R_2$ where the common attributes ($R_1 \cap R_2$) form a candidate key for at least one of the new relations.

Dependency Preservation

Ensures all original functional dependencies can be checked by looking at individual relations in a decomposition without performing a join.

Insertion Anomaly

Occurs when certain information cannot be represented in a database because the primary key is not yet available.

Armstrong's Axioms: Transitivity

A rule stating that if $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$.

Armstrong's Axioms: Augmentation

A rule stating that if $X \rightarrow Y$, then $XZ \rightarrow YZ$.

Closure of Attributes ($X^+$)

The set of all attributes that a given set of attributes X can determine via functional dependencies.

Boyce-Codd Normal Form (BCNF)

A relation schema where for every non-trivial functional dependency $X \rightarrow A$, X must be a superkey.

Minimal Cover

A simplified set of functional dependencies where the order of evaluation and deletion of redundant dependencies can affect the resulting set.

Multivalued Dependency ($X \rightarrow \rightarrow Y$)

Asserts that for a given X value, the associated set of Y values is entirely independent of the values in the rest of the attributes.

Composite Search Key

An index search key that contains several fields.

Index-only Plan

A query evaluation plan where the query is answered solely using the data entries in the index without accessing the actual data records.