Supplemental Materials and Enrichment Activity Form

Program: Course:
Relational Database Maintenance BSIT
System
Batch Number: Week/s Covered : Inclusive Dates:
2nd week of September 8, 2025 to September 12, 2025
September 2025
Faculty Name: Yr. & Sec.: Time & Day:
MLDELOSSANTOS BSIT 1-31 4:00pm-7:00pm & TH

MODULE 6 (Unit 6: Transaction Processing and Query Optimization )

Topics:
1. Transaction Processing
2. ACID Properties of DBMS
3. Lock-based Concurrency Control
4. Query Optimization

Course Learning Outcomes:

At the end of this lesson students should be able to:
1. Principle of Transaction Management System
2. Concept of Lock-Based Concurrency Control
3. Dead Lock, Two Phase Locking Scheme
4. Need for Query Optimization
5. Query Optimizer Architecture
6. Query Evaluation Plans
7. Query Optimization Using Genetic Algorithm

Unit 6: Transaction Processing and Query Optimization

Transaction Processing

Managing Data is the critical role in each and every organization. To achieve the hike in business they
need to manage data efficiently. DBMS provides a better environment to store and retrieve the data in an
economical and efficient manner. User can store and retrieve data through various sets of instructions.
These sets of instructions do several read and write operations on database. These processes are
denoted by a special term “Transaction” in DBMS.

Transaction is the execution of user program in DBMS. It is different from the execution of the program
external to DBMS. In other words it can be stated as the various read and write operations done by the
user program on the DBMS, when it is executed in DBMS environment.

The key notations in transaction management are as follows:

Object. The smallest Data item which is read or updated by the Transaction is called as Object in
this case.
 Supplemental Materials and Enrichment Activity Form

Transaction. Transaction is represented by the symbol T. It is termed as the execution of query

in DBMS.
Read Operation. Read operation on particular object is notated by symbol R (object-name).
Write Operation. Write operation on particular object is notated by symbol W(object-name).
Commit. This term used to denote the successful completion of one Transaction.
Abort. This term used to denote the unsuccessful interrupted Transaction.

Concept of Transaction Management

User program executed by DBMS may claim several transactions. In the web environment, there is a
possibility to several users’ attempt to access the data stored in same database. To maintain the
accuracy and the consistency of the database several scheduling algorithms are used.

To improve the effective throughput of the DBMS we need to enforce certain concurrent executions in
DBMS. Transaction Manager is responsible for scheduling the Transactions and providing the safest path
to complete the task. To maintain the data in the phase of concurrent access and system failure, DBMS
need to ensure four important properties. These properties are called as ACID properties.

ACID Properties of DBMS

ACID is an acronym for Atomicity, Consistency, Isolation, and Durability.

A– Atomicity

C– Consistency

I– Isolation

D– Durability

Atomicity and Durability are closely related.

Consistency and Isolation are closely related.

The ACID properties are explained as follows

Atomicity

Either all Transactions are carried out or none are. The meaning is the transaction cannot be subdivided,
and hence, it must be processed in its entirety or not at all. Users should not have to worry about the
effect of incomplete Transactions in case of any system crash occurs.

Transactions can be incomplete for three kinds of reasons:

1. Transaction can be aborted, or terminated unsuccessfully. This happens due to some anomalies
arises during execution. If a transaction is aborted by the DBMS for some internal reason, it is
automatically restarted and executed as new.
 Supplemental Materials and Enrichment Activity Form

2. Due to system crash. This may be happen due to Power Supply failure while one or more Transactions
in execution.

3. Due to unexpected situations. This may be happen due to unexpected data value or be unable to
access some disk. So the transaction will decide to abort. (Terminate itself).

Durability

If the System crashes before the changes made by a completed Transaction are written to disk, then it
should be remembered and restored during the system restart phase

Partial Transactions should be avoided to gain consistency of database. To undo the operations done
by the Partial Transactions DBMS maintains certain log files. Each and every moment of disk writes are
recorded in this log files before they are reflected to disk. These are used to undo the operations done
when the system failure occurs.

Consistency and Isolation

Consistency

Users are responsible for ensuring transaction consistency. User who submits the transaction should
make sure the transaction will leave the database in a consistent state

Isolation

In DBMS system, there are many transactions may be executed simultaneously. These transactions
should be isolated to each other. One’s execution should not affect the execution of the other
transactions. To enforce this concept DBMS has to maintain certain scheduling algorithms. One of the
scheduling algorithms used is Serial Scheduling.
 Supplemental Materials and Enrichment Activity Form

Serial Scheduling In this scheduling method, transactions are executed one by one from the start to
finish. An important technique used in this serial scheduling is interleaved execution

Explanation

In the above example, twoTransactionsT1,T2 and two Objects A,B are taken into account. Commit
denotes successful completion of both Transactions. First one read and one write operation are done on
the object A by Transaction [Link] is followed by T1. It does one write operation on object A. The same
procedure followed by others for further. Finally both Transactions are ended successfully

Anomalies due to Interleaved Transactions

If all the transactions in DBMS systems are doing read operation on the Database then no problem will
arise. When the read and write operations done alternatively there is a possibility of some type of
anomalies.

These are classified into three categories

. [Link]–Read Conflicts (WR Conflicts)

[Link]–Write Conflicts (RW Conflicts)

[Link]–Write Conflicts (WW Conflicts)

WR Conflicts
 Supplemental Materials and Enrichment Activity Form

Explanation

Suppose if the transactions are interleaved according to the above schedule, then the account transfer
program T1 deducts$100 from account A, then the interest deposit program T2 reads the current values
of accounts A and Band adds 6% interest to each, and then the account transfer program credits$100
[Link] execution like if the two instructions
are executed one by one. This type of anomalies leaves the database in inconsistency state

RW Conflicts

Explanation

At first, T1 checks whether the money in account A is more than$100. Immediately it is

interleavedandT2alsocheckstheaccount for money and reduce itby$100.AfterT2,T1 is tried to reduce the
same account A. If the initial amount inAis$101then, after theexecutionofT2only$1will remain in
accountA.NowT1will try to reduce itby$[Link] Database inconsistent.
 Supplemental Materials and Enrichment Activity Form

WW Conflicts

The third type of anomalous behavior is that one Transaction is updating an object while another one is
also in progress.

Explanation

If A and Bare two accounts and their values have to be kept equal always, Transaction T1 updates both
objects to 3,000 and T2 updates both objects to 2,000. At first T1 updates the value of object A to3,000.
Immediately T2 makes A as 2,000 and Bas 2,000 and committed. After the completion of T2 ,T1 updates
B to 3,000 Now the value of Ais 2,000 and value of Bis3,000, they are not equal. Constraint violated in
this case due to serial scheduling.

Durability

Durable means the changes are permanent. Once a transaction is committed, no subsequent failure of
the database can reverse the effect of the transaction.

Lock-Based Concurrency Control

Concurrency Control is the control on the Database and Transactions which are executed concurrently to
ensure that each Transaction completed healthy. Concurrency control is concerned with preventing loss
of data integrity due to interference between users in a multiuser environment.

Need for Concurrency Control

In database management system several transactions are executed simultaneously. In order to achieve
concurrent transactions, the technique of interleaved execution is used. But in this technique there is a
 Supplemental Materials and Enrichment Activity Form

possibility for the occurrence of certain anomalies, due to the overriding of one transaction on the
particular Database Object which is already referred by another Transaction.

Lock-Based Concurrency Control

It is the best method to control the concurrent access to the Database Objects by providing suitable
permissions to the Transactions. Also it is the only method which takes less cost of Time and less
program complexity in terms of code development.

Key Terms in Lock-Based Concurrency Control

Database Object

Database Object is the small data element, the value of which one is altered during the execution of
transactions.

Lock

Lock is a small object associated with Database Object which gives the information about the type of
operations allowed on a particular Database Object.

Lock can be termed as a type of permission provided by the transaction manager to the transactions
to do a particular operation on a Database Object. The transaction must get this permission from
Transaction Manager to access any Database Object for alteration. Locking mechanisms are the most
common type of concurrency control mechanism. With locking, any data that is retrieved by a user for
updating must be locked, or denied to other users, until the update is complete.

Locking Protocol

It is the set of rules to be followed by each transaction, to ensure that the net effect of execution of each.
Transaction in interleaved fashion will be same as, the result obtained when the Transactions executed in
serial fashion. Generally, locks can be classified into two. First one is related to what already told in the
previous paragraph. Next one is the unwanted effect when we implement lock of the first type. The two
types of Lock are:

1. Strict Two-Phase Locking (Strict 2PL)

2. Deadlock

Strict Two-Phase Locking (Strict 2PL)

It is a most widely used locking protocol. It provides few rules to the Trans actions to access the
Database Objects. They are:
 Supplemental Materials and Enrichment Activity Form

Shared Lock. It is type of lock established on a Database Object. It is like a component which is sharable
within all active transactions. A Database Object can be shared locked by more than one number of
transactions. To get a shared lock on particular Database Object the Database Object should satisfy the
following condition.

Condition. It should not be exclusively locked by any of the other Trans actions

Exclusive Lock

. It is type of lock established on a Database Object. It is like a component which cannot be shared within
all active Transactions. It is dedicated to particular transaction; only that particular transaction can access
and modify that object.

Condition. It should not be exclusively locked by any one of the other Transactions

Deadlock

Deadlock occurs within the Transactions in DBMS system. Due to this neither one will be committed. This
is the dead end to the execution of transactions. DBMS has to use suitable recovery systems to
overcome Deadlocks.

Reasons for Deadlock Occurrence.

Deadlock occurs mainly due to the Lock Based Concurrency Control. The exclusive lock type will isolate
one particular Database Object from the access of other transactions. This will suspend all the
transactions who request Shared lockon that particular Database Object until the transaction which holds
Exclusive lock on that object is completed.
 Supplemental Materials and Enrichment Activity Form

This will create a loop in Database which leads to Deadlock within transactions. This will leave the
Database in inconsistent state.

Explanation

Here we can observe that the loop occurs between T1 and T3. Neither T1 nor T3 are completed

Methods to Overcome Deadlock

Mostly it is not possible to avoid the occurrence of Deadlock. Most of the methods available are detection
and recovery based.

Detection from the Average Waiting Time of the Transaction If more than two transactions are waiting for
the long time, then it implies that at some part of the database, deadlock has occurred. So we can detect
Deadlock easily. Deadlock Detection algorithm Deadlock detection algorithms are used to find any loops
in the Database. The main advantage is that we can find the locked transactions quickly and it is enough
to restart only those particular transactions.

Recovery Mechanism

Once if Deadlock is found then we have several methods to release locked Transactions.

Method 1: Release of Objects from Big Transaction

In this method the transaction which holds more number of Database Object will be taken and all
Database Objects associated with that Big Transaction will be removed.
 Supplemental Materials and Enrichment Activity Form

Method 2: Restarting the Locked Transactions

In this method Database Objects associated with all Transactions are released

and they will be restarted

Sample Deadlock Detection Program in“C”(Pseudocode)

The sample pseudocode for dead lock detection is as follows. The program flow and the process block
for the deadlock detection are illustratedinFigs.7.6 and7.7,respectively
 Supplemental Materials and Enrichment Activity Form

IN THE FLOWCHART:

NTR=[Link] Transactions

NOR=[Link] Objects Requested

OAL=Object Allocated

ORTT=Object Requested To Transaction

OATT=Object Allocated To Transaction

 Supplemental Materials and Enrichment Activity Form

Transaction Processing Example

Imagine Alice buys 1 Smartphone.

We need to:

Insert into orders

Insert into order_items

Update product stock

Use a transaction to ensure Atomicity:

START TRANSACTION;

-- Step 1: Create new order

INSERT INTO orders (customer_id) VALUES (1);
SET @last_order_id = LAST_INSERT_ID();

-- Step 2: Insert order item

INSERT INTO order_items (order_id, product_id, quantity)
 Supplemental Materials and Enrichment Activity Form

VALUES (@last_order_id, 2, 1);

-- Step 3: Update product stock

UPDATE products
SET stock = stock - 1
WHERE product_id = 2 AND stock >= 1;

-- Commit if all successful

COMMIT;

If any step fails (e.g., stock < 1), we can use:

ROLLBACK;

This ensures consistency.

Query Optimization

.As we are in the comfortable age of information technology, databases have become a necessary and
fundamental tool for managing and exploiting the power of information. Because the amount of data in a
database grows larger and larger as time passes, one of the most important characteristics of a data
base is its ability to maintain a consistent and acceptable level of performance. The principal mechanism
through which a database maintains an optimal level of performances is known as the database query
optimizer; without a well-designed query optimizer, even small databases would be noticeably slug gish.
The query optimizers for some of the most popular commercial-quality databases are estimated to have
required about 50 man-years of development. It should therefore go without saying that the specific
processes involved in designing the internal structure of a real-world optimizer can be overwhelm ingly
complex. Nevertheless, because of the optimizer’s paramount importance to the robustness and flexibility
of a database, it is worthwhile to engage in a survey of the theory behind the rudimentary components of
a basic, cost-based query optimizer.

Query Processing

The activities involved in retrieving data from the database are called as query processing. The aims of
query processing are to transform a query written in a high-level language typically SQL, into a correct
and efficient execution strategy expressed in a low-level language (implementing relational algebra), and
to execute the strategy to retrieve the required data. An important aspect of query processing is Query
Optimization.

The activity of choosing an efficient execution strategy for processing a query is called as query
optimization. As there are many equivalent trans formations of the same high-level query, the aim of
query optimization is to choose the one that minimizes the resource usage.

A DBMS uses different techniques to process, optimize, and execute high level queries (SQL). A query
expressed in high-level query language must be f first scanned, parsed, and validated.

The scanner identifies the language components (tokens) in the text of the query, while the parser
checks the correctness of the query syntax. The query is also validated (by accessing the system catalog)
 Supplemental Materials and Enrichment Activity Form

whether the attribute names and relation names are valid. An internal representation (tree or graph) of the
query is created.

Queries are parsed and then presented to a query optimizer, which is responsible for identifying an
efficient plan. The optimizer generates alternative plans and chooses the plan with the least estimated
cost.

Need for Query Optimization

In high-level query languages, any given query can be processed in different ways. Resources required
by each query will be different. DBMS has the responsibility to select the optimized way to process the
query. Query optimizers do not “optimize”– just try to find “reasonably good” evaluation strategies. Query
optimizer uses relational algebra expressions.

Basic Steps in Query Optimization

The two basic steps involved in query optimization are:

– Enumerating alternative plans for evaluating the expression.

Because number of alternative plans are large

.– Estimating the cost of each enumerated plan and choosing

the plan with least estimated cost. Taking SQL query for query
Optimization, when it is given as input to the following system
of processes, the Query undergoes to the following stages as
illustrated in Fig.7.8. As in Fig.7.8, the DBMS begins by parsing
the SQL statement. It breaks the statement into individual
words, makes sure that the statement has a valid verb, legal
clauses, and so on. Syntax errors and misspellings can be
detected in this step. The DBMS validates the statement. It
checks the statement against the system catalog. It checks
whether all the tables referred exists in the database and their
definition exists in the catalog. The optimizer optimizes the
statement. It explores various ways to carry out the statement.
After exploring alternatives, it chooses one of them.

The optimizer then generates an execution plan for the statement. The plan is a binary representation of
the steps that are required to carry out the statement; it is the DBMS equivalent of “executable code.” It is
carried out in Runtime Database Processor. Finally, the DBMS carries out the statement by executing the
execution plan.

Query Optimizer Architecture In the query optimizer architecture we provide an abstraction of the query
optimization process in a DBMS. Given a database and a query on it, several execution plans exist that
can be employed to answer the query. In principle, all the alternatives need to be considered so that the
 Supplemental Materials and Enrichment Activity Form
one with the best estimated performance is chosen. An abstraction of the process of generating and
testing these alternatives is shown in Fig.7.9, which is essentially a modular architecture of a query
optimizer. Based on the figure, the entire query optimization process involves two stages: Rewriting and
Planning. There is only one module in the first stage, the Rewriter, whereas all other modules are in the
second stage.

Module Functionality

The functionalities of each module in the Query optimizer are discussed in this section.

Rewriter

This module applies transformations to a given query and produces equivalent queries that are hopefully
more efficient, e.g., replacement of views with their definition. The transformations performed by the
Rewriter depend only on the declarative, i.e., static characteristics of queries do not take into account the
actual query costs for the specific DBMS and database concerned. If the rewriting is known or assumed
to always be beneficial, the original query is discarded; otherwise, it is sent to the next stage as well. By
the nature of the rewriting transformations, this stage operates at the declarative level.

Planner

This is the main module of the ordering stage. It examines all possible execution plans for each query
produced in the previous stage and selects the overall cheapest one to be used to generate the answer of
the original query. It employs a search strategy, which examines the space of execution plans in a
particular fashion. This space is determined by two other modules of the optimizer, the Algebraic Space
and the Method-Structure Space. For the most part, these two modules and the search strategy
determine the cost, i.e., running time, of the optimizer itself, which should be as low as possi ble. The
execution plans examined by the Planner are compared based on estimates of their cost so that the
cheapest may be chosen. These costs are derived by the last two modules of the optimizer namely the
Cost Model and the Size-Distribution Estimator.

Algebraic Space

This module determines the action execution orders that are to be considered by the Planner for each
query sent to it. All such series of actions produce the same query answer, but usually differ in
performance. They are usually represented in relational algebra as formulas or in tree form. Because of
the algorithmic nature of the objects generated by this module and sent to the Planner, the overall
planning stage is characterized as operating at the procedural level.
 Supplemental Materials and Enrichment Activity Form

Method-Structure Space

This module determines the implementation choices that exist for the execution of each ordered series of
actions specified by the Algebraic Space. This choice is related to the available join methods for each join
(e.g., nested loops, merge scan, and hash join). This choice is also related to the available indices for
accessing each relation, which is determined by the physical schema of each database stored in its
catalogs. Given an algebraic formula or tree from the Algebraic Space, this module produces all
corresponding complete execution plans, which specify the implementation of each algebraic operator
and the use of any indices.

Cost Model

This module specifies the arithmetic formulas that are used to estimate the cost of execution plans. For
every different join method, for every different index type access, and in general for every distinct kind of
step that can be found in an execution plan, there is a formula that gives its cost.

Given the complexity of many of these steps, most of these formulas are simple approximations of what
the system actually does and are based on certain assumptions regarding issues like buffer
management, disk–CPU overlap, sequential vs. random I/O, etc. The most important input parameters to
a formula are the size of the buffer pool used by the corresponding step, the sizes of relations or indices
accessed, and possibly various distributions of values in these relations. While the first one is determined
by the DBMS for each query, the other two are estimated by the Size-Distribution Estimator.

Size-Distribution Estimator

This module specifies how the sizes (and possibly frequency distributions of attribute values) of database
relations and indices as well as (sub) query results are estimated. As mentioned above, these estimates
are needed by the Cost Model. The specific estimation approach adopted in this module also deter mines
the form of statistics that need to be maintained in the catalogs of each database, if any.

Detailed Description

This section provides a detailed description of the Algebraic Space, the Planner, and Size-Distribution
Estimator, respectively.

Algebraic Space

SQL query corresponds to a select-project-join query in relational algebra. Typically, such an algebraic
query is represented by a query tree whose leaves are database relations and nonleaf nodes are
algebraic operators like selections (denoted by σ) projections (denoted by π), and joins (denoted by ). An
intermediate node indicates the application of the corresponding operator on the relations generated by
its children, the result of which is then sent further up. Thus, the edges of a tree represent data flow from
bottom to top, i.e., from the leaves, which correspond to data in the database, to the root, which is the
final operator producing the query answer. Figure7.10 gives three examples of query trees for the query.

SELECT name, floor FROM emp, dept WHERE [Link] = [Link] AND sal > 100K

For a complicated query, the number of all query trees may be enormous. To reduce the size of the
space that the search strategy has to explore, DBMSs usually restrict the space in several ways. The first
typical restriction deals with selections and projections:
 Supplemental Materials and Enrichment Activity Form
R1 Selections and projections are
processed on the “y” and almost
never generate intermediate
relations. Selections are processed
as relations are accessed for the first
time. Projections are processed as
the results of other operators are
generated.

For example, plan P1 of Sect.7.1.1

satisfies restriction R1: the index
scan of emp finds emp tuples that
satisfy the selection on [Link] on
the “y and attempts to join only those; furthermore, the projection on the result attributes occurs as the
join tuples are generated. For queries with no join, R1 is root. For queries with joins, however, it implies
that all operations are dealt with as part of join execution. Restriction R1 eliminates only suboptimal query
trees, since separate processing of selections and projections incurs additional costs. Hence, the
Algebraic Space module specifies alternative query trees with join operators only, selections and
projections being implicit.

Given a set of relations to be combined in a query, the set of all alternative join trees is determined by
two algebraic properties of join: commutativity (R1 R2 ≡R2 R1)and associativity ((R1 R2) R3 ≡ R1 (R2
R3)). The first determines which relation will be inner and outer in the join execution. The second
determines the order in which joins will be executed. Even with the R1 restriction, the alternative join trees
that are generated by commutativity and associativity is very large, (N!) for N relations. Thus, DBMSs
usually further restrict the space that must be explored. In particular, the second typical restriction deals
with cross products.

R2 Cross products are never formed, unless the query itself asks for them. Relations are combined
always through joins in the query. For example, consider the following query:

SELECT name, floor, balance

FROM emp, dept, acnt

WHERE [Link]=[Link] AND [Link]=[Link].

Figure7.11 shows the three possible join trees (modulo join commutativity) that can be used to combine
the emp, dept, and acnt relations to answer the query.

Of the three trees in the Fig.7.11, tree T3 has a cross product, since its lower join involves relations emp
and acnt, which are not explicitly joined in the query. Restriction R2 almost always eliminates suboptimal
 Supplemental Materials and Enrichment Activity Form
join trees, due to the large size of the results typically generated by cross products. The exceptions are
very few and there are cases where the relations forming cross products are extremely small. Hence, the
Algebraic Space module specifies alternative join trees that involve no cross product. The exclusion of
unnecessary cross products reduces the size of the space to be explored, but that still remains very large.
Although some systems restrict the space no further (e.g., Ingres and DB2-Client/Server), others require
an even smaller space (e.g., DB2/MVS). In particular, the third typical restriction deals with the shape of
join trees. R3 The inner operand of each join is a database relation, never an intermediate result. For
example, consider the following query:

SELECT name, floor, balance, address

FROM emp, dept, acnt, bank

WHERE [Link]=[Link] AND [Link]=[Link] AND [Link]=[Link]

Figure7.12 shows three possible cross-product-free join trees that can be used to combine the emp,
dept, acnt, and bank relations to answer the query. Tree T1 satisfies restriction R3, whereas trees T2 and
T3 do not, since they have at least one join with an intermediate result as the inner relation. Because of
their shape, join trees that satisfy restriction R3, e.g., tree T1, are called left-deep. Trees that have their
outer relation always being a database relation, e.g., tree T2, are called right-deep. Trees with at least
one join between two intermediate results, e.g., tree T3 is called bushy. Restriction R3 is of a more
heuristic nature than R1 and R2 and may well eliminate the optimal plan in several cases. It has been
claimed that most often the optimal left-deep tree is not much more expensive than the optimal tree
overall. The two typical arguments used are:

– Having original database relations as inners increases the use of any preexisting indices

.– Having intermediate relations as outers allows sequences of nested loops joins to be executed in a
pipelined fashion

Fig. 7.12. Examples of left-deep (T1), right-deep (T2), and bushy (T3) join trees

restriction R3 significantly reduces the number of alternative join trees, to O(2N) for many queries with N
relations. Hence, the Algebraic Space module of the typical query optimizer only specifies join trees that
are left-deep. In summary, typical query optimizers make restrictions R1, R2, and R3 to reduce the size of
the space they explore.
 Supplemental Materials and Enrichment Activity Form

Planner

The role of the Planner is to explore the set of alternative execution plans, as specified by the Algebraic
Space and the Method-Structure space, and find the cheapest one, as determined by the Cost Model and
the Size-Distribution Estimator. This section deals with different types of search strategies that the
Planner may employ for its exploration. The first one focuses on the most important strategy, dynamic
programming, which is the one used by essentially all commercial systems. The second one discusses a
promising approach based on randomized algorithms, and the third one talks about other search
strategies that have been proposed. Size-Distribution Estimator The final module of the query optimizer
that we examine in detail is the

Size Distribution Estimator.

Given a query, it estimates the sizes of the results of (sub) queries and the frequency distributions of
values in attributes of these results.

Basic Algorithms for Executing Query Operations

A query basically consists of following operations. The query can be analyzed by analyzing these
operations separately

.– Selection Operation

– Join Operation

– Projection Operation

– Set Operations Select Operation A query can have condition to select the required data. For that
selection it may use several ways to search for the data. The following are some of the ways to search

:– File Scan

– Index Scan

File Scan

A number of search algorithms are possible for selecting the records from a file. The selection of records
from a file is known as file scan, as the algorithm scans the records of a file to search for and retrieve
records that satisfy the selection condition.

Index Scan

If the search algorithm uses an index to perform the search, then it is referred as Index Scan.

– Linear Search:

This is also known as Brute Force method. In this method, every record in the file is retrieved and tested
as to whether its attribute values satisfy the selection condition

.– Binary Search: If a selection condition involves an equality comparison on a key attribute on which the
file is ordered, a binary search can be used. Binary search is more efficient than linear search
 Supplemental Materials and Enrichment Activity Form
.– Primary Index Single Record Retrieval: If a selection condition involves an equality comparison on a
primary key attribute with a primary index, we can use the primary index to retrieve that record

.– Secondary Index: This search method can be used to retrieve a single record if the indexing field has
unique values (key field) or to retrieve multiple records if the indexing field is not a key. This can also be
used for comparisons involving , <=or>= 342 7 Transaction Processing and Query Optimization

– Primary Index Multiple Records Retrieval: A search condition uses com parison condition, etc. on a key
field with primary index is known as Primary index multiple records retrieval

.– Clustering Index: If the selection condition involves an equality comparison on a nonkey attribute with a
clustering index, we can use that index to retrieve all the records satisfying the condition.

Conjunctive Condition Selection

If the selection condition of the SELECT operation is a conjunctive codition (a condition that is made up
of several simple conditions with the AND operator), then the DBMS can use the following additional
methods to perform the selection.

Conjunctive selection: If an attribute in any single simple condition in the conjunctive condition has an
access path that permits use of binary search or an index search, use that condition to retrieve the
records and then check if that record satisfies the remaining condition.

Conjunctive selection using composite index: If two or more attributes are involved in equality conditions
in the conjunctive condition and a composite index exists on the combined fields we can use the index.

Query Optimization for Select Operation

Following method gives query optimization for selection operation:

1. If more than one of the attributes has an access path, then use the one that retrieves fewer disk
blocks.

2. Need to consider the selectivity of a condition: Selectivity of a condition is the number of tuples that
satisfy the condition divided by total number of tuples. The smaller the selectivity the fewer the number of
tuples retrieved and higher the desirability of using that condition to retrieve the records.

Join Operation

Join is one of the most time-consuming operations in query processing. Here we consider only equijoin or
natural join. Two-way join is a join of two relations, and there are many ways to perform the join. Multiway
join is a join of more than two relations and number of ways to execute multiway joins increases rapidly
with number of relations.

We use methods for implementing two-way joins of form

RJN(a = b)S

where, R and S are relations which need to be joined, a and b are attributes used for conditions, and JN
→ Type of join.
 Supplemental Materials and Enrichment Activity Form

Methods for Implementing Joins

Following are various methods to implement join operations.

Nested (Inner–Outer) Loop

For each record t in R (outer loop), retrieve every record s from S (inner loop) and test whether the two
records satisfy the join condition t[A] = s[B].

Example:

SELECT
c.customer_name,
o.order_id,
p.product_name
FROM
Customers c
INNER JOIN
(Orders o
INNER JOIN Products p ON o.product_id = p.product_id)
ON
c.customer_id = o.customer_id;

Access Structure Based Retrieval of Matching Records

If an index (or hash key) exists for one of the two join attributes– say, B of S retrieve each record t in R,
one at a time, and then use the access structure to retrieve directly all matching records from S that
satisfy s[B] = t[A].

Sort-merge join

If the records of R and S are physically sorted (ordered) by value of the join attributes A and B,
respectively, then both the relations are scanned in order to the join attributes, matching the records that
have same values for A and B. In this case, the relations R and S are only scanned once.

Example:

SELECT e.emp_id, [Link], d.dept_name

FROM (
SELECT * FROM Employees ORDER BY dept_id
) AS e
JOIN (
SELECT * FROM Departments ORDER BY dept_id
) AS d
ON e.dept_id = d.dept_id;
 Supplemental Materials and Enrichment Activity Form

Hash-join

The tuples of relations R and S are both hashed to the same hash file, using the same hashing function
on the join attributes A of R and B of S as hash keys. A single pass through the relation with fewer
records (say, R) hashes its tuples to the hash file buckets. A single pass through the other relation (S)
then hashes each of its tuples to the appropriate bucket, where the record is combined with all matching
records from R.

In practice all the above techniques are implemented by accessing whole disk blocks of a relation,
rather than individual records. Depending on the availability of buffer space in memory the number of
blocks read in from the file can be adjusted. It is advantageous to use the relation with fewer blocks as
the outer loop relation in nested loop method.

For method using access structures to retrieve matching tuples, either the smaller relation or the file that
has a match for every record (high join selection factor) should be used in the outer loop. In some cases
an index may be created specifically for performing the join operation if one does not exist already.

Sort-Merge algorithm is the most efficient, sometimes the relations are sorted before merging. Hash join
method is efficient if the hash file can be kept in the main memory.

Example:

SELECT e.emp_id, [Link], d.dept_name

FROM Employees e
JOIN Departments d
ON e.dept_id = d.dept_id;

Query Optimization Example

Query:

Find total spending per customer.

SELECT [Link], SUM([Link] * [Link]) AS total_spent

FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN order_items oi ON o.order_id = oi.order_id
JOIN products p ON oi.product_id = p.product_id
GROUP BY c.customer_id;

Optimization Technique

Add indexes for faster lookups:

CREATE INDEX idx_orders_customer ON orders(customer_id);

CREATE INDEX idx_orderitems_order ON order_items(order_id);
CREATE INDEX idx_orderitems_product ON order_items(product_id);
 Supplemental Materials and Enrichment Activity Form

Use EXPLAIN to check query plan:

EXPLAIN SELECT [Link], SUM([Link] * [Link]) AS total_spent

FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN order_items oi ON o.order_id = oi.order_id
JOIN products p ON oi.product_id = p.product_id
GROUP BY c.customer_id;

This will show if indexes are being used properly.

==================================================================
References:

==================================================================

Exercise 6: Transaction Processing and Query Optimization

1. Normalize the following table:

CREATE TABLE ecommerce_orders (
-- Order info
order_id BIGINT NOT NULL,
order_date DATETIME NOT NULL,

-- Customer info (duplicated in every row for easy reporting)

customer_id BIGINT NOT NULL,
customer_name VARCHAR(150) NOT NULL,
customer_email VARCHAR(150),
customer_phone VARCHAR(50),
customer_address TEXT,

-- Product info (1 row = 1 product in the order)

product_id BIGINT NOT NULL,
product_name VARCHAR(200) NOT NULL,
product_sku VARCHAR(50),
product_category VARCHAR(100),
brand_name VARCHAR(100),
unit_price DECIMAL(10,2),
quantity INT,
line_total DECIMAL(12,2), -- unit_price * quantity

-- Payment info
payment_method VARCHAR(50), -- e.g., Credit Card, PayPal, COD
payment_status VARCHAR(50), -- Paid, Pending, Failed
transaction_id VARCHAR(100),

-- Shipping info
shipping_method VARCHAR(100),
shipping_status VARCHAR(50), -- Processing, Shipped, Delivered
tracking_number VARCHAR(100),
shipping_cost DECIMAL(10,2),
 Supplemental Materials and Enrichment Activity Form
-- Order totals (duplicated on each row of the same order)
order_subtotal DECIMAL(12,2),
order_discount DECIMAL(12,2),
order_tax DECIMAL(12,2),
order_grand_total DECIMAL(12,2),

-- Order items
order_id BIGINT NOT NULL,
product_id BIGINT NOT NULL,
quantity INT NOT NULL,
line_total DECIMAL(12,2), -- quantity * unit_price

PRIMARY KEY (order_id, product_id),

FOREIGN KEY (order_id) REFERENCES orders(order_id),
FOREIGN KEY (product_id) REFERENCES products(product_id)

PRIMARY KEY (order_id, product_id) -- composite key (1 order, many products)

);

2. Using transaction processing, implement the following:

• Insert into orders

• Insert into order_items

• Update product stock

• Use a transaction to ensure Atomicity:

• Commit if all successful

• Rollback If any step fails

3. Lastly, perform query optimization.