NoSQL: Definition and Characteristics

What is NoSQL?

NoSQL (Not Only SQL) is a category of database management systems that do not follow the traditional relational database model. NoSQL databases are designed to store, retrieve, and manage large volumes of unstructured, semi-structured, or structured data that may not fit neatly into tables with fixed schemas.

NoSQL databases emerged to address the limitations of relational databases in handling big data, real-time web applications, and distributed computing environments.

Note: This answer is based on standard database literature, as no specific curriculum notes were provided.

Characteristics of NoSQL

1. Non-Relational / Schema-Free

• NoSQL databases do not require a fixed schema like relational databases.
• Data can be stored in flexible formats such as key-value pairs, documents, graphs, or wide columns.
• New fields can be added without altering the entire database structure.

2. Horizontal Scalability

• NoSQL databases are designed to scale out by adding more servers (horizontal scaling) rather than upgrading a single server (vertical scaling).
• This makes them suitable for handling massive amounts of data across distributed systems.

3. Distributed Architecture

• Data is distributed across multiple nodes or servers.
• This ensures high availability and fault tolerance.
• Examples include replication and sharding of data across clusters.

4. High Performance

• NoSQL databases are optimized for fast read and write operations.
• By avoiding complex joins and rigid schemas, they achieve lower latency and higher throughput.

5. BASE Properties (instead of ACID)

NoSQL follows the BASE model:

6. Support for Variety of Data Models

NoSQL supports multiple data storage models:

• Key-Value Store (e.g., Redis)
• Document Store (e.g., MongoDB)
• Column-Family Store (e.g., Cassandra)
• Graph Database (e.g., Neo4j)

7. Open Source and Cost-Effective

• Most NoSQL databases are open-source and can run on commodity hardware, reducing infrastructure costs.

8. Handles Big Data

• NoSQL is well-suited for storing and processing large volumes of data (Big Data) generated by social media, IoT devices, and web applications.

Summary Table

• EMPLOYEE (Ssn, Ename, Bdate, Address, Sex, Salary, Superssn, Dno) - DEPARTMENT (Dname, Dnumber, Mgrssn, Mgrstartdate) - PROJECT (Pname, Pnumber, Plocation, Dnum) - DEPENDENT (Essn, Dependentname, Sex, Bdate, Relationship) - DEPTLOCATIO...

Serial, Non-Serial, and Serializable Schedules

1. Serial Schedule

A serial schedule is one in which transactions are executed one after another, without any interleaving of operations. One transaction must complete entirely before the next one begins.

Properties:

• No concurrency
• Always consistent (correct by definition)
• Poor performance due to no overlap

Example:

Here T1 executes completely before T2 starts. This is a serial schedule: T1 → T2.

2. Non-Serial Schedule

A non-serial schedule is one in which operations of multiple transactions are interleaved with each other. Transactions execute concurrently.

Properties:

• Allows concurrency and better throughput
• May or may not produce consistent results
• Not all non-serial schedules are correct

Example:

Here operations of T1 and T2 are interleaved. This is a non-serial schedule.

3. Serializable Schedule

A serializable schedule is a non-serial schedule that produces the same result as some serial schedule of the same transactions. It is the standard criterion for correctness of concurrent execution.

A non-serial schedule S is serializable if it is equivalent to some serial schedule.

Types of Serializability:

• Conflict Serializability (most commonly tested)
• View Serializability

4. Testing Serializability: Precedence Graph (Conflict Graph) Method

Concept of Conflicting Operations

Two operations conflict if:

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

Steps to Test Conflict Serializability

Step 1: Identify all pairs of conflicting operations between different transactions.

Step 2: Build a Precedence Graph (Serialization Graph):

• One node for each transaction
• Draw a directed edge from Ti → Tj if an operation of Ti conflicts with an operation of Tj, and Ti's operation appears before Tj's operation in the schedule

Step 3: Check for cycles in the graph:

• No cycle → Schedule is conflict serializable
• Cycle exists → Schedule is NOT conflict serializable

Worked Example

Consider the following schedule S with transactions T1, T2, T3:

Step 1: Identify Conflicting Pairs

Step 2: Draw Precedence Graph

T1 ---------> T2
 ^             |
 |             v
 +---- T2    T3 <----> T2

More precisely:

• T1 → T2 (T1 reads X before T2 writes X)
• T2 → T1 (T2 writes X before T1 reads X at step 4)
• T2 → T3 (T2 writes Y before T3 writes Y)
• T3 → T2 (T3 reads Y before T2 writes Y)

Step 3: Check for Cycles

• T1 → T2 → T1 forms a cycle
• T2 → T3 → T2 forms a cycle

Conclusion: The schedule contains cycles in the precedence graph, therefore it is NOT conflict serializable.

Example of a Serializable Schedule

**Conflicting

Three Schema Architecture and Data Independence

Three Schema Architecture

The three schema architecture (also called the ANSI/SPARC architecture) is a framework for database systems that separates the database into three distinct levels or schemas. This architecture was proposed to achieve data independence and support multiple user views.

The Three Levels

1. External Level (View Level)

• The highest level of abstraction, closest to the end users.
• Describes how individual users or groups of users see the data.
• Each user group has its own external schema (user view), showing only the portion of the database relevant to that user.
• Different users can have different views of the same data.
• Example: A student may see only their own grades, while a teacher sees all student grades.

2. Conceptual Level (Logical Level)

• The middle level, representing the community or organizational view of the entire database.
• Described by a conceptual schema, which defines:
  • All entities, attributes, and relationships
  • Constraints, security, and integrity rules
• Hides the physical storage details but describes what data is stored and how it is logically structured.
• Managed by the Database Administrator (DBA).

3. Internal Level (Physical Level)

• The lowest level, closest to physical storage.
• Described by an internal schema, which defines:
  • How data is physically stored on disk
  • File organization, indexing, hashing, access paths
  • Storage allocation and compression
• Deals with the actual implementation of the database.

Diagram

+-----------------------------+
|   External Schema 1  |  External Schema 2  |  ...  |   <- External Level
+-----------------------------+
           |
+-----------------------------+
|      Conceptual Schema      |                           <- Conceptual Level
+-----------------------------+
           |
+-----------------------------+
|       Internal Schema       |                           <- Internal Level
+-----------------------------+
           |
+-----------------------------+
|     Physical Database       |
+-----------------------------+

How the Architecture Creates Data Independence

Data independence is the ability to change the schema at one level without having to change the schema at the next higher level. The three schema architecture achieves this through two types of mappings:

1. Logical Data Independence

• The ability to change the conceptual schema without changing the external schemas or application programs.
• Example: Adding a new attribute (column) to a table, or splitting a table, does not affect the user views as long as the mapping between external and conceptual levels is updated.
• This is harder to achieve in practice.

2. Physical Data Independence

• The ability to change the internal schema without changing the conceptual schema.
• Example: Changing the file organization from sequential to indexed, or moving data to a different storage device, does not affect the logical structure.
• This is easier to achieve and is supported by most DBMS.

Summary Table

Conclusion

The three schema architecture creates data independence by introducing clear separation between how data is physically stored, how it is logically organized, and how it is viewed by users. The mappings between levels ensure that changes at one level are translated appropriately, shielding higher levels from lower-level changes. This reduces maintenance cost, improves flexibility, and allows the database to evolve without disrupting existing applications.

A transaction is a logical unit of work or a sequence of operations performed on a database that must be executed as a whole. It is a collection of database operations (such as read, write, insert, update, delete) that together form a si...

NoSQL: Definition and Characteristics

What is NoSQL?

NoSQL (Not Only SQL) is a category of database management systems that do not follow the traditional relational database model. NoSQL databases are designed to store, retrieve, and manage large volumes of unstructured, semi-structured, or structured data that may not fit neatly into tables with fixed schemas.

NoSQL databases emerged to address the limitations of relational databases in handling big data, real-time web applications, and distributed computing environments.

Note: This answer is based on standard database literature, as no specific curriculum notes were provided.

Characteristics of NoSQL

1. Non-Relational / Schema-Free

• NoSQL databases do not require a fixed schema like relational databases.
• Data can be stored in flexible formats such as key-value pairs, documents, graphs, or wide columns.
• New fields can be added without altering the entire database structure.

2. Horizontal Scalability

• NoSQL databases are designed to scale out by adding more servers (horizontal scaling) rather than upgrading a single server (vertical scaling).
• This makes them suitable for handling massive amounts of data across distributed systems.

3. Distributed Architecture

• Data is distributed across multiple nodes or servers.
• This ensures high availability and fault tolerance.
• Examples include replication and sharding of data across clusters.

4. High Performance

• NoSQL databases are optimized for fast read and write operations.
• By avoiding complex joins and rigid schemas, they achieve lower latency and higher throughput.

5. BASE Properties (instead of ACID)

NoSQL follows the BASE model:

6. Support for Variety of Data Models

NoSQL supports multiple data storage models:

• Key-Value Store (e.g., Redis)
• Document Store (e.g., MongoDB)
• Column-Family Store (e.g., Cassandra)
• Graph Database (e.g., Neo4j)

7. Open Source and Cost-Effective

• Most NoSQL databases are open-source and can run on commodity hardware, reducing infrastructure costs.

8. Handles Big Data

• NoSQL is well-suited for storing and processing large volumes of data (Big Data) generated by social media, IoT devices, and web applications.

Summary Table

Three Schema Architecture and Data Independence

Three Schema Architecture

The three schema architecture (also called the ANSI/SPARC architecture) is a framework for database systems that separates the database into three distinct levels or schemas. This architecture was proposed to achieve data independence and support multiple user views.

The Three Levels

1. External Level (View Level)

• The highest level of abstraction, closest to the end users.
• Describes how individual users or groups of users see the data.
• Each user group has its own external schema (user view), showing only the portion of the database relevant to that user.
• Different users can have different views of the same data.
• Example: A student may see only their own grades, while a teacher sees all student grades.

2. Conceptual Level (Logical Level)

• The middle level, representing the community or organizational view of the entire database.
• Described by a conceptual schema, which defines:
  • All entities, attributes, and relationships
  • Constraints, security, and integrity rules
• Hides the physical storage details but describes what data is stored and how it is logically structured.
• Managed by the Database Administrator (DBA).

3. Internal Level (Physical Level)

• The lowest level, closest to physical storage.
• Described by an internal schema, which defines:
  • How data is physically stored on disk
  • File organization, indexing, hashing, access paths
  • Storage allocation and compression
• Deals with the actual implementation of the database.

Diagram

+-----------------------------+
|   External Schema 1  |  External Schema 2  |  ...  |   <- External Level
+-----------------------------+
           |
+-----------------------------+
|      Conceptual Schema      |                           <- Conceptual Level
+-----------------------------+
           |
+-----------------------------+
|       Internal Schema       |                           <- Internal Level
+-----------------------------+
           |
+-----------------------------+
|     Physical Database       |
+-----------------------------+

How the Architecture Creates Data Independence

Data independence is the ability to change the schema at one level without having to change the schema at the next higher level. The three schema architecture achieves this through two types of mappings:

1. Logical Data Independence

• The ability to change the conceptual schema without changing the external schemas or application programs.
• Example: Adding a new attribute (column) to a table, or splitting a table, does not affect the user views as long as the mapping between external and conceptual levels is updated.
• This is harder to achieve in practice.

2. Physical Data Independence

• The ability to change the internal schema without changing the conceptual schema.
• Example: Changing the file organization from sequential to indexed, or moving data to a different storage device, does not affect the logical structure.
• This is easier to achieve and is supported by most DBMS.

Summary Table

Conclusion

The three schema architecture creates data independence by introducing clear separation between how data is physically stored, how it is logically organized, and how it is viewed by users. The mappings between levels ensure that changes at one level are translated appropriately, shielding higher levels from lower-level changes. This reduces maintenance cost, improves flexibility, and allows the database to evolve without disrupting existing applications.

• EMPLOYEE (Ssn, Ename, Bdate, Address, Sex, Salary, Superssn, Dno) - DEPARTMENT (Dname, Dnumber, Mgrssn, Mgrstartdate) - PROJECT (Pname, Pnumber, Plocation, Dnum) - DEPENDENT (Essn, Dependentname, Sex, Bdate, Relationship) - DEPTLOCATIO...

Serial, Non-Serial, and Serializable Schedules

1. Serial Schedule

A serial schedule is one in which transactions are executed one after another, without any interleaving of operations. One transaction must complete entirely before the next one begins.

Properties:

• No concurrency
• Always consistent (correct by definition)
• Poor performance due to no overlap

Example:

Here T1 executes completely before T2 starts. This is a serial schedule: T1 → T2.

2. Non-Serial Schedule

A non-serial schedule is one in which operations of multiple transactions are interleaved with each other. Transactions execute concurrently.

Properties:

• Allows concurrency and better throughput
• May or may not produce consistent results
• Not all non-serial schedules are correct

Example:

Here operations of T1 and T2 are interleaved. This is a non-serial schedule.

3. Serializable Schedule

A serializable schedule is a non-serial schedule that produces the same result as some serial schedule of the same transactions. It is the standard criterion for correctness of concurrent execution.

A non-serial schedule S is serializable if it is equivalent to some serial schedule.

Types of Serializability:

• Conflict Serializability (most commonly tested)
• View Serializability

4. Testing Serializability: Precedence Graph (Conflict Graph) Method

Concept of Conflicting Operations

Two operations conflict if:

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

Steps to Test Conflict Serializability

Step 1: Identify all pairs of conflicting operations between different transactions.

Step 2: Build a Precedence Graph (Serialization Graph):

• One node for each transaction
• Draw a directed edge from Ti → Tj if an operation of Ti conflicts with an operation of Tj, and Ti's operation appears before Tj's operation in the schedule

Step 3: Check for cycles in the graph:

• No cycle → Schedule is conflict serializable
• Cycle exists → Schedule is NOT conflict serializable

Worked Example

Consider the following schedule S with transactions T1, T2, T3:

Step 1: Identify Conflicting Pairs

Step 2: Draw Precedence Graph

T1 ---------> T2
 ^             |
 |             v
 +---- T2    T3 <----> T2

More precisely:

• T1 → T2 (T1 reads X before T2 writes X)
• T2 → T1 (T2 writes X before T1 reads X at step 4)
• T2 → T3 (T2 writes Y before T3 writes Y)
• T3 → T2 (T3 reads Y before T2 writes Y)

Step 3: Check for Cycles

• T1 → T2 → T1 forms a cycle
• T2 → T3 → T2 forms a cycle

Conclusion: The schedule contains cycles in the precedence graph, therefore it is NOT conflict serializable.

Example of a Serializable Schedule

**Conflicting

ER Diagram: Need and Design

Part 1: Need for an ER Diagram (3 marks)

An Entity-Relationship (ER) Diagram is a high-level conceptual data model that graphically represents the structure of a database. The need for an ER diagram arises due to the following reasons:

1. Visual Representation of Data: It provides a clear, pictorial view of the database structure, making it easy to understand the relationships among data entities before actual implementation.

2. Communication Tool: It serves as a common language between database designers, developers, and non-technical stakeholders (clients, managers) to discuss and validate requirements.

3. Blueprint for Database Design: It acts as a blueprint for translating the conceptual model into a logical and then physical database schema (tables, keys, constraints).

4. Error Detection at Early Stage: Design flaws, redundancies, and missing relationships can be identified and corrected at the design stage, saving time and cost during implementation.

5. Documentation: It serves as permanent documentation of the database structure for future maintenance and modification.

6. Simplifies Complex Systems: For large and complex systems, ER diagrams break down the system into manageable entities and relationships, making design systematic and organized.

Part 2: ER Diagram Design (7 marks)

Assumptions / Scenario: University Management System

Entities and Their Attributes

Relationships

Special Requirements Checklist

ER Diagram (Text/Notation Representation)

                    [DOB]  ((Phone))  [Name]  [Address]
                      |       |         |        |
                    (Age*)    |         |        |
                      \       |         |        /
                       ======[STUDENT]======
                      /                      \
              (double line)                   \
                  ||                           \
           <BELONGS_TO>                    <ENROLLS> (M:N)
                  |                             |
           [DEPARTMENT]                      [COURSE]
           DeptID, DeptName,              CourseID, CourseName,
           Location                       Credits
                                               |
                                          <TEACHES>
                                               |
                                         [PROFESSOR]
                                    ProfID, ProfName, Salary
                                        /           \
                                  <WORKS_IN>    <HAS_DEPENDENT>
                                       |               || (double line)
                                 [DEPARTMENT]    [[DEPENDENT]]
                                              DepName(dashed underline),
                                              Relationship, Age

ER Diagram (Formal Diagram Description)

+------------------------------------------------------------------+
|                  UNIVERSITY MANAGEMENT SYSTEM                    |
+------------------------------------------------------------------+

  [DOB]  ((Phone))  [Name]  [Address]
    |        |         |       |
  (Age*)     |         |       |
    +--------+---------+-------+
    |                          |
 ====[  STUDENT  ]====         |
 ||  StudentID(PK)  ||         |
 ||  Name, Address  ||         |
 ||  DOB            ||         |
 ||  Age*           ||         |
 ||  {Phone}        ||         |
 ====                ====      |
  |                    |       |
  | (Total)            |       |
  |                    |       |
<BELONGS_TO>      <ENROLLS> (M:N)
  |                    |
  |              [  COURSE  ]
[DEPARTMENT]     CourseID(PK)
DeptID(PK)       CourseName
DeptName         Credits
Location              |
  |              <TEACHES>
  |                   |
<WORKS_IN>----[PROFESSOR]----<HAS_DEPENDENT>
              ProfID(PK)              ||
              ProfName           [[DEPENDENT]]
              Salary             DepName (partial key, dashed underline)
                                 Relationship
                                 Age

Notation Key

Cardinality Summary

The M:N relationship ENROLLS cannot be represented by a foreign key in either table, so on conversion to tables it becomes a separate relation ENROLLMENT(StudentID, CourseID, Grade) whose primary key is the pair of foreign keys. The weak entity DEPENDENT likewise becomes DEPENDENT(ProfID, DepName, Relationship, Age) with ProfID as both part of the primary key and a foreign key, deleted along with its owner professor.

Conclusion

An ER diagram is needed because it captures the structure of the data, the entities, their attributes and the relationships among them, before any table is written, and it does so in a notation that a non technical user can still read and approve. The design above satisfies the requirements of the question: five entities (STUDENT, DEPARTMENT, COURSE, PROFESSOR and the weak entity DEPENDENT), a many to many relationship between the two strong entities STUDENT and COURSE, a derived attribute (Age, computed from DOB) and a multi-valued attribute (Phone) on STUDENT, and total participation of STUDENT in BELONGS_TO.

A transaction is a logical unit of work or a sequence of operations performed on a database that must be executed as a whole. It is a collection of database operations (such as read, write, insert, update, delete) that together form a si...

Normalization and Second Normal Form (2NF)

What is Normalization?

Normalization is the process of organizing the attributes and tables of a relational database to minimize data redundancy and improve data integrity. It involves decomposing a large table into smaller, well-structured tables and defining relationships between them.

Goals of Normalization:

• Eliminate redundant data
• Ensure data dependencies make sense
• Reduce anomalies (insertion, update, deletion anomalies)

Second Normal Form (2NF)

A relation is in Second Normal Form (2NF) if:

1. It is already in First Normal Form (1NF), AND
2. Every non-key attribute is fully functionally dependent on the entire primary key (i.e., there is no partial dependency).

Partial Dependency: A non-key attribute depends on only a part of a composite primary key, not the whole key.

Note: 2NF is only relevant when the primary key is composite (made up of more than one attribute).

Example

Table NOT in 2NF

Consider the following relation:

• Primary Key: (StudentID, CourseID) -- composite key
• Functional Dependencies:
  • (StudentID, CourseID) → Grade ✅ (full dependency)
  • StudentID → StudentName ❌ (partial dependency)
  • CourseID → CourseName ❌ (partial dependency)

StudentName depends only on StudentID, and CourseName depends only on CourseID. These are partial dependencies, so this table violates 2NF.

Converting to 2NF

Decompose the table to remove partial dependencies:

Table 1: Student

Table 2: Course

Table 3: Enrollment

Now:

• Each non-key attribute is fully dependent on the whole primary key.
• All three tables are in 2NF.

Summary

Shadow Paging

Definition

Shadow paging is a recovery technique used in database systems that maintains two page tables simultaneously:

• Current Page Table - reflects all changes made by the current (active) transaction.
• Shadow Page Table - a copy of the page table taken at the start of the transaction; it remains unchanged during the transaction and points to the stable (committed) state of the database.

Both page tables initially point to the same disk pages. As the transaction modifies pages, new copies of those pages are written to new disk locations, and only the current page table is updated to point to the new pages. The shadow page table continues to point to the original pages.

How Shadow Paging Works

Setup

At transaction start:
Shadow Page Table                 Current Page Table
  (frozen copy)                    (being updated)
   +---------+                       +---------+
   | Page 1  |----------+----------->| Page 1  |
   | Page 2  |-------+  |  +---------| Page 2  |
   | Page 3  |----+  |  |  |  +------| Page 3  |
   +---------+    |  |  |  |  |      +---------+
                  v  v  v  v  v
               +----+----+----+  DISK PAGES
               | P1 | P2 | P3 |
               +----+----+----+

When the transaction modifies page 2:

   Shadow Page Table            Current Page Table
   | Page 2 |---> [ old P2 ]    | Page 2 |---> [ new P2' ]

The old page P2 is never overwritten; a fresh copy P2' is written to a free disk block and only the current page table is made to point at it.

How Shadow Paging is Used for Recovery

On successful commit:

• All modified pages are flushed to disk.
• The current page table is written to disk.
• The pointer held in the database header is switched from the shadow page table to the current page table in a single atomic write.
• The old pages that the shadow table referred to become free space.

On failure or abort (system crash, transaction error):

• The current page table and the new pages are simply discarded.
• The database header still points at the shadow page table, which describes exactly the state of the database before the transaction began.
• The database is therefore already consistent when it restarts, with no undo and no redo required.

Advantages and Disadvantages

Conclusion

Shadow paging achieves atomicity and durability by never overwriting a page in place. The shadow page table preserves the pre-transaction image of the database while the current page table accumulates the changes, and commit reduces to switching one pointer. Recovery is therefore trivial (either the switch happened and the transaction is committed, or it did not and the transaction never existed), which is why the technique is valued for its simplicity even though the page copying and fragmentation costs keep it out of most multi-user database systems.

Integrity Constraints

Definition

An Integrity Constraint is a rule or condition imposed on a database to ensure the accuracy, consistency, and validity of data stored in the database. Integrity constraints prevent invalid data from being entered into the database and maintain the correctness of data throughout all operations (insertion, deletion, and update).

Three Main Categories of Integrity Constraints

1. Domain Integrity Constraints

• These constraints specify that the value of each attribute must be an atomic value from its domain (data type).
• They restrict the type, format, and range of values that can be stored in a column.
• Example: An attribute Age must contain only positive integer values; a Gender attribute may only accept 'M' or 'F'.

2. Entity Integrity Constraints

• This constraint states that the primary key of a relation must be unique and not null.
• Every tuple (row) in a relation must be uniquely identifiable.
• No attribute that is part of the primary key can have a NULL value.
• Example: In a Student table, the StudentID (primary key) must have a unique, non-null value for every student record.

3. Referential Integrity Constraints

• This constraint is defined between two relations and is used to maintain consistency among tuples.
• It states that a foreign key in one relation must either match a primary key value in the referenced relation, or be NULL.
• It ensures that references between tables remain valid.
• Example: In an Enrollment table, the StudentID (foreign key) must correspond to an existing StudentID in the Student table.

Summary Table

Mapping 1:N and N:M Relationships in ER-to-Relational Mapping

1. Mapping 1:N (One-to-Many) Relationship

Rule / Approach

In a 1:N relationship, the entity on the N-side (many-side) gets the primary key of the 1-side entity added as a foreign key in its relation. No new relation is created.

Steps

1. Create relations for both participating entity types.
2. Identify the entity on the many side.
3. Add the primary key of the one-side entity as a foreign key into the many-side relation.
4. Also include any attributes of the relationship in the many-side relation.

Example

ER Diagram: A DEPARTMENT employs many EMPLOYEES (1:N)

DEPARTMENT (1) ----manages---- EMPLOYEE (N)

Resulting Relations:

DEPARTMENT (Dept_No, Dept_Name, Location)
              PK

EMPLOYEE (Emp_ID, Emp_Name, Salary, Dept_No)
           PK                        FK → DEPARTMENT

The primary key Dept_No from DEPARTMENT is placed as a foreign key in the EMPLOYEE relation.

2. Mapping N:M (Many-to-Many) Relationship

Rule / Approach

In an N:M relationship, a new relation (cross/junction table) is created to represent the relationship. This new relation contains:

• The primary key of the first entity (as FK)
• The primary key of the second entity (as FK)
• Any attributes of the relationship itself
• The combination of both foreign keys forms the primary key of the new relation.

Steps

1. Create relations for both participating entity types.
2. Create a new relation for the relationship.
3. Include the primary keys of both entities as foreign keys in the new relation.
4. The composite primary key = PK of entity 1 + PK of entity 2.
5. Add any relationship attributes to the new relation.

Example

ER Diagram: A STUDENT enrolls in many COURSES, and a COURSE has many STUDENTS (N:M), with an attribute Grade.

STUDENT (N) ----enrolls---- COURSE (M)
                  |
                Grade (relationship attribute)

Resulting Relations:

STUDENT (Student_ID, Student_Name, Address)
          PK

COURSE (Course_ID, Course_Name, Credits)
         PK

ENROLLMENT (Student_ID, Course_ID, Grade)
             FK→STUDENT  FK→COURSE
             |________________________|
                  Composite PK

A new relation ENROLLMENT is created with Student_ID and Course_ID as a composite primary key, and Grade as a relationship attribute.

Summary Table

Transaction, Lost Update, and Dirty Read Problems

What is a Transaction?

A transaction is a logical unit of work that consists of a sequence of database operations (such as read and write) that must be executed as a single, indivisible unit. A transaction either completes fully (commits) or has no effect at all (rolls back).

A transaction must satisfy the ACID properties:

Example of a transaction:

BEGIN TRANSACTION
    READ(A)
    A = A - 500
    WRITE(A)
    READ(B)
    B = B + 500
    WRITE(B)
COMMIT

Problems in Concurrent Execution of Transactions

When multiple transactions execute concurrently without proper control, several problems can arise. Two major problems are:

1. Lost Update Problem
2. Dirty Read Problem

1. Lost Update Problem

Definition

The lost update problem occurs when two transactions read the same data item and then both update it based on the original value they read. The update made by the first transaction is overwritten (lost) by the second transaction, resulting in incorrect data.

How It Occurs

• Transaction T1 reads a data item X.
• Transaction T2 also reads the same data item X.
• T1 updates X and writes it back.
• T2 updates X based on the old value it read and writes it back.
• T1's update is lost because T2 overwrites it.

Example

Suppose two bank clerks are updating the same account balance simultaneously.

Initial Balance of Account A = 1000

Expected Result: 1000 + 200 - 300 = 900

Actual Result: 700

T1's update of +200 is lost because T2 read the old value (1000) before T1 wrote its result, and T2's WRITE overwrote T1's update.

2. Dirty Read Problem

Definition

The dirty read problem (also called the temporary update problem) occurs when a transaction reads data that has been modified by another transaction that has not yet committed. If the first transaction later rolls back, the second transaction has read data that never officially existed, leading to inconsistency.

How It Occurs

• Transaction T1 reads a data item X and updates it.
• Transaction T2 reads the updated (dirty) value of X before T1 commits.
• T1 fails and rolls back, restoring X to its original value.
• T2 has already used the incorrect (dirty) value in its computation.

Example

Suppose a flight booking system where two transactions operate on available seats.

Initial Seats Available = 10

Expected Result: T1 rolled back, so only T2 should have booked. Seats should be 9.

Actual Result: 8

T2 read the dirty (uncommitted) value of 9 written by T1. After T1 rolled back, the actual value was restored to 10, but T2 already computed based on 9, causing an incorrect final value of 8.

Summary Comparison

Solution

These problems are solved by concurrency control mechanisms such as:

• Locking protocols (shared lock, exclusive lock)
• Timestamp ordering
• Serializable schedules

These ensure that concurrent transactions produce results equivalent to some serial execution of those transactions.

Normalization: Need, 1NF, 2NF, and 3NF

Why is Normalization Required?

Normalization is the process of organizing a relational database to reduce data redundancy and improve data integrity by decomposing large, poorly structured tables into smaller, well-structured ones.

Problems Without Normalization (Anomalies)

Consider the following unnormalized table:

1. Insertion Anomaly: A new course cannot be inserted unless at least one student is enrolled in it. The course data depends on student data being present.

2. Deletion Anomaly: If Student 2 (Sita) drops Course C01, the information about Dr. Sharma teaching DBMS is also lost.

3. Update Anomaly: If Dr. Sharma's name changes, it must be updated in every row where C01 appears. Missing even one row causes inconsistency.

Goals of Normalization

• Eliminate redundant data
• Ensure data dependencies make sense
• Make the database easier to maintain
• Reduce storage space

First Normal Form (1NF)

Definition

A relation is in 1NF if:

• All attributes contain atomic (indivisible) values
• There are no repeating groups or multi-valued attributes
• Each column contains values of a single type
• Each row is uniquely identifiable

Example

Violation of 1NF:

Here, the Courses column has multiple values -- this violates 1NF.

After converting to 1NF:

Now every attribute is atomic. The table is in 1NF.

Second Normal Form (2NF)

Definition

A relation is in 2NF if:

• It is already in 1NF
• Every non-key attribute is fully functionally dependent on the entire primary key (no partial dependency)

Partial Dependency: A non-key attribute depends on only a part of a composite primary key.

Example

Consider the table (Primary Key = {StudentID, CourseID}):

Functional Dependencies:

• {StudentID, CourseID} --> Grade (full dependency -- OK)
• StudentID --> StudentName (partial dependency -- violates 2NF)
• CourseID --> CourseName (partial dependency -- violates 2NF)

After converting to 2NF (decompose):

Student Table:

Course Table:

Enrollment Table:

Now all non-key attributes are fully dependent on the whole primary key. The tables are in 2NF.

Third Normal Form (3NF)

Definition

A relation is in 3NF if:

• It is already in 2NF
• There is no transitive dependency -- no non-key attribute depends on another non-key attribute

Transitive Dependency: If A --> B and B --> C, then A --> C is a transitive dependency (C depends on A through B).

Example

Consider the table (Primary Key = StudentID):

Functional Dependencies:

• StudentID --> DeptID (direct dependency -- OK)
• DeptID --> DeptName (DeptName depends on DeptID, not on StudentID)
• Therefore: StudentID --> DeptID --> DeptName (transitive dependency -- violates 3NF)

After converting to 3NF (decompose):

Student Table:

Department Table:

Now there is no transitive dependency. Both tables are in 3NF.

Summary Table

Conclusion

Normalization is required because an unnormalized table stores the same fact in many rows, which wastes space and, more seriously, allows the copies to disagree. Removing repeating groups gives 1NF, removing partial dependency on part of a composite key gives 2NF, and removing transitive dependency through a non-key attribute gives 3NF. Each step replaces one table by two smaller tables joined on a key, so the insertion, deletion and update anomalies disappear while the original information can still be recovered by a join. Most practical database designs stop at 3NF (or BCNF), since further decomposition begins to cost more in join time than it saves in redundancy.

• Person (Pid, pname, dob, paid) - Doctor (Did, pid, dname, dspeciality) Note: Standard relational algebra operations are used below, consistent with Tribhuvan University CSIT curriculum. --- To find the names of persons who are also doc...