BE Computer Engineering (IOE, TU) Database Management System (IOE, CT 652) Question Paper 2078 Nepal

(a) Entity-Relationship Diagram (8 marks)

Since an ER diagram cannot be drawn here, it is described precisely below; the components map directly to standard ER notation (rectangles = entity sets, ovals = attributes, diamonds = relationship sets, underlined attribute = primary key).

Entity sets and attributes (primary key underlined):

• STUDENT( roll_no, name, semester, program )
• COURSE( course_code, title, credit_hours )
• TEACHER( emp_id, name )
• DEPARTMENT( dept_id, dept_name )

Relationship sets and constraints:

Cardinality / participation:

• A student enrolls in many courses and a course is taken by many students, with grade as an attribute on the ENROLLS relationship (drawn as an oval attached to the diamond).
• A course is taught by one or more teachers and a teacher may teach many courses ⇒ M:N TEACHES.
• Every course belongs to exactly one department and every teacher belongs to exactly one department ⇒ the COURSE-side and TEACHER-side of OFFERS/WORKS_IN have total participation (double line) with cardinality 1 on the DEPARTMENT side and many on the course/teacher side.

[STUDENT]==(ENROLLS:grade)==[COURSE]==(TEACHES)==[TEACHER]
                                |                    |
                            (OFFERS 1:N)        (WORKS_IN 1:N)
                                |                    |
                                +====[DEPARTMENT]=====+

(b) Relational schemas (4 marks)

Entity sets become tables; the M:N relationships ENROLLS and TEACHES become separate tables; the 1:N relationships are captured by a foreign key on the many side.

• STUDENT( roll_no, name, semester, program )
• DEPARTMENT( dept_id, dept_name )
• COURSE( course_code, title, credit_hours, dept_id )  — dept_id FK → DEPARTMENT
• TEACHER( emp_id, name, dept_id )  — dept_id FK → DEPARTMENT
• ENROLLS( roll_no, course_code, grade )  — roll_no FK → STUDENT, course_code FK → COURSE
• TEACHES( emp_id, course_code )  — emp_id FK → TEACHER, course_code FK → COURSE

(Underlined = primary key; italic / noted = foreign key.)

(a) Closures and candidate keys (5 marks)

Given $F=\{A\rightarrow BC,\; CD\rightarrow E,\; B\rightarrow D,\; E\rightarrow A\}$.

Closure $(A)^+$:

• Start $\{A\}$. By $A\rightarrow BC$: add $B,C \Rightarrow \{A,B,C\}$.
• By $B\rightarrow D$: add $D \Rightarrow \{A,B,C,D\}$.
• By $CD\rightarrow E$: $C,D$ present, add $E \Rightarrow \{A,B,C,D,E\}$.

$$\boxed{(A)^+ = \{A,B,C,D,E\} = R}$$

so A is a (super)key.

Closure $(B)^+$:

• Start $\{B\}$. By $B\rightarrow D$: add $D \Rightarrow \{B,D\}$.
• No other FD’s left side is contained in $\{B,D\}$ ($CD$ needs $C$).

$$\boxed{(B)^+ = \{B,D\}}$$

so B is not a key.

Finding all candidate keys. Note the chain $A\rightarrow BC$, $E\rightarrow A$, so $E$ also determines everything: $(E)^+ = E\rightarrow A\rightarrow BCD\rightarrow E = R$. Check the others:

• $A^+ = R$ ✔, $E^+ = R$ ✔.
• $(BC)^+$: $B\rightarrow D$ gives $\{B,C,D\}$, then $CD\rightarrow E$ gives $E$, then $E\rightarrow A$ gives $A \Rightarrow R$ ✔ so BC is a key.
• $(CD)^+$: $CD\rightarrow E$, $E\rightarrow A$, $A\rightarrow BC \Rightarrow R$ ✔ so CD is a key.

So the candidate keys are: $A$, $E$, $BC$, $CD$. (Each is minimal — no proper subset is a key.)

Prime attributes = $\{A, B, C, D, E\}$ — every attribute appears in some candidate key, so all attributes are prime.

(b) 3NF vs BCNF and highest normal form of R (4 marks)

3NF: for every non-trivial FD $X\rightarrow Y$, either $X$ is a superkey or every attribute in $Y$ is a prime attribute.

BCNF: for every non-trivial FD $X\rightarrow Y$, $X$ must be a superkey (stricter — the prime-attribute exception is removed).

Highest normal form of R. Check each FD:

• $A\rightarrow BC$: $A$ is a key ✔
• $CD\rightarrow E$: $CD$ is a key ✔
• $E\rightarrow A$: $E$ is a key ✔
• $B\rightarrow D$: $B$ is not a superkey. So BCNF is violated.
  • But $D$ is a prime attribute (in candidate key $CD$), so the 3NF condition holds.

Hence R is in 3NF but not in BCNF; the violating dependency is $B\rightarrow D$.

(c) BCNF decomposition (3 marks)

The BCNF-violating FD is $B\rightarrow D$. Compute $(B)^+ = \{B,D\}$. Decompose on it:

• $R_1(\underline{B}, D)$ with FD $B\rightarrow D$ — key $B$, in BCNF.
• $R_2(A,B,C,E)$ = $R$ minus $D$ — its FDs (projected): $A\rightarrow BC$, $E\rightarrow A$, and $BC\rightarrow E$ (since $BC$ determines $E$). Candidate keys of $R_2$ are $A, E, BC$; every FD’s LHS is a key ⇒ $R_2$ is in BCNF.

Lossless? Yes — the common attribute $B$ is a key of $R_1$ ($B\rightarrow BD$), satisfying the lossless-join condition $R_1\cap R_2 \rightarrow R_1$.

Dependency-preserving? $R_1$ preserves $B\rightarrow D$; $R_2$ preserves $A\rightarrow BC$, $E\rightarrow A$. The FD $CD\rightarrow E$ has its LHS split across the two relations and is not directly preserved, so this BCNF decomposition is lossless but not (fully) dependency-preserving — the classic trade-off, since not every schema admits a decomposition that is simultaneously BCNF and dependency-preserving.

(a) ACID properties (4 marks)

(b) Conflict-serializability of the schedule (4 marks)

Operations on A: $T_1$:R(A) @1, $T_2$:R(A) @2, $T_1$:W(A) @3, $T_2$:W(A) @4. Operations on B: only $T_1$.

Conflicting pairs (different transactions, same data item, at least one write):

• $T_2$:R(A)@2 before $T_1$:W(A)@3 ⇒ edge $T_2 \rightarrow T_1$ (read-before-write).
• $T_1$:R(A)@1 before $T_2$:W(A)@4 ⇒ edge $T_1 \rightarrow T_2$.
• $T_1$:W(A)@3 before $T_2$:W(A)@4 ⇒ edge $T_1 \rightarrow T_2$.

Precedence graph: nodes $\{T_1,T_2\}$ with edges $T_1\rightarrow T_2$ and $T_2\rightarrow T_1$.

T1  <==>  T2     (cycle)

The graph contains a cycle $T_1\rightarrow T_2\rightarrow T_1$. Therefore the schedule is NOT conflict-serializable, and no equivalent serial schedule exists.

(c) 2PL, serializability, deadlock and cascading rollback (4 marks)

How 2PL guarantees serializability. In two-phase locking each transaction has a growing phase (it may acquire locks but not release any) followed by a shrinking phase (it may release locks but not acquire any). Because every transaction obtains all its locks before releasing any, the order of lock points defines a serialization order; one can prove the resulting schedule is conflict-serializable (its precedence graph is acyclic).

Why deadlock still occurs. 2PL controls the order of locking but not the requests. Two transactions can each hold a lock the other needs: $T_1$ holds $X$ and waits for $Y$, while $T_2$ holds $Y$ and waits for $X$ — a circular wait ⇒ deadlock. 2PL must be combined with deadlock detection (wait-for graph) or prevention (wait-die/wound-wait).

Why cascading rollback occurs. Basic 2PL may release locks during the shrinking phase before commit. Another transaction can then read this uncommitted (dirty) data; if the first transaction later aborts, every transaction that read its data must also abort — a cascading rollback. This is fixed by strict 2PL, which holds all exclusive (write) locks until commit/abort, ensuring recoverable, cascadeless schedules.

(a) Relational algebra — Kathmandu customers with balance > 50000 (3 marks)

Join the three relations, select on city and balance, then project the name.

$$\pi_{name}\Big(\;\sigma_{city='Kathmandu'\,\wedge\,balance>50000}\big(\;Customer \bowtie Depositor \bowtie Account\;\big)\Big)$$

(The natural joins match on cust_id between Customer and Depositor, and on acc_no between Depositor and Account.)

(b) SQL — branches whose total balance exceeds 1,000,000 (3 marks)

SELECT branch, SUM(balance) AS total_balance
FROM   Account
GROUP BY branch
HAVING SUM(balance) > 1000000;

The GROUP BY aggregates per branch and HAVING filters groups after aggregation (a WHERE clause cannot be used on an aggregate).

(c) SQL — customers holding more than one account (4 marks)

SELECT c.name
FROM   Customer c
JOIN   Depositor d ON c.cust_id = d.cust_id
GROUP BY c.cust_id, c.name
HAVING COUNT(d.acc_no) > 1;

We group the depositor rows by customer and keep only those whose account count exceeds one. (Counting acc_no per cust_id and testing > 1 is the key idea.)

Definitions

• Super key: any set of one or more attributes that uniquely identifies each tuple in a relation. (May contain extra attributes.) E.g. in STUDENT(roll_no, name, …), {roll_no} and {roll_no, name} are both super keys.
• Candidate key: a minimal super key — no proper subset is itself a super key. E.g. {roll_no}.
• Primary key: the one candidate key chosen by the designer to identify tuples; it cannot be NULL and must be unique.
• Foreign key: an attribute (or set) in one relation that references the primary key of another (or the same) relation, linking the two tables.

Referential integrity (example)

Given ACCOUNT(acc_no, branch) and DEPOSITOR(cust_id, acc_no) where DEPOSITOR.acc_no is a foreign key referencing ACCOUNT.acc_no:

Referential integrity requires that every value of DEPOSITOR.acc_no must already exist as an acc_no in ACCOUNT (or be NULL). This prevents a depositor from pointing to a non-existent account — i.e. no “dangling” reference.

ON DELETE CASCADE

When a referenced row is deleted, the action on the child rows is governed by the referential action. With ON DELETE CASCADE, deleting a parent row automatically deletes all child rows that reference it. For example, deleting an ACCOUNT row also deletes every DEPOSITOR row holding that acc_no, keeping the database referentially consistent. (Other options are ON DELETE SET NULL and ON DELETE RESTRICT/NO ACTION, which block the delete.)

(a) Primary (clustered) vs Secondary (non-clustered) index (3 marks)

(b) B+ tree vs B tree, and vs ordered index file (3 marks)

Why B+ tree is preferred over B tree:

• In a B+ tree all data pointers reside in the leaf nodes, while internal nodes store only keys; in a B tree, records/pointers may sit at internal nodes too. Keeping internal nodes key-only gives a higher fan-out, hence a shorter, shallower tree and fewer disk I/Os.
• B+ tree leaves are linked sequentially, so range queries and ordered traversal are efficient (follow leaf pointers); a B tree must do in-order traversal up and down the tree.
• Search cost is uniform — every key search reaches a leaf — giving predictable performance.

Advantage of B+ tree over a simple ordered (sorted) index file: a B+ tree is a dynamic, self-balancing structure; insertions and deletions are handled by node split/merge in $O(\log n)$ time, so performance does not degrade as the file grows. An ordered index file requires costly reorganization (shifting/overflow blocks) on every insert, degrading over time.

Static hashing

In static hashing a fixed number of buckets $B$ is allocated, and a record with search-key $K$ is placed in bucket $h(K) \bmod B$ using a hash function $h$. Lookup, insert and delete on the key require computing the hash and accessing a single bucket — ideally O(1) disk access. The number of buckets is decided in advance and does not change as the file grows or shrinks.

Bucket overflow problem

Because $B$ is fixed, problems arise as the data set changes:

• Bucket overflow occurs when more records hash to a bucket than it can hold. Causes: insufficient buckets, an uneven (skewed) hash distribution, or steady growth of the file.
• Overflow is handled by overflow chaining (linking extra overflow buckets to the full bucket). Long overflow chains turn the O(1) lookup into a costly chain scan, degrading performance.
• If the file shrinks, many buckets become nearly empty, wasting space. The only remedy is a full rehash/reorganization, which is expensive.

Dynamic (extendible) hashing

Extendible hashing lets the bucket structure grow and shrink on demand, eliminating periodic full reorganization.

• It uses a directory: an array of $2^{d}$ pointers, where $d$ is the global depth. The first $d$ bits of the hash value $h(K)$ index into the directory, which points to the bucket holding the record.
• Each bucket has a local depth $d'\le d$, the number of leading hash bits that all records in that bucket share.
• On overflow of a bucket with local depth $d'$:
  • If $d' < d$: split the bucket, redistribute its records by their $(d'+1)$-th bit, set the two new buckets’ local depth to $d'+1$, and update the affected directory pointers. No directory growth needed.
  • If $d' = d$: double the directory (increment global depth $d\to d+1$), then split the bucket as above.

This way only the overflowing bucket is split — most of the file is untouched — so growth is incremental and graceful, avoiding both the bucket-overflow chains and the wasteful full rehashing of static hashing.

(a) Log-based recovery: deferred vs immediate modification (3 marks)

A log is a sequence of records on stable storage describing every update, e.g. $\langle T_i, X, V_{old}, V_{new}\rangle$, written before the change is applied (write-ahead logging).

Deferred database modification:

• All writes of a transaction are recorded only in the log; the actual database is not modified until the transaction commits (after $\langle T_i, commit\rangle$ is logged).
• On recovery: redo all transactions that have both start and commit records; transactions without a commit need no undo (database was never changed). Only a redo is required — simpler.

Immediate database modification:

• Updates are written to the database as they happen (after logging, but possibly before commit).
• On recovery: undo transactions that started but did not commit (using $V_{old}$), and redo committed transactions (using $V_{new}$). Both undo and redo lists are needed.

(b) Checkpoint (3 marks)

A checkpoint is a point at which the DBMS periodically writes a $\langle checkpoint, L\rangle$ record to the log after: (1) flushing all log records in main memory to stable storage, and (2) flushing all modified (dirty) buffer blocks to disk, where $L$ is the list of transactions active at that moment.

How it reduces recovery work: without checkpoints, recovery would have to scan the entire log from the beginning. With a checkpoint, the recovery manager need only consider transactions that were active at or started after the last checkpoint — everything committed and flushed before the checkpoint is already safely on disk and need not be redone. So recovery scans the log backward only up to the most recent checkpoint, drastically cutting the redo/undo workload and recovery time after a crash.

(a) Deadlock and necessary conditions (2 marks)

A deadlock is a situation in which two or more transactions are each waiting indefinitely for a data item locked by another, so none can proceed (a circular wait of resources).

The four necessary (Coffman) conditions are:

1. Mutual exclusion — a resource (lock) is held in a non-shareable mode.
2. Hold and wait — a transaction holds at least one resource while waiting for others.
3. No preemption — a held lock cannot be forcibly taken away; it is released only voluntarily.
4. Circular wait — a cycle of transactions exists, each waiting for a resource held by the next.

(b) Wait-die vs Wound-wait (4 marks)

Both are deadlock-prevention schemes using transaction timestamps; an older transaction has a smaller timestamp. Suppose $T_i$ requests a lock held by $T_j$.

Key idea: Both ensure that waits only go in one direction of timestamp order, so no cycle (circular wait) can form ⇒ no deadlock. In wait-die an older transaction waits and a younger one is killed; in wound-wait an older transaction preempts (wounds) the younger and the younger one waits. In both, rolled-back transactions keep their original timestamp so they are not starved — eventually they become the oldest and complete.

(a) Levels of database security (3 marks)

Security must be enforced at several levels — a weakness at any one level compromises the whole system:

1. Database / DBMS level (authorization): privileges on tables, views, rows — GRANT/REVOKE, roles, views to restrict visible data.
2. Operating-system level: OS file permissions and accounts must protect the database files; an OS breach bypasses DBMS controls.
3. Network level: data in transit must be protected (encryption, SSL/TLS) against eavesdropping and tampering.
4. Physical level: the servers/disks must be in a secured location to prevent theft or destruction.
5. Human level: users must be properly authenticated and trained to prevent social-engineering / careless disclosure of credentials.

(b) GRANT, REVOKE and WITH GRANT OPTION (3 marks)

GRANT gives privileges (SELECT, INSERT, UPDATE, DELETE, etc.) on database objects to users or roles:

GRANT SELECT, UPDATE ON Account TO clerk;

REVOKE withdraws previously granted privileges:

REVOKE UPDATE ON Account FROM clerk;

WITH GRANT OPTION lets the recipient further grant the same privilege to other users:

GRANT SELECT ON Account TO manager WITH GRANT OPTION;

Here manager can not only read Account but also pass SELECT on Account to others. If the original grant is later revoked, the privileges that were propagated from it are normally revoked in cascade as well (to remove the whole authorization chain).

JOIN in relational algebra

A join combines tuples from two relations based on a condition relating their attributes; it is essentially a Cartesian product followed by a selection (and possibly a projection). Let Employee(eid, name, dept_id) and Department(dept_id, dname).

Theta join ($\bowtie_\theta$)

Combines tuples that satisfy an arbitrary condition $\theta$ (using $=,<,>,\le,\ge,\ne$). Common attributes are not merged.

$$Employee \bowtie_{Employee.dept\_id = Department.dept\_id} Department$$

Example: pairs each employee with its matching department row; the result keeps both dept_id columns. (When $\theta$ uses only =, it is an equi-join.)

Natural join ($\bowtie$)

A special equi-join on all attributes with the same name, automatically keeping just one copy of each common attribute.

$$Employee \bowtie Department$$

Joins on the common attribute dept_id and outputs (eid, name, dept_id, dname) with a single dept_id. Only employees whose dept_id matches a department appear (unmatched tuples are dropped).

Outer join

Extends the join to preserve unmatched tuples, padding missing attributes with NULL:

• Left outer join ($⟕$): keeps all left-relation tuples; e.g. an employee with no department still appears with dname = NULL.
• Right outer join ($⟖$): keeps all right-relation tuples; e.g. a department with no employees appears with employee fields NULL.
• Full outer join ($⟗$): keeps unmatched tuples from both sides.

Summary: theta join = condition-based, keeps duplicate cols; natural join = auto-match same-named cols, one copy; outer join = like a join but retains non-matching rows with NULLs.

(a) Weak entity set and identifying relationship (2 marks)

A weak entity set is one that does not have a primary key of its own; it cannot be uniquely identified by its own attributes alone. It depends on a strong (owner) entity for identification. Its only partial key is a discriminator (partial key), shown with a dashed underline; the full key = owner’s primary key + discriminator.

The relationship that links the weak entity to its owner is the identifying relationship (drawn as a double diamond), and the weak entity has total participation in it.

Example: DEPENDENT(name, relationship) of an EMPLOYEE. A dependent’s name is not unique across all employees; it is identified by (employee.emp_id, dependent.name). The relationship HAS_DEPENDENT is the identifying relationship.

(b) Specialization and generalization (2 marks)

• Specialization (top-down): taking a higher-level (super) entity set and defining sub-groups (subclasses) that have additional, distinguishing attributes. Example: EMPLOYEE is specialized into SECRETARY, ENGINEER, MANAGER, each with extra attributes. Shown with an ISA triangle pointing to the superclass.
• Generalization (bottom-up): the reverse — recognizing common attributes among several entity sets and combining them into a higher-level entity set. Example: CAR and TRUCK are generalized into VEHICLE with shared attributes (reg_no, model).

Subclasses inherit the attributes and relationships of the superclass. Constraints include disjoint vs overlapping and total vs partial participation.

(c) Aggregation (2 marks)

Aggregation is an abstraction that treats a relationship (together with its participating entities) as a single higher-level entity, so that this relationship can itself participate in another relationship. It overcomes the ER-model limitation that a relationship cannot directly link to another relationship.

Example: the relationship WORKS_ON between EMPLOYEE and PROJECT is aggregated into one unit; a MANAGER entity then has a MANAGES relationship to this aggregated WORKS_ON, expressing that a manager supervises the assignment of an employee to a project (not just an employee or a project separately). It is drawn by enclosing the WORKS_ON relationship and its entities in a box and connecting MANAGES to that box.