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

(a) ER Diagram (10)

Entity sets and attributes (primary keys in bold):

• STUDENT( reg_no, name, semester, program )
• COURSE( course_code, title, credit_hours )
• TEACHER( emp_id, name, department )
• EXAM (weak entity, see below)

Relationship sets:

1. ENROLLS — between STUDENT and COURSE, many-to-many (M:N). Descriptive (relationship) attribute: grade. Each (student, course) pair produces one grade.
2. TEACHES — between TEACHER and COURSE. A teacher teaches many courses but a particular course offering is handled by exactly one teacher, so cardinality is 1:N (one TEACHER : many COURSE), with COURSE in total participation (every offered course has a teacher).
3. SITS — between STUDENT and EXAM (or modelled as a weak entity dependent on ENROLLS/COURSE).

Attribute kinds to show on the diagram:

• Composite attribute: name of STUDENT/TEACHER decomposed into {first_name, last_name}.
• Multivalued attribute: phone of STUDENT (drawn with a double oval) — a student may have several phone numbers.
• Derived attribute: age of STUDENT (drawn with a dashed oval), derived from a stored dob.
• Key attributes underlined: reg_no, course_code, emp_id.

Cardinality / participation (described in words, since the figure cannot be drawn):

 STUDENT ===<ENROLLS(grade)>=== COURSE        (M : N, both partial)
 COURSE  ---<TEACHES>--- TEACHER             (N : 1, COURSE total)

• A double line from COURSE to TEACHES denotes total participation (each course must have a teacher); STUDENT–ENROLLS and COURSE–ENROLLS are partial.
• EXAM is a weak entity (double rectangle) identified by the SITS/identifying relationship with COURSE; its partial key (e.g. exam_date or attempt_no) plus the owner's key forms its identifier.

(b) Mapping M:N relationship and weak entity to tables (5)

Many-to-many ENROLLS → a separate table whose key is the combination of the two participating keys, with the relationship attribute as a non-key column:

ENROLLS( reg_no, course_code, grade )
   PRIMARY KEY (reg_no, course_code)
   FOREIGN KEY (reg_no)      REFERENCES STUDENT(reg_no)
   FOREIGN KEY (course_code) REFERENCES COURSE(course_code)

1:N TEACHES does not need its own table; post a foreign key on the many side:

COURSE( course_code, title, credit_hours, teacher_id )
   FOREIGN KEY (teacher_id) REFERENCES TEACHER(emp_id)   -- NOT NULL (total participation)

Weak entity EXAM → a table that includes the owner's primary key as part of its own (composite) primary key and as a foreign key:

EXAM( reg_no, course_code, exam_date, marks )
   PRIMARY KEY (reg_no, course_code, exam_date)
   FOREIGN KEY (reg_no, course_code) REFERENCES ENROLLS(reg_no, course_code)

Thus the M:N relationship becomes a junction table and the weak entity inherits the identifying owner's key as part of its primary key and as a foreign key.

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

(a) Closure {A}+ and candidate keys (5)

Start with {A}.

• A→B, A→C, A→E give {A, B, C, E}.
• E→C already have C.
• BC→D: B and C present ⇒ add D ⇒ {A, B, C, D, E}.

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

Since A alone determines every attribute, A is a (super)key, and as it is a single attribute it is minimal, so:

The only candidate key is { A }.

(No other attribute appears on the left of an FD in a way that can derive A — A never appears on any right-hand side — so every candidate key must contain A; A by itself already suffices, hence it is the unique candidate key.)

(b) Highest normal form satisfied (5)

• Prime attributes: only A (the sole candidate key). Non-prime: B, C, D, E.

• 2NF: No partial dependency is possible because the key is a single attribute, so R is automatically in 2NF.

• 3NF: A relation is in 3NF if, for every FD X→Y, either X is a superkey or Y is prime. Check the non-trivial dependencies:

  • A→B, A→C, A→E: A is the key ✔
  • BC→D: BC is not a superkey and D is not prime ✘
  • E→C: E is not a superkey and C is not prime ✘

  Hence R violates 3NF (transitive dependencies E→C and BC→D exist).

• BCNF: also violated for the same reason.

Highest normal form = 2NF (R is in 1NF and 2NF but not 3NF, hence not BCNF).

(c) BCNF decomposition (5)

Apply the BCNF algorithm to the violating dependencies.

1. E → C violates BCNF. Decompose on closure {E}+ = {E, C}:
   • R1( E, C )
   • R2( A, B, D, E ) (remaining attributes + E)
2. In R2, F restricted gives A→B, A→E and BE→D? We have BC→D but C ∉ R2; using A→E and A→B, A is still the key of R2 ({A}+ over R2 = {A,B,D,E}). Check R2 = R2(A, B, D, E) with FDs A→B, A→D (since A→B,A→C,BC→D ⇒ A→D), A→E. A is a superkey, so R2 is in BCNF.
3. R1(E, C) with E→C: E is the key ⇒ BCNF.

Resulting BCNF schema:

R1( E, C )            key: E
R2( A, B, D, E )      key: A

• Lossless-join: Yes. The common attribute is E, and in R1 we have E→C (E is a key of R1), so R1 ∩ R2 = {E} → R1, satisfying the lossless-join condition at every step.
• Dependency-preserving: Not fully. A→B, A→E, A→C (= A→E→C) and E→C are preserved, but BC→D cannot be checked within a single relation (B and C are split: B in R2, C in R1), so this decomposition is lossless but not dependency-preserving — a typical trade-off of BCNF (3NF could preserve all dependencies if required).

(a) Transaction and ACID properties (6)

A transaction is a logical unit of work that accesses and possibly updates the database, executed as a single indivisible operation that takes the database from one consistent state to another. Example: transferring Rs. 1000 from account X to account Y.

(b) Precedence graph & conflict-serializability (4)

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

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

• W1(A) before R2(A) ⇒ T1 → T2
• W1(A) before W2(A) ⇒ T1 → T2
• R1(A) before W2(A) ⇒ T1 → T2

All edges go T1 → T2 only.

Precedence graph:   T1 ──▶ T2

The graph has no cycle, therefore S is conflict-serializable.

Equivalent serial schedule: T1 ; T2 (run T1 completely, then T2).

(c) 2PL and cascading rollback (4)

Two-Phase Locking (2PL): every transaction obtains all its locks in a growing phase (locks only acquired, none released) and releases them in a shrinking phase (locks only released, none acquired). Because once a transaction releases a lock it can never acquire another, conflicting operations of two transactions are forced into a consistent order — the lock points define a serialization order — which guarantees conflict-serializable schedules.

Cascading rollback: occurs when a transaction reads an uncommitted (dirty) value of another transaction that later aborts, forcing the reader (and anything that read from it) to also abort.

Example:

T1: W(A) ......... abort
T2:       R(A) ... (read T1's dirty A)

When T1 aborts, T2 must be rolled back too, possibly cascading further. Strict 2PL (hold all exclusive locks until commit/abort) prevents cascading rollback by ensuring no transaction reads or overwrites uncommitted data.

(a) SQL queries (8, 2 each)

(i) Employees in the department located in 'Kathmandu':

SELECT e.ename
FROM   EMPLOYEE e JOIN DEPARTMENT d ON e.dno = d.dno
WHERE  d.location = 'Kathmandu';

(ii) Per-department name and average salary, only departments with > 5 employees:

SELECT d.dname, AVG(e.salary) AS avg_salary
FROM   DEPARTMENT d JOIN EMPLOYEE e ON e.dno = d.dno
GROUP  BY d.dno, 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.pno FROM PROJECT p WHERE p.dno = 10
         EXCEPT
         SELECT w.pno FROM WORKS_ON w WHERE w.eid = e.eid
       );

(iv) Give a 10% raise to employees with > 100 total hours across all projects:

UPDATE EMPLOYEE
SET    salary = salary * 1.10
WHERE  eid IN (
         SELECT eid FROM WORKS_ON
         GROUP BY eid
         HAVING SUM(hours) > 100
       );

(b) Relational algebra (4, 2 each)

(i) Employees in the Kathmandu-located department:

$$\pi_{ename}\big( EMPLOYEE \bowtie \big(\sigma_{location='Kathmandu'}(DEPARTMENT)\big) \big)$$

(iii) Employees who work on every project of department 10 — using the division operator:

$$\text{ProjDno10} \leftarrow \pi_{pno}\big(\sigma_{dno=10}(PROJECT)\big)$$ $$\text{EmpProj} \leftarrow \pi_{eid,\,pno}(WORKS\_ON)$$ $$Result \leftarrow \pi_{ename}\Big( \big( \text{EmpProj} \div \text{ProjDno10}\big) \bowtie EMPLOYEE \Big)$$

The division returns exactly those eid values that pair with all project numbers controlled by department 10.

Three-Schema (ANSI/SPARC) Architecture (6)

The architecture separates a user's view of data from how it is physically stored, organised in three levels:

        ┌──────────────────────────────────────┐
        │  External level  (View 1)(View 2)...  │  ← many user views
        └──────────────────────────────────────┘
                     ↑  external/conceptual mapping
        ┌──────────────────────────────────────┐
        │  Conceptual level (logical schema)    │  ← whole DB, entities, relations
        └──────────────────────────────────────┘
                     ↑  conceptual/internal mapping
        ┌──────────────────────────────────────┐
        │  Internal level (physical schema)     │  ← files, indexes, storage layout
        └──────────────────────────────────────┘

• External (View) level: describes the part of the database relevant to a particular user/application; hides the rest. Multiple views can exist over one conceptual schema.
• Conceptual (Logical) level: describes what data is stored and the relationships among it for the whole community of users — entities, attributes, constraints — independent of physical storage.
• Internal (Physical) level: describes how data is physically stored — file organisation, record formats, indexes, access paths.

Data independence

• Logical data independence: the ability to change the conceptual schema (e.g. add an attribute or a new entity) without altering external views or application programs. (Harder to achieve in practice.)
• Physical data independence: the ability to change the internal schema (e.g. add an index, reorganise files, change storage device) without changing the conceptual schema or applications. (Easier to achieve.)

In short: physical independence insulates the logical design from storage changes, while logical independence insulates user views/programs from changes to the logical design.

Relational Algebra Operators (6)

Let STUDENT(sid, name, age, dept) and ENROLL(sid, course) be example relations.

(a) Selection (σ): chooses rows satisfying a predicate.

$$\sigma_{age > 20}(STUDENT)$$

returns all students older than 20.

(b) Projection (π): chooses columns (and removes duplicates).

$$\pi_{name,\,dept}(STUDENT)$$

returns only the name and dept of each student.

(c) Natural join (⋈): combines two relations on all common attributes, keeping matching tuples once.

$$STUDENT \bowtie ENROLL$$

joins on the common attribute sid, producing (sid, name, age, dept, course) for matching students.

(d) Division (÷): Given $R(X,Y) \div S(Y)$, returns the X-values in R that are associated with every Y-value in S.

$$\pi_{sid,\,course}(ENROLL) \div \pi_{course}(\sigma_{required}(COURSE))$$

returns the students enrolled in all required courses.

Why division answers 'for all' queries

Queries of the form "find X that are related to all Y" (universal quantification, ∀) map directly to division: division keeps exactly those X whose set of associated Y-values is a superset of S. SQL has no direct ÷ operator, so such queries are written with double NOT EXISTS or EXCEPT, but division expresses the same "for all" semantics concisely in relational algebra.

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

A clustered index stores rows in key order so range scans read sequential blocks; a secondary index gives an alternate access path but its matching rows are scattered across the file.

Why B+-tree is preferred over B-tree

• In a B-tree, keys and data pointers are stored in all nodes (internal + leaf). In a B+-tree, all data/record pointers reside only in the leaf nodes; internal nodes hold only keys for routing.
• Because internal nodes carry no data pointers, each B+-tree node holds more keys, giving a higher fan-out and shorter height ⇒ fewer disk I/Os per lookup.
• Leaf-node linkage: the leaves of a B+-tree are chained together in a linked list in sorted order. For a range query (e.g. salary BETWEEN 30000 AND 60000) one descent finds the lower bound, then the query simply follows the leaf-level links sequentially until the upper bound — no repeated root-to-leaf traversals. A plain B-tree must do an in-order traversal jumping between levels, which is slower.
• B+-trees also give uniform search cost (every search reaches a leaf), simplifying performance prediction.

These properties make the B+-tree the standard index structure in database systems.

Deadlock (6)

A deadlock is a situation in which two or more transactions are each waiting for a data-item lock held by another, forming a cycle of waiting so that none can ever proceed.

Example: T1 holds lock on A and requests B; T2 holds lock on B and requests A — both wait forever.

Timestamp-based deadlock-prevention schemes use each transaction's timestamp TS(T) (older transaction ⇒ smaller timestamp ⇒ higher priority). When transaction Ti requests a lock held by Tj, the system decides whether Ti waits or someone is rolled back, in a way that can never form a cycle.

Wait-Die (non-preemptive)

When Ti requests an item held by Tj:

• If TS(Ti) < TS(Tj) (Ti is older): Ti is allowed to wait.
• If TS(Ti) > TS(Tj) (Ti is younger): Ti dies (is rolled back) and restarts later with its same timestamp.

Rolled back: the younger requesting transaction. "Older waits, younger dies."

Wound-Wait (preemptive)

When Ti requests an item held by Tj:

• If TS(Ti) < TS(Tj) (Ti is older): Ti wounds Tj — Tj is rolled back (preempted), and Ti gets the item.
• If TS(Ti) > TS(Tj) (Ti is younger): Ti waits.

Rolled back: the younger held transaction (Tj). "Older wounds, younger waits."

In both schemes only younger transactions are ever aborted, so a waiting cycle can never form (waits always go from younger→older or older→younger consistently), guaranteeing no deadlock. Restarting with the original timestamp prevents starvation, since a transaction eventually becomes the oldest.

Log-Based Recovery (6)

A log is an append-only sequence of records on stable storage describing every database modification, written before the change reaches the database (Write-Ahead Logging). A typical update record is <Ti, X, old_value, new_value>, along with <Ti start> and <Ti commit> markers.

Deferred modification

• Updates are recorded in the log but not applied to the database until the transaction commits.
• On crash recovery, only REDO is needed: redo all transactions having both <Ti start> and <Ti commit> in the log. Transactions without a commit are simply ignored (their changes never reached the DB).
• Log record needs only the new value.

Immediate modification

• Updates may be written to the database before commit, but the log record is forced to disk first (WAL).
• Recovery may need both UNDO and REDO:
  • REDO transactions that have <Ti commit> (re-apply new values).
  • UNDO transactions that have <Ti start> but no <Ti commit> (restore old values), in reverse order.
• Log record stores both old and new values.

Checkpoints

A <checkpoint> record is written periodically after flushing all log records and modified buffer blocks to disk. It bounds the amount of log that must be examined: during recovery the system scans backwards to the most recent checkpoint instead of the entire log. Transactions that committed before the checkpoint need no work; only transactions active at or after the checkpoint are considered.

Recovery procedure after a crash (immediate modification)

1. Scan the log backward to the last <checkpoint>.
2. Build two lists: REDO-list = transactions with a commit record; UNDO-list = transactions started but not committed.
3. UNDO the UNDO-list transactions (restore old_values, scanning backward), then REDO the REDO-list transactions (re-apply new_values, scanning forward).

This restores the database to the last consistent committed state while discarding the effects of incomplete transactions.

DDL vs DML (6)

DDL example: CREATE TABLE STUDENT(sid INT PRIMARY KEY, name VARCHAR(50)); DML example: INSERT INTO STUDENT VALUES (1, 'Ram'); and SELECT * FROM STUDENT;

Integrity constraints

• PRIMARY KEY — uniquely identifies each row; values must be unique and NOT NULL. One per table.
• FOREIGN KEY — a column referencing the primary key of another (or same) table; enforces referential integrity (a child value must exist in the parent).
• UNIQUE — values in the column(s) must all be distinct, but (unlike PK) NULLs are allowed and a table may have several UNIQUE constraints.
• CHECK — enforces a Boolean condition on each row, e.g. CHECK (salary > 0); rows violating it are rejected.

ON DELETE CASCADE

A referential action on a foreign key: when a referenced (parent) row is deleted, all child rows that reference it are automatically deleted too, preserving referential integrity. Example: deleting a DEPARTMENT row with FOREIGN KEY(dno) REFERENCES DEPARTMENT ON DELETE CASCADE on EMPLOYEE will also delete that department's employees. (Alternatives include ON DELETE SET NULL and ON DELETE RESTRICT/NO ACTION.)

Goals of Database Security (6)

The three main goals (the CIA triad applied to data):

1. Confidentiality / Secrecy — protect data from unauthorised disclosure.
2. Integrity — allow only authorised, valid modifications; prevent improper alteration.
3. Availability — ensure authorised users can access data when needed (no denial of service).

Supporting goals include authentication (verifying identity) and authorization/access control (restricting what an authenticated user may do).

Discretionary Access Control (DAC) with GRANT / REVOKE

In DAC, the owner of an object grants/revokes privileges (SELECT, INSERT, UPDATE, DELETE, etc.) to other users at their discretion.

-- Give Ram read and insert rights on STUDENT
GRANT SELECT, INSERT ON STUDENT TO Ram;

-- Allow Ram to further pass on the privilege
GRANT SELECT ON STUDENT TO Sita WITH GRANT OPTION;

-- Take back the privilege
REVOKE INSERT ON STUDENT FROM Ram;

WITH GRANT OPTION lets the grantee re-grant the privilege; REVOKE removes it (and, with CASCADE, dependent grants).

SQL Injection and prevention

SQL injection is an attack where malicious SQL is inserted into an application input that is concatenated directly into a query, altering its logic. Example: a login query ... WHERE user = '$u' AND pass = '$p' with input ' OR '1'='1 becomes always-true, bypassing authentication (and can be used to read or destroy data).

Prevention: use parameterized queries / prepared statements (bind variables), which send user input as data, never as executable SQL, so the injected text cannot change the query structure. (Input validation and least-privilege accounts are additional defences.)

Anomalies in an un-normalized relation (6)

Consider one table storing student, course and instructor data together (each course has one instructor):

ENROLL(sid, sname, course, instructor, office)

Here the same instructor/office is repeated for every student of a course (redundancy), causing three anomalies:

• Insertion anomaly: We cannot insert a new course and its instructor (e.g. "AI taught by Dr. Rai") until at least one student enrolls, because sid (part of the key) would be NULL. Similarly, a new student with no course can't be added cleanly.
• Deletion anomaly: If the only student of a course leaves and we delete that row, we lose the instructor/office information for that course unintentionally.
• Update anomaly: If Dr. Shah's office changes, we must update every row for the DBMS course. Missing any row leaves the data inconsistent (same instructor with two offices).

How normalization removes them

Decompose into smaller relations so each fact is stored once:

STUDENT( sid, sname )
COURSE ( course, instructor, office )    -- course → instructor, office
ENROLL ( sid, course )                   -- key (sid, course)

Now:

• A new course+instructor is inserted into COURSE without needing a student ⇒ no insertion anomaly.
• Removing the last enrollment only deletes an ENROLL row; COURSE still holds the instructor ⇒ no deletion anomaly.
• An instructor's office is stored once in COURSE ⇒ a single update keeps data consistent ⇒ no update anomaly.

This is achieved by removing the partial/transitive dependencies (e.g. course → instructor, office) through normalization to 2NF/3NF.

EER concepts (6)

Specialization is a top-down process of defining subclasses (subtypes) of a higher-level entity set (superclass) based on some distinguishing characteristic. Example: EMPLOYEE is specialized into SECRETARY, ENGINEER, MANAGER. Subclasses inherit the superclass attributes and may have their own (e.g. ENGINEER has engineering_type).

Generalization is the inverse, bottom-up process: combining several entity sets sharing common features into a single higher-level superclass. Example: CAR and TRUCK are generalized into VEHICLE (sharing reg_no, max_speed).

Aggregation treats a relationship (and its participating entities) as a higher-level entity, so it can take part in another relationship. Example: the relationship WORKS_ON between EMPLOYEE and PROJECT is aggregated so that a MANAGER can be related (via MANAGES) to that whole works-on relationship — avoiding an invalid relationship among relationships.

Specialization constraints

A specialization is described by two pairs of constraints:

Disjointness constraint:

• Disjoint (d): an entity can belong to at most one subclass. Example: an ACCOUNT is either SAVINGS or CURRENT, not both.
• Overlapping (o): an entity may belong to more than one subclass simultaneously. Example: a PERSON who is both an EMPLOYEE and a STUDENT.

Completeness (participation) constraint:

• Total (double line): every superclass entity must belong to some subclass. Example: every EMPLOYEE must be a FULL_TIME or PART_TIME employee.
• Partial (single line): a superclass entity may belong to no subclass. Example: a VEHICLE might be neither CAR nor TRUCK (e.g. a motorcycle not yet specialized).

Illustration: In a BANK ACCOUNT specialized into SAVINGS and CURRENT with a {disjoint, total} constraint, every account is exactly one of the two types; making it {overlapping, partial} would instead allow an account to be both types or neither.