Module 1

Query Processing &

Optimization
Class-TE IT
Subject: ADMT
Query Optimization
q Query Optimization is a process of selecting the most
efficient way to execute a given query by considering various
query plans and choosing the one that requires the least
resources, such as CPU time, memory, and disk I/O.

q A query can have many possible execution strategies each

with different performances the process of selecting a
reasonably efficient execution plan is known s query
optimization
Goals of Query Optimization
1. Eliminate Unwanted Data:
Query optimization aims to eliminate unnecessary data to reduce
the amount of data processed and improve performance.

-- Initial query that selects all columns

SELECT * FROM Employees;

-- Optimized query that selects only necessary columns

SELECT Emp_Name FROM Employees;

Goals of Query Optimization
2. Speed Up Queries:
The optimization process tries to find query plans that provide
results quickly

-- Initial query that might take longer to execute

SELECT * FROM LargeTable WHERE SomeCondition;

-- Optimized query with index

CREATE INDEX idx_condition ON LargeTable(SomeCondition);

SELECT * FROM LargeTable

WHERE SomeCondition;
Goals of Query Optimization
3. Increase Query Performance by Simplifying Complex Queries:
Breaking down complex SQL statements into simpler ones can
enhance performance.

4. Select the Best Query Plan from Alternatives::

The optimizer evaluates multiple query plans and selects the one
with the lowest estimated cost.
SELECT salary FROM instructor WHERE salary > 75000;

Alternative 1 : σ(salary < 75000) (π(salary) (instructor))

Alternative 2: π(salary) (σ(salary < 75000) (instructor))
 Student Result Subject
Roll Name City
Roll No Subject_ID Marks Subject_ID Subject_Name
No
1 Priya Mumbai S1 Physics
1 S1 90
2 Ram Chennai 2 S2 60 S2 Chemistry
3 S1 75
3 Jayanti Pune S3 Math
4 S3 42

4 Kapil Mumbai

Display rollno,name of students who have enrolled in Physics

Subject

П RollNo, Name (ϭSubject_Name=’Physics’(Student ⋈ Result ⋈ Subject))

q The above expression constructs a large intermediate relation, Student
⋈ Result ⋈ Subject. However, we are interested in only a few tuples of
this relation
Initial Expression Tree 1. Result ⋈ Subject
П RollNo, Name Roll No Subject_ID Marks Subject_Name

1 S1 90 Physics
ϭSubject_Name=’Physics’ 2 S2 60 Chemistry
3 S1 75 Physics
4 S3 42 Math
⋈ 2. Student ⋈ Result ⋈ Subject
Roll Name City Subject_ID Marks Subject_Name
Student ⋈ No
1 Priya Mumbai S1 90 Physics
2 Ram Chennai S2 60 Chemistry
Result Subject 3 Jayanti Pune S1 75 Physics
4 Kapil Mumbai S3 42 Math
qSince we are concerned with only those tuples in the Subject relation that
pertain to the “Physics” Subject, we do not need to consider those tuples
that do not have Subject_Name = “Physics”.
qBy reducing the number of tuples of the Subject relation that we need to
access, we reduce the size of the intermediate result.
qOur query is now represented by the following relational-algebra expression
which is equivalent to our original algebra expression, but which generates
smaller intermediate relations.

П RollNo, Name (Student ⋈ (Result ⋈ (ϭSubject_Name=’Physics’ (Subject))))

 1. ϭSubject_Name=’Physics’ (Subject)
Transformed Expression Subject_ID Subject_Name

Tree S1 Physics

П RollNo, Name
2. Result ⋈ (ϭSubject_Name=’Physics’ (Subject))

Roll No Subject_ID Marks Subject_Name

⋈
1 S1 90 Physics
⋈ Student 3 S1 75 Physics

3. Student ⋈ (Result ⋈ (ϭSubject_Name=’Physics’ (Subject)))

Result ϭSubject_Name=’Physics’
Roll Name City Subject_ID Marks Subject_Name
No
Subject 1 Priya Mumbai S1 90 Physics
3 Jayanti Pune S1 75 Physics
 Roll Name
Evaluation Plan No
1 Priya
⋈ 3 Jayanti Roll Name
Roll No
No 1 Priya
1
ПRollNo ПRollNo, Name 2 Ram
3 3 Jayanti
4 Kapil
Roll Subject_ Student
No ID
1 S1 ⋈
3 S1 Subject_ID

Roll
No
Subject_ID ПSubject_ID S1

П RollNo, Subject_ID
1 S1 ϭSubject_Name=’Physics’ Subject_ID Subject_Name

2 S2
S1 Physics
3 S1
4 S3 Result Subject
qAn evaluation plan defines exactly what algorithm should be used for each
operation, and how the execution of the operations should be coordinated.
Figure 3 illustrates one possible evaluation plan for the expression.
qAs we have seen, several different algorithms can be used for each
relational operation, giving rise to alternative evaluation plans.
qGiven a relational-algebra expression, it is the job of the query optimizer
to come up with a query-evaluation plan that computes the same result as
the given expression, and is the least-costly way of generating the result
Generation of query-evaluation plans involves three steps:
(1) generating expressions that are logically equivalent to the given ex-
pression
(2) annotating the resultant expressions in alternative ways to generate
alternative query-evaluation plans
(3) estimating the cost of each evaluation plan, and choosing the one whose
estimated cost is the least.
Evaluation of Expression

q For evaluating an expression that carries multiple operations in

it, we can perform the computation of each operation one by
one.
q In the query processing system, we use two methods for
evaluating an expression carrying multiple operations.
q Materialization
q Pipelining
1. Materialization
q In this method, the given expression evaluates one relational operation
at a time.
q Also, each operation is evaluated in an appropriate sequence or order.
q After evaluating all the operations, the outputs are materialized
(stored) in a temporary relation for their subsequent uses. It leads the
materialization method to a disadvantage.
q The disadvantage is that it needs to construct those temporary relations
for materializing the results of the evaluated operations, respectively.
q These temporary relations are written on the disks unless they are small
in size.
 qStore the result of A ⋈ B in a
temporary file.

qStore the result of C ⋈ D in a

temporary file.

qFinally, join the results stored in

temporary files.

overall cost=sum of costs of individual operations + cost of writing

intermediate results to disk, cost of writing results to results to temporary
files and reading them back is quite high.
2. Pipelining
qP i p e l i n i n g i s a n a l te r n ate m e t h o d o r a p p ro a c h to t h e
materialization method.
qIn pipelining, it enables us to evaluate each relational operation
of the expression simultaneously in a pipeline.
qIn this approach, after evaluating one operation, its output is
passed on to the next operation, and the chain continues till all
the relational operations are evaluated thoroughly.
qThus, there is no requirement of storing a temporary relation in
pipelining.
qSuch an advantage of pipelining makes it a better approach as
compared to the approach used in the materialization method.
qEven the costs of reading & writing temporary files is eliminated.

qImplementation of Pipelining :
1. Demand Driven Pipelining
2. Producer Driven Pipelining
1. Demand Driven Pipelining:
§ In the demand-driven pipeline, the system repeatedly makes tuples
request from the operation, which is at the top of the pipeline.
§ Whenever the operation gets the system request for the tuples, initially,
it computes those next tuples which will be returned, and after that, it
returns the requested tuples.
§ The operation repeats the same process each time it receives any tuples
request from the system.
§ In case, the inputs of the operation are not pipelined, then we compute
the next returning tuples from the input relations only.
§ However, the system keeps track of all tuples which have been returned
so far.
§ So, in the demand-driven pipeline, a pipeline is implemented on the
basis of the demand or request of tuples made by the system.
2. Producer Driven Pipelining:
§ In the producer-driven pipeline, the operations do not wait for the
system request for producing the tuples.
§ Instead, the operations are eager to produce such tuples.
§ In the producer-driven pipeline, it models each operation as a
separate thread or process within the system.
§ Each operation at the bottom of the pipeline continuously
generate output records and put them into its output buffer untill
buffer is full.
§ An operation at any other level of pipeline generates output
records when it gets input records from lower part in pipeline untill
its output buffer is full
Demand Driven Pipelining vs Producer Driven Pipelining
Demand Driven Pipeline Producer Driven Pipeline
1. It is similar to pulling data up 1. It is similar to pushing data up
from the top of an operation tree. from the below of an operation tree.

2. Tuples are generated in a lazy 2. Tuples are eagerly generated.

manner.
3. It is easy to implement. 3. It is not so easy to implement a
producer-driven pipeline.
4. It is most commonly used for 4. It is typical so rarely used in the
evaluating an expression. systems. But, it is good for systems
such as parallel processing systems.
Tranformation of Relational Expression

q The first step of the optimizer says to implement such

expressions that are logically equivalent to the given
expression.
q The equivalence rule says that expressions of two forms are
the same or equivalent because both expressions produce
the same outputs on any legal database instance.
q The optimizer uses various equivalence rules on relational-algebra
expressions for transforming the relational expressions.
q For describing each rule, we will use the following symbols:

θ, θ1, θ2 … : Used for denoting the predicates.

L1, L2, L3 … : Used for denoting the list of attributes.

E, E1, E2 …. : Represents the relational-algebra expressions.

Rule 1: Cascade of σ (selection)

q The rule says that we break down conjunctive selection operations into
individual selections, which is called a cascade of σ.
q Conjunctive selections are operations in relational algebra that filter rows
from a relation based on multiple conditions.

σθ1​∧θ2​(E)
​

q This operation selects rows that satisfy both θ₁ and θ₂ simultaneously.

σθ1 ᴧ θ 2 (E) = σθ1 (σθ2 (E))

If we want to select employees who work in the “Sales” department and
earn more than 50,000, then

ϭDepartment=’Sales’ ^ Salary>50000(Employee)

Equivalent expression

ϭDepartment=’Sales’ (ϭ Salary>50000(Employee))
Rule 2: Commutative Rule

q Theta Join (θ) is commutative.

E1 ⋈ θ E2 = E2⋈ θ E1
q This rule states that selections operations are commutative.
σθ1 (σθ2 (E)) = σ θ2 (σθ1 (E))

σSalary >50000 (σDepartment=”Sales” (Employee))

Equivalent expression

σDepartment=”Sales” (σ Salary >50000(Employee))

Rule 3: Cascade of ∏

q This rule states that we only need the final operations in the sequence of
the projection operations, and other operations are omitted. Such a
transformation is referred to as a cascade of ∏.

∏L1 (∏L2 (. . . (∏Ln (E)) . . . )) = ∏L1 (E)

Equivalent expression

∏Emp_Name(σDepartment=’HR’(Employee))
Rule 4: Associative Rule

q This rule states that natural join operations are associative.

(E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3)

Rule 5: Selection with Cartesian product and Joins

q When we have Cartesian product on two tables and a selection

condition on the result, then we can replace it with natural join with
filter condition.

σθ (E1 x E2) = E1 ⋈ θ E2
 σe. Deptid=[Link] (Emp x Dept) = Emp ⋈ e. Deptid=[Link] Dept
Eid Name Salary Deptid Deptid Name
Emp
100 Priya 20000 1 1 Sales
Eid Name Salary Deptid
101 Ram 35000 3 1 Sales
100 Priya 20000 1 102 Kapil 25000 2 1 Sales
Emp x
Dept
101 Ram 35000 3 100 Priya 20000 1 2 Marketing

101 Ram 35000 3 2 Marketing

102 Kapil 25000 2
102 Kapil 25000 2 2 Marketing
Dept
Deptid Name 100 Priya 20000 1 3 Design

1 Sales 101 Ram 35000 3 3 Design

102 Kapil 25000 2 3 Design
2 Marketing
3 Design
Eidv Name Salary Deptid Deptid Name
Emp ⋈ e. Deptid=[Link] Dept 100 Priya 20000 1 1 Sales
Eidv Name Salary Deptid Name 102 Kapil 25000 2 2 Marketing
100 Priya 20000 1 Sales
101 Ram 35000 3 3 Design
102 Kapil 25000 2 Marketing
101 Ram 35000 3 Design σe. Deptid=[Link] (Emp x Dept)
Rule 6: Distributive Selection Operation over theta join

q When all the columns of select conditions have only one table, then we
can re-write selection with theta join as below:

σθ0 (E1 ⋈ θ E2) = (σθ0 (E1)) ⋈ θ E2

σSalary=25000 (Emp ⋈ e. Deptid=[Link] Dept) = (σSalary=25000Emp) ⋈ e. Deptid=[Link]

σSalary=25000 (Emp ⋈ e. Deptid=[Link] Dept) = σSalary=25000(Emp) ⋈ e. Deptid=[Link]

Emp Emp ⋈ e. Deptid=[Link] Dept

Eid Name Salary Deptid Eid Name Salary Deptid Name

100 Priya 20000 1 100 Priya 20000 1 Sales

102 Kapil 25000 2 Marketing
101 Ram 35000 3
101 Ram 35000 3 Design
102 Kapil 25000 2

Dept
Deptid Name Eid Name Salary Deptid Name
102 Kapil 25000 2 Marketing
1 Sales
2 Marketing σSalary=25000 (Emp ⋈ e. Deptid=[Link] Dept)
3 Design

σSalary=25000 (Emp ) σSalary=25000(Emp) ⋈ e. Deptid=[Link]

Eid Name Salary Deptid Eid Name Salary Deptid Name
102 Kapil 25000 2 Marketing
102 Kapil 25000 2
Rule 7: Distribution of the projection operation over the union operation.

q This rule states that we can distribute the projection operation on the
union operation for the given expressions.

∏L (E1 υ E2) = (∏L (E1)) υ (∏L (E2))

Rule 8: The union and intersection set operations are commutative

E1 υ E2 = E2 υ E1

E1 ꓵ E2 = E2 ꓵ E1
Rule 9: The union and intersection set operations are associative.

(E1 υ E2) υ E3 = E1 υ (E2 υ E3)

(E1 ꓵ E2) ꓵ E3 = E1 ꓵ (E2 ꓵ E3)

Find Equivalence expression for the below algebric expression
Example on nested loop join:

Number of records of Student =nstudent= 5000

Number of blocks of Student =bstudent= 100
Number of records of Takes =ntakes= 10000
Number of blocks of Takes =btakes= 400

Calculate worst case and best case block transfer for

nested join operation on Student and Takes Relation.
Outer Relation : r = Student(br=100)

Inner Relation: s= Takes (bs=400)

Total Pairs= nr * ns= 5000 * 10000= 50000000

Worst Case:

• Block Transfers= nr * bs + br = 5000 * 400 + 100

=2000100

• Total Seek = nr +br = 5000 +100 = 5100

Best Case:

Block Transfers: br + bs = 100 + 400 = 500

Total Seeks = 2
Problem:
Let relation r1(A,B,C) and r2(C, D, E) have following properties:
r1 has 20000 tuples, r2 has 45000 tuples , 25 tuples of r1 fit in one block
and 30 tuples of r2 fit in one block, Estimate number of block transfer and
seeks required using nested loop join.
Number of block calculation:
nr=20000
ns=45000
br=20000/25=800
bs=45000/30=1500

Worst Case:

• Block Transfers= nr * bs + br =20000 * 1500 + 800

=30000800

• Total Seek = nr +br = 45000+800= 45800

Best Case:

Block Transfers: br + bs = 800+1500= 2300

Total Seeks = 2
 Module 1
Query Processing &
Optimization
Course: Advance Data Mangemnet Technologies
Class: TE IT
Faculty Name: Prof. R. S. More
What is a query ?
• A "query" refers to a request for data or
information from a database.
• It is a way to retrieve specific data by specifying
criteria or conditions that the desired data must
meet.
• Queries are typically written in a query language,
such as SQL
What is a query Processing ?
• Query processing refers to the range of activities involved in
extracting data from a database.
• Query Processing includes translations of high-level
Queries into low-level expressions that can be used at the
physical level of the file system, query optimization, and
actual execution of the query to get the actual result.
• Query processing refers to the series of steps that a database
management system (DBMS) takes to execute a query and
return the desired results.
• High-level queries are converted into low-level expressions
during query processing.
 Steps in query processing:

1. Parsing & Translation

2. Optimization

3. Evaluation
Step 1 - Parsing & Translation

a. Syntax Checking:
Ø The parser examines the query to ensure it follows the syntax rules of
the query language (e.g., SQL).
Ø If there are syntax errors, the parser will generate error messages and
halt further processing until the errors are corrected.
b. Semantic Checking:
Ø The parser verifies that the query is semantically correct.
Ø This involves checking that the tables and columns referenced in the
query exist in the database schema, that the operations make sense ,
and that the user has the necessary permissions to access the data.
Step 1 - Parsing & Translation
c. Parse Tree Construction:
Ø The parser constructs a parse tree, a hierarchical
representation of the query's structure.
Ø Each node in the parse tree represents a component
of the query, such as a table, column, or operation
(e.g., selection, projection, join).

e.g

SELECT salary FROM instructor WHERE salary > 75000;

Step 2 - Parsing & Translation

d. Translation to Relational Algebra:

Ø The parse tree is translated into a relational-algebra expression.

Ø Relational algebra provides a formal framework for query operations and
is the foundation for query optimization and execution.
Ø Relational-algebra expressions consist of a series of operations (such as
selection, projection, join, union, etc.) that define how to retrieve and
manipulate the data.e.g

• σ(salary < 75000) (π(salary) (instructor))

• π(salary) (σ(salary < 75000) (instructor))

Step 2 - Optimization
Ø It is a process in which multiple query execution plan for satisfying a query are
examined and most efficient query plan is satisfied for execution.
Ø Here, DMBS picks up the most efficient evaluation plan based on the cost each plan
has. The aim here is to minimize the query evaluation time.
Ø The optimizer also evaluates the usage of index present in the table and the columns
being used.
Ø It also finds out the best order of subqueries to be executed so as to ensure only the
best of the plans gets executed.
Ø In short, for any query, there are multiple evaluation plans to execute it.
Choosing the one which costs the least is called Query Optimization in DBMS.
Ø Some of the factors weighed in by the optimizer to calculate the cost of a query
evaluation plan is:
1. CPU time
2. Number of tuples to be scanned
3. Disk access time
4. number of operations
Query Evaluation Plan
Ø with addition to the relational algebra translation, it is required to annotate the translated
relational algebra expression with the instructions used for specifying and evaluating each
operation. Thus, after translating the user query, the system executes a query evaluation
plan.
Query Evaluation Plan:
Ø In order to fully evaluate a query, the system needs to construct a query evaluation plan.
Ø The annotations in the evaluation plan may refer to the algorithms to be used for the
particular index or the specific operations.
Ø Such relational algebra with annotations is referred to as Evaluation Primitives. The
evaluation primitives carry the instructions needed for the evaluation of the operation.
Ø Thus, a query evaluation plan defines a sequence of primitive operations used for
evaluating a query. The query evaluation plan is also referred to as the query execution
plan.
Ø A query execution engine is responsible for generating the output of the given query. It
takes the query execution plan, executes it, and finally makes the output for the user
query.
3. Evaluation

Ø The query-execution engine executes the query plan.

Ø Intermediate results are processed according to the plan, using the
specified algorithms and indices.
Ø Final results are retrieved and formatted for output.
 Measure Of Query Cost
Ø Cost of query evaluation can be measured in terms of
resources
- disk access time, CPU time to execute query and
cost of communication.
Ø Disk Cost can be estimated as:
1. Number of seek(average-seek-cost)
2. Number of blocks read(average-block-read-cost)
3. Number of blocks written(average-block-write-
cost)
Assumptions:

- we are going to consider only on two cost measures i.e

number of block transfer and number of block seeks.
- write cost and read cost is same.
- data must be read from disk initially.

tT- average time to transfer one block of data.

tS- Average block access time
Cost for b Block transfers plus S seeks:

b*tT+ S*tS

Here , tT & tS depends on where the data is been stored:

e.g
For 4KB block size:
High End Magenetic Disk: tS=4Sec and tT=0.1 msec.
SDD: tS= 20-90microsec and tT=2-10 microsec.
 Selection Operation
• Selection Operation is like a File Scan Operation.
§ It is lowest-level operator to access data.
§ It is like a search algorithm that locates and retrieve
records that fulfill a selection condition.
§ It allows an entire relation to be read in those cases
where relation is stored in single ,dedictaed file.

• An attribute or set of attributes used to lookup records in file is

called a search key.
Selection Operation: A1(Linear Search)
Select * from EMP where Salary = 30000;
Ø The system scans each file blocks and test all the
records to see whether they satisfy the selection
condition.
Ø Linear Search can be applied regardless of:
- selection condition.
- ordering of records in the file.
- availability of indices
Ø An initial seek is required to access first block of
the file. If the blocks are not stored in
contiguious memory then an extra seek may be
required.
Ø br- no. of blocks in file and 1 seek operation.

COST= tS+br*tT
Selection Operation: A1(Linear Search, Equality on Key)

Ø If selection is on key attribute then search stops

on finding the records.
Select * from EMP where Empid= 1003;

Average Cost = tS+(br/2)*tT

Worst case Cost = tS+br*tT
 Nested Loop Join Operation
Select * from Employee e inner join Dept d on [Link]=[Link] ;

Deptid DName
br1
1 Purchase
bs1
2 Sales

br2 3 Production

4 Marketing
bs2
5 Finance
br3
br1 br1

bs1 bs2

Main Memory Main Memory

br1 br1

bs1 bs2

Main Memory Main Memory

Select * from Employee e inner join Dept d on [Link]=[Link] ;

Empid Name Salary Deptid DName

1001 Jaya 40000 05 Marketing
1002 Akshata 50000 04 Finance
1003 Vinayak 40000 03 Production
1004 Surabhi 30000 03 Production
1005 Jayanti 10000 01 Purchase
1006 Pramod 30000 01 Purchase
1007 Neha 20000 01 Purchase
1008 Nilesh 30000 02 Sales
1009 Mayur 50000 02 Sales
 Nested Loop Join Operation
for each tuple Rt in r do begin
for each tuple St in s do begin
test pair(Rt , St) to test if they satisfy the given join condition
if they do add [Link] to the result
end
end

r- Outer Relation
s- Inner Relation
[Link] - the tuple constructed by concatenating the attribute values of tuples Rt , St
 Nested Loop Join Operation
• Nested Loop Join requires no indices.
• It is expensive as it checks each pair of tuples in two Relations.
• The cost of nested loop join algorithm will be:
§ The number of pairs to be considered nr*ns.
§ where nr denotes the number of tuples in relation R and ns
are number of tuples in relation S
§ For each record in R a complete scan on S is performed.
 Performance of Nested Loop Join Operation
Worst Case:
• The buffer can hold only one block of each relation.
• Total block transfer = nr * bs + br
where bs and br denotes number of blocks containing tuples of R and S.

• Only one seek for each scan on inner relation S since it is read
sequentially and total br seeks to read R.
Total Seek = nr +br
• Total Cost= Block transfer + Total Seek = (nr * bs + br )+ (nr +br)
 Performance of Nested Loop Join Operation
Best Case:
• If there is enough space for both the relation to fit
simultaneously in memory then each block would have to be
read only once.
Cost will be: br + bs along with two seek
Example:

Number of records of Student =nstudent= 5000

Number of blocks of Student =bstudent= 100
Number of records of Takes =ntakes= 10000
Number of blocks of Takes =btakes= 400

Calculate worst case and best case block transfer for

nested join operation on Student and Takes Relation.
Outer Relation : r = Student(br=100)

Inner Relation: s= Takes (bs=400)

Total Pairs= nr * ns= 5000 * 10000= 50000000

Worst Case:

• Block Transfers= nr * bs + br = 5000 * 400 + 100

=2000100

• Total Seek = nr +br = 5000 +100 = 5100

Best Case:

Block Transfers: br + bs = 100 + 400 = 500

Total Seeks = 2
 Sorting Operation
Sorting data is very important in database systems for two main reasons:

1. SQL Queries specifies output to be ordered

2. Efficient Data Processing

o Many database operations, like joining tables, work much faster if the
data is sorted first. For example, if you have two lists of customers and
their orders, finding which orders belong to which customers is much
quicker if both lists are sorted.

In simple terms, sorting helps in making sure that the data is shown in the desired order
and makes certain operations faster and more efficient.
 Sorting Operation
• We can sort a relation by building an index on the sort key, and then using
that index to read the relation in sorted order.
• However, such a process orders the relation only logically, through an index,
rather than physically.
• Hence, the reading of tuples in the sorted order may lead to a disk access
(disk seek plus block transfer) for each record, which can be very expensive,
since the number of records can be much larger than the number of blocks.
• For this reason, it may be desirable to order the records physically.
Example
Imagine you have a table of students with columns for StudentID, Name,
and Grade. If you want to read the data sorted by Grade, you can create an
index on the Grade column.
 Sorting Operation

• When dealing with large datasets that don't fit entirely into the main
memory, special sorting techniques are required. These techniques
are often referred to as external sorting.
• External sorting methods are designed to efficiently handle data that
must be stored on external storage, like hard drives, due to its size.
• One of the most common and effective external sorting algorithms
is external merge sort.
 External Merge Sort Algorithm

1. Divide the Data into Chunks:

§ Split the dataset into smaller chunks that can fit into the main
memory. Each chunk is called a run.
§ For example, if you have a dataset of 100GB and your memory
can handle 1GB at a time, you would divide the dataset into
100 chunks of 1GB each.
i = 0;
repeat
§ read M blocks of the relation, or the rest of the relation,
whichever is smaller;
§ sort the in-memory part of the relation;
§ write the sorted data to run file Ri ;
§ i = i + 1;
until the end of the relation

M denote the number of blocks in the main-memory buffer available for sorting,
 External Merge Sort Algorithm

2. Sort Each Chunk in Memory:

§ Load each chunk into memory one by one.

§ Use an efficient in-memory sorting algorithm, such as
quicksort, to sort each chunk.
§ Write the sorted chunks back to the disk. Now you have
multiple sorted runs stored on the disk.
read one block of each of the N files Ri into a buffer block in memory;
repeat
§ choose the first tuple (in sort order) among all buffer blocks;
§ write the tuple to the output, and delete it from the buffer block;
§ if the buffer block of any run Ri is empty and not end-of-file(Ri)
§ then read the next block of Ri into the buffer block;
until all input buffer blocks are empty
 External Merge Sort Algorithm
3. Merge the Sorted Runs:

§ Perform a multi-way merge to combine the sorted runs into a

single sorted file.
§ During the merge phase, you use a priority queue (min-heap)
to efficiently merge the chunks.
§ The priority queue helps keep track of the smallest elements
among the runs to form the sorted sequence.
 External Merge Sort - Cost Analysis

The primary cost in external sorting is associated with reading

from and writing to the disk. Here's a breakdown:

1. Initial Run Formation:

Ø I/O Cost: Each block of data is read once and written once.
If the data size is N blocks, the cost is:
2� (N reads + N writes)
 External Merge Sort - Cost Analysis

2. Merge Phase:

Ø I/O Cost: During each merge pass, all data blocks are read from
and written back to disk. If � is the number of runs and � is
the block size that can fit into memory, the number of merge
passes required is approximately :

2N logB M
 External Merge Sort - Cost Analysis

Total Cost = 2N + 2N logB M

Where:

• � is the number of data blocks.

• � is the number of initial runs.
• � is the number of runs that can be merged in memory simultaneously.
 Module 2
Advanced Data Management
Techniques
Course Outcome:

CO2- Apply Sophisticated access Protocol to the Database

Class- TE IT
Subject- ADMT
 Database Security and the DBA
❑ The Database Administrator (DBA) is responsible in managing and securing a
database system.
❑ The DBA’s responsibilities include granting privileges to users who need to
use the system and classifying users and data in accordance with the policy of
the organization.
❑ The DBA has a DBA account in the DBMS, sometimes called a system or
superuser account, which provides powerful capabilities that are not made
available to regular database accounts and users.
❑ DBA-privileged commands include commands for performing the following
types of actions:
1. Account creation:
creates a new account and password for a user or a group of users to enable
access to the DBMS.
2. Privilege granting:
permits the DBA to grant certain privileges to certain accounts.
3. Privilege revocation:
revoke (cancel) certain privileges that were previously given to certain accounts.
4. Security level assignment:
assigning user accounts the appropriate security clearance level.
Advanced Database Access protocols:

A. Discretionary Access Control

B. Mandatory Access Control and Role Based Access
Control
C. Remote Database Access protocol.
Discretionary Access Control (DAC)
❑ Discretionary Access Control (DAC) is a security mechanism
that allows users to control access to their own data based
on their discretion(own choice).
❑ In a database system, DAC is implemented by allowing users
to grant and revoke privileges to other users.
❑ Types of Discretionary Privileges

1. Account level
2. Relation (or table) level
1. Account Level Privileges
❑ Account-level privileges are permissions granted to a user
account, enabling the account to perform various actions
within the database management system (DBMS).
❑ These privileges control what an account can and cannot do
and apply generally to the account rather than to specific
database objects.
 Account-Level Privileges:
1. CREATE SCHEMA/TABLE:
Ability to create schemas or tables.A schema is a collection of database
objects, including tables, views, and procedures.
2. CREATE VIEW:
Ability to create views.A view is a virtual table based on the result-set of
an SQL query
3. ALTER:
Modify schemas by adding/removing attributes.
4. DROP:
Delete relations or views.
5. MODIFY:
Insert, delete, or update tuples.
6. SELECT:
Retrieve information using SELECT queries.
❑ Suppose that the DBA creates four accounts—A1, A2, A3, and A4—and
wants only A1 to be able to create base relations. To do this, the DBA
must issue the following
GRANT command in SQL:
GRANT CREATETAB TO A1;

❑ The CREATETAB (create table) privilege gives account A1 the capability

to create new database tables (base relations) and is hence an account
privilege.
2. Relational Level Privileges

❑ DBA can control privilege to access each relation/view in

database.
❑ Relation-level privileges specify the individual tables and
views on which each type of command can be applied for
each user.
❑ The granting and revoking of privileges generally follow an
authorization model for discretionary privileges known as the access
matrix model,
❑ The rows of aaccess matrix M represent subjects (users, accounts,
programs) and the columns represent objects (relations, records,
columns, views, operations).
❑ Each position M(i, j) in the matrix represents the types of privileges
(read, write, update) that subject i holds on object j.
DAC ACCESS MATRIX EXAMPLE
❑ To control the granting and revoking of relation privileges, each relation
R in a database is assigned an owner account, which is typically the
account that was used when the relation was created in the first place.
❑ The owner of a relation is given all privileges on that relation.
❑ In SQL2, the DBA can assign an owner to a whole schema by creating
the schema and associating the appropriate authorization identifier with
that schema, using the CREATE SCHEMA command.
❑ The owner account holder can pass privileges on any of the owned
relations to other users by granting privileges to their accounts.
In SQL, the following types of privileges can be granted on each individual relation R:
1. SELECT (retrieval or read) privilege on R: In SQL, this gives the account the
privilege to use the SELECT statement to retrieve tuples from R.
2. Modification privileges on R.: This gives the account the capability to modify the
tuples of R. In SQL, this includes three privileges: UPDATE, DELETE, and INSERT.
3. References privilege on R: This gives the account the capability to reference (or
refer to) a relation R when specifying integrity constraints. This privilege can also
be restricted to specific attributes of R.
❑ suppose that account A1 wants to grant to account A2 the privilege to
insert and delete tuples in both of these relations.
❑ However, A1 does not want A2 to be able to propagate these privileges
to additional accounts. A1 can issue the following command:

GRANT INSERT, DELETE ON EMPLOYEE, DEPARTMENT TO A2;

❑ Account A2 cannot grant INSERT and DELETE privileges on the EMPLOYEE

and DEPARTMENT tables because A2 was not given the GRANT OPTION
❑ Now, Suppose that A1 wants to allow account A3 to retrieve information
from either of the two tables and also to be able to propagate the SELECT
privilege to other accounts. A1 can issue the following command:

GRANT SELECT ON EMPLOYEE, DEPARTMENT TO A3 WITH GRANT OPTION;

❑ The clause WITH GRANT OPTION means that A3 can now propagate the
privilege to other accounts by using GRANT.

GRANT SELECT ON EMPLOYEE TO A4;

❑ suppose that A1 decides to revoke the SELECT privilege on the EMPLOYEE
relation from A3; A1 then can issue this command:

REVOKE SELECT ON EMPLOYEE FROM A3;

❑ The DBMS must now revoke the SELECT privilege on EMPLOYEE from A3,
and it must also automatically revoke the SELECT privilege on EMPLOYEE
from A4. This is because A3 granted that privilege to A4, but A3 does not
have the privilege any more.
❑ Finally, suppose that A1 wants to allow A4 to update only the Salary
attribute of EMPLOYEE; A1 can then issue the following command:
GRANT UPDATE ON EMPLOYEE (Salary) TO A4;

❑ The UPDATE and INSERT privileges can specify particular attributes that
may be updated or inserted in a relation. Other privileges (SELECT,
DELETE) are not attribute specific
Advantages
❑ User Friendly:- Managing data and permissions is easier with DAC.
❑ Flexible:- While working, often a need to share data with co-workers
comes up. DAC system allows any user with access to certain information
to grant access to others as well, hence making the working process
smooth.
❑ Less Headache for Administration:- DAC doesn’t require regular
maintenance does not take much time. Sharing of data is much easier as
the administration does not need to interfere whenever a piece of
information is needed to be shared with a user.
Disadvantages of DAC:-
❑ Less Secure System:- As access can be given from one person to another,
data is not very well secured under DAC. Thus, it is not much feasible for
the administration to overview Access Control List(ACL) now and then,
which may lead to leakage of information to someone outside the
organization.
❑ Hard to keep track of data:- As the DAC system is not centralized, the only
way administration can monitor data flow is by going through ACL. Thich is
only convenient in the case of a small organization where employees are
fewer.
Mandatory Access Control (MAC)

❑ Mandatory Access Control (MAC) is a security approach that adds an

extra layer of protection by classifying data and users based on security
levels.
❑ This system is especially important for government, military, and other
highly sensitive environments.
❑ In MAC, both data (like tables or files) and users are given security labels
such as Top Secret (TS), Secret (S), Confidential (C), and Unclassified (U).
❑ Users can only access data if their security level is equal to or higher than
the data they are trying to access.
❑ For example, someone with Secret clearance can read data classified as
Secret, Confidential, or Unclassified, but not Top Secret.
❑ There are two main rules in MAC.
1. The first rule, called the "simple security property," ensures that a
user cannot read data at a higher security level than their own.
2. The second rule, known as the "star property," prevents a user
from writing data to a lower security level.
❑ This prevents information from leaking to less secure areas.
❑ For instance, someone with Top Secret clearance cannot write information
to a Confidential or Unclassified file, which helps prevent accidental or
malicious information leaks.
❑ To integrate multilevel security into the relational database model, data
objects like attribute values and tuples are assigned security
classifications.
❑ Each attribute (A) is paired with a classification attribute (C) in the schema,
and each attribute value in a tuple has a corresponding security
classification.
❑ Additionally, some models add a tuple classification attribute (TC) to
represent the security level of the entire tuple. This approach is known as
the multilevel model because it supports multiple security levels.
 A multilevel relation schema with 𝑛attributes looks like this:

❑ Attributes (A1, A2, ...): Data attributes.

❑ Classifications (C1, C2, ...): Security classifications for each
attribute.
❑ Tuple Classification (TC): Represents the highest classification
among the attribute classifications in a tuple.
❑ Assume that the Name attribute is the apparent key, and consider the
query
SELECT * FROM EMPLOYEE
❑ A user with security clearance S would see the same relation shown in
Figure , since all tuple classifications are less than or equal to S.
❑ However, a user with security clearance C would not be allowed to see the
values for Salary of ‘Brown’ and Job_performance of ‘Smith’, since they
have higher classification.

NULL C
NULL C GOOD C
❑ For a user with security clearance U, the filtering allows only the Name
attribute of ‘Smith’ to appear, with all the other attributes appearing as
null (C). Thus, filtering introduces null values for attribute values whose
security classification is higher than the user’s security clearance.
Advantages
❑ High-level data protection:
With MAC, one can be sure that their most confidential data is well
protected and leaves no room for any leakage.
❑ Centralized Information: Once data is set in a category it cannot be
de-categorized by anyone other than the head administrator. This makes the
whole system centralized and under the control of only one authority.
❑ Privacy: Data is set manually by an administrator. No one other than admin
can make changes in category or list of users' accesses to any category. It can
be updated only by admin.
Disadvantages

❑ Careful Setting-Up Process:

Sometimes a piece of information needs to be shared among
co-workers in the same organization but MAC restricts anyone to do so.
Hence MAC must be set up with good care
❑ Regular Update Required:
It requires regular updating when new data is added or old data is
deleted.
Role Based Access Control (RBAC)

❑ RBAC assigns permissions to roles, and users are then assigned to these
roles.
❑ Roles can be created and destroyed with CREATE ROLE and DESTROY
ROLE commands.
❑ The GRANT and REVOKE commands, can then be used to assign and
revoke privileges from roles, as well as for individual users when needed
❑ For instance, in a medical organization, the different roles of users may
include those such as doctor, nurse, attendant, nurse, patients, etc.
❑ Obviously, these members require different levels of access in order to
perform their functions
❑ Multiple individuals can be assigned to each role.
❑ The role hierarchy in RBAC is a natural way to organize roles to reflect the
organization’s lines of authority and responsibility.
❑ By convention, junior roles at the bottom are connected to progressively
senior roles as one moves up the hierarchy.
❑ If a user has one role, the user automatically has roles lower in the
hierarchy.
❑ Role hierarchy can be implemented in the following manner:

GRANT ROLE full_time TO Employee_type1

GRANT ROLE intern TO employee_type2

❑ Another important aspect is identity management, which ensures each

person has a unique identity within the system.
❑ This involves authenticating users and managing their access to
information.
Advantages
❑ Simplified Management:
▪ Instead of assigning permissions to each user individually, you assign them to
roles. Users then inherit permissions based on their role.
▪ Makes it easier to manage large numbers of users since you only need to
update roles when changes are required.
❑ Improved Security:
▪ Permissions are managed centrally through roles, ensuring consistent access
control policies across the organization.
▪ Reduces the risk of errors and unauthorized access, as users can only perform
actions permitted by their role.
❑ Flexibility and Scalability:
▪ Roles can be easily created, modified, or deleted to match changes in the
organization.
▪ As your organization grows or changes, RBAC adapts without needing to
overhaul the entire access control system.
DAC vs MAC vs RBAC
DAC MAC RBAC
Access controlled by resource Access based on security Access based on roles
Definition owners clearance and labels assigned to users

Control Decentralized (owner-defined Centralized Centralized (roles and

policies) (administrator-defined permissions defined by
policies) admin)
Flexibility High Low Moderate to High

Security Level Moderate High High

Application Corporate environments, Military, government, sensitive Large enterprises,

collaborative projects data environments complex organizational
structures
Remote Database Access Control (RDAC)
❑ A remote database access protocol is a set of rules that allows users and
applications to connect to and interact with a database located on a remote
server over a network.
❑ It follows a client-server architecture, where the client (user or application)
sends requests to the server (remote database), which then processes these
requests and returns the results.
❑ Common communication protocols like HTTP/HTTPS and TCP/IP ensure
reliable data transmission.
❑ Authentication and authorization steps verify the user’s identity and
permissions.
❑ SQL queries or stored procedures are used to request data, and the
results are sent back to the client.
❑ Data encryption (e.g., SSL/TLS) protects sensitive information during
transmission.
❑ This protocol provides secure, flexible, and efficient remote access to
databases, making it easy for users to retrieve and manage data from
anywhere with an internet connection.
Advantages
1. Accessibility:
Users can access the database from anywhere with an internet connection.

2. Scalability:
Supports multiple users and applications simultaneously without
compromising performance.

3. Security:
Encryption and secure authentication methods protect data during
remote access.

4. Flexibility:
Compatible with various client applications and programming languages
through standard interfaces like ODBC and JDBC.
Advance Database Model

Temporal Database Model

Mobile Database Model
Spatial Database Model
 1. Temporal Database Model
❑ A temporal database stores data relating to time instances.
❑ It offers temporal data types and stores information relating to past,
present and future time.
❑ The temporal database has three major notions or attributes.
1. Valid time: the time period during which a fact is true in the real
world.
2. Transaction time: the time period during which a fact stored in the
database was known
3. Decision Time:The time at which the decision is made about the fact.
Types of Temporal Relation

1. Uni-Temporal Relation: The relation which is associated with valid or

transaction time is called Uni-Temporal relation. It is related to only one time.

2. Bi-Temporal Relation: The relation which is associated with both valid time
and transaction time is called a Bi-Temporal relation. Valid time has two parts
namely start time and end time, similar in the case of transaction time.

3. Tri-Temporal Relation: The relation which is associated with three aspects

of time namely Valid time, Transaction time, and Decision time called as
Tri-Temporal relation.
1. Temporal Data Definition Language:

❑ VALIDTIME and TRANSACTIONTIME are two distinct dimensions of time

used to track and manage data changes.
❑ VALIDTIME refers to the time period during which a fact or data item is
true in the real world. It represents the validity of the data.
❑ In a database schema, valid time is often represented by columns like
ValidFrom and ValidTo, which denote the start and end dates (or
timestamps) during which the data is valid.
❑ TRANSACTIONTIME refers to the time period during which a fact or data
item is stored in the database.
❑ In a database schema, transaction time is often represented by
columns like TransactionStart and TransactionEnd, which denote the
time period during which the data was valid in the database.
In TimeDB, a bitemporal table can be created the following way:

CREATE TABLE Employees (EmpID INTEGER, Name CHAR(30), Department

CHAR(40), Salary INTEGER) AS VALIDTIME AND TRANSACTIONTIME;

EmpID Name Department Salary ValidFrom ValidTo TransactionStart TransactionEnd

□ ValidFrom: The start date when the employee's record is valid in the real world.
□ ValidTo: The end date when the employee's record is valid in the real world.
□ TransactionStart: The timestamp when the record was inserted or last modified in the
database.
□ TransactionEnd: The timestamp when the record was deleted or superseded (NULL if still
active).
1. Temporal DML:

VALIDTIME PERIOD '1985-2023'

INSERT INTO Employees VALUES (10, 'ABC', 'Research', 11000);

EmpID Name Department Salary ValidFrom ValidTo TransactionStart TransactionEnd

10 ABC Research 11000 01-01-1985 01-01-2023 Current_TimeStamp NULL

Record is not deleted or

suspended
when the record was inserted
or last modified in the
database
Challenges of Temporal Databases
1. Data Storage: In temporal databases, each version of the data needs to be stored
separately. As a result, storing the data in temporal databases requires more
storage as compared to storing data in non-temporal databases.
2. Schema Design: The temporal database schema must accommodate the time
dimension. Creating such a schema is more difficult than creating a schema for
non-temporal databases.
3. Query Processing: Processing the query in temporal databases is slower than
processing the query in non-temporal databases due to the additional complexity
of managing temporal data.
 2. Spatial Database Model

❑ Spatial databases are specialized databases designed to manage and query

data related to objects in multidimensional spaces.
❑ These databases are essential for applications that deal with geographic or
spatial information, such as maps, weather data, and more.
❑ The objects in these databases can be anything from points, like the location
of a landmark, to complex polygons representing areas like cities or
countries.
Spatial Data Types:

1. Point: Represent specific locations on

the map, like cities or landmarks.
2. Line: Represents a sequence of points
connected by straight lines, such as
roads or rivers.
3. Polygon: Represent closed areas or
regions, like lakes, parks, or
boundaries of districts.
Spatial Query Language:
Spatial databases extend SQL (Structured Query Language) to include spatial
queries. For example:
SELECT * FROM Cities WHERE ST_Distance(location, 'POINT(10 10)') < 100;
This query finds all cities within 100 units of distance from a specific point.
Application of Spatial Database:

1. Geographic Information Systems (GIS):

GIS applications use spatial databases to store, manipulate, and analyze geographic data,
allowing users to visualize data on maps, perform spatial analysis, and make decisions based
on spatial information.

[Link] Planning:
Urban planners use spatial databases to model city layouts, analyze traffic patterns, and
plan infrastructure projects. For example, they can determine the best location for a new
park by analyzing the population density and proximity to residential areas.

[Link] Systems:

Navigation systems rely on spatial databases to store map data, calculate routes, and
provide directions. The system queries the spatial database to find the shortest path
between two points, taking into account road types, traffic, and other spatial factors.
 3. Mobile Database Model
❑ Traditionally, large-scale databases were centralized, but this changed with
the rise of distributed applications. Modern technology trends have further
transformed database systems due to several key developments:
1. Increased Use of Portable Devices
2. Affordable Wireless networks
3. Enhanced Mobility
❑ Mobile databases are designed to be used on handheld devices like smartphones and
tablets.
❑ These databases allow users to access, update, and synchronize data with a central
database while users are travelling.
❑ This is especially useful for people who need to work away from their offices, such as
delivery drivers, salespeople, and emergency responders.
❑ Example:

□ Imagine a delivery driver using a mobile database on their handheld device.

□ Throughout the day, they collect customer signatures after deliveries.
□ At the end of the day, they connect their device to the internet and
synchronize the collected data with the company's central database.
□ In a mobile-computing environment,
the concept of a "cell" refers to the
geographical area covered by a
mobile support station.
□ Each mobile support station manages
mobile hosts within its designated
cell, handling tasks like routing and
maintaining communication with the
wired network.
□ As mobile hosts move from one cell
to another, control needs to be
transferred from one support station
to the next.
Challenges in Mobile Databases
1. Dynamic Locations: Devices move, making it difficult to know their exact
location at all times, which can complicate data processing.
For example, If a traveller information system provides data on
hotels, roadside services, etc. to motorists; queries about services
that are ahead on the current route must be processed based on
knowledge of the user's location, direction of motion, and speed.
2. Energy Constraints: Mobile devices rely on batteries, so energy efficiency
is crucial.
 Module-3
Distributed Database System
Course Outcome:
CO3 - Implement Distributed Database

Subject-ADMT
Class-TE IT
What is Distributed Database System?

q A Distributed Database System is a union of two important

techonologies- Database Management System and Computer
Newtork.

q DBMS involves centtalization while computer Network technology

involves decentralization.

q A Distributed Database System is a multiple, logically related

database system physically distributed across several sites using a
computer network that is normally under the control of a central site
q Site 1 and Site 3 has their own local database as well as their own DMS
software. In addition they are part of distribute database system which
allow their user to access the local database as well as distributed database.
q Site 2 does not have local database and therefore this users are directly
access Distributed Database.
q to communicate with distributed database a site requires a copy of
distributed DBMS as well as global data dictionary.
q DC is software component that has information of all the nodes in the
network.
Features

1. Data is stored at number of sites and each site is logically

independent single computer.
2. Sites are interconnected by a high speed network rather than
multiprocessor configuration
3. Each site is a database system in its own right, running its own DBMS.
4. The whole distributed database system is logically a single database .
5. The distributed database system has full functionality of a DBMS.
Types of Distributed Database System:

Ø Homogeneous Distributed Database System

Ø Heterogenous Distributed Database System.
 1. Homogeneous Distributed Database System
q A homogeneous distributed database system is one in which all the
participating databases are identical in terms of software, data structures,
and the operating system.
q Each database in the network operates under the same database
management system (DBMS) and follows the same schema, making it
easier to manage and maintain.
q The uniformity across all nodes ensures consistency and simplifies data
integration and querying across the distributed system.
q Consider a global retail chain that uses a homogeneous distributed
database system. Each store in different locations (e.g., New York, London,
Tokyo) has its own database. However, all these databases run on the same
DBMS (e.g., MySQL), use the same data schema (e.g., customer records,
sales transactions), and have the same data management procedures.

q When a customer makes a purchase in New York, the local database in New
York stores the transaction. However, because the databases are
homogeneous, data from the New York store can be easily integrated with
data from London and Tokyo for global analytics and reporting.
Benefits of Homogeneous Distributed Databases:
q Consistency: All nodes follow the same rules, ensuring consistent
data across the entire system.
q Ease of Administration: Uniform systems simplify tasks such as
updates, backups, and recovery.
q Simplified Development: Developers can build applications with
the assumption that the underlying database is consistent across
all locations.
 2. Heterogeneous Distributed Database System
q A heterogeneous distributed database system is one in which the
participating databases can be different in terms of the DBMS software,
data models, or hardware platforms.
q This means that each node (or site) in the distributed system may use a
different DBMS (e.g., Oracle, MySQL, SQL Server), and may even run on
different operating systems (e.g., Windows, Linux) or hardware
architectures.
q Despite these differences, the system is designed to work together to
provide a unified view of the data.
q Consider a multinational corporation that has different departments using
different database systems due to historical or functional reasons. For
example:
q Finance Department: Uses Oracle for its robust transaction processing
capabilities.
q Human Resources Department: Uses Microsoft SQL Server to manage
employee records.
q Sales Department: Uses MySQL for its ease of use and cost-effectiveness.
q Supply Chain Department: Uses a NoSQL database like MongoDB to
handle large amounts of unstructured data from various suppliers.
q Each department’s database operates independently, but the corporation
needs to combine and analyze data from all these systems to make informed
business decisions. A heterogeneous distributed database system enables this
integration, even though the underlying databases are different.
Benefits of Heterogeneous Distributed Databases:
q Flexibility: Allows each department or location to use the database
system that best suits its specific needs.
q Data Integration: Enables the combination of data from different
sources, providing a comprehensive view across the organization.
q Scalability: New systems and databases can be added without
needing to standardize everything, allowing for growth and
adaptation over time.
 Drawbacks:

q Complexity in Management: Managing a heterogeneous system

requires specialized middleware and careful coordination to ensure
everything works together.
q Query Processing: Queries need to be adapted to each DBMS, which
can complicate processing and impact performance.
q Consistency Issues: Maintaining data consistency across different
systems can be challenging, especially if they follow different
consistency models.
Architecture of Distributed Database System:
1. Client Server Architecture qIn this model, the database services are
provided by a central server, while clients (users
or applications) request services over the
network.
qThe server functions primarily encompass data
management, query processing, optimization
and transaction management.
qClient functions include mainly user interface.
However, they have some functions like
consistency checking and transaction
management.
qThe two different client - server architecture
are
qSingle Server Multiple Client
qMultiple Server Multiple Client
 4- levels of schema
2. Peer-Peer Architecture
user view of data

q In a Peer-to-Peer (P2P) architecture,

each node in the distributed database
system functions as both a client and
a server. the global
logical view
q There is no central authority or server, logical data of data.
meaning all nodes have equal organization
responsibilities in terms of storing
data, processing queries, and
participating in transactions.
q This decentralized model has high
Fault Tolerance: The system remains
operational even if multiple nodes fail.
q Easy to add more nodes to the system,
Physical data
enhancing capacity and performance
organization
3. Multi-Tier Architecture

qIt is a design approach in distributed databases where the system is divided

into layers (or tiers), each with a specific responsibility.
qThis separation of concerns allows for modularity, scalability, and easier
management.
qTypically, the architecture is divided into three main tiers: the presentation tier,
the application (or logic) tier, and the data tier.
qStructure:
qPresentation Tier: The user interface or client application.
qApplication Tier: The business logic and processing layer.
qData Tier: The distributed database nodes.
 Fragmentation
q The process of dividing the database into a smaller multiple parts is
called as fragmentation.
q These fragments may be stored at different locations.
q The data fragmentation process should be carrried out in such a way
that the reconstruction of original database from the fragments is
possible.
Types of Fragmentation

1. Horizontal Fragmentation
a. Primary Horizontal Fragmentation
b. Derived Horizontal Fragmentation

2. Vertical Fragmentation
3. Hybrid Fragmentation
1. Horizontal Fragmentation:

q Horizontal fragmentation refers to the process of dividing a table

horizontally by assigning each row (or a group of rows) of relation to
one or more fragments.
q These fragments can then be assigned to different sites in the
distributed system. Some of the rows or tuples of the table are placed
in one system and the rest are placed in other systems.
q The rows that belong to the horizontal fragments are specified by a
condition on one or more attributes of the relation
In relational algebra horizontal fragmentation on table T, can be
represented as follows:

σp(T)
where, σ is relational algebra operator for selection

p is the condition satisfied by a horizontal fragment

T is Relation
 Fragemnt 1: σDep = 1 EMPLOYEE
Employee

Fragemnt 2: σDep = 2 EMPLOYEE

1. Primary Horizontal Fragmentation:
q Primary Horizontal Fragmentation is a table fragmentation technique
in which we fragment a single table and this fragmentation is row-wise
and using a set of simple conditions/predicates.
q Simple predicate
Given a table/relation R with set of attributes [A1, A2, A3, …, An], a
simple predicate Pi can be expressed as follows;
Pi : Aj θ Value θ can be any symbol {≤, ≥, ≠, <, >, =}
Example: P1: Marks <= 75
q Minterm Predicate:
• When we fragment any relation horizontally, we use single
condition or set of simple predicates to filter the data.
• If we combine all simple predicate using conjunction (^) and
negation we obtain a set of complex predicates called the
minterm predicates.

Min-term predicate, Mi = P1 Λ P2 Λ P3 Λ … Λ Pn
• Algorithm for Primary Horizontal Fragmentation:
q Find set of simple predicates that are relevant in partitioning
input relation
q Derive minterm based on simple predicate.
q Eliminate meaningless minterms.
q Use remaining minterms to define the fragments.
Player
Select * from Player where P1
PID PName Country YBorn FTest
Country=’India’
100 Sachin India 1973 1989
101 Rahul India 1973 1996
102 Virat India 1988 2011
Select * from Player
103 Dhoni India 1981 2005 P2
104 Saurav India 1972 1996 where Country=’Australia’
105 Brian W Indies 1969 1990
106 Sanath Srilanka 1969 1991
107 Shaun South Africa 1973 1995
108 Daniel New Zealand 1979 1997
Select * from Player
where YBorn<=1975 P3
109 Ricky Australia 1974 1995
110 Shane Australia 1969 1992
111 Yuvraj India 1981 2003
112 Brett Australia 1976 1999
Using this predicate P1, P2, P3 we may derive 8 minterm as follow:

m1: Country=’India’ And Country = ‘Australia’ And YBorn <=1975

m2: Country=’India’ And Country = ‘Australia’ And YBorn >1975
m3: Country=’India’ And Country ≠ ‘Australia’ And YBorn <=1975
m4: Country=’India’ And Country ≠ ‘Australia’ And YBorn >1975
m5: Country≠’India’ And Country ≠ ‘Australia’ And YBorn <=1975
m6: Country≠’India’ And Country ≠ ‘Australia’ And YBorn > 1975
m7: Country≠’India’ And Country = ‘Australia’ And YBorn <=1975
m8: Country≠’India’ And Country = ‘Australia’ And YBorn >1975
• m1 and m2 are meaningless as no player can come from both the
countries
• m3 and m4 are about players from India.
• m5 and m6 is about player from other countries.
• m7 and m8 are about player from Australia.
Player m3: Country=’India’ And Country ≠
PID PName Country YBorn FTest ‘Australia’ And YBorn <=1975
100 Sachin India 1973 1989
101 Rahul India 1973 1996
102 Virat India 1988 2011
103 Dhoni India 1981 2005
104 Saurav India 1972 1996
105 Brian W Indies 1969 1990
106 Sanath Srilanka 1969 1991 m4: Country=’India’ And Country ≠
107 Shaun South Africa 1973 1995
‘Australia’ And YBorn >1975
108 Daniel New Zealand 1979 1997

109 Ricky Australia 1974 1995

110 Shane Australia 1969 1992
111 Yuvraj India 1981 2003
112 Brett Australia 1976 1999
Player m5: Country≠’India’ And Country ≠

PID PName Country YBorn FTest

‘Australia’ And YBorn <=1975
100 Sachin India 1973 1989
101 Rahul India 1973 1996
102 Virat India 1988 2011
103 Dhoni India 1981 2005
104 Saurav India 1972 1996
105 Brian W Indies 1969 1990
106 Sanath Srilanka 1969 1991 m6: Country≠’India’ And Country ≠
107 Shaun South Africa 1973 1995
‘Australia’ And YBorn > 1975
108 Daniel New Zealand 1979 1997

109 Ricky Australia 1974 1995

110 Shane Australia 1969 1992
111 Yuvraj India 1981 2003
112 Brett Australia 1976 1999
Player m7: Country≠’India’ And Country =

PID PName Country YBorn FTest

‘Australia’ And YBorn <=1975
100 Sachin India 1973 1989
101 Rahul India 1973 1996
102 Virat India 1988 2011
103 Dhoni India 1981 2005
104 Saurav India 1972 1996
105 Brian W Indies 1969 1990
106 Sanath Srilanka 1969 1991 m8: Country≠’India’ And Country =
107 Shaun South Africa 1973 1995
‘Australia’ And YBorn > 1975
108 Daniel New Zealand 1979 1997

109 Ricky Australia 1974 1995

110 Shane Australia 1969 1992
111 Yuvraj India 1981 2003
112 Brett Australia 1976 1999
F1
F1 U F2 U F3 U F4 U F5 U F6
PID PName Country YBorn FTest
100 Sachin India 1973 1989
F2 101 Rahul India 1973 1996
102 Virat India 1988 2011
103 Dhoni India 1981 2005
104 Saurav India 1972 1996
F3
105 Brian W Indies 1969 1990
106 Sanath Srilanka 1969 1991
F4
107 Shaun South Africa 1973 1995
108 Daniel New Zealand 1979 1997
F5 109 Ricky Australia 1974 1995
110 Shane Australia 1969 1992
F6 111 Yuvraj India 1981 2003
112 Brett Australia 1976 1999
Correctness of Fragments:
1. Completeness:
q If a relation R is fragmented into a set of fragments, then a record of
Relation R must be found in any one or more of the fragments. This
rule ensures that we have not lost any records during the process of
fragmentation.
qBy performing the union operation between all the Player table
fragments we will be able to get Player back without any information
loss. Hence, the above fragmentation is Complete.
F1 U F2 U F3 U F4 U F5 U F6 = Player Relation
2. Reconstruction
q After fragmenting a table, we must be able to reconstruct it back to its
original form without any data loss through some relational operation.
Reconstruction can be performed with the help of union [Link]
rule ensures that we can construct a base table back from its fragments
without losing any information.
q By performing Union operation between all the fragments, we will be
able to get the original table back. Hence, the fragmentation is correct
and the reconstruction property is satisfied.
3. Disjointness:
q If a relation R is fragmented into a set of sub-tables R1, R2, R3, …, Rn, a
record belongs to R1 is not found in any other fragment. This ensures
that R1 ≠ R2.

F1 ∩ F2 ∩ F3 ∩ F4 ∩ F5 ∩ F6 = NULL

q So we can say that disjointness property is satisfied.

 2. Derived Horizontal Fragmentation:
qIn Derived Horizontal Fragmentation we fragment a table based on the
constraints defined on another table.
qBoth tables are linked with each other with the help of primary and foreign
key and must establish the Owner-Member relation.
qOwner table is a parent table to which we apply the [Link] table
is a child table that can be fragmented but by following the constraints of the
parent table.
qIf we fragment the tables separately, then for every insertion of records the table
must verify the existence of one such value in the parent table. Hence, for this case,
the Primary Horizontal Fragmentation would not work.
 Address
Student
Roll City
Roll No Name Marks State No
10 Pune, Maharashtra
10 XYZ 67 Maharashtra
11 ABC 34 Gujarat 10 Surat, Gujarat
12 PQR 89 Maharashtra
11 Ahmedabad,Gujarat
13 ABC 90 Goa
14 XYZ 75 Kerala 12 Mumbai,Maharashtra

13 Panji, Goa

14 Kochi,Kerala
fragmenting the relation STUDENT on the State attribute,
Roll Name Marks State
F1 No qIt is necessary to fragment the
10 XYZ 67 Maharashtra second relation ADDRESS based on
12 PQR 89 Maharashtra
the fragment created in STUDENT
relation. The fragmentation of
F2
Roll Name Marks State ADDRESS is done as follow as a set
No
11 ABC 34 Gujarat
of semi-joins as follows.

Roll Name Marks State 1. A1 = ADDRESS ⋉ F1

No
F3 13 ABC 90 Goa
2. A2 = ADDRESS ⋉ F2
3. A3 = ADDRESS ⋉ F3
Roll Name Marks State 4. A4 = ADDRESS ⋉ F4
No
F4 14 XYZ 75 Kerala
 Roll No City
Roll Name Marks State
No 10 Pune, Maharashtra
F1
10 XYZ 67 Maharashtra A1 10 Surat, Gujarat
12 PQR 89 Maharashtra
12 Mumbai,Maharashtra

Roll Name Marks State

F2 No A2 Roll No City
11 ABC 34 Gujarat 11 Ahmedabad,Gujarat

Roll Name Marks State

F3 No Roll No City
13 ABC 90 Goa A3 13 Panji, Goa

Roll Name Marks State

F4 No A4 Roll No City
14 XYZ 75 Kerala 14 Kochi,Kerala
2. Vertical fragmentation
q Vertical fragmentation refers to the process of decomposing a
table vertically by attributes or columns.
q In this fragmentation, some of the attributes are stored in one
system and the rest are stored in other systems. This is because
each site may not need all columns of a table.
q In order to take care of restoration, each fragment must contain
the primary key field(s) in a table.
q The fragmentation should be in such a manner that we can rebuild a table
from the fragment by taking the natural JOIN operation and to make it
possible we need to include a special attribute called Tuple-id to the
schema.
q In relational algebra vertical fragmentation on table T, can be represented
as follows:

πa1, a2,…, an (T)

where a1,a2,....an are attributes

Employee

F2

F1

we join these two fragments F1 and F2 as πEMPLOYEE (F1 ⋈ F2)

3. Hybrid Fragmentation

q The combination of vertical fragmentation of a table followed by

further horizontal fragmentation of some fragments is called mixed or
hybrid fragmentation.
q For defining this type of fragmentation we use the SELECT and the
PROJECT operations of relational algebra.
q In some situations, the horizontal and the vertical fragmentation isn’t
enough to distribute data for some applications and in that conditions,
we need a fragmentation called a mixed/hybrid fragmentation.
q Mixed fragmentation can be done in two different ways:
1. The first method is to first create a set or group of horizontal fragments
and then create vertical fragments from one or more of the horizontal
fragments.
2. The second method is to first create a set or group of vertical fragments
and then create horizontal fragments from one or more of the vertical
fragments.
q The original relation can be obtained by the combination of
JOIN and UNION operations which is given as follows:

σP(πa1, a2..,an(T))
πa1,a2….,an (σp(T))
Advantages of Fragmentation

q Due to unavailability of the irrelevant data, we can maintain the

security and privacy of the database system.
q Efficiency of the database system is increased.
q Data is locally available, so Local query optimization techniques
are sufficient for most of the database queries
Disadvantages of Fragmentation

q There is a lack of back-up copies of data in distributed area and it

may cause the database to be ineffective if a site down.
q Reconstruction is expensive techniques in case of recursive
fragmentation.
 Design Issues in Distributed Database
1. Scalability
Challenges:
o Handling Increased Load: As the system grows with more users or increased data, it
must be able to handle this growth efficiently without significant performance
degradation.
o Geographic Distribution: Ensuring low latency and high performance across nodes
located in different geographical regions can be difficult, particularly with network
delays and data synchronization.
Strategies to Achieve Scalability:
q Horizontal Scaling: Involves adding more machines (nodes) to the system. This is
often more cost-effective and can offer redundancy.
q Vertical Scaling: Enhancing the capacity (CPU, memory, etc.) of existing
machines, though this has limits and can become expensive.
q Sharding: Distributing data across multiple databases or servers to manage it
more effectively and reduce the load on any single system.
2. Fault Tolerance
Challenges:
q Failure Handling: Systems must be resilient to failures of individual
components (e.g., servers, networks) without causing the entire system to
fail.
q Data Consistency: Ensuring data remains consistent even when failures
occur is critical and challenging, particularly with distributed databases.
Strategies to Achieve Fault Tolerance:
q Redundancy: Replicating data across multiple nodes to ensure availability
even if one node fails.
q Automatic Failover: Automatically switching to a backup system when a
failure is detected.
q Algorithms: Using algorithms like Paxos or Raft to maintain data
consistency across distributed nodes.
3. Latency

Challenges:
q Network Delays: Communication between distributed nodes can
introduce latency, especially over long distances.
q Resource Competing: Competing for shared resources can increase
latency.

Strategies to Minimize Latency:

q Caching: Storing frequently accessed data closer to where it’s needed to
reduce access time.
q Load Balancing: Distributing requests across multiple nodes to prevent
any single node from becoming a bottleneck.
q Optimized Data Placement: Strategically placing data in locations that
minimize access time for the most frequent operations.
4. Security

Challenges:
q Data Protection: Ensuring that data remains secure during transmission
and storage across different nodes.
q Authentication and Authorization: Managing who has access to the
system and what they are allowed to do.

Strategies to Ensure Security:

q Encryption: Encrypting data both at rest and in transit to protect it from
unauthorized access.
q Access Control: Implementing strict authentication and authorization
mechanisms.
q Audit Logs: Keeping detailed logs of all operations to detect and
respond to security breaches.
5. Interoperability
Challenges:
q Heterogeneous Systems: Distributed systems often involve different
platforms, technologies, and protocols that need to work together.
Strategies to Enhance Interoperability:
q Standardized Protocols: Using well-established protocols and standards to
ensure different parts of the system can communicate effectively.
q Middleware: Implementing middleware solutions that facilitate
communication and data exchange between different systems.