Database Management System 2021 Board Question Paper

How Database Processing Solves Data Redundancy

In traditional file processing systems, each department or application maintains its own private, isolated files. This causes identical pieces of data (e.g., student address) to be duplicated across multiple independent files, leading to storage waste and data inconsistency.

DBMS Solution:

1. Centralized Data Repository: All data is integrated into a unified database schema controlled by the DBMS. Multiple application modules access the exact same shared physical tables.
2. Controlled/Minimal Redundancy: Where duplication is required for performance (such as foreign keys), the DBMS maintains consistency automatically through foreign key referential integrity constraints.
3. Single Source of Truth: An update made in one table (e.g., updating customer address) is immediately reflected across all reporting views, eliminating contradictory records.

Responsibilities of a Database Administrator (DBA)

A Database Administrator (DBA) is the person or group responsible for the centralized operational control, configuration, maintenance, and security of the entire database system.

Key Responsibilities:

1. Schema Definition & Modification: Designing and creating conceptual, physical, and external database schemas using DDL statements.
2. Storage Structure & Access Method Definition: Configuring physical file allocations, tablespaces, indexing strategies, and clustering parameters.
3. Granting User Authorization & Security: Assigning roles, usernames, passwords, and fine-grained permissions (GRANT/REVOKE) to prevent unauthorized data access.
4. Integrity Constraint Specification: Enforcing domain constraints, primary keys, foreign keys, and business validation rules.
5. Backup and Disaster Recovery: Formulating routine automated backup schedules and executing restoration procedures following system failures.

Purpose of Storage Manager in a DBMS

The Storage Manager is a critical system module in the DBMS engine that provides the operational interface between the low-level data stored on physical disks (raw disk blocks) and the high-level application queries and transactions submitted to the system.

Key Functions:

1. Buffer Management: Allocates and manages main memory RAM cache (buffer pool) to minimize expensive physical disk I/O operations.
2. File & Record Organization: Manages physical space allocation on block devices and maintains internal record layouts and free-space maps.
3. Indexing: Manages B+ tree and hash index structures for rapid record retrieval.
4. Transaction Logging: Interfaces with the transaction manager to write Write-Ahead Log (WAL) records for crash recovery.

Binary and Ternary Relationships with Examples

The degree of a relationship refers to the number of participating entity sets:

1. Binary Relationship (Degree = 2):

Associates instances from two entity sets.

• Example: Employee Works_In Department.
  • Entities: Employee, Department
  • Relationship: Works_In

2. Ternary Relationship (Degree = 3):

Simultaneously associates instances from three distinct entity sets.

• Example: Vendor Supplies Part to a Project.
  • Entities: Vendor, Part, Project
  • Relationship: Supplies (signifies that a specific vendor supplies a particular part specifically for a given project).

Two Types of Participation Constraints in ER Modeling

Participation constraint specifies whether the existence of an entity depends on its being related to another entity via the relationship set:

1. Total (Mandatory) Participation:

• Definition: Every single entity instance in the entity set must participate in at least one relationship instance in the relationship set.
• ER Notation: Represented by a double line connecting the entity set rectangle to the relationship diamond.
• Example: Every Loan entity must be associated with at least one Customer.

2. Partial (Optional) Participation:

• Definition: Some entity instances in the entity set may not participate in any relationship instance.
• ER Notation: Represented by a standard single line.
• Example: Not every Customer must have taken a Loan (some may only maintain deposit accounts).

Concept of Lossless-Join Decomposition

A decomposition of a relational schema (R) into two sub-schemas (R_1) and (R_2) is termed lossless-join (or non-additive join) if joining the two projected relations with natural join ((\bowtie)) guarantees exact reconstruction of the original relation (R) without generating any spurious (false) tuples:

$$R_1 \bowtie R_2 = R$$

Formal Mathematical Condition:

The decomposition is lossless with respect to a set of functional dependencies (F) if and only if the common attribute(s) forms a superkey for at least one of the decomposed relations:

$$(R_1 \cap R_2) \longrightarrow R_1 \quad \text{OR} \quad (R_1 \cap R_2) \longrightarrow R_2$$

Definition of Deletion Anomaly

A Deletion Anomaly is an unintended, undesirable consequence of unnormalized relational database design where the deletion of one specific piece of factual data causes the involuntary, permanent loss of other completely unrelated valid data.

Example:

Consider an unnormalized table:

$$\text{CourseEnrollment}(\underline{\text{StudentID}}, \text{StudentName}, \text{CourseID}, \text{CourseName}, \text{Faculty})$$

• If a student is the only enrollee in a specialized course (e.g., “Advanced AI”), deleting that student’s enrollment record from the table also inadvertently deletes the course’s existence, title, and faculty details from the university system.

Concept of Embedded SQL

Embedded SQL refers to the inclusion of hard-coded SQL Data Manipulation (DML) and Data Definition (DDL) statements directly inside the source code of a general-purpose host programming language (such as C, C++, COBOL, or Java).

Key Characteristics:

1. Preprocessor Directives: In C/C++, embedded SQL statements are prefixed by EXEC SQL and terminated by a semicolon ;.
2. Host Variables: Uses host programming language variables (prefixed with a colon :) to pass data parameters into SQL queries and receive result column values.
3. Cursor Mechanism: Uses cursors to iterate row-by-row over multi-row SQL result sets, bridging the impedance mismatch between set-oriented SQL and procedural record-at-a-time host languages.

Two Pitfalls (Problems) of Lock-Based Protocols

While lock-based concurrency control protocols ensure serializability, they suffer from two major operational problems:

1. Deadlock:

   • Occurs when two or more transactions are in a circular wait state, each holding a lock on a data item that another transaction requires to proceed (e.g., (T_1) holds lock on (A) waiting for (B); (T_2) holds lock on (B) waiting for (A)).
   • Neither transaction can proceed, requiring the DBMS to detect the cycle and abort/rollback one transaction.

2. Starvation (Livelock):

   • Occurs when a transaction repeatedly waits indefinitely for a lock on a data item because a continuous succession of other higher-priority transactions are granted conflicting locks before it.

Definition of Atomicity with Example

Atomicity is the “all-or-nothing” property of database transactions (the ‘A’ in ACID). It guarantees that either all operations belonging to the transaction execute to successful completion and commit, or if any failure occurs, the entire transaction is completely aborted and rolled back, leaving the database unchanged.

Practical Banking Example:

Suppose Rs. 5,000 is transferred from Account A to Account B:

1. Read(A)
2. A = A - 5000
3. Write(A)
4. --- System Crash / Power Failure occurs here ---
5. Read(B)
6. B = B + 5000
7. Write(B)

• Under Atomicity: The transaction manager detects the crash at Step 4 and undoes Steps 1–3, restoring Account A to its original balance. Money is never deducted from A without being credited to B.

Entity-Relationship (ER) Diagram for Bus Ticketing System

1. Identified Entities and Attributes:

1. Driver: DriverID (PK), Name, LicenseNo, ContactNo.
2. Bus: BusNo (PK), PlateNo, Capacity, Model.
3. Customer: CustomerID (PK), Name, Phone, Email.
4. Ticket: TicketNo (PK), SeatNo, Source, Destination, Fare, TravelDate, Status.

2. Relationships & Structural Constraints:

• Drives: Between Driver and Bus (1:1 or 1:N cardinality; a driver drives a designated bus).
• Books / Has: Between Customer and Ticket (1:N; a customer must have at least one ticket to travel; Total participation).
• Validates / Checks: Between Driver and Ticket (1:N; driver verifies validity of customer tickets).
• Assigned_To: Between Ticket and Bus (N:1; ticket is issued for a specific bus).

3. ER Diagram Representation:

  +------------+             +------------+             +------------+
  |   Driver   |---(Drives)--|    Bus     |<---(For)---|   Ticket   |
  +------------+             +------------+             +------------+
        |                                                     ^
        |                                                     |
        +-------------------(Validates)-----------------------+
                                                              ^
                                                              |
                                                           (Has)
                                                              |
                                                        +------------+
                                                        |  Customer  |
                                                        +------------+

SQL DDL Statement to Create the “Football Team” Table

CREATE TABLE Football_Team (
    Team_ID VARCHAR(10) NOT NULL,
    Team_Name VARCHAR(20) NOT NULL,
    Rank INT NOT NULL,
    Goal_Score INT NOT NULL,
    GoalConsided INT NOT NULL,
    No_of_players INT NOT NULL,

    -- Table Constraints
    CONSTRAINT PK_FootballTeam PRIMARY KEY (Team_ID),
    CONSTRAINT CHK_TeamRank CHECK (Rank >= 0),
    CONSTRAINT CHK_GoalScore CHECK (Goal_Score >= 0),
    CONSTRAINT CHK_GoalConsided CHECK (GoalConsided >= 0),
    CONSTRAINT CHK_PlayerCount CHECK (No_of_players >= 11 AND No_of_players <= 25)
);

Explanation of Schema Constraints:

• VARCHAR(10) alphanumeric data type chosen for Team_ID with PRIMARY KEY enforcing uniqueness and NOT NULL.
• Team_Name VARCHAR(20) enforces character limit not exceeding 20.
• Rank, Goal_Score, and GoalConsided enforce NOT NULL and non-negative values (>= 0).
• No_of_players enforces the required range from 11 to 25 inclusive via CHECK constraint.

SQL Queries for Author, Publishes, and Book Schema

Schema:

• Author (AID, A_Name, Age, Address, country)
• Publishes (AID, BID, publisheddate)
• Book (BID, B_name, page, price)

---

a) Find the Name of Author who is NOT from ‘Nepal’:

SELECT A_Name
FROM Author
WHERE country <> 'Nepal';

---

b) Find the number of books written by each author:

SELECT A.AID, A.A_Name, COUNT(P.BID) AS Total_Books_Written
FROM Author A
LEFT JOIN Publishes P ON A.AID = P.AID
GROUP BY A.AID, A.A_Name;

---

c) Find the name of Author who has published the most expensive book:

SELECT DISTINCT A.A_Name
FROM Author A
JOIN Publishes P ON A.AID = P.AID
JOIN Book B ON P.BID = B.BID
WHERE B.price = (SELECT MAX(price) FROM Book);

---

d) Insert the detail of a new Author:

INSERT INTO Author (AID, A_Name, Age, Address, country)
VALUES (101, 'Parijat', 56, 'Kathmandu', 'Nepal');

Finding Candidate Key for Relation Schema $R$

Given Schema:

$$R = \{E, F, G, H, I, J, K, L, M, N\}$$

Functional Dependencies ($FDs$):

1. {E, F} -> {G}
2. {F} -> {I, J}
3. {E, H} -> {K, L}
4. {K} -> {M}
5. {L} -> {N}

Step 1: Identify Attributes Not Appearing on Any Right-Hand Side (RHS)

• Attributes appearing on the RHS: G, I, J, K, L, M, N
• Attributes never appearing on the RHS: E, F, H

Conclusion: Since E, F, and H are never determined by any other attribute, they must be part of every candidate key.

Step 2: Compute Attribute Closure of ${E, F, H}$

• {E, F, H}^+ = {E, F, H}
• By FD 1 ({E, F} -> {G}): {E, F, H, G}
• By FD 2 ({F} -> {I, J}): {E, F, H, G, I, J}
• By FD 3 ({E, H} -> {K, L}): {E, F, H, G, I, J, K, L}
• By FD 4 ({K} -> {M}): {E, F, H, G, I, J, K, L, M}
• By FD 5 ({L} -> {N}): {E, F, H, G, I, J, K, L, M, N} = R

Since {E, F, H}^+ determines all attributes in (R) and no proper subset of {E, F, H} can determine (R):

$$\mathbf{\text{Candidate Key for } R = \{E, F, H\}}$$

Normalizing Employee Relation Up to BCNF

Given unnormalized Employee table:

• Columns: E-ID, E-name, Contact No, Post, Salary
• Data has multi-valued contact numbers (e.g., 98405, 21325).

Step 1: Normalization to First Normal Form (1NF)

• Violation in raw table: Contact No contains multi-valued non-atomic values.
• 1NF Rule: Every column must contain only atomic (indivisible) values.
• Resolution: Flatten rows so each cell holds exactly one phone number:

Composite Primary Key for 1NF: {E-ID, Contact_No}.

Step 2: Normalization to 2NF & 3NF

• Functional Dependencies:
  • E-ID -> E-name, Post, Salary (Partial dependency on composite key {E-ID, Contact_No}).
  • Post -> Salary (Transitive dependency).

Decompose into 3NF:

1. Employee (E-ID, E-name, Post) with PK: E-ID.
2. Employee_Phone (E-ID, Contact_No) with composite PK: {E-ID, Contact_No} and FK: E-ID.
3. Job_Post (Post, Salary) with PK: Post.

Step 3: Normalization to BCNF (Boyce-Codd Normal Form)

• BCNF Requirement: For every functional dependency (X \rightarrow Y), (X) must be a superkey.
• In all three relations:
  • Employee: Determinant E-ID is candidate key (\rightarrow) in BCNF.
  • Employee_Phone: Key is {E-ID, Contact_No}, no non-trivial FDs (\rightarrow) in BCNF.
  • Job_Post: Determinant Post is candidate key (\rightarrow) in BCNF.

$$\mathbf{\text{Final BCNF Schemas: Employee}(\underline{\text{E-ID}}, \text{E-name}, \text{Post}), \; \text{EmpPhone}(\underline{\text{E-ID}, \text{Contact\_No}}), \; \text{JobSal}(\underline{\text{Post}}, \text{Salary})}$$

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

1. Why Concurrency Control is Needed:

When multiple database transactions execute concurrently, uncoordinated interleaved operations on shared data items lead to anomalies:

• Lost Updates
• Dirty Reads (Temporary Update)
• Unrepeatable / Inconsistent Reads

---

2. Two-Phase Locking (2PL) Protocol:

2PL guarantees conflict serializability by requiring each transaction to acquire and release locks in two distinct phases:

1. Growing Phase: A transaction may acquire locks of any type (Shared S or Exclusive X), but may not release any lock.
2. Lock Point: The moment when the transaction has acquired the final lock it requires.
3. Shrinking Phase: A transaction may release locks, but may not acquire any new lock.

---

3. Scenario Management:

Given accounts: (A = 5500, B = 4500, C = 2000).

• (T_1): Transfer Rs. 500 from A to B:
  1. Lock-X(A) (Growing)
  2. Read(A) (\rightarrow A = 5500 - 500 = 5000), Write(A)
  3. Lock-X(B) (Growing)
  4. Read(B) (\rightarrow B = 4500 + 500 = 5000), Write(B)
  5. Unlock(A) (Shrinking begins)
  6. Unlock(B)
• By strictly growing locks before releasing any lock, serializability is maintained, ensuring consistency across accounts.

Database Application Architectures

Database application architecture defines how the database engine, application logic, and user interface components are partitioned and distributed across computing hardware:

1. Teleprocessing (1-Tier / Centralized) Architecture:

• All processing—user interface display, business logic execution, and DBMS operations—runs on a single central mainframe computer.
• Users interact via simple dumb display terminals.

2. Two-Tier Client-Server Architecture:

• Client Tier: Runs the User Interface and application logic (Fat Client). Communicates with the server via database connectivity APIs (JDBC, ODBC).
• Server Tier: Runs the DBMS software responsible for query evaluation, transaction control, and disk storage.
• Advantage: Offloads UI processing to client workstations.
• Disadvantage: High network traffic and maintenance cost when updating client software on hundreds of machines.

3. Three-Tier Web Architecture:

• Presentation Tier (Client): Thin client running in a web browser (HTML5, CSS, Vue/Nuxt, JavaScript).
• Application Tier (Business Logic Server): Web/Application servers (Node.js, Spring Boot, Python) running business validation and workflows.
• Database Tier (Backend Server): Dedicated enterprise database server (PostgreSQL, Oracle, MySQL).
• Advantages: Highly scalable, secure (clients never connect directly to database), clean separation of concerns.