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

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.

Data Independence and Three Schema Architecture

What is Data Independence?

Data independence is the ability to modify the schema definition at one level of the database system without affecting the schema definition at the next higher level.

In simple terms, it means changes made to the structure or storage of data do not require changes to the application programs that use the data.

There are two types of data independence:

Three Schema Architecture

The ANSI/SPARC Three Schema Architecture divides the database into three levels:

+-----------------------------+
|   External Level (View)     |  <-- User views / subschemas
+-----------------------------+
|   Conceptual Level          |  <-- Logical structure of entire DB
+-----------------------------+
|   Internal Level            |  <-- Physical storage details
+-----------------------------+

1. External Schema (View Level): Describes how individual users or groups see the data. Different users can have different views.

2. Conceptual Schema: Describes the overall logical structure of the entire database -- what data is stored, relationships, constraints, etc.

3. Internal Schema: Describes the physical storage structure -- file organization, indexes, access paths, etc.

How Three Schema Architecture Ensures Data Independence

1. Physical Data Independence

• Achieved through the mapping between Internal and Conceptual levels.
• If the physical storage is changed (e.g., changing file organization, adding indexes, moving data to new storage), only the internal schema and its mapping to the conceptual schema need to be updated.
• The conceptual schema remains unchanged, so application programs and user views are not affected.
• Example: Changing a sequential file to a B-tree index does not affect the logical description of the data.

2. Logical Data Independence

• Achieved through the mapping between Conceptual and External levels.
• If the conceptual schema is changed (e.g., adding a new attribute, splitting a table), only the mapping between conceptual and external schemas needs to be updated.
• The external schemas (user views) remain unchanged, so application programs are not affected.
• Example: Adding a new column to a table does not affect existing user views that do not use that column.

Summary

Change in Internal Schema
        |
        v
  Update Internal-Conceptual Mapping  --> Physical Data Independence
        |
        v
  Conceptual Schema unchanged
        |
        v
  Update Conceptual-External Mapping  --> Logical Data Independence
        |
        v
  External Schema (Applications) unchanged

The three schema architecture acts as a buffer between levels, ensuring that changes at one level are isolated from other levels, thus providing both physical and logical data independence.

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