Normalization

Normalization is a systematic process of organizing data in a database to reduce data redundancy and improve data integrity. It involves dividing larger tables into smaller, more manageable tables and defining relationships between them. The primary goal is to eliminate undesirable characteristics like insertion, update, and deletion anomalies.

Purpose of Normalization

The main objectives of normalization are:

• Reducing Redundancy: Minimizing the duplication of data across different tables.
• Improving Data Integrity: Ensuring the accuracy and consistency of data.
• Avoiding Anomalies: Preventing issues that arise when data is inserted, updated, or deleted incorrectly.
• Simplifying Database Design: Making the database structure more logical and easier to manage.
• Enhancing Query Performance: Well-normalized databases often lead to faster query execution.

Normal Forms

There are several normal forms, each with specific rules. The most commonly used are First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), and Boyce-Codd Normal Form (BCNF).

First Normal Form (1NF)

A relation is in 1NF if all its attributes contain atomic values. This means that each cell in the table should hold only a single value, and there should be no repeating groups of columns.

Example: A table with a 'Phone Numbers' column that contains multiple numbers for one person is not in 1NF. To achieve 1NF, this would be split into multiple rows or a separate table.

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and all its non-prime attributes are fully functionally dependent on every candidate key. This means that no non-prime attribute should be dependent on only a part of a composite candidate key.

Condition: Must be in 1NF and no partial dependencies.

Example: Consider a table `Student_Course` with columns (StudentID, CourseID, StudentName, CourseName, Grade). If (StudentID, CourseID) is the composite key, and `StudentName` depends only on `StudentID`, and `CourseName` depends only on `CourseID`, then there are partial dependencies. To achieve 2NF, we would create separate tables: `Students` (StudentID, StudentName), `Courses` (CourseID, CourseName), and `Enrollment` (StudentID, CourseID, Grade).

Third Normal Form (3NF)

A relation is in 3NF if it is in 2NF and all its non-prime attributes are nontransitively dependent on every candidate key. This means that no non-prime attribute should be dependent on another non-prime attribute.

Condition: Must be in 2NF and no transitive dependencies.

Example: Consider a table `Employee` with columns (EmployeeID, EmployeeName, DepartmentID, DepartmentName, DepartmentLocation). If `EmployeeID` determines `DepartmentID`, and `DepartmentID` determines `DepartmentName` and `DepartmentLocation`, then `DepartmentName` and `DepartmentLocation` are transitively dependent on `EmployeeID`. To achieve 3NF, we would create: `Employee` (EmployeeID, EmployeeName, DepartmentID) and `Department` (DepartmentID, DepartmentName, DepartmentLocation).

Boyce-Codd Normal Form (BCNF)

BCNF is a stricter version of 3NF. A relation is in BCNF if for every non-trivial functional dependency X → Y, X is a superkey. This means that the determinant (X) must be a candidate key.

Condition: Must be in 3NF and for every functional dependency X → Y, X must be a superkey.

Example: Consider a table `Student_Advisor` (StudentID, CourseID, AdvisorID). Assume a student can have multiple advisors for different courses, and an advisor advises multiple students for multiple courses. Let the candidate key be (StudentID, CourseID). Suppose an advisor can advise only one student per course. Functional dependencies: (StudentID, CourseID) → AdvisorID, and AdvisorID → StudentID (an advisor advises a specific student). The second dependency violates BCNF because AdvisorID is not a superkey. To fix this, we might need to decompose the table further.

Query Processing and Optimization

Query processing is the process by which a database management system (DBMS) executes a user's query. Query optimization is the technique used to find the most efficient way to execute a given query. The goal is to minimize the execution time and resource consumption.

Phases of Query Processing

A typical query processing involves several stages:

1. Parsing and Translation: The SQL query is parsed to check for syntax errors and translated into an internal representation, often a relational algebra expression or a query tree.
2. Optimization: The system generates multiple possible execution plans for the query and selects the most efficient one based on cost estimation.
3. Execution: The chosen execution plan is executed by the DBMS to retrieve the results.

Query Optimization Techniques

Query optimizers aim to find the cheapest execution plan. This involves considering various factors like the size of relations, the availability of indexes, and the cost of different join methods.

Cost Estimation

The optimizer estimates the cost of each plan. Costs are typically measured in terms of I/O operations, CPU usage, and the number of tuples processed.

Join Order Optimization

The order in which tables are joined can significantly impact performance. For a query involving multiple joins (e.g., R JOIN S JOIN T), the optimizer considers different join orders like ((R JOIN S) JOIN T) or (R JOIN (S JOIN T)). It uses statistics about the data (e.g., number of tuples, selectivity of predicates) to estimate the size of intermediate results and choose the order that produces the smallest intermediate results.

Join Methods

Different algorithms can be used for joining two relations:

• Nested Loop Join: For each tuple in the outer relation, scan the inner relation to find matching tuples. Simple but can be inefficient for large relations.
• Block Nested Loop Join: Reads blocks of tuples from the outer relation into memory and then scans the inner relation for each block.
• Index Nested Loop Join: Uses an index on the join column of the inner relation to quickly find matching tuples.
• Sort-Merge Join: Sorts both relations on the join attribute and then merges them. Efficient if relations are already sorted or can be sorted efficiently.
• Hash Join: Builds a hash table on the join attribute of the smaller relation and probes it with tuples from the larger relation. Very efficient for large, unsorted relations.

Predicate Evaluation

Optimizers try to apply selection predicates as early as possible in the execution plan to reduce the number of tuples processed in subsequent operations.

Use of Indexes

Indexes (like B-trees or hash indexes) can significantly speed up selection and join operations by allowing the DBMS to quickly locate relevant tuples without scanning the entire table.

Transaction Processing

A transaction is a sequence of operations performed by a database system as a single logical unit of work. For example, transferring money from one bank account to another involves debiting one account and crediting another; these two operations must be treated as a single transaction.

ACID Properties

To ensure data integrity and consistency, transactions must adhere to the ACID properties:

• Atomicity: A transaction is an indivisible unit. Either all its operations are completed successfully, or none of them are. If a transaction fails midway, the system must roll back all changes made by it.
• Consistency: A transaction must transform the database from one valid state to another. It must not violate any database constraints.
• Isolation: The execution of one transaction must be independent of other concurrently executing transactions. The effect of concurrent transactions should be the same as if they were executed serially.
• Durability: Once a transaction has been committed, its changes are permanent and will survive any subsequent system failures (e.g., power outages, crashes).

Transaction States

A transaction goes through several states during its lifecycle:

• Active: The transaction is executing its operations.
• Partially Committed: The last operation has been executed, and the transaction is being validated.
• Committed: The transaction has successfully completed and its changes are permanently stored.
• Failed: The transaction cannot proceed further due to some error. It must be rolled back.
• Aborted: The transaction has been rolled back. It may be restarted.

Transaction Log

A transaction log (or journal) is a crucial component for ensuring atomicity and durability. It records all changes made to the database before they are actually written to the database files. This log is used for recovery purposes.

Concurrency Control

Concurrency control mechanisms are used to manage simultaneous execution of transactions in a multi-user database system to ensure data consistency and integrity, while allowing as much concurrency as possible. The main challenge is to prevent the anomalies that can arise from concurrent access.

Concurrency Problems

When multiple transactions access the same data concurrently, several problems can occur:

• Lost Update: Two transactions read the same data, modify it, and write it back. The update made by one transaction is lost because the other transaction overwrites it without considering the first update.
• Dirty Read (Uncommitted Dependency): A transaction reads data that has been modified by another transaction, but the modifying transaction has not yet committed. If the modifying transaction aborts, the first transaction will have read invalid data.
• Non-repeatable Read: A transaction reads a data item twice, but between the two reads, another committed transaction modifies or deletes the data item. The second read returns a different value than the first.
• Phantom Read: A transaction executes a query twice, but between the two executions, another committed transaction inserts new rows that satisfy the query's condition. The second execution returns more rows than the first.

Concurrency Control Techniques

Several techniques are used to prevent these problems:

1. Locking Protocols

Locking involves granting temporary exclusive access to data items to transactions. Transactions must acquire a lock before accessing a data item and release it when done.

• Shared Lock (S-lock): Allows a transaction to read a data item but not modify it. Multiple transactions can hold a shared lock on the same item.
• Exclusive Lock (X-lock): Allows a transaction to read and modify a data item. Only one transaction can hold an exclusive lock on an item at a time.

Two-Phase Locking (2PL): A protocol where each transaction follows two phases:

• Growing Phase: The transaction acquires locks but does not release any.
• Shrinking Phase: The transaction releases locks but does not acquire any new ones.

Strict Two-Phase Locking (Strict 2PL): All exclusive locks are held until the transaction commits or aborts. This prevents dirty reads and cascading rollbacks.

2. Timestamp Ordering

Each transaction is assigned a unique timestamp when it begins. The DBMS uses these timestamps to determine the serial order of transactions. Read and write operations are validated against the timestamps of other transactions to ensure consistency.

• Read Timestamp (RTS): The timestamp of the latest transaction that read the data item.
• Write Timestamp (WTS): The timestamp of the latest transaction that wrote the data item.

If a transaction T_i attempts to read a data item X:

• If T_i's timestamp is less than WTS(X), it's a potential read-after-write problem, so T_i must be aborted.
• Otherwise, the read is allowed, and RTS(X) is updated to max(RTS(X), T_i's timestamp).

If T_i attempts to write X:

• If T_i's timestamp is less than RTS(X) or WTS(X), it's a potential write-after-read or write-after-write problem, so T_i must be aborted.
• Otherwise, the write is allowed, and WTS(X) is updated to T_i's timestamp.

3. Multi-Version Concurrency Control (MVCC)

MVCC maintains multiple versions of data items. When a transaction needs to read data, it accesses the version that was current at the time the transaction began or at the time of its read request, depending on the isolation level. This allows readers to not block writers and vice-versa, increasing concurrency.

4. Optimistic Concurrency Control (OCC)

OCC assumes that conflicts are rare. Transactions proceed without acquiring locks. During the commit phase, each transaction checks if any conflicts occurred. If a conflict is detected, the transaction is aborted and restarted.

Recovery Techniques

Recovery techniques are essential for restoring the database to a consistent state after a failure (e.g., system crash, power outage, media failure). These techniques rely on the information stored in the transaction log.

Types of Failures

• Transaction Failures: A transaction terminates abnormally due to errors (e.g., constraint violation, invalid input).
• System Failures: The operating system or hardware fails, causing the DBMS to crash.
• Media Failures: A disk or storage device becomes corrupted or lost.

Recovery Based on Logs

The transaction log contains records of all operations performed by the system. Recovery involves using this log to undo the effects of incomplete transactions and redo the effects of committed transactions that may not have been fully written to disk.

Log Records

Common log records include:

• START TRANSACTION: Marks the beginning of a transaction.
• WRITE ITEM: Records the old and new values of a data item that has been modified.
• COMMIT TRANSACTION: Marks the successful completion of a transaction.
• ABORT TRANSACTION: Marks the abortion of a transaction.

Recovery Process

When the system restarts after a failure, it performs the following steps:

1. Analyze the Log: The log is scanned to identify transactions that were active at the time of the crash.
2. Redo Operations: For all transactions that committed before the crash, their operations are redone using the log records to ensure their changes are applied to the database. This is necessary because some changes might have been logged but not yet written to the main database files.
3. Undo Operations: For all transactions that did not commit before the crash (i.e., were in the active or partially committed state), their operations are undone using the log records. This involves restoring the old values of the modified data items as recorded in the log.

Logging Techniques

• Write-Ahead Logging (WAL): A fundamental principle where log records must be written to stable storage *before* the corresponding data blocks are written to disk. This ensures that even if the system crashes after writing the log but before writing the data, the log contains enough information to recover the data.
• Immediate Database Updates: Data blocks are updated on disk as soon as a transaction modifies them. Recovery involves undoing changes from uncommitted transactions.
• Deferred Database Updates: Updates are not immediately written to disk. Instead, they are recorded in the log. Only after a transaction commits are the updates applied to the database. Recovery involves redoing all committed transactions.

Checkpoints

A checkpoint is a point in time where the system ensures that all transaction log records up to that point have been written to stable storage, and all corresponding database updates have also been written to disk. Checkpoints reduce the amount of log that needs to be scanned during recovery. When the system restarts, it only needs to consider log records after the most recent checkpoint.