Database Management System (DBMS) - Model Answer

1. What is a Database Management System? (2 marks)

A Database Management System (DBMS) is a collection of the database, its processing methods, and the set of rules and conditions to be followed for managing data. It is the way to store data and also provides a mechanism for manipulation of data. It is basically a computerized record-keeping system.

In simple terms, a DBMS allows users to:

• Store data in an organized manner
• Retrieve data efficiently
• Manipulate data (insert, update, delete, query)
• Protect data from unauthorized access and system failures

Examples: Oracle, MS SQL Server, DB2, MySQL

2. DBMS Architecture (Three-Schema Architecture) (5 marks)

The most widely accepted architecture for a DBMS is the Three-Schema Architecture (also called the ANSI/SPARC architecture). It separates the user's view of the database from the physical storage of data.

Diagram

+---------------------------+   +---------------------------+   +---------------------------+
|     External View 1       |   |     External View 2       |   |     External View 3       |
|   (End User / App 1)      |   |   (End User / App 2)      |   |   (End User / App 3)      |
+---------------------------+   +---------------------------+   +---------------------------+
           |                               |                               |
           +-------------------------------+-------------------------------+
                                           |
                              [ EXTERNAL LEVEL ]
                         (Multiple External/User Views)
                                           |
                          External / Conceptual Mapping
                                           |
                              [ CONCEPTUAL LEVEL ]
                              (Conceptual Schema)
                                           |
                          Conceptual / Internal Mapping
                                           |
                               [ INTERNAL LEVEL ]
                               (Internal Schema)
                                           |
                              +------------+------------+
                              |      Stored Database    |
                              +-------------------------+

Description of Each Level

a) External Level (View Level)

• This is the highest level of abstraction.
• It describes how individual users or groups of users see the data.
• Different users may have different views of the same database.
• Each external view is defined by an external schema (also called a subschema).
• Example: A student may see only their own marks, while a teacher sees all students' marks.

b) Conceptual Level (Logical Level)

• This is the middle level of abstraction.
• It describes what data is stored in the database and the relationships among the data.
• It is defined by a conceptual schema.
• It hides the details of physical storage and focuses on the logical structure.
• Example: Tables, attributes, relationships, constraints.

c) Internal Level (Physical Level)

• This is the lowest level of abstraction.
• It describes how data is physically stored on the storage medium.
• It is defined by an internal schema.
• It deals with storage allocation, indexing, hashing, etc.
• Example: File structures, B-trees, storage blocks.

Mappings

The process of transforming requests and results between levels is called mappings:

Note: The three schemas are only descriptions of data. The actual data is stored at the physical (internal) level only. Most DBMSs do not completely separate the three levels but support this architecture to some extent.

3. Data Independence (3 marks)

Data independence is the capacity to change the schema at one level of a database system without having to change the schema at the next higher level.

It is one of the most important advantages of the three-schema architecture.

There are two types of data independence:

a) Logical Data Independence

"It is the capacity to change the conceptual schema without having to change external schemas or application programs."

• We may change constraints, add new entities, or reduce the database at the conceptual level.
• Only the view definition and the external/conceptual mapping need to be updated.
• Application programs that refer to the external schema remain unaffected.
• Example: Adding a new attribute (column) to a table should not affect existing user views or application programs.

b) Physical Data Independence

• It is the capacity to change the internal schema without having to change the conceptual schema.
• Changes in physical storage (e.g., changing file organization, indexing method) do not affect the logical structure.
• Only the conceptual/internal mapping needs to be updated.
• Example: Changing from sequential file storage to indexed storage should not affect the conceptual schema or user views.

Summary Table

Key Point: Data independence is achieved through the three-schema architecture and its mappings. It allows the database to evolve without disrupting existing users or applications, making the system flexible and maintainable.

Entities, Their Types, and Reduction of ER Diagram to Tables

Part 1: Entity and Its Types

Definition of Entity

An entity is a real-world object or thing that has an independent existence and can be distinguished from other objects. For example: a Student, a Hotel, a Room, an Employee.

An entity type defines a collection of entities that have the same attributes. An entity set is the collection of all entities of a particular entity type at a given point in time.

Types of Entities

1. Strong Entity

A strong entity is an entity type that has a key attribute (primary key) which uniquely identifies each entity in the entity set. It does not depend on any other entity for its existence.

• Represented by a single rectangle in the ER diagram.
• Example: Hotel (identified by Hotel_ID), Employee (identified by Emp_ID)

2. Weak Entity

csc265-weak-entity-mapping

Entity types that do not have key attributes of their own are called weak entity types: their entity sets do not have sufficient attributes to form a primary key on their own.

Key characteristics of weak entities:

• Cannot be identified on their own; they depend on an owner (strong) entity.
• Always have total participation in the identifying relationship.
• Represented by a double rectangle in the ER diagram.
• The identifying relationship is represented by a double diamond.
• Have a partial key (discriminator) instead of a full primary key.

Example: Room is a weak entity that depends on Hotel. A room cannot exist without a hotel.

[Hotel] ====<< has >>==== [[Room]]

3. Superclass and Subclass Entities (Specialization / Generalization)

• Specialization is a top-down approach where a higher-level entity is broken into lower-level entities (subclasses).
• Generalization is a bottom-up approach where lower-level entities are combined into a higher-level entity (superclass).

Example:

Employee (superclass)
    ISA
   /    \
Developer  Tester  (subclasses)

Part 2: Reduction of ER Diagram Components into Tables

As a general guideline, if a relation schema corresponds to one entity type or one relationship type, its meaning is straightforward to explain. If instead a relation corresponds to a mixture of multiple entities and relationships, semantic ambiguities result.

Therefore, each entity type and each relationship type should ideally map to one relation (table).

Rule 1: Mapping a Strong Entity to a Table

Each strong entity type becomes a separate table. The key attribute becomes the primary key.

Example:

ER Entity: Student(Student_ID, Name, Age, Email)

Table:

Student(Student_ID, Name, Age, Email)
PK: Student_ID

Rule 2: Mapping a Weak Entity to a Table

A weak entity becomes a table where:

• The partial key of the weak entity is included.
• The primary key of the owner entity is included as a foreign key.
• The primary key of the weak entity table = (Owner's PK + Partial Key).

Example:

• Strong Entity: Hotel(Hotel_ID, Hotel_Name, Location)
• Weak Entity: Room depends on Hotel, with partial key Room_No and attribute Type

Tables:

Hotel(Hotel_ID, Hotel_Name, Location)
PK: Hotel_ID

Room(Hotel_ID, Room_No, Type)
PK: (Hotel_ID, Room_No)
FK: Hotel_ID references Hotel(Hotel_ID)

Rule 3: Mapping a 1:1 (One-to-One) Relationship

In a 1:1 relationship, the primary key of one entity is added as a foreign key in the other entity's table. Preferably, the foreign key is placed in the entity with total participation.

Example:

• Employee(Emp_ID, Name) manages Department(Dept_ID, Dept_Name)
• Relationship: Manages (1:1)

Tables:

Employee(Emp_ID, Name)
PK: Emp_ID

Department(Dept_ID, Dept_Name, Emp_ID)
PK: Dept_ID
FK: Emp_ID references Employee(Emp_ID)

Rule 4: Mapping a 1:N (One-to-Many) Relationship

The primary key of the "one" side entity is added as a foreign key in the table of the "many" side entity.

Example:

• Department(Dept_ID, Dept_Name) has many Employee(Emp_ID, Name)
• Relationship: Works_In (1:N)

Tables:

Department(Dept_ID, Dept_Name)
PK: Dept_ID

Employee(Emp_ID, Name, Dept_ID)
PK: Emp_ID
FK: Dept_ID references Department(Dept_ID)

Rule 5: Mapping an M:N (Many-to-Many) Relationship

Unlike 1:1 and 1:N relationships, an M:N relationship cannot be represented by simply adding a foreign key to either entity's table, because that would force each row to reference only one match on the other side. Instead, a new separate table (junction/bridge table) is created that contains:

• The primary keys of both participating entities (as foreign keys).
• Any attributes of the relationship itself.
• A composite primary key made up of both foreign keys together.

Example:

• Student(Student_ID, Name) enrolls in many Course(Course_ID, Course_Name), and a course has many students.
• Relationship: Enrolls (M:N), with attribute Grade

Tables:

Student(Student_ID, Name)
PK: Student_ID

Course(Course_ID, Course_Name)
PK: Course_ID

Enrolls(Student_ID, Course_ID, Grade)
PK: (Student_ID, Course_ID)
FK: Student_ID references Student(Student_ID)
FK: Course_ID references Course(Course_ID)

Summary

Every ER construct reduces to a relational table by the same underlying idea: strong entities become tables with their own primary key, weak entities inherit the owner's key as part of a composite key, 1:1 and 1:N relationships push a foreign key onto one existing table, and M:N relationships require a brand-new junction table carrying both sides' keys as a composite primary key. Applying these five rules to every entity and relationship in an ER diagram is what produces a complete, normalized relational schema.

Conflict Schedule

Definition

A conflict schedule (more precisely, a schedule with conflicting operations) refers to a schedule in which two or more transactions contain conflicting operations. Two operations in a schedule are said to conflict if they satisfy all three of the following conditions:

1. They belong to different transactions.
2. They access the same data item X.
3. At least one of them is a write operation.

The possible conflicting pairs are:

Conflict Serializability

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. To test this, a precedence graph (serialization graph) is constructed.

Algorithm (from notes):

1. Look at only read_Item(X) and write_Item(X) operations.
2. Construct a precedence graph with directed edges.
3. Draw an edge from Ti → Tj if an operation in Ti appears before a conflicting operation in Tj.
4. The schedule is conflict serializable if and only if the precedence graph has no cycles.

Example

Consider two transactions:

• T1: read(X), write(X), read(Y), write(Y)
• T2: read(X), write(X), read(Y), write(Y)

Schedule S:

Identifying Conflicts:

Every pair below is on the same data item, from different transactions, with at least one write, so each pair contributes an edge in the direction of the operation that comes first in the schedule.

Precedence Graph:

T1 ---------> T2
 ^            |
 |____________|

• Edges run in both directions, so the graph contains a cycle (T1 → T2 → T1).
• Therefore, Schedule S is NOT conflict serializable. Neither serial order works: T2 reads X before T1 writes it, which would put T2 first, while T1 writes X before T2 writes it, which would put T1 first.

A Conflict Serializable Schedule S1:

Interleaving the same two transactions differently gives a schedule that is conflict serializable.

Here every conflicting pair has the T1 operation first: read(X) of T1 before write(X) of T2, write(X) of T1 before both read(X) and write(X) of T2, read(Y) of T1 before write(Y) of T2, and write(Y) of T1 before both read(Y) and write(Y) of T2.

Precedence Graph:

T1 ---------> T2

• There is no cycle in this precedence graph.
• Therefore, Schedule S1 is conflict serializable, equivalent to the serial schedule T1 → T2, even though its operations are interleaved.

Example of a NON-Conflict Serializable Schedule

Schedule S2:

Conflicts:

• T2:write(X) before T1:write(X) → T2 → T1
• T1:write(Y) before T2:write(Y) → T1 → T2

Precedence Graph:

T1 ---------> T2
 ^            |
 |____________|

• There is a cycle (T1 → T2 → T1).
• Therefore, Schedule S2 is NOT conflict serializable.

Summary

A conflict schedule contains conflicting operations (same data item, different transactions, at least one write). It is conflict serializable if its precedence graph contains no cycle, meaning it is equivalent to some serial execution of the transactions.

Functional Dependencies and Second Normal Form (2NF)

Functional Dependency (FD)

A functional dependency is a constraint between two sets of attributes in a relation. For a relation R, a functional dependency X → Y means that the value of attribute set X uniquely determines the value of attribute set Y.

• X is called the determinant
• Y is called the dependent

Example: In a Student table, StudentID → StudentName means that knowing the StudentID uniquely determines the StudentName.

A set of functional dependencies is given for each relation, and each relation has a designated primary key, which is then evaluated for normalization. (from notes)

Second Normal Form (2NF)

"To be in second normal form, a relation must be in First Normal Form AND the relation must not contain any partial dependency." (from notes)

Key Definitions:

• Non-prime attribute: An attribute that is not part of any candidate key
• Partial Dependency: When a proper subset of a candidate key determines a non-prime attribute

Partial Dependency = Proper subset of candidate key → non-prime attribute

Conditions for 2NF:

1. The relation must be in 1NF
2. There must be no partial dependency (every non-prime attribute must be fully functionally dependent on the whole candidate key)

Example

Table NOT in 2NF:

• Primary Key (Composite): {StudentID, CourseID}
• Functional Dependencies:
  • StudentID, CourseID → Grade (full dependency - OK)
  • StudentID → StudentName (partial dependency - violation)
  • CourseID → CourseName (partial dependency - violation)

Since StudentName depends only on StudentID (a proper subset of the composite key), this is a partial dependency, so the table is NOT in 2NF.

Decomposition to achieve 2NF:

Table 1: Student

Table 2: Course

Table 3: Enrollment

Now every non-prime attribute is fully dependent on the entire primary key. All three tables are in 2NF.

Summary

Buffer Management in DBMS

Definition

Buffer Management refers to the process by which the DBMS manages a collection of in-memory buffers (called the DBMS cache) that temporarily hold disk pages (blocks) containing data items needed for processing. Since disk I/O is slow, the DBMS brings data into main memory buffers, performs operations there, and then writes the modified data back to disk at an appropriate time.

How Buffer Management Works

When a transaction needs to read or update a data item, the DBMS follows these steps:

1. Check the buffer directory to see if the required disk page is already in the DBMS cache (buffer pool).
2. If not present, the page is fetched from disk into a free buffer slot.
3. The data item is updated in memory (not directly on disk).
4. A dirty bit is associated with each buffer:
   • Dirty bit = 0: the buffer has not been modified.
   • Dirty bit = 1: the buffer has been modified and needs to be written back to disk.
5. Eventually, the modified buffer is written back to disk based on the recovery policy in use.

Key Policies in Buffer Management

Buffer management is closely tied to recovery algorithms. Two important policy pairs govern when modified pages are written to disk:

1. Steal / No-Steal Policy

2. Force / No-Force Policy

Role of the DBMS Cache Directory

• A directory is maintained to track which database pages are currently held in the buffer pool.
• This avoids redundant disk reads if the same page is needed again.
• The DBMS recovery subsystem uses this information to manage undo and redo operations during crash recovery.

Importance of Buffer Management

• Reduces the number of expensive disk I/O operations.
• Ensures data consistency by controlling when dirty pages are flushed to disk.
• Supports transaction recovery by coordinating with logging mechanisms (undo/redo logs).
• Works together with checkpointing, where all modified buffers are force-written to disk to establish a consistent recovery point.

Summary

Buffer management is the mechanism by which the DBMS controls a pool of main memory buffers (DBMS cache) to hold disk pages temporarily, tracks modifications using dirty bits and a directory, and applies steal/no-steal and force/no-force policies to decide when to write data back to disk, thereby balancing performance and recoverability.