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

A university wants to computerize its academic records. The system must store information about students (registration number, name, address, contact numbers — a student may have more than one contact number), courses (course code, title, credit hours), teachers (employee id, name, designation), and departments (department code, name). A department offers many courses and employs many teachers; each course is offered by exactly one department. A student enrolls in many courses and obtains a grade in each enrolled course. A course may be taught by one or more teachers in a given semester.

(a) Draw an Entity-Relationship (ER) diagram for the above scenario. Clearly show entity sets, attributes (including key, composite, and multivalued attributes), relationship sets, and cardinality/participation constraints. (10 marks)

(b) Reduce the ER diagram you have drawn into a set of relational schemas, underlining the primary keys and indicating the foreign keys. (6 marks)

Consider the relation R(A, B, C, D, E) with the set of functional dependencies

F = { A → BC, CD → E, B → D, E → A }.

(a) Compute the closure (A)^+ and (B)^+ and hence list all candidate keys of R. (5 marks)

(b) Determine the highest normal form that R satisfies and justify your answer. (4 marks)

(c) Explain the difference between 3NF and BCNF. Decompose R into BCNF, stating clearly whether your decomposition is lossless-join and dependency-preserving. (7 marks)

(a) Define a schedule and explain the terms conflict serializability and view serializability with suitable examples. (6 marks)

(b) Consider the following schedule S of two transactions T1 and T2 on data items A and B:

T1: R(A)  W(A)        R(B)  W(B)
T2:           R(A) W(A)         

(time increases left to right). Draw the precedence (serialization) graph and determine whether S is conflict serializable. If serializable, give an equivalent serial schedule. (6 marks)

(c) Explain how the two-phase locking (2PL) protocol guarantees serializability. Why can basic 2PL still suffer from deadlock and cascading rollback, and how do strict 2PL and rigorous 2PL address this? (4 marks)

Consider the following relational database schema (primary keys underlined):

Employee(__eid__, ename, salary, dept_no, mgr_id)
Department(__dept_no__, dname, location)
Project(__pid__, pname, dept_no, budget)
WorksOn(__eid__, __pid__, hours)

(a) Write SQL queries for the following: (10 marks)

• (i) List the name and salary of all employees who work in the department located in 'Pokhara'.
• (ii) For each department, display the department name and the average salary of its employees, only for departments having more than 5 employees.
• (iii) Find the names of employees who work on every project controlled by department number 10.
• (iv) Give a 10% salary raise to all employees who work more than 40 hours in total across all projects.
• (v) List the name of each employee together with the name of their manager.

(b) Express queries (i) and (iii) above using relational algebra. (6 marks)

Explain the three-schema (ANSI/SPARC) architecture of a DBMS with a neat diagram. Distinguish between logical data independence and physical data independence, giving one example of each.

(a) Differentiate between a primary index, a clustering index, and a secondary index. (4 marks)

(b) A B+-tree of order p = 4 is to be built by inserting the keys 10, 20, 5, 30, 25, 15 in the given order. Show the structure of the B+-tree after all insertions, illustrating any node splits. (4 marks)

(a) State the ACID properties of a transaction and briefly explain each. (4 marks)

(b) Explain how a log-based recovery scheme using deferred update (NO-UNDO/REDO) recovers the database after a system crash. Illustrate using the log records of a sample transaction. (4 marks)

Define the following relational algebra operations and give one example of each: selection (σ), projection (π), natural join (⋈), and the division operation (÷). For each, state when you would use it in querying a relational database.

(a) What is a deadlock? Explain the wait-for graph method of deadlock detection with an example. (4 marks)

(b) Describe the timestamp-ordering protocol for concurrency control and explain how it ensures that conflicting operations are executed in timestamp order. (4 marks)

(a) Define partial dependency and transitive dependency, and explain how they relate to 2NF and 3NF respectively. (4 marks)

(b) Given the relation Order(order_id, cust_id, cust_name, item_id, item_name, qty), identify the anomalies present and normalize the relation up to 3NF, showing the resulting schemas. (4 marks)

(a) Explain discretionary access control (DAC) in databases and the role of the SQL GRANT and REVOKE statements, with examples. (4 marks)

(b) What is a checkpoint in database recovery, and how does it reduce the amount of work needed during recovery after a crash? (4 marks)

Explain the concepts of generalization, specialization, and aggregation in the Enhanced Entity-Relationship (EER) model, using a suitable example for each.