ADVANCED DATABASE

i
CHAPTER ONE only be between 0 and 100. If someone tries to
enter a grade of 150, that would violate the
TRANSACTION CONCEPT consistency rule because it's outside the allowed
range.

The concept of a transaction in advanced Consistency ensures that the data in the database
databases refers to a sequence of operations or is reliable and makes sense. It helps prevent
actions performed on a database as a single mistakes or incorrect information from being
logical unit. Imagine you are shopping online and stored in the database. Just like following the
adding items to your cart, entering your shipping rules of a game makes it fair for everyone,
address, and making the payment. All these maintaining consistency in a database ensures
actions collectively form a transaction. fairness and accuracy in the data.

Transactions are important because they ensure

that the database remains consistent and reliable.
3. Isolation: Transactions should be isolated
They follow the ACID properties: from each other, which means that the
operations within a transaction should not
1. Atomicity: A transaction is atomic,
interfere with other concurrent
meaning it is treated as a single
transactions. This prevents conflicts and
indivisible unit of work. Either all the
ensures that each transaction sees a
operations within a transaction are
consistent view of the data. In our online
completed successfully, or none of them
shopping example, if two customers are
are. In our online shopping example,
simultaneously adding items to their carts,
either the entire process of adding items
the system should ensure that they do not
to the cart, entering the address, and
accidentally add the same item, and each
making the payment is completed, or
customer sees their own separate cart.
none of it is.
4. Durability: Once a transaction is
2. Consistency: A transaction takes the
successfully completed, its changes are
database from one consistent state to
permanent and should persist even in the
another. It means that the data in the
event of system failures. The data changes
database should satisfy all the predefined
made during the transaction should be
rules and constraints. For instance, if you
stored securely and not lost. In our online
have a rule that a customer cannot
shopping example, once you've
purchase more items than their available
successfully made the payment, the
credit limit, the transaction should ensure
system ensures that the transaction is
that this rule is not violated.
permanently recorded, and your purchase
Imagine you have a set of rules for playing a is not lost even if there is a power outage
game. Consistency means that you always follow or a server crash.
those rules, and everyone playing the game
By adhering to these ACID properties,
follows the same rules too. It's like having a fair
transactions provide reliability and integrity to
and equal game for everyone.
database operations. They ensure that the
In a database, consistency means that the data database remains consistent and that multiple
follows certain rules or conditions that are set for concurrent users can work on the database
it. For example, let's say you have a database of without interfering with each other.
students' grades, and the rule is that a grade can
INTRODUCTION TO TRANSACTION commonly used in various real-life situations to
handle different processes smoothly.
A transaction is like a package of actions that
Imagine you have a set of Lego blocks, and you
you do all together as if they were just one
want to build a specific structure. To make sure
thing. For example, imagine you want to buy
everything goes smoothly, you decide to work on
something from a store. The transaction includes
one block at a time. You start by picking up a
different steps like choosing the item, paying for
block and place it in the right spot. Once it's in
it, and getting a receipt. All of these actions are
the right place, you consider it completed and
grouped together as one transaction.
move on to the next block. If something goes
In a database, a transaction is a similar concept. wrong with a block, you put it back where it
It involves a set of actions that work together as was before you started.
a single logical unit. These actions can include
In a similar way, a transaction in a database is
reading information from the database (like
like working with Lego blocks. It's an atomic unit
checking the price of an item), writing or
of work, which means it's a single task that
updating data (like adding your purchase to the
needs to be done all at once or not at all. Just
store's records), or deleting data (like removing
like completing a block before moving on to the
an item from inventory).
next one, a transaction needs to be completed
Transactions are used in many real-life scenarios. entirely or not done at all.
For instance, when you withdraw money from an
To keep track of transactions, the system needs
ATM, the transaction includes checking your
to know when they start, when they end, and
account balance, subtracting the withdrawn
whether they are successfully completed or not.
amount, and updating the balance. Similarly,
It's like having a record of when you start
when you make a credit card purchase, the
building with the Lego blocks, when you finish,
transaction involves verifying your card,
and whether the structure is successfully
deducting the amount from your account, and
completed or needs to be undone.
recording the transaction details.
In application programs, transactions are
Other examples of transactions include making
separated by "begin" and "end" statements. Think
flight reservations, checking into a hotel,
of them as markers that indicate the start and
scanning items at a supermarket, registering for
end of a transaction. An application program can
classes at school, or receiving a bill for your
have several transactions, and each transaction is
purchases. Each of these scenarios involves
bounded by these "begin" and "end" statements.
multiple steps, and all the steps together form a
It's like having multiple sets of Lego blocks, and
transaction.
each set represents a different transaction that
The purpose of having transactions is to ensure you're working on.
that everything happens correctly and reliably. It's
These transaction boundaries help in organizing
like having a safety net that guarantees that
and managing the work. They ensure that each
either all the steps of the transaction are
transaction is treated as a separate unit and can
completed successfully, or none of them are. This
be tracked individually. If something goes wrong
helps maintain the integrity and consistency of
with a transaction, it can be aborted, just like
the database, making sure that the information
undoing the work with a set of Lego blocks if
stored remains accurate and reliable.
you make a mistake.
So, transactions are like bundles of actions that
So, in simpler terms, a transaction is like
are treated as a single unit. They are used to
working with Lego blocks, where each block
make sure that operations on the database are
represents a step in the transaction. The
done correctly and consistently, and they are
transaction needs to be completed entirely or not
done at all. Application programs use "begin" and item from a list. It allows you to remove
"end" statements to mark the boundaries of data from the database. For example, you
transactions, allowing multiple transactions to be might want to delete a customer's account
managed separately. Keeping track of transactions when they request to close it or remove a
helps in recovery and ensuring that the work is product from the inventory that is no
done correctly and consistently. longer available.

BASIC TRANSACTION OPERATIONS These basic transaction operations — read, write,

insert (or update), and delete—are the building
In a transaction, there are four basic operations blocks of working with a database. They allow
that can be performed on a database: read, write, you to retrieve, modify, add, and remove data to
insert (or update), and delete. Let's define each of perform various tasks and maintain the accuracy
these operations in simpler terms: and integrity of the database.

1. Read: The read operation is like looking "Read_item(X)" command includes the following
up information in a book or searching for steps :-
something on the internet. It allows you
1. Find the address of the disk block that
to retrieve data from the database without
contains item X: Imagine you have a
making any changes to it. For example,
bookshelf with many books, and you want
you might want to read the price of a
to find a specific book called X. To do
product or check the availability of an
that, you need to know which bookshelf
item in a store's inventory.
and which shelf on that bookshelf holds
2. Write: The write operation is like taking a the book X. Similarly, in a database, the
pen and making changes to a book or "Read_item(X)" command needs to find
document. It allows you to modify the location (address) of the disk block
existing data in the database. For where the data for item X is stored.
example, you might want to update the
2. Copy the disk block into a buffer in main
quantity of an item in the inventory when
memory: Think of the buffer in main
it is sold or change the address associated
memory as a temporary storage area, like
with a customer's account.
a desk or table, where you can place the
Insert (or Update): The insert operation is book you want to read. Before you can
like adding a new page to a book or read the book, you need to take it from
inserting a new entry into a list. It allows the bookshelf and put it on the desk.
you to add new data to the database. For Similarly, the database system copies the
example, you might want to insert a new disk block that contains item X from the
customer's information when they create disk storage to a buffer in main memory,
an account or add a new product to the if it's not already there. This makes it
inventory. easier and faster to access and manipulate
the data.
Update is similar to insert, but instead of
adding entirely new data, it modifies 3. Copy item X from the buffer to the
existing data in the database. It's like program variable named x: Once the disk
editing or correcting information in a block is in the buffer, it's like having the
book or document. For example, you book you want to read on the desk. Now,
might want to update a customer's phone you can open the book and find the
number or change the price of a product. specific information you're looking for,
which is item X. In the database, the
3. Delete: The delete operation is like tearing
system copies the specific data for item X
a page out of a book or removing an
 from the buffer in main memory to a you want to work on placed on the desk.
program variable named x. This allows You can open the book and make changes
the program or application to work with to the specific information you're
the data and perform any necessary interested in, which is item X. In the
operations or calculations on it. database, the system copies the updated
data for item X from the program variable
So, in simpler terms, the "Read_item(X)"
named X and places it in the correct
command involves finding the location of the disk
location within the buffer in main
block that contains the data for item X, bringing
memory. This ensures that the changes
that disk block into a temporary storage area
are applied to the right place in the
called a buffer in main memory, and then
buffer.
copying the specific data for item X from the
buffer into a program variable named x. This 4. Store the updated block from the buffer
allows the program to access and work with the back to disk: Once you have made the
data effectively. necessary changes to the data in the
buffer, it's like having the book on the
desk all updated and ready to be placed
"write_item(X)" command includes the following
back on the bookshelf. In the database,
steps :-
the system stores the updated disk block
1. Find the address of the disk block that from the buffer back to the disk storage.
contains item X: Imagine you have a This ensures that the changes you made
bookshelf with many books, and you want to item X are permanently saved and
to find a specific book called X to update stored on the disk. The updated data may
or make changes to it. To do that, you be written back to the disk immediately
need to know which bookshelf and which or at a later point in time, depending on
shelf on that bookshelf holds the book X. the system's implementation.
Similarly, in a database, the
So, in simpler terms, the "write_item(X)"
"write_item(X)" command needs to find
command involves finding the location of the disk
the location (address) of the disk block
block that contains the data for item X, bringing
where the data for item X is stored.
that disk block into a temporary storage area
2. Copy the disk block into a buffer in main called a buffer in main memory, copying the
memory: Think of the buffer in main updated data for item X from the program
memory as a temporary storage area, like variable named X into the correct location in the
a desk or table, where you can place the buffer, and finally, storing the updated block
book you want to work on. Before you from the buffer back to the disk storage. This
can make changes to the book, you need ensures that the changes made to item X are
to take it from the bookshelf and put it correctly saved and persist in the database.
on the desk. Similarly, the database
system copies the disk block that contains
item X from the disk storage to a buffer
in main memory, if it's not already there.
This makes it easier and faster to access
and modify the data.

3. Copy item X from the program variable

named X into its correct location in the
buffer: Now that you have the disk block
in the buffer, it's like having the book
Example:- Imagine we have two transactions Transaction 2:

1. read_item(x): In this step, we read the

current value of variable x from the
database. It's like checking your own bank
account balance again.
2. x := x + M: Here, we add a specific
amount M to the value of x. It's like
depositing or adding money to your
account, where x represents your current
balance and M represents the amount
you're depositing.
3. write_item(x): This step involves updating
Transaction 1:
the value of x in the database with the
1. read_item(x): In this step, we retrieve the new result after adding M. It's like
current value of a variable named x from recording the updated balance in your
the database. It's like looking at your bank account after making the deposit.
bank account balance to see how much
So, in simpler terms, transaction 1 involves
money you currently have.
reading the value of x, subtracting N from x and
2. x := x - N: Here, we subtract a specific
recording the updated value, reading the value of
amount N from the value of x. It's like
y, adding N to y, and recording the updated
transferring or giving some money to a
value. Transaction 2 involves reading the value of
friend, where the value of x represents
x, adding M to x, and recording the updated
your current balance, and N represents
value.
the amount you're transferring.
3. write_item(x): This step involves updating These transactions simulate financial transactions
the value of x in the database with the like transferring money to a friend (transaction 1)
new result after subtracting N. It's like and making a deposit to your own account
recording the updated balance in your (transaction 2). Each step within a transaction is
bank account after transferring the performed as a single unit, ensuring consistency
money. and integrity in the database.
4. read_item(y): Now, we read the current
TRANSACTION STATES
value of another variable named y from
the database. It's like checking your
friend's account balance to see how much
money they have.
5. y := y + N: Here, we add a specific
amount N to the value of y. It's like
adding the transferred amount to your
friend's account, where y represents their
current balance and N represents the
amount received.
6. write_item(y): This step involves updating Active State: This is the initial state of a
the value of y in the database with the transaction. It indicates that the transaction has
new result after adding N. It's like started and is currently executing its operations.
recording the updated balance in your It's like a person starting a task or process.
friend's account after they receive the Partially Committed State: When a transaction
money. reaches this state, it means that all the operations
within the transaction have been executed marking it as done yet. The committed state is
successfully, and the transaction is ready to be when the task is officially completed. The failed
committed. However, it has not been committed state is when you encounter an error or problem
yet. It's like completing a task but not officially during the task. The aborted state is like undoing
marking it as done. the work and going back to the starting point.
The incomplete state is when you're still in the
Committed State: When a transaction is
middle of the task and haven't finished or
committed, it means that all its operations have
encountered any errors yet.
been successfully executed, and the changes made
by the transaction have been permanently saved These transaction states help in managing and
in the database. It's like marking a task as tracking the progress of transactions in a
completed and making it officially done. database, ensuring that changes are applied
correctly and consistently.
Failed State: If a transaction encounters an error
or failure during its execution, it enters the failed DATABASE LOG RECORDS
state. It indicates that one or more operations
within the transaction were not successful. It's In a database system, a log record is a
like encountering a roadblock or obstacle while mechanism used to keep a record of different
trying to complete a task. actions performed by transactions. It acts as a
chronological record of events, capturing the
Aborted State: When a transaction is aborted, it
changes made to the database during
means that it was unable to complete its
transactional operations. These log records are
operations successfully or encountered an error.
essential for ensuring the reliability, consistency,
In this state, any changes made by the
and recoverability of the database.
transaction are discarded, and the database is
rolled back to the state it was in before the Log records are typically used in conjunction with
transaction started. It's like undoing the work a unique transaction identifier (referred to as T in
done in a task and reverting to the previous this context) that is automatically generated by
state. the system. This transaction ID helps identify and
associate each log record with a specific
Incomplete State: If a transaction is neither
transaction.
committed nor aborted, it is in an incomplete
state. It indicates that the transaction is still in There are various types of log records commonly
progress and has not reached a final state yet. It's used in database systems:
like being in the middle of a task and not having
1. [start_transaction, T]: This log record
completed it or encountered any errors.
indicates the beginning of a transaction
Terminated State :- The "terminated" state refers with the unique identifier T. It serves as
to the state of a transaction after it has a marker for when a transaction starts its
completed its execution, whether it has been execution.
committed or aborted. In this state, the
2. [write_item, T, X, old_value, new_value]:
transaction has finished its work, and its impact
This log record represents a modification
on the database has been finalized. It does not
made by a transaction with identifier T to
actively participate in any further operations or
a database item X. It includes the old
modifications.
value and the new value of the item to
In simpler terms, the different transaction states track the change made by the transaction.
can be compared to the stages of completing a
3. [read_item, T, X]: This log record signifies
task. The active state is when you start working
that a transaction with identifier T has
on something. The partially committed state is
read the value of a specific database item
like completing the task but not officially
 X. It records the transaction's access to To perform the transfer, the transaction goes
the item without altering its value. through two steps: subtracting 750 birr from
Account A and adding 750 birr to Account B.
4. [commit, T]: This log record indicates the
However, just after subtracting the money from
successful completion of a transaction
Account A, but before adding it to Account B, a
with identifier T. It confirms that the
failure occurs (like a power outage or hardware
changes made by the transaction can be
failure).
permanently recorded (committed) in the
database. Now, the database is in an inconsistent state
because the transaction was not completed.
5. [abort, T]: This log record signifies that a
Account A lost 750 birr, but Account B did not
transaction with identifier T has been
receive it. It's like having an incomplete
aborted or canceled. It denotes that the
transaction where one account lost money, and
transaction was unable to complete
the other account didn't receive it.
successfully, and any changes made by it
should be discarded. To ensure consistency, a reliable database
management system (DBMS) has the capability to
These log records play a vital role in database
restore the old values. It means that the DBMS
management, allowing for recovery in the event
can roll back the changes made by the
of system failures, providing transactional
transaction and bring the database back to its
consistency, and enabling auditing and analysis of
previous state. In this case, the DBMS can restore
database operations.
the lost 750 birr to Account A, ensuring that the
By capturing the sequence of events and changes data is consistent and accurate.
made by transactions, log records help ensure
In simpler terms, the example demonstrates
data integrity, facilitate system recovery, and
atomicity by showing that either the entire
provide a historical trail of database activities.
transaction (subtracting from Account A and
DESIRABLE PROPERTIES OF TRANSACTION adding to Account B) should happen or none of it
should happen. If a failure occurs in the middle,
Desirable properties of a transaction, often the DBMS can restore the data to maintain
referred to as the ACID properties, are crucial for consistency and ensure that no money is lost in
ensuring the reliability and integrity of database the process.
operations. Let's define and explain each property
in simpler terms, along with examples: Consistency: Consistency refers to ensuring that a
transaction, when executed correctly, takes the
Atomicity: Atomicity ensures that a transaction is database from one valid and consistent state to
treated as a single indivisible unit of work. It another. It means that the data in the database
means that either all the operations within a should satisfy all the predefined rules, constraints,
transaction are completed successfully, or none of and integrity conditions before and after the
them are. It's like an "all or nothing" principle. transaction.
For example, if you transfer money from one
bank account to another, either the entire In the example given, before the transaction,
transfer is successful, and both accounts are Account A had 5000 birr, and Account B had
updated, or no money is transferred at all. 8000 birr. The transaction aimed to transfer 750
birr from Account A to Account B.
Example :- Imagine you have two bank accounts,
Account A and Account B. Account A has 5000 After the transaction is completed successfully,
birr, and Account B has 8000 birr. You want to the new state of the database should still adhere
transfer 750 birr from Account A to Account B. to the integrity constraints. In this case, the
updated balances are Account A with 4250 birr
and Account B with 8750 birr.
The consistency property ensures that the manipulates data, but the isolation property
integrity constraints are maintained. In this ensures that these transactions do not collide or
example, the sum of the account balances, 4250 interfere with each other. The changes made by
birr (Account A) and 8750 birr (Account B), one transaction should not be visible to other
equals the initial sum of 13000 birr (5000 birr + transactions until it has completed successfully
8000 birr). This demonstrates that the database and brought the database to a consistent state.
remains consistent and satisfies the predefined
For example, imagine two customers making
rules even after the transaction.
withdrawals from their bank accounts at the same
In simpler terms, consistency means that the time. Isolation ensures that each customer's
transaction should not violate any predefined transaction is treated independently, and the
rules or constraints. In the example, the system safeguards against any issues that may
transaction ensures that the total amount of arise from concurrent withdrawals. The balances
money in the accounts remains the same (13000 and availability of funds are correctly managed
birr) before and after the transaction. It confirms for each customer, and one customer's withdrawal
that the transfer of 750 birr from Account A to does not impact the other customer's transaction.
Account B is done correctly, maintaining the
In summary, isolation property in a database
overall balance and integrity of the database.
ensures that concurrent transactions are isolated
Consistency in a database ensures that data from one another. Each transaction operates as if
remains reliable and accurate throughout the it's the only one running, and changes made by a
execution of transactions, preventing any transaction are not visible to other transactions
inconsistencies or violations of predefined rules. until it has successfully completed, ensuring data
consistency and preventing interference or
To ensure the consistency , the sum of the
conflicts between transactions.
accounts before and after transaction must be the
same , here 5000 + 8000 = 12,000 and 4250 + Example :- In this scenario, we have two
8750 = 12,000 // concurrent transactions, T1 and T2, that involve
transferring money from Account A to Account B.
Isolation: Isolation ensures that concurrent
Transaction T1 transfers a fixed amount of $750,
transactions do not interfere with each other
while Transaction T2 transfers 20% of the amount
while executing simultaneously. Isolation property
from Account A to Account B. The initial
ensures that concurrent transactions, where
balances are Account A = $5000 and Account B =
multiple users access the shared database at the
$8000.
same time, do not interfere with each other. It
means that each transaction works in isolation To demonstrate the isolation property, we will
fashion, as if it is the only transaction running, show the execution of these transactions in a
and the data used by one transaction cannot be table. Since isolation ensures that transactions
accessed by any other transaction until it has work independently, we will keep the other
completed its execution. transaction's table empty while one transaction is
executing. This helps depict the isolation between
In simpler terms, isolation ensures that
the transactions.
transactions operate independently without
interfering with each other. It's like having
separate bubbles around each transaction, where
they can work without any knowledge or impact
of other transactions happening concurrently.

Consider a scenario where multiple users are

performing transactions simultaneously on a
shared database. Each transaction accesses and
 independently and do not interfere with each
other, ensuring isolation.

By maintaining the isolation property, the

database system ensures that concurrent
transactions can be executed safely and reliably
without causing conflicts or inconsistencies.

Example 2 :- Let's define the scenario where two

transactions, T1 and T2, do not satisfy the
isolation property. Before depicting the table, let's
start with a brief introduction:

In this scenario, we have two concurrent

Description of Transactions: transactions, T1 and T2, that involve transferring
money from Account A to Account B. However,
Transaction T1: these transactions do not adhere to the isolation
1. Read(A): This step retrieves the value of property, meaning they can interfere with each
Account A. other's execution. This can lead to inconsistencies
2. A = A - 750: It subtracts $750 from and incorrect results.
Account A.
3. Write(A): The updated value of Account A
is written back to the database.
4. Read(B): This step retrieves the value of
Account B.
5. B = B + 750: It adds $750 to Account B.
6. Write(B): The updated value of Account B
is written back to the database.

Transaction T2:

1. Read(A): This step retrieves the value of

Account A.
2. Temp = A * 0.2: It calculates 20% of the
value of Account A and stores it in the
temporary variable Temp.
Inconsistency leads to a data loss :- Data loss
3. A = A - Temp: It subtracts the calculated
refers to the situation where information or
Temp value from Account A.
changes made to a database are not properly
4. Write(A): The updated value of Account A
recorded or stored, resulting in the loss of
is written back to the database.
valuable data. It occurs when the database
5. Read(B): This step retrieves the value of
becomes inconsistent or experiences discrepancies,
Account B.
making it difficult or impossible to retrieve or
6. B = B + Temp: It adds the value of Temp
recover the original or accurate information.
to Account B.
7. Write(B): The updated value of Account B In the context of inconsistency, data loss can
is written back to the database. occur when transactions do not maintain the
necessary integrity and fail to ensure that the
In adherence to the isolation property, while
database remains in a consistent state. If the
Transaction T1 is executing, the Transaction T2
transactions do not adhere to the rules,
table remains empty and vice versa. This
demonstrates that the transactions work
constraints, or predefined conditions, it can lead Durability: It's like guaranteeing that once a
to data loss. transaction is successfully completed, its changes
are permanently saved and won't be lost.
For example, let's consider a scenario where two
transactions are attempting to update the same These properties work together to maintain the
data simultaneously without proper isolation. If reliability, consistency, and integrity of the
one transaction reads and modifies the data while database, ensuring that transactions are processed
the other transaction is in progress, it can lead to correctly and data remains accurate.
inconsistencies. In such a case, the changes made
by one transaction may overwrite or disregard SINGLE USER AND MULTI USER USERS
the changes made by the other transaction,
resulting in data loss. Single-User System: In a single-user system, only
one user interacts with the database at a time.
Data loss can have severe consequences, including
The user has exclusive access to the database and
incorrect or missing information, financial
performs transactions without interference from
discrepancies, or the inability to retrieve
other users. It's like having sole ownership of the
important data. It can impact the reliability and
database, where only one person can make
accuracy of the database, leading to potential
changes or access the data at any given time.
errors and operational issues.
In simpler terms, a single-user system is like
To prevent data loss, it's crucial to ensure that
having exclusive control over a database. Imagine
transactions follow proper guidelines and adhere
you have a personal diary that only you can
to the principles of consistency and isolation. By
write in. You can update, add, or retrieve
maintaining data integrity and avoiding
information from the diary without anyone else
inconsistencies, the risk of data loss can be
accessing or modifying it.
minimized, ensuring that the database remains
reliable and valuable for the intended purposes. Multi-User System: In a multi-user system,
multiple users can simultaneously access and
Durability: Durability ensures that once a
interact with the database. Each user can perform
transaction is successfully committed, its changes
transactions independently, accessing and
are permanent and will persist, even in the event
modifying the data concurrently. It's like having
of system failures or crashes. It means that the
shared access to the database, where multiple
updated data is stored securely and will not be
people can make changes or access the data
lost. For instance, when you book a flight ticket
simultaneously.
online and receive a confirmation, the durability
property ensures that your ticket remains valid, In simpler terms, a multi-user system is like
even if there is a power outage or server sharing a whiteboard with other people. Each
malfunction. person can write or erase information on the
whiteboard at the same time, and everyone can
In simpler terms, the ACID properties of a
see the changes made by others. However, to
transaction can be explained as follows:
ensure data consistency and prevent conflicts,
Atomicity: It's like an "all or nothing" rule, where there are mechanisms in place to manage
a transaction is either fully completed or not concurrent access and maintain data integrity.
done at all.
In a multi-user system, the DBMS (Database
Consistency: It's like ensuring that all the data
Management System) handles the coordination
changes made by a transaction follow the
and control of transactions to ensure that they
predefined rules and constraints.
don't interfere with each other. The DBMS
Isolation: It's like maintaining separate bubbles
manages concurrent access, enforces isolation,
for each transaction, so they don't interfere with
and ensures that transactions are executed
each other's work.
correctly and consistently. It provides mechanisms task receives a reasonable share of
such as locks, timestamps, and transaction processing time.
scheduling algorithms to prevent conflicts and
2. Parallel Processing: Parallel processing
maintain data integrity.
involves the simultaneous execution of
multiple tasks or processes using multiple
CONCURRENCY CPUs or processor cores. In this approach,
tasks are divided into smaller subtasks,
Concurrency refers to the ability of a system to and each subtask is executed on a
execute multiple tasks or processes separate CPU or core concurrently.
simultaneously. In the context of database
Advantages of Parallel Processing:
systems, concurrency allows multiple transactions
to be executed concurrently, enabling multiple • Increased processing speed: Parallel
users to access and modify the database processing allows tasks to be executed
concurrently. concurrently, resulting in faster processing
times for large-scale computations or
Concurrency provides several benefits, such as
data-intensive operations.
improved system throughput, increased user
• Enhanced scalability: With parallel
responsiveness, and efficient utilization of system
processing, additional CPUs or cores can
resources. However, it also introduces challenges,
be added to the system, enabling
such as ensuring data integrity, managing
scalability and accommodating increased
conflicts, and preventing inconsistencies.
workload or data volume.
Now let's define interleaved processing and • High-performance computing: Parallel
parallel processing, along with their advantages: processing is especially advantageous for
1. Interleaved Processing: Interleaved tasks that can be divided into independent
processing, also known as time-sharing or sub tasks, such as complex calculations,
concurrent processing, involves executing simulations, and data analytics.
multiple tasks or processes by interleaving
their execution on a single CPU. In this
approach, the CPU switches rapidly
between different tasks, allocating small
time slices to each task in a round-robin
or priority-based manner.

Advantages of Interleaved Processing:

• Improved responsiveness: Interleaved

processing allows multiple tasks or
transactions to make progress
simultaneously, providing a more
Both interleaved processing and parallel
responsive system for users.
processing offer advantages in different contexts.
• Efficient resource utilization: By sharing
Interleaved processing is suitable for systems with
the CPU among multiple tasks, interleaved
a single CPU and provides improved
processing maximizes the utilization of
responsiveness and resource utilization. Parallel
system resources, ensuring optimal
processing, on the other hand, leverages multiple
performance.
CPUs or cores to achieve higher processing speed
• Fairness in task execution: Interleaved
and scalability for computationally intensive tasks.
processing provides fair allocation of CPU
time to different tasks, ensuring that each
It's important to note that the choice between Resolving conflicts and maintaining consistency
interleaved processing and parallel processing while enforcing constraints can be more
depends on the system architecture, workload challenging than in read operations.
characteristics, and specific requirements of the
Overall, write operations can introduce more
application or database system.
complexities and potential conflicts in concurrent
THE WRITE OPERATION CAUSES MORE environments due to their impact on data
PROBLEM THAN THE READ OPERATION modifications and integrity constraints. Effective
concurrency control mechanisms, such as locking,
The write operation can cause more problems
isolation levels, and transaction management, are
than the read operation in concurrency control
employed to address these challenges and
due to its potential impact on data consistency
maintain data consistency and integrity in multi-
and integrity. There are a few key reasons for
user systems.
this:

Conflicting Updates: When multiple transactions PROBLEMS OF CONCURRENT TRANSACTION

attempt to write to the same data item
concurrently, conflicts can arise. Conflicting Data Inconsistency: Data inconsistency is a
updates occur when two or more transactions problem that can occur when multiple
modify the same data simultaneously. This can transactions are executing concurrently. It arises
lead to inconsistent or contradictory outcomes, when the interleaved execution of transactions
making it challenging to determine the correct leads to conflicts and inconsistent outcomes. For
state of the data. example, if two transactions simultaneously
modify the same data item, the final state of the
Overwriting Changes: In the case of lost updates,
data may be incorrect or contradictory, resulting
one transaction's changes to a data item can be
in data inconsistency.
overwritten by another transaction. If two
transactions both read and modify the same data In simpler terms, data inconsistency means that
concurrently, one transaction's modifications may the data becomes incorrect or contradictory when
get lost when the other transaction commits its multiple transactions are executing at the same
changes. This can result in data inconsistencies time. It can happen when transactions interfere
and the loss of valuable updates. with each other and make conflicting changes to
the same data, leading to inconsistent results.
Rollback and Undo Operations: In some
situations, a transaction may need to be rolled Lost Updates (Write Write Problem): Lost updates
back or undone due to conflicts or errors during occur when multiple transactions attempt to
execution. When a write operation is rolled back, modify the same data item simultaneously, and
it needs to revert the changes it made to the the changes made by one transaction are
data. This can be more complex and challenging overwritten or lost due to the interleaved
than undoing a read operation, as the write execution of transactions. This can lead to
operation may have altered the data in a way incorrect data or loss of valuable updates.
that affects other transactions or dependencies
In simpler terms, lost updates happen when one
within the database.
transaction's changes to data are lost because
Data Integrity Constraints: Write operations often another transaction overwrites them. It's like
involve enforcing data integrity constraints, such having two people editing the same document at
as primary key uniqueness, referential integrity, the same time, and one person's changes get
or other business rules. Concurrent write overwritten by the other person, resulting in lost
operations need to ensure that these constraints updates.
are maintained consistently to prevent data
corruption or violation of integrity rules.
The lost update problem occurs when the In this scenario, the problem arises because the
modifications made by one transaction to a data update made by Transaction T1 is lost or
item are overwritten or lost by the update overwritten by the update operation of
operation of another transaction before the first Transaction T2. Transaction T1 initially reads the
transaction can commit its changes. This can lead balance as $500, adds $100 to it, and intends to
to data inconsistencies and the loss of valuable write the updated balance as $600. However,
updates. before Transaction T1 can commit its changes,
Transaction T2 reads the balance as $500, adds
To illustrate this, let's consider a simple example
$200 to it, and writes the updated balance as
using a table:
$700. As a result, the update made by
Table: Bank Account Transaction T1 is lost, and the final balance is
$700 instead of $600.
Account Id Balance
This demonstrates how the lost update problem
1 $500
can occur when concurrent transactions attempt
to modify the same data, leading to the loss of
Suppose we have two transactions, T1 and T2, valuable updates and inconsistencies in the final
both attempting to update the balance of Account data state. Effective concurrency control
ID 1 concurrently. The initial balance is $500. mechanisms, such as proper locking and
synchronization techniques, are needed to prevent
Transaction T1:
or mitigate the lost update problem and maintain
1. Reads the current balance of Account ID data integrity.
1: $500.
Example :-
2. Adds $100 to the balance: $500 + $100 =
$600.

Transaction T2:

1. Reads the current balance of Account ID

1: $500.
2. Adds $200 to the balance: $500 + $200 =
$700.

Now, let's assume the interleaved execution of

these transactions:

step Transaction Transaction T2

T1(Balance = (Balance = Example :-
$500) $500)
1 Read Balance
2 Read Balance
3 Add $100
4 Add $200
5 Write balance
($600)
6 Write Balance
($700)
Dirty Reads (The temporary update , result, the aggregate function may calculate
inconsistent read ):- A dirty read occurs when values based on a mix of old and updated
one transaction reads data that has been modified records, leading to incorrect or inconsistent
by another transaction but has not been summary results.
committed yet. This can lead to reading and To illustrate this problem, let's consider an
using incorrect or incomplete data, as the example:
changes made by the other transaction may be
rolled back or aborted later. Suppose we have a table named Sales, which
tracks the sales transactions for different products:
In simpler terms, a dirty read happens when one
transaction reads data that is still in an Table: Sales
intermediate state due to another ongoing
Product ID Product Name Quantity
transaction. It's like reading a draft of a
1 Product A 10
document that may change later, leading to
potential confusion or incorrect information. 2 Product B 15

Example :- 3 Product C 20

Now, let's imagine two transactions, T1 and T2,

operating concurrently:

Transaction T1:

1. Reads the current total quantity from the

Sales table: 10 + 15 + 20 = 45.
2. Performs some other operations.

Transaction T2:

1. Updates the quantity of Product B:

Quantity = 30.
Example :-
Now, let's assume the interleaved execution of
these transactions:

step T1 T2
1 Read total quantity

2 Update quantity
of product B

3 Continue Execution

In this scenario, the problem arises because

Transaction T1 calculates the total quantity based
on the initial values of the records before
Transaction T2 updates the quantity of Product B.
The incorrect summary problem (unrepeatable
The result obtained by Transaction T1 is incorrect
read) The problem of incorrect summary occurs
since it does not reflect the updated quantity of
when one transaction is calculating an aggregate
Product B.
summary function, such as a total or average, on
a set of records, while other concurrent
transactions are updating some of these records
before the first transaction is committed. As a
Example :-

This problem occurs due to the lack of proper

synchronization and isolation between the
concurrent transactions. The summary function in
Transaction T1 does not have a consistent view
of the data, as it mixes old and updated values,
leading to incorrect summary results.

To ensure the correct summary, it is essential to

employ proper concurrency control mechanisms,
such as transaction isolation levels and
appropriate locking strategies. These mechanisms
guarantee that the summary function operates on
a consistent and up-to-date set of records,
preventing the problem of incorrect summary and
ensuring accurate results.
 CHAPTER TWO though multiple transactions are running
concurrently.
CONCURRENCY CONTROL
4. Atomicity: Atomicity ensures that each
Concurrency control is a fundamental aspect of transaction is treated as an indivisible
database management systems (DBMS) that unit of work. Concurrency control
ensures the proper execution of multiple guarantees that either all the operations
transactions concurrently while maintaining data within a transaction are executed
consistency and integrity. It involves coordinating successfully, or none of them are applied,
the access and modification of shared data by preventing partial updates or incomplete
multiple users or processes to prevent conflicts transactions.
and inconsistencies. Concurrency control techniques utilize various
In simpler terms, concurrency control is like mechanisms such as locking, timestamps, and
traffic management for a busy road. Imagine a transaction isolation levels to manage concurrent
road where several cars are trying to move access and modifications. These mechanisms
forward simultaneously. To prevent accidents and control access to shared data, resolve conflicts,
ensure smooth traffic flow, traffic lights, lanes, enforce isolation, and ensure data integrity, thus
and rules are implemented. Similarly, in a DBMS, enabling multiple transactions to execute safely
concurrency control techniques are employed to and reliably.
manage simultaneous access and modifications of CONCURRENCY CONTROL TECHNIQUES
data to avoid conflicts and maintain data
integrity. Different concurrency control techniques, such as
locking, timestamp, and optimistic concurrency
Concurrency control mechanisms in a DBMS aim
control, using simpler terms:
to address the following challenges:
1. Locking: Locking is a concurrency control
1. Data Conflicts: Conflicts can occur when
technique that involves acquiring locks on
multiple transactions try to access or
data items to control access by multiple
modify the same data concurrently.
transactions. A lock acts like a permission
Concurrency control ensures that
slip, allowing only one transaction to read
conflicting operations are appropriately
or write a data item at a time.
scheduled and executed to maintain
consistency. In simpler terms, locking is like a "keep out" sign
on a door. Imagine a room that only one person
2. Data Consistency: Maintaining data
can enter at a time. When someone wants to
consistency is crucial to ensure that the
enter, they need to obtain a key (lock) to open
database remains in a valid state even
the door. While one person has the key (lock),
when multiple transactions are executed
others have to wait until the key is released. This
concurrently. Concurrency control prevents
ensures that only one person accesses the room at
situations where the data becomes
any given time, preventing conflicts.
inconsistent or violates integrity
constraints. 2. Timestamp: Timestamp-based concurrency
control uses timestamps to order and
3. Isolation: Isolation refers to the degree of
control the execution of transactions. Each
separation between transactions.
transaction is assigned a unique
Concurrency control mechanisms ensure
timestamp that represents its start time.
that each transaction appears to execute
The timestamps help determine the order
independently, as if it were the only
of execution and resolve conflicts.
transaction accessing the data, even
In simpler terms, timestamps are like a time- When a user wants to read or modify data in the
stamp machine that marks when each transaction database, the locking method ensures that they
starts. It ensures that transactions are executed in obtain a lock on the data item they need. This
the right order, like people waiting in line based lock prevents other users from accessing or
on the time they arrived. This helps avoid modifying the same data until the first user
conflicts and ensures that transactions are releases the lock.
processed in a fair and orderly manner.
Imagine you and your friend want to update a
3. Optimistic Concurrency Control: Optimistic shared document online. The locking method
concurrency control is a technique that would be like taking turns. When you start
assumes there will be no conflicts among making changes, you "lock" the document,
concurrent transactions. It allows preventing your friend from editing it at the
transactions to execute without acquiring same time. Once you finish and release the lock,
locks initially but performs checks later to your friend can then "lock" the document and
ensure that conflicts have not occurred. If make their changes.
conflicts are detected, the affected
By using locks, the locking method ensures that
transactions are rolled back and retried.
each user gets exclusive access to the data they
In simpler terms, optimistic concurrency control need, one at a time, to avoid conflicts and
is like playing a game with friends where maintain data consistency.
everyone is expected to follow the rules and not
In simpler terms, the concepts of locking and
interfere with each other. The game proceeds
unlocking in the context of transactions and data
without strict restrictions or supervision.
items can be explained as follows:
However, if any conflicts arise, such as two
people trying to take the same turn, the game is 1. Locking :- When a transaction wants to
reset, and they try again to ensure fairness. access or modify a particular data item, it
needs to "lock" that item. Locking means
These concurrency control techniques aim to
that the transaction claims exclusive
prevent conflicts and ensure data consistency in
ownership or control over the data item.
multi-user systems. Locking restricts concurrent
This ensures that no other transaction can
access to data items, timestamp ordering ensures
access or modify the same data item
transaction sequencing, and optimistic
simultaneously.
concurrency control assumes no conflicts initially
but performs checks later to maintain data Imagine you and your friend have a toy car, and
integrity. you both want to play with it. To avoid conflicts,
you decide to use a locking mechanism. When
Each technique has its advantages and
you want to play with the car, you "lock" it by
considerations, and their selection depends on the
holding onto it tightly. This prevents your friend
specific requirements and characteristics of the
from taking the car and playing with it until you
application or database system.
release the lock.

2. Unlocking :- Once a transaction finishes

LOCKING IN DETAIL
using a data item, it needs to "unlock"
the item. Unlocking means that the
In simpler terms, the locking method is a
transaction releases its ownership or
technique used to manage multiple users or
control over the data item, allowing other
processes accessing a database at the same time.
transactions to access or modify it if
It helps maintain data integrity and prevent
needed.
conflicts that may arise when multiple users try
to modify the same data simultaneously.
In the toy car scenario, when you're done playing Using the book analogy again, imagine you want
with the car, you "unlock" it by letting go. Now, to write some notes in the book. In the exclusive
your friend can take the car and play with it lock model, you would acquire an exclusive lock
because you've released the lock. on the book, giving you the exclusive right to
make changes. This means no one else can read
The purpose of locking and unlocking in
or modify the book until you release the lock.
transactions is to ensure that only one transaction
can access or modify a particular data item at a The exclusive lock model ensures that only one
time. This helps prevent conflicts and maintain transaction can modify a data item at a time,
the integrity and consistency of the data. preventing conflicts and maintaining data
integrity during write operations.
TWO LOCK MODES
Both lock models have their uses depending on
In simpler terms, the shared and exclusive lock the needs of the transactions. The shared lock
models are two types of locking mechanisms used model allows concurrent reading but prohibits
in databases to control access to data items. Let's writing, while the exclusive lock model provides
dive into each model in more detail: exclusive access for both reading and writing,
ensuring data consistency during modifications.
1. Shared Lock Model: In the shared lock
model, multiple transactions are allowed
LOCK MANAGER
to simultaneously acquire shared locks on
a data item. When a transaction holds a In simpler terms, a lock manager is a component
shared lock, it can only read the data in a database system that is responsible for
item but cannot modify it. Other managing locks on data items. It keeps track of
transactions can also acquire shared locks which transactions have locked which data items,
on the same data item, allowing them to the type of lock being held, and maintains a
read the data concurrently. reference to the next data item locked.
Imagine you and your friends are reading a book To help in managing this information, the lock
together. In the shared lock model, each of you manager uses a data structure called a lock table.
can hold a shared lock on the book. This means The lock table is like a table or a list that holds
all of you can read the book at the same time, information about the locks placed on different
but none of you can make changes to the text. data items.
The shared lock model is useful when multiple Let's break down the key components of the lock
transactions need to access the same data for manager and the lock table:
read operations, ensuring concurrent reading
without conflicts. 1. Transaction Identification: Each
transaction is assigned a unique identifier.
2. Exclusive Lock Model: In the exclusive The lock manager uses these identifiers to
lock model, only one transaction can keep track of which transaction has
acquire an exclusive lock on a data item locked a specific data item. It uses this
at a time. When a transaction holds an information to grant or deny lock requests
exclusive lock, it has exclusive access to from other transactions.
the data item, allowing both read and
write operations. Other transactions are 2. Data Item Identification: Every data item
blocked from acquiring any type of lock in the database is also assigned a unique
on the same data item until the exclusive identifier. The lock manager uses these
lock is released. identifiers to associate locks with specific
data items. It helps identify which data
 items are currently locked and by which Before you can play with the toy, you need to
transactions. "lock" it by holding onto it tightly. This ensures
that your friend cannot take the toy and play
3. Lock Model: The lock model refers to the
with it at the same time.
type of lock being held on a data item.
For example, it could be a shared lock or 2. Not Locking an Already Locked Item :- A
an exclusive lock (as explained earlier). transaction must not attempt to lock a
The lock manager keeps track of the lock data item that is already locked by
model for each locked data item to ensure another transaction. If a data item is
proper access control. already locked, it means that another
transaction has exclusive access to it.
4. Pointer to the Next Locked Data Item:
Trying to lock it again would lead to a
The lock manager maintains a reference
conflict and potential data inconsistency.
or a pointer to the next data item that
has been locked by the same transaction. Continuing with the toy box analogy, if your
This helps in efficiently managing locks friend already has the toy and has locked it by
and ensuring proper order when releasing holding onto it, you cannot attempt to lock it as
or acquiring locks. well. It's important to wait for your friend to
release the lock before you can access the toy.

3. Not Unlocking a Free Data Item :- A

transaction must not try to unlock a data
item that is not currently locked by itself.
Unlocking a free data item means
releasing the lock on a data item that the
By using the lock table, the lock manager can transaction does not currently hold. This
efficiently manage and control access to data could lead to data inconsistencies or
items. It keeps track of which transactions have conflicts with other transactions.
locked which data items, the lock models being In the toy box scenario, if you have already
used, and maintains a reference to the next released the lock on the toy by letting go, it
locked data item. This helps prevent conflicts, would not make sense for your friend to try to
ensure data integrity, and maintain concurrency unlock it because the toy is already freely
control in the database system. available. It's important to only unlock data items
A well-formed transaction follows three important that you have previously locked.
rules : Following these rules ensures that transactions
1. Locking before Reading or Writing :- A operate in a well-formed manner, avoiding
transaction must lock a data item before conflicts, maintaining data integrity, and
it reads or writes to it. This means that preventing inconsistencies in the database system.
before a transaction can access or modify
LOCKING BASIC RULES
a data item, it needs to obtain a lock on
that item. Locking ensures that the In simpler terms, the basic rules of locking in a
transaction has exclusive access to the transactional system can be explained as follows:
data item and prevents conflicts with
other transactions that may also want to 1. Locking an Item: When a transaction
access or modify the same item. wants to access a data item, it first
requests access by issuing a "lock item(x)"
Imagine you and your friend have a toy box, and operation. If the data item is already
you both want to play with a specific toy inside. locked by another transaction, the
To avoid conflicts, you decide to use locks.
 requesting transaction is forced to wait another transaction can also read the
until the item becomes available. If the same item without causing any conflicts.
data item is currently unlocked (lock(x) =
To illustrate, imagine you and your friends are
0), the transaction sets the lock to 1
reading a book together. Each of you can hold a
(lock(x) = 1) and is allowed to access the
shared lock on the book, allowing all of you to
item.
read different parts of the book simultaneously.
Imagine you and your friend want to play with
By following these locking rules, transactions can
the same toy. To ensure fairness, you have a lock
access and modify data items in a controlled and
on the toy. When your friend wants to play with
coordinated manner, preventing conflicts and
it, they ask for permission by saying "lock
maintaining data integrity in the database system.
item(x)". If the toy is already locked, your friend
has to wait until you finish playing. But if the read_lock(x) Pseudo code
toy is unlocked, your friend can set the lock to 1
and start playing with it.

2. Unlocking an Item: After a transaction

finishes its operations on a data item, it
issues an "unlock_item(x)" operation. This
operation sets the lock back to 0 (lock(x)
= 0), indicating that the data item is now
available for other transactions to access.

Continuing with the toy example, when you

finish playing with the toy, you issue an
"unlock_item(x)" operation by letting go of the
toy. This action sets the lock to 0, indicating that
the toy is now free for your friend or other
transactions to play with.
write_lock(x) Pseudo code
3. Shared Lock and Exclusive Lock:
Transactions can have different types of
locks on data items. A shared lock allows
a transaction to read the data item but
not modify it. An exclusive lock, on the
other hand, gives a transaction both the
ability to read and modify the data item.

For instance, if you have a shared lock on the

toy, it means you can only look at the toy and
play with it, but you cannot make any changes
or modifications. However, if you have an
exclusive lock, you have the authority to read,
modify, and even replace the toy with a different
one. Lock Conversion
4. No Conflict in Reads: Multiple transactions
Let's break down lock conversion, lock upgrade,
can hold shared locks on the same item
and lock downgrade in simpler terms:
simultaneously because reads do not
conflict. This means that while one 1. Lock Conversion: Lock conversion refers to
transaction is reading the data item, changing the type of lock held on a data
 item by a transaction. It occurs when a transactions, your exclusive lock will be
transaction wants to upgrade or downgraded to a shared lock, allowing both you
downgrade its lock on a data item from and your friend to play with the car
one type to another. simultaneously.

Imagine you and your friend are playing with a In summary, lock conversion is the process of
toy car. You have a shared lock, which means changing the type of lock held on a data item.
you can look at the car and play with it, but you Lock upgrade involves changing a shared lock to
can't make changes. However, you want to an exclusive lock, granting exclusive access. Lock
upgrade your lock to an exclusive lock, which downgrade, on the other hand, involves changing
would allow you to not only play with the car an exclusive lock to a shared lock, allowing
but also modify it. shared access to the data item. These mechanisms
allow transactions to adapt their lock type to
To convert the lock, you would request a lock
accommodate their specific needs while ensuring
conversion operation. The system will check if
data integrity and concurrency control in the
the requested conversion is allowed and if there
database system.
are any conflicting locks held by other
transactions. If the conversion is allowed, your SERIALIZABILITY
shared lock will be upgraded to an exclusive
lock, granting you the ability to modify the toy Serializability in the context of databases refers to
car. the property of executing multiple transactions in
2. Lock Upgrade: Lock upgrade refers to a way that produces the same result as if the
changing a shared lock to an exclusive transactions were executed sequentially, one after
lock on a data item. It allows a another. In other words, it ensures that the
transaction that initially held a shared concurrent execution of transactions does not
lock to acquire exclusive access to the result in any inconsistency or incorrectness in the
data item. final outcome.

Continuing with the toy car example, suppose To understand serializability, let's consider an
you initially had a shared lock on the car, but example :-
now you want to make modifications to it. To do Suppose there are two transactions :- T1 and T2,
so, you would request a lock upgrade. If there operating on a database. T1 transfers money from
are no conflicting locks held by other account A to account B, and T2 updates the
transactions, your shared lock will be upgraded account balance of account A.
to an exclusive lock, giving you the exclusive
right to modify the toy car. If these transactions were executed sequentially,
the outcome would be predictable and consistent.
3. Lock Downgrade: Lock downgrade, on the However, in a concurrent execution scenario
other hand, refers to changing an where T1 and T2 run simultaneously, conflicts
exclusive lock to a shared lock on a data can arise. For example, T1 might read an
item. It allows a transaction that initially inconsistent account balance if T2 has not yet
held an exclusive lock to share access to updated it.
the data item with other transactions.
Serializability guarantees that the concurrent
Let's say you have an exclusive lock on the toy execution of transactions, even with potential
car, which means you have exclusive control over conflicts, will produce a result equivalent to some
it. However, you realize that your friend also sequential execution of those transactions. It
wants to play with the car. In this case, you can ensures that the final state of the database
request a lock downgrade to a shared lock. If remains consistent and valid.
there are no conflicting locks held by other
To achieve serializability, concurrency control For instance, let's consider T1 updating the price
mechanisms like Two-Phase Locking (2PL) are of a product while T2 is reading the product's
employed. 2PL ensures that transactions acquire price. If T2 reads the old price before T1's
and release locks on data items in a consistent update, it may perform calculations or decisions
manner, preventing conflicts and maintaining a based on incorrect information.
proper order of operations.
These conflicts arise because read operations do
By enforcing serializability, database systems not modify the data item and can be allowed
ensure that the execution of concurrent concurrently. However, when a write operation
transactions maintains data integrity, consistency, occurs, it should have exclusive access to prevent
and correctness. It allows multiple transactions to inconsistencies.
safely operate on a shared database, ensuring that
To address the serializability problem in read and
the final result is equivalent to a sequential
write locks, concurrency control mechanisms like
execution without any inconsistencies or conflicts.
Two-Phase Locking (2PL) are employed. 2PL
ensures that transactions acquire appropriate locks
THE SERIALIZABILITY PROBLEM in a consistent order, preventing read-write and
write-read conflicts. This helps maintain the
The serializability problem in read and write serializability of transactions and ensures data
locks arises when there is a potential for conflicts integrity.
between transactions that require both read and By properly managing read and write locks and
write access to the same data item. This can lead handling conflicts, the serializability problem can
to inconsistencies and incorrect outcomes if not be mitigated, enabling correct and consistent
managed properly. execution of concurrent transactions.
To understand this problem, let's consider two
transactions: T1 and T2, where T1 performs a TWO PHASE LOCKING TECHNIQUE
read operation (read_lock) on a data item and T2
performs a write operation (write_lock) on the Two-Phase Locking (2PL) is a concurrency control
same data item. technique used in database systems to ensure
serializability and prevent conflicts between
1. Read-Write Conflict :- The read-write
transactions. It consists of two distinct phases: the
conflict occurs when T1 reads a data item
growing phase and the shrinking phase.
that T2 is currently writing to or has
modified. If T1 reads the data item before In simpler terms, 2PL is like a protocol or set of
T2's modifications are applied, it may rules that transactions follow when accessing and
obtain an inconsistent or incorrect value. modifying data. It ensures that transactions
acquire and release locks in a specific order to
For example, let's say T1 wants to read the
prevent conflicts and maintain the consistency of
balance of an account while T2 is simultaneously
the database.
updating that account's balance. If T1 reads the
account balance before T2's update is committed, Here's a more detailed explanation of the two
it would obtain an outdated or incorrect balance. phases of 2PL:

2. Write-Read Conflict :- The write-read 1. Growing Phase: During the growing

conflict occurs when T1 writes to a data phase, transactions acquire locks on data
item that T2 is currently reading. This items they need before they start
conflict can lead to T1 modifying the data performing any modifications. Once a
item based on an outdated value read by transaction acquires a lock on a data
T2, resulting in inconsistencies. item, it holds onto that lock until it no
longer needs the item.
Imagine you and your friend are playing with
different toys, and you want to ensure fairness
and avoid conflicts. Before you start playing with
your toy, you acquire a lock on it, indicating
that you are going to use it. Your friend does the
same with their toy. This way, both of you have
acquired locks during the growing phase,
ensuring exclusive access to your respective toys.
By adhering to the protocol of Two-Phase
The purpose of the growing phase is to ensure Locking, transactions can ensure that they acquire
that transactions acquire all the necessary locks at locks in a controlled manner, preventing conflicts
the beginning and prevent conflicts later on. and maintaining the integrity and consistency of
the database.
2. Shrinking Phase: Once a transaction has
finished using a data item, it releases the
lock during the shrinking phase, allowing
other transactions to access and modify
the item.

Continuing with the toy example, when you

finish playing with your toy, you release the
lock, indicating that you no longer need exclusive
access to it. This allows your friend or any other
transaction to acquire the lock and play with the
toy.
Problems With Locking
The shrinking phase ensures that locks are
released when they are no longer needed, Deadlock and starvation are two potential issues
allowing other transactions to access the data that can arise when using locking as a
item and maintain concurrency. concurrency control mechanism in a database
system. Let's define them in simpler terms :-
Why do we need Two-Phase Locking?
1. Deadlock: Deadlock occurs when two or
We need Two-Phase Locking to ensure data
more transactions are unable to proceed
consistency and prevent conflicts between
because each of them is waiting for a
transactions. By following the rules of 2PL,
resource that is held by another
transactions acquire locks before accessing data,
transaction in the waiting chain. As a
ensuring exclusive access to the items they need.
result, the transactions are stuck in a
This prevents conflicts that can arise when
deadlock state, unable to make progress.
multiple transactions try to access or modify the
same data simultaneously.

Imagine if you and your friend both tried to play

with the same toy at the same time without
using locks. It would lead to conflicts, confusion,
and potential damage to the toy. Two-Phase
Locking helps in avoiding such conflicts by
enforcing a systematic approach to acquiring and Imagine a scenario where two friends, Alice and
releasing locks. Bob, each have a toy car and want to borrow the
other's toy for a brief moment. Alice holds her
toy car and waits for Bob to lend his car, while
Bob holds his toy car and waits for Alice to lend • Deadlock prevention
her car. Since both are waiting for a resource • Deadlock Detection and Avoidance
that the other is holding, they are trapped in a • Lock timeouts
deadlock, unable to proceed.
DEADLOCK PREVENTION PROTOCOL
In a database system, deadlock can occur when
transactions hold locks on certain data items and Let's define the deadlock prevention protocol,
try to acquire additional locks, but those locks including the conservative two-phase locking and
are already held by other transactions in a transaction time stamp, in simpler terms:
circular manner. This can lead to a complete
1. Conservative Two-Phase Locking: In the
standstill in the system, halting progress and
conservative two-phase locking protocol, a
requiring intervention to resolve the deadlock.
transaction locks all the data items it
2. Starvation: Starvation refers to a situation needs before it begins executing its
where a transaction is unable to execute operations. This protocol aims to prevent
or complete its operations because it deadlocks by ensuring that a transaction
keeps getting bypassed or delayed by never waits for a data item.
other transactions. In other words, the
To understand this protocol, let's use an example:
transaction is "starved" of the necessary
Imagine you and your friend want to borrow toys
resources or opportunities to proceed.
from each other. In the conservative two-phase
Think of a scenario where there is a line of locking approach, before you start playing with a
people waiting to use a single computer at a toy, you make sure to hold all the other toys you
public library. If a particular person keeps getting need. This way, you won't have to wait for a toy
skipped or delayed by others who are constantly to become available, avoiding potential deadlocks.
joining the line, that person is experiencing
However, the limitation of this protocol is that it
starvation. They are not able to access the
restricts concurrency. Since transactions lock all
computer, even though they have been waiting
the required data items upfront, it may result in
for a long time.
unnecessary delays if other transactions need
In a database system, starvation can occur when access to some of the locked data items.
a transaction repeatedly gets delayed or pushed
2. Transaction Time Stamp: In the
aside by other transactions that are constantly
transaction time stamp approach, each
acquiring locks on the desired data items. This
transaction is assigned a priority or time
can happen if there is no proper scheduling or
stamp when it starts. Lower priority
prioritization mechanism in place.
transactions are not allowed to wait for
Both deadlock and starvation are undesirable higher priority transactions, which helps
situations that can hinder the performance and prevent deadlocks.
efficiency of a database system. Deadlock leads to
To understand this approach, let's imagine you
a complete standstill, while starvation results in
and your friend want to use a computer at a
certain transactions being delayed or unable to
library. The library assigns time stamps based on
execute. Managing these issues requires careful
who arrived first. If you have a lower time
design and implementation of concurrency control
stamp, it means you have higher priority to use
mechanisms, such as deadlock detection and
the computer. Your friend, with a higher time
resolution algorithms and fair scheduling policies,
stamp, cannot make you wait for an extended
to ensure smooth and efficient operation of the
period, ensuring fairness and preventing
database system.
deadlocks.
SOLUTION TO A DEADLOCK
By assigning priorities to transactions based on would allow your friend to "die" (abort) and
their time stamps, the system ensures that lower restart their task later, while you continue using
priority transactions do not wait indefinitely for the computer.
higher priority transactions, thereby avoiding
Wait-die ensures that younger transactions wait
potential deadlocks.
for older transactions to release resources,
These deadlock prevention protocols aim to avoid preventing potential deadlocks while maintaining
deadlocks in a database system by ensuring that fairness. Younger transactions may experience
transactions do not get stuck waiting for some delays but are eventually allowed to
resources indefinitely. While conservative two- execute.
phase locking prevents deadlocks by upfront
2. Wound-Wait: Wound-wait is another
locking, it restricts concurrency. On the other
deadlock prevention strategy that follows
hand, the transaction time stamp approach
a more aggressive approach compared to
assigns priorities to transactions, ensuring fairness
wait-die. In this strategy, when a younger
and preventing lower priority transactions from
transaction requests a resource held by an
waiting indefinitely for higher priority ones.
older transaction, the older transaction is
WAIT - DIE | WOUND -WAIT "wounded" (aborted), allowing the
younger transaction to proceed. However,
Wait-die and wound-wait are two deadlock if an older transaction requests a resource
prevention strategies used in transactional systems held by a younger transaction, the
to manage potential deadlocks. They help ensure younger transaction waits until the older
the system avoids deadlocks by allowing transaction releases the resource.
transactions to either wait or be preempted based
To understand this strategy, let's go back to the
on their age or priority.
queue for using a computer. If you arrive later
Let's define wait-die and wound-wait in simpler (younger transaction) and find that your friend is
terms: already using the computer (older transaction),
you would wound (abort) your friend's task,
1. Wait-Die: Wait-die is a deadlock
allowing you to access the computer immediately.
prevention strategy that follows a
However, if you arrived earlier (older transaction)
conservative approach. In this strategy,
and your friend wants to use the computer
when a younger transaction requests a
(younger transaction), you would make your
resource held by an older transaction, the
friend wait until you finish using the computer.
younger transaction waits until the older
transaction releases the resource. Wound-wait takes a more aggressive approach by
However, if an older transaction requests prioritizing younger transactions over older ones.
a resource held by a younger transaction, It allows younger transactions to proceed by
the older transaction is allowed to "die" preempting older transactions, reducing potential
(abort) and be restarted later. delays for the younger transactions.

To understand this strategy, imagine you and Both wait-die and wound-wait strategies aim to
your friend are waiting in a queue to use a prevent deadlocks by managing resource requests
computer. If you arrive later (younger and ensuring fairness. These strategies determine
transaction) and find that your friend is already whether a transaction should wait or be aborted
using the computer (older transaction), you would based on its age or priority relative to other
wait for your friend to finish before you can transactions. By employing these strategies,
access the computer. However, if you arrived transactional systems can avoid deadlocks and
earlier (older transaction) and your friend wants maintain the overall integrity and concurrency of
to use the computer (younger transaction), you the system.
DEADLOCK DETECTION AND RESOLUTION chances of deadlocks and allowing the system to
continue executing transactions smoothly.

While lock timeouts provide a preventive measure

against deadlocks, it's important to set the
timeout duration carefully to avoid unnecessarily
aborting transactions that could eventually
acquire the required locks. Balancing the timeout
duration ensures efficient concurrency while
reducing the likelihood of deadlocks in the
system.

TIMESTAMP BASED CONCURRENCY CONTROL

Let's delve into timestamp-based concurrency

LOCK TIMEOUTS
control in simpler terms:

lock timeouts can be considered as a mechanism In a database system, timestamp-based

for preventing deadlocks in a database system. It concurrency control uses timestamps to determine
is a concurrency control technique that helps the order of executing transactions and resolve
avoid potential deadlocks by setting a maximum conflicts. Here's a more detailed explanation:
duration for a transaction to wait for a lock on a
1. Timestamp Assignment: Each transaction
data item.
is assigned a unique timestamp that
In simpler terms, lock timeouts work by imposing represents its start time. This timestamp is
a time limit on how long a transaction can wait like a "time-stamp machine" that marks
to acquire a lock. If the transaction exceeds the when the transaction began its execution.
specified time limit and is unable to acquire the It helps establish a chronological order for
lock, it is automatically aborted or rolled back, the transactions.
releasing any previously acquired locks.
Imagine you and your friend enter a store, and
To understand this concept, imagine you and the store manager gives you both a unique
your friend are waiting to borrow a book from a timestamp when you arrive. Your timestamp
library. The library enforces a lock timeout indicates the exact time you entered the store,
policy, meaning if you wait for too long to while your friend receives a timestamp
borrow the book, the library staff will cancel representing their arrival time.
your request and allow the book to be borrowed
2. Transaction Execution Order: The
by someone else.
timestamps are used to determine the
Similarly, in a database system, when a order in which transactions are executed.
transaction requests a lock on a data item, it The database system processes transactions
waits for a certain duration. If the lock is not based on their timestamps, ensuring a
granted within that timeframe, the transaction is systematic and ordered execution.
terminated and treated as if it had encountered a
Continuing with the store analogy, after receiving
deadlock. This helps prevent transactions from
the timestamps, you and your friend line up to
waiting indefinitely and potentially causing a
make your purchases. The store serves customers
deadlock situation.
based on their timestamp order, starting with the
By using lock timeouts, the database system customer with the earliest timestamp. This
ensures that transactions do not remain stuck ensures fairness and an orderly execution
waiting for locks indefinitely, minimizing the sequence.
 3. Conflict Resolution: Timestamps also play Imagine you and your friends are playing a game
a crucial role in resolving conflicts that together, but there is no strict supervision or
may arise when multiple transactions try restrictions on how you can play. Everyone is
to access or modify the same data expected to follow the rules and not interfere
concurrently. Conflicts occur when there with each other. You proceed with the game,
is contention for shared resources or assuming there won't be any conflicts.
conflicting operations.
However, if a conflict does arise, such as two
If a conflict occurs, the transaction with the people trying to take the same turn or conflicting
earlier timestamp is given priority and allowed to moves, the game is reset, and everyone tries
proceed, while the transaction with the later again to ensure fairness. In this case, the
timestamp is either delayed or rolled back, conflicting moves are rolled back, and the game
depending on the conflict resolution policy. restarts from a consistent state.

To illustrate this, imagine you and your friend In the context of a database system, optimistic
are shopping in the store, and there is only one concurrency control works similarly. Transactions
item left of a popular product. Both of you have are allowed to execute without acquiring locks
timestamps indicating the order of arrival. The initially, assuming there won't be any conflicts. It
store gives priority to the customer with the relies on the idea that conflicts between
earlier timestamp, allowing them to purchase the transactions are relatively rare. After the
item, while the customer with the later transactions complete their operations, the system
timestamp must wait or choose an alternative performs checks to ensure that no conflicts have
product. occurred. If conflicts are detected during the
checks, the affected transactions are rolled back
By using timestamps, the database system ensures
and retried to maintain data integrity.
a fair and ordered execution of transactions. It
helps avoid conflicts, resolves contention for Optimistic concurrency control offers the
resources, and maintains data consistency and advantage of allowing more concurrent access to
integrity. Transactions are processed in a data items, as transactions are not hindered by
systematic manner based on their timestamps, locks during execution. It aims to strike a balance
preventing inconsistencies and ensuring that the between concurrency and data consistency by
final state of the database reflects a correct assuming that conflicts are infrequent. However,
sequence of operations. it requires careful checking and potential retries
to handle conflicts if they do occur.

VALIDATION (OPTIMISTIC) CONCURRENCY Each concurrency control technique, including

CONTROL SCHEMES locking, timestamp ordering, and optimistic
concurrency control, serves the purpose of
Optimistic concurrency control is a technique
preventing conflicts and maintaining data
used in database systems that assumes there will
consistency in multi-user systems. The choice of
be no conflicts among concurrent transactions. It
technique depends on the specific requirements
allows transactions to proceed without acquiring
and characteristics of the application or database
locks initially, but it performs checks later to
system.
ensure that conflicts have not occurred. If
conflicts are detected during the checks, the
affected transactions are rolled back and retried.

To understand this concept better, let's use an

analogy of playing a game with friends:
 CHAPTER THREE • Evaluation:

◦ Plan Execution: The selected execution

QUERY PROCESSING AND OPTIMIZATION
plan from the optimization phase is
used to retrieve the data from the
Query processing refers to the set of
database. The system executes the
activities performed by a database
query by accessing the required
management system (DBMS) to process and
tables, applying any necessary joins,
execute a user's query against a database. It
involves transforming a high-level query, filtering rows based on conditions,
written in a database query language (e.g., and performing any requested
SQL), into a series of operations that retrieve aggregations or sorting operations.
the desired data from the database. ◦ Result Generation: As the query is
executed, the system generates the
• Parsing and Translation: result set based on the specified
columns and conditions. The retrieved
◦ Parsing: The query is analyzed to
data is formatted into a format
ensure it follows the syntax and
suitable for the user or application,
grammar rules of the database query
such as a table or a result set object.
language (e.g., SQL). The query is
◦ Result Delivery: The final result set is
broken down into its constituent
delivered to the user or application
parts, such as keywords, table names,
that initiated the query. This may
columns, and conditions.
involve transmitting the result over a
◦ Translation: The parsed query is then
network connection or storing it in a
translated into an internal
temporary location for further
representation that the database
processing or presentation.
system can understand and execute.
This representation typically involves Overall, query processing involves parsing and
generating a query tree or an translating the user's query, optimizing the query
intermediate representation of the execution plan to minimize cost, and finally
query structure. executing the query to fetch the requested data
from the database. It is a critical component of
• Optimization: database systems that enables efficient retrieval of
information based on user queries.
◦ Optimization: The database system
analyzes the query and considers
different execution strategies to
determine the most efficient way to
retrieve the data. This involves
exploring various possibilities, such as
different access paths, join algorithms,
and index usage, to minimize the
overall cost of executing the query.
◦ Cost Estimation: The system estimates
the cost associated with each potential
execution plan, considering factors
like disk I/O, CPU utilization, and
memory usage. The goal is to select
the execution plan with the lowest
estimated cost.
PARSING AND TRANSLATION optimization and evaluation, which lead to the
retrieval of the desired data from the database.
When we talk about parsing and translation in
When a user executes a query, the database
the context of query processing, it refers to the
system goes through a process of parsing and
initial stages where the user's query is
translation to understand and process the query
transformed from a high-level language like SQL
effectively. Here's a simpler breakdown:
into a format that the database system can
understand and execute. 1. Parsing: The parser checks the syntax of
the query to ensure it follows the rules
Here's a simplified explanation of the concepts
and structure of the query language. It
involved:
verifies the names of relations (tables) in
1. Parsing :- Parsing is the process of the database, the tuples (rows), and the
analyzing the query to ensure it follows required attribute values (columns). It
the syntax and rules of the query creates a tree-like structure called a parse
language (e.g., SQL). It breaks down the tree, representing the query's structure.
query into its individual components, such
2. Translation: The parse tree is then
as keywords, table names, columns, and
translated into an internal representation,
conditions. This step ensures that the
often in the form of relational algebra.
query is properly structured and can be
Relational algebra is a mathematical
understood by the database system.
language used to describe operations on
2. Translation :- Once the query is parsed, it relational databases. This translation
needs to be translated into a format that involves replacing the use of views and
the system can work with effectively. transforming the query into a set of
Although SQL is convenient for humans to relational algebra expressions.
write and understand, it may not be
For example, let's consider the query in SQL:
directly suitable for the internal
"SELECT emp_name FROM Employee WHERE
operations of the database system. So, the
salary > 10000;"
query is further translated into an internal
representation, often using relational To make the system understand the query, it
algebra. needs to be translated into relational algebra. In
this case, the translation could be represented as
Relational algebra is a mathematical language
follows:
that describes operations on relational databases.
It provides a formal framework for representing σsalary > 10000 (πsalary (Employee))
queries and performing operations like projection,
πsalary (σsalary>10000(Employee))
selection, join, and aggregation. By translating
the user's query into relational algebra
expressions, the database system can optimize This translation represents the selection operation
and execute the query more efficiently. (σ) where the salary attribute is filtered based on
the condition salary > 10000, and then the
Overall, parsing and translation involve ensuring
projection operation (π) is applied to retrieve the
the query's syntax is correct, breaking it down
emp_name attribute from the resulting set.
into its components, and translating it into an
internal representation (such as relational algebra) Once the query is translated into relational
that the database system can work with algebra, the database system can execute each
effectively. These steps lay the foundation for operation using different algorithms. These
further query processing activities, such as algorithms determine the most efficient way to
retrieve the requested data from the database.
Overall, query processing starts with parsing the 4. Operation Execution: With the query
query to check its syntax and structure. Then, the execution plan in hand, the database
query is translated into relational algebra to system starts executing the plan step by
create an internal representation. This internal step. It performs operations like table
representation allows the system to perform scans, index lookups, joins, filtering rows
operations on the database efficiently and retrieve based on conditions, aggregations, and
the desired data. sorting. Each operation is carried out
according to the instructions provided by
the plan.
QUERY EXECUTION PLAN
5. Result Generation: As the operations are
A query execution plan is a detailed set of
executed, the database system generates
instructions that a database system creates to
the result set based on the specified
execute a user's query and retrieve the requested
columns, conditions, and requested
data. It outlines the steps and operations the
aggregations. It formats the retrieved data
system needs to follow in order to efficiently
into a suitable format, such as a table or
process the query.
result set object.
Here's a breakdown in simpler terms:
In simpler terms, a query execution plan is like a
1. Understanding the Query: The query detailed recipe for the database system. It
execution plan starts with the database outlines the optimized steps and operations
system understanding the user's query, needed to retrieve the requested data from the
which is written in a database query database and produce the desired result. The
language like SQL. The system analyzes system follows this plan to efficiently execute the
the query to determine the tables query and generate the output that the user
involved, the requested columns, any expects.
specified conditions, and the desired
result.
QUERY OPTIMIZATION
2. Query Optimization: Once the system
understands the query, it optimizes the Query optimization refers to the process
query execution plan. This optimization performed by a database system to generate an
process involves considering different efficient plan for executing a user's query. The
ways to retrieve the data, evaluating goal is to minimize the cost and time required to
possible access paths, join algorithms, and evaluate the query and retrieve the desired data.
other factors to find the most efficient Here's a breakdown in simpler terms:
plan. The goal is to minimize the cost of
1. Understanding Query Cost: The cost of
executing the query in terms of time and
evaluating a query can vary depending on
resources.
factors like the complexity of the query,
3. Plan Generation: After the optimization the amount of data involved, and the
phase, the database system generates the available resources. The database system
query execution plan. This plan outlines is responsible for constructing the
the sequence of steps and operations evaluation plan, so users do not need to
needed to retrieve the data and produce worry about writing their queries in an
the result. It specifies the order of table optimized manner.
access, join operations, filtering
2. Generating Efficient Evaluation Plan: The
conditions, and any necessary
database system uses query optimization
aggregations or sorting.
techniques to generate an efficient
 evaluation plan for the query. The system return the desired result. It includes various sub-
considers different possibilities, such as tasks and the time taken for each of these tasks.
access paths, join algorithms, and index Here's a breakdown in simpler terms:
usage, to find the plan that minimizes the
1. Query Processing Time: The cost of the
overall cost of executing the query.
query involves the time taken to process
3. Cost Analysis: To optimize a query, the the query from start to finish. This
query optimizer estimates the cost of each includes tasks such as parsing and
operation involved. This estimation translating the query (making sure it
considers factors such as memory follows the correct syntax and structure),
allocations, execution costs, and other optimizing the query (finding the most
resources required by different operations. efficient way to execute it), evaluating the
By analyzing the estimated costs, the query (executing the operations and
system can choose the most efficient plan. retrieving the data), and finally returning
the result to the user.
4. Plan Selection: After analyzing the costs,
the query optimizer selects the evaluation 2. Execution Time: Once the query is
plan that minimizes the overall cost of optimized, executing it involves accessing
executing the query. The chosen plan both primary and secondary memory
outlines the sequence of operations and based on the file organization method.
optimizations that will be used to retrieve The time taken to retrieve the data can
the data. vary depending on the file organization
and the use of indexes. Different file
5. Query Execution: Once the evaluation
organization methods and the presence of
plan is selected, the database system
appropriate indexes can impact the
executes the query. It follows the chosen
efficiency of retrieving the data and affect
plan and performs operations like
the overall query execution time.
accessing tables, joining data, applying
conditions, and aggregating results. 3. Sub-tasks and Time: The cost of the query
considers the time taken by each sub-task
6. Producing Output: As the query is
involved in query processing. These sub-
executed, the system generates the output
tasks include parsing, translation,
of the query, which is the desired result.
optimization, evaluation, and result
The result is formatted and presented to
retrieval. The time spent on each task
the user in a suitable form, such as a
adds up to the overall cost of the query.
table or result set.
4. Fraction of Seconds: While the cost of a
In simpler terms, query optimization is the
query is often measured in a fraction of
process performed by the database system to
seconds, it's important to note that it
generate an efficient plan for executing a query.
involves multiple tasks and the time taken
The system analyzes the query, estimates the cost
by each of them. Even though it may
of different operations, selects the best plan, and
seem quick, the cumulative time spent on
executes the query to produce the desired output.
each task contributes to the total query
The aim is to minimize the time and resources
cost.
required for evaluating the query.
In simpler terms, the cost of a query is the time
it takes for the query to interact with the
MEASURES OF QUERY COST
database and return the result. It includes various
The cost of a query refers to the time it takes for tasks like parsing, translation, optimization,
the query to interact with the database and evaluation, and result retrieval. The execution
time depends on factors such as file organization (S * tS) + (B * tT)
and the use of indexes. Although it may be
In simpler terms, the disk I/O cost represents the
measured in a fraction of seconds, it represents
time taken to search and find records on the
the cumulative time spent on each task involved
disk. It considers the seek time for locating
in query processing.
specific data and the transfer time for returning
the fetched data. The disk I/O cost is a
significant factor in determining the overall cost
ESTIMATING QUERY COST
of accessing data from the disk during query
The cost estimation of a query evaluation plan processing.
involves calculating the net estimated cost by
determining the cost of each operation within the
plan and combining them. The cost estimation is
done based on various resources, including the
number of disk accesses, CPU execution time, and
communication costs in distributed or parallel
database systems.

When evaluating a query, the majority of the

time is spent on accessing data from memory.
The cost of access time includes factors such as
disk I/O time, CPU time, and network access
time. Among these factors, disk I/O time is the
most significant and takes the majority of the
time during query processing. Other times can be
disregarded compared to disk I/O time.

To calculate the disk I/O time, typically only two

factors are considered: seek time and transfer
time. Seek time refers to the time taken by the
processor to find a single record in the disk
memory. Transfer time is the time taken by the
disk to return the fetched result back to the
processor or user.

For example, if we need to find the student ID of

a student named 'John,' the processor will fetch
the relevant data from memory based on the
index and file organization method. The time
taken by the processor to locate John's ID on the
disk is known as seek time. The time taken by
the disk to transfer the fetched result back to the
processor or user is called transfer time and is
represented by tT.

To calculate the disk I/O cost, we consider the

number of seeks (S) required to fetch a record
and the number of blocks (B) that need to be
returned to the user. The disk I/O cost is then
calculated as:
 CHAPTER FOUR In this situation, database recovery comes
into play. It aims to restore the database to
DATABASE RECOVERY a point before the transaction started,
ensuring that the incorrect changes are
Database recovery refers to the process of undone, and the accounts are back to their
restoring a database system to a consistent previous correct values. The recovery process
and usable state after a failure or an error. It ensures that the transaction's properties, like
involves recovering lost or damaged data and the money being transferred fully or not at
ensuring the database's integrity and all (atomicity), the accounts remaining in a
reliability. valid state (consistency), and the transaction
In simpler terms, imagine you have a digital being isolated from other transactions
filing cabinet where you store important (isolation), are preserved.
information. Sometimes, accidents happen, By recovering the database, we make sure
such as power outages, hardware failures, or that any inconsistencies or errors caused by
software errors. These accidents can cause failures are corrected, and the system can
your files to become corrupted or even continue functioning properly, providing
disappear completely. accurate and reliable data.
Database recovery is like having a backup
TYPES OF FAILURES
plan for your filing cabinet. It's the process
of fixing or restoring your files if something Here are the types of failures in a database
goes wrong. It ensures that your data is system explained in simpler terms:
protected and can be retrieved in case of any
1. Hardware Failure: This type of failure
mishaps. Recovery involves identifying and
occurs when there is a problem with the
correcting errors, recovering lost data, and physical components of the computer
making sure everything is back in order so system that houses the database. It could
you can continue using your database be a malfunctioning hard drive, power
smoothly. supply failure, or even a complete system
crash. Hardware failures can result in
PURPOSE OF DATABASE RECOVERY data loss or corruption.

The purpose of database recovery is to fix 2. Software Error: Software errors refer to
any problems caused by failures or errors bugs, glitches, or programming mistakes
and bring the database back to a state where in the database management system
(DBMS) or the applications that interact
it was consistent and reliable before the issue
with the database. These errors can cause
occurred.
the database to behave unexpectedly,
Let's imagine you're using an online banking leading to data inconsistencies or system
system to transfer funds from one account to crashes.
another. But suddenly, the system crashes 3. System Crash: A system crash happens
right in the middle of the transaction. As a when the entire computer system abruptly
result, the accounts involved in the transfer stops working or becomes unresponsive. It
may have incorrect values or incomplete can be caused by hardware failures,
changes. software errors, or external factors like
power outages. A system crash can result
 in the loss or corruption of data that was In simpler terms, imagine the transaction log as a
being processed at the time of the crash. journal or diary that keeps track of all the
activities happening in a database. Whenever a
4. Natural Disasters: Natural disasters like
transaction (such as an update, insertion, or
earthquakes, floods, fires, or hurricanes
deletion of data) takes place, the log captures the
can physically damage the infrastructure
details of that transaction.
where the database system is stored. Such
disasters can lead to the destruction of The transaction log contains the following
hardware, data loss, or make the system information:
temporarily or permanently inaccessible.
1. Transaction Identification: Each
5. Human Error: Human error refers to transaction is assigned a unique identifier,
mistakes made by individuals interacting known as a transaction ID, which helps in
with the database system. It could include identifying and tracking the specific
accidental deletion of important data, transactions.
entering incorrect commands, or
2. Operation Details: The log records the
improperly configuring the system. Human
specific operations performed within a
errors can have significant consequences
transaction, such as the changes made to
and may require database recovery to
data (e.g., updated values, inserted
restore the system to a valid state.
records, or deleted entries).
6. Network Failure: Network failures occur
3. Timestamp: The log also includes
when there is a disruption in the
timestamps, indicating when each
communication between the database
operation took place. This information
server and the client systems. It can be
helps in maintaining the chronological
due to issues like network outages,
order of the transactions.
connectivity problems, or
misconfigurations. Network failures can 4. Before and After Values: For update and
cause interruptions in database operations deletion operations, the log stores the old
and lead to data inconsistencies. value (before the change) and the new
value (after the change). This allows for
These different types of failures can occur
undoing or redoing the changes during
independently or in combination, posing risks to
database recovery.
the integrity and availability of the database
system. Understanding these failures helps in The transaction log serves multiple purposes:
implementing appropriate measures for database
1. Recovery: The primary purpose of the
recovery, such as backups, redundancy, and fault-
transaction log is to aid in database
tolerant systems, to mitigate the impact of
recovery. In the event of a system failure,
failures and ensure the smooth functioning of the
the log is used to restore the database to
database.
a consistent state by redoing committed
transactions and undoing incomplete or
TRANSACTION LOG uncommitted transactions.

2. Rollback and Undo Operations: The log

Transaction log, also known as a transaction log enables the rollback or undoing of
file or simply a log, is a vital component of a transactions. By analyzing the log, it is
database management system (DBMS) that records possible to revert the database to a
all the changes made to a database. It serves as a previous state by undoing the changes
chronological record of transactions, providing a made by a specific transaction or a series
detailed history of database modifications. of transactions.
 3. Durability: The transaction log ensures the condition is met, the changes made to the
durability property of the ACID data items are then written to the disk.
(Atomicity, Consistency, Isolation,
3. Shadow Update: In shadow update, the
Durability) properties of a transaction.
modified version of a data item does not
The log allows for the recovery of
overwrite its disk copy directly. Instead, it
committed transactions even in the
is written to a separate location on the
presence of failures, ensuring that changes
disk, creating a shadow copy. This allows
are permanently saved and not lost.
both the original (disk) and modified
4. Replication and High Availability: (cache) versions of the data item to
Transaction logs are crucial in database coexist simultaneously. The system
replication and high availability scenarios. maintains a pointer or reference to the
By replicating the log to multiple database shadow copy, enabling efficient retrieval
servers, changes made in one server can of the updated data when needed.
be applied to others, ensuring data
4. In-place Update: In in-place update, the
consistency and availability.
disk version of the data item is directly
Overall, the transaction log acts as a reliable and overwritten by the cache version. When a
detailed record of database modifications, modification is made to a data item in
providing a mechanism for recovering data in the cache, the corresponding data item on
case of failures and enabling the database system the disk is replaced with the updated
to maintain integrity and consistency. value. This approach ensures that only
one version of the data item exists at a
DATA UPDATES
time, and the disk copy is updated
When it comes to data updates in a database, immediately with the latest changes.
there are different approaches that can be used to
In in-place update, the term "in-place"
manage the changes made to data items. Let's
refers to the fact that the modified
break down the four mentioned approaches in
version of a data item is directly written
simpler terms:
back to the same location on the disk
1. Immediate Update: In immediate update, where the original data item was stored.
as soon as a data item is modified in the The disk version is overwritten by the
cache (temporary memory), the cache version, effectively replacing the old
corresponding disk copy is immediately value with the updated value.
updated. It ensures that the changes are
Here's a simplified explanation of how in-place
reflected on the disk right away,
update works:
providing a consistent view of the data.
This approach ensures that the disk 1. Original Data: Initially, the data item
always contains the most up-to-date exists on the disk in its original form, and
version of the data. a copy is loaded into the cache for
processing.
2. Deferred Update: In deferred update, the
modified data items in the cache are not 2. Modification: When a modification is
immediately written to the disk. Instead, made to the data item in the cache (e.g.,
they are held in the cache until a specific changing the value of a field), the cache
condition is met. This condition can be version of the data item is updated to
when a transaction ends its execution or reflect the changes.
after a fixed number of transactions have 3. Update on Disk: In an in-place update,
completed their execution. Once the the cache version is directly written back
 to the same location on the disk where In-Place Update:
the original data item resides. This means
• In in-place update, the disk version of the
the disk copy is replaced with the
data item is overwritten by the cache
modified version.
version.
4. One Version: After the update is • When a modification is made to a data
complete, there is only one version of the item in the cache, the cache version
data item, and it exists on the disk. The replaces the original data item directly at
cache copy may still be present, but it is the same disk location where it was
synchronized with the disk copy. stored.
• In-place update eliminates the need for
In-place update is a straightforward approach
additional storage locations or versions of
because it eliminates the need for additional disk
the data item, as there is only one
space or storage locations to store multiple
version on the disk.
versions of the data item. It allows for efficient
• This approach allows for efficient
utilization of disk space and simplifies the update
utilization of disk space and simplifies the
process. However, it's important to note that in-
update process by directly overwriting the
place updates can have implications for data
original data.
recovery in the event of failures since the original
data is directly overwritten. To summarize, the main difference is that
immediate update focuses on ensuring that the
Overall, in-place update involves directly
disk copy is immediately updated when a
replacing the original data item on the disk with
modification is made in the cache, while in-place
the modified version from the cache, ensuring
update focuses on directly overwriting the
that only one version of the data item exists at a
original data item on the disk with the modified
time.
version from the cache. Both approaches aim to
what is the difference between immediate update maintain consistency between the cache and the
and in-place update ? disk, but they differ in how and when the
updates are written to the disk.
The main difference between immediate update
and in-place update lies in how the updates are These different approaches to data updates offer
handled and when they are written to the disk. flexibility and trade-offs in terms of performance,
Let's explore these two concepts in more detail: consistency, and reliability. The choice of the
update method depends on factors such as the
Immediate Update:
specific requirements of the application, the
• In immediate update, as soon as a data system's ability to handle concurrent updates, and
item is modified in the cache (temporary the need for data consistency and durability.
memory), the corresponding disk copy is
immediately updated. DATABASE RECOVERY TECHNIQUES
• The modification made in the cache is
directly propagated to the disk, ensuring Database recovery techniques are essential
that the disk always contains the most
components of a database management system
(DBMS) that ensure data integrity and
up-to-date version of the data item.
consistency in the face of failures or errors.
• Immediate update provides immediate
When a failure occurs, such as a system crash
consistency between the cache and the
or a power outage, it can result in data loss or
disk. Once the update is performed, the corruption. Database recovery techniques help
changes are durable and available for bring the database back to a consistent state,
future transactions to access. restore lost or damaged data, and preserve the
properties of transactions, such as atomicity,
consistency, isolation, and durability (ACID). In simpler terms, let's say you're writing a story,
These techniques include undo and redo and you have been saving each chapter as you
operations, write-ahead logging, shadow complete it. Unfortunately, your computer
paging, checkpoints, and deferred updates. crashes, and you lose all your progress. However,
Each technique plays a specific role in you have a backup of your work up until the last
recovering the database, either by reverting
saved chapter. The redo operation allows you to
incomplete transactions or reapplying
restore your story by replaying the actions from
committed changes from transaction logs. By
the backup and applying the changes you made
understanding and utilizing these recovery
techniques, database administrators can ensure in each chapter to get back to where you left off.
the reliability and availability of their In database recovery, the redo operation works
databases. similarly. By analyzing the transaction log, the
database management system (DBMS) identifies
1) Undo and Redo Operations: Undo and
committed transactions that were not yet applied
redo operations are fundamental recovery
to the database due to a failure. The redo
techniques.
operation re-applies the changes made by those
Undo Operation: The undo operation is like a committed transactions, using the transaction log
"do-over" button for a transaction that wasn't as a guide. This ensures that the database is
completed or committed. When a transaction brought to a consistent state by incorporating the
starts but encounters an error or is interrupted, changes that were previously committed but not
the undo operation allows us to reverse the yet applied.
changes made by that transaction and restore the When we say "reapply" in the context of
database to its previous state. database recovery, it means to perform the same
In simpler terms, imagine you're playing a game, changes or modifications again to the database.
and you make some moves, but then realize you Reapplying changes involves executing the same
made a mistake. The undo operation lets you go operations that were previously performed by a
back to a point before you made the mistake and committed transaction.
erase the incorrect moves, effectively restoring To understand it better, let's consider a simple
the game to its earlier state. example:
In database recovery, the undo operation works Suppose you have a database table called
similarly. The transaction log keeps track of all "Employees" with various columns like "Name,"
the changes made by a transaction. If the "Age," and "Salary." Let's say there was a
transaction is incomplete or uncommitted due to committed transaction that increased the salary of
a failure, the undo operation uses the transaction all employees by 10%. However, due to a failure
log to identify the changes made by that or error, these changes were not yet applied to
transaction and applies the opposite operations to the database.
undo those changes. This way, the database is
During the recovery process, the redo operation
brought back to the state it was in before the
identifies this committed transaction through the
transaction started.
transaction log. It then re-executes the specific
Redo Operation: The redo operation is like operation, which is to increase the salary of all
replaying the actions of committed transactions employees by 10%, and applies it to the
during the recovery process. It ensures that any database. By doing so, the changes made by the
changes made by committed transactions are re- committed transaction are reapplied to the
applied to the database to maintain consistency database, ensuring that the salary increase is
and durability. correctly reflected in the updated data.
In simpler terms, reapplying changes means 3. Data Modifications: After the log records
taking the recorded modifications from the are written, the system proceeds with
transaction log and executing them again on the modifying the actual data in the database.
database to bring it back to the state it was in This can involve updating, inserting, or
before the failure occurred. It ensures that any deleting data items based on the user's
committed changes that were not yet applied due actions or application requirements.
to a failure are properly incorporated,
4. Recovery Scenario: In the event of a
maintaining data consistency and integrity.
system crash or failure, the database
Reapplying changes is an important step in needs to be recovered to a consistent
database recovery as it ensures that all the state. The WAL method allows the system
committed transactions are correctly reflected in to restore the database by analyzing and
the database, preventing any inconsistencies or applying the log records.
missing updates that may have occurred due to
5. Recovery Process:
the failure.
a. Redo Phase: During the recovery
Overall, the undo operation reverses incomplete
process, the system starts with the redo
or uncommitted changes, while the redo
phase. It scans the log from the most
operation reapplies committed changes, both
recent checkpoint or stable point (where
utilizing the transaction log to guide the recovery
all modified data was flushed to disk) to
process and restore the database to a consistent
the end of the log. For each log record
state after failures or errors.
encountered, it re-applies the operation to
2) Write-Ahead Logging (WAL) Write-Ahead the corresponding data item, bringing it
Logging (WAL) is a database recovery method up to date with the most recent changes.
that ensures data consistency and recoverability
b. Undo Phase: Once the redo phase is
in the event of a system crash or failure. It
complete, the system proceeds with the
involves recording log records before modifying
undo phase. Here, the log records are
the corresponding data in the database.
analyzed in reverse order, starting from
Here's a step-by-step breakdown of how WAL the end of the log and moving towards
works: the checkpoint or stable point. If
necessary, the system rolls back the
1. Log Records: A log record is a sequential
incomplete or uncommitted transactions,
entry in a log file that captures the
restoring the database to a consistent state
details of each database operation. These
before the crash occurred.
operations typically include insertions,
updates, and deletions. Each log record By following this WAL approach, the database
contains information such as the operation system ensures that log records are written to
type, the affected data item, and the new stable storage before the corresponding data
or old values of the data item. changes are made. This guarantees that the log
can be used during recovery to reapply
2. Logging Process: Before any modifications
committed changes and undo uncommitted
are made to the database, the system first
changes, thereby maintaining data consistency
writes the corresponding log records to
and recoverability.
stable storage. Stable storage refers to a
reliable, non-volatile storage medium that Overall, WAL is an essential mechanism for
preserves data even in the event of a reliable and efficient database recovery, enabling
system crash or power failure. Writing the the system to recover from failures and restore
log records to stable storage ensures their the database to a consistent state based on the
durability. logged operations
3) Shadow Paging :- recovery process is finished, the system
performs a swap operation. It replaces the
Shadow Paging is a database recovery method original database with the shadow copy,
that involves creating a shadow or temporary making the modifications permanent and
copy of the database during the recovery process. updating the data in the actual database.
This shadow copy provides a consistent view of
6. Cleaning Up: After the swap, the shadow
the database while the actual database is being
pages and the mapping table are no
modified. Once the modifications are complete,
longer needed. They can be discarded or
the system swaps the shadow copy with the
reused for future recovery processes.
original database.
By utilizing shadow paging, the database system
Here's a step-by-step breakdown of how Shadow
ensures that the modifications made during
Paging works:
recovery do not affect the original database
1. Initial Snapshot: The recovery process directly. The shadow copy allows for a consistent
starts with taking an initial snapshot or view of the data during recovery, and the swap
copy of the entire database. This snapshot operation finalizes the modifications and updates
serves as the starting point for recovery the database accordingly.
and represents a consistent state of the
Overall, Shadow Paging provides a mechanism for
database at that particular moment.
recovering the database without directly
2. Shadow Pages: Shadow Paging uses a modifying the original data. It creates a
technique called "copy-on-write." Instead temporary shadow copy, allows modifications to
of modifying the original database pages be made on the shadow copy, and then swaps it
directly, any modifications made during with the original database to complete the
the recovery process are written to new recovery process.
shadow pages. These shadow pages are
separate from the original pages and
4) CHECKPOINTS
remain intact throughout the recovery
process. Checkpoints are specific points in the transaction
3. Transaction Execution: As the system log of a database system where the state of the
executes transactions or modifies data database is recorded.
during the recovery process, it uses the In simpler terms, imagine you're reading a long
shadow pages for those modifications. The book, and you want to mark your progress so
shadow pages allow the system to keep that if you need to stop and come back later,
the original database intact and ensure a you know where to continue. To do this, you
consistent view of the data during place a bookmark at a certain page. This way,
recovery. when you want to resume reading, you can start
4. Page Mapping: To keep track of the from the bookmarked page instead of going
mapping between the original database through the entire book again.
pages and the corresponding shadow In database systems, checkpoints serve a similar
pages, a separate page table or mapping purpose. They act as bookmarks or designated
table is maintained. This table stores the points in the transaction log where the database
mapping information, indicating which management system (DBMS) records the state of
shadow page corresponds to each original the database. The DBMS takes a snapshot of the
page. database at these checkpoints and saves this
5. Completing Modifications: Once all the information, including the current state of the
modifications are complete and the database and other relevant metadata.
During the recovery process, when the DBMS to the database, instead of immediately writing
needs to bring the database to a consistent state those changes directly to the database, the
after a failure or crash, it starts from the last changes are stored temporarily in the transaction
recorded checkpoint. By doing so, it reduces the log.
amount of transaction log that needs to be
This approach ensures that the modifications are
processed for recovery. The DBMS then applies
not immediately applied to the database itself.
the logged transactions recorded after the
The changes are recorded in the transaction log,
checkpoint, ensuring that the database is restored
providing a record of the pending modifications
to its last consistent state.
until the transaction completes and commits.
Checkpoints are valuable for improving recovery
During the recovery process, the DBMS examines
efficiency and reducing the time required to bring
the transaction log and determines the fate of the
the database to a consistent state. Instead of
recorded changes. If the transaction committed,
examining the entire transaction log, the DBMS
meaning it was successful and should be applied,
can start from a known checkpoint and
the changes recorded in the log are re-applied to
selectively process the transactions that occurred
the database. On the other hand, if the
after that point. This selective processing
transaction rolled back or was unsuccessful, the
minimizes the recovery time and resources
changes in the log are discarded, ensuring that
required, making the recovery process more
they do not affect the database.
efficient.
Deferred updates offer flexibility and reliability.
In summary, checkpoints are specific points in
They allow transactions to make temporary
the transaction log where the DBMS records the
modifications without immediately impacting the
state of the database. During recovery, the DBMS
database. By deferring the actual updates until
starts from the last checkpoint, allowing it to
the transaction commits, the system ensures that
selectively process only the transactions that
only the successful changes are applied, and
occurred after that point. Checkpoints help
unsuccessful changes are effectively discarded.
improve recovery efficiency by reducing the
amount of log to be processed and reducing the In summary, deferred updates, or lazy updates,
time required to bring the database to a are a strategy where modifications to the
consistent state. database are postponed until the transaction
commits. Instead of immediately writing changes
to the database, the modifications are stored
6)Deferred updates, or lazy updates (NO
temporarily in the transaction log. During
UNDO /REDO), is a strategy in database
recovery, the changes recorded in the log are
systems where the actual modifications to the
either re-applied to the database if the
database are postponed until the transaction
commits. transaction committed or discarded if the
transaction rolled back. This approach provides
In simpler terms, imagine you're making changes flexibility and ensures that only successful
to your room's decorations. Instead of changes affect the database.
immediately gluing new decorations to the walls,
you decide to write down your planned changes
on a piece of paper. Then, if you change your
mind or want to revert the changes, you can
simply discard the paper without permanently
altering the room.

In database systems, deferred updates work

similarly. When a transaction makes modifications
 CHAPTER FIVE correct data access across distributed
nodes is crucial. These systems use
concurrency control protocols, such as
PARALLEL AND DISTRIBUTED DATABASE SYSTEMS
locking, timestamp ordering, or optimistic
concurrency control, to handle concurrent
Parallel and distributed database systems are
data access and ensure data consistency.
advanced database architectures designed to
handle large-scale data processing and storage A distributed database refers to a collection of
across multiple computers or nodes. These multiple databases that are spread across different
systems are capable of distributing data and computers connected through a network. A
processing tasks to achieve high performance, distributed database management system is a
scalability, fault tolerance, and availability. They software system that handles this distributed
are commonly used in modern data-intensive database while ensuring that the distribution is
applications, such as big data analytics, cloud transparent to the user.
computing, and web-scale services.
Distributed databases are distinct from the files
Key Characteristics of Parallel and Distributed found on the Internet. Web pages consist of files
Database Systems: stored on various nodes on the Internet, but they
don't possess the same functionalities as a
1. Parallelism: These systems leverage
database system, such as uniform query
parallel processing techniques to execute
processing and transaction management.
tasks concurrently across multiple
processors or nodes. By dividing the To differentiate a distributed database from a
workload and processing tasks in parallel, multiprocessor system with shared storage, certain
they can achieve higher performance and conditions must be met:
faster data processing.
1. The databases are connected through a
2. Distribution: Data is distributed across computer network, with multiple sites or
multiple nodes in the system, allowing for nodes. These sites are linked via a
efficient storage and retrieval. Distribution communication network that facilitates
can be achieved through various data and command transmission between
techniques, such as partitioning, them.
replication, or sharding.
2. The connected databases are logically
3. Scalability: Parallel and distributed related, meaning that the information
database systems are designed to scale stored in them has some form of logical
horizontally by adding more nodes to the interrelation.
system. This allows them to handle
3. There is no requirement for all connected
increasing amounts of data and processing
nodes to be identical in terms of data,
demands.
hardware, or software. They can differ
4. Fault Tolerance: These systems incorporate from one another.
mechanisms to handle failures and ensure
The sites within a distributed database can be
data integrity and availability. Techniques
located physically close to each other (e.g., in the
like data replication, redundancy, and
same building or adjacent buildings) and
fault detection and recovery mechanisms
connected through a local area network (LAN).
are employed to mitigate the impact of
Alternatively, they can be geographically
failures.
dispersed across large distances and linked via a
5. Consistency and Concurrency Control: wide area network (WAN). Different types of
Maintaining consistency and ensuring networks, such as wireless hubs, cables,
telephone lines, or satellites, can be used Easier expansion: Distributed database systems
individually or in combination. offer flexibility for system expansion. Adding
more data, increasing database sizes, or
The network's topology, which determines the
incorporating additional processors becomes
communication paths between sites, can
simpler in a distributed environment. It enables
significantly impact performance, influencing
organizations to scale up their system smoothly as
strategies for distributed query processing and
their needs grow.
database design. However, for high-level
architectural considerations, the specific network By leveraging distributed databases, organizations
type is less important than ensuring that each site can enhance application development, achieve
can communicate directly or indirectly with all higher reliability and availability, improve
other sites. performance, and facilitate system expansion.
These advantages contribute to more efficient and
effective data management in distributed
ADVANTAGE OF DISTRIBUTED DATABASE
environments.
Distributed databases offer several advantages for
TYPES OF DISTRIBUTED DATABASES
organizations. Here are some key benefits
explained in simpler terms: A homogeneous distributed database system is a
network of two or more databases that use the
Improved ease and flexibility of application
same type of database management system
development: Developing and maintaining
(DBMS) software and can be stored on one or
applications becomes easier when using a
more machines. In simpler terms, it is a system
distributed database. The transparency of data
where multiple databases, running the same
distribution and control allows organizations with
software, are connected together to form a
geographically distributed sites to work on
distributed network.
applications seamlessly.
In a homogeneous distributed database system,
Increased reliability and availability: A distributed
data can be accessed and modified simultaneously
database system isolates faults to their specific
on several databases within the network. This
site of origin, preventing them from affecting
means that if a change is made to the data in
other databases connected to the network. If one
one department, it will be automatically updated
site fails, other sites can continue to operate,
in other departments as well. This ensures
ensuring data reliability and availability.
consistency and synchronization of data across all
Replicating data and software at multiple sites
the sites.
further enhances reliability. In contrast, a
centralized system would become completely For example, let's consider a scenario where three
unavailable if a single site fails. departments within an organization are using
Oracle-9i as their DBMS software. In this case,
Improved performance: Distributed databases
each department will have its own database, but
optimize performance by keeping data closer to
all the databases will be connected and
where it is most frequently needed. This
synchronized. If any changes are made in one
localization reduces contention for computing
department's database, those changes will be
resources and minimizes access delays, especially
reflected in the databases of the other
in wide area networks. With a large database
departments as well.
distributed across multiple sites, each site
contains a smaller local database, resulting in To achieve this level of cooperation and
faster queries and transactions. Additionally, synchronization, all the sites within the
executing queries in parallel across multiple sites distributed system must run the same type of
improves overall performance. DBMS software. Each site needs to be aware of
the existence of other sites and agree to
cooperate in processing user queries and lack of awareness can limit cooperation and
exchanging information about transactions. coordination in transaction processing.

It's important to note that in a homogeneous Another challenge arises from the differences in
distributed database system, local sites surrender schemas (the structure of the database) among
some of their autonomy in terms of their right to the different DBMS software. These schema
change schemas (the structure of the database) or differences can create difficulties in processing
DBMS software. This is necessary to maintain transactions that involve multiple databases. It
compatibility and coordination between all the may require additional efforts and transformations
sites in the network. to ensure compatibility and consistency of data
across the heterogeneous system.
Overall, a homogeneous distributed database
system allows for the sharing and management of In summary, a heterogeneous distributed database
data across multiple databases, all running the system involves connecting multiple databases
same DBMS software, ensuring consistent and running different DBMS software, allowing data
synchronized access to information. sharing and accessibility through generic
connectivity methods. However, the system may
2) A heterogeneous distributed database system is
face challenges related to site awareness, limited
a network of two or more databases that use
cooperation in transaction processing, and schema
different types of database management system
differences among the databases.
(DBMS) software and can be stored on one or
more machines. In simpler terms, it is a system ARCHITECTURE OF DISTRIBUTED DBMS
where multiple databases, running different
Distributed database management systems (DBMS)
software, are connected together to form a
are designed to manage data spread across
distributed network.
multiple computers or servers. They employ
In a heterogeneous distributed database system, different architectures to handle the distribution
data can be accessed and shared among several and processing of queries. Here's a simplified
databases within the network with the help of explanation of the three common architectures:
generic connectivity methods such as ODBC client-server, collaborating server, and
(Open Database Connectivity) and JDBC (Java middleware.
Database Connectivity). These connectivity
1. Client-Server Architecture:- In the client-
standards enable communication and data
server architecture, there are multiple
exchange between different types of DBMS
clients (users or applications) and a few
software.
servers connected in a network. Clients
For example, imagine a scenario where you have directly connect to specific servers and
a network of databases represented by different access their data by sending direct
DBMS software, such as Oracle, MySQL, and queries. When a client sends a query, it is
MongoDB. In this case, each site within the solved by the earliest available server,
network can access and interact with data from which then sends the result back to the
other sites using ODBC or JDBC. This allows for client. This architecture is simple to
data sharing and integration across different types implement and execute because it relies
of databases. on a centralized server system.

However, there are some challenges in a 2. Collaborating Server Architecture:- In the

heterogeneous distributed database system. Unlike collaborating server architecture, a single
homogeneous systems, where all sites run the query is executed on multiple servers. The
same DBMS software, in a heterogeneous system, servers work together to break down the
each site may run a different DBMS, which single query into multiple smaller queries,
means they may not be aware of each other. This each executed on different servers. The
 results from these queries are then PRINCIPLE OF DATA DISTRIBUTION
combined and sent back to the client. In
In a distributed database system, there are
this architecture, the database servers
different ways to divide the data and tables into
collaborate and support indirect queries,
smaller parts. This division is known as
meaning they can query each other. This
fragmentation. Two common types of
architecture allows for distributed
fragmentation are horizontal fragmentation and
processing of queries and can improve
vertical fragmentation.
performance.
1. Horizontal fragmentation: It involves
3. Middleware Architecture:- The middleware
dividing a table into subsets of rows or
architecture is designed to execute a
tuples. Each subset contains a portion of
single query on multiple servers as well.
the original table's data. This
However, it differs from the collaborating
fragmentation splits the table based on
server architecture by having a dedicated
certain criteria, such as specific values in
server called middleware. This middleware
a column or ranges of values. For
server acts as a mediator between the
example, if we have an employee table,
client and multiple independent database
horizontal fragmentation may split it into
servers. It manages queries and
subsets based on departments, where each
transactions from the client and
subset contains employees from a
distributes them to the appropriate
particular department.
servers. The middleware architecture
utilizes local servers to handle local
queries and transactions. Middleware
software is employed to execute queries
and transactions across one or more
independent database servers.

In summary, the client-server architecture 2. Vertical fragmentation: It involves dividing

involves direct client-server interactions, with a table into subsets of columns. Each
clients sending queries to specific servers. subset represents a portion of the original
Collaborating server architecture allows servers to table's attributes or columns. This
work together to process a single query. fragmentation splits the table based on
Middleware architecture uses a dedicated server specific attributes or columns. For
to manage queries and transactions across example, if we have an employee table,
multiple servers. These architectures enable vertical fragmentation may split it into
distributed database management and enhance subsets, such as one subset containing
scalability, performance, and data availability in basic employee information (e.g., name,
a networked environment. ID) and another subset containing
additional details (e.g., address, salary).
3) HYBRID FRAGMENTATION This approach provides flexibility and efficiency
in distributing and organizing data in a
The third principle of data distribution in a
distributed database system.
distributed database system is called hybrid
fragmentation. It combines aspects of both When a user submits a global query that involves
horizontal and vertical fragmentation to achieve a the entire distributed database, it needs to be
more flexible and efficient data division. transformed into multiple fragment queries to
retrieve data from the appropriate fragments.
In hybrid fragmentation, a table is divided into
Fragmentation transparency ensures that the user
subsets of rows (horizontal fragmentation) and
is unaware of the existence of these individual
each subset is further divided into subsets of
fragments and can interact with the database as
columns (vertical fragmentation). This allows for
if it were a single entity.
more granular control over which data is
distributed and how it is organized. Example :-

With hybrid fragmentation, you can divide a

table based on specific criteria, such as
department, just like in horizontal fragmentation.
However, within each subset, you can also select
which columns or attributes to include, similar to
vertical fragmentation.

For example, let's consider an employee table.

With hybrid fragmentation, you could divide the
table horizontally based on departments, creating
subsets of employees for each department. Within
each department subset, you can further divide TYPES OF DATA FRAGMENTATION
the columns based on attributes, such as having Let's define the types of data fragmentation,
one subset with basic employee information and including horizontal, vertical, and hybrid
another subset with additional details. fragmentation, in simpler terms:

1. Horizontal Data Fragmentation: Horizontal

fragmentation involves dividing a table
into subsets of rows or tuples. Each
subset contains a portion of the original
table's data. This division is done based
on specific criteria, such as values in a
particular column or ranges of values. It
This hybrid approach provides greater flexibility ensures that each subset has all the
in distributing and organizing data in a columns of the original table, maintaining
distributed database system. It allows for more its completeness.
efficient access and retrieval of data by selecting
For example, if we have an employee table,
only the relevant subsets and columns for a given
horizontal fragmentation may split it into subsets
query or transaction.
based on departments, where each subset
In summary, hybrid fragmentation combines contains employees from a specific department.
elements of both horizontal and vertical This helps organize the data based on different
fragmentation. It allows for dividing a table into groups or categories.
subsets of rows (horizontal) and further dividing
each subset into subsets of columns (vertical).
Example :- In Example 1, let's say we have a 2. Vertical Data Fragmentation: Vertical
database schema for students, and we want to fragmentation involves dividing a table
maintain the details of all students studying into subsets of columns. Each subset
Computer Science at the School of Computer represents a portion of the original table's
Science separately. In this case, the database attributes or columns. This division is
designer would horizontally fragment the based on specific attributes or columns of
database. the table.

This means that the original STUDENT table For example, if we have an employee table,
would be divided into subsets or fragments based vertical fragmentation may split it into subsets
on certain criteria. Specifically, the database such as one subset containing basic employee
designer would create a new table called information (e.g., name, ID) and another subset
COMP_STD by selecting all the rows from the containing additional details (e.g., address,
STUDENT table where the course is "Computer salary). This allows for more efficient storage and
Science." retrieval of data, as each subset focuses on a
specific aspect of the table.
The resulting COMP_STD table would only
contain the details of students enrolled in the Example :-
Computer Science course. By performing this
In Example 1, let's consider a University database
horizontal fragmentation, we ensure that the
that keeps records of all registered students in a
School of Computer Science has a separate table
table called STUDENT. Now, the fees details are
specifically dedicated to maintaining the details of
maintained in the accounts section. To perform
Computer Science students.
vertical fragmentation, the database designer
In Example 2, we have an Account table with would create a new table called STD_FEES.
columns such as Acc_No, Balance, Branch_Name,
The STD_FEES table would be created by
and Type. Let's assume that there are multiple
selecting only the required columns from the
values for the Branch_Name column, such as
STUDENT table, specifically the Regd_No
Pune, Baroda, and Delhi.
(registration number) and Fees columns. This
Suppose we want to retrieve all the accounts that means that the new table would contain only
belong to the "Baroda" branch. In this case, the these two columns from the original STUDENT
query would be written as follows: table. The purpose of this vertical fragmentation
is to separate and store the fees-related
SELECT * FROM ACCOUNT WHERE
information in a separate table, allowing for more
Branch_Name = "Baroda"
efficient access and management of that specific
This query retrieves all the rows from the data.
ACCOUNT table where the Branch_Name is
"Baroda." It helps in accessing specific accounts
associated with the Baroda branch.

To summarize, horizontal fragmentation involves

dividing a table into subsets based on specific
criteria, such as course enrollment or branch
location. By horizontally fragmenting the
database, we can create separate tables or subsets
that hold specific data based on the defined
criteria. This helps in organizing and managing
data more efficiently in a distributed database
system.
 improving performance in a distributed database
system.

In Example 2, we have two fragments of vertical

fragmentation. Fragmentation1 selects all the
columns from the table Acc_NO, and
Fragmentation2 selects all the columns from the
table Balance.
3. Hybrid-Fragmentation:-Hybrid
Fragmentation1: SELECT * FROM Acc_NO
fragmentation is achieved by combining
This query retrieves all the columns from the both horizontal and vertical partitioning
table Acc_NO. It represents a subset or fragment techniques. In this approach, a table is
of the original table where only the Acc_No divided horizontally into subsets of rows,
column is considered. and within each subset, further division is
done vertically into subsets of columns.
Fragmentation2: SELECT * FROM Balance
For instance, in an employee table, hybrid
This query retrieves all the columns from the
fragmentation could involve horizontally dividing
table Balance. It represents another subset or
the table based on departments, creating subsets
fragment of the original table where only the
of employees for each department. Within each
Balance column is considered.
department subset, further vertical fragmentation
In vertical fragmentation, the original table is could be applied to group columns based on
divided into subsets or fragments based on specific attributes.
columns. Each fragment contains a specific subset
The hybrid fragmentation approach offers
of columns from the original table. This approach
flexibility and optimization opportunities by
helps in organizing and managing data based on
allowing the data to be organized and distributed
different attributes or columns, allowing for more
based on both rows and columns. It provides
efficient storage and retrieval of specific
finer control over data distribution and can be
information.
useful in scenarios where different subsets of data
To summarize, vertical fragmentation involves need to be accessed or processed efficiently.
dividing a table into subsets based on columns.
To summarize, horizontal fragmentation divides a
Each subset represents a specific subset of
table into subsets of rows, vertical fragmentation
columns from the original table. This approach
divides a table into subsets of columns, and
enables efficient access and management of data
hybrid fragmentation combines both approaches,
based on specific attributes or columns,
dividing a table horizontally and further dividing
each subset vertically. These fragmentation
techniques help in organizing and distributing
data in a distributed database system.

Example :- In the example given, let's consider a

table containing employee information. We'll
focus on two fragments of hybrid fragmentation:

Fragmentation1: SELECT * FROM Emp_Name

WHERE Emp_Age < 40

This fragment selects all the rows from the

original table where the employee's age is less
than 40. It represents a subset of rows based on
a specific condition.

Fragmentation2: SELECT * FROM Emp_Id WHERE

Emp_Address = 'Pune' AND Salary < 14000

This fragment selects all the rows from the

original table where the employee's address is
DATA REPLICATION AND ALLOCATION
'Pune' and the salary is less than 14000. It
represents another subset of rows based on In distributed database systems, data replication
multiple conditions. plays a crucial role in improving data availability
and performance. Replication involves creating
The purpose of hybrid fragmentation is to provide
copies of data across multiple sites within the
a more tailored and efficient way of organizing
distributed system. This response explores the
data based on both row subsets and column
concept of data replication and allocation,
subsets simultaneously.
ranging from full replication to no replication,
To reconstruct the original table from these and the implications they have on system
hybrid fragments, we can use set operations like reliability, performance, and transaction
UNION and FULL OUTER JOIN. These operations processing. The decision of replication and
help combine the fragmented subsets and merge allocation strategies depends on factors such as
them back into a single table. data availability requirements, transaction
patterns, and performance goals.
In summary, hybrid fragmentation involves
dividing a table into subsets of rows and subsets Data Replication and Allocation:
of columns simultaneously. It allows for a more
Data replication is the process of creating copies
flexible and customized approach to data
of data within a distributed database system. The
partitioning in a distributed database system.
most extreme form of replication is fully
Reconstructing the original table from hybrid
replicating the entire database at every site in the
fragments can be done using set operations like
distributed system. This approach offers
UNION and FULL OUTER JOIN to merge the
remarkable data availability, allowing the system
subsets back together.
to continue functioning even if some sites fail. It
also improves performance for global queries
since the results can be obtained locally from any
site.

However, full replication can significantly impact

update operations. Every logical update made to
the database must be applied to each copy,
resulting in increased overhead. This becomes Let's define the three replication schemes (full
especially challenging when there are numerous replication, no replication, and partial replication)
copies of the database. Concurrency control and and the concept of query processing and
recovery techniques become more complex and optimization in simpler terms:
resource-intensive.
1. Full Replication: In the full replication
On the opposite end of the spectrum, there is no scheme, the entire database is replicated
replication. Each fragment of data is stored at a and made available at almost every
single site, ensuring data uniqueness. This location or user in the communication
approach, known as non-redundant allocation, network. This means that every user can
eliminates the need for synchronization among access a complete copy of the database.
copies. However, it reduces data availability and
Advantages of full replication:
fault tolerance.
• High availability of data: Since the
Between these extremes, there are various degrees
database is replicated everywhere, it is
of partial replication. In a partially replicated
readily accessible, ensuring data
database, some fragments are replicated, while
availability.
others are not. The number of copies for each
• Faster execution of queries: Users can
fragment can vary from one to the total number
retrieve data quickly as they can access
of sites in the distributed system. Partial
the nearest replica, reducing
replication is often employed in scenarios
communication delays.
involving mobile workers who carry partially
replicated databases on devices like laptops or Disadvantages of full replication:
PDAs, which are periodically synchronized with
• Concurrency control challenges: Managing
the central server.
concurrent updates becomes complex
The process of assigning fragments or copies of when multiple replicas are involved, as
fragments to specific sites in the distributed conflicts need to be resolved.
system is referred to as data distribution or data • Slower update operations: Updating all
allocation. The allocation strategy depends on replicas to maintain consistency requires
factors such as performance goals, availability more time and resources.
requirements, and transaction patterns. For
2. No Replication: In the no replication
example, a fully replicated database is suitable
scheme, each fragment of the database is
when high availability is essential and most
stored exactly at one location, and there
transactions are retrieval-based. However, if
are no additional copies or replicas.
specific transactions primarily access certain parts
of the database at a particular site, it may be Advantages of no replication:
beneficial to allocate the corresponding fragments • Minimized concurrency: With only one
exclusively to that site. Data accessed by multiple copy of each fragment, concurrency
sites can be replicated to enhance performance conflicts are reduced.
and reduce network latency. • Easy recovery of data: If a failure occurs,
Determining the optimal replication and allocation data recovery is simpler as there is only
strategy for a distributed database system is a one copy to restore.
complex optimization problem. It requires Disadvantages of no replication:
considering trade-offs between data availability,
system performance, resource utilization, and the • Poor availability of data: If the server
specific requirements of the applications and holding the fragment fails, access to that
users. specific fragment is lost until the server is
restored.
 • Slower query execution: As multiple fragments. This transparency simplifies the
clients may need to access the same development and usage of applications, making it
server, it can lead to increased contention easier to work with the distributed database
and slower query processing. system.

3. Partial Replication: Partial replication

involves replicating only selected
fragments of the database, rather than
replicating the entire database.

Advantages of partial replication:

• Replication based on importance: Replicas

are created for specific fragments based
on the importance of the data they hold.
• Flexible optimization: Allows for
optimization by choosing which fragments
to replicate, considering factors such as
access frequency or criticality.

TRANSPARENCY :- Transparency in the context of

distributed databases refers to hiding the
complexities of the system's implementation from
end users. A highly transparent system provides
flexibility to users and application developers by
minimizing their need to understand the
underlying details. In a traditional centralized
database, transparency relates to logical and
physical data independence for application
developers.

However, in the case of a distributed database

scenario, where data and software are distributed
across multiple sites connected by a computer
network, additional types of transparency come
into play. Let's consider an example of a
company database that we have been discussing.
The EMPLOYEE, PROJECT, and WORKS_ON
tables can be divided into smaller parts and
stored across different sites. This fragmentation
allows for better management and potential
replication of the fragments.

Transparency ensures that end users and

application developers are unaware of the
fragmentation and replication details. They can
interact with the database as if it were a single
unified entity, without needing to consider the
distribution of data and the presence of replicated
i