Database Management System

Definition of Database

A database is an organized, structured collection of logically related data, stored electronically in a computer system, designed to be easily accessed, managed, updated, and queried by multiple concurrent users and software applications while ensuring data integrity, minimal redundancy, and high security.

Concept of Queries in DBMS

A query is a formal request for data or information submitted to a Database Management System (DBMS) using a standardized query language such as Structured Query Language (SQL).

Key Functions:

• Data Retrieval: Extracting specific records from one or more tables matching defined criteria (e.g., SELECT statements).
• Data Manipulation: Filtering, sorting, grouping, aggregating, and joining data across tables.
• Action Queries: Executing updates, deletions, and insertions (DML).

Concept of Composite Key

A composite key (or composite primary key) is a primary key that consists of two or more attributes (columns) combined together to uniquely identify each tuple (row) within a relational table.

Operational Characteristics:

• Used when no single individual attribute in the table is sufficient on its own to guarantee uniqueness.
• Example: In a course enrollment table ENROLLMENT (StudentID, CourseID, Semester, Grade), neither StudentID nor CourseID alone is unique, but the combination (StudentID, CourseID) uniquely identifies each enrollment instance.

Two Advantages of Using a Centralized Database

1. Elimination of Data Redundancy and Enhanced Consistency:
   • Because all enterprise data is stored and managed at a single central physical server location, duplicate data entry is avoided, ensuring all departments access a single version of truth.
2. Simplified Security and Unified Administration:
   • Implementing security policies, user privilege controls, software updates, and automated disaster backups is straightforward since the entire database resides in a single, well-defended data center.

Concept of Data Independence

Data independence is the capacity of a database system to modify a schema definition at one level of the Three-Schema Architecture (Physical, Logical, View) without requiring alterations to schemas at higher levels.

Two Levels of Data Independence:

1. Logical Data Independence: The ability to modify the logical schema (e.g., adding or deleting a column or table) without having to alter external views or rewrite existing application programs.
2. Physical Data Independence: The ability to modify the physical storage structures (e.g., changing file formats, switching from HDD to SSD, adding B-Tree indexes) without impacting the logical conceptual schema.

Example of One-to-One (1:1) Relationship

A One-to-One (1:1) relationship occurs when an instance in Entity Set A is associated with at most one instance in Entity Set B, and vice versa.

Real-World Example:

• Citizen and National Identity Card (NID):
  • Entity A: CITIZEN (CitizenshipNo, Name, DateOfBirth)
  • Entity B: NATIONAL_ID_CARD (NID_CardNo, IssueDate, BiometricHash)
  • Relationship: Assigned
  • Constraint: Each Nepalese citizen is assigned exactly one unique National Identity Card, and each National Identity Card belongs to exactly one citizen.

Syntax of DELETE Statement in SQL

The DELETE statement is a Data Manipulation Language (DML) command used to remove existing rows from a database table based on specified conditional criteria:

DELETE FROM table_name WHERE condition;

Example:

DELETE FROM Customers WHERE Age < 18;

(Note: If the WHERE clause is omitted, all records in the table will be deleted, though the table structure itself remains intact).

Definition of Database Anomalies

Anomalies are unintended, problematic inconsistencies, errors, and structural defects that occur in un-normalized relational database tables containing redundant data when performing standard Data Manipulation Language (DML) operations:

• Insertion Anomaly: Inability to record certain facts without adding unrelated or dummy attributes.
• Deletion Anomaly: Accidental loss of critical business facts when deleting an unrelated attribute.
• Update Anomaly: Inconsistent data states resulting from updating some redundant records while leaving duplicates unchanged.

Definition of Transaction in DBMS

A transaction is a logical unit of database processing that includes one or more database operations (such as reading, inserting, updating, or deleting records). It is treated as an indivisible atomic action that must either execute completely or have no effect whatsoever, transitioning the database from one valid, consistent state to another while satisfying all ACID properties.

Definition of Database Recovery

Database recovery is the systematic process of restoring a database to its most recent consistent, correct, and operational state following a system failure, hardware crash, power outage, transaction abort, or storage corruption. It relies on transaction logs, checkpoints, and backup archives to perform UNDO (rollback uncommitted changes) and REDO (roll-forward committed updates) operations.

Classification of Database Users

Database Management Systems serve diverse user groups with varying technical proficiencies and operational requirements:

1. Database Administrator (DBA):

• The primary technical custodian of the database.
• Responsible for physical database design, user account provisioning, role-based authorization, performance monitoring, tuning, and disaster backup/recovery.

2. Database Designers (Architects):

• Design the conceptual and logical schemas before the database is implemented.
• Identify enterprise entities, relationships, attributes, primary keys, and integrity constraints, normalizing tables up to 3NF/BCNF.

3. Application Programmers (Software Engineers):

• Write application software (in Python, Java, C#, PHP) that interacts with the DBMS through APIs and embedded SQL (JDBC, ODBC).
• Develop user interfaces and execute transactions for business operations.

4. Sophisticated Users (Data Analysts & Business Intelligence Pros):

• Engineers, data scientists, and business analysts who thoroughly understand SQL and relational algebra.
• Write complex, ad-hoc analytical queries to extract operational insights without using pre-packaged graphical interfaces.

5. Naive / Parametric End Users:

• Everyday operational staff (bank tellers, supermarket cashiers, customer care agents) who interact with the database exclusively through graphical user interface (GUI) forms and buttons without knowing underlying SQL syntax.

Concept of Shadow Paging Recovery Technique

Shadow paging is a recovery technique that does not rely on traditional transaction log files for undoing or redoing database modifications. Instead, it maintains two separate page tables during a transaction’s execution:

---

How Shadow Paging Works

1. Current Page Table:
   • Used by the active transaction to locate and access all database pages currently in use. When a page is modified, a new copy of the page is written to a free block on disk, and the Current Page Table is updated to point to this new disk page.
2. Shadow Page Table:
   • A snapshot copy of the page table pointing to original, unmodified disk pages as they existed when the transaction started. The Shadow Page Table is never modified during the transaction’s lifetime.

---

Transaction Completion and Crash Handling

• On Successful Commit:
  • The DBMS simply writes the Current Page Table to non-volatile disk, overwriting or pointer-swapping the old Shadow Page Table. The new pages permanently become the official database state.
• On Transaction Failure or System Crash (Rollback):
  • Recovery is instantaneous! The DBMS simply discards the Current Page Table and resets the pointer back to the unmodified Shadow Page Table. No expensive log scanning, REDO, or UNDO passes are required.

Advantages & Disadvantages:

• Advantage: Fast, overhead-free crash recovery without maintaining complex log records.
• Disadvantage: High page fragmentation on physical disk and substantial overhead in copying page tables.

Concept of Specialization in Enhanced ER (EER) Modeling

Specialization is a top-down conceptual database design process that takes a generalized, higher-level entity type (supertype) and decomposes it into one or more distinctive, lower-level entity subtypes based on specific distinguishing characteristics, attributes, or business roles.

---

Key Characteristics:

• Subtypes inherit all attributes and relationships of the supertype (Attribute Inheritance).
• Subtypes possess unique, specialized attributes not shared by the general entity.

---

Real-World Example: Bank Account Hierarchy

• Supertype Entity:
  • ACCOUNT (AccountNo, Balance, DateOpened, BranchID)
• Specialized Subtype Entities:
  1. SAVINGS_ACCOUNT:
     • Inherits: AccountNo, Balance, DateOpened, BranchID
     • Unique Specialized Attributes: InterestRate, MinimumBalanceLimit
  2. FIXED_DEPOSIT_ACCOUNT:
     • Inherits: AccountNo, Balance, DateOpened, BranchID
     • Unique Specialized Attributes: MaturityDate, LockInPeriod, TenureMonths
  3. CURRENT_ACCOUNT:
     • Inherits: AccountNo, Balance, DateOpened, BranchID
     • Unique Specialized Attributes: OverdraftLimit, AnnualMaintenanceFee

In this hierarchy, Account represents the generalized superclass, while Savings, Fixed Deposit, and Current are specialized subclasses.

ACID Properties in Database Transaction Management

To ensure data integrity and reliable concurrent execution, every database transaction must satisfy the four fundamental ACID properties:

---

1. Atomicity (“All-or-Nothing”):

• Either all operations comprising the transaction execute successfully to completion, or the entire transaction is rolled back and none of its changes take effect.
• Handled by the Transaction Manager and Recovery Subsystem.

2. Consistency (State Invariant Preservation):

• A transaction must take the database from one valid state satisfying all defined integrity constraints (Primary Keys, Foreign Keys, CHECK constraints) to another valid state.
• Example: The total monetary balance across two accounts must remain invariant before and after an inter-account fund transfer.

3. Isolation (Independence of Concurrent Execution):

• Multiple transactions executing concurrently must execute independently without interfering with one another. The intermediate, uncommitted state of a running transaction must remain hidden from other concurrent transactions.
• Managed by the Concurrency Control Subsystem using techniques like Two-Phase Locking (2PL) or Timestamp Ordering.

4. Durability (Permanence of Committed Data):

• Once a transaction successfully issues a COMMIT, its updates become permanent in non-volatile storage. The updates will not be lost even if the system immediately experiences a hardware crash or power outage.
• Enforced by the Recovery Manager using Write-Ahead Logging (WAL) and checkpointing.

Concept of View in SQL

A view is a virtual table in SQL whose contents are not physically stored as separate records on disk. Instead, a view is dynamically populated from an underlying SQL SELECT query executed against one or more base tables each time the view is accessed.

Key Advantages of Views:

1. Security & Data Hiding: Restricts user access to specific columns and rows, preventing unauthorized viewing of sensitive attributes (e.g., hiding employee salaries while showing names and departments).
2. Query Simplification: Pre-packages complex multi-table JOINs, aggregations, and subqueries into a clean virtual table that can be queried with a simple SELECT statement.
3. Logical Data Independence: Buffers frontend client applications from modifications made to underlying base table structures.

---

SQL Syntax to Create a View

CREATE VIEW view_name AS SELECT column1, column2, ... FROM table_name WHERE condition;

Concrete Example:

CREATE VIEW HighValueCustomers AS SELECT C_id, CName, address, age FROM Customer WHERE age > 50;

-- Querying the newly created view: SELECT * FROM HighValueCustomers;

Concept of Schema and Instance in DBMS

In database theory, Schema and Instance represent the fundamental distinction between the structural blueprint of a database and its operational data contents:

---

Comparison Basis	Database Schema	Database Instance
Definition	The overall structural design, blueprint, and skeleton of the database, defining tables, column data types, and integrity constraints.	The actual collection of data, records, and tuples stored in the database at a specific moment in time.
Frequency of Change	Defined during the initial system design phase; changes very rarely (only during formal database schema migrations).	Changes continuously as users insert, update, or delete records in real time.
Programming Analogy	Analogous to a Class or Variable Type declaration in programming (e.g., defining a Struct).	Analogous to the specific variable values held in memory at runtime.
Example	Schema: Student (RollNo INT, Name VARCHAR(50), GPA FLOAT)	Instance: (101, ‘Suman’, 3.85) and (102, ‘Pooja’, 3.92) on September 10 at 10:00 AM.

Concept of JOIN in Relational Databases

A JOIN is an essential relational database operation used in SQL to combine columns from two or more tables based on a related logical column (typically a Foreign Key referencing a Primary Key) to produce a unified result set.

---

Comprehensive Classification of Joins

1. Inner Join (INNER JOIN / Equi-Join):

• Returns only those rows where there is an exact match in both joined tables based on the join condition. Unmatched rows from both sides are omitted.
• SQL Syntax: SELECT Orders.OrderID, Customers.CustomerName FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID;

2. Left Outer Join (LEFT JOIN):

• Returns all rows from the left table, paired with matching rows from the right table. If no match exists on the right, NULL values are inserted for the right table’s columns.
• Application: Finding all registered customers, including those who have never placed an order.

3. Right Outer Join (RIGHT JOIN):

• Returns all rows from the right table, paired with matching rows from the left table. If no match exists on the left, NULL values are inserted for the left table’s columns.

4. Full Outer Join (FULL OUTER JOIN):

• Returns all rows when there is a match in either the left or the right table. Where no match exists, NULLs populate the missing attributes on either side.

5. Cross Join (Cartesian Product):

• Produces the mathematical Cartesian product ($M \times N$) by pairing every row of the first table with every row of the second table without any join condition.

6. Self Join:

• A table is joined with itself using alias names, typically used to evaluate hierarchical or recursive relationships (e.g., finding the manager of an employee within the same Employee table).

Two-Phase Locking (2PL) Concurrency Control Protocol

Two-Phase Locking (2PL) is the standard concurrency control protocol used by relational DBMS engines to ensure that concurrent transactions execute in a conflict-serializable manner without causing data corruption (lost updates, dirty reads, unrepeatable reads).

---

The Fundamental Rule of 2PL

A transaction must acquire locks and release locks in two distinct, sequential phases:

1. Growing Phase (Lock Acquisition Phase):
   • A transaction may acquire new locks (Shared Locks for reading, Exclusive Locks for writing) as needed.
   • The transaction cannot release any lock during this phase.
2. Shrinking Phase (Lock Release Phase):
   • Once the transaction releases its very first lock, it immediately enters the shrinking phase.
   • The transaction may release locks, but it can never acquire any new locks.

• Phase 1 (Growing Phase): Locks acquired, no locks released until the Lock Point is reached.
• Phase 2 (Shrinking Phase): Locks released, no new locks acquired.

---

Types of Two-Phase Locking

1. Basic 2PL: Follows the pure growing and shrinking phases; guarantees conflict serializability but may suffer from cascading rollbacks.
2. Strict 2PL (S2PL): Mandates that all exclusive (write) locks held by a transaction must be retained until the transaction explicitly executes a COMMIT or ROLLBACK.
   • Advantage: Guarantees strict schedules and completely eliminates cascading aborts.
3. Rigorous 2PL: Mandates that all locks (both shared and exclusive) must be held until the transaction finishes and commits.

Deadlock Consideration: While 2PL guarantees serializability, it does not prevent deadlocks; database engines employ wait-for graphs and deadlock detection timeouts to break deadlocked cycles.

Database Recovery Techniques Based on Immediate Update

In the Immediate Database Modification (Immediate Update) recovery scheme, updates made by an active transaction are allowed to be written directly to the physical database on disk even before the transaction issues a COMMIT command:

---

Core Principles & Write-Ahead Logging (WAL)

To preserve the Atomicity and Durability (ACID) properties under immediate update, the DBMS strictly enforces the Write-Ahead Logging (WAL) Protocol:

• Before any data item is updated on disk, the corresponding log record containing the Old Value (Before-Image) and the New Value (After-Image) must be written to non-volatile log storage on disk.

Log Record Structure: [Transaction_ID, Data_Item, Old_Value, New_Value]

---

Crash Recovery Algorithm (UNDO / REDO Scheme)

When the system restarts after a crash, the recovery manager analyzes the transaction log by identifying transactions relative to the most recent Checkpoint:

1. Transactions to REDO (Roll-Forward):
   • Any transaction $T_i$ for which the log contains both a <T_i, START> and a <T_i, COMMIT> record.
   • Action: The recovery manager reapplies all updates using the New Values (After-Images) to guarantee Durability, ensuring committed changes are permanently on disk.
2. Transactions to UNDO (Rollback):
   • Any transaction $T_j$ for which the log contains a <T_j, START> record but no corresponding COMMIT or ABORT record (it was active when the crash occurred).
   • Action: The recovery manager rolls back all modifications by writing back the Old Values (Before-Images) in reverse chronological order, guaranteeing Atomicity.

Conclusion: The Immediate Update technique requires both UNDO and REDO capabilities, making it more dynamic than the Deferred Update technique (which only requires REDO).

E-R Diagram Design: Hospital Management System

1. Identification of Entities and Attributes:

• PATIENT:
  • PatientID (Primary Key, unique identifier)
  • Name (Composite: FirstName, LastName)
  • DOB / Age
  • Gender
  • Address
  • ContactNo
• DOCTOR:
  • DoctorID (Primary Key)
  • DoctorName
  • Specialization
  • Qualification
  • Phone
• DEPARTMENT:
  • DeptID (Primary Key)
  • DeptName (e.g., Cardiology, Neurology, Orthopedics)
  • OfficeLocation / Floor
• APPOINTMENT (Associative Entity / Relation):
  • AppointmentID (Primary Key)
  • AppointmentDate
  • AppointmentTime
  • Status (Scheduled, Completed, Cancelled)

---

2. Relationship Sets and Cardinality Constraints:

1. Works_In (Doctor to Department):
   • Cardinality: N : 1 (Many-to-One).
   • Multiple doctors work in one department; each doctor belongs to exactly one department.
2. Schedules / Books (Patient to Appointment):
   • Cardinality: 1 : N (One-to-Many).
   • A patient can book multiple appointments over time; an appointment belongs to exactly one patient.
3. Attends / Conducts (Doctor to Appointment):
   • Cardinality: 1 : N (One-to-Many).
   • A doctor conducts multiple appointments; each appointment is conducted by one specific doctor.

---

3. Structured Textual ER Representation:

[DEPARTMENT] (DeptID, DeptName, OfficeLocation) ^ | (1) <Works_In> | (N) [DOCTOR] (DoctorID, DoctorName, Specialization) ^ | (1) <Conducts> | (N) [APPOINTMENT] (AppointmentID, AppointmentDate, AppointmentTime, Status) | (N) <Books> | (1) v [PATIENT] (PatientID, Name, DOB, Gender, Address, ContactNo)

Notation Summary:

• Rectangles represent Entities (PATIENT, DOCTOR, DEPARTMENT, APPOINTMENT).
• Diamonds represent Relationships (Works_In, Conducts, Books).
• Underlined attributes represent Primary Keys (PatientID, DoctorID, DeptID, AppointmentID).

Solution: SQL DDL and DML Statements

Given Schema:

• Customer (C_id, CName, address, age)
• Buys_item (Code, iname, price, C_id)

---

a. DDL Statements to Create the Schema:

CREATE TABLE Customer ( C_id INT PRIMARY KEY, CName VARCHAR(100) NOT NULL, address VARCHAR(150), age INT CHECK (age > 0) );

CREATE TABLE Buys_item ( Code INT PRIMARY KEY, iname VARCHAR(100) NOT NULL, price DECIMAL(10, 2) NOT NULL CHECK (price >= 0), C_id INT, CONSTRAINT fk_customer FOREIGN KEY (C_id) REFERENCES Customer(C_id) ON DELETE CASCADE ON UPDATE CASCADE );

---

b. Add a New Customer:

INSERT INTO Customer (C_id, CName, address, age) VALUES (101, ‘Subash Sharma’, ‘Pokhara’, 32);

---

c. List the Name of Customers Whose Age is Greater Than 50:

SELECT CName FROM Customer WHERE age > 50;

---

d. Update the Address of Customer to ‘Kathmandu’ Whose C_id = 110:

UPDATE Customer SET address = ‘Kathmandu’ WHERE C_id = 110;

Concept of Normalization

Normalization is a formal, systematic database design technique introduced by E.F. Codd used to organize relational tables to minimize data redundancy, avoid insertion, deletion, and update anomalies, and enforce data integrity by decomposing complex, un-normalized relations into smaller, well-structured relations.

---

Levels of Normalization

1. First Normal Form (1NF):

• Rule: A relation is in 1NF if and only if all attribute values are atomic (indivisible) and there are no repeating groups or multi-valued columns.
• Example:
  • Un-normalized Table: Student (StudentID, Name, MobileNumbers) where MobileNumbers contains “9841001, 9801002”.
  • 1NF Conversion: Split into individual atomic rows:
    • (101, Suman, 9841001)
    • (101, Suman, 9801002)

---

2. Second Normal Form (2NF):

• Rule: The relation must be in 1NF, and every non-prime attribute must be fully functionally dependent on the entire primary key (Elimination of Partial Dependencies).
• Example:
  • Consider ENROLLMENT (StudentID, CourseID, CourseName, Grade) with composite key (StudentID, CourseID).
  • Defect: CourseName depends only on CourseID, which is a partial key.
  • 2NF Decomposition:
    • STUDENT_GRADE (<u>StudentID, CourseID</u>, Grade**)**
    • COURSE (<u>CourseID</u>, CourseName**)**

---

3. Third Normal Form (3NF):

• Rule: The relation must be in 2NF, and no non-prime attribute should be transitively dependent on the primary key (Elimination of Transitive Dependencies: $X \rightarrow Y$ and $Y \rightarrow Z$).
• Example:
  • Consider EMPLOYEE (EmpID, EmpName, DeptID, DeptName) with primary key EmpID.
  • Defect: EmpID $\rightarrow$ DeptID and DeptID $\rightarrow$ DeptName. DeptName depends transitively on EmpID via DeptID.
  • 3NF Decomposition:
    • EMPLOYEE (<u>EmpID</u>, EmpName, DeptID**)**
    • DEPARTMENT (<u>DeptID</u>, DeptName**)**

---

4. Boyce-Codd Normal Form (BCNF / “3.5 NF”):

• Rule: A relation is in BCNF if and only if for every non-trivial functional dependency $X \rightarrow Y$, $X$ must be a Super Key.
• BCNF is a stricter version of 3NF that resolves anomalies occurring in tables that have multiple overlapping candidate keys.
• Example:
  • Consider ADVISING (StudentID, Subject, Advisor) where an advisor teaches only one subject, but a subject can have multiple advisors:
    • Dependencies: (StudentID, Subject) $\rightarrow$ Advisor; and Advisor $\rightarrow$ Subject.
    • Defect: In Advisor $\rightarrow$ Subject, Advisor is NOT a super key, violating BCNF.
    • BCNF Decomposition:
      • ADVISOR_SUBJECT (<u>Advisor</u>, Subject**)**
      • STUDENT_ADVISOR (<u>StudentID, Advisor</u>)