GATE CS & IT Engineering Databases Syllabus

Name the four types of integrity constraints in the relational model.

1) Domain constraint (attribute values come from a defined domain); 2) Entity integrity (primary key cannot be NULL); 3) Referential integrity (foreign key matches an existing primary key or is NULL); 4) Key constraint (uniqueness of candidate/primary keys).

State the entity integrity constraint.

No attribute that is part of a primary key may have a NULL value, ensuring every tuple is uniquely identifiable.

State the referential integrity constraint.

A foreign key value in a referencing relation must either match some primary key value in the referenced relation or be entirely NULL; it cannot reference a non-existent tuple.

What are the referential triggered actions ON DELETE / ON UPDATE in SQL?

CASCADE (propagate the delete/update), SET NULL (set foreign key to NULL), SET DEFAULT (set to a default value), and NO ACTION / RESTRICT (reject the operation if it violates integrity).

Differentiate a candidate key, primary key, and super key.

A super key is any attribute set that uniquely identifies tuples. A candidate key is a minimal super key (no proper subset is a super key). A primary key is one candidate key chosen as the main identifier; remaining candidate keys are alternate keys.

What is a prime attribute versus a non-prime attribute?

A prime attribute is part of at least one candidate key. A non-prime attribute is not part of any candidate key.

Define a functional dependency $X \to Y$.

$X \to Y$ holds if any two tuples that agree on attribute set $X$ must also agree on attribute set $Y$; that is, $X$ functionally determines $Y$.

State Armstrong's three axioms for functional dependencies.

Reflexivity: if $Y \subseteq X$ then $X \to Y$. Augmentation: if $X \to Y$ then $XZ \to YZ$. Transitivity: if $X \to Y$ and $Y \to Z$ then $X \to Z$.

What condition must a relation satisfy to be in First Normal Form (1NF)?

Every attribute must contain only atomic (indivisible) single values; no multi-valued attributes, composite attributes, or nested/repeating groups are allowed.

What is the requirement for Second Normal Form (2NF)?

The relation must be in 1NF and have no partial dependency, i.e., no non-prime attribute may depend on a proper subset of any candidate key. Every non-prime attribute must be fully functionally dependent on the whole candidate key.

What is the requirement for Third Normal Form (3NF)?

The relation must be in 2NF and have no transitive dependency of non-prime attributes on candidate keys. For every FD $X \to Y$, either $X$ is a super key or $Y$ is a prime attribute.

How does BCNF differ from 3NF?

BCNF is stricter: for every non-trivial FD $X \to Y$, $X$ must be a super key (no prime-attribute exception). Every BCNF relation is in 3NF, but not vice versa. 3NF is always dependency-preserving and lossless; BCNF may not be dependency-preserving.

What is a partial functional dependency? Give an example.

A partial dependency occurs when a non-prime attribute depends on only part of a composite candidate key. Example: in $R(StudentID, CourseID, StudentName)$ with key $\{StudentID, CourseID\}$, $StudentID \to StudentName$ is partial. It violates 2NF.

What is a transitive functional dependency? Give an example.

A transitive dependency exists when $X \to Y$ and $Y \to Z$ with $Y$ not a candidate key, so $X \to Z$ indirectly. Example: $RollNo \to DeptID$ and $DeptID \to DeptName$ gives $RollNo \to DeptName$. It violates 3NF.

What two properties should a good relational decomposition satisfy?

1) Lossless-join (non-additive): the natural join of decomposed relations reconstructs exactly the original relation. 2) Dependency preservation: the union of FDs on the sub-relations implies all original FDs.

Compare heap (unordered) and sequential (ordered) file organization.

Heap file: records placed in insertion order; insertion is fast (O(1) append) but searching is linear O(n). Sequential file: records stored sorted on a key; supports binary search O(log n) and efficient range queries, but insertion/deletion is costly due to reordering.

What is hashing (hash) file organization and its main drawback?

Records are placed in buckets determined by a hash function on the key, giving near O(1) equality-search access. Drawbacks: poor performance for range queries and the need to handle bucket overflow (via chaining or rehashing).

Differentiate a primary (clustered) index from a secondary (non-clustered) index.

A clustered/primary index is built on the ordering key field, so the physical order of records matches the index; only one per table. A secondary index is on a non-ordering field, is dense, and does not match physical order; many are allowed.

What is the difference between a dense and a sparse index?

A dense index has one index entry for every search-key value (every record). A sparse index has entries for only some keys (typically one per data block); sparse indexes require ordered files.

What is a B-tree of order $m$?

A balanced multiway search tree where every node has at most $m$ children and at least $\lceil m/2 \rceil$ children (root at least 2). Keys and their data pointers are stored in both internal and leaf nodes, and all leaves are at the same level.

In a B-tree of order $m$, how many keys can a node hold and what is the minimum for a non-root node?

A node holds at most $m-1$ keys and at least $\lceil m/2 \rceil - 1$ keys (the root may have as few as 1 key).

What are the key structural differences between a B-tree and a B+ tree?

In a B+ tree, all actual data record pointers are stored only in leaf nodes; internal nodes hold only keys for routing (keys may be duplicated). Leaves are linked in a sorted linked list. In a B-tree, data pointers exist in all nodes and there is no leaf linkage.

Why are B+ trees preferred over B-trees for database indexing?

Internal nodes store only keys (no data), so they have a higher fan-out and shorter height, fewer disk I/Os. The linked leaf list makes sequential and range queries efficient, and every search traverses to a leaf giving uniform access cost.

In a B+ tree of order $p$ for internal nodes, how many tree pointers and keys does an internal node hold?

An internal node holds at most $p$ tree pointers and $p-1$ keys, with a minimum of $\lceil p/2 \rceil$ tree pointers (so $\lceil p/2 \rceil - 1$ keys); the root needs at least 2 pointers.

Define a database transaction and name its four ACID properties.

A transaction is a logical unit of work containing one or more operations executed as a single indivisible action. ACID: Atomicity (all or nothing), Consistency (preserves integrity constraints), Isolation (concurrent transactions don't interfere), Durability (committed changes persist).

Draw out the states in a transaction's state diagram.

Active -> Partially Committed (after final operation) -> Committed (changes made permanent), or Active/Partially Committed -> Failed -> Aborted (rolled back). From Aborted it may restart or be killed.

When is a schedule conflict-serializable, and how is it tested?

A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping non-conflicting (non-conflicting = different transactions, not both on same data item with at least one write) adjacent operations. It is tested by checking that the precedence (serialization) graph is acyclic.

List the three types of problems that arise from uncontrolled concurrent execution.

1) Lost update (write-write); 2) Dirty read / temporary update (reading uncommitted data, read of a write later rolled back); 3) Unrepeatable read and the incorrect summary / phantom problem.

What is Two-Phase Locking (2PL) and what does it guarantee?

2PL is a protocol where every transaction acquires all locks in a growing phase and releases locks only in a shrinking phase (no lock acquired after the first release). It guarantees conflict-serializability. Strict 2PL holds all exclusive locks until commit/abort, also ensuring recoverability and cascade-free schedules.

How does timestamp-ordering concurrency control decide whether to allow an operation?

Each transaction gets a unique timestamp $TS(T)$; each data item keeps read and write timestamps. An operation that would violate timestamp order (e.g., a write whose effect is already overwritten or read by a younger transaction) is rejected and the transaction is rolled back, ensuring serializability by timestamp order.

Differentiate recoverable, cascadeless, and strict schedules.

Recoverable: a transaction commits only after all transactions whose data it read have committed. Cascadeless (avoids cascading rollback): transactions read only committed data. Strict: no transaction reads or writes a data item until the transaction that last wrote it commits/aborts. Relationship: Strict $\subseteq$ Cascadeless $\subseteq$ Recoverable.