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

Relational Algebra

Relational algebra is a procedural query language that takes one or two relations as input and produces a new relation as output. It is the theoretical foundation of SQL and specifies how to obtain a result through a sequence of operations.

Consider the relations:

Employee(eid, name, dept, salary) and Department(dept, location).

1. Selection ($\sigma$)

Selects rows (tuples) that satisfy a given predicate.

$$\sigma_{salary > 30000}(Employee)$$

Returns all employees earning more than 30000.

2. Projection ($\pi$)

Selects specified columns (attributes) and removes duplicates.

$$\pi_{name,\ salary}(Employee)$$

Returns only the name and salary columns.

3. Union ($\cup$)

Combines tuples of two union-compatible relations (same arity and domains), removing duplicates.

$$\pi_{name}(\sigma_{dept='IT'}(Employee)) \cup \pi_{name}(\sigma_{dept='HR'}(Employee))$$

Returns names of employees in IT or HR.

4. Set Difference ($-$)

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

$$\pi_{eid}(Employee) - \pi_{eid}(\sigma_{dept='IT'}(Employee))$$

Returns ids of all employees not in IT.

5. Cartesian Product ($\times$)

Combines every tuple of the first relation with every tuple of the second. If $R$ has $m$ tuples and $S$ has $n$ tuples, $R \times S$ has $m \times n$ tuples.

$$Employee \times Department$$

6. Join ($\bowtie$)

Combines related tuples from two relations based on a condition; it is effectively a Cartesian product followed by a selection.

• Theta join: $Employee \bowtie_{Employee.dept = Department.dept} Department$
• Natural join (matches common attributes automatically):

$$Employee \bowtie Department$$

Returns each employee combined with the location of their department.

Summary

The fundamental (primitive) operations are $\sigma, \pi, \cup, -, \times$ plus rename ($\rho$); join and intersection are derived operations expressible using these primitives.

SQL (Structured Query Language)

SQL is the standard declarative language for defining, manipulating, and querying data in a relational DBMS. Its sub-languages are DDL (CREATE, ALTER, DROP), DML (INSERT, UPDATE, DELETE, SELECT), DCL (GRANT, REVOKE) and TCL (COMMIT, ROLLBACK).

Assume the schema:

CREATE TABLE Department (
    dept_id   INT PRIMARY KEY,
    dname     VARCHAR(30) NOT NULL
);

CREATE TABLE Employee (
    emp_id    INT PRIMARY KEY,
    name      VARCHAR(50) NOT NULL,
    salary    DECIMAL(10,2),
    dept_id   INT,
    FOREIGN KEY (dept_id) REFERENCES Department(dept_id)
);

Inserting data

INSERT INTO Department VALUES (1, 'IT'), (2, 'HR');
INSERT INTO Employee VALUES (101, 'Ram', 45000, 1),
                           (102, 'Sita', 38000, 1),
                           (103, 'Hari', 30000, 2);

Join operation

List each employee with their department name:

SELECT e.name, e.salary, d.dname
FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id;

GROUP BY operation

Find the number of employees and average salary per department:

SELECT d.dname, COUNT(*) AS num_emp, AVG(e.salary) AS avg_sal
FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id
GROUP BY d.dname
HAVING AVG(e.salary) > 30000;

Nested subquery

Find employees who earn more than the average salary of all employees:

SELECT name, salary
FROM Employee
WHERE salary > (SELECT AVG(salary) FROM Employee);

A correlated subquery example — employees earning above their own department's average:

SELECT name, salary
FROM Employee e
WHERE salary > (SELECT AVG(salary)
                FROM Employee
                WHERE dept_id = e.dept_id);

These queries demonstrate table creation (DDL), data insertion (DML), and the join, aggregation, and nested-query capabilities of SQL.

Database Recovery

Database recovery is the process of restoring the database to the most recent consistent state that existed before a failure (transaction failure, system crash, or media failure), so that the atomicity and durability properties of transactions are preserved.

Log-Based Recovery

The system maintains a log (an append-only sequence of records on stable storage) recording every database modification. A typical update log record is:

$$\langle T_i,\ X,\ V_{old},\ V_{new} \rangle$$

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

1. Deferred Database Modification

• All updates are recorded only in the log; the actual database is not modified until the transaction commits.
• During recovery, only redo is needed:
  • REDO every $T_i$ that has both $\langle T_i\ \text{start} \rangle$ and $\langle T_i\ \text{commit} \rangle$ in the log (using $V_{new}$).
  • Transactions with no commit record are simply ignored (their changes never reached the database).
• No UNDO is required.

2. Immediate Database Modification

• Updates are written to the database while the transaction is still active, after the log record is written (WAL).
• During recovery, both operations are needed:
  • UNDO (restore $V_{old}$) every $T_i$ that has a start but no commit record.
  • REDO (apply $V_{new}$) every $T_i$ that has both start and commit records.
• Undo must be done before redo, processing the log backward then forward.

3. Checkpoints

Scanning the entire log after a crash is expensive. A checkpoint $\langle \text{checkpoint}\ L \rangle$ is periodically written after flushing all log records and modified buffer blocks to disk, where $L$ is the list of active transactions.

During recovery the system scans backward only until the most recent checkpoint:

• Transactions that committed before the checkpoint need no action.
• Only transactions active at, or started after, the checkpoint need to be redone/undone.

This dramatically reduces recovery time and limits the portion of the log that must be examined.

Deadlock in a Database

A deadlock is a situation in which two or more transactions are each waiting for a lock held by another, so that none of them can ever proceed — they wait for each other in a cycle. 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$.

Handling Deadlocks

1. Deadlock Prevention — ensure the system never enters a deadlock:

• Acquire all required locks at once, or impose a total ordering on data items and lock them in that order.
• Timestamp-based schemes such as Wait-Die (older transaction waits, younger is rolled back) and Wound-Wait (older wounds/rolls back younger, younger waits).

2. Deadlock Detection — allow deadlocks but detect them using a Wait-For Graph (WFG), where an edge $T_i \rightarrow T_j$ means $T_i$ is waiting for $T_j$. A cycle in the WFG indicates a deadlock.

3. Deadlock Recovery — once detected, select a victim transaction (usually the one with least cost/work done) and roll it back (full or partial), releasing its locks so others can continue. Starvation is avoided by limiting how often the same transaction is chosen as victim.

4. Timeout — a simpler scheme where a transaction waiting longer than a threshold is assumed deadlocked and rolled back.

Schedule

A schedule is a chronological ordering of the operations (read, write, commit, abort) of a set of concurrent transactions, preserving the relative order of operations within each individual transaction.

Serial vs Serializable Schedule

A serializable schedule gives the same final result as if the transactions had run serially, so it preserves database consistency while still allowing concurrency. Serializability is commonly tested via conflict serializability (an acyclic precedence/serialization graph) or view serializability.

Stored Procedure

A stored procedure is a named, precompiled set of one or more SQL statements (and procedural logic) that is stored in the database and executed on the server as a single unit by calling its name. It may accept input/output parameters and can include control structures such as loops, conditionals, and exception handling (e.g. PL/SQL, T-SQL).

Example

CREATE PROCEDURE GetEmpByDept (IN p_dept INT)
BEGIN
    SELECT emp_id, name, salary
    FROM Employee
    WHERE dept_id = p_dept;
END;

-- Invocation
CALL GetEmpByDept(1);

Advantages

• Performance: parsed and compiled once, so repeated execution is faster; 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 permission to execute the procedure without direct access to the underlying tables.
• Consistency: centralizes rules so all applications behave the same way.

Data Redundancy and Normalization

Data redundancy is the unnecessary repetition of the same data in multiple places within a database. Storing data redundantly (e.g. repeating a customer's address in every order row) wastes storage and causes anomalies:

• Insertion anomaly — cannot add data without other unrelated data.
• Update anomaly — a change must be made in many rows; missing one leaves the data inconsistent.
• Deletion anomaly — deleting one row unintentionally removes other useful information.

How Normalization Reduces Redundancy

Normalization is the process of decomposing relations into smaller, well-structured relations based on functional dependencies, organizing data to minimize redundancy and avoid anomalies. It is applied through a series of normal forms:

• 1NF — atomic (single-valued) attributes, no repeating groups.
• 2NF — 1NF + no partial dependency (non-key attributes fully depend on the whole primary key).
• 3NF — 2NF + no transitive dependency (non-key attributes do not depend on other non-key attributes).
• BCNF — stricter 3NF where every determinant is a candidate key.

By splitting a table so that each fact is stored exactly once and linking the resulting tables through primary key / foreign key relationships, normalization removes duplicated data and thus eliminates the update, insertion, and deletion anomalies.

Multivalued Dependency (MVD) and 4NF

Multivalued Dependency

A multivalued dependency $X \twoheadrightarrow Y$ holds in a relation when, for each value of $X$, there is a set of values of $Y$ that is independent of all other attributes $Z = R - X - Y$. In other words, $Y$ and $Z$ are independent multivalued facts about $X$.

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

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

Storing all combinations forces redundant rows (every instructor paired with every textbook), causing update anomalies even though there is no functional dependency among them.

Fourth Normal Form (4NF)

A relation is in 4NF if it is in BCNF and contains no non-trivial multivalued dependency $X \twoheadrightarrow Y$ unless $X$ is a superkey.

To achieve 4NF the relation is decomposed to separate independent multivalued facts. The example becomes:

• Course_Instructor(course, instructor)
• Course_Textbook(course, textbook)

This removes the cross-product redundancy while preserving all information (a lossless decomposition).

Join

A join is a relational/SQL operation that combines rows from two or more tables based on a related column (usually a primary key–foreign key relationship), producing a single result set.

Inner Join

Returns only the matching rows — rows that satisfy the join condition in both tables. Unmatched rows are excluded.

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

Outer Join

Returns matching rows plus unmatched rows from one or both tables; missing columns are filled with NULL. There are three types:

• LEFT OUTER JOIN — all rows from the left table + matching rows from the right (NULLs where no match). e.g. all employees, even those with no department.
• RIGHT OUTER JOIN — all rows from the right table + matching rows from the left.
• FULL OUTER JOIN — all rows from both tables, matched where possible, NULLs elsewhere.

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

Key difference: an inner join keeps only matched tuples, whereas an outer join preserves unmatched tuples from one or both relations using NULLs.

Strong vs Weak Entity

Example: Employee(emp_id, name) is a strong entity. Dependent(name, relation) is a weak entity that exists only with respect to an employee; it is identified by combining emp_id (owner key) with name (partial key) → composite key (emp_id, name).

File System vs DBMS

Summary: A file system stores data in independent OS files with logic embedded in applications, leading to redundancy and inconsistency, whereas a DBMS provides a centralized, controlled environment offering data integrity, security, concurrency, recovery, and data independence.

Roles of a Database Administrator (DBA)

The DBA is the person responsible for the overall management, control, and integrity of the database system. The main roles are:

1. Schema definition — designs the database schema (tables, relationships) and writes the DDL definitions and storage structure.
2. Storage structure and access-method definition — decides physical organization and indexes for efficient access.
3. Schema and physical modification — alters the schema and physical organization as requirements change.
4. Granting authorization / security — controls user access by granting and revoking privileges and enforcing data security.
5. Integrity constraint specification — defines and maintains constraints (primary keys, foreign keys, checks) to preserve data integrity.
6. Backup and recovery — schedules backups and restores the database to a consistent state after failures.
7. Performance monitoring and tuning — monitors usage, tunes queries and indexes, and manages disk space.
8. Concurrency and routine maintenance — manages multi-user access, applies patches/upgrades, and handles day-to-day administration.