Dean's Office Official Model Question Paper

Answer: Data Independence: The capacity to modify a database schema at one level without affecting schemas at adjacent higher levels.

• Physical Data Independence: Ability to modify internal/physical storage structures (indexing, file organization) without changing the conceptual schema.
• Logical Data Independence: Ability to modify the conceptual schema (adding columns, tables) without changing external schemas or application views.

Answer:

1. Atomicity: All transaction operations succeed completely, or none are applied (‘all-or-nothing’).
2. Consistency: A transaction transforms the database from one valid state to another, preserving all integrity constraints.
3. Isolation: Concurrent transactions execute without interfering with one another.
4. Durability: Once committed, transaction updates persist permanently, surviving system crashes.

Answer:

• Primary Key: A candidate key chosen to uniquely identify every tuple in a relation; cannot contain null values.
• Foreign Key: An attribute (or set of attributes) in one relation that matches the primary key of another relation, enforcing referential integrity between tables.

Answer: Weak Entity: An entity that does not possess sufficient attributes to form its own primary key and depends on the existence of an identifying strong entity. Identification: Identified by combining the primary key of its identifying strong entity with its own partial key (discriminator) via an identifying relationship.

Answer: Deadlock: A condition where two or more concurrent transactions are in a state of indefinite waiting because each holds a lock on a data item that another transaction requires. Prevention Technique: Wait-Die or Wound-Wait timestamp-based ordering schemes.

ANSI/SPARC Three-Schema Database Architecture

1. The Three Schema Levels

The architecture separates the database into three abstraction layers:

1. Internal (Physical) Level:

   • Closest to physical hardware storage.
   • Describes how data is physically stored on disk: data structures, record formats, B+ tree indexes, compression algorithms, and access paths.
   • Managed by database systems programmers and DBAs.

2. Conceptual (Logical) Level:

   • Represents the global view of the entire database for the entire organization.
   • Defines entities, data types, relationships, constraints, and business rules without regard to physical storage.
   • Defined using DDL by database designers.

3. External (View) Level:

   • Closest to end users.
   • Consists of multiple external schemas (views) tailored to specific user groups (e.g., HR view, Sales view, Student view).
   • Hides irrelevant or sensitive data (e.g., employee salaries hidden from departmental coworkers).

---

2. Mappings and Data Independence

• External-Conceptual Mapping: Maps external views to the global conceptual schema. Provides Logical Data Independence—the conceptual schema can be modified (e.g., adding an optional column) without altering existing application views.
• Conceptual-Internal Mapping: Maps conceptual relations to physical disk blocks and file indexes. Provides Physical Data Independence—the storage subsystem can be migrated from HDD to NVMe SSD or index re-built without altering the logical schema or user SQL queries.

SQL Queries for University Schema

a) Students majoring in ‘Management’ with GPA > 3.5:

SELECT Name, GPA
FROM Student
WHERE Major = 'Management' AND GPA > 3.5;

---

b) Total students enrolled in each course for ‘Fall 2024’:

SELECT C.CourseID, C.Title, COUNT(E.StudentID) AS TotalEnrolled
FROM Course C
LEFT JOIN Enrollment E ON C.CourseID = E.CourseID AND E.Semester = 'Fall 2024'
GROUP BY C.CourseID, C.Title;

---

c) Courses with zero student enrollments:

-- Using NOT EXISTS:
SELECT Title
FROM Course C
WHERE NOT EXISTS (
    SELECT 1
    FROM Enrollment E
    WHERE E.CourseID = C.CourseID
);

-- Alternative using LEFT JOIN:
SELECT C.Title
FROM Course C
LEFT JOIN Enrollment E ON C.CourseID = E.CourseID
WHERE E.StudentID IS NULL;

---

d) Update credits by +1 for ‘Computer Science’ courses:

UPDATE Course
SET Credits = Credits + 1
WHERE Department = 'Computer Science';

Boyce-Codd Normal Form (BCNF) vs. Third Normal Form (3NF)

1. Definitions

• 3NF Definition: A relation $R$ is in 3NF if for every functional dependency $X \to Y$:
  1. $X \to Y$ is a trivial dependency ($Y \subseteq X$), OR
  2. $X$ is a superkey of $R$, OR
  3. Each attribute in $Y - X$ is a prime attribute (part of some candidate key).
• BCNF Definition: A relation $R$ is in BCNF if for every non-trivial functional dependency $X \to Y$, $X$ must be a superkey of $R$. (BCNF eliminates the prime attribute exception of 3NF).

---

2. Illustrative Example: 3NF Satisfied but BCNF Violated

Consider relation $R(\text{Student}, \text{Subject}, \text{Teacher})$ with rules:

1. A student takes multiple subjects, each taught by a specific teacher: $(\text{Student}, \text{Subject}) \to \text{Teacher}$.
2. Each teacher teaches only one subject: $\text{Teacher} \to \text{Subject}$.
3. A subject may have multiple teachers.

• Candidate Keys: $(\text{Student}, \text{Subject})$ and $(\text{Student}, \text{Teacher})$.
• Prime Attributes: $\{\text{Student}, \text{Subject}, \text{Teacher}\}$.

Check 3NF:

• For $(\text{Student}, \text{Subject}) \to \text{Teacher}$: LHS is a superkey (Satisfies).
• For $\text{Teacher} \to \text{Subject}$: LHS is not a superkey, but RHS ($\text{Subject}$) is a prime attribute! Thus, the relation is in 3NF.

Check BCNF:

• In $\text{Teacher} \to \text{Subject}$, $\text{Teacher}$ is NOT a superkey.
• Therefore, the relation violates BCNF. (Anomaly: We cannot record which teacher teaches a subject until a student enrolls).

---

3. Lossless Decomposition into BCNF

Decompose $R$ into two relations:

1. $R_1(\underline{\text{Teacher}}, \text{Subject})$ with FD: $\text{Teacher} \to \text{Subject}$. (Teacher is a superkey; in BCNF).
2. $R_2(\underline{\text{Student}, \text{Teacher}})$ with composite key $(\text{Student}, \text{Teacher})$. (In BCNF).

The decomposition is lossless ($R_1 \cap R_2 = \{\text{Teacher}\}$, which is a key for $R_1$), eliminating redundancy.

Concurrency Control: Two-Phase Locking (2PL) Protocol

1. Core Principles of 2PL

The Two-Phase Locking protocol ensures conflict serializability by constraining when a transaction can acquire and release locks:

• Phase 1: Growing Phase (Lock Acquisition): A transaction may acquire locks (shared or exclusive) but cannot release any lock.
• Phase 2: Shrinking Phase (Lock Release): A transaction may release locks, but once it releases any lock, it can never acquire any new lock.
• Lock Point: The moment when the transaction holds its maximum number of locks (end of Growing Phase). The ordering of lock points determines the equivalent serial schedule.

---

2. Variants of 2PL

1. Basic 2PL:
   • Locks are released gradually during the shrinking phase before transaction commit.
   • Problem: Vulnerable to cascading aborts (if transaction $T_1$ modifies item $X$, releases lock, and then aborts, any $T_2$ that read $X$ must also abort).
2. Strict 2PL:
   • Mandates that all exclusive (write) locks must be held until the transaction explicitly commits or aborts.
   • Prevents cascading aborts and guarantees strict schedules.
3. Rigorous (Strong Strict) 2PL:
   • Mandates that all locks (both shared read locks and exclusive write locks) must be held until the transaction terminates (commit/abort).
   • Guarantees that transactions serialize in the exact order in which they commit.

---

3. Proof that 2PL Guarantees Conflict Serializability

If a schedule produced by 2PL were non-serializable, its precedence graph would contain a cycle ($T_1 \to T_2 \to \dots \to T_1$). An edge $T_1 \to T_2$ implies $T_1$ accessed a data item before $T_2$, meaning $T_1$ released a lock before $T_2$ acquired it. A cycle would require $T_1$ to release a lock before acquiring another lock, directly violating the 2PL rule that no locks can be acquired after any lock is released.

Comprehensive Database Case Solution: YatriRide Platform

a) Conceptual ER Diagram & Cardinality Specifications

• Entities & Cardinalities:
  • Passenger (1) —— (0..N) Trip [One passenger books zero or many trips; each trip belongs to exactly one passenger]
  • Driver (1) —— (1) Vehicle [Each driver is registered with exactly one vehicle]
  • Driver (1) —— (0..N) Trip [One driver completes zero or many trips; each accepted trip is assigned to one driver]
  • Trip (1) —— (1) Payment [Each completed trip has exactly one associated payment record]

---

b) Normalized Relational Database Schema (3NF)

1. Passenger Table:

   • PassengerID INT PRIMARY KEY AUTO_INCREMENT
   • FullName VARCHAR(100) NOT NULL
   • PhoneNumber VARCHAR(15) UNIQUE NOT NULL
   • Email VARCHAR(100)
   • WalletBalance DECIMAL(10, 2) DEFAULT 0.00 CHECK (WalletBalance >= 0)

2. Driver Table:

   • DriverID INT PRIMARY KEY AUTO_INCREMENT
   • FullName VARCHAR(100) NOT NULL
   • LicenseNumber VARCHAR(50) UNIQUE NOT NULL
   • Phone VARCHAR(15) UNIQUE NOT NULL
   • Rating DECIMAL(3, 2) DEFAULT 5.00
   • Status ENUM(‘Available’, ‘OnTrip’, ‘Offline’) DEFAULT ‘Offline’

3. Vehicle Table:

   • VehicleID INT PRIMARY KEY AUTO_INCREMENT
   • DriverID INT UNIQUE NOT NULL, FOREIGN KEY (DriverID) REFERENCES Driver(DriverID)
   • RegistrationNumber VARCHAR(30) UNIQUE NOT NULL
   • MakeModel VARCHAR(100) NOT NULL
   • Category ENUM(‘Bike’, ‘Car’, ‘EV-Van’) NOT NULL

4. Trip Table:

   • TripID BIGINT PRIMARY KEY AUTO_INCREMENT
   • PassengerID INT NOT NULL, FOREIGN KEY (PassengerID) REFERENCES Passenger(PassengerID)
   • DriverID INT NULL, FOREIGN KEY (DriverID) REFERENCES Driver(DriverID)
   • PickupLocation VARCHAR(255) NOT NULL
   • DropLocation VARCHAR(255) NOT NULL
   • FareAmount DECIMAL(10, 2) NOT NULL
   • TripStatus ENUM(‘Requested’, ‘Accepted’, ‘Completed’, ‘Cancelled’) DEFAULT ‘Requested’
   • CreatedAt TIMESTAMP DEFAULT CURRENT_TIMESTAMP

5. Payment Table:

   • PaymentID BIGINT PRIMARY KEY AUTO_INCREMENT
   • TripID BIGINT UNIQUE NOT NULL, FOREIGN KEY (TripID) REFERENCES Trip(TripID)
   • PaymentMethod ENUM(‘eSewa’, ‘Khalti’, ‘Cash’, ‘Wallet’) NOT NULL
   • Amount DECIMAL(10, 2) NOT NULL
   • PaymentTime TIMESTAMP DEFAULT CURRENT_TIMESTAMP

---

c) Diagnosis of Double-Booking and Atomic Concurrency Solution

1. Diagnosis:

   • A classic Race Condition (Lost Update / Phantom Update): Two drivers query the database simultaneously when TripStatus = 'Requested'. Both read the row before either updates it, and both issue UPDATE Trip SET DriverID = ?, TripStatus = 'Accepted' WHERE TripID = ?, resulting in a double-booking collision.

2. Atomic Transaction Solution using Pessimistic Locking (FOR UPDATE):

START TRANSACTION;

-- Lock the specific trip row against concurrent reader-writers:
SELECT TripID, TripStatus
FROM Trip
WHERE TripID = 10052
FOR UPDATE;

-- Verify within the locked context that the trip is still unassigned:
-- (Application logic checks: IF TripStatus == 'Requested')
UPDATE Trip
SET DriverID = 402,
    TripStatus = 'Accepted'
WHERE TripID = 10052 AND TripStatus = 'Requested';

-- Update the accepting driver's operational status:
UPDATE Driver
SET Status = 'OnTrip'
WHERE DriverID = 402;

COMMIT;

Mechanism: The SELECT ... FOR UPDATE statement locks the specific trip row at the database storage engine level (row-level exclusive lock). If Driver B attempts to accept the same trip while Driver A’s transaction is in flight, Driver B’s query blocks until Driver A commits. Upon release, Driver B reads TripStatus = 'Accepted', preventing duplicate assignment.