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

Database Recovery

Recovery is the process of restoring a database to a correct (consistent) state after a failure (system crash, transaction failure, or media failure), ensuring the atomicity and durability of transactions. The recovery manager uses a log (an append-only file written to stable storage) that records every update before it is applied.

Log-Based Recovery

For every write the log stores a record of the form:

meaning transaction $T_i$ changed data item $X$ from old value $V_{old}$ to new value $V_{new}$. Other records are $\langle T_i\ \text{start}\rangle$, $\langle T_i\ \text{commit}\rangle$ and $\langle T_i\ \text{abort}\rangle$. The Write-Ahead Logging (WAL) rule requires the log record to reach stable storage before the corresponding data block.

Deferred Database Modification

• Updates are not written to the database until the transaction reaches its commit point; they are only recorded in the log.
• On failure, only redo is needed (no undo), because no uncommitted change ever reached the database.
• Recovery: redo(T) for every $T$ that has both start and commit in the log; ignore the rest.

Immediate Database Modification

• Updates are written to the database while the transaction is still active (before commit).
• The log must store both old and new values, so recovery needs both undo and redo.
• Recovery: undo(T) for transactions with start but no commit; redo(T) for transactions with start and commit.

Checkpoints

Without checkpoints, recovery would have to scan the entire log. A checkpoint is a point at which:

1. All log records in main memory are flushed to stable storage.
2. All modified buffer blocks are written to disk.
3. A $\langle \text{checkpoint } L\rangle$ record (listing active transactions) is written.

During recovery the log is scanned backwards to the most recent checkpoint: transactions that committed before the checkpoint are already safe and can be skipped, drastically reducing recovery time.

Summary: WAL + log records enable redo/undo; deferred modification needs only redo, immediate modification needs undo + redo, and checkpoints limit how much of the log must be processed.

Indexing in Databases

An index is an auxiliary data structure (a file of $\langle \text{search-key},\ \text{pointer}\rangle$ entries) built on one or more attributes to speed up record retrieval, avoiding a full linear scan. The attribute on which the index is built is the search key. An index trades extra storage and update cost for faster queries.

Ordered (Single-Level) Index Types

• A primary index orders the data file on a key attribute; only one is possible because a file can be physically sorted on only one field.
• A clustering index is like a primary index but the ordering field is not a candidate key, so several records share an index entry.
• A secondary index is defined on a field that does not determine the physical order, so it must contain an entry for every record (dense). Multiple secondary indexes can exist on one table.

Structure of a B+ Tree Index

A B+ tree is a balanced, multi-level, dynamic index that keeps performance stable under insertions/deletions. For order $n$:

• Internal (index) nodes hold up to $n-1$ search-key values and $n$ child pointers; they only guide the search.
• Leaf nodes hold the actual search keys together with record/block pointers, and are linked in a doubly linked list for efficient range and sequential scans.
• All leaves are at the same level (perfectly balanced); every node except the root is at least half full.
• Search, insert and delete all take $O(\log_{\lceil n/2\rceil} N)$ I/O.

Key advantages: all data pointers reside in the leaves (uniform access cost), the linked leaf list makes range queries efficient, and the tree self-balances so query cost stays predictable as the database grows.

Functional Dependency (FD)

A functional dependency $X \rightarrow Y$ on a relation $R$ means that whenever two tuples agree on the attributes in $X$, they must also agree on the attributes in $Y$. $X$ is the determinant; $Y$ is functionally determined by $X$. Example: in Student(RollNo, Name, Address), $\text{RollNo} \rightarrow \text{Name},\ \text{Address}$. FDs express integrity constraints and are the basis of normalization.

Armstrong's Axioms (Inference Rules)

The three primary (sound and complete) rules:

1. Reflexivity: if $Y \subseteq X$ then $X \rightarrow Y$.
2. Augmentation: if $X \rightarrow Y$ then $XZ \rightarrow YZ$.
3. Transitivity: if $X \rightarrow Y$ and $Y \rightarrow Z$ then $X \rightarrow Z$.

Derived (secondary) rules: Union ($X\rightarrow Y,\ X\rightarrow Z \Rightarrow X\rightarrow YZ$), Decomposition ($X\rightarrow YZ \Rightarrow X\rightarrow Y$), and Pseudotransitivity ($X\rightarrow Y,\ WY\rightarrow Z \Rightarrow WX\rightarrow Z$).

Computing the Closure of an Attribute Set

The closure $X^{+}$ is the set of all attributes functionally determined by $X$ under a set of FDs $F$.

Algorithm Closure(X, F):
    result := X
    repeat
        for each FD  A -> B  in F:
            if A ⊆ result then
                result := result ∪ B
    until result does not change
    return result

Example

Let $R(A,B,C,D,E)$ with

Compute $\{A,D\}^{+}$:

1. Start: $\{A, D\}$.
2. $A \rightarrow B$ applies ⇒ add $B$ → $\{A, B, D\}$.
3. $B \rightarrow C$ applies ⇒ add $C$ → $\{A, B, C, D\}$.
4. $CD \rightarrow E$ applies (both $C, D$ present) ⇒ add $E$ → $\{A, B, C, D, E\}$.
5. No new attribute ⇒ stop.

Result: $\{A,D\}^{+} = \{A,B,C,D,E\}$. Since this equals all attributes of $R$, $AD$ is a candidate key. Closures are used to test key candidates and to check whether an FD $X \rightarrow Y$ holds (true iff $Y \subseteq X^{+}$).

Different categories of database users interact with a DBMS in different ways:

• Database Administrator (DBA): central control of the database; grants/revokes access, defines schema and storage structure, handles backup, recovery, and performance tuning.
• Database Designers: identify the data and relationships to be stored and design the schema (conceptual/logical/physical).
• Naive / End Users: interact through ready-made application programs or menus (e.g., a bank teller, ticket clerk) without knowing SQL.
• Sophisticated Users: analysts, scientists, and engineers who write their own ad-hoc queries (SQL, query tools) to meet complex needs.
• Application Programmers: write the application programs (in host languages with embedded SQL) used by naive users.
• Specialized / Standalone Users: maintain complex applications such as CAD, knowledge-base, or expert systems that do not fit the traditional data-processing model.

Keys in the relational model:

• Candidate Key: a minimal set of attributes that uniquely identifies each tuple in a relation. A relation can have several candidate keys, and no proper subset of a candidate key is itself unique. Example in Student(RollNo, RegNo, Name): both RollNo and RegNo are candidate keys.

• Primary Key: the one candidate key chosen by the designer to be the principal identifier of the relation. It cannot be NULL and must be unique (entity integrity). Example: RollNo chosen as the primary key.

• Foreign Key: an attribute (or set) in one relation that references the primary key of another (or the same) relation, enforcing referential integrity. It may be NULL and may repeat. Example: DeptID in Student referencing DeptID in Department.

Weak Entity Set

A weak entity set is an entity set that does not have a sufficient attribute of its own to form a primary key; its existence depends on another (strong/owner) entity set through an identifying (or supporting) relationship.

Key points:

• It has a partial key (discriminator) — attributes that distinguish weak entities belonging to the same owner entity.
• Its full primary key = primary key of the owner entity + its own partial key.
• It participates in the identifying relationship with total participation.
• In an ER diagram, the 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 Payment entity for a Loan. A payment is identified only by a payment_number which restarts from 1 for each loan, so payment_number alone is not unique across all payments.

• Strong entity: Loan(loan_number, amount)
• Weak entity: Payment(payment_number, date, amount) — payment_number is the partial key.
• Identifying relationship: Loan–Payment.
• Primary key of Payment = {loan_number, payment_number}.

Thus a Payment cannot exist without the Loan that owns it.

View in SQL

A view is a virtual (logical) table derived from one or more base tables (or other views) by a stored SELECT query. It does not store data itself (unless materialized); its rows are computed when the view is referenced.

CREATE VIEW HighPaid AS
SELECT emp_id, name, salary
FROM   Employee
WHERE  salary > 50000;

It can then be queried like a table: SELECT * FROM HighPaid;

Advantages

1. Security / Access control: expose only selected columns/rows, hiding sensitive data from users.
2. Simplicity / Abstraction: complex joins and aggregations are pre-defined, so users write simple queries against the view.
3. Logical data independence: the view shields applications from changes to the underlying base-table structure.
4. Customized presentation: different users see different tailored views of the same data.
5. Reusability & consistency: a frequently used query is written once and reused, ensuring consistent results.

DELETE vs DROP vs TRUNCATE

DELETE – removes specific rows matching a condition; the table and schema stay:

DELETE FROM Student WHERE marks < 40;

TRUNCATE – removes all rows quickly, keeps the empty table structure:

TRUNCATE TABLE Student;

DROP – removes the whole table including its data, structure, indexes and constraints:

DROP TABLE Student;

Aggregate Functions in SQL

Aggregate functions operate on a set (group) of rows and return a single summary value. They are commonly used with the GROUP BY clause and filtered with HAVING.

Examples

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

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

-- Average salary per department
SELECT dept_id, AVG(salary) AS avg_sal
FROM   Employee
GROUP BY dept_id
HAVING AVG(salary) > 40000;

Note: all aggregate functions ignore NULL values (except COUNT(*), which counts every row).

Trigger

A trigger is a stored procedure that is automatically executed (fired) by the DBMS in response to a specified event — an INSERT, UPDATE, or DELETE — on a particular table. It enforces business rules, complex integrity constraints, auditing, and automatic derivations without explicit user calls.

A trigger is defined by:

• Event – the DML operation that activates it.
• Timing – BEFORE or AFTER (or INSTEAD OF for views).
• Granularity – FOR EACH ROW (row-level) or statement-level.
• Action – the SQL/PLSQL body to execute, optionally guarded by a condition (WHEN).

Example (audit log on salary update)

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

Whenever an employee's salary is updated, the trigger automatically records the old and new values in the audit table.

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 – select students with marks > 80:

• Algebra: $\sigma_{marks>80}(\text{Student})$
• Tuple calculus: $\{\,t \mid t \in \text{Student} \wedge t.marks > 80\,\}$

Thus algebra tells the system how to compute, while calculus only states what is required.

When a relation $R$ is decomposed into $R_1, R_2, \dots$, the decomposition should preserve information and constraints. Two desirable properties are:

Lossless (Non-Loss) Join Decomposition

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

Test (binary case): the decomposition of $R$ into $R_1, R_2$ is lossless iff their common attributes form a superkey of at least one of them:

This property is mandatory for any correct decomposition.

Dependency-Preserving Decomposition

A decomposition is dependency-preserving if the set of functional dependencies that can be enforced on the individual decomposed relations is equivalent to the original set:

This ensures every original FD can be checked on a single relation without performing a join, so constraints stay efficiently enforceable.

Example: $R(A,B,C)$ with $F=\{A\rightarrow B,\ B\rightarrow C\}$ decomposed into $R_1(A,B)$ and $R_2(B,C)$. Common attribute $B$ is a key of $R_2$ ⇒ lossless; $A\rightarrow B$ holds in $R_1$ and $B\rightarrow C$ in $R_2$ ⇒ dependency-preserving. A good (e.g. BCNF/3NF) design always aims for losslessness, and 3NF additionally guarantees dependency preservation.