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

Transaction

A transaction is a logical unit of work that accesses and possibly modifies the contents of a database. It is a sequence of one or more SQL operations (read/write) executed as a single, indivisible unit — either all of its operations are reflected in the database (commit), or none are (abort/rollback).

Example: transferring Rs. 500 from account A to account B involves two writes (A = A - 500, B = B + 500) that must succeed or fail together.

ACID Properties

• Atomicity — All operations of a transaction are treated as a single unit; either all complete successfully or none take effect. If the transaction fails midway (e.g. after debiting A but before crediting B), all changes are rolled back. Enforced by the transaction-management / recovery component.
• Consistency — A transaction takes the database from one consistent state to another, preserving all integrity constraints (e.g. total money before = total after). Enforced jointly by the application and integrity rules.
• Isolation — Concurrently executing transactions must not interfere; the intermediate state of one transaction must be invisible to others. The result must be equivalent to some serial execution. Enforced by the concurrency-control component.
• Durability — Once a transaction commits, its changes are permanent and survive subsequent system failures. Enforced by the recovery component (using logs and stable storage).

States of a Transaction

A transaction passes through the following states:

1. Active — the initial state; the transaction stays here while it is executing its read/write operations.
2. Partially Committed — entered after the final statement has executed, but changes may still be in main-memory buffers (not yet on disk).
3. Failed — entered when normal execution can no longer proceed (e.g. hardware/logic error, constraint violation).
4. Aborted — entered after the transaction has been rolled back and the database restored to its state prior to the transaction's start. The transaction may then be restarted or killed.
5. Committed — entered after successful completion when all changes are permanently recorded.

State Diagram (described)

        begin
  --------------->  [ Active ]
                       |   \
          last stmt    |    \ error
                       v     v
          [ Partially Committed ]   [ Failed ]
                       |                 |
               commit  |                 | rollback
                       v                 v
               [ Committed ]        [ Aborted ]

• Active → Partially Committed: after the last operation executes.
• Active → Failed or Partially Committed → Failed: when an error occurs.
• Partially Committed → Committed: when changes are written to stable storage.
• Failed → Aborted: after rollback. From Aborted, the transaction is either restarted or terminated.

Concurrency Control

Concurrency control is the management of simultaneous execution of multiple transactions on a shared database so that the result is correct (i.e. preserves the isolation and consistency of ACID). Without it, interleaved execution can cause anomalies such as lost update, dirty read, and unrepeatable read. The goal is to ensure that any concurrent (interleaved) schedule is equivalent to some serial schedule — i.e. that it is serializable.

Timestamp-Based Protocol

Each transaction $T_i$ is assigned a unique timestamp $TS(T_i)$ at start time (an older transaction has a smaller timestamp). Every data item $Q$ keeps two values:

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

Read rule — $T_i$ issues read(Q):

• If $TS(T_i) < W\text{-}timestamp(Q)$: $T_i$ needs an already-overwritten value → reject and roll back $T_i$.
• Else: execute the read and set $R\text{-}timestamp(Q) = \max(R\text{-}timestamp(Q), TS(T_i))$.

Write rule — $T_i$ issues write(Q):

• If $TS(T_i) < R\text{-}timestamp(Q)$: a newer transaction already read the value $T_i$ is producing → reject and roll back $T_i$.
• If $TS(T_i) < W\text{-}timestamp(Q)$: $T_i$ is writing an obsolete value → reject (or ignore, by Thomas' write rule).
• Else: execute the write and set $W\text{-}timestamp(Q) = TS(T_i)$.

The protocol guarantees conflict serializability (in timestamp order) and is deadlock-free, but rolled-back transactions must restart with a new timestamp, and it can suffer from starvation.

Two-Phase Locking (2PL) Protocol

Transactions acquire shared (S) locks for reading and exclusive (X) locks for writing. Every transaction follows two phases:

1. Growing (expanding) phase — the transaction may acquire locks but may not release any lock.
2. Shrinking (contracting) phase — the transaction may release locks but may not acquire any new lock.

The point at which it holds the maximum number of locks is the lock point. 2PL guarantees conflict serializability (transactions are serializable in order of their lock points).

Variants:

• Strict 2PL — all exclusive locks are held until commit/abort; prevents cascading rollbacks.
• Rigorous 2PL — all locks (shared and exclusive) are held until commit/abort.

Limitation: basic 2PL is not deadlock-free — two transactions can each hold a lock the other needs, causing a deadlock that must be detected/resolved separately.

Relational Algebra

Relational algebra is a procedural query language that takes one or two relations (tables) as input and produces a new relation as output. Because the result is itself a relation, operations can be composed. It forms the theoretical basis for SQL query processing and optimization.

Assume two relations:

Student(RollNo, Name, Dept) and Dept(Dept, HOD).

Fundamental Operations

1. Selection ($\sigma$)

Selects rows (tuples) that satisfy a given predicate.

$$\sigma_{Dept = 'CSIT'}(Student)$$

Returns all students whose department is CSIT.

2. Projection ($\pi$)

Selects specified columns and removes duplicate rows.

$$\pi_{Name,\ Dept}(Student)$$

Returns only the Name and Dept columns.

3. Union ($\cup$)

Returns all tuples appearing in either relation; the two relations must be union-compatible (same number of attributes and matching domains). Duplicates are removed.

$$\pi_{Name}(\sigma_{Dept='CSIT'}(Student)) \cup \pi_{Name}(\sigma_{Dept='CSE'}(Student))$$

Names of students from CSIT or CSE.

4. Set Difference ($-$)

Returns tuples that are in the first relation but not in the second (relations must be union-compatible).

$$\pi_{Dept}(Dept) - \pi_{Dept}(Student)$$

Departments that have no students.

5. Cartesian Product ($\times$)

Combines every tuple of the first relation with every tuple of the second. If $Student$ has $m$ rows and $Dept$ has $n$ rows, the result has $m \times n$ rows with all attributes of both.

$$Student \times Dept$$

6. Join ($\bowtie$)

A Cartesian product followed by a selection on matching attributes. A natural join combines tuples having equal values on common attributes and keeps only one copy of those attributes.

$$Student \bowtie Dept$$

Pairs each student with the row of his/her department (matching on Dept), e.g. attaching the HOD's name to each student. A theta-join $R \bowtie_{\theta} S$ uses an arbitrary condition $\theta$.

Note: Selection, projection, union, set difference, Cartesian product, rename, and set union are the six fundamental operations; join, intersection, and division are derived from them.

Trigger

A trigger is a special kind of stored procedure that is automatically executed (fired) by the DBMS in response to a specified event on a table — an INSERT, UPDATE, or DELETE. Unlike ordinary procedures, a trigger is not called explicitly; the database invokes it whenever the triggering event occurs.

Components: an event (the DML operation), a timing (BEFORE or AFTER), and an action (the SQL body). Triggers are used to enforce business rules, maintain audit logs, and preserve referential integrity automatically.

Example

Automatically log every salary change in an Employee table into an Audit table:

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

Here :OLD and :NEW refer to the row values before and after the update. Whenever a salary is updated, the trigger fires automatically and records the change — no application code is required.

Relational Algebra vs Relational Calculus

Both are formal query languages of equal expressive power (relationally complete), but they differ in how a query is expressed.

Example — "names of CSIT students":

• Algebra: $\pi_{Name}(\sigma_{Dept='CSIT'}(Student))$
• Calculus (TRC): $\{ t.Name \mid t \in Student \land t.Dept = 'CSIT' \}$

Both produce the same result; algebra states the operations, calculus states the condition.

When a relation is decomposed into smaller relations during normalization, two properties are desirable.

Lossless-Join Decomposition

A decomposition of relation $R$ into $R_1$ and $R_2$ is lossless (non-additive) if joining them back reproduces exactly the original relation — no spurious (extra) tuples and no lost tuples:

$$R_1 \bowtie R_2 = R$$

Condition: the decomposition is lossless if the common attributes form a superkey of at least one of the sub-relations, i.e.

$$(R_1 \cap R_2) \rightarrow R_1 \quad \text{or} \quad (R_1 \cap R_2) \rightarrow R_2$$

A lossy decomposition is unacceptable because it changes the information content of the database.

Dependency-Preserving Decomposition

A decomposition is dependency-preserving if every functional dependency in the original relation can be checked without performing a join — i.e. the union of the FDs enforceable on the individual sub-relations is equivalent (has the same closure) to the original set $F$:

$$(F_1 \cup F_2 \cup \dots \cup F_n)^+ = F^+$$

This lets the DBMS enforce all constraints locally and efficiently.

Summary: Lossless join preserves the data (no information loss); dependency preservation preserves the constraints (FDs remain enforceable cheaply). A good decomposition (e.g. to 3NF) achieves both; BCNF always guarantees losslessness but may not preserve dependencies.

Deadlock

A deadlock is a situation in which two or more transactions are each waiting for a data item locked by another, so that none of them can proceed — they wait indefinitely in a circular chain.

Example: $T_1$ holds a lock on $A$ and requests $B$, while $T_2$ holds a lock on $B$ and requests $A$. Each waits for the other forever.

Handling Deadlocks

1. Deadlock Prevention

Ensure the system never enters a deadlock state, using timestamp-based schemes:

• Wait-Die (non-preemptive): an older transaction may wait for a younger one; a younger transaction requesting a resource held by an older one is rolled back (dies).
• Wound-Wait (preemptive): an older transaction requesting a resource held by a younger one forces the younger to abort (wounds it); a younger one simply waits.
• Other schemes: acquire all locks at once, or impose a fixed ordering on resources.

2. Deadlock Detection and Recovery

Allow deadlocks to occur, then detect them using a wait-for graph (nodes = transactions, edge $T_i \rightarrow T_j$ means $T_i$ waits for $T_j$). A cycle in this graph indicates a deadlock. The system then recovers by selecting a victim transaction (usually the one with least work done / lowest cost) and rolling it back to break the cycle, restarting it later.

3. Timeout

A simpler scheme: if a transaction waits longer than a preset time limit, it is assumed deadlocked and is rolled back.

Necessary conditions for deadlock are mutual exclusion, hold-and-wait, no preemption, and circular wait; breaking any one prevents deadlock.

Schedule

A schedule is a chronological sequence of operations (read, write, commit, abort) from one or more transactions, showing the order in which their instructions are executed by the system. It preserves the relative order of operations within each individual transaction.

Serial vs Serializable Schedule

A schedule is serializable if its outcome is equivalent to that of some serial schedule, guaranteeing database consistency despite concurrency. The two common forms are:

• Conflict serializable — can be transformed into a serial schedule by swapping non-conflicting adjacent operations (tested by an acyclic precedence graph).
• View serializable — produces the same reads-from and final writes as a serial schedule.

Thus a serial schedule is trivially serializable, but a serializable schedule allows concurrency while still behaving like a serial one.

Stored Procedure

A stored procedure is a named, precompiled collection of one or more SQL statements (together with procedural logic such as variables, conditionals, and loops) that is stored in the database and executed on the server when called by name. It is created once with CREATE PROCEDURE and invoked with CALL / EXEC, optionally accepting input (IN), output (OUT), and input-output (INOUT) parameters.

Example

CREATE PROCEDURE GetStudentCount(IN dept_name VARCHAR(20), OUT cnt INT)
BEGIN
  SELECT COUNT(*) INTO cnt
  FROM Student
  WHERE Dept = dept_name;
END;

-- call
CALL GetStudentCount('CSIT', @result);

Advantages

• Performance — precompiled and cached, so repeated calls avoid re-parsing; reduces network traffic (one call instead of many statements).
• Reusability & maintainability — business logic is written once and shared by many applications.
• Security — users can be granted rights to execute a procedure without direct access to the underlying tables.
• Consistency — centralizes and standardizes data-access logic.

Unlike a trigger, a stored procedure must be explicitly called; unlike a function, it need not return a single value and can perform DML/transaction-control operations.

Data Redundancy

Data redundancy is the unnecessary repetition of the same data in multiple places in a database. It commonly arises from poorly designed (un-normalized) tables that store related data together. Redundancy wastes storage and, more seriously, causes update anomalies:

• Insertion anomaly — cannot add some data without also adding unrelated data (e.g. cannot store a new department until a student is enrolled in it).
• Deletion anomaly — deleting a row unintentionally removes other useful facts.
• Update anomaly — a value duplicated in many rows must be changed in every copy; missing one leaves the database inconsistent.

How Normalization Reduces It

Normalization is the process of decomposing a large, redundant relation into smaller, well-structured relations based on functional dependencies and applying a series of normal forms (1NF, 2NF, 3NF, BCNF):

• 1NF removes repeating groups/multivalued attributes (atomic values only).
• 2NF removes partial dependencies (non-key attributes depending on part of a composite key).
• 3NF / BCNF removes transitive dependencies (non-key attribute depending on another non-key attribute).

By splitting data so that each fact is stored exactly once (each non-key attribute depends on "the key, the whole key, and nothing but the key"), normalization eliminates duplication and the associated anomalies, while a lossless decomposition guarantees the original data can be reconstructed by joins.

Multivalued Dependency (MVD)

A multivalued dependency, written $X \twoheadrightarrow Y$ ("$X$ multidetermines $Y$"), holds in relation $R$ when, for a given value of $X$, there is a set of values of $Y$ that is independent of the remaining attributes $Z = R - X - Y$. In other words, $Y$ and $Z$ are independent of each other but both depend on $X$.

Formally, $X \twoheadrightarrow Y$ holds if whenever two tuples agree on $X$, swapping their $Y$ values produces tuples that also exist in $R$.

Example: relation Course(course, instructor, textbook), where a course can have several instructors and several textbooks independently. Then:

$$course \twoheadrightarrow instructor \quad \text{and} \quad course \twoheadrightarrow textbook$$

This forces every (instructor, textbook) combination to be stored, creating redundancy.

Fourth Normal Form (4NF)

A relation is in 4NF if it is already in BCNF and contains no non-trivial multivalued dependencies. Precisely, for every non-trivial MVD $X \twoheadrightarrow Y$, $X$ must be a superkey of $R$.

To achieve 4NF, the table is decomposed to separate the independent multivalued facts — e.g. split Course into Course_Instructor(course, instructor) and Course_Textbook(course, textbook). This removes the redundancy caused by the MVD while remaining a lossless decomposition.

Join

A join is an operation that combines rows from two (or more) relations based on a related (matching) column between them, producing a single result set. It is used to retrieve data spread across multiple tables linked by primary-key / foreign-key relationships.

Consider Employee(emp_id, name, dept_id) and Department(dept_id, dept_name).

Inner Join

An inner join returns only the rows that have matching values in both tables; non-matching rows from either side are excluded.

SELECT e.name, d.dept_name
FROM Employee e
INNER JOIN Department d ON e.dept_id = d.dept_id;

Employees without a valid department, and departments with no employees, do not appear.

Outer Join

An outer join returns matching rows plus the unmatched rows from one or both tables, filling missing columns with NULL. Three types:

• LEFT OUTER JOIN — all rows from the left table; unmatched right columns are NULL (e.g. every employee, even those with no department).

  SELECT e.name, d.dept_name
  FROM Employee e
  LEFT OUTER JOIN Department d ON e.dept_id = d.dept_id;
  

• RIGHT OUTER JOIN — all rows from the right table; unmatched left columns are NULL (e.g. every department, even empty ones).
• FULL OUTER JOIN — all rows from both tables, with NULLs wherever there is no match.

Summary: an inner join keeps only matches; an outer join also preserves the unmatched rows from the left, right, or both sides.