Lecture Notes

Disk Storage, File Structures, Hashing & Modern Storage Architectures

1. Introduction to Physical Database Storage

• Databases are physically stored as files containing records.

• These files reside on secondary storage devices (mainly disks).

• This layer corresponds to the physical level in the three-schema architecture:

o External level

o Conceptual level

o Physical level (focus here)

Goal: Efficient storage, retrieval, and management of data

2. Storage Hierarchy in Database Systems

Levels of Storage:

1. Primary Storage

o RAM (volatile, fastest, expensive)

2. Secondary Storage

o Magnetic disks, SSDs (non-volatile, moderate speed)

3. Tertiary Storage

o Magnetic tapes, optical disks (archival, slowest, cheapest)

Key Concepts:

• Access Time

• Cost per bit

• Volatility

3. Storage Devices Overview

Magnetic Disks
• Data stored on platters with tracks & sectors

• Access via:

o Seek time

o Rotational latency

o Transfer time

Solid-State Drives (SSDs)

• Based on flash memory

• Faster than disks, no moving parts

• Limited write cycles

Optical Storage

• CD/DVD/Blu-ray

• Used for read-heavy workloads

Magnetic Tape

• Used for backup and archival

• Sequential access

4. Improving Disk Access Efficiency

• Block-based storage

• Buffering

• Caching

• Scheduling algorithms (e.g., SCAN, LOOK)

5. Buffer Management & Double Buffering

Buffer:

• Temporary memory area for disk blocks

Double Buffering:

• Two buffers used simultaneously:

 o One for processing

o One for loading next block

Improves I/O throughput

Buffer Replacement Strategies:

• FIFO

• LRU (Least Recently Used)

• MRU

6. File Organization Concepts

File:

• Collection of records

Record:

• Collection of fields (attributes)

Blocking:

• Grouping records into blocks/pages

7. Record Storage Formats

Types:

• Fixed-length records

• Variable-length records

Techniques:

• Spanned vs Unspanned records

• Record pointers

8. File Operations

Common operations:

• Insert
 • Delete

• Update

• Search

• Scan

9. File Organization Methods

9.1 Unordered Files (Heap Files)

• Records stored in no particular order

• Fast insert

• Slow search

Best for: Bulk insert operations

9.2 Ordered Files (Sequential Files)

• Records sorted based on a key

• Efficient for:

o Range queries

o Sequential access

Drawback:

• Expensive insert/delete

9.3 Hashed Files

Concept:

• Use a hash function to map:

Key → Storage Location

Advantages:

• Fast equality search: O(1) average

Issues:
 • Collisions (two keys map to same location)

Collision Resolution:

• Chaining

• Open addressing

• Overflow blocks

10. Advanced File Structures

B-Trees

• Balanced tree structure

• Efficient for:

o Search

o Insert

o Delete

Widely used in database indexing

Files of Mixed Records

• Used in object-oriented databases

• Store complex/nested objects

11. RAID Architecture (Redundant Array of Disks)

Purpose:

• Improve performance + reliability

RAID Levels:

• RAID 0 → Striping (performance)

• RAID 1 → Mirroring (reliability)

• RAID 5 → Parity-based

Benefits:
• Fault tolerance

• Parallel access

12. Modern Storage Architectures

Storage Area Network (SAN)

• High-speed network connecting storage devices

• Block-level access

Network Attached Storage (NAS)

• File-level access over network

• Easy to deploy

iSCSI (Internet SCSI)

• Uses IP networks for storage communication

• Cost-effective alternative to Fibre Channel

13. Advanced Storage Concepts

Storage Tiering

• Data stored across:

o SSD (hot data)

o HDD (warm data)

o Tape (cold data)

Object-Based Storage

• Data stored as objects instead of files

• Used in:

o Cloud storage

o Big data systems

14. Importance for Query Processing

• File organization directly impacts:

o Query execution time

o Index efficiency

o Optimization techniques

Foundation for:

• Query processing (Chapter 18)

• Query optimization (Chapter 19)

15. Summary

• Databases rely on efficient physical storage structures

• Key techniques:

o Buffering

o File organization

o Hashing

o Indexing

• Modern systems use:

o RAID

o SAN/NAS

o Cloud/object storage
Lecture Notes – 16.1 Introduction

Disk Storage & Storage Organization in Databases

1. Need for Physical Storage

• A database is a collection of persistent data stored on physical media.

• The DBMS (Database Management System):

o Retrieves data

o Updates data

o Processes queries

Data must be stored efficiently to ensure:

• Fast access

• Reliability

• Scalability

2. Storage Hierarchy in Computer Systems

Storage systems are organized into a hierarchy based on speed, cost, and capacity.

Categories of Storage:

2.1 Primary Storage (Main Memory)

Examples:

• Cache memory (SRAM)

• Main memory (DRAM)

Characteristics:

• Directly accessible by CPU

• Very fast access

• Limited capacity

• Expensive
• Volatile (data lost on power failure)

Memory Types:

• Cache (SRAM)

o Fastest

o Used for instruction execution optimization

• DRAM (Main Memory)

o Slower than cache

o Cheaper

o Used for program execution

2.2 Secondary Storage

Examples:

• Magnetic disks (HDD)

• Solid-State Drives (SSD)

Characteristics:

• Non-volatile

• Larger capacity

• Lower cost than primary storage

• Moderate access speed

SSD (Flash Memory Based):

• Faster than HDD

• No moving parts

• Uses EEPROM technology

• Requires block-level erase/write

2.3 Tertiary Storage (Offline Storage)

Examples:
• Optical disks (CD, DVD, Blu-ray)

• Magnetic tapes

Characteristics:

• Very large capacity

• Lowest cost

• Slowest access

• Used for:

o Backup

o Archival

3. Memory Hierarchy Concept

Key Principle:

• Higher speed → Higher cost → Lower capacity

• Lower speed → Lower cost → Higher capacity

Storage Units:

• KB (10³ bytes)

• MB (10⁶ bytes)

• GB (10⁹ bytes)

• TB (10¹² bytes)

• PB (10¹⁵ bytes)

4. Database Storage Behavior

Key Observations:

• Databases are large and persistent

• Stored mainly on secondary storage (disks)

Why Not Main Memory?

1. Limited capacity
2. Volatile nature

3. High cost

5. Main Memory Databases

• Entire database stored in RAM

• Used in:

o Real-time systems

o Telecom switching

Advantages:

• Extremely fast access

Limitation:

• Requires backup (usually disk)

6. Flash Memory

Characteristics:

• Non-volatile

• Faster than disks

• Slower than DRAM

Types:

• NAND Flash → High capacity (used in SSDs, USB drives)

• NOR Flash → Faster read, lower density

Applications:

• Mobile phones

• USB drives

• Cameras

7. Optical Storage
Types:

• CD-ROM (Read-only)

• CD-R / DVD-R (Write Once Read Many – WORM)

• Blu-ray (High capacity)

Features:

• Long lifespan

• Suitable for archiving

• Slower than disks

8. Magnetic Tape Storage

Features:

• Sequential access

• Very low cost

• Very high capacity

Usage:

• Backup systems

• Archival storage

9. Persistent vs Transient Data

Persistent Data:
• Stored long-term (databases)

• Survives system restarts

Transient Data:

• Temporary

• Exists only during program execution

10. Why Databases Use Secondary Storage

1. Large size of databases

2. Non-volatility (data safety)

3. Cost efficiency

Hence:

• Disk = Primary storage medium for databases

11. Database Storage Organization

Data Organization:

• Stored as files

• Files consist of records

• Records consist of fields

Data Access Process:

1. Locate data on disk

2. Load into main memory

3. Process by CPU

4. Write back if modified

12. Role of DBMS in Storage

DBMS Responsibilities:
 • Manage disk storage

• Optimize data placement

• Provide access methods

13. Physical Database Design

Definition:

Choosing efficient storage structures and file organizations

Goal:

• Improve performance

• Reduce access time

14. File Organization Techniques

Heap File (Unordered)

• Records stored randomly

• Fast insert

• Slow search

Sequential File (Ordered)

• Records sorted by key

• Efficient for range queries

Hashed File

• Uses hash function:

Key → Address

• Fast direct access

Tree-Based Structures
 • Example: B-Trees

• Balanced search trees

15. Secondary (Auxiliary) Structures

Purpose:

• Improve access efficiency

Examples:

• Indexes

• Access paths

Covered in detail in next chapter

16. Key Takeaways

✔ Storage hierarchy balances speed, cost, and capacity

✔ Databases mainly reside on secondary storage
✔ Data must be moved to main memory for processing
✔ File organization determines access efficiency
✔ Physical design is crucial for performance tuning
Lecture Notes – 16.2 Secondary Storage Devices

1. Overview

• Secondary storage devices are used to store large volumes of persistent data.

• Main types covered:

o Magnetic Disks (HDD)

o Solid-State Drives (SSD)

o Magnetic Tapes

These devices are essential because:

• Databases are too large for main memory

• Data must persist long-term

16.2.1 Hardware Description of Disk Devices

1. Magnetic Disk Basics

• Stored in a Hard Disk Drive (HDD)

• Data stored as:

o Bits (0/1) → grouped into bytes (8 bits)

Disk Capacity:

• Measured in:

o GB (Gigabytes)

o TB (Terabytes)
2. Disk Structure

Components:

• Platters (circular disks)

• Tracks → concentric circles

• Sectors → subdivisions of tracks

• Blocks → group of sectors (unit of transfer)

Key Terms:

• Track → circular path

• Sector → smallest physical storage unit

• Cylinder → same track across multiple platters

Cylinder concept improves performance:

• No head movement required

3. Disk Addressing

Methods:

1. CHB Addressing

o Cylinder

o Head (track/surface)

o Block

2. LBA (Logical Block Addressing)

o Linear numbering of blocks

o Used in modern systems

4. Disk Operations

Read/Write Process:

1. Move head to track → Seek Time

2. Wait for sector rotation → Rotational Delay

 3. Transfer data → Transfer Time

Total Access Time:

Access Time = Seek Time + Rotational Delay + Transfer Time

Important:

• Seek time & latency dominate performance

5. Disk Components

Key Hardware:

• Read/Write Head

• Actuator Arm

• Spindle Motor

• Disk Controller

6. Disk Types

Movable Head Disk

• Heads move across tracks

• Most common

Fixed Head Disk

• One head per track

• Faster but expensive

7. Disk Interfaces

Common Interfaces:

• SATA (Serial ATA) → widely used

• SAS (Serial Attached SCSI) → enterprise systems

Performance:

• SAS > SATA (in IOPS and performance)

 8. Disk Performance Issues

Bottleneck:

• Disk access time (milliseconds)

• Much slower than CPU (nanoseconds)

Solution:

• Optimize data placement

• Reduce disk I/O

16.2.2 Improving Disk Access Efficiency

Techniques:

1. Buffering

• Store disk data temporarily in RAM

• Reduces CPU–disk speed mismatch

2. Data Organization

• Store related data in:

o Contiguous blocks

o Same cylinder

Reduces seek time

3. Read-Ahead (Prefetching)

• Load extra blocks in advance

• Works well for sequential access

4. Disk Scheduling
 Elevator Algorithm:

• Moves disk arm in one direction

• Services requests along the path

Reduces arm movement

5. Log Disk for Writes

• Sequential write storage

• Avoids random disk writes

6. SSD Buffering for Recovery

• Use fast non-volatile memory

• Prevents data loss during crashes

16.2.3 Solid-State Drives (SSD)

1. Overview

• Based on flash memory

• No moving parts

2. Structure

• Controller + NAND flash chips

3. Advantages

• Faster access time

• Silent operation

• Shock-resistant

• Higher throughput
 4. Differences from HDD

Feature HDD SSD

Moving parts Yes No

Speed Slower Faster

Fragmentation Issue Minimal

Data placement Important Flexible

5. Wear Leveling

• Writes distributed across cells

• Increases lifespan

6. Types of SSD

• NAND Flash SSD

• DRAM-based SSD (faster but expensive)

7. Limitations

• High cost per GB

• Limited write cycles

8. Enterprise SSD (EFD)

• Used in data centers

• High IOPS (up to millions/sec)

• Low latency (~microseconds)

16.2.4 Magnetic Tape Storage

1. Overview

• Sequential access storage

• Used for backup and archival

2. Characteristics

Advantages:

• Very low cost

• Very high capacity

• Long-term storage

Disadvantages:

• Slow access

• Sequential only

3. Working

• Data stored in blocks

• Requires:

o Tape drive

o Sequential scanning

4. Use Cases

• Database backup

• Historical data storage

• Disaster recovery

5. Tape Technologies

Examples:

• LTO (Linear Tape Open)

• DLT / SDLT
 6. Tape Libraries

• Robotic systems

• Store thousands of tapes

• Used in large enterprises

7. Backup Strategies

• Periodic disk → tape backup

• Mirrored disk systems

• Rotation strategy

16.2 Key Takeaways

✔ HDDs are primary secondary storage for databases

✔ Disk access time is a major bottleneck
✔ Efficient data placement improves performance
✔ SSDs provide high-speed alternatives
✔ Magnetic tapes are ideal for backup & archival
Lecture Notes – 16.3 Buffering of Blocks

1. Introduction to Buffering

• Buffering is the process of temporarily storing disk blocks in main memory

(RAM).

• Used to bridge the speed gap between:

o Fast CPU

o Slow disk (I/O operations)

Goal: Improve data transfer efficiency and system performance

2. Why Buffering is Needed

• Disk operations are slow (milliseconds)

• CPU operations are fast (nanoseconds)

• Direct interaction causes CPU idle time

Solution: Use buffers to:

• Overlap I/O and computation

• Enable parallelism
3. Parallelism in Buffering

Types of Execution:

• Concurrent (Interleaved) → Single CPU

• Parallel Execution → Multiple processors or I/O controller

Buffering works best when:

• Disk I/O and CPU processing occur simultaneously

4. Double Buffering Technique

Concept:

• Use two buffers:

o Buffer 1 → CPU processes data

o Buffer 2 → Disk loads next block

After processing:

• Buffers switch roles

Advantages:

• Eliminates CPU waiting time

• Supports continuous data flow

• Reduces:
 o Seek time

o Rotational delay (for sequential blocks)

Working:

1. Disk reads Block A → Buffer 1

2. CPU processes Buffer 1

3. Disk reads Block B → Buffer 2

4. CPU processes Buffer 2

Cycle continues

5. Continuous Block Transfer

• Double buffering enables:

o Sequential reading/writing

o Efficient processing of large files

16.3.1 Buffer Management

6. Buffer Manager

Definition:

A DBMS component responsible for:

• Managing memory buffers

• Allocating space for disk blocks

• Deciding which pages to replace

7. Buffer Pool

• Collection of memory pages (buffers)

• Controlled by DBMS
 • Size determined by DBA

8. Types of Buffer Managers

1. Direct Memory Control

• DBMS manages RAM directly

• Used in most RDBMS

2. Virtual Memory Control

• OS manages memory

• Used in:

o Main memory DBMS

o Object-oriented DBMS

9. Goals of Buffer Manager

1. Maximize cache hits (page found in memory)

2. Minimize disk I/O

3. Replace pages intelligently

10. Buffer Metadata

Each page in buffer pool maintains:

1. Pin Count

• Number of users accessing the page

• If pin-count > 0 → page is pinned

• If pin-count = 0 → page is unpinned

Pinned pages cannot be replaced

2. Dirty Bit
 • Indicates if page is modified

Value Meaning

0 Not modified

1 Modified (must write to disk)

11. Page Request Handling

Case 1: Page already in buffer

• Increase pin-count

• Return page

Case 2: Page not in buffer

Steps:

1. Select a page to replace

2. If dirty → write to disk

3. Load new page into buffer

4. Return page to application

12. Buffer Overflow Issue

• If no unpinned page available:

o Process must wait

o Or transaction may be aborted

13. Thrashing

• Occurs when:

o Buffer size is too small

o Frequent swapping between disk and memory

Result: Performance degradation

16.3.2 Buffer Replacement Strategies

14. Need for Replacement Policy

• Buffer pool is limited

• Must decide:
Which page to remove?

15. Replacement Strategies

1. LRU (Least Recently Used)

Idea:

• Replace page not used for longest time

Advantage:

• Good for locality of reference

Disadvantage:

• Overhead of tracking usage time

2. Clock Policy (Second Chance)

Concept:

• Circular buffer with flags (0 or 1)

Working:

• If flag = 1 → set to 0 and skip

• If flag = 0 → replace page

Efficient approximation of LRU

3. FIFO (First-In-First-Out)
Idea:

• Replace oldest page

Advantage:

• Simple implementation

Disadvantage:

• May remove frequently used pages

4. MRU (Most Recently Used)

Idea:

• Replace most recently used page

Use Case:

• Sequential scans

16. Limitations of Standard Policies

• Not ideal for:

o Sequential file access

o Large datasets

• May remove important pages (e.g., index root)

17. Advanced Considerations

Pinned Pages:

• Cannot be replaced

Priority Buffers:

• Important pages retained longer

Force Writing:

• Pages written to disk even if not replaced

• Used in recovery mechanisms

 18. Key Takeaways

✔ Buffering improves CPU–disk interaction

✔ Double buffering enables parallel processing
✔ Buffer manager controls memory efficiently
✔ Replacement strategies impact performance
✔ Poor buffer management leads to thrashing
Lecture Notes – 16.4 Placing File Records on Disk

1. Introduction

• Database data is stored as:

o Files → Records → Fields

• These records must be efficiently placed on disk for fast access.

Objective:

• Optimize storage utilization

• Improve retrieval performance

16.4.1 Records and Record Types

2. Record Concept

Record:

• A collection of related data fields

• Represents an entity

Example:

EMPLOYEE Record

• Name

• SSN

• Salary

• Department

3. Record Type (Schema)

• Defines:

o Field names

o Data types
 Example (C structure):

struct employee {
char name[30];
char ssn[9];
int salary;
int job_code;
char department[20];
};

4. Data Types

Type Description

Integer Numeric values

Float Real numbers

String Characters

Boolean TRUE/FALSE

Date YYYY-MM-DD

5. Large Data Objects

BLOB (Binary Large Object)

• Stores:

o Images

o Videos

o Audio

• Stored separately

• Record contains pointer

CLOB (Character Large Object)

• Stores large text

• Used in DBMS like Oracle, DB2

16.4.2 Files and Record Types

6. File Concept

• A file = collection of records

• Usually same record type

7. Types of Records

Fixed-Length Records

Features:

• Same size for all records

• Easy to access

• Fast processing

Advantages:

• Direct field access

• Simple structure

Disadvantages:

• Wastes space (unused fields)

Variable-Length Records

Reasons:

1. Variable-length fields (e.g., name)

2. Repeating fields

3. Optional fields

4. Mixed record types

 8. Variable Record Storage Techniques

1. Delimiters

• Use special characters to separate fields

2. Length Indicators

• Store field size before value

3. Field-Value Pairs

• Format:

<field-type, field-value>

4. Record Type Indicator

 • Used for mixed records

16.4.3 Record Blocking

9. Blocking Concept

• Disk transfers occur in blocks

• Multiple records stored in one block

10. Blocking Factor (bfr)

Formula:
𝐵
𝑏𝑓𝑟 = ⌊ ⌋
𝑅
Where:

• B = Block size (bytes)

• R = Record size (bytes)

11. Unused Space

• If records don’t perfectly fit:

Unused space = B − (bfr × R)

12. Spanned vs Unspanned Records

Unspanned Organization

• Record fits within one block

• No splitting

Simple
Wastes space
 Spanned Organization

• Record can span multiple blocks

Better space utilization

More complex processing

13. Number of Blocks Required

Formula:
𝑟
𝑏=⌈ ⌉
𝑏𝑓𝑟

Where:

• r = number of records

• bfr = blocking factor

16.4.4 File Block Allocation Methods

14. Allocation Techniques

1. Contiguous Allocation

• Blocks stored sequentially

Fast access
Difficult to expand

2. Linked Allocation
• Each block points to next

Easy expansion
Slow traversal

3. Indexed Allocation

• Index block stores pointers

Direct access
Extra storage overhead

4. Clustered Allocation

• Groups of contiguous blocks (extents)

Combines benefits of above methods

16.4.5 File Headers

15. File Header (Metadata)

Contains:

• File location (disk addresses)

• Record format

• Field details

• Block organization

16. Searching for Records

Process:

1. Load block into buffer

2. Search records in memory

 Problem:

• If block location unknown → Linear search

Inefficient for large files

17. Goal of File Organization

• Minimize:

o Disk I/O

o Block transfers

• Avoid:

o Full file scans

18. Key Takeaways

✔ Records represent real-world entities

✔ Files store collections of records
✔ Fixed vs variable-length affects performance
✔ Blocking improves storage efficiency
✔ Allocation methods impact access speed
✔ File headers help in record retrieval
Lecture Notes – 16.5 Operations on Files

1. Introduction

• File operations define how records are accessed and manipulated in a

database.

• Two main categories:

Types of Operations:

1. Retrieval Operations

o Do not modify data

o Used to search and read records

2. Update Operations

o Modify the file contents:

▪ Insert

▪ Delete

▪ Update

2. Selection Conditions (Filtering)

• Used to identify specific records

• Based on field values

Examples:

• (Ssn = '123456789')

• (Department = 'Research')

• (Salary ≥ 30000)

3. Types of Conditions

Simple Condition

• Single comparison

Salary ≥ 30000
 Complex Condition

• Combination using Boolean operators

(Salary ≥ 30000) AND (Department = 'Research')

4. Search Strategy

Steps:

1. Extract simple condition

2. Locate records using simple condition

3. Apply full condition check

Improves efficiency

5. Current Record Concept

• First matching record → Current Record

• Next operations continue from this point

6. Record-at-a-Time Operations

6.1 Open

• Prepares file for use

• Allocates buffers

• Loads file header

• Sets pointer to start

6.2 Reset

• Moves pointer to beginning of file

6.3 Find (Locate)

• Searches first record satisfying condition

• Loads block into buffer

• Sets current record

6.4 Read (Get)

• Copies current record to program

• May move pointer to next record

6.5 FindNext

• Finds next record satisfying condition

• Continues search from current position

6.6 Delete

• Removes current record

• Updates disk file

6.7 Modify

• Updates field values

• Writes changes to disk

6.8 Insert

• Adds new record

• Steps:

1. Locate target block

2. Load block into buffer

3. Insert record

4. Write back to disk

6.9 Close

• Releases buffers

• Ends file access

7. Scan Operation

Definition:

• Combines Find + Read + FindNext

Behavior:

• Returns:

o First record (if new/reset)

o Next record (otherwise)

Can include condition filtering

8. Set-at-a-Time Operations

8.1 FindAll

• Retrieves all matching records

8.2 Find n

• Retrieves first n matching records

8.3 FindOrdered

• Retrieves records in sorted order

8.4 Reorganize

• Reorders file structure

 • Example:

o Sorting records

o Defragmentation

9. File Organization vs Access Method

File Organization

• How data is stored:

o Records

o Blocks

o Structure

Access Method

• Operations used to access data:

o Find

o Read

o Insert

Key Difference:

Aspect File Organization Access Method

Focus Storage structure Data access

Example Heap, Sorted, Hashed Indexed access

10. Static vs Dynamic Files

Static Files

• Rare updates
• Mostly read-only

Example:

• Data warehouses

Dynamic Files

• Frequent updates

• Insert/Delete/Modify common

Example:

• Transaction systems

11. Design Considerations

Important Factors:

• Frequency of operations:

o Search

o Insert

o Delete

• Type of queries

• Performance requirements

12. Example: EMPLOYEE File

Scenario 1:

• Search by SSN
Use:

• Ordered file

• Index on SSN

Scenario 2:
 • Group by Department
Use:

• Sorted by department

Conflict:

• Cannot optimize for all queries simultaneously

DBA must choose:

• Best compromise

13. Key Challenges

• Single file organization:

o Cannot satisfy all operations efficiently

• Trade-offs required:

o Retrieval vs update performance

14. Key Takeaways

✔ File operations enable data access and modification

✔ Selection conditions control record retrieval
✔ Record-at-a-time vs set-at-a-time operations
✔ File organization affects performance
✔ DBAs must balance conflicting requirements
Lecture Notes – 16.6 Files of Unordered Records (Heap Files)

1. Introduction

• Heap file (Unordered file):

o Simplest file organization

o Records stored in the order of insertion

o No sorting or ordering

New records are always added at the end of the file

2. Key Characteristics

• No ordering based on any field

• Easy and fast insertion

• Poor search performance

• Often used with indexes (secondary access paths)

3. Insertion Operation

Steps:

1. Locate last disk block (from file header)

2. Load block into buffer

3. Insert new record

4. Write block back to disk

Advantage:

• Very fast → O(1) (approx.)

4. Searching in Heap Files

Method:

• Linear search (Sequential scan)

 Cost:

• For b blocks:

o Average case → b/2 blocks

o Worst case → b blocks

Very inefficient for large files

5. Deletion Techniques

Method 1: Physical Deletion

Steps:

1. Find record

2. Remove from block

3. Rewrite block

Issue:

• Leaves empty space (fragmentation)

Method 2: Deletion Marker

• Add a flag/bit to each record

Value Meaning

0 Valid record

1 Deleted record

Advantage:

• Faster deletion

• No immediate rewriting

6. File Reorganization

Purpose:
• Remove deleted records

• Reclaim space

Process:

• Read blocks sequentially

• Pack valid records

• Rewrite file

7. Handling Free Space

• Reuse deleted record spaces during insertion

• Requires:

o Extra bookkeeping

o Free space tracking

8. Record Types Supported

• Fixed-length records

• Variable-length records

9. Spanned vs Unspanned

• Heap files can use:

o Spanned records

o Unspanned records

10. Record Modification

Issue:

• Modified record size may change

Solution:

• Delete old record

 • Insert updated record

11. Sorting Heap Files

• Heap files are not ordered

• To read in sorted order:

o Create a sorted copy

Problem:

• Sorting large files is expensive

• Uses external sorting techniques

12. Direct Access (Relative Files)

For fixed-length records:

Formula:
𝑖
Block number = ⌊ ⌋
𝑏𝑓𝑟

Record Position:

Record index in block = 𝑖 𝑚𝑜𝑑 𝑏𝑓𝑟

Where:

• i = record number

• bfr = blocking factor

Advantage:

• Direct access by position

Limitation:

• Cannot search using conditions (e.g., name, salary)

13. Advantages of Heap Files

✔ Simple implementation
✔ Fast insertion
✔ Flexible (supports all record types)
✔ Good for bulk data loading

14. Disadvantages of Heap Files

Slow search (linear scan)

Poor performance for large files
Fragmentation due to deletions
Requires periodic reorganization

15. Use Cases

• Temporary data storage

• Bulk data collection

• Systems with:

o Frequent inserts

o Rare searches

16. Key Takeaways

✔ Heap files store records without order

✔ Best for insertion-heavy workloads
✔ Search operations are expensive
✔ Deletion creates fragmentation
✔ Often combined with indexes for efficiency
Lecture Notes: 16.7 Files of Ordered Records (Sorted Files)

1. Definition

• A sorted (ordered) file stores records physically ordered on disk based on a

specific field.

• This field is called the ordering field.

If the ordering field has unique values, it is called the:

• Ordering Key

2. Example
• EMPLOYEE file ordered by:

o Name → records stored alphabetically

o Employee_ID → records stored numerically

3. Advantages of Ordered Files

Efficient Sequential Access

• Records can be read directly in sorted order

• No need for sorting during query execution

Efficient Range Queries

• Queries like:

o Salary > 50000

o A < Name < M

• Records satisfying condition are stored contiguously

Faster Search using Binary Search

• Instead of scanning entire file:

o Use binary search on blocks

Performance:

• Binary search → log₂(b) block accesses

• Linear search → b/2 (avg), b (worst)

Efficient Next Record Access

• Once a record is found:

o Next record is usually in same block

o No additional disk access needed

 4. Binary Search on Disk Files

Concept

• Search is done on blocks (not individual records)

Algorithm

l ← 1; u ← b

while (u ≥ l)
i ← (l + u) / 2
read block i

if K < first key in block i

u←i-1
else if K > last key in block i
l←i+1
else
search within block

Cost

• log₂(b) block accesses

5. Disadvantages of Ordered Files

Expensive Insertions

• Must maintain order

• Requires:

o Finding correct position

o Shifting records

Cost:

• On average, half the file must be moved

Expensive Deletions
• Requires:

o Shifting records OR

o Using deletion markers

Costly Updates

• If ordering field changes:

o Record must be:

▪ Deleted

▪ Reinserted at correct position

Poor Performance for Non-Key Searches

• If search is based on:

o Non-ordering field → linear search required

6. Optimization Techniques

1. Free Space in Blocks

• Keep empty space for future inserts

Limitation:

• Eventually fills up → problem returns

2. Overflow File (Very Important)

• Maintain:

o Main File (sorted)

o Overflow File (unsorted)

Working

• New records → added to overflow file

 • Periodically:

o Overflow file is:

▪ Sorted

▪ Merged with main file

Advantages

• Fast insertions

Disadvantages

• Search becomes complex:

o Must search:

▪ Main file (binary search)

▪ Overflow file (linear search)

7. Performance Summary

Operation Performance

Search (key) Fast (Binary search)

Range query Very efficient

Insert Expensive

Delete Moderate

Update (key field) Expensive

8. Comparison with Heap Files

Feature Ordered File Heap File

Insert Slow Very fast

Search Fast (key) Slow

Feature Ordered File Heap File

Range Query Efficient Inefficient

Maintenance High Low

9. Indexed Sequential Files

• Ordered files are often combined with:

o Primary Index

Result:

• Faster search

• Efficient access

10. Clustered Files

• If ordering field is not unique:

o File is called a:

▪ Clustered File

11. Key Exam Points

• Definition of ordered file

• Binary search on disk

• Advantages vs disadvantages

• Overflow file concept

• Cost comparison (log₂(b) vs b/2)

• Insert/delete complexity

12. Conclusion

• Ordered files provide:

o Fast search and range queries

• But suffer from:

o High update cost

• Best used when:

o Data is mostly read-only

o Queries involve ordering field

Lecture Notes: 16.8 Hashing Techniques

Introduction to Hashing

Hashing is a primary file organization technique used to provide very fast access to
records when searching with an equality condition on a single field.

• The field used for searching is called the Hash Field

• If it is also a unique key, it is called the Hash Key

• A Hash Function h(K) maps a key value into a storage address or bucket.

Example:

If h(K) = K mod M

For K = 123, M = 10

Then:

123 mod 10 = 3

So record is stored in location 3

16.8.1 Internal Hashing

Used when records are stored in main memory using arrays.

• Array index ranges from 0 to M-1

• Each position is called a slot

Common Hash Function

ℎ(𝐾) = 𝐾 𝑚𝑜𝑑 𝑀

Where:

• K = Key

• M = Number of slots
Hashing Strings

Character strings can be converted into numbers using ASCII values.

Example Algorithm:

temp = 1
For each character:
temp = temp × code(character) mod M
hash_address = temp mod M

Collision in Hashing

A collision occurs when two different keys map to the same address.

Example:
If:

• h(25)=5

• h(35)=5

Then collision occurs.

Collision Resolution Techniques

1. Open Addressing

Search next free location sequentially.

Example:

If slot 5 occupied:

Check 6 → 7 → 8 ...

2. Chaining

Use linked list of overflow records.

Slot 5 → Record A → Record B → Record C

3. Multiple Hashing

Use second hash function if first causes collision.

h1(K)
If full → h2(K)

Good Hash Function Goals

1. Uniform distribution of records

2. Minimum collisions

3. Efficient space usage

Recommended Fill Factor:

70% to 90%
𝑟
= 0.7 to 0.9
𝑀
Where:

• r = number of records

• M = number of locations

16.8.2 External Hashing for Disk Files

Used for disk storage.

Instead of single record locations, storage uses Buckets

Bucket

A bucket may contain:

• One disk block OR

• Multiple contiguous blocks

Hash function maps key to bucket number

Advantages

• Many records can fit in one bucket

• Reduces collision problem

Overflow Handling

If bucket becomes full:

Use overflow chain with pointers.

Bucket 2 → Overflow Block → Overflow Block

Operations in External Hashing

Search

Fast if searching by hash key.

Delete

• Remove record from bucket

 • Replace with overflow record if needed

Update

• Non-hash field: modify in same bucket

• Hash field: delete old record + insert new record

Static Hashing

Uses fixed number of buckets M

Problems

If records are fewer:

Unused space

If records are more:

Too many collisions

Reorganization Needed

Need new hash function and redistribute records.

16.8.3 Dynamic Hashing Techniques

Used when file grows or shrinks dynamically.

Types:

1. Extendible Hashing

2. Dynamic Hashing

3. Linear Hashing

1. Extendible Hashing

Uses a directory of bucket pointers.

Directory size:

2𝑑

Where:

• d = Global Depth

Uses first d bits of hash value.

Terms
Global Depth (d)

Number of bits used for directory indexing.

Local Depth (d')

Number of bits identifying a bucket.

Bucket Split

When bucket overflows:

• Split into two buckets

• Increase local depth

If local depth = global depth:

• Double directory size

Advantages

• Performance does not degrade as file grows

• Only local reorganization

• Dynamic expansion

Disadvantage

Requires two accesses:

1. Directory

2. Bucket
2. Dynamic Hashing

Uses binary tree directory.

Nodes:

Internal Node

• Left pointer = 0 bit

• Right pointer = 1 bit

Leaf Node

Points to actual bucket.

Advantage
Efficient bucket management with tree structure.

3. Linear Hashing

No directory required.

Uses gradual bucket splitting.

Initial buckets:

0,1,2,...,M-1

Initial hash:

ℎ𝑖 (𝐾) = 𝐾 𝑚𝑜𝑑 𝑀

When Overflow Occurs

Split buckets in linear order:

0,1,2,3...

New bucket added at end.

New hash function:

ℎ𝑖+1 (𝐾) = 𝐾 𝑚𝑜𝑑 2𝑀

Search Procedure

If:

• h(K) < n

Then use next hash function.

Where:

• n = number of buckets already split

Load Factor
𝑟
𝑙=
𝑏𝑓𝑟 × 𝑁
Where:

• r = number of records

• bfr = bucket capacity

• N = number of buckets

Split Threshold

If load > 0.9 → Split

Merge Threshold

If load < 0.7 → Combine

Advantages of Linear Hashing

• No directory needed

• Dynamic growth/shrinkage
 • Good space utilization

• Controlled load factor

Comparison Table

Technique Directory Expansion Speed

Static Hashing No No Fast initially

Extendible Hashing Yes Yes Very Fast

Dynamic Hashing Tree Yes Fast

Linear Hashing No Yes Efficient

Key Terms

Term Meaning

Hash Function Maps key to address

Collision Two keys same address

Bucket Block storing multiple records

Overflow Extra storage when full

Global Depth Bits used in directory

Local Depth Bits identifying bucket

Load Factor File fullness ratio

Lecture Notes: 16.9 Other Primary File Organizations

Introduction

Primary file organization determines how records are stored physically on disk for
efficient retrieval and update.

Earlier methods studied:

• Heap files

• Ordered files

• Hash files

This section introduces other primary file organizations, namely:

1. Files of Mixed Records

2. B-Trees and Other Data Structures as Primary Organization

16.9.1 Files of Mixed Records

Meaning

So far, we assumed one file contains records of only one record type.

Examples:

• EMPLOYEE file → only employee records

• STUDENT file → only student records

• DEPARTMENT file → only department records

But in real database applications, multiple entity types are related to each other.

Interrelated Records

Example:

A STUDENT record may contain:

Major_dept = CSE

This refers to a DEPARTMENT record.

So:

• STUDENT and DEPARTMENT records are related.

 • Relationships are maintained through connecting fields.

Logical Relationships

When records are stored in separate files:

1. Retrieve STUDENT record first

2. Read Major_dept

3. Search DEPARTMENT file using that value

This is called a logical reference relationship.

Physical Relationships in DBMS

Some systems physically store related records together.

Used in:

• Object DBMS

• Hierarchical DBMS

• Network DBMS

• Legacy database systems

These systems use:

1. Physical clustering

2. Physical pointers

Physical Clustering

Related records are stored close together on disk.

Example:

DEPARTMENT record
STUDENT record 1
STUDENT record 2
STUDENT record 3

All students belonging to same department stored near department record.

Advantage of Physical Clustering

If query is frequent:

Retrieve department and all students majoring in it

Then clustered storage gives:

• Faster retrieval

• Fewer disk accesses

• Better performance

Mixed File

A mixed file stores records of more than one type in same disk area.

Example:

DEPARTMENT
STUDENT
STUDENT
PROJECT
EMPLOYEE

Use in Object Databases

Object DBMS stores related objects together.

Example:

• Customer object

• Orders object

• Payment object

Stored in clustered mixed files.

Use in Data Warehouses

Data warehouses collect data from multiple sources.

During ETL process:

• Extract
 • Transform

• Load

Data first enters:

ODS (Operational Data Store)

ODS often stores records of multiple types together.

Later transferred into data warehouse.

Identifying Record Types

Since mixed files contain different record types, system must distinguish them.

Each record includes:

Record Type Field

Usually first field in record.

Example:

Type = STUDENT
USN = 101
Name = Ravi

or

Type = DEPARTMENT
Dept = CSE
HOD = Kumar

Role of DBMS Catalog

Using metadata/catalog, DBMS identifies:

• Record type

• Field names

• Field sizes

• Data interpretation

Advantages of Mixed Files

 1. Faster access to related records

2. Reduced disk I/O

3. Efficient for relationship-based queries

4. Useful in object databases and warehouses

Disadvantages of Mixed Files

1. More complex storage management

2. Difficult updates

3. Need type identification field

4. Space organization complexity

16.9.2 B-Trees and Other Data Structures as Primary Organization

Concept

Primary storage can also use advanced data structures.

One important structure:

B-Tree

Used when:

• Number of records is small/moderate

• Record size is small

• Need fast searching/insertion/deletion

What is a B-Tree?

A balanced tree structure used for:

• Searching

• Insertion

• Deletion

It keeps data sorted and balanced.

Why B-Tree as Primary File Organization?

Advantages:

• Fast search using tree traversal

• Efficient updates

• Balanced structure

• Good disk block utilization

Example Structure

50
/ \
20,30 70,90

Records are stored in sorted nodes.

Other Data Structures

Any disk-adaptable structure can be used, such as:

• B+ Trees

• Hash Trees

• Indexed Trees

• Trie-based structures

Column-Based Storage

Modern relational databases may store data by columns instead of rows.

Traditional row storage:

ID Name Age Salary

1 A 20 50000

Column storage:

ID: 1
Name: A
Age: 20
Salary: 50000
Actually stored as separate columns:

ID column
Name column
Age column
Salary column

Advantages of Column Storage

1. Fast analytical queries

2. Better compression

3. Read only required columns

4. Useful in data warehouses

Comparison Table

Organization Best Use Advantage

Mixed File Related record access Faster joins

B-Tree Search/update Balanced fast access

Hash File Equality search Very fast lookup

Column Storage Analytics Fast aggregation

Key Terms

Term Meaning

Mixed File File containing multiple record types

Record Type Field Field identifying type of record

Physical Clustering Related records stored together

Logical Reference Relationship through key field

B-Tree Balanced search tree

ODS Operational Data Store

Lecture Notes: 16.10 Parallelizing Disk Access Using RAID Technology

Introduction

As processor speed and memory capacity increase rapidly, secondary storage (disks)
must also improve in:

• Performance

• Reliability

• Capacity

One major advancement is:

RAID Technology

RAID = Redundant Array of Independent (Inexpensive) Disks

RAID combines multiple disks to act as one logical storage system.

Objectives of RAID

RAID is designed to achieve:

1. Higher performance

2. Better reliability

3. Large storage capacity

4. Parallel disk access

5. Fault tolerance

Why RAID is Needed?

Problem:

CPU and RAM improve faster than disks.

Component Growth Rate

RAM Capacity Very Fast

Processor Speed Very Fast

Disk Access Time Slow

Component Growth Rate

Disk Transfer Rate Moderate

So storage becomes the bottleneck.

Basic Idea of RAID

Use multiple small disks together as:

One large logical disk

This gives:

• Parallel reads/writes

• Faster transfer rate

• Redundancy

Data Striping

RAID uses striping to distribute data across multiple disks.

It improves speed by accessing disks in parallel.

Types:

1. Bit-Level Striping

2. Block-Level Striping

Bit-Level Striping

Each byte is split into bits and bits stored across disks.

Example with 4 disks:

Disk0 → bit0, bit4

Disk1 → bit1, bit5
Disk2 → bit2, bit6
Disk3 → bit3, bit7

Advantage:

High transfer rate.

Block-Level Striping

Entire blocks are distributed across disks.

Formula:

𝐷𝑖𝑠𝑘 = 𝑗 𝑚𝑜𝑑 𝑚

Where:

• j = block number

• m = number of disks

Example with 4 disks:

Block0 → Disk0
Block1 → Disk1
Block2 → Disk2
Block3 → Disk3

Benefits of Striping

1. Faster read/write

2. Parallel I/O

3. Load balancing

4. Better throughput

16.10.1 Improving Reliability with RAID

More disks means more chances of failure.

If one disk has MTBF:

200,000 hours

Then 100 disks fail more often collectively.

MTBF

Mean Time Between Failures

Measures reliability.
More disks = lower overall MTBF.

Redundancy

To avoid data loss, RAID stores extra information.

Methods:

1. Mirroring

2. Parity

3. Error-correcting codes

Mirroring / Shadowing

Same data written to two disks.

Disk A = Original
Disk B = Copy

If Disk A fails, Disk B is used.

Advantages of Mirroring

1. High reliability

2. Faster reads (read from either disk)

3. Easy recovery

Disadvantage:

Requires double storage.

Parity Method

Extra disk stores parity information.

Used to reconstruct lost data.

Example:

Disk1 = A
Disk2 = B
Disk3 = A XOR B
If one disk fails, recover using parity.

Redundancy Placement

Two approaches:

1. Dedicated parity disk

2. Distributed parity across all disks

Distributed parity gives better load balancing.

16.10.2 Improving Performance with RAID

RAID improves performance using striping.

Small Requests

Single block requests can be served by different disks simultaneously.

Large Requests

Multi-block files can be read in parallel from many disks.

More Disks = Better Speed

More disks increase:

• Throughput
 • Parallelism

• Response time improvement

But reliability decreases without redundancy.

16.10.3 RAID Organizations and Levels

Different RAID levels combine:

• Striping granularity

• Redundancy method

RAID Levels Overview

RAID Level Method Fault Tolerance Speed

RAID 0 Striping only No Very High

RAID 1 Mirroring Yes High

RAID 2 Hamming Code Yes Moderate

RAID 3 Byte striping + parity disk Yes High

RAID 4 Block striping + parity disk Yes Good

RAID 5 Block striping + distributed parity Yes Very Good

RAID 6 Block striping + dual parity Yes (2 failures) Good

RAID 0

Features:

• Data striping only

• No redundancy

Advantages:

• Fastest writes

• Maximum capacity

Disadvantage:
If one disk fails → data lost

RAID 1

Features:

• Mirrored disks

Disk1 = Data
Disk2 = Copy

Advantages:

• Excellent reliability

• Faster reads

Used For:

Critical systems, logs

RAID 2

Uses Hamming codes for error correction.

Rarely used today.

RAID 3

Uses:

• Byte-level striping

• Single parity disk

Good for large sequential data transfer.

RAID 4

Uses:

• Block-level striping

• Dedicated parity disk

RAID 5

Most popular RAID.

Uses:

• Block striping

• Distributed parity

Parity spread across all disks.

Advantages:

• Good read speed

• Good reliability

• Better than RAID 4

RAID 6

Uses:

• Dual parity (P + Q)

• Reed-Solomon codes

Can survive:

Failure of any two disks

Rebuilding Failed Disk

When disk fails:

• RAID 1: easiest rebuild

• RAID 5/6: reconstruct using parity

RAID Combinations

RAID 0 + 1

Combines:

• Striping

• Mirroring
Minimum 4 disks required.

Popular RAID in Industry

Most common:

• RAID 0

• RAID 1

• RAID 5

• RAID 10 (1+0)

Example Diagram

RAID 5 (4 Disks)

Disk1 Disk2 Disk3 Disk4

A1 A2 A3 P(A)
B1 B2 P(B) B3
C1 P(C) C2 C3

Advantages of RAID

1. Faster disk access

2. Parallel operations

3. Fault tolerance
 4. Better reliability

5. Scalable storage

Disadvantages of RAID

1. Higher cost

2. Complex setup

3. Rebuild time after failure

4. Extra storage needed for parity/mirror

Comparison Table

RAID Min Disks Performance Reliability

0 2 Excellent None

1 2 Good Excellent

5 3 Very Good Good

6 4 Good Excellent

Key Terms

Term Meaning

Striping Splitting data across disks

Mirroring Duplicate copy of data

Parity Redundant recovery data

MTBF Mean Time Between Failures

Fault Tolerance Continue operation after failure

Lecture Notes: 16.11 Modern Storage Architectures

Introduction

Modern enterprises generate huge amounts of data from:

• Databases

• E-commerce

• ERP systems

• Data Warehouses

• Multimedia Applications

• Cloud Services

To manage this data efficiently, modern storage architectures are used.

Main Modern Storage Architectures

1. Storage Area Networks (SAN)

2. Network-Attached Storage (NAS)

3. iSCSI and Network Storage Protocols

4. Automated Storage Tiering (AST)

5. Object-Based Storage

16.11.1 Storage Area Networks (SAN)

Definition

A Storage Area Network (SAN) is a high-speed network that connects servers to

storage devices.

Storage devices act as nodes on a separate network.

Why SAN is Needed?

Traditional server-attached storage has problems:

• Difficult to manage

• Fixed storage allocation

 • Poor utilization

• High management cost

SAN solves these issues.

SAN Architecture

Servers ↔ SAN Switch ↔ RAID / Disk Arrays / Tape Libraries

Uses:

• Fibre Channel (FC)

• High-speed connectivity

Features of SAN

1. Many-to-many server-storage connection

2. Flexible attachment/detachment of storage

3. Centralized storage management

4. High performance

5. Better scalability

Advantages of SAN

• Storage can be shared by many servers

• Easy expansion

• Better backup and disaster recovery

• Long-distance storage connection (up to 10 km)

SAN Replication

Two types:

1. Synchronous replication → local copies

2. Asynchronous replication → disaster recovery sites

Disadvantages of SAN

• High cost

• Complex setup

• Vendor compatibility issues

16.11.2 Network-Attached Storage (NAS)

Definition

A NAS device is a dedicated file storage server connected to a LAN.

Used mainly for file sharing.

NAS Architecture

Clients → LAN → NAS Head → Storage Disks

NAS box provides access to files.

Characteristics of NAS

• No monitor/keyboard/mouse needed

• Easy installation

• File-level storage access

• Shared by multiple users

Stores Files Such As

• Email boxes

• Web content

• Backups

• Shared folders

• Multimedia files

Protocols Used by NAS

 • NFS (Network File System)

• CIFS (Common Internet File System)

Advantages of NAS

1. Low cost

2. Easy management

3. Expandable storage

4. Good for file sharing

SAN vs NAS

Feature SAN NAS

Access Type Block level File level

Network Fibre Channel Ethernet/LAN

Speed Very High Moderate

Complexity High Low

Best For Databases File Sharing

16.11.3 iSCSI and Other Network Storage Protocols

iSCSI

Definition

iSCSI = Internet Small Computer System Interface

It sends SCSI commands over IP networks.

Benefits of iSCSI

• Uses existing Ethernet network

• No expensive Fibre Channel cables

• Long-distance storage access

 • Lower cost than SAN

How iSCSI Works

DBMS Request → OS → SCSI Command → IP Packet → Ethernet → Storage Device

Used Over

• LAN

• WAN

• Internet

Advantages of iSCSI

1. Low cost

2. Easy implementation

3. Uses standard IP networks

4. Popular in small/medium businesses

Other Network Storage Protocols

FCIP

Fibre Channel over IP

Used to connect distant SANs.

FCoE

Fibre Channel over Ethernet

Combines Fibre Channel with Ethernet.

High performance with 10 Gigabit Ethernet.

Comparison
Protocol Uses IP Uses FC Cost

iSCSI Yes No Low

FCIP Yes Yes High

FCoE No TCP/IP Yes Medium

16.11.4 Automated Storage Tiering (AST)

Definition

Automatically moves data among storage devices based on usage frequency.

Storage Tiers

From slowest to fastest:

1. SATA drives

2. SAS drives

3. SSD drives

Working Principle

• Frequently used data → SSD

• Moderately used data → SAS

• Rarely used data → SATA

Example

Hot Data → SSD

Warm Data → SAS
Cold Data → SATA

Advantages of AST

1. Better performance

2. Lower cost
 3. Efficient storage utilization

4. Automatic optimization

Example Product

EMC FAST = Fully Automated Storage Tiering

16.11.5 Object-Based Storage

Definition

Stores data as objects instead of files or blocks.

Each object contains:

1. Data

2. Metadata

3. Unique ID

Structure of Object

Object =
[Data + Metadata + Global Identifier]

Why Object Storage?

Needed for:

• Cloud systems

• Big data

• Web-scale applications

• Massive unstructured data

Examples of Unstructured Data

• Photos

• Videos
 • Songs

• Web pages

• Backups

Advantages of Object Storage

1. Highly scalable

2. Global namespace

3. Easy replication

4. Supports distributed storage

5. Handles petabytes of data

Popular Users

• Facebook → Photos

• Spotify → Songs

• Dropbox → File storage

Cloud Platforms Using Object Storage

• Amazon S3

• Microsoft Azure

• OpenStack Swift

Example APIs

GET Object
PUT Object
DELETE Object

Disadvantages

• Object-level locking

• Less suitable for high-speed transaction systems

 • Not ideal for traditional OLTP databases

Comparison of Storage Architectures

Technology Access Type Best Use

SAN Block Enterprise DB

NAS File Shared files

iSCSI Block over IP Low-cost storage

AST Tiered storage Performance optimization

Object Storage Object Cloud / Big Data

Key Terms

Term Meaning

SAN Storage Area Network

NAS Network Attached Storage

iSCSI SCSI over IP

AST Automated Storage Tiering

Object Storage Storage using objects

Lecture Notes: 23.1 Distributed Database Concepts

Introduction

A Distributed Database (DDB) is a collection of multiple logically related databases

distributed across different locations (nodes) connected by a network.

A Distributed DBMS (DDBMS) is software that:

• Manages distributed databases

• Makes distribution transparent to users

23.1.1 What Constitutes a Distributed Database

For a database to be considered distributed, it must satisfy:

1. Network Connectivity

• Multiple computers (nodes/sites)

• Connected via a communication network

Node1 ↔ Node2 ↔ Node3 ↔ Node4

2. Logical Interrelation

• Data at different sites must be logically related

• Example:

STUDENT → DEPARTMENT → PROJECT

3. Heterogeneity (Optional)

Nodes may differ in:

• Hardware

• Operating systems

• DBMS software

• Data formats

Types of Networks
Network Type Description

LAN Local area (within building)

WAN Wide area (across cities/countries)

Wireless Wi-Fi / satellite

Key Point

Users do NOT see network complexity → handled by DDBMS.

23.1.2 Transparency

Definition

Transparency hides complexity of distributed system from users.

Types of Transparency

1. Data Organization Transparency

Also called Distribution Transparency

a) Location Transparency

User does not know where data is stored.

SELECT * FROM EMPLOYEE;

(No need to specify location)

b) Naming Transparency

Each object has a unique name across system.

2. Replication Transparency

• Data copies exist at multiple sites

• User is unaware of duplicates

3. Fragmentation Transparency

Data is divided into parts.

Types:

a) Horizontal Fragmentation

Rows divided:

EMPLOYEE
→ EMP_USA
→ EMP_INDIA

b) Vertical Fragmentation

Columns divided:

EMPLOYEE
→ (ID, Name)
→ (Salary, Dept)

4. Design Transparency

User unaware of database design details.

5. Execution Transparency

User does not know where queries execute.

23.1.3 Availability and Reliability

Definitions

• Reliability → System works at a given time

• Availability → System works continuously over time

Failure Concepts

Term Meaning

Fault Cause of problem

Error Incorrect system state

Failure System not working correctly

Types of Failures

1. Transaction failures

2. Hardware failures

3. Network failures
Fault Tolerance

System continues operation even when failures occur.

Techniques to Improve Reliability

• Data replication

• Backup systems

• Error detection & correction

23.1.4 Scalability and Partition Tolerance

Scalability

Ability to expand system capacity.

Types of Scalability

1. Horizontal Scalability

Add more nodes:

Node1 + Node2 + Node3

2. Vertical Scalability

Upgrade existing node:

• More RAM

• More CPU

• More storage

Partition Tolerance

System continues working even if network splits into parts.

Group A X Group B

Communication fails, but both groups operate independently.

23.1.5 Autonomy

Definition

Degree of independence of each node.

Types of Autonomy

1. Design Autonomy

Different DB models or systems.

2. Communication Autonomy

Node decides whether to share data.

3. Execution Autonomy

Local users execute transactions independently.

23.1.6 Advantages of Distributed Databases

1. Ease of Application Development

• Distributed apps easier to build

• Data located near users

2. Increased Availability

• Failure of one node does not stop entire system

• Replication ensures backup

3. Improved Performance

Reasons:

• Data stored near usage location

• Reduced network delay

 • Parallel processing

Types of Parallelism:

• Inter-query (multiple queries at different nodes)

• Intra-query (single query split into parts)

4. Scalability

• Easy to add nodes

• Supports growing data

Trade-Off: Transparency vs Autonomy

Feature Benefit Drawback

Transparency Easy to use High overhead

Autonomy More control Less integration

Summary Diagram

Distributed Database System

Nodes → Connected via Network

↓
Data Fragmented + Replicated
↓
Transparency hides complexity
↓
High Availability + Performance

Key Terms

Term Meaning

DDB Distributed Database

DDBMS Distributed DB Management System

Term Meaning

Transparency Hidden system complexity

Fragmentation Splitting data

Replication Data duplication

Scalability Ability to expand

Autonomy Independence of nodes

Lecture Notes: 23.2 Data Fragmentation, Replication, and Allocation Techniques
for Distributed Database Design

Introduction

In a Distributed Database System (DDBS), data is stored across multiple sites.

To design an efficient distributed database, three major decisions are required:

1. Fragmentation – Divide database into smaller parts

2. Replication – Store copies of data at multiple sites

3. Allocation – Decide where fragments/copies are stored

Global Directory

All information about:

• Fragment locations

• Replicas

• Allocation schema

is stored in a Global Directory.

23.2.1 Data Fragmentation and Sharding

Definition

Fragmentation means dividing a database relation into logical units called fragments.

These fragments are stored at different sites.

Why Fragmentation?

• Better performance

• Local access to data

• Reduced communication cost

• Parallel query processing

• Scalability

Types of Fragmentation
 1. Horizontal Fragmentation (Sharding)

2. Vertical Fragmentation

3. Mixed / Hybrid Fragmentation

1. Horizontal Fragmentation (Sharding)

Definition

Rows (tuples) of a relation are divided into subsets.

Example

EMPLOYEE table divided by department:

EMPLOYEE
→ EMP_D5 (Dno = 5)
→ EMP_D4 (Dno = 4)
→ EMP_D1 (Dno = 1)

Each site stores employees of its department.

Relational Algebra

𝜎𝐶𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 (𝑅)

Example:

𝜎𝐷𝑛𝑜=5 (𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)

Complete Horizontal Fragmentation

All rows included:

𝐶1 𝑂𝑅 𝐶2 𝑂𝑅 … 𝑂𝑅 𝐶𝑛

Disjoint Horizontal Fragmentation

No row belongs to two fragments.

Reconstruction

Use UNION

𝑅 = 𝐹1 ∪ 𝐹2 ∪ 𝐹3

Derived Horizontal Fragmentation

Fragment one relation based on another related relation.

Example:

• DEPARTMENT fragmented first

• EMPLOYEE fragmented using foreign key Dno

2. Vertical Fragmentation

Definition

Columns (attributes) are divided into subsets.

Example

EMPLOYEE divided into:

Personal Info

(Ssn, Name, Bdate, Address, Sex)

Work Info

(Ssn, Salary, Super_ssn, Dno)

Important Rule

Primary key must appear in every fragment.

Why?

To reconstruct original table.

Relational Algebra

𝜋𝐴𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 (𝑅)

Reconstruction

Use:

• OUTER UNION
or

• FULL OUTER JOIN

Conditions for Complete Vertical Fragmentation

1.

𝐿1 ∪ 𝐿2 ∪. . .∪ 𝐿𝑛 = 𝐴𝑇𝑇𝑅𝑆(𝑅)

2.

𝐿𝑖 ∩ 𝐿𝑗 = 𝑃𝐾(𝑅)

3. Mixed (Hybrid) Fragmentation

Combination of:

• Horizontal fragmentation

• Vertical fragmentation

Example

First divide employees by department, then divide attributes.

EMP_D5_Personal
EMP_D5_Work
EMP_D4_Personal
EMP_D4_Work
General Fragment Expression

𝜋𝐿 (𝜎𝐶 (𝑅))

Where:

• C = condition

• L = attribute list

Fragmentation Schema

Defines all fragments such that:

• Entire database is covered

• Original database can be reconstructed

23.2.2 Data Replication and Allocation

Data Replication

Definition

Copies of fragments stored at multiple sites.

Types of Replication

1. Full Replication

Entire database copied to every site.

Site1 = Full DB
Site2 = Full DB
Site3 = Full DB

Advantages

• Very high availability

• Fast local reads

Disadvantages

• Slow updates

• High storage cost

 • Complex concurrency control

2. No Replication

Each fragment stored at only one site.

Also called:

Nonredundant Allocation

3. Partial Replication

Some fragments replicated, others not.

Most practical approach.

Mobile Replication Example

Laptops/mobile devices carry partial data and later synchronize.

Data Allocation

Definition

Assigning fragments or replicas to sites.

Allocation Depends On

1. Access frequency

2. Query type (read/write)

3. Performance goals

4. Availability requirements

5. Update rate

Allocation Examples

Retrieval-heavy systems

Use more replication.

Update-heavy systems

Use less replication.

Optimization Problem

Finding best allocation is complex.

23.2.3 Example of Fragmentation, Allocation, Replication

Scenario

Company has 3 sites:

Site Department

Site 1 Headquarters

Site 2 Dept 5

Site 3 Dept 4

Site Requirements

Site 2 / Site 3

Need frequent access to:

• EMPLOYEE

• PROJECT

Only selected attributes:

Name, Ssn, Salary, Super_ssn

Site 1

Headquarters needs:

• Full employee data

• Full project data

• DEPENDENT data
Fragmentation Applied

DEPARTMENT

Horizontal fragmentation by department number.

EMPLOYEE

Derived horizontal fragmentation:

EMPD_5
EMPD_4

Then vertical fragmentation.

WORKS_ON Fragmentation Problem

WORKS_ON links:

• Employee

• Project

But employee department and project department may differ.

Example:

Employee in Dept 5 works on Project of Dept 4

So fragmentation becomes complex.

Allocation Strategy

Store WORKS_ON fragments locally where joins are needed.

This enables:

EMPLOYEE ⋈ WORKS_ON
PROJECT ⋈ WORKS_ON

to run locally.

Benefits of Good Fragmentation Design

1. Local query execution

 2. Reduced network traffic

3. Faster joins

4. Better scalability

5. Improved availability

Comparison Table

Technique Divides By Best Use

Horizontal Rows Department/location-based data

Vertical Columns Different attribute needs

Mixed Rows + Columns Complex workloads

Key Terms

Term Meaning

Fragment Subset of database

Sharding Horizontal fragmentation

Replica Copy of fragment

Allocation Placement of fragment

Global Directory Metadata of distributed DB

Lecture Notes: 23.3 Overview of Concurrency Control and Recovery in Distributed
Databases

1. Introduction

In a Distributed Database Management System (DDBMS), data is stored across

multiple networked sites.
Unlike centralized systems, distributed databases face additional challenges in:

• Maintaining consistency among multiple copies of data

• Handling failures of sites and communication links

• Coordinating commits across multiple sites

• Resolving deadlocks spanning different locations

Thus, concurrency control and recovery mechanisms in distributed databases are

more complex.

2. Major Problems in Distributed Concurrency Control and Recovery

2.1 Multiple Copies of Data Items

A data item may exist at several sites due to replication.

Challenges:

• All copies must remain consistent.

• Updates at one site must be reflected elsewhere.

• If one site fails and recovers later, outdated copies must be synchronized.

2.2 Failure of Individual Sites

A site may crash because of:

• Hardware failure

• Power outage

• Software crash

Requirements:

• Remaining active sites should continue operation.

 • Recovered site must be updated before rejoining.

2.3 Failure of Communication Links

Network connections between sites may fail.

Consequences:

• Messages may be lost

• Delayed communication

• Sites become isolated

Extreme Case: Network Partitioning

The network splits into groups of connected sites.

Example:

• Group A can communicate internally

• Group B can communicate internally

• But A and B cannot communicate with each other

System should continue working if possible.

2.4 Distributed Commit Problem

If a transaction updates data at multiple sites:

• All sites must commit together

• Or all must roll back

If one site fails during commit, inconsistency may occur.

Solution:

Two-Phase Commit Protocol (2PC)

2.5 Distributed Deadlock

Deadlock can involve transactions at multiple sites.

Example:

• T1 waits for lock at Site A

 • T2 waits for lock at Site B

• Circular waiting occurs

Distributed deadlock detection is more difficult than centralized deadlock handling.

3. Distributed Concurrency Control Based on Distinguished Copy

To control replicated data, one copy of each item is chosen as the distinguished copy.

All lock requests for that data item go to the site storing the distinguished copy.

4. Primary Site Technique

Definition:

One single site is chosen as the primary site for all data items.

All locking information is stored there.

Working:

• Every lock request sent to primary site

• Primary site grants/rejects lock

• Transactions then access data copies elsewhere

Advantages:

• Simple design

• Similar to centralized locking

• Easy to implement

Disadvantages:

1. Bottleneck Problem

All lock requests go to one site.

2. Single Point of Failure

If primary site crashes:

 • Entire locking system stops

5. Primary Site with Backup Site

Improvement over Primary Site

A second site acts as backup.

Both sites maintain lock tables.

If Primary Fails:

• Backup becomes new primary

• New backup is selected

Advantages:

• Better reliability

• Faster recovery

Disadvantages:

• Lock processing slower (must update two sites)

• Still possible bottleneck

6. Primary Copy Technique

Concept:

Different data items have different coordinator sites.

Example:

• Item A managed at Site 1

• Item B managed at Site 2

• Item C managed at Site 3

Advantages:
 • Load distributed across sites

• No single central bottleneck

Disadvantages:

• If one site fails, items coordinated there are affected

7. Election of New Coordinator

If coordinator fails and no backup exists:

Remaining sites elect a new coordinator.

Basic Election Process:

1. Site Y suspects coordinator failure

2. Y sends proposal to all active sites

3. If majority approve → Y becomes coordinator

Purpose:

• Restore system control

• Resume transaction processing

8. Distributed Concurrency Control Based on Voting

Instead of distinguished copy, all copies participate.

Working:

For lock request:

1. Request sent to all sites holding copy

2. Each site votes yes/no

3. If majority grants → lock obtained

Example:

5 copies exist.

Need majority = 3 votes.

If transaction receives 3 yes votes → lock granted.

Advantages:

• Fully distributed

• No central coordinator

Disadvantages:

• High message traffic

• More communication overhead

• Complex under failures

9. Distributed Recovery

Recovery ensures system consistency after failures.

10. Difficulty in Detecting Site Failure

Suppose Site X sends message to Site Y but gets no response.

Possible reasons:

1. Message lost

2. Site Y crashed

3. Y replied but response lost

Hence determining actual failure is difficult.

11. Distributed Commit

For transaction affecting multiple sites:

Commit only if every site has safely recorded changes in local log.
Solution: Two-Phase Commit (2PC)

Phase 1: Prepare Phase

Coordinator asks all sites:

Can you commit?

Phase 2: Decision Phase

If all say yes:

COMMIT

Else:

ROLLBACK

Benefit:

Ensures all sites make same decision.

12. Comparison of Techniques

Method Coordinator Advantage Limitation

Primary Site One site Simple Bottleneck

Primary + Backup Two sites Reliability Extra overhead

Primary Copy Multiple sites Balanced load Site failure affects items

Voting All sites Fully distributed High messaging

13. Key Terms

• Concurrency Control – Controls simultaneous transactions.

• Recovery – Restores database after failure.

• Replication – Multiple copies of data.

• Coordinator Site – Manages locks/commit.

• Deadlock – Transactions waiting forever.

• 2PC – Two-phase commit protocol.

• Voting Protocol – Majority lock approval.

Lecture Notes: 23.4 Overview of Transaction Management in Distributed Databases

1. Introduction

In a Distributed Database Management System (DDBMS), transactions may access

data stored at multiple sites.
To ensure correct execution, the system must guarantee the ACID properties of
transactions:

• Atomicity

• Consistency

• Isolation

• Durability

This is achieved through:

• Global transaction manager

• Local transaction managers

• Concurrency control managers

• Recovery managers

2. Components of Distributed Transaction Management

2.1 Global Transaction Manager (GTM)

An additional component used in distributed databases.

Role:

• Coordinates execution of transactions across multiple sites.

• Usually the site where transaction originates becomes temporary GTM.

2.2 Local Transaction Managers (LTM)

Each site has its own transaction manager.

Responsibilities:

• Manage local database operations

• Maintain logs
 • Coordinate with GTM

• Perform local commit/abort

2.3 Concurrency Controller

Responsible for:

• Lock acquisition

• Lock release

• Preventing conflicts

• Ensuring isolation

2.4 Runtime Processor

Executes actual database operations such as:

• Read

• Write

• Update

• Delete

3. Transaction Operations Supported

Distributed transaction managers provide an interface similar to centralized DBMS:

• BEGIN_TRANSACTION

• READ

• WRITE

• END_TRANSACTION

• COMMIT_TRANSACTION

• ROLLBACK / ABORT

4. Transaction Bookkeeping Information

For each transaction, manager stores:

 • Unique transaction ID

• Originating site

• Transaction name

• Status (active/committed/aborted)

• Locks held

• Log records

5. Handling READ Operations

When transaction requests READ:

• If valid local copy exists → return local copy

• Otherwise retrieve from another site

Benefit:

Reduces communication overhead and improves speed.

6. Handling WRITE Operations

When WRITE occurs:

• Update must become visible at all sites storing copies of that data item.

Example:

If Employee salary stored at Site A and Site B:

Update at A must also update B.

7. Handling ABORT / ROLLBACK

If transaction fails:

• All partial changes must be undone at every site.

This ensures Atomicity.

8. Handling COMMIT

If transaction succeeds:
 • All updates must be permanently recorded at every site.

This ensures Durability.

9. Transaction Execution Flow

Step-by-step:

1. Transaction begins.

2. Transaction manager receives operations.

3. Concurrency controller checks locks.

4. If locked → transaction waits.

5. If lock granted → runtime processor executes.

6. Result sent back.

7. Locks released after completion.

8. Commit or rollback performed.

10. Two-Phase Commit Protocol (2PC)

Used for atomic commit in distributed systems.

Purpose:

Ensures all sites either:

• Commit together, or

• Abort together

Phases of 2PC

Phase 1: Voting / Prepare Phase

Coordinator asks participants:

Can you commit?

Each site replies:

• YES
 • NO

Phase 2: Decision Phase

If all YES:

COMMIT

If any NO:

ABORT

Limitation of 2PC

Blocking Problem

If coordinator crashes after participants vote YES:

• Participants wait indefinitely

• Locks remain held

• Performance drops

11. Three-Phase Commit Protocol (3PC)

Developed to solve blocking problem of 2PC.

12. Phases of 3PC

Instead of 2 phases, commit process has 3 phases:

Phase 1: Vote Phase

Participants vote YES/NO.

Phase 2: Prepare-to-Commit (Precommit)

Coordinator informs all participants that commit is likely.

Phase 3: Commit

Final commit message sent.

13. Advantage of 3PC

If coordinator crashes during commit stage:

Another participant can determine correct action.

Example:

If precommit received → safe to commit.

If precommit not received → abort.

Thus indefinite waiting is avoided.

14. Timeout Mechanism in 3PC

If coordinator does not respond within time limit:

• Participants decide based on current phase.

• Locks are released after timeout.

This improves system availability.

15. Comparison: 2PC vs 3PC

Feature 2PC 3PC

Number of Phases 2 3

Blocking Problem Yes Reduced

Complexity Lower Higher

Coordinator Failure Handling Weak Better

Performance Faster Slightly slower

16. Operating System Support for Transaction Management

Some transaction functions can be moved to Operating System kernel.

17. Benefits of OS-Level Transaction Support

17.1 Better Semaphore Management

DBMS uses semaphores (locks) for shared resources.

If OS is unaware:

• It may suspend lock-holding process

• Other processes remain blocked

OS support avoids this issue.

17.2 Hardware-Assisted Locking

Special hardware instructions can reduce lock overhead.

Useful because locking is frequent in DBMS.

17.3 Shared Common Services

If multiple DBMS products run on same machine:

OS can provide common services such as:

• Lock management

• Logging

• Two-phase commit

This avoids repeated implementation.

18. Key Terms

• Global Transaction Manager – Coordinates distributed transaction.

• Local Transaction Manager – Controls local site transaction.

• 2PC – Two-phase commit protocol.

• 3PC – Three-phase commit protocol.

• Blocking Protocol – Participants wait indefinitely.

• Semaphore – Synchronization lock.

Lecture Notes: Query Processing and Optimization in Distributed Databases

23.5 Query Processing and Optimization in Distributed Databases

Introduction

In a Distributed Database Management System (DDBMS), data is stored at multiple

sites connected through a network. Query processing in distributed databases is more
complex than in centralized databases because:

• Data may be fragmented and distributed across sites.

• Relations may be replicated.

• Communication cost between sites becomes significant.

• Query execution must minimize data transfer and response time.

The main goal of distributed query optimization is to execute queries with minimum
total cost, especially minimizing network communication cost.

23.5.1 Distributed Query Processing

Distributed query processing occurs in four major stages.

1. Query Mapping

Definition

The user query written in SQL is translated into an equivalent relational algebra
expression based on the global conceptual schema.

Activities Performed

• Syntax checking

• Semantic analysis

• Query normalization

• Query simplification

• Conversion into algebraic form

Important Point

At this stage:

• Distribution details are ignored.

 • Processing is similar to a centralized DBMS.

Example

SQL Query:

SELECT Fname, Lname

FROM EMPLOYEE
WHERE Salary > 50000;

Relational Algebra:

πFname,Lname(σSalary>50000(EMPLOYEE))

2. Localization

Definition

The global query is converted into fragment-level queries based on:

• Fragmentation information

• Replication details

• Data distribution information

Purpose

To identify:

• Which fragments are needed

• At which sites the fragments exist

Example

If EMPLOYEE relation is fragmented into:

• EMPD1 at Site 1

• EMPD2 at Site 2

Then the query is rewritten separately for each fragment.

3. Global Query Optimization

Definition

Different execution strategies are evaluated and the best one is selected.

Optimization Factors
The total cost includes:

• CPU cost

• I/O cost

• Communication cost

Important Observation

In distributed systems:

Communication cost is usually the dominant cost.

Especially in:

• WAN environments

• Cloud-based distributed databases

Objective

Minimize:

• Amount of data transferred

• Query response time

• Total execution cost

4. Local Query Optimization

Definition

Each individual site optimizes its local subquery using centralized DBMS techniques.

Techniques Used

• Index selection

• Join ordering

• Access path optimization

Note

• First three stages are done centrally.

• Final stage is performed locally at each site.

23.5.2 Data Transfer Costs in Distributed Query Processing

Why Data Transfer Cost Matters

In distributed databases:

• Intermediate results must travel across networks.

• Final results may need transmission to another site.

Hence:

Reducing transferred data is the key optimization goal.

Example Database Distribution

Relation Site Size

EMPLOYEE Site 1 1,000,000 bytes

DEPARTMENT Site 2 3,500 bytes

Query Q

Requirement

Retrieve:

• Employee name

• Department name

Relational Algebra

𝑄 = 𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝐷𝑛𝑎𝑚𝑒 (𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 ⋈𝐷𝑛𝑜=𝐷𝑛𝑢𝑚𝑏𝑒𝑟 𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇)

𝑄 = 𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝐷𝑛𝑎𝑚𝑒 (𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 ⋈𝐷𝑛𝑜=𝐷𝑛𝑢𝑚𝑏𝑒𝑟 𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇)

Strategy 1

Transfer Both Relations to Result Site

Transferred data:

• EMPLOYEE = 1,000,000 bytes

• DEPARTMENT = 3,500 bytes

Total Transfer
 1,003,500 bytes

1,000,000 + 3,500 = 1,003,500

Strategy 2

Move EMPLOYEE to Site 2

• Perform join at Site 2

• Send result to Site 3

Result size:

40 × 10,000 = 400,000 bytes

Total transfer:

1,000,000 + 400,000 = 1,400,000

40 × 10,000 = 400,000

Strategy 3

Move DEPARTMENT to Site 1

• Join performed at Site 1

• Send result to Site 3

Transferred data:

400,000 + 3,500 = 403,500

400,000 + 3,500 = 403,500

Best Strategy

Strategy 3

Because it transfers minimum data.

Query Q′

Requirement

Retrieve:

• Department name

• Manager name

Relational Algebra

𝑄 ′ = 𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝐷𝑛𝑎𝑚𝑒 (𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇 ⋈𝑀𝑔𝑟_𝑠𝑠𝑛=𝑆𝑠𝑛 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)

𝑄 ′ = 𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝐷𝑛𝑎𝑚𝑒 (𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇 ⋈𝑀𝑔𝑟_𝑠𝑠𝑛=𝑆𝑠𝑛 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)

Transfer Cost Comparison for Q′

Strategy Data Transfer

Transfer both relations 1,003,500 bytes

Move EMPLOYEE 1,004,000 bytes

Move DEPARTMENT 7,500 bytes

Best Strategy

Strategy 3 again

Huge improvement because only 100 manager tuples participate in the join.
23.5.3 Distributed Query Processing Using Semijoin

Motivation

Semijoin reduces:

• Number of tuples transferred

• Unnecessary attributes transferred

Main Idea

Instead of transferring an entire relation:

1. Transfer only join attributes

2. Filter matching tuples

3. Transfer only necessary tuples

Semijoin Definition

𝑅 ⋉𝐴=𝐵 𝑆

Produces:

𝜋𝑅 (𝑅 ⋈𝐴=𝐵 𝑆)

𝑅 ⋉𝐴=𝐵 𝑆 = 𝜋𝑅 (𝑅 ⋈𝐴=𝐵 𝑆)

Properties of Semijoin

Important Property

Semijoin is not commutative

𝑅⋉𝑆 ≠ 𝑆⋉𝑅

𝑅⋉𝑆 ≠ 𝑆⋉𝑅

Semijoin Execution Steps

Step 1

Project join attributes from DEPARTMENT.

For Q:

𝐹 = 𝜋𝐷𝑛𝑢𝑚𝑏𝑒𝑟 (𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇)

Size:

4 × 100 = 400 bytes

Step 2

Transfer F to Site 1 and join with EMPLOYEE.

For Q:

𝑅 = 𝜋𝐷𝑛𝑜,𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒 (𝐹 ⋈ 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)

Transferred size:

34 × 10,000 = 340,000 bytes

Step 3

Transfer reduced relation back and perform final join.

Total Transfer for Q

340,400 bytes

Total Transfer for Q′

4,800 bytes

Advantages of Semijoin

Reduces communication cost

Eliminates unnecessary tuples
Efficient when few tuples participate in join
Useful in WAN environments
23.5.4 Query and Update Decomposition

Without Distribution Transparency

The user must know:

• Fragment locations

• Replica locations

• Fragment names

Example:
User explicitly references:

• PROJS_5

• WORKS_ON_5

With Full Distribution Transparency

The DDBMS automatically handles:

• Fragment location

• Replication

• Query decomposition

• Result assembly

The user writes queries as if database were centralized.

Query Decomposition

Purpose

Break a global query into:

• Smaller subqueries

• Executable at different sites

Example Query

Retrieve:

• Employee names
 • Hours worked

• Employees working on projects controlled by department 5

SQL Query

SELECT Fname, Lname, Hours

FROM EMPLOYEE, PROJECT, WORKS_ON
WHERE Dnum = 5
AND Pnumber = Pno
AND Essn = Ssn;

Decomposed Relational Algebra

Subquery T1

𝑇1 ← 𝜋𝐸𝑠𝑠𝑛 (𝑃𝑅𝑂𝐽𝑆5 ⋈𝑃𝑛𝑢𝑚𝑏𝑒𝑟=𝑃𝑛𝑜 𝑊𝑂𝑅𝐾𝑆_𝑂𝑁5)

Subquery T2

𝑇2 ← 𝜋𝐸𝑠𝑠𝑛,𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒 (𝑇1 ⋈𝐸𝑠𝑠𝑛=𝑆𝑠𝑛 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)

Final Result

𝑅𝐸𝑆𝑈𝐿𝑇 ← 𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝐻𝑜𝑢𝑟𝑠 (𝑇2 ⋈ 𝑊𝑂𝑅𝐾𝑆_𝑂𝑁5)

𝑇1 ← 𝜋𝐸𝑠𝑠𝑛 (𝑃𝑅𝑂𝐽𝑆5 ⋈𝑃𝑛𝑢𝑚𝑏𝑒𝑟=𝑃𝑛𝑜 𝑊𝑂𝑅𝐾𝑆_𝑂𝑁5)

Guard Conditions

Definition

A guard condition specifies:

• Which tuples belong to a fragment

Example

For horizontal fragmentation:

Dnum = 5

Only tuples satisfying the condition are stored.

Update Decomposition

Example Insert

New EMPLOYEE tuple:

('Alex', 'B', 'Coleman', ...)

The DDBMS decomposes this into:

• Insert into EMPLOYEE fragment

• Insert into EMPD4 fragment

Automatically based on guard conditions.

Key Concepts Summary

Concept Description

Query Mapping Convert SQL to relational algebra

Localization Map query to fragments

Global Optimization Choose best distributed strategy

Local Optimization Optimize at each site

Communication Cost Major factor in DDBMS

Semijoin Reduces transferred data

Query Decomposition Break query into subqueries

Guard Condition Defines fragment membership

Advantages of Distributed Query Optimization

Reduced network traffic

Faster query execution
Better resource utilization
Efficient parallel processing
Scalability
Lecture Notes: Types of Distributed Database Systems

23.6 Types of Distributed Database Systems

Introduction

A Distributed Database Management System (DDBMS) consists of:

• Multiple databases

• Distributed data and software

• Sites connected through communication networks

Although all DDBMSs distribute data across several sites, they differ in:

• Software uniformity

• Local autonomy

• Data models used

• Degree of heterogeneity

Classification Factors of DDBMS

Distributed database systems are classified based on:

1. Homogeneity

2. Autonomy

3. Distribution

4. Heterogeneity

1. Homogeneous Distributed Database System

Definition

A DDBMS is called homogeneous if:

• All sites use identical DBMS software

• All users use the same software environment

Characteristics

• Same data model

• Same query language

 • Easier query processing

• Easier transaction management

Advantages

Simpler design
Better transparency
Easier optimization
Uniform security policies

Example

• Multiple branches of a bank using the same Oracle DBMS.

2. Heterogeneous Distributed Database System

Definition

A DDBMS is called heterogeneous if:

• Different sites use different DBMS software

• Different data models may exist

Characteristics

• Different query languages

• Different schemas

• Different operating systems possible

Advantages

Flexibility
Integration of legacy systems
Supports diverse environments

Challenges

Complex query translation

Semantic conflicts
Difficult schema integration

Example

One site may use:

 • Oracle (Relational DBMS)

• Another uses IMS (Hierarchical DBMS)

• Another uses IDMS (Network DBMS)

Degree of Local Autonomy

Definition

Local autonomy refers to the ability of a site to:

• Operate independently

• Control its own data and transactions

Types of Local Autonomy

Type Description

No Local Autonomy All access controlled globally

Partial Local Autonomy Local transactions allowed

Full Local Autonomy Fully independent local DBMS

Classification Based on Autonomy

The autonomy spectrum gives rise to:

1. Centralized DDBMS

2. Federated Database System (FDBS)

3. Multidatabase System

Centralized Distributed Database (Point B)

Characteristics

• Appears as a centralized DBMS

• Single global conceptual schema

• No local autonomy
Features

• Centralized control

• Uniform operations

• Users access through a global system

Limitation

Local sites cannot function independently

Federated Database System (FDBS)

Definition

An FDBS consists of:

• Independent local DBMSs

• Shared global schema

Characteristics

• High local autonomy

• Global integration exists

• Local databases maintain independence

Key Feature

Applications access databases through:

• A federated/global schema

Multidatabase System

Definition

A multidatabase system:

• Has fully autonomous local databases

• Does NOT maintain a fixed global schema

Characteristics

• Schema constructed dynamically

• Very high local autonomy

• Interactive integration

Important Point

The system creates:

• Temporary integrated views when needed

Comparison: Federated vs Multidatabase Systems

Feature Federated DBMS Multidatabase System

Global Schema Exists Does not exist

Local Autonomy High Very high

Integration Predefined Dynamic

Coordination Moderate Minimal

Peer-to-Peer Database Systems

Characteristics

• Full heterogeneity
 • Full autonomy

• Equal participating nodes

Features

• No centralized controller

• Dynamic communication

• Independent resource sharing

Heterogeneous FDBS

Example Components

Different servers may use:

• Relational DBMS

• Network DBMS

• Hierarchical DBMS

• Object-oriented DBMS

Canonical System Language

Purpose

Used to:

• Standardize communication among heterogeneous databases

Requirement

Language translators are needed to convert:

• Canonical queries
→ Local DBMS queries

23.6.1 Federated Database Management System (FDBS) Issues

Sources of Heterogeneity

Heterogeneity in FDBS arises due to several factors.

1. Differences in Data Models

Problem

Different databases may use:

• Relational model

• Hierarchical model

• Network model

• Object-oriented model

• File systems

Challenge

Representing all systems uniformly is difficult.

Example

The same information may appear as:

• Relation name

• Attribute name

• Data value

in different databases.

Need for Intelligent Query Processing

The FDBS must:

• Understand metadata

• Relate semantically equivalent information

2. Differences in Constraints

Problem

Constraint implementation differs among systems.

Examples

• Referential integrity
 • Triggers

• Business rules

Challenge

Global schema must reconcile:

• Conflicting constraints

• Different enforcement mechanisms

3. Differences in Query Languages

Problem

Even relational databases may support different SQL versions.

Examples

• SQL-89

• SQL-92

• SQL-99

• SQL:2008

Differences May Include

• Data types

• Operators

• String functions

• Query syntax

Semantic Heterogeneity

Definition

Semantic heterogeneity occurs when:

• Same data has different meanings or interpretations

Example

Two CUSTOMER relations may differ because:

 • One belongs to the USA

• Another belongs to Japan

Differences may include:

• Currency

• Tax systems

• Customer attributes

• Accounting standards

Major Causes of Semantic Heterogeneity

1. Universe of Discourse

Different organizations define data differently.

Example

ACCOUNT table may contain:

• Different attributes

• Different business meanings

2. Representation and Naming

Problem

Same concept represented differently.

Example

Employee ID:

• Emp_ID

• Eno

• Employee_Number

3. Subjective Interpretation

Problem

Different interpretations of same data.

Example

“Active Customer” may mean:

• Customer active in last 6 months

• Customer active in last 1 year

4. Transaction and Policy Constraints

Includes

• Serializability rules

• Recovery policies

• Compensating transactions

5. Derivation of Summaries

Problem

Aggregation methods may differ.

Examples

• Monthly sales calculations

• Tax summaries

• Currency conversion rules

Middleware in Heterogeneous FDBS

Organizations use middleware to:

• Connect heterogeneous systems

• Process distributed transactions

• Apply business rules

Examples of Middleware and ERP Systems

Type Examples

Middleware WebLogic, WebSphere

ERP Systems SAP, J.D. Edwards ERP

Role of Middleware

Middleware performs:

• Query routing

• Transaction coordination

• Data transformation

• Communication management

Types of Autonomy in FDBS

1. Communication Autonomy

Definition

Ability of a local DBMS to decide:

• Whether to communicate with other databases

Example

A local site may deny external access during maintenance.

2. Execution Autonomy

Definition

Ability to:

• Execute local operations independently

• Decide execution order

Benefit

External operations do not interfere with local processing.

3. Association Autonomy

Definition

Ability to decide:

• What resources to share

• How much functionality to expose

Example

A database may allow:

• Read-only access

• Restricted query capabilities

Major Challenge in FDBS Design

Goal

Enable:

• Interoperability among databases

while preserving:

• Local autonomy

• Independence

• Security

Key Concepts Summary

Concept Description

Homogeneous DDBMS Same DBMS software at all sites

Heterogeneous DDBMS Different DBMSs across sites

Local Autonomy Independent control of local DBMS

Federated DBMS Shared global schema with autonomous databases

Multidatabase System No global schema; dynamic integration

Concept Description

Semantic Heterogeneity Differences in meaning of data

Middleware Software connecting heterogeneous systems

Canonical Language Common language for heterogeneous DBMSs

Advantages of Federated Database Systems

Integration of existing databases

Preservation of local autonomy
Flexibility
Scalability
Supports heterogeneous environments

Disadvantages of Federated Database Systems

Complex schema integration

Difficult query optimization
Semantic conflicts
Higher system complexity
Increased maintenance cost
Lecture Notes: Distributed Database Architectures

23.7 Distributed Database Architectures

Introduction

Distributed database architectures define:

• How distributed databases are organized

• How components interact

• How queries and transactions are processed across multiple sites

Modern enterprises use:

• Distributed architectures

• Parallel architectures

• Client/server models

• Federated systems

These architectures support:

• Scalability

• High performance

• Distributed transaction processing

• Data sharing

23.7.1 Parallel versus Distributed Architectures

Multiprocessor Architectures

There are three common multiprocessor architectures:

1. Shared Memory Architecture

2. Shared Disk Architecture

3. Shared-Nothing Architecture

1. Shared Memory Architecture

Definition

Multiple processors:
 • Share primary memory (RAM)

• Share secondary storage (disk)

Characteristics

• Tightly coupled system

• High-speed communication

• Common memory access

Advantages

Fast processor communication

Efficient synchronization
High performance

Disadvantages

Memory contention
Limited scalability

Shared Memory Architecture Overview

Processors → Shared RAM → Shared Disk

2. Shared Disk Architecture

Definition

Multiple processors:

• Share secondary storage

• Have separate primary memory

Characteristics

• Loosely coupled architecture

• Independent memory management

Advantages

Better scalability than shared memory

Shared database access

Disadvantages
 Disk contention
Complex coordination

Shared Disk Architecture Overview

Processors → Separate RAM → Shared Disk

Parallel Database Management Systems

DBMSs developed using:

• Shared memory

• Shared disk architectures

are called:

Parallel Database Management Systems

Purpose

To support:

• High-performance computing

• Data warehousing

• Massive transaction processing

3. Shared-Nothing Architecture

Definition

Each processor has:

• Its own RAM

• Its own disk

• No shared memory

Processors communicate through:

• High-speed network

• Bus or switch
Shared-Nothing Architecture

Processor + Local RAM + Local Disk

↕ Network ↕
Processor + Local RAM + Local Disk

Characteristics of Shared-Nothing Architecture

Features

• Complete independence of nodes

• High scalability

• Parallel processing support

Advantages

Excellent scalability
Fault isolation
High parallelism

Disadvantages

Data communication overhead

Complex query partitioning

Parallel vs Distributed Databases

Feature Parallel DBMS Distributed DBMS

Node Homogeneity Usually homogeneous Often heterogeneous

Communication High-speed internal Network communication

Control Centralized Distributed

Hardware Similar nodes Different hardware possible

Operating System Usually same May differ

Distributed Database Environment

In distributed databases:
 • Hardware heterogeneity is common

• Different operating systems may exist

• Nodes may operate autonomously

Types of Database Architectures

Architecture Description

Parallel Database Multiple processors work together

Centralized DB with Distributed Access Single DB accessed remotely

Pure Distributed Database Database distributed across sites

23.7.2 General Architecture of Pure Distributed Databases

Goal

Provide users with:

• Unified database view

• Transparent distributed access

Generic Schema Architecture of DDB

The architecture consists of:

1. Global Conceptual Schema (GCS)

 2. Local Conceptual Schema (LCS)

3. Local Internal Schema (LIS)

1. Global Conceptual Schema (GCS)

Definition

A unified logical view of the entire distributed database.

Responsibilities

• Provides network transparency

• Hides distribution details

• Maintains global consistency

Benefit

Users see:

• One integrated database

instead of multiple databases.

2. Local Conceptual Schema (LCS)

Definition

Logical structure of data at each site.

Includes

• Relations

• Constraints

• Local data organization

3. Local Internal Schema (LIS)

Definition

Physical storage details at each site.

Includes

• File organization
 • Indexes

• Access paths

• Storage methods

Transparency in DDB Architecture

The mappings among:

• GCS

• LCS

• LIS

provide:

• Fragmentation transparency

• Replication transparency

• Location transparency

Component Architecture of DDBMS

The distributed architecture extends centralized DBMS architecture.

Major Components

1. Global Query Compiler

Functions

• Parses global queries

• Verifies constraints

• References global schema

2. Global Query Optimizer

Responsibilities

• Generates optimized execution plans

• Evaluates candidate strategies

Optimization Factors

• CPU cost

• I/O cost

• Network latency

• Intermediate result size

Join Processing Importance

In distributed databases:

• Join operations are expensive

• Intermediate result sizes greatly affect performance

Cost-Based Optimization

The optimizer:

1. Evaluates all candidate strategies

2. Estimates total cost

3. Selects minimum-cost strategy

3. Local DBMS Components

Each local DBMS contains:

• Local query optimizer

• Transaction manager

• Execution engine

• Local system catalog

4. Global Transaction Manager

Responsibilities

Coordinates:

• Distributed transactions
 • Execution across multiple sites

Works with

Local transaction managers at each site.

23.7.3 Federated Database Schema Architecture

Five-Level Schema Architecture

Federated DBMSs use five schema levels:

1. Local Schema

2. Component Schema

3. Export Schema

4. Federated Schema

5. External Schema
1. Local Schema

Definition

Complete conceptual schema of a local database.

Represents

• Full local database definition

2. Component Schema

Definition

Local schema translated into:

• Canonical Data Model (CDM)

Purpose

Provides common representation across heterogeneous databases.

Schema Translation
Mappings are created to:

• Convert component schema commands

→ Local DBMS commands

3. Export Schema

Definition

Subset of component schema shared with federation.

Important Point

Not all local data must be shared.

4. Federated Schema

Definition

Global integrated schema of the federation.

Formed By

Integrating:

• All export schemas

5. External Schema

Definition

User-specific or application-specific views.

Similar To

External views in three-level architecture.

Challenges in FDBS Architecture

FDBSs face additional challenges in:

• Query processing

• Transaction processing

• Recovery management
 • Metadata management

because of:

• Heterogeneity

• Local autonomy

23.7.4 Three-Tier Client/Server Architecture

Introduction

Modern distributed applications commonly use:

Three-tier architecture

especially in:

• Web applications

• Enterprise systems

Layers in Three-Tier Architecture

1. Presentation Layer
 2. Application Layer

3. Database Server Layer

1. Presentation Layer (Client Layer)

Responsibilities

• User interaction

• Input handling

• Displaying information

Technologies Used

• HTML

• XHTML

• CSS

• JavaScript

• SVG

• Java

• Adobe Flex

Role of Web Browsers

Browsers provide:

• Graphical interface

• Dynamic Web pages

• Communication via HTTP

Presentation Layer Functions

User input
Output display
Navigation
Form handling
2. Application Layer (Business Logic Layer)

Responsibilities

Implements:

• Business rules

• Application logic

• Query generation

• Security checks

Database Connectivity Methods

Application servers connect using:

• ODBC

• JDBC

• SQL/CLI

Functions of Application Layer

Query formulation
Result formatting
Authentication
Authorization
Transaction coordination

3. Database Server Layer

Responsibilities

• Query processing

• Update processing

• Result generation

Uses

• SQL

• Stored procedures
XML in Distributed Databases

Increasingly:

• XML is used for data exchange

between:

• Application servers

• Database servers

Interaction in Three-Tier Architecture

Step 1: Query Formulation

Application server:

• Receives client request

• Decomposes global query

• Sends local queries to sites

Step 2: Local Query Processing

Each database server:

• Executes local query

• Sends result to application server

Possibly formatted in XML.

Step 3: Result Integration

Application server:

• Combines subquery results

• Formats output

• Sends response to client

Role of Application Server

The application server:

• Generates distributed execution plans

• Coordinates distributed transactions

• Maintains replica consistency

• Handles global recovery

Distributed Concurrency Control

Application servers ensure:

• Consistency among replicated data copies

using:

• Global concurrency control algorithms

Global Recovery

The application server ensures:

• Atomicity of global transactions

even when:

• Some sites fail

Distribution Transparency

Definition

Ability to hide:

• Data location

• Fragmentation details

• Replication details

from applications and users.

Benefits of Distribution Transparency

 Simplifies application development
Centralized database illusion
Easier query formulation
Improved usability

Without Distribution Transparency

Applications must know:

• Exact data locations

• Fragment names

• Site information

This increases:

• Complexity

• Maintenance effort

Key Concepts Summary

Concept Description

Shared Memory Shared RAM and disk

Shared Disk Shared disk, separate RAM

Shared-Nothing Independent nodes with network communication

GCS Global conceptual schema

LCS Local conceptual schema

LIS Local internal schema

Global Query Optimizer Chooses minimum-cost execution strategy

Federated Schema Integrated global schema

Three-Tier Architecture Client, application, database layers

Distribution Transparency Hides distribution details

Advantages of Distributed Architectures

Scalability
High availability
Parallel processing
Fault tolerance
Resource sharing
Better performance

Disadvantages

Complex transaction management

Difficult recovery handling
Communication overhead
Complex query optimization
Security challenges
Lecture Notes: Distributed Catalog Management

23.8 Distributed Catalog Management

Introduction

In a Distributed Database Management System (DDBMS), efficient management of

metadata is essential for:

• Query processing

• Data location tracking

• Fragmentation management

• Replication control

• View management

This metadata is stored in:

Distributed Catalogs

What is a Catalog?

Definition

A catalog is a database containing:

• Metadata about the distributed database system

Metadata Includes

• Relation names

• Fragment information

• Replica locations

• User privileges

• Storage details

• Index information

• Schema definitions

• Site information
Importance of Distributed Catalog Management

Efficient catalog management ensures:

Fast query processing

Efficient data retrieval
Data distribution transparency
Proper replication management
Improved site autonomy
Better system performance

Major Catalog Management Schemes

There are three popular schemes:

1. Centralized Catalogs

2. Fully Replicated Catalogs

3. Partially Replicated Catalogs

Factors Affecting Choice of Catalog Scheme

The choice depends on:

• Database size

• Read/write access patterns

• Degree of autonomy

• Replication requirements

• Network characteristics

1. Centralized Catalogs

Definition

The entire catalog is stored at:

• One central site

Architecture
All Sites → Central Catalog Site

Characteristics

• Single catalog repository

• All metadata requests handled centrally

• Easy implementation

Read Operation in Centralized Catalog

Process

1. Noncentral site requests catalog data

2. Data locked at central site

3. Data sent to requesting site

4. Acknowledgment returned

5. Lock released

Write Operation in Centralized Catalog

Process

All updates must:

• Pass through the central site

Advantages of Centralized Catalogs

Simple design
Easy maintenance
Easy consistency management
Simple synchronization

Disadvantages of Centralized Catalogs

Single point of failure

Performance bottleneck
 Poor scalability
Reduced reliability
Reduced site autonomy
High communication overhead

Bottleneck Problem

In write-intensive applications:

• All updates accumulate at one site

leading to:

• Slow performance

• Increased waiting time

Applications Suitable for Centralized Catalogs

Best suited for:

• Small distributed systems

• Low update frequency

• Simple architectures

2. Fully Replicated Catalogs

Definition

Complete identical copies of the catalog exist:

• At every site

Architecture

Site1 Catalog = Site2 Catalog = Site3 Catalog

Characteristics

• Every site stores full catalog

• Local access possible

 • Faster metadata retrieval

Read Operations

Major Benefit

Reads are:

• Performed locally

No remote access needed.

Write Operations

Important Requirement

Every update must:

• Be broadcast to all sites

Consistency Management

Updates are treated as:

Distributed Transactions

A:

Two-Phase Commit Protocol (2PC)

is used to maintain consistency.

Two-Phase Commit Overview

Phase 1: Prepare Phase

Coordinator asks all sites:

• “Can you commit?”

Phase 2: Commit Phase

If all agree:

• Commit occurs everywhere

Otherwise:
 • Rollback occurs

Advantages of Fully Replicated Catalogs

High availability
Fast read access
Improved fault tolerance
Better reliability
Local metadata access

Disadvantages of Fully Replicated Catalogs

High update overhead

Increased network traffic
Complex synchronization
Expensive write operations

Network Traffic Issue

For every update:

• Broadcast sent to all sites

This becomes costly in:

• Large distributed systems

• Write-heavy workloads

Applications Suitable for Fully Replicated Catalogs

Best suited for:

• Read-intensive applications

• High availability systems

• Frequently accessed metadata

3. Partially Replicated Catalogs

Definition

Each site maintains:

• Complete catalog information for local data

• Cached copies of remote entries

Characteristics

• Local metadata stored locally

• Remote metadata cached

• Partial replication used

Architecture

Each Site:
• Full Local Catalog
• Partial Remote Cache

Cached Entries

Important Point

Cached copies:

• May become stale

• May not contain latest updates

Birth Site Concept

Definition

The original site where an object was created is called:

Birth Site

Update Propagation

Process

Changes to copies are:

 • Immediately propagated to birth site

Retrieval of Updated Copies

Updated remote copies may be:

• Retrieved later

• Refreshed on access

This is called:

Lazy Update Approach

Advantages of Partially Replicated Catalogs

Better site autonomy

Reduced network traffic
Improved scalability
Faster local access
Balanced read/write performance

Disadvantages of Partially Replicated Catalogs

Possible stale data

Complex cache management
Synchronization challenges
Metadata inconsistency risk

Comparison of Catalog Management Schemes

Feature Centralized Fully Replicated Partially Replicated

Catalog Location Single site All sites Local + partial remote

Read Performance Slow remote reads Fast local reads Fast local reads

Write Performance Bottleneck Expensive broadcasts Moderate

Reliability Low High Moderate

Feature Centralized Fully Replicated Partially Replicated

Site Autonomy Low Low High

Network Traffic Moderate High Moderate

Scalability Poor Moderate Good

Data Distribution Transparency

Definition

Users should access distributed data:

• Without knowing physical locations

Synonyms for Remote Objects

To support transparency:

• Users may create synonyms for remote objects

Example

Suppose EMPLOYEE exists at Site 2.

User at Site 1 creates:

CREATE SYNONYM EMP FOR EMPLOYEE@SITE2;

Then user can query:

SELECT * FROM EMP;

without knowing:

• Actual remote location

Unique Accessibility of Fragments

Requirement

Fragments across sites should:

• Be uniquely identifiable
 • Avoid ambiguity

Role of Distributed Catalogs in Query Processing

Catalogs help:

• Locate fragments

• Identify replicas

• Select optimal execution sites

• Optimize distributed queries

Role in Replication Management

Catalogs maintain:

• Replica locations

• Replica consistency information

• Synchronization details

Role in Security Management

Catalogs also store:

• User privileges

• Access rights

• Authorization information

Challenges in Distributed Catalog Management

Major Challenges

1. Consistency Maintenance

Keeping all catalog copies synchronized.

2. Scalability

Handling growth in:

 • Sites

• Metadata

• Transactions

3. Fault Tolerance

Ensuring availability despite:

• Site failures

• Network failures

4. Communication Overhead

Reducing:

• Network traffic

• Synchronization cost

5. Site Autonomy

Balancing:

• Global consistency

• Local independence

Key Concepts Summary

Concept Description

Catalog Metadata repository

Centralized Catalog Single-site catalog storage

Fully Replicated Catalog Complete catalog at all sites

Partially Replicated Catalog Local catalogs with cached remote entries

Metadata Data about data

Birth Site Original creation site of object

Concept Description

Two-Phase Commit Protocol ensuring consistency

Distribution Transparency Hides data location details

Synonym Alias for remote object

Advantages of Efficient Catalog Management

Faster query execution

Better distributed optimization
Improved transparency
Better replication management
Enhanced reliability
Efficient metadata access