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

Normalization

Normalization is the process of organizing the attributes and relations of a relational database to reduce data redundancy and eliminate undesirable anomalies (insertion, update, and deletion anomalies). It decomposes larger "bad" relations into smaller well-structured relations based on functional dependencies and keys.

Why normalization is necessary

• Eliminates redundancy — the same data is not stored repeatedly, saving storage.
• Avoids update anomaly — a fact stored once need only be changed once.
• Avoids insertion anomaly — new data can be inserted without requiring unrelated data.
• Avoids deletion anomaly — deleting a row does not accidentally lose other facts.
• Ensures data consistency and integrity.

First Normal Form (1NF)

A relation is in 1NF if every attribute holds only atomic (indivisible) values — no repeating groups or multi-valued attributes.

Unnormalized:

In 1NF:

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any candidate key (i.e., every non-key attribute depends on the whole key, not part of it). Partial dependency arises only with composite keys.

Consider STUDENT_COURSE(StudID, Course, StudName) with key {StudID, Course}. Here StudName depends only on StudID — a partial dependency. Decompose:

• STUDENT(StudID, StudName)
• ENROLL(StudID, Course)

Third Normal Form (3NF)

A relation is in 3NF if it is in 2NF and there is no transitive dependency of a non-prime attribute on the key (every non-key attribute depends directly on the key, not via another non-key attribute).

Consider STUDENT(StudID, DeptID, DeptName) where StudID → DeptID and DeptID → DeptName, so StudID → DeptName is transitive. Decompose:

• STUDENT(StudID, DeptID)
• DEPT(DeptID, DeptName)

Formally, $X \rightarrow A$ holds for 3NF if $X$ is a superkey or $A$ is a prime attribute.

Conclusion

Progressively applying 1NF → 2NF → 3NF removes atomicity violations, partial dependencies, and transitive dependencies respectively, yielding a clean, anomaly-free, and consistent schema.

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$, $X$ is a superkey of $R$. BCNF is a stricter version of 3NF (sometimes called 3.5NF). A relation in BCNF is automatically in 3NF.

Difference between 3NF and BCNF

Thus every BCNF relation is in 3NF, but not every 3NF relation is in BCNF. The two differ only when a relation has multiple overlapping candidate keys.

Example decomposition into BCNF

Consider R(Student, Subject, Teacher) with the rules:

• A teacher teaches exactly one subject: Teacher → Subject.
• For each student–subject pair there is one teacher: {Student, Subject} → Teacher.

Candidate keys: {Student, Subject} and {Student, Teacher}. The attribute Subject is prime, so the FD Teacher → Subject satisfies 3NF (RHS is prime). But the determinant Teacher is not a superkey, so $R$ violates BCNF.

Decompose on Teacher → Subject:

• $R_1(\underline{Teacher}, Subject)$
• $R_2(\underline{Student, Teacher})$

Both relations are now in BCNF (in each, the only determinant is a candidate key). This removes the redundant repetition of the teacher–subject fact, though dependency preservation of {Student, Subject} → Teacher may be lost — illustrating BCNF's trade-off.

Transaction

A transaction is a logical unit of work that accesses and possibly updates the database through a sequence of read and write operations. It must be executed as a whole — either all of its operations complete successfully or none do. Example: a fund transfer that debits account A and credits account B.

ACID Properties

1. Atomicity — A transaction is all-or-nothing; if any operation fails, the whole transaction is rolled back so no partial effects remain. (Managed by the recovery/transaction manager.)
2. Consistency — A transaction takes the database from one valid (consistent) state to another, preserving all integrity constraints.
3. Isolation — Concurrently executing transactions do not interfere; the intermediate state of one is invisible to others. The result is as if transactions ran serially. (Managed by the concurrency-control manager.)
4. Durability — Once a transaction commits, its changes are permanent and survive system crashes (ensured via logs / stable storage).

States of a Transaction

• Active — the initial state; the transaction is executing its operations.
• Partially Committed — after the final operation has executed (changes may still be in buffers, not yet on disk).
• Committed — after successful completion; changes are permanently saved.
• Failed — when normal execution can no longer proceed (e.g., error, constraint violation).
• Aborted — after rollback; the database is restored to its state before the transaction began. It may then be restarted or killed.

State Diagram (described)

              +-----------+        +----------------------+        +-----------+
  begin --->  |  ACTIVE   | -----> | PARTIALLY COMMITTED  | -----> | COMMITTED |
              +-----------+        +----------------------+        +-----------+
                   |                        |
                   v                        v
              +-----------+            (write fails)
              |  FAILED   | <----------------+
              +-----------+
                   |
                   v
              +-----------+
              |  ABORTED  |  --> (restart -> Active) or (kill -> terminate)
              +-----------+

The transaction starts Active; after its last statement it becomes Partially Committed, then Committed on success. Any failure moves it to Failed, then Aborted after rollback, from where it may be restarted or terminated.

Weak Entity Set

A weak entity set is an entity set that does not have a primary key (sufficient attributes) of its own to uniquely identify its entities. Its existence depends on another entity set called the identifying (owner/strong) entity set, to which it is connected through an identifying relationship.

Key points:

• It is identified by combining its own partial key (discriminator) with the primary key of the owner entity.
• It has total participation in the identifying relationship (existence dependency).
• In an ER diagram, a weak entity is drawn with a double rectangle, the identifying relationship with a double diamond, and the partial key is underlined with a dashed line.

Example

Consider a LOAN entity and its PAYMENT instalments in a bank.

• PAYMENT(Payment_No, Date, Amount) cannot be uniquely identified by Payment_No alone, since different loans may both have payment number 1, 2, 3...
• PAYMENT therefore is a weak entity, dependent on the strong entity LOAN(Loan_No, Amount) via the identifying relationship loan-payment.
• Its partial key is Payment_No; its full identifier becomes the composite {Loan_No, Payment_No}.

Another classic example: DEPENDENT(Name) of an EMPLOYEE — identified by {EmpID, Name}.

View in SQL

A view is a virtual table derived from one or more base tables (or other views) by a stored SELECT query. It does not store data of its own (except a materialized view); instead, its rows are computed from the underlying tables whenever the view is referenced.

CREATE VIEW HighPaidEmp AS
SELECT EmpID, Name, Salary
FROM Employee
WHERE Salary > 50000;

It is then queried like a table: SELECT * FROM HighPaidEmp;

Advantages of Views

• Security — restricts access by exposing only selected rows/columns and hiding sensitive data of the base tables.
• Simplicity — complex joins and queries are encapsulated, so users query a simple view instead of writing complicated SQL.
• Data independence / abstraction — applications using a view are insulated from changes in the underlying table structure.
• Customized presentation — different users can see the data tailored to their needs.
• Consistency & reusability — a commonly used query is defined once and reused everywhere.

DELETE vs DROP vs TRUNCATE

Examples:

DELETE FROM Student WHERE Marks < 40;  -- removes matching rows only
TRUNCATE TABLE Student;                -- removes all rows, keeps the empty table
DROP TABLE Student;                    -- removes the table entirely

Summary: DELETE removes selected rows and is reversible; TRUNCATE quickly empties the whole table but keeps its structure and is not reversible; DROP deletes the whole table along with its definition.

Aggregate Functions in SQL

Aggregate functions take a collection (column) of values as input and return a single summary value. They are commonly used with the GROUP BY clause and filtered with HAVING. Except for COUNT(*), they ignore NULL values.

Examples

Using an Employee(EmpID, Dept, Salary) table:

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

-- Total and average salary
SELECT SUM(Salary) AS Total, AVG(Salary) AS Average FROM Employee;

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

-- Average salary per department (grouped)
SELECT Dept, AVG(Salary) AS AvgSal
FROM Employee
GROUP BY Dept
HAVING AVG(Salary) > 40000;

The last query groups rows by department, computes the average salary of each group, and keeps only groups whose average exceeds 40000.

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 or view — namely an INSERT, UPDATE, or DELETE. The user does not call it explicitly; it runs whenever the triggering event occurs.

Classification:

• Timing: BEFORE or AFTER the event.
• Granularity: FOR EACH ROW (row-level) or statement-level.
• Uses transition variables such as NEW (new row value) and OLD (old row value).

Uses: enforcing complex integrity constraints, maintaining audit trails/logs, automatically updating derived data, and validating data.

Example

Maintain an audit log whenever a salary is updated:

CREATE TRIGGER trg_salary_audit
AFTER UPDATE OF Salary ON Employee
FOR EACH ROW
BEGIN
  INSERT INTO Salary_Audit(EmpID, Old_Salary, New_Salary, Changed_On)
  VALUES (:OLD.EmpID, :OLD.Salary, :NEW.Salary, SYSDATE);
END;

Whenever an employee's salary is updated, this trigger fires automatically and records the old and new salary along with the timestamp into the Salary_Audit table — without any explicit call from the application.

Relational Algebra vs Relational Calculus

Both are formal query languages for the relational model; relational algebra forms the basis of query execution, while relational calculus is the basis for declarative languages like SQL. They are equivalent in expressive power.

Summary: Relational algebra tells the system the exact procedure to follow, whereas relational calculus only describes the properties of the desired result and lets the system decide how to compute it.

Lossless-Join Decomposition

When a relation $R$ is decomposed into relations $R_1$ and $R_2$, the decomposition is lossless (non-additive) if joining $R_1$ and $R_2$ back gives exactly the original relation, with no spurious (extra) tuples:

Condition (for binary decomposition): the decomposition of $R$ into $R_1$ and $R_2$ is lossless if their common attributes form a key of at least one of the relations, i.e. one of the following holds:

If this condition fails, the join produces extra tuples (a lossy decomposition) and information is effectively distorted. Lossless join is a mandatory requirement of any good decomposition.

Example: $R(A,B,C)$ with $A \rightarrow B$, decomposed into $R_1(A,B)$ and $R_2(A,C)$. Common attribute $A$ is the key of $R_1$, so the join is lossless.

Dependency-Preserving Decomposition

A decomposition of $R$ into $R_1, R_2, \dots, R_n$ is dependency preserving if the union of the functional dependencies enforceable on the individual relations is equivalent to the original set $F$ (has the same closure):

This ensures each FD can be checked on a single relation without performing a join, so constraints are enforced efficiently after decomposition.

Note: A 3NF decomposition can always be both lossless and dependency-preserving, whereas a BCNF decomposition is always lossless but may not be dependency-preserving.

Deadlock

A deadlock is a situation in which two or more transactions are waiting indefinitely for one another to release locks, so none of them can proceed. For example, transaction $T_1$ holds a lock on data item $A$ and waits for $B$, while $T_2$ holds a lock on $B$ and waits for $A$ — a circular wait.

A deadlock requires all four conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait.

Handling of Deadlocks

1. Deadlock Prevention

Design the locking protocol so that a deadlock can never form, e.g.:

• Wait-Die (non-preemptive): an older transaction waits for a younger one; a younger one requesting an item held by an older one is rolled back (dies).
• Wound-Wait (preemptive): an older transaction forces (wounds/rolls back) a younger holder; a younger one waits.
• Acquiring all locks at once, or ordering data items and locking in that order.

2. Deadlock Detection and Recovery

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

3. Deadlock Avoidance / Timeout

Use a timeout: if a transaction waits longer than a threshold, it is assumed to be deadlocked and is aborted and restarted.

Schedule

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

Serial Schedule

A serial schedule executes transactions one after another, without interleaving — all operations of one transaction finish before the next begins. A serial schedule is always consistent and correct, but it gives no concurrency, so resource utilization and throughput are poor.

Serializable Schedule

A serializable schedule is a concurrent (interleaved) schedule whose final effect on the database is equivalent to some serial schedule of the same transactions. It therefore preserves consistency while still allowing concurrency. Common notions are conflict serializability (testable via a precedence/serialization graph that must be acyclic) and view serializability.

Difference

In short: every serial schedule is serializable, but a serializable schedule allows interleaving as long as its result matches some serial execution.