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

A university wants to computerize its academic records. The system must store information about Students (student id, name, address, multiple phone numbers, date of birth), Courses (course code, title, credit hours), and Instructors (employee id, name, department). The following rules apply:

• A student may enroll in many courses, and a course may have many students enrolled. For each enrollment the system records the semester and the obtained grade.
• A course is taught by exactly one instructor in a given semester, but an instructor may teach many courses.
• Each course may have zero or more prerequisite courses (which are themselves courses).
• Departments employ instructors; an instructor belongs to exactly one department.

(a) Draw a complete Entity-Relationship (ER) diagram for the above scenario. Clearly indicate entity sets, relationship sets, primary keys, cardinality ratios, participation constraints, and any composite/multivalued attributes. (8 marks)

(b) Identify any weak entity set or recursive relationship present in your design and justify your modeling choice. (4 marks)

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

F = { A -> BC,  CD -> E,  B -> D,  E -> A }

(a) Compute the closure {A}+ and {B}+, and find all candidate keys of R. (4 marks)

(b) Determine the highest normal form that R currently satisfies, justifying your answer with respect to 2NF, 3NF, and BCNF. (4 marks)

(c) Decompose R into BCNF. State whether your decomposition is dependency-preserving and lossless-join, and explain why. (4 marks)

(a) State and explain the ACID properties of a transaction with a suitable example for each property. (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)  
         (interleaved in the order: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B))

Draw the precedence (serialization) graph for schedule S and determine whether S is conflict-serializable. If it is, give an equivalent serial schedule. (6 marks)

Consider the following relational schema for an airline reservation database (primary keys underlined in description):

FLIGHT(flight_no, source, destination, departure_time, fare)
PASSENGER(pid, pname, age, city)
BOOKING(pid, flight_no, booking_date, seat_no)

(a) Write SQL statements for the following: (8 marks)

1. List the names of passengers who have booked a flight from 'Kathmandu' to 'Pokhara'.
2. For each source city, display the source and the average fare of flights departing from it, only for cities having more than 3 flights.
3. Find the names of passengers who have NOT made any booking.
4. Increase the fare by 10% for all flights whose destination is 'Biratnagar'.

(b) Write relational algebra expressions for queries (1) and (3) above. (4 marks)

Explain the three-schema (ANSI/SPARC) architecture of a DBMS. How does it achieve logical data independence and physical data independence?

Define entity integrity constraint and referential integrity constraint. With an example of two related tables, explain what actions a DBMS can take (CASCADE, SET NULL, RESTRICT) when a referenced tuple is deleted.

Differentiate between a primary (clustered) index and a secondary (non-clustered) index. Explain the difference between dense and sparse indexing with a diagram.

What is a B+ tree index? Construct a B+ tree of order 3 (i.e. maximum 3 pointers / 2 keys per node) by inserting the following keys in order: 8, 5, 1, 7, 3, 12, 9, 6. Show the tree after all insertions.

(a) What is the two-phase locking (2PL) protocol? Explain its growing and shrinking phases. (3 marks)

(b) How do strict 2PL and rigorous 2PL differ, and how do they help avoid cascading rollbacks? (3 marks)

Explain log-based recovery using deferred update and immediate update techniques. What is the role of checkpoints in reducing recovery time after a system crash?

What is a deadlock in a database system? Explain the wait-die and wound-wait deadlock prevention schemes based on transaction timestamps with an example of each.

Discuss database security with respect to authorization and access control. Explain how the SQL GRANT and REVOKE statements are used to manage privileges, and briefly describe role-based access control.

Explain the difference between the natural join and the theta join operations in relational algebra with a suitable example of each.