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

(a) ER Diagram

Entity sets and attributes (primary keys in bold):

• STUDENT( student_id, name, address, phone (multivalued), dob )
• COURSE( course_code, title, credit_hours )
• INSTRUCTOR( employee_id, name )
• DEPARTMENT( dept_name )

Relationship sets:

Textual depiction of the diagram:

        (name)(address)(dob)         (course_code)(title)(credit_hours)
            \   |   /                       \    |    /
  {phone}===[ STUDENT ]====<ENROLLS>====[ COURSE ]====<PREREQUISITE>
            (student_id)   /semester        |  ^________________|  (recursive)
                          /grade            |
                                       <TEACHES>/semester
                                            |
                                     [ INSTRUCTOR ]----<BELONGS_TO>----[ DEPARTMENT ]
                                     (employee_id)(name)                 (dept_name)

Notation used: double oval {phone} = multivalued attribute; the address can be drawn as a composite attribute (street, city, zip). The diamond on STUDENT—COURSE carries the relationship attributes semester and grade because they belong to the enrollment, not to either entity. The 1 and N labels mark cardinality ratios; a double line denotes total participation.

(b) Weak entity / recursive relationship

• Recursive relationship – PREREQUISITE. A prerequisite of a course is itself a course, so the relationship PREREQUISITE connects the COURSE entity set to itself (a unary/recursive M:N relationship). Two role names are needed, e.g. is_prereq_of and requires. This is the natural model because prerequisites are full-fledged courses with their own attributes; creating a separate entity would duplicate data.
• Weak entity set. In the base design there is no weak entity. However, if the enrollment had to be uniquely identified (e.g. an ENROLLMENT is recorded per attempt), it could be modeled as a weak entity identified by the combination of (student_id, course_code, semester) — its existence depends on both STUDENT and COURSE (identifying relationships), and semester acts as the partial (discriminator) key. Modeling enrollment as a relationship with attributes (semester, grade) is preferred here since each (student, course, semester) triple is unique and no independent identity is required.

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

(a) Attribute closures and candidate keys

{A}+: A → A, BC (A→BC), so {A,B,C}; B→D gives D → {A,B,C,D}; CD→E gives E → {A,B,C,D,E}; E→A adds nothing new.

$$\{A\}^+ = \{A,B,C,D,E\}$$

{B}+: B → {B}; B→D → {B,D}; no other LHS is satisfied.

$$\{B\}^+ = \{B,D\}$$

Note that F never appears on the right-hand side of any FD, so F must be in every key. Also A, E, and (via E→A) the set {A,B,C,D,E} are mutually derivable: A→…→E and E→A, B→D, etc.

Check {A,F}+ = {A,B,C,D,E} ∪ {F} = all attributes → AF is a candidate key. Because A, E are equivalent (A⁺ contains E and E→A), EF is also a key: {E}+ via E→A then A→BC→…= all, so {E,F}+ = R → EF is a candidate key. Likewise B determines D but not C, so B alone won't form a key; however since A→BC and the cycle makes A,E,B,C,D inter-derivable from any of A or E, the prime attributes are determined by A or E plus F.

Candidate keys: { AF, EF }. (Prime attributes: A, E, F.)

(b) Highest normal form

• 2NF: No partial dependency of a non-prime attribute on part of a key. Non-prime attributes are B, C, D. Keys are AF, EF. Since F never appears on any LHS, no FD lets a proper subset of a key determine a non-prime attribute fully, but A→BC means part of key AF (namely A) determines non-prime B,C → partial dependency. Hence R violates 2NF.
• Therefore the highest normal form satisfied is 1NF only.

(3NF and BCNF also fail, e.g. A→BC has A as a non-superkey LHS, violating BCNF; and B→D has non-prime D dependent on non-superkey B, violating 3NF.)

(c) BCNF decomposition

Apply the BCNF algorithm. A→BC violates BCNF (A is not a superkey). Decompose on A→{A}+:

• R1(A,B,C,D,E) = {A}+, with FDs A→BC, B→D, CD→E, E→A.
• R2(A,F) = (R − ({A}+ − A)).

In R1, B→D violates BCNF (B not a superkey of R1). Decompose: {B}+ in R1 = {B,D}.

• R3(B,D) with B→D.
• R1'(A,B,C,E) with A→BC… now A→BC, E→A, and (CD→E loses D). Keys of R1' are A and E.

Final BCNF schema (one valid result):

• R2(A, F)
• R3(B, D) — from B→D
• R4(A, B, C, E) — preserving A→BC, E→A

Lossless-join: Yes. Each binary decomposition step splits on a dependency X→Y where the common attribute X is a key of one fragment (A is key of R4, B is key of R3), satisfying the lossless-join condition $R_1 \cap R_2 \to R_1$ or $\to R_2$.

Dependency-preserving: No. The dependency CD→E cannot be enforced in any single resulting relation (C, D, E are not all together in one fragment after splitting B→D out). This is the well-known trade-off: BCNF decomposition can lose dependency preservation. If dependency preservation is essential, one would stop at 3NF instead.

(a) ACID Properties

1. Atomicity – A transaction is all-or-nothing; either all its operations commit or none do. Example: a funds transfer debits account X and credits account Y; if the system crashes after the debit, the debit is rolled back so money is never lost.
2. Consistency – A transaction takes the database from one valid (constraint-satisfying) state to another. Example: after the transfer, the sum (X + Y) remains unchanged, preserving the total-balance integrity constraint.
3. Isolation – Concurrent transactions do not interfere; the result is as if they ran serially. Example: if T1 transfers money while T2 computes the total balance, T2 must not see the partial state where X is debited but Y is not yet credited.
4. Durability – Once committed, changes survive subsequent failures. Example: after the transfer commits and the user is notified, a power failure cannot undo it because the change is recorded in the log/disk.

(b) Conflict-serializability of schedule S

Order of operations: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B).

Identify conflicting pairs (different transactions, same item, at least one write):

• W1(A) … R2(A): W–R conflict ⇒ T1 → T2
• W1(A) … W2(A): W–W conflict ⇒ T1 → T2
• R1(A) … W2(A): R–W conflict ⇒ T1 → T2

(Operations on B are all in T1, so no cross conflicts.)

Precedence graph:

   ┌─────┐        ┌─────┐
   │ T1  │ ─────▶ │ T2  │
   └─────┘        └─────┘

The graph has a single edge T1 → T2 and no cycle. Therefore S is conflict-serializable.

Equivalent serial schedule: topological order of the graph ⇒ T1, then T2 (i.e. all of T1's operations followed by all of T2's).

(a) SQL statements

1. Passengers who booked a flight from Kathmandu to Pokhara:

SELECT DISTINCT p.pname
FROM PASSENGER p
JOIN BOOKING b   ON p.pid = b.pid
JOIN FLIGHT  f   ON b.flight_no = f.flight_no
WHERE f.source = 'Kathmandu' AND f.destination = 'Pokhara';

2. Source city and average fare, only for cities with more than 3 flights:

SELECT source, AVG(fare) AS avg_fare
FROM FLIGHT
GROUP BY source
HAVING COUNT(*) > 3;

3. Passengers who have NOT made any booking:

SELECT pname
FROM PASSENGER
WHERE pid NOT IN (SELECT pid FROM BOOKING);
-- or: LEFT JOIN BOOKING b ON p.pid=b.pid WHERE b.pid IS NULL

4. Increase fare by 10% for flights to Biratnagar:

UPDATE FLIGHT
SET fare = fare * 1.10
WHERE destination = 'Biratnagar';

(b) Relational algebra

Query (1) – passenger names on Kathmandu→Pokhara flights:

$$\pi_{pname}\Big(PASSENGER \bowtie BOOKING \bowtie \big(\sigma_{source='Kathmandu' \,\land\, destination='Pokhara'}(FLIGHT)\big)\Big)$$

Query (3) – passengers with no booking (set difference):

$$\pi_{pname}\Big(PASSENGER \bowtie \big(\pi_{pid}(PASSENGER) - \pi_{pid}(BOOKING)\big)\Big)$$

The ANSI/SPARC three-schema architecture separates a database description into three levels of abstraction to hide implementation details from users:

1. External (View) level – Multiple user-specific views; each external schema describes the part of the database a particular user group sees, hiding the rest.
2. Conceptual (Logical) level – A single community schema describing what data is stored (entities, relationships, constraints) for the whole organization, independent of physical storage.
3. Internal (Physical) level – Describes how data is physically stored: file organization, indexes, compression, storage structures.

Mappings connect adjacent levels (external↔conceptual and conceptual↔internal).

• Logical data independence: ability to change the conceptual schema (e.g. add an attribute or split a relation) without altering external schemas / application programs. Achieved by updating the external/conceptual mapping rather than the views.
• Physical data independence: ability to change the internal schema (e.g. add an index, change file organization) without altering the conceptual schema. Achieved by updating the conceptual/internal mapping. Physical independence is easier to achieve than logical independence.

Entity integrity constraint: No attribute that forms part of the primary key of a relation may be NULL (and the primary key must be unique). This guarantees every tuple is uniquely identifiable.

Referential integrity constraint: A foreign key value in one relation must either match an existing primary-key value in the referenced relation or be NULL. It ensures relationships between tables remain valid (no "dangling" references).

Example – two related tables:

DEPARTMENT(dept_id PK, dname)
EMPLOYEE(emp_id PK, ename, dept_id FK -> DEPARTMENT(dept_id))

Here EMPLOYEE.dept_id must reference an existing DEPARTMENT.dept_id.

Actions when a referenced (parent) tuple is deleted (referential actions on DELETE):

Example: FOREIGN KEY (dept_id) REFERENCES DEPARTMENT(dept_id) ON DELETE CASCADE.

Primary (clustered) vs Secondary (non-clustered) index

Dense vs Sparse indexing

• Dense index: contains an index entry for every search-key value (every record) in the data file.
• Sparse index: contains an index entry for only some search-key values — typically one entry per data block (the first record of each block). It requires less space but works only when the data file is ordered on the search key.

Diagram (described):

DENSE INDEX                       SPARSE INDEX
Index      Data file              Index      Data file (ordered)
 10 ─────▶ 10                      10 ─────▶ |10  20  30|  (block 1)
 20 ─────▶ 20                      40 ─────▶ |40  50  60|  (block 2)
 30 ─────▶ 30                      70 ─────▶ |70  80  90|  (block 3)
 40 ─────▶ 40
 (one pointer per record)         (one pointer per block; search
                                   finds the block, then scans it)

Dense indexing gives faster lookups (direct hit) at higher storage cost; sparse indexing saves space but needs a sequential scan within a block.

B+ tree index

A B+ tree is a balanced, multi-level tree index in which all actual key values appear in the leaf nodes; internal nodes hold only separator keys to guide the search. Leaves are linked in a sorted chain for efficient range queries. All leaves are at the same depth, giving guaranteed $O(\log n)$ search/insert/delete.

For order 3 (max 3 pointers ⇒ max 2 keys per node; a node splits when it holds a 3rd key).

Insertion of 8, 5, 1, 7, 3, 12, 9, 6

• 8,5 → leaf [5,8].
• 1 → [1,5,8] overflows; split, middle 5 goes up.
  • Root [5], leaves [1] [5,8].
• 7 → goes to [5,8] → [5,7,8] overflows; split, 7 up.
  • Root [5,7], leaves [1] [5] [7,8].
• 3 → leaf [1] → [1,3].
• 12 → leaf [7,8] → [7,8,12] overflows; split, 8 up.
  • Root [5,7,8] overflows; split internal, 7 up.
  • Root [7]; level-2 [5] [8]; leaves [1,3] [5] [7] [8,12].
• 9 → leaf [8,12] → [8,9,12] overflows; split, 9 up to [8] → [8,9].
  • leaves [1,3] [5] [7] [8] [9,12], internal node [8,9].
• 6 → leaf [5] → [5,6].

Final B+ tree

                         [ 7 ]
                        /     \
                  [ 5 ]         [ 8 , 9 ]
                 /     \        /   |    \
            [1,3]      [5,6]  [7]  [8]  [9,12]

Leaf chain (sorted, linked): 1 3 → 5 6 → 7 → 8 → 9 12. The tree is balanced with all leaves at the same level.

(a) Two-Phase Locking (2PL)

2PL is a concurrency-control protocol guaranteeing conflict-serializability. Each transaction acquires and releases locks in two distinct phases:

1. Growing (expanding) phase: the transaction may acquire locks (shared/exclusive) but may not release any lock.
2. Shrinking (contracting) phase: once the transaction releases its first lock, it enters this phase and may only release locks — it can acquire no new locks.

The point between the two phases (where the transaction holds all its locks) is the lock point. Ordering transactions by lock point yields an equivalent serial schedule, so basic 2PL ensures serializability (though not freedom from deadlock).

(b) Strict vs Rigorous 2PL

• Strict 2PL: all exclusive (write) locks are held until the transaction commits or aborts; shared locks may be released earlier.
• Rigorous 2PL: all locks (both shared and exclusive) are held until commit/abort.

Avoiding cascading rollbacks: Because write locks are not released until commit, no other transaction can read or overwrite data that an uncommitted transaction has written. Hence if a transaction aborts, no committed-on-its-data transactions need to be rolled back — cascading aborts are eliminated (the schedule is recoverable and cascadeless). Rigorous 2PL additionally guarantees that transactions can be serialized in their commit order.

Log-based recovery

The DBMS keeps a sequential log of <Ti, X, old_value, new_value> records describing every update. Following the write-ahead logging (WAL) rule, the log record is written to stable storage before the corresponding data page.

1. Deferred update (NO-UNDO/REDO): Updates are recorded in the log but not applied to the database until the transaction commits. Because the database on disk is never changed by an uncommitted transaction, recovery needs no UNDO.

• On crash: REDO all transactions that have a <commit> record (replay their new values); ignore the rest.

2. Immediate update (UNDO/REDO): Updates are written to the database as they happen, possibly before commit. The log stores both old and new values.

• On crash: UNDO all transactions with no <commit> (restore old values, in reverse order) and REDO all committed transactions (apply new values).

Role of checkpoints

A checkpoint periodically flushes all log buffers and modified (dirty) data pages to disk and writes a <checkpoint> record listing active transactions. After a crash, the recovery manager need only scan the log back to the most recent checkpoint instead of the entire log:

• Transactions that committed before the checkpoint are already on disk and need no REDO.
• Only transactions active at/after the checkpoint must be REDONE or UNDONE.

This dramatically reduces recovery time and the amount of log that must be processed.

Deadlock

A deadlock is a state in which two or more transactions are each waiting for a lock held by another, so that none can ever proceed — a circular wait. Example: T1 holds a lock on A and waits for B, while T2 holds B and waits for A.

Timestamp-based deadlock prevention

Each transaction gets a unique timestamp TS(Ti) at start; a smaller timestamp ⇒ older transaction. When Ti requests a lock held by Tj, one of the schemes decides whether Ti waits or someone is rolled back. Both schemes are non-preemptive vs preemptive and avoid cyclic waits by allowing waits in only one timestamp direction.

1. Wait-Die (non-preemptive): If Ti requests a data item held by Tj:

• If TS(Ti) < TS(Tj) (Ti is older) → Ti waits.
• Else (Ti is younger) → Ti dies (rolls back) and restarts later with the same timestamp. "Older waits, younger dies." Example: TS(T1)=5, TS(T2)=10. T1 wants T2's item → T1 older → T1 waits. If T2 wants T1's item → T2 younger → T2 dies and restarts.

2. Wound-Wait (preemptive): If Ti requests a data item held by Tj:

• If TS(Ti) < TS(Tj) (Ti is older) → Ti wounds Tj: Tj is rolled back and Ti gets the item.
• Else (Ti is younger) → Ti waits. "Older wounds younger; younger waits." Example: TS(T1)=5, TS(T2)=10. T1 (older) wants T2's item → T1 wounds T2 (T2 rolls back). T2 (younger) wanting T1's item → T2 waits.

Both schemes prevent deadlock because waiting is always in one consistent timestamp direction, so no cycle can form. Rolled-back transactions keep their original timestamp to avoid starvation.

Database security – authorization & access control

Database security protects data against unauthorized access, modification, or destruction, ensuring confidentiality, integrity, and availability. Authorization (access control) is the mechanism that decides which users may perform which operations (SELECT, INSERT, UPDATE, DELETE, etc.) on which objects (tables, views, columns). The DBMS maintains an authorization/privilege catalog and checks every request against it.

GRANT and REVOKE

SQL implements Discretionary Access Control (DAC) through these statements:

-- give privileges
GRANT SELECT, UPDATE ON Employee TO alice;
-- WITH GRANT OPTION lets the grantee pass the privilege on
GRANT SELECT ON Employee TO bob WITH GRANT OPTION;

-- take privileges back
REVOKE UPDATE ON Employee FROM alice;

• GRANT confers specified privileges on a database object to a user/role.
• WITH GRANT OPTION allows the recipient to grant the same privilege to others.
• REVOKE withdraws privileges; REVOKE ... CASCADE also removes privileges that were granted onward by the affected user.

Role-Based Access Control (RBAC)

Instead of granting privileges to individual users, privileges are assigned to roles (named sets of privileges, e.g. clerk, manager), and roles are granted to users:

CREATE ROLE manager;
GRANT SELECT, UPDATE ON Salary TO manager;
GRANT manager TO alice;

RBAC simplifies administration: changing a role's privileges instantly affects all its members, and users inherit privileges by their job function rather than individually.

Theta join ($\bowtie_\theta$): combines tuples of two relations that satisfy an arbitrary comparison condition $\theta$ (using =, <, >, ≤, ≥, ≠) on attributes from the two relations. It keeps all columns of both relations (the join attribute(s) appear twice).

$$R \bowtie_{R.A < S.B} S = \sigma_{R.A < S.B}(R \times S)$$

Example: EMPLOYEE ⋈_{EMP.salary < MGR.budget} MANAGER returns employee–manager pairs where the salary is below the manager's budget. An equijoin is the special case where θ uses only equality.

Natural join ($\bowtie$): a special equijoin that joins on all attributes with the same name in both relations, requires them to be equal, and then removes the duplicate (redundant) common columns from the result.

$$STUDENT \bowtie ENROLL$$

if both have attribute student_id, joins where STUDENT.student_id = ENROLL.student_id and outputs student_id only once.

Key differences: