BSc CSIT (TU) Science Database Management System (BSc CSIT, CSC260) Question Paper 2081 Nepal

Boyce-Codd Normal Form (BCNF)

A relation $R$ is in BCNF if, for every non-trivial functional dependency $X \rightarrow Y$ that holds on $R$, the determinant $X$ is a superkey of $R$. In other words, the left-hand side of every FD must be able to uniquely identify a tuple. BCNF is a stricter version of 3NF that removes all anomalies arising from functional dependencies.

BCNF vs 3NF

BCNF differs from 3NF only when a non-prime determinant exists, or when candidate keys overlap.

Example: Decomposing into BCNF

Consider the relation:

with the FDs:

• $\{\text{Student, Subject}\} \rightarrow \text{Teacher}$
• $\text{Teacher} \rightarrow \text{Subject}$ (each teacher teaches exactly one subject)

Candidate keys: $\{\text{Student, Subject}\}$ and $\{\text{Student, Teacher}\}$. Prime attributes are Student, Subject, Teacher.

Why it is in 3NF but not BCNF: For the FD $\text{Teacher} \rightarrow \text{Subject}$, the determinant Teacher is not a superkey, so BCNF is violated. It is still in 3NF because Subject is a prime attribute.

BCNF decomposition — split on the violating FD $\text{Teacher} \rightarrow \text{Subject}$:

Now:

• In $R_1$, the only FD is $\text{Teacher} \rightarrow \text{Subject}$ and Teacher is the key → BCNF.
• In $R_2$, the key is $\{\text{Student, Teacher}\}$ and there are no other FDs → BCNF.

The join $R_1 \bowtie R_2$ on Teacher reconstructs $R$ without loss (lossless), though the FD $\{\text{Student, Subject}\} \rightarrow \text{Teacher}$ is no longer enforced by a single relation, illustrating that BCNF may sacrifice dependency preservation.

Transaction

A transaction is a logical unit of work that consists of one or more database operations (read/write) executed as a single, indivisible action. It takes the database from one consistent state to another. Example: transferring Rs. 500 from account A to account B (debit A, credit B) is one transaction.

ACID Properties

The four ACID properties guarantee reliable transaction processing:

• A — Atomicity: A transaction is all-or-nothing. Either all its operations are completed and committed, or none are; partial effects are rolled back. (Managed by the recovery/transaction manager.)
• C — Consistency: A transaction transforms the database from one valid (consistent) state to another, preserving all integrity constraints.
• I — Isolation: Concurrently executing transactions do not interfere; intermediate states of one are invisible to others. The result is equivalent to some serial execution.
• D — Durability: Once a transaction commits, its changes are permanent and survive subsequent system failures (ensured via logs/non-volatile storage).

States of a Transaction

A transaction passes through the following states:

1. Active — the initial state; the transaction is executing its read/write operations.
2. Partially Committed — the final statement has executed, but changes may still be in buffers (not yet written to disk).
3. Committed — the transaction completed successfully and all changes are permanently saved; durability is guaranteed.
4. Failed — normal execution can no longer proceed (e.g., constraint violation, system error).
5. Aborted — the transaction has been rolled back and the database is restored to its state prior to the transaction. It may then be restarted or killed.

State Diagram (described)

           +---------+
  begin -->| Active  |
           +----+----+
        ok |    | error
           v    v
  +------------------+   +--------+
  | Partially        |   | Failed |
  | Committed        |   +---+----+
  +---------+--------+       |
            |                v
            v            +---------+
      +-----------+      | Aborted |
      | Committed |      +---------+
      +-----------+      (restart / kill)

Transitions: Active → Partially Committed → Committed (success path); Active → Failed → Aborted and Partially Committed → Failed → Aborted (failure path). From Aborted a transaction may be restarted (back to Active) or terminated.

Concurrency Control

Concurrency control is the mechanism by which a DBMS manages the simultaneous execution of multiple transactions so that the database remains consistent and the result is equivalent to some serial execution (serializability). Without it, concurrent access leads to problems such as the lost update, dirty read, and unrepeatable read anomalies.

Timestamp-Based Protocol

Each transaction $T_i$ is assigned a unique timestamp $TS(T_i)$ when it starts; older transactions get smaller timestamps. Each data item $X$ keeps two values:

• $W\text{-}TS(X)$ — largest timestamp of a transaction that successfully wrote $X$.
• $R\text{-}TS(X)$ — largest timestamp of a transaction that successfully read $X$.

The order of conflicting operations is forced to follow timestamp order:

Read $X$ by $T_i$:

• If $TS(T_i) < W\text{-}TS(X)$ → $T_i$ is too old to read a value already overwritten → abort and roll back $T_i$.
• Otherwise execute the read and set $R\text{-}TS(X) = \max(R\text{-}TS(X), TS(T_i))$.

Write $X$ by $T_i$:

• If $TS(T_i) < R\text{-}TS(X)$ or $TS(T_i) < W\text{-}TS(X)$ → abort $T_i$.
• Otherwise execute the write and set $W\text{-}TS(X) = TS(T_i)$.

This protocol guarantees conflict serializability and is deadlock-free (no waiting — conflicts cause rollback), but may cause cascading rollbacks/starvation.

Two-Phase Locking (2PL) Protocol

2PL uses shared (S) locks for reading and exclusive (X) locks for writing. Every transaction acquires and releases locks in two distinct phases:

1. Growing phase: the transaction may acquire locks but cannot release any.
2. Shrinking phase: the transaction may release locks but cannot acquire any new ones.

The single point at which the last lock is acquired is the lock point. 2PL guarantees conflict serializability of schedules.

Variants:

• Strict 2PL: all exclusive locks are held until commit/abort → prevents cascading rollbacks.
• Rigorous 2PL: all locks (S and X) held until commit/abort.

Limitation: Basic 2PL can lead to deadlocks (two transactions each waiting for a lock held by the other), which must be handled by detection or prevention.

DELETE vs DROP vs TRUNCATE

Examples:

DELETE FROM Student WHERE id = 5;  -- removes one row, can ROLLBACK
TRUNCATE TABLE Student;            -- removes all rows, keeps table
DROP TABLE Student;               -- removes table and its definition

Summary: DELETE selectively removes rows and is recoverable; TRUNCATE quickly empties a table but keeps its structure; DROP deletes the table object completely.

Aggregate Functions in SQL

Aggregate functions perform a calculation on a set (group) of values and return a single summary value. They are commonly used with the GROUP BY clause and filtered with HAVING. They ignore NULL values (except COUNT(*)).

Examples (table Employee(empno, name, dept, salary)):

-- Total number of employees
SELECT COUNT(*) FROM Employee;

-- Total and average salary
SELECT SUM(salary) AS total, AVG(salary) AS avg_sal FROM Employee;

-- Highest and lowest salary
SELECT MAX(salary), MIN(salary) FROM Employee;

-- Average salary per department, only depts averaging above 50000
SELECT dept, AVG(salary) AS avg_sal
FROM Employee
GROUP BY dept
HAVING AVG(salary) > 50000;

Here GROUP BY dept partitions rows by department and AVG(salary) is computed per group, while HAVING filters the aggregated results.

Trigger

A trigger is a special stored procedure that is automatically executed (fired) by the DBMS in response to a specified event (INSERT, UPDATE, or DELETE) on a table or view. Triggers are used to enforce business rules, maintain integrity constraints, audit changes, and automatically update related data.

Classification:

• By timing: BEFORE or AFTER the triggering event.
• By granularity: row-level (FOR EACH ROW) or statement-level.
• Pseudo-records OLD (existing values) and NEW (new values) reference the affected row.

Example (audit on salary change):

CREATE TRIGGER salary_audit
AFTER UPDATE OF salary ON Employee
FOR EACH ROW
BEGIN
  INSERT INTO Salary_Log(empno, old_sal, new_sal, changed_on)
  VALUES (:OLD.empno, :OLD.salary, :NEW.salary, SYSDATE);
END;

Whenever an employee's salary is updated, this trigger fires automatically and records the old value, new value, and timestamp in Salary_Log — without any explicit call from the application.

Relational Algebra vs Relational Calculus

Both are formal query languages for the relational model and are equivalent in expressive power, but they differ in approach.

Example — "names of students in the CS department":

• Algebra (procedural): $\pi_{name}(\sigma_{dept='CS'}(Student))$
• Tuple calculus (declarative): $\{t.name \mid t \in Student \land t.dept = 'CS'\}$

By Codd's theorem, relational algebra and (safe) relational calculus are equivalent in expressive power.

Lossless Join Decomposition

A decomposition of relation $R$ into $R_1$ and $R_2$ is a lossless-join (non-additive) decomposition if joining the decomposed relations reconstructs exactly the original relation — no spurious (extra) tuples are introduced and none are lost:

Condition (for binary decomposition): the decomposition is lossless if the common attributes form a key of at least one of the sub-relations, i.e. one of the following holds:

Losslessness is essential — without it, decomposition would corrupt the data.

Dependency-Preserving Decomposition

A decomposition is dependency-preserving if the set of functional dependencies enforceable on the individual sub-relations is equivalent to (i.e. can derive the closure of) the original set $F$:

This means every FD of the original relation can be checked on a single decomposed relation without performing a join, so constraints are efficiently enforced.

Key Point

• Lossless join is mandatory and is always achievable (e.g., BCNF).
• Dependency preservation is desirable but is not always achievable in BCNF; 3NF, however, guarantees both lossless join and dependency preservation.

Deadlock

A deadlock is a situation in which two or more transactions are each waiting indefinitely for a data item that is locked by another transaction in the set, so none can proceed. For example, $T_1$ holds a lock on $A$ and waits for $B$, while $T_2$ holds a lock on $B$ and waits for $A$ — a circular wait.

The four necessary conditions are mutual exclusion, hold-and-wait, no preemption, and circular wait.

Handling Deadlocks

1. Deadlock Prevention

Design the locking scheme so a deadlock can never occur, typically using transaction timestamps:

• Wait-Die (non-preemptive): an older transaction waits for a younger one; a younger one requesting a resource held by an older one is rolled back ("dies").
• Wound-Wait (preemptive): an older transaction forces ("wounds") a younger holder to roll back; a younger one waits for an older holder.

2. Deadlock Detection and Recovery

Allow deadlocks to occur, then detect and resolve them:

• Maintain a wait-for graph (nodes = transactions, edge $T_i \rightarrow T_j$ means $T_i$ waits for $T_j$).
• A cycle in the graph indicates a deadlock.
• Recovery: select a victim transaction (usually the one with least work done or fewest locks) and roll it back to break the cycle.

3. Timeout-Based

If a transaction waits longer than a preset time limit, assume a deadlock and abort it. Simple but may abort transactions unnecessarily.

Schedule

A schedule is a chronological (time-ordered) sequence of the operations (read, write, commit, abort) of two or more concurrent transactions, preserving the relative order of operations within each individual transaction. It shows how the operations of the transactions are interleaved during execution.

Serial vs Serializable Schedule

Key idea: A serializable schedule is the goal of concurrency control — it permits the performance benefits of interleaved execution while guaranteeing the same correctness as if the transactions had run serially. For example, an interleaved schedule of $T_1$ and $T_2$ is serializable if its result equals either the serial order $T_1 \rightarrow T_2$ or $T_2 \rightarrow T_1$.

Stored Procedure

A stored procedure is a named, precompiled collection of SQL statements (and optional procedural logic such as variables, loops, and conditionals) stored in the database and executed on the server by calling its name. It is created with CREATE PROCEDURE and invoked with CALL or EXEC.

Key characteristics:

• Accepts input/output parameters.
• Precompiled and stored, so repeated execution is faster (no re-parsing).
• Encapsulates business logic on the server, promoting reusability and modularity.
• Improves security (users can be granted execute rights without direct table access) and reduces network traffic (one call instead of many statements).

Example:

CREATE PROCEDURE GetSalary(IN emp_id INT, OUT sal DECIMAL(10,2))
BEGIN
  SELECT salary INTO sal FROM Employee WHERE empno = emp_id;
END;

-- Call it
CALL GetSalary(101, @result);

Advantages: better performance, code reuse, centralized logic, enhanced security, and reduced network load. Disadvantage: logic becomes database-specific and harder to port/version-control.

Data Redundancy

Data redundancy is the unnecessary repetition of the same data in multiple places within a database. It commonly arises when related data is stored together in a single un-normalized table. Redundancy wastes storage and, more importantly, causes update anomalies:

• Insertion anomaly: cannot insert some data without other (possibly unknown) data.
• Deletion anomaly: deleting one fact unintentionally removes another.
• Update anomaly: a value repeated in many rows must be changed everywhere, risking inconsistency if some copies are missed.

Example: storing the department name and department location in every employee row repeats the location for each employee of that department.

How Normalization Reduces Redundancy

Normalization is the process of decomposing relations based on functional dependencies into smaller, well-structured relations to eliminate redundancy and anomalies, progressing through normal forms (1NF → 2NF → 3NF → BCNF):

• 1NF removes repeating groups / multi-valued attributes (atomic values).
• 2NF removes partial dependencies (non-key attributes depending on part of a composite key).
• 3NF removes transitive dependencies (non-key attributes depending on other non-key attributes).
• BCNF ensures every determinant is a superkey.

By separating each independent fact into its own table and linking tables with foreign keys, each piece of data is stored only once. This eliminates redundant copies, prevents update/insert/delete anomalies, and keeps the database consistent.