DBMS Oral Exam Review Flashcards

Comprehensive vocabulary flashcards generated from the lecture transcript and diagrams covering DBMS concepts, relational theory, SQL/QBE, indexing, query execution, concurrency control, crash recovery, and database design.

Three Levels of Data Abstraction

The database architecture consisting of the Physical Level (physical schema), Conceptual Level (logical schema), and View Level, which provides logical and physical data independence.

DBMS Layered Architecture

The architectural structure of a DBMS containing layers for Query Optimization and Execution, Relational Operators, Files and Access Methods, Buffer Management, and Disk Space Management.

Basic SQL Query Syntax

The fundamental structure of an SQL query consisting of SELECT [DISTINCT] target-list, FROM relation-list, and WHERE qualification.

SQL Division via EXCEPT / NOT EXISTS

An SQL query technique used to express division or universal quantification by combining subqueries with NOT EXISTS and EXCEPT clauses.

SQL GROUP BY Clause Syntax

The SQL query structure incorporating SELECT, FROM, WHERE, GROUP BY grouping-list, and HAVING group-qualification to partition tuples into groups for aggregate evaluation.

ISAM (Index Sequential Access Method)

A static tree index structure composed of non-leaf index pages pointing to sequentially ordered leaf pages, utilizing overflow pages when leaf pages fill up.

B+ Tree Index

A dynamic, balanced tree index structure composed of Root, Internal, and Leaf nodes that adjusts dynamically to insertions and deletions to remain balanced.

Static Hashing

A index structure where key values are mapped to primary bucket pages using a hash function $h(\text{key}) \bmod N$, which can lead to long overflow chains when pages fill up.

Extendible Hashing

A dynamic hashing scheme that uses a directory with a Global depth and data buckets with Local depths to avoid overflow pages by splitting buckets and doubling the directory when needed.

Linear Hashing

A dynamic hashing scheme that manages bucket growth using a pointer 'Next' to split buckets sequentially one by one without needing a centralized directory.

Left-Deep vs. Bushy Join Trees

Comparison of relational operator trees where left-deep trees restrict joins to a base table and an intermediate result to allow pipelining, while bushy trees allow joins between two sub-results.

Reading Uncommitted Data (WR Conflict)

An execution anomaly (dirty read) where transaction $T_2$ reads a data object modified by transaction $T_1$ before $T_1$ has committed or aborted.

Dependency Graph

A directed graph with nodes representing active transactions and edges representing conflicting access operations, used to detect deadlocks or test for conflict serializability.

Unrepeatable Read (RW Conflict)

An execution anomaly where transaction $T_2$ modifies or updates an object that has been read by transaction $T_1$ while $T_1$ is still active.

Overwriting Uncommitted Data (WW Conflict)

An execution anomaly where transaction $T_2$ overwrites the value of an object that has already been modified by transaction $T_1$ before $T_1$ commits.

Database Management System (DBMS)

Software designed to assist in maintaining and utilizing a large collection of data, providing a convenient and efficient way to store and retrieve database information.

Data Model

A collection of high-level data description constructs that hide low-level storage details, providing tools to describe data, relationships, semantics, and consistency constraints.

Data Independence

The property of a DBMS allowing schemas (physical or logical) to be modified without affecting higher-level applications or abstract views.

Transaction

An execution of a user program in a DBMS representing the basic, atomic sequence of database actions (reads and writes) that cannot be divided further.

Integrity Constraint (IC)

A condition specified on a database schema that restricts the valid data instances that can be stored in the database.

Primary Key

A candidate key selected by the database designer as the principal means of uniquely identifying tuples within a relation.

Foreign Key

A set of fields in one relation used to refer to a tuple in another relation by matching its primary key.

Referential Integrity

A constraint ensuring that every value of a foreign key matches an existing primary key value in the referenced relation.

Relational Algebra

A formal query language with operational building blocks that take one or more relations as input and produce a relation as output.

Selection ($\sigma$)

A basic relational algebra operation that selects a subset of rows from a relation that satisfy a given condition.

Projection ($\pi$)

A basic relational algebra operation that selects specified columns from a relation and eliminates duplicate rows.

Natural Join

An equijoin over all common attributes of two relations where duplicate common attribute columns are removed.

Relational Calculus

A declarative formal query language based on mathematical logic, available as Tuple Relational Calculus (TRC) or Domain Relational Calculus (DRC).

Unsafe Query

A syntactically valid calculus query that produces an infinite number of answer tuples.

Relational Completeness

The capability of a query language to express any query that can be expressed in relational algebra or relational calculus.

Nested Query

A query that contains another subquery embedded within its WHERE or HAVING clauses.

Trigger

A database procedure executed automatically when specified modification events occur, composed of an Event, Condition, and Action.

Search Key

A set of attributes used to look up and locate records within a data file.

Clustered Index

An index where the physical order of stored data records matches or closely matches the order of data entries in the index.

Access Method

A technique used by a DBMS to retrieve data records from storage based on a query condition, such as file scans, tree indexes, or hash indexes.

External Merge Sort Cost

The I/O performance metric for sorting $N$ pages using $B$ buffer pages, evaluated as $2N \times (1 + \rceil \text{log}_{B-1}(N / B) \rceil)$ I/O operations.

Conflict Serializable Schedule

A schedule that is conflict equivalent to some serial schedule, characterized by an acyclic dependency graph.

Strict 2PL Protocol

A locking protocol where transactions obtain Shared locks for reads and Exclusive locks for writes, holding all locks until the transaction commits.

Optimistic Concurrency Control

A lock-free concurrency control method (Kung-Robinson) where transactions execute across three phases: READ, VALIDATE, and WRITE.

ACID Properties

The four defining properties of database transactions: Atomicity, Consistency, Isolation, and Durability.

Write-Ahead Logging (WAL) Protocol

A protocol ensuring durability and atomicity by requiring update log records to be written to disk before corresponding data pages, and all log records to be written before transaction commit.

Functional Dependency (FD)

A constraint $X \rightarrow Y$ stating that if two tuples in a relation agree on attribute set $X$, they must also agree on attribute set $Y$.

Armstrong's Axioms

A sound and complete set of inference rules for FDs: Reflexivity (if Y \ref X, then $X \rightarrow Y$), Augmentation (if $X \rightarrow Y$, then $XZ \rightarrow YZ$), and Transitivity (if $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$).

Boyce-Codd Normal Form (BCNF)

A strict normal form where for every non-trivial functional dependency $X \rightarrow A$, the determinant $X$ must be a superkey.

Third Normal Form (3NF)

A normal form where for every functional dependency $X \rightarrow A$, either the dependency is trivial, $X$ is a superkey, or $A$ is a prime attribute.

Lossless-Join Decomposition

A relation decomposition into sub-relations $X$ and $Y$ ensuring that joining their projections produces the exact original relation without extra spurious tuples: $\text{π}_X(R) \bowtie \text{π}_Y(R) = R$.

Dependency Preserving Decomposition

A decomposition of a relation schema where all functional dependencies in the original set $F^+$ can be enforced using only the functional dependencies of the decomposed relations.

Minimal Cover

A simplified, equivalent set of functional dependencies where each FD has a single RHS attribute and contains no redundant FDs or extra attributes on the LHS.