Srinix College of Engineering, Balasore

Database Engineering (CSPC2004)

Module – IV
Lecture Note: 30 07-04-2026
Introduction to File Structure: A file structure defines how data are represented, stored, and accessed
on computer hardware, acting as a crucial bridge between logical data needs and physical storage devices.
File structure in a Database Management System (DBMS) defines how data records are mapped onto disk
blocks and physically stored in the system's memory.
The primary objective is to optimize the speed of data access, storage efficiency, and the ease of performing
operations like insertion, deletion, and updating records.
 File: A collection of related records, stored in a binary format.
 Record: A single entry in a file, analogous to a row in a database table.
 Disk Blocks/Buckets: The physical memory locations (units of storage) where records are stored.
 File Organization: The specific method used to arrange records within a file, which dictates the
efficiency of data retrieval and modification operations.

Placing File records on disk: Placing file records on disk involves mapping logical records into physical
blocks using techniques like Heap, Sequential, Hashed, or Clustered organization.
Records are packed into blocks using spanned (across blocks) or unspanned (within one block) methods to
optimize disk I/O, which is crucial for reducing access time.
 File Organization Techniques:
 Heap File Organization (Unordered): Records are placed wherever there is space, typically at the
end of the file, allowing for fast insertion but slower searches.
 Sequential File Organization (Ordered): Records are placed in a specific order based on a key field,
making range queries efficient.
 Hash File Organization: A hash function is applied to a record field to determine the specific disk
block address for placement, enabling fast direct access.
 Clustered File Organization: Related records from multiple tables are stored together in the same or
nearby blocks to optimize join operations.
 Record Packing Methods:
 Unspanned Records: A record must fit entirely within one block. If it cannot, it moves to the next
block, leaving empty space, often used for fixed-length records.
 Spanned Records: A large record can be split across multiple blocks, with pointers linking them. This
is more space-efficient, suitable for variable-length records.
 Block Allocation Methods:
 Contiguous Allocation: Files are assigned consecutive disk blocks, providing fast sequential access
but making file expansion difficult.
 Linked Allocation: File blocks are linked together, making expansion easy, but direct access slower.
 Indexed Allocation: Index blocks are used to store pointers to the actual data blocks, offering a
balance between efficiency and flexibility.
Hashing Techniques: Hashing is a database technique used for high-speed data retrieval. Instead of navigating
through a multi-level index structure (like a B-Tree), a hash function maps search keys directly to a specific disk location
(called a bucket), allowing for near-constant time O(1) access. That means storing and retrieving data in O(1) [in order
of one] time.
This is otherwise called as mapping technique because we try to map the larger value with smaller value by using
hashing.
Hash terminology:
 Search Key: By using this key, we can search something in the database.
 Hash Table: This is a table looks like an array to store the data based on search key.
 Hash Function (h): A mathematical function that takes a search key as input and returns a bucket address.
Basically, there are three hash functions used. (K Mod n, Mid Square method and Folding method).
 Bucket: A storage unit (usually a disk block) that holds one or more data records.
 Hash Index: The resulting address or "slot" generated by the hash function where the record is stored.
 Collision: Occurs when the hash function generates the same bucket address for two different keys.
Example:
 Search Key (24, 52, 91, 67, 48, 83)
 Hash Table
 Hash Function (K Mod 10, Mid Square method and Folding method).

0
1 91
52
2
83
3
24
4
5
6
67
7
48
8
9

Hash Table
1) K Mod 10: Here, K is the search key. The first search key is 24.
24 Mod 10 = 4 (Remainder value), and this (4) is the hash value. 24 will store at the index 4. Then
52 Mod 10 = 2 (Remainder value), and this (2) is the hash value. 52 will store at the index 2. Then so on upto last to
store the value.
2) Mid Square Method: Suppose the key is 123. This method finds out the square of the middle number and the no is
2 (i.e. 22). Here the hash value comes to 4 and the key 123 will store at index 4.
3) Folding Method: Suppose the key is 123456 and the hash table is from 0-999. This method divides the number in
two equal part (i.e. 123 and 456) and then add the numbers.
123 + 456 = 579. Here the hash value comes to 579 and the key 123456 will store at index 579.

Suppose there is a search key 62 and we want to store it in the hash table. 62 Mod 10 = 2. Index 2 is already filled
with 52. Here the collision occurs. To avoid the collision, we use some other technology.
Types of Hashing Techniques:
1. Static Hashing
In static hashing, the number of buckets in the database remains constant. The hash function always produces the same
output for a given key.
 Limitation: If the data size grows significantly, the fixed number of buckets leads to frequent collisions and
performance degradation.
 Collision Resolution Techniques:
o Chaining (Open Hashing): If a bucket is full, the system allocates an overflow bucket and links it to
the original, creating a chain of buckets.
o Open Addressing (Closed Hashing): If a collision occurs, the system linearly or quadratically searches
for the next available empty bucket (Linear Probing/Quadratic Probing/Double Hashing).

Collision Resolution Techniques

Chaining Open Addressing

(Open Hashing) (Closed Hashing)

Linear Probing Quadratic Probing Double Hashing

In case of Chaining (Open Hashing) technology, the key 62 will store at index 2 (hash value) as like as a
chain (linked list).

91
52 62
83
24

67
48
In case of Linear probing, instead of making chain just we have to go for the next available index to
store the value. If the immediate next index is already filled then go for next available index to store
the value and so on up to last index. In this case the index 3 and index 4 is already filled. So, the value
62 will store at index 5, as index 5 is empty.
In case of Quadratic probing, we have to use the formula (h + i2 Mod n). Here, h is the hash value
and i is the probe no. (no. of times attempt) to store the value in hash table.
2 + 12 = 3 Mod 10 = 3. As the index 3 is already filled we have to go for next attempt. Here the hash
value is fix (i.e. 2) but the no. of attempt is increased to 2. So, the calculation is:
2 + 22 = 6 Mod 10 = 6. As the index 6 is empty, we will store the value 62 at index 6.
In case of Double hashing, just we have to use two hash functions to store the value at proper index.
If the first hash function is not suitable that means if collision occurs then we have to use another hash
function to store the value at proper index.
2. Dynamic Hashing
Dynamic hashing (also called Extendible Hashing) is designed to handle changing data volumes by
allowing the number of buckets to grow or shrink on demand.
 Mechanism: It uses a directory of pointers to buckets. When a bucket overflows, it is split,
and the directory may be updated or expanded to accommodate the new structure.
 Advantage: It avoids the "overflow chain" performance issues of static hashing and provides
better space utilization for evolving datasets.
Comparison: Static Hashing vs. Dynamic Hashing:

Feature Static Hashing Dynamic Hashing

No. of Buckets Fixed Changes dynamically

Overflow Uses chaining or open addressing Uses bucket splitting & directory
Handling updates
Performance Can degrade if the database grows Remains consistent as data grows
Complexity Simple to implement More complex to implement
Best For Databases with a predictable, Databases with unpredictable or
constant size growing data
Lecture Note: 31 08-04-2026
Parallelizing Disk Access using RAID Technology: Parallelizing disk access using RAID (Redundant
Array of Independent Disks) technology in DBMS improves performance and reliability by distributing data
across multiple disks (striping) to enable simultaneous I/O operations.
It converts multiple small drives into a single logical volume, increasing speed and providing fault tolerance.
RAID Levels for Parallelism:
 RAID 0 (Striping): Divides data into blocks and distributes them across multiple disks. It offers the
best read/write performance by operating in parallel, but provides no data redundancy.
 RAID 1 (Mirroring): This is a data storage configuration that copies identical data across two or more
drives to provide 100% redundancy. It ensures high reliability because if one drive fails, the system
continues to operate using the remaining drive(s).
 RAID 5 (Distributed Parity): Stripes data and parity information across three or more disks. It offers
high read performance and fault tolerance, rebuilding data if one disk fails.
 RAID 10 (Mirrored Striping): Combines mirroring (RAID 1) and striping (RAID 0) for high
performance and high redundancy, ideal for write-intensive databases.
Benefits to DBMS:
 Increased Throughput: Multiple disks serving I/O requests simultaneously reduce bottlenecking and
speed up query response times.
 Load Balancing: Data striping spreads the I/O load evenly across all disks.
 Fault Tolerance: RAID levels 1, 5, and 10 provide redundancy, allowing the system to continue
running if a disk fails.
 Scalability: Storage systems can be expanded by adding more disks to the array.

Indexing structures for files: Indexing structures in a Database Management System (DBMS)
are specialized data structures like B-trees or Hash tables used to locate data in a file quickly without having
to scan the entire table.
Indexing Data Structures:
These are the underlying data structures used to store and organize the "index table":
 B-Tree / B+ Tree: These are the most common structures. They are self-balancing trees that keep
data sorted and allow for efficient searching, insertion, and deletion.
o Best for: General-purpose indexing, especially when you need to perform range queries
(e.g., WHERE age BETWEEN 20 AND 30) or ORDER BY operations.
 Hash Index: These use a hash function to map search keys to specific "buckets" where data is stored.
o Best for: Extremely fast exact-match lookups (e.g., WHERE id = 500). They do not support
range queries because they do not maintain a sorted order.
 Bitmap Index: These use bit arrays (strings of 0s and 1s) to represent the presence or absence of a
value.
o Best for: Columns with low cardinality (few unique values, like "Gender" or "Marital
Status") and data warehousing/analytical workloads.
Single-level Ordered Indexes: Single-level ordered indexes in DBMS are ordered files
comprising key-pointer pairs used to speed up search operations by acting as a pointer to the
main data file.
Single-level ordered indexing is a simple yet powerful method to speed up the searching
process while fetching data from a database.
Basics of Single-Level Ordered Indexing:
When a database file is unindexed, we will have to use linear search for retrieving a specific
record. We need to scan all records one by one until the desired one is found. This approach is
slow, when the databases are so large.
Single-level ordered indexing addresses this problem by organizing records in an auxiliary file
called the index file.
An index file contains two main components −
 Index Key − A field from the original file (e.g., a name or ID) that is used to organize
and locate data.
 Pointer − A reference to the location of the record in the original file.
The values in the index are stored in a specific order, so we can use efficient searching
algorithms like the binary search. Since the index file is much smaller than the original data
file, searches are faster.
Types of Single-Level Ordered Indexes
 Primary Index (Sparse): Created on an ordered data file where the index field is the
primary key (ordered key field). It is usually a sparse index, meaning it contains one
entry for each disk block rather than every record.
 Secondary Index (Dense): Created on a non-ordering field (non-key or non-unique
field). To enable fast searching of unordered data, it is typically a dense index,
containing an index entry for every record in the table.
 Clustered/Clustering Index (Sparse): Applied when the data file is ordered, but the
index field is not a unique key (non-unique ordering field). Multiple records with the
same field value are grouped together (clustered).
 Dense Index: A type of ordered index where an entry exists for every search key value,
guaranteeing fast lookup.
 Sparse Index: An index where entries exist for only some of the search values (e.g.,
one entry per disk block), requiring less storage space than a dense index.
Lecture Note: 32 09-04-2026
Dynamic Multilevel Indexes using B Trees and B+ Trees: In Database Management
Systems (DBMS), dynamic multilevel indexing uses self-balancing tree structures, primarily
B Trees and B+ Trees, to maintain efficient data access as the database grows or shrinks.
These indexes automatically adjust by splitting or merging nodes during insertions and
deletions.
Overview of B-Trees and B+ Trees in Multilevel Indexing:
Feature B Tree B+ Tree
Data Storage Stores both keys and data (or data Stores data pointers only in leaf nodes;
pointers) in all nodes (internal and internal nodes store only search keys.
leaf).
Tree Height Generally deeper because internal Typically, shallower because more keys
nodes take up more space per fit into internal nodes, increasing "fan-
entry. out".
Search Time Variable: A search might end early Consistent: Every search must traverse
if the key is found in an internal from the root down to a leaf node.
node.
Range Slower: Requires multiple tree Highly Efficient: Leaf nodes are linked
Queries traversals as keys are spread across together, allowing fast sequential
levels. scanning.
Deletion Complex: Deleting from internal Simpler: Deletions only occur at the
nodes requires intricate leaf level, though they may trigger
rebalancing. parent updates.

How They Work as Multilevel Indexes:

1. Hierarchical Structure: Both trees organize data into multiple levels—Root, Internal
(index) nodes, and Leaf nodes. Each level acts as an "index for the index" below it,
significantly reducing disk I/O operations compared to single-level indexing.
2. Dynamic Rebalancing:
Insertion: If a leaf node becomes full, it splits into two. The median key is promoted to
the parent node. This process can propagate upward, eventually creating a new root if
necessary.
Deletion: If a node falls below the minimum occupancy (usually half full), it
may borrow a key from a sibling or merge with one, ensuring the tree remains balanced
and compact.
3. Leaf Node Chaining (B+ Trees): In a B+ Tree, leaf nodes are connected via a Singly-
Linked List or Doubly-Linked List. This allows the DBMS to find the start of a range
and then simply follow pointers to retrieve subsequent records without re-traversing the
tree.
Indexes on Multiple Keys: Indexes on multiple keys, known as composite
indexes or concatenated indexes, are a type of database index built on two or more columns of
a table.
They are designed to optimize queries that filter, sort, or group data based on the specific
combination and order of those columns.
A composite index treats the combination of values in the indexed columns as a single search
key. The entries in the index are typically stored in a sorted, hierarchical structure (most
commonly a B+ tree) using lexicographical order, similar to how words are ordered in a
dictionary.
The sorting is based on the first column, then the second column, and so on.
Advantages
 Faster Complex Queries: They significantly improve performance for queries
with WHERE clauses that involve all or a leading subset of the indexed columns.
 Efficient Filtering and Sorting: Queries with ORDER BY or GROUP BY clauses on
the indexed columns can be executed faster because the data is already ordered in the
index structure, reducing the need for separate sorting operations.
 Reduced Disk I/O: By using the index to find the exact data location, the database
engine avoids scanning the entire table, minimizing disk input/output operations.
 Enforcing Uniqueness: They can enforce uniqueness constraints across a combination
of columns, ensuring that no two records have the same set of values for all indexed
keys.
Disadvantages
 Write Overhead: INSERT, UPDATE, and DELETE operations become slower
because the database management system (DBMS) must also update the index structure
for every change.
 Storage Consumption: They require additional disk space to store the index entries.
 Limited Usability: A composite index cannot effectively optimize queries that use only
a non-leading column in the index definition (e.g., an index on <A, B> is not efficient
for a query only on column B).
Lecture Note: 33 10-04-2026
Translating SQL Queries into Relational Algebra:
Translating SQL queries into relational algebra is a fundamental process in database management systems,
serving as the bridge between a user's declarative request (what data to get) and the
system's procedural execution plan (how to get it).
Basic Mapping of SQL to Relational Algebra:
The standard SELECT-FROM-WHERE block maps to algebraic operations in a specific order:
 FROM Clause → Cartesian Product (X) or Join: Combines the specified tables.

 WHERE Clause → Selection (σ): Filters rows based on the provided condition.

 SELECT Clause → Projection (π): Selects specific columns from the filtered results.
Core Algebraic Operators:
SQL Keyword Relational Algebra Operator Description

SELECT (Columns) Projection (π) Extracts specified columns.

WHERE Selection (σ) Filters rows satisfying a condition.

JOIN / FROM R, S Join / Cross Product (X) Combines rows from multiple relations.

UNION Union (∪) Combines results from two queries (must be

union-compatible).
EXCEPT / MINUS Set Difference (-) Finds rows in the first set but not the second.

INTERSECT Intersection (∩) Finds rows common to both sets.

AS / RENAME Rename (ρ) Renames a relation or its attributes.

Advanced SQL Translations:

 Aggregation and Grouping: Standard relational algebra does not include these, but extended relational
algebra uses the Aggregation operator to handle GROUP BY and functions like SUM or COUNT.
 Nested Subqueries: These are typically decomposed into separate blocks. Correlated subqueries
(where the inner query depends on the outer) are often translated using context relations and Semi-
joins or Anti-joins to improve efficiency.
 Universal Quantification ("ALL"): SQL queries asking for "all X that satisfy Y" (e.g., find employees
who have taken ALL trainings) are translated using the Division (÷) operator.
The Translation Process:
1. Decomposition: The SQL query is broken into smaller units called query blocks.
2. Conversion: Each block is converted into an equivalent relational algebra expression.
3. Optimization: The Database Query Optimizer uses algebraic equivalence rules (e.g., pushing
selections down) to create the most efficient query tree.
Algorithms for External Sorting: External sorting refers to a class of sorting algorithms designed to handle
datasets too large to fit into a computer's main memory (RAM). These algorithms minimize slow disk I/O operations by
processing data in chunks that fit in memory and then merging them on external storage like hard drives or SSDs.
Core Mechanism (External Merge Sort): The most common implementation is External Merge Sort, which typically
operates in two main phases:

 Sorting Phase (Run Generation): The large dataset is divided into "runs"—chunks small enough to fit in
RAM. Each chunk is read into memory, sorted using a standard Internal Sorting algorithm
(like Quicksort or Heapsort), and written back to disk as a sorted temporary file.
 Merge Phase: The sorted runs are combined into a single larger file. This is often done using a multi-way
merge. For example, a 10-way merge would use 10 input buffers (one for each run) and one output buffer, using
a Min-Heap to efficiently select the smallest element among all current buffers.
Common Algorithms & Variations:

 K-way Merge Sort: Generalizes the merge process by merging sorted runs at once. Using a larger reduces the
total number of merge passes required.
 Replacement Selection: A more efficient run generation method that uses a Priority Queue to produce initial
runs that are, on average, twice the size of available memory.
 Polyphase Merge Sort: An optimized merge strategy originally designed for tape drives that reduces the
number of merges passes and output files by using a Fibonacci-like distribution of runs.
 Balanced Multiway Merge Sort: Distributes runs evenly across multiple storage units to perform merging in
parallel, improving throughput.

Algorithms for SELECT and JOIN Operations: Algorithms for SELECT and JOIN operations
are fundamental to query processing in dbms. They determine how data are retrieved and combined, with the choice of
algorithm, impacting performance based on data size, available memory, and indexing.

SELECT Operations: The SELECT operation (or "selection") filters records from a single table based on specific
criteria. The DBMS chooses an algorithm based on file organization and existing indexes.

 Linear Search (Brute Force): Scans every record in the table to find those that satisfy the condition. It is slow
for large tables but works regardless of indexing or sorting.
 Binary Search: Used when the data is physically sorted on the selection attribute. It repeatedly halves the search
space, offering much faster performance than linear search.
 Primary/Clustering Index Search: Uses a B-tree or similar structure to jump directly to the relevant record(s).
This is the most efficient method for unique key lookups.
 Secondary Index Search: Used for searches on non-unique or non-key attributes that have an index. The
DBMS uses the index to retrieve pointers to the matching data blocks.
 Hash Key Search: Retrieves records instantly by applying a hash function to the search key to find its exact
disk location.
JOIN Operations: JOIN operations combine rows from two or more tables based on a related column. They are
among the most resource-intensive operations in a database.

 Nested-Loop Join (NLJ): The most basic join. It compares every row of the "outer" table with every row of
the "inner" table. Its complexity is, making it inefficient for large datasets.
 Block Nested-Loop Join (BNLJ): An optimized version of NLJ that processes data in blocks rather than
individual rows, significantly reducing disk I/O.
 Indexed Nested-Loop Join (INLJ): If the inner table has an index on the join attribute, the DBMS uses it to
find matches directly instead of performing a full scan for every outer row.
 Sort-Merge Join: Both tables are first sorted on the join attribute and then merged in a single pass. This is
highly efficient for large, sorted datasets or when pre-existing clustered indexes exist.
 Hash Join: Uses a hash function to partition rows from both tables into buckets based on the join key. It then
joins the buckets. It is often the fastest choice for large-scale equi-joins that don't have indexes.
Lecture Note: 34 13-04-2026
Algorithms for PROJECT and SET Operations: Algorithms for PROJECT and SET operations in
databases, efficiently handling duplicates and managing data-intensive operations through sorting, hashing, or indexing.
The Project (π) operation is implemented by sorting or hashing to remove duplicates, while UNION (∪),
INTERSECTION (∩), and SET DIFFERENCE (-) use sort-merge or hash-based algorithms to compare and process
union-compatible relations.

Algorithms for PROJECT (π) Operations:

The project operation reduces the number of attributes (columns) in a relation. The core challenge is removing duplicate
tuples after dropping columns.
 Sorting-Based Project: Sort the relation on the projected attributes to bring identical tuples together. A single
scan then removes duplicates.
 Hash-Based Project: Use a hash function on the projected attributes to partition the relation into buckets.
Duplicate tuples will fall into the same bucket, allowing for efficient in-memory comparison and elimination.

Algorithms for SET Operations:

Set operations apply only to union-compatible relations (same number of attributes, compatible domains).
 Sort-Merge Algorithm (UNION, INTERSECTION, DIFFERENCE):
1. Sort both relations R and S on the same columns.
2. Scan both sorted lists to produce the result:
o UNION (R ∪ S): Merge lists, keeping only one instance of duplicate tuples.
o INTERSECTION (R ∩ S): Output tuples that appear in both relations.
o SET DIFFERENCE (R - S): Output tuples that appear in R but not in S.
 Hash-Based Algorithms:
1. Partition both relations into sets of buckets using a hash function on all attributes.
2. For each pair of corresponding buckets, compare tuples using a hash table to perform the set operation.

Implementing Aggregate Operations and OUTER JOINs: Outer joins (LEFT, RIGHT, FULL) preserve
unmatched rows from tables, filling missing data with NULL, and are implemented by modifying algorithms like
nested-loop or hash-join. When combined with aggregate functions (e.g., SUM, AVG, COUNT), they provide insights
into data sets, such as calculating totals for each group, even when no matching record exists in the secondary table.
Implementing Outer Joins and Aggregates:
 Outer Join Implementation:
o Nested-Loop Join: The outer relation retains all its tuples. If a match is found in the inner table, the
joined row is added; otherwise, it is added with NULL for the inner table's columns.
o Sort-Merge/Hash-Join: These algorithms can be extended to retain unmatched rows.
o Relational Algebra: Computed by performing an inner join, identifying missing tuples, padding them
with NULL, and unioning them back.
 Aggregate Operations:
o Functions like AVG, SUM, MIN, MAX, and COUNT often operate within GROUP BY clauses to
provide analytical insights.
o When an aggregate function is used with an outer join, it is crucial to understand that the aggregate can
be applied to rows that may have NULL values from the non-matching side.
Lecture Note: 35 15-04-2026
Combining Operations Using Pipelining: Pipelining in database systems combines multiple
relational operations (SELECT, JOIN, PROJECT) into a single execution step. It passes data directly between
operators without creating, writing, and reading temporary files on disk. This technique significantly reduces
disk I/O, improves performance, and increases throughput, effectively allowing query processing in parallel.
For example, rather than being implemented separately, a JOIN can be combined with
two SELECT operations on the input files and a final PROJECT operation on the resulting file; all this is
implemented by one algorithm with two input files and a single output file. Rather than creating four temporary
files, we apply the algorithm directly and get just one result file.
Key Aspects of Pipelining in Query Processing
 Reduced Disk Access: By avoiding the materialization of intermediate results in temporary files,
pipelining reduces disk I/O costs.
 Stream-based Evaluation: The results of one operation are immediately fed as input to the next, often
called stream-based processing.
 Faster Response Time: Pipelining allows the database to start producing output tuples much faster
than if the entire query was materialized.
Example:
Suppose we want to perform combined multiply and add operation with a stream of nos.
Ai * Bi + Ci for i= 1, 2, 3……7
R1← Ai, R2←Bi
R3←R1 * R2, R4←Ci
R5←R3 + R4

Ai Bi Ci

R1 R2

Multiplier

R3 R4

Adder

R5

(Perform combined multiply and add operation)

Using Heuristics in Query Optimization: Heuristic query optimization is a rule-based technique in
database management systems (DBMS) used to transform a high-level query (like SQL) into an efficient
execution plan.
Unlike cost-based optimization, which calculates the exact resource cost (CPU, I/O) of many possible plans,
heuristics use "rules of thumb" or logical transformations to eliminate inefficient operations early.
Rules of thumb refers to a set of predefined, practical guidelines and best practices used by database
management systems (DBMS) to transform a SQL query into an efficient execution plan without calculating
the exact, absolute lowest cost.
These rules are designed to produce a "good enough" solution quickly, rather than guaranteeing the absolute
best solution.
Heuristic Rules
 Perform Selection Early (Filter First): Move SELECT operations as far down the query tree as
possible. This reduces the number of records (tuples) before expensive operations like joins.
 Perform Projection Early (Reduce Columns): Apply PROJECT operations early to discard
unnecessary attributes. This minimizes the width of intermediate results, saving memory and
processing time.
 Transform Cartesian Products into Joins: A Cartesian product followed by a filter is extremely
inefficient. Heuristics combine these into a single JOIN operation to avoid generating massive
intermediate tables.
 Restrictive Operations First: Execute the most restrictive selections and joins (those that return the
fewest rows) before others to keep intermediate data sets small.
 Query Rewriting: Break down complex conjunctive conditions into a "cascade" of simpler selections
that can be independently moved down the tree.
Benefits & Limitations
 Efficiency: Heuristic methods have polynomial time complexity, making them much faster than the
exponential search required for exhaustive cost-based optimization.
 Simplicity: They provide a straightforward, rule-based approach that is easier to implement for simple
queries.
 Suboptimality Risk: Because heuristics are "rules of thumb" and don't account for actual data
distribution or system load, they may not always find the absolute best execution plan.
 Hybrid Approach: Most modern database systems, like Oracle, use a hybrid model where heuristics
perform initial logical pruning before a cost-based optimizer makes the final physical decisions.
 Scalability: Works well for large datasets. This is by minimizing intermediate results.
Lecture Note: 36 16-04-2026
Using Selectivity and Cost Estimates in Query Optimization: In query
optimization, selectivity and cost estimates are the primary drivers of Cost-Based Optimization
(CBO). The optimizer evaluates multiple potential execution plans for a single SQL statement and
selects the one with the lowest total "cost".
Selectivity Estimation: Selectivity measures the restrictiveness of a query predicate. It represents the
fraction of rows from a table that satisfy a specific condition (e.g., WHERE age > 30).
 Calculation: It is expressed as a number between 0 and 1, where 0 means no rows are selected
and 1 means all rows are selected.
 Formula for Equality: For a condition like column = value, selectivity is often estimated as 1
/ (number of distinct values) in that column.
 Role in Optimization: High selectivity (values near 0) indicates a very restrictive condition,
prompting the optimizer to favor index scans over full table scans.
 Statistics & Histograms: Optimizers use Oracle's DBMS_STATS or similar tools to gather
statistics. If data is skewed, histograms provide more accurate selectivity than simple
averages.
Cost Estimation: Cost is a numerical value representing the estimated resource consumption required
to execute a plan.
 Components: The total cost typically includes I/O operations (disk access), CPU
usage (sorting, joins), and memory usage.
 I/O Dominance: In disk-based systems, the number of disk blocks transferred is usually the
most significant factor in the cost function.
 Distributed Systems: Cost functions also include communication/network costs for moving
data between nodes
Physical Database Design in Relational Databases: Physical database design in relational
databases is the process of translating a logical data model into a specific implementation on
secondary storage, focusing on performance, storage efficiency, and security.
Unlike the platform-independent logical design, physical design is specific to a chosen Database
Management System (DBMS) such as Oracle, MySQL, or DB2.
Steps in Physical Database Design:
1. Translate Logical Data Model: Convert logical entities into tables, attributes into columns,
and relationships into primary and foreign keys.
2. Assign Data Types: Specify exact formats (e.g., VARCHAR, INTEGER, TIMESTAMP)
and constraints like NOT NULL or UNIQUE for every column.
3. Analyze Workload: Identify critical and frequent transactions using techniques like
a transaction usage map to determine where performance optimization is most needed.
4. Select File Organizations: Decide how records are physically arranged on disk (e.g., Heap,
Hash, or Sequential) to balance retrieval speed against update costs.
 5. Design Indexes: Determine primary, clustering, and secondary indexes to accelerate queries
without creating excessive update overhead.
6. Estimate Storage: Calculate the required disk space based on record size, growth rates, and
index requirements.
7. Implement Security and Views: Define user views and security mechanisms (e.g.,
authentication, authorization) to protect data.
Performance Techniques:
 Indexing: Use B+ trees or Hash indexes to avoid full table scans. Generally, index primary keys and
frequently used foreign keys, but avoid indexing frequently updated attributes.
 Partitioning: Divide large tables horizontally (by rows) or vertically (by columns) across different
storage objects or disks to reduce I/O bottlenecks.
 Clustering: Physically store related records from one or more tables close to each other on disk to
minimize the number of disk accesses.
 Denormalization: Intentionally reintroduce redundancy by merging tables to reduce the number of
joins required for frequent queries.
 Materialized Views: Store the results of complex queries as physical tables to speed up repeated
reporting tasks.
Lecture Note: 37 17-04-2026
An Overview of Database Tuning in Relational Systems: Database tuning in relational systems
is the iterative process of optimizing performance to achieve faster query execution, higher throughput, and
efficient resource utilization.
It involves adjustments across several layers, from high-level query structure to low-level physical storage
and hardware configuration.

Areas of Database Tuning:

 Query Tuning: Focuses on rewriting SQL statements to be more efficient. Techniques include using
specific column names instead of SELECT *, preferring WHERE over HAVING for filtering before
grouping, and using EXISTS instead of IN for subqueries.
 Index Tuning: Involves creating, dropping, or modifying indexes based on actual usage. Proper
indexing on frequently searched columns (e.g., in WHERE and JOIN clauses) avoids full table scans,
though excessive indexing can slow down INSERT and UPDATE operations.
 Physical Design Tuning: Adjusts how data is stored on disk. This includes:
o Denormalization: Recombining tables to reduce complex joins for read-heavy applications.
o Partitioning: Splitting large tables into smaller segments to limit the data scanned by queries.
o Clustering: Physically ordering data on disk to match common search patterns (e.g., clustered
indexes).
 System & Resource Tuning: Configuring the Oracle Database environment and hardware. This
involves allocating sufficient RAM for data caching, optimizing CPU usage, and managing disk I/O
through techniques like RAID or Database Defragmentation.

Database Tuning Methodology:

1. Identify Bottlenecks: Use tools like Oracle's SQL Tuning Advisor or the EXPLAIN command to
analyze execution plans and identify high-load queries.
2. Collect Statistics: Update database statistics regularly so the query optimizer has accurate information
about data distribution and table sizes to choose the best execution path.
3. Analyze Execution Plans: Examine how the database engine executes a query—what indexes it uses
and in what order—to spot inefficiencies.
4. Implement & Measure: Apply changes (e.g., adding an index or rewriting a join) and remeasure
performance against baselines to verify improvements.

Common Performance Bottlenecks:

 Lack of Indexes: Forces the database to scan entire large tables for single records.
 Stale Statistics: Causes the optimizer to choose suboptimal execution plans based on outdated data
information.
 Resource Contention: High levels of concurrent access leading to locking issues and wait times.
 Inefficient Query Logic: Unnecessary use of DISTINCT, complex correlated subqueries, or improper
use of wildcards at the start of search patterns (e.g., LIKE '%pattern').