BE Computer Engineering (Pokhara University) Database Management System (PU, CMP 222) Question Paper 2079 Nepal

(a) ER Diagram (10 marks)

Entity sets and attributes (key attributes underlined are shown in bold):

• STUDENT(reg_no, name, address, {contact_no}) — reg_no is the key; {contact_no} is a multivalued attribute (a student may have several numbers).
• COURSE(course_code, title, credit_hours)
• TEACHER(emp_id, name, designation)
• DEPARTMENT(dept_code, name)

Relationship sets and constraints:

Diagram (described): Draw four rectangles for the entity sets. Ovals attached to STUDENT: reg_no (underlined), name, address, and contact_no shown as a double oval (multivalued). A diamond OFFERS links DEPARTMENT (1 side, single line) to COURSE (N side, double line for total participation). A diamond EMPLOYS links DEPARTMENT (1) to TEACHER (N, double line). A diamond ENROLLS links STUDENT and COURSE with M and N near the lines and a grade oval hanging off the diamond. A diamond TEACHES links TEACHER and COURSE with M : N.

(b) Relational Schemas (6 marks)

STUDENT(reg_no, name, address)                      -- PK: reg_no
STUDENT_CONTACT(reg_no, contact_no)                 -- PK: (reg_no, contact_no); FK reg_no -> STUDENT
DEPARTMENT(dept_code, name)                         -- PK: dept_code
TEACHER(emp_id, name, designation, dept_code)       -- PK: emp_id; FK dept_code -> DEPARTMENT
COURSE(course_code, title, credit_hours, dept_code) -- PK: course_code; FK dept_code -> DEPARTMENT
ENROLLS(reg_no, course_code, grade)                 -- PK: (reg_no, course_code); FK reg_no -> STUDENT, FK course_code -> COURSE
TEACHES(emp_id, course_code)                         -- PK: (emp_id, course_code); FK emp_id -> TEACHER, FK course_code -> COURSE

Notes: the multivalued attribute contact_no becomes a separate table. The 1:N relationships OFFERS and EMPLOYS are mapped by posting dept_code as a foreign key into COURSE and TEACHER (no separate table needed). The M:N relationships ENROLLS and TEACHES each become their own relation; grade becomes an attribute of ENROLLS.

Relation R(A, B, C, D, E), F = { A → BC, CD → E, B → D, E → A }.

(a) Closures and candidate keys (5 marks)

(A)⁺: A → BC gives B, C ⇒ {A,B,C}. B → D gives D ⇒ {A,B,C,D}. CD → E gives E ⇒ {A,B,C,D,E}.

$$(A)^+ = \{A,B,C,D,E\} = R \Rightarrow A \text{ is a superkey (in fact a key).}$$

(B)⁺: B → D gives D ⇒ {B,D}. No further FD applies (CD needs C; A,E,C unreachable).

$$(B)^+ = \{B,D\} \Rightarrow B \text{ is NOT a key.}$$

Finding all candidate keys: A determines everything, so A is a candidate key. Since E → A and A → everything, E → A → R, so E is a candidate key. Also A → BC, so anything determining A works. Check B: B⁺={B,D} — no. Check combinations giving A via E: nothing else yields E except CD. CD: CD → E → A → BC, so (CD)⁺ = R ⇒ CD is a candidate key. Does any single attribute besides A, E work? No. Does a smaller subset of CD work? C⁺={C}, D⁺={D} — no.

Candidate keys: { A }, { E }, { C D }.

Prime attributes = attributes in some candidate key = { A, C, D, E }. Non-prime attribute = B only.

(b) Highest normal form (4 marks)

• 2NF check — partial dependency of a non-prime attribute on part of a candidate key? The only composite key is CD; does C→B or D→B? No (C⁺, D⁺ do not contain B). So no partial dependency ⇒ R is in 2NF.
• 3NF check — for each FD X → Y either X is a superkey or every attribute in Y is prime. A → BC: A is a key ✓. E → A: E is a key ✓. CD → E: CD is a key ✓. B → D: B is not a superkey, but D is prime ✓. All FDs satisfy 3NF.
• BCNF check — every determinant must be a superkey. B → D has determinant B, and B is not a superkey. So R violates BCNF.

Highest normal form satisfied = 3NF.

(c) 3NF vs BCNF, and BCNF decomposition (7 marks)

Difference: A relation is in 3NF if for every non-trivial FD X → A either X is a superkey or A is a prime attribute (the second relaxation is allowed). BCNF is stricter: for every non-trivial FD X → A, X must be a superkey — the "prime attribute" exception is removed. Thus every BCNF relation is in 3NF, but not vice-versa. BCNF removes all redundancy due to FDs but may not preserve all dependencies; 3NF always preserves dependencies and is always achievable losslessly.

Decomposition into BCNF: The violating FD is B → D. Compute B⁺ = {B, D}.

• Split into R1(B, D) with FD B → D — here B is the key, so R1 is in BCNF.
• Remaining R2(A, B, C, E) = R minus (B⁺ − B) = R minus {D}. Project the FDs: A → BC, E → A, and CD → E becomes irrelevant (D gone) — effectively keys of R2 are {A}, {E}, and we still have B reachable? In R2, A → BC (C present), E → A. Determinants A and E are superkeys of R2. So R2(A, B, C, E) is in BCNF.

Result:

$$R1(\underline{B}, D) \qquad R2(\underline{A}, B, C, E)$$

• Lossless-join: Yes. The common attribute B is a key of R1 (B → D = B → R1), satisfying the lossless-join test (R1 ∩ R2 = {B} is a superkey of R1).
• Dependency-preserving: The FD CD → E is not preserved — C, D, E are no longer together in any single relation (D is only in R1, while C, E are in R2). Hence this BCNF decomposition is lossless-join but not dependency-preserving, illustrating the classic trade-off (a dependency-preserving lossless 3NF design retaining CD→E exists, but BCNF here forces loss of that dependency).

(a) Schedule, conflict and view serializability (6 marks)

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

Conflict serializability: Two operations conflict if they belong to different transactions, access the same data item, and at least one is a write. A schedule is conflict serializable if it can be transformed into some serial schedule by swapping only non-conflicting adjacent operations. Equivalently, it is conflict serializable iff its precedence graph is acyclic.

Example: S1: T1:R(A); T1:W(A); T2:R(A); T2:W(A) is conflict serializable (equivalent to serial T1, T2).

View serializability: A schedule is view serializable if it is view-equivalent to some serial schedule, i.e. (i) same transactions read the same initial values, (ii) each read reads the value written by the same write (same read-from relationships), and (iii) the final write on each item is by the same transaction. View serializability is more general — every conflict-serializable schedule is view-serializable, but not vice-versa (schedules with blind writes may be view- but not conflict-serializable).

(b) Precedence graph (6 marks)

Schedule S in order: T1:R(A), T1:W(A), T2:R(A), T2:W(A), T1:R(B), T1:W(B).

Find conflicting pairs on the same item:

• On A: T1:W(A) before T2:R(A) ⇒ edge T1 → T2. T1:W(A) before T2:W(A) ⇒ T1 → T2. T1:R(A) before T2:W(A) ⇒ T1 → T2.
• On B: only T1 operates, no inter-transaction conflict.

Precedence graph: nodes {T1, T2} with a single directed edge T1 → T2.

   T1 ───────▶ T2

The graph has no cycle, therefore S is conflict serializable. The equivalent serial schedule is obtained from the topological order: T1 → T2 (run all of T1 then all of T2).

(c) Two-phase locking (4 marks)

Under 2PL every transaction acquires and releases locks in two phases: a growing phase (only acquires/upgrades locks, never releases) followed by a shrinking phase (only releases, never acquires). The point separating them is the lock point. Ordering transactions by their lock points yields a serial order conflict-equivalent to the schedule, so 2PL guarantees conflict serializability.

However:

• Deadlock: two transactions can each hold a lock the other needs and wait forever; 2PL prevents serializability violations but not deadlock (handled by detection via wait-for graph, or prevention via timeouts/timestamps).
• Cascading rollback: in basic 2PL a transaction may release a lock and let others read its uncommitted data; if it later aborts, all dependent transactions must also abort.

Strict 2PL holds all exclusive (write) locks until commit/abort — this prevents reading uncommitted writes, eliminating cascading rollbacks and giving recoverable schedules. Rigorous 2PL holds all locks (both shared and exclusive) until commit/abort — even stronger, it makes transactions serializable in commit order and is the easiest to implement; both still require deadlock handling.

Schema: Employee(eid, ename, salary, dept_no, mgr_id), Department(dept_no, dname, location), Project(pid, pname, dept_no, budget), WorksOn(eid, pid, hours).

(a) SQL Queries (10 marks)

(i) Name and salary of employees in the department located in 'Pokhara':

SELECT e.ename, e.salary
FROM Employee e JOIN Department d ON e.dept_no = d.dept_no
WHERE d.location = 'Pokhara';

(ii) Department name and average salary, only for departments with more than 5 employees:

SELECT d.dname, AVG(e.salary) AS avg_salary
FROM Department d JOIN Employee e ON d.dept_no = e.dept_no
GROUP BY d.dept_no, d.dname
HAVING COUNT(*) > 5;

(iii) Employees who work on every project controlled by department 10 (division / double-NOT-EXISTS):

SELECT e.ename
FROM Employee e
WHERE NOT EXISTS (
    SELECT p.pid FROM Project p WHERE p.dept_no = 10
    EXCEPT
    SELECT w.pid FROM WorksOn w WHERE w.eid = e.eid
);

(iv) 10% raise to employees whose total hours across all projects exceed 40:

UPDATE Employee
SET salary = salary * 1.10
WHERE eid IN (
    SELECT eid FROM WorksOn GROUP BY eid HAVING SUM(hours) > 40
);

(v) Each employee with the name of their manager (self-join):

SELECT e.ename AS employee, m.ename AS manager
FROM Employee e LEFT JOIN Employee m ON e.mgr_id = m.eid;

(b) Relational Algebra (6 marks)

(i) Name and salary of employees in the 'Pokhara' department:

$$\pi_{ename,\ salary}\big(\ Employee \bowtie \sigma_{location='Pokhara'}(Department)\ \big)$$

(iii) Employees who work on every project of department 10 — use division (÷). Let the set of department-10 projects be

$$P_{10} \leftarrow \pi_{pid}\big(\sigma_{dept\_no=10}(Project)\big)$$

and the (employee, project) pairs from WorksOn be

$$EW \leftarrow \pi_{eid,\ pid}(WorksOn).$$

Then

$$Result \leftarrow \pi_{ename}\Big(\ \big(\ EW \div P_{10}\ \big) \bowtie Employee\ \Big).$$

The division EW ÷ P₁₀ returns exactly the eids that appear paired with all pids in P₁₀, which is then joined with Employee to obtain the names.

Three-Schema (ANSI/SPARC) Architecture

The ANSI/SPARC architecture separates the user's view of data from its physical storage through three levels of abstraction:

1. External (View) level — the topmost level; describes the part of the database relevant to a particular user/application group as one or more external schemas (user views). Hides the rest of the database.
2. Conceptual (Logical) level — a single conceptual schema describing the whole database for the community of users: entities, attributes, relationships, constraints. It hides physical storage details.
3. Internal (Physical) level — the internal schema describes how data is physically stored: file organization, indexes, access paths, compression.

   User1 view   User2 view   User3 view      <- EXTERNAL level
        \          |          /
          [ external/conceptual mapping ]
                CONCEPTUAL schema           <- CONCEPTUAL level
          [ conceptual/internal mapping ]
                INTERNAL schema             <- INTERNAL level
                 (physical storage)

Mappings between adjacent levels let the DBMS translate a request stated against an external schema down to the physical access. This separation is what provides data independence.

Logical vs Physical Data Independence

• Logical data independence: the capacity to change the conceptual schema without altering external schemas or application programs. Example: adding a new attribute/column or a new entity type to the conceptual schema should not require existing views/queries to be rewritten. (Harder to achieve in practice.)
• Physical data independence: the capacity to change the internal schema without altering the conceptual schema. Example: creating a new index, changing a file from heap to hashed organization, or moving a file to a new disk should not change the logical structure or queries. (Easier to achieve.)

(a) Primary vs Clustering vs Secondary index (4 marks)

Key idea: there can be only one primary or clustering index per file because a file can be physically ordered on only one field, but many secondary indexes.

(b) B+-tree of order p = 4, insert 10, 20, 5, 30, 25, 15 (4 marks)

For order p = 4 an internal node holds at most p−1 = 3 keys and 4 pointers; a leaf holds at most 3 keys. Split when overflow occurs.

• Insert 10, 20, 5 → leaf: [5, 10, 20] (full).
• Insert 30 → leaf overflows to [5,10,20,30]; split. Middle key 20 copied up. Result:

          [20]
         /    \
   [5,10]    [20,30]
  

• Insert 25 → goes to right leaf [20,25,30] (fits).

          [20]
         /    \
   [5,10]    [20,25,30]
  

• Insert 15 → goes to left leaf [5,10,15] (fits).

Final B+-tree:

              [ 20 ]
             /      \
   [5,10,15]        [20,25,30]

Leaves are linked left→right: [5,10,15] → [20,25,30]. (In a B+-tree the separator key 20 in the root is also retained in the leaf, since all data values live in the leaves.)

(a) ACID properties (4 marks)

• Atomicity — a transaction is all-or-nothing; either all its operations take effect or none do. Partial effects of a failed transaction are undone (rolled back).
• Consistency — a transaction transforms the database from one consistent (valid) state to another, preserving all integrity constraints; if it started consistent it ends consistent.
• Isolation — concurrently executing transactions do not interfere; the result is as if they ran serially. Intermediate states of one transaction are hidden from others.
• Durability — once a transaction commits, its effects are permanent and survive subsequent system failures (guaranteed via the log on stable storage).

(b) Deferred-update (NO-UNDO/REDO) log-based recovery (4 marks)

In the deferred update scheme, all updates of a transaction are recorded only in the log (and in buffers) and are not written to the database on disk until the transaction reaches its commit point. Because no uncommitted change ever reaches the database, recovery never needs to UNDO — hence NO-UNDO/REDO.

Log records for a sample transaction T:

<T, start>
<T, X, new_value>      -- only the AFTER image is logged (no old value needed)
<T, Y, new_value>
<T, commit>

Recovery after a crash: scan the log and classify transactions:

• If the log contains both <T, start> and <T, commit> → T is committed but its writes may not have reached disk → REDO T by re-applying every <T, X, new_value> (write new values to the database). REDO is idempotent, so re-doing already-applied writes is harmless.
• If the log contains <T, start> but no <T, commit> → T did not commit; since deferred update never wrote its changes to disk, nothing to undo — simply ignore T.

Thus after recovery only the effects of committed transactions are present, satisfying atomicity and durability.

Relational Algebra Operations

Using example relations Employee(eid, ename, salary, dept_no) and Department(dept_no, dname).

1. Selection (σ) — selects rows (tuples) that satisfy a predicate; a horizontal filter.

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

Use it when you need only the tuples meeting a condition (e.g. employees earning more than 50,000).

2. Projection (π) — selects columns (attributes) and removes duplicate tuples; a vertical filter.

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

Use it when you want only certain attributes of each tuple (e.g. just names and salaries).

3. Natural join (⋈) — combines tuples of two relations that agree on all common (same-named) attributes, keeping one copy of each common attribute.

$$Employee \bowtie Department$$

(joins on the shared dept_no). Use it to combine related information stored across two tables (e.g. each employee together with their department name).

4. Division (÷) — for relations R(A,B) and S(B), R ÷ S returns the values of A that are associated in R with every value of B in S.

$$\pi_{eid,\ pid}(WorksOn) \div \pi_{pid}(Project)$$

Use it for "for all" / "every" queries — e.g. find employees who work on every project. It is the algebraic counterpart of universal quantification.

(a) Deadlock and wait-for graph detection (4 marks)

A deadlock is a situation in which two or more transactions are each waiting for a lock held by another, forming a circular wait, so none of them can ever proceed.

Wait-for graph (WFG): a directed graph with one node per active transaction. An edge Tᵢ → Tⱼ is added whenever Tᵢ is waiting for a data item currently locked by Tⱼ. The system is deadlocked iff the WFG contains a cycle. The DBMS periodically tests for cycles; when one is found it selects a victim transaction in the cycle and rolls it back to break the deadlock.

Example: T1 holds a lock on A and requests B; T2 holds B and requests A.

   T1 ───▶ T2
    ▲        │
    └────────┘

The edges T1 → T2 (T1 waits for B held by T2) and T2 → T1 (T2 waits for A held by T1) form a cycle ⇒ deadlock; abort one of them.

(b) Timestamp-ordering protocol (4 marks)

Each transaction T is assigned a unique timestamp TS(T) when it starts (older transaction ⇒ smaller timestamp). For every data item X the DBMS maintains:

• read_TS(X) = largest timestamp of any transaction that has read X;
• write_TS(X) = largest timestamp of any transaction that has written X.

The protocol enforces that conflicting reads/writes are executed in timestamp order (as if transactions ran serially in timestamp order). On each operation by T:

• T issues read(X): if TS(T) < write_TS(X), T is trying to read a value already overwritten by a younger transaction ⇒ abort T (and restart with a new timestamp). Otherwise read is allowed and read_TS(X) ← max(read_TS(X), TS(T)).
• T issues write(X): if TS(T) < read_TS(X) or TS(T) < write_TS(X), then a younger transaction has already read/written X ⇒ abort T. Otherwise the write is allowed and write_TS(X) ← TS(T).

Because every conflict is resolved in favour of the order of timestamps, the resulting schedule is conflict serializable (equivalent to the serial order of timestamps) and is deadlock-free (transactions are restarted, never made to wait in a cycle), though it can cause restarts/starvation.

(a) Partial vs Transitive dependency (4 marks)

• Partial dependency: a non-prime attribute is functionally dependent on part (a proper subset) of a composite candidate key, rather than on the whole key. A relation is in 2NF if it is in 1NF and has no partial dependency — every non-prime attribute is fully functionally dependent on every candidate key. Removing partial dependencies achieves 2NF.
• Transitive dependency: a non-prime attribute depends on another non-prime attribute, i.e. X → Y → Z where X is the key, Y is non-prime, and Z is non-prime (Z depends on the key only through Y). A relation is in 3NF if it is in 2NF and has no transitive dependency of a non-prime attribute on the key. Removing transitive dependencies achieves 3NF.

(b) Normalizing Order(order_id, cust_id, cust_name, item_id, item_name, qty) (4 marks)

Assumed FDs: candidate key is (order_id, item_id); order_id → cust_id, cust_name; cust_id → cust_name; item_id → item_name; (order_id, item_id) → qty.

Anomalies present (un-normalized):

• Insertion: cannot store a new customer or item without an order.
• Deletion: deleting the last order line of a customer loses the customer's name.
• Update: a customer's name is repeated on every order line and must be changed everywhere.

2NF — remove partial dependencies on the composite key (order_id, item_id):

• order_id → cust_id, cust_name (partial) → ORDER_HEADER(order_id, cust_id, cust_name)
• item_id → item_name (partial) → ITEM(item_id, item_name)
• (order_id, item_id) → qty (full) → ORDER_ITEM(order_id, item_id, qty)

3NF — in ORDER_HEADER there is a transitive dependency order_id → cust_id → cust_name; split out the customer:

• ORDER_HEADER(order_id, cust_id)
• CUSTOMER(cust_id, cust_name)

Final 3NF schemas (PK underlined):

CUSTOMER(cust_id, cust_name)                    -- PK cust_id
ITEM(item_id, item_name)                        -- PK item_id
ORDER_HEADER(order_id, cust_id)                 -- PK order_id; FK cust_id -> CUSTOMER
ORDER_ITEM(order_id, item_id, qty)              -- PK (order_id,item_id); FK order_id, FK item_id

(a) Discretionary Access Control and GRANT/REVOKE (4 marks)

Discretionary Access Control (DAC): an access-control model in which the owner of an object (e.g. a table) grants other users specific privileges (SELECT, INSERT, UPDATE, DELETE, REFERENCES, EXECUTE) on that object at their own discretion. Access decisions are based on the identity of the user and the privileges explicitly granted to them. SQL implements DAC through the GRANT and REVOKE statements.

• GRANT gives privileges to a user/role. With WITH GRANT OPTION, the recipient may further pass the privilege on.

GRANT SELECT, UPDATE ON Employee TO ram;
GRANT SELECT ON Department TO sita WITH GRANT OPTION;

• REVOKE withdraws previously granted privileges. With CASCADE, revocation also removes privileges that were granted onward by the revoked user.

REVOKE UPDATE ON Employee FROM ram;
REVOKE SELECT ON Department FROM sita CASCADE;

(b) Checkpoint in recovery (4 marks)

A checkpoint is a point at which the DBMS writes a <checkpoint> record to the log and flushes all log buffers and all modified (dirty) database buffers to stable storage, so that everything before the checkpoint is known to be safely on disk.

How it reduces recovery work: without checkpoints, after a crash the recovery manager would have to scan the entire log from the beginning, possibly REDOing/UNDOing very old transactions whose effects are already on disk. With checkpoints, recovery only needs to consider the log from the most recent checkpoint onward:

• Transactions that committed before the last checkpoint are already reflected on disk → no REDO needed.
• Only transactions active at or after the checkpoint need to be REDOne (if committed) or UNDOne (if not committed).

This dramatically shortens the portion of the log to be processed and the time taken to recover.

Generalization, Specialization and Aggregation (EER model)

Generalization — a bottom-up abstraction that combines several lower-level entity types sharing common attributes into a higher-level superclass. Example: entity types Car, Truck, and Bus are generalized into a superclass Vehicle holding the common attributes (reg_no, manufacturer). Drawn with an is-a triangle pointing up to the superclass.

Specialization — the top-down reverse process: a higher-level entity type is divided into specialized subclasses based on some distinguishing characteristic, with each subclass having its own specific attributes. Example: Employee is specialized into Engineer, Manager, and Technician; Manager additionally has a bonus attribute. The subclasses inherit the attributes and relationships of the superclass. (Constraints: disjoint/overlapping and total/partial participation.)

Aggregation — an abstraction that treats a relationship (together with its participating entities) as a higher-level entity, so that the relationship can itself participate in another relationship. Example: an Employee works-on a Project (relationship WORKS_ON); to record which Manager manages that particular employee-on-project assignment, we aggregate WORKS_ON into a single abstract entity and relate it to Manager via a MANAGES relationship — something a plain ER model cannot express directly.