Unit 3: Query Processing, Decomposition, and Localization

1. Query Processing Problem

2. Objectives of Query processing
3. Complexity of RA Operations
4. Characterization of Query Processors
5. Layers of Query Processing
6. Query Decomposition
7. Localization of Distributed Data

……………………………… ……………… ……………… ………………………………

3. Query Processing, Decomposition, and Localization

1. Query Processing Problem

Query processing involves converting a high-level declarative query (e.g., SQL) into an
efficient execution strategy that retrieves the required data from a distributed database
system.

Challenges:

• Data Fragmentation: Data may be horizontally, vertically, or hybrid fragmented across

multiple sites.
• Data Replication: Multiple copies of the same data exist at different sites.
• Network Latency: Transferring data between sites introduces communication costs.

Example: Assume a Bank Database where customer records (Customer) are

horizontally fragmented based on city:

Site Fragment

Site A Customers from New York

Site B Customers from Los Angeles

Site C Customers from Chicago

A query:
SELECT * FROM Customer WHERE city = 'New York';

• In a centralized system, the query runs on a single server.

• In a distributed system, the query processor identifies that the relevant data is only at
Site A, preventing unnecessary searches at Sites B and C.

2. Objectives of Query Processing

Goals:

1. Reduce Query Execution Time: Minimize response time.

2. Optimize Resource Utilization: Reduce CPU, disk, and network costs.
3. Minimize Data Transfer: Process data locally before transferring.

Example: For the same Customer table, consider this query:

SELECT COUNT(*) FROM Customer WHERE balance > 5000;

• Instead of fetching all customer data from multiple sites to one central site, local
processing should be done first:
o Each site calculates COUNT(*) locally.
o The final count is computed by summing the results at a central site.

This reduces communication cost and improves efficiency.

3. Complexity of Relational Algebra (RA) Operations

Key RA Operations:

Operation Complexity Example

Selection (σ) O(n) σ balance > 5000 (Customer)

Projection (π) O(n) π name, balance (Customer)

Join (⋈) O(n log n) Customer ⋈ Account

Set operations (∪, ∩, −) O(n log n) Customer ∩ VIP_Customers

Cartesian Product (×) O(n²) Customer × Transactions

Optimization Principles:
 • Perform the most selective operations first (e.g., apply σ early).
• Delay or avoid Cartesian products.
• Use hashing or indexing techniques to improve performance.

4. Characterization of Query Processors

Types of Query Optimization:

1. Exhaustive Search: Evaluates all possible query execution plans (high cost).
2. Heuristic-Based Optimization: Uses rules to prune the search space.
3. Randomized Optimization: Uses randomized algorithms to find an optimal execution
plan.

Example: Query:

SELECT * FROM Customer C, Account A WHERE C.cust_id = A.cust_id;

Possible execution plans:

1. Nested Loop Join (Cost: High):

o For each customer, scan Account to find matching tuples.
2. Hash Join (Cost: Medium):
o Hash Customer on cust_id, then probe Account using the hash.
3. Sort-Merge Join (Cost: Low for sorted input):
o Sort Customer and Account by cust_id, then merge.

The query optimizer selects the lowest-cost strategy based on system statistics.

5. Layers of Query Processing

Layer 1: Query Decomposition

• Converts a high-level query (relational calculus) into an algebraic query.

Example:

SELECT name FROM Customer WHERE city = 'New York' AND balance > 5000;

Decomposed into:

1. Normalization:
2. σ city = 'New York' ∧ balance > 5000 (Customer)
3. Query Restructuring:
4. π name (σ city = 'New York' (σ balance > 5000 (Customer)))
Layer 2: Data Localization

• Translates queries from global schema to local fragments.

Example: Global query:

SELECT * FROM Customer WHERE city = 'Chicago';

Becomes:

σ city = 'Chicago' (Customer_CHICAGO)

This avoids scanning irrelevant fragments.

Layer 3: Global Query Optimization

• Determines the best execution strategy considering:

o Query execution order.
o Distribution of computation across sites.
o Communication minimization using semijoins.

Layer 4: Distributed Query Execution

• Executes optimized query plans at multiple sites.

6. Query Decomposition

Steps:

1. Normalization: Converts SQL to relational algebra.

2. Semantic Analysis: Removes redundant conditions.
3. Query Simplification: Rewrites query for efficiency.
4. Restructuring: Optimizes algebraic expressions.

Example:

SELECT name FROM Customer WHERE (balance > 5000 AND balance < 10000);

• Normalized:
• σ balance > 5000 ∧ balance < 10000 (Customer)
• Simplified:
• σ 5000 < balance < 10000 (Customer)
7. Localization of Distributed Data

Translates queries from global schema to fragmented schema.

Example: Global Query:

SELECT * FROM Customer WHERE city = 'Los Angeles';

Fragmented Tables:

• Customer_LA
• Customer_NY
• Customer_CHI

Rewritten as:

σ city = 'Los Angeles' (Customer_LA)

• The query only executes at Site B, reducing unnecessary scans.

Summary

1. Query Processing Problem

Query processing in a distributed database is complex due to:

- Data Distribution: Data is stored across multiple sites.

- Network Latency: Queries must be processed efficiently to reduce delays.

- Cost Optimization: Query execution should minimize computation and communication costs.

- Data Integration: Queries may need to access heterogeneous databases.

2. Objectives of Query Processing

The primary objectives of query processing in a distributed database are:

1. Minimizing Communication Costs: Reduce data transfer between sites.

2. Reducing Local Processing Costs: Optimize computations at each site.

3. Enhancing Response Time: Improve query execution speed.

4. Ensuring Data Consistency: Maintain correctness in concurrent transactions.

5. Providing Distributed Transparency: Users should not need to know where data is stored.

3. Complexity of Relational Algebra (RA) Operations

Relational Algebra (RA) operations become more complex in a distributed setting due to:

- Distributed storage of data across multiple sites.

- Cost of transferring data between sites for operations like JOIN.

- Synchronization issues when executing queries in parallel.

4. Characterization of Query Processors

A query processor translates SQL queries into optimized execution plans.

Types of Query Processing Strategies:

1. Centralized Query Processing: Handled at a central site.

2. Semi-Distributed Query Processing: Some processing is remote, but final execution is

centralized.

3. Fully Distributed Query Processing: Each site processes its local data, results are merged.

5. Layers of Query Processing

Query processing occurs in multiple stages:

1. Query Parsing and Translation: Converts SQL into relational algebra.

2. Query Decomposition: Breaks queries into smaller subqueries.

3. Data Localization: Identifies where the required data is stored.

4. Global Query Optimization: Selects the best execution plan.

5. Query Execution and Result Integration: Executes queries and merges results.

6. Query Decomposition
Query decomposition breaks a complex distributed query into subqueries for efficient execution.

Steps in Query Decomposition:

1. Normalization: Convert SQL query into relational algebra.

2. Analysis: Check for correctness.

3. Simplification: Remove redundant conditions.

4. Fragmentation Mapping: Identify which fragments contain the required data.

5. Query Restructuring: Generate optimized subqueries.

7. Localization of Distributed Data

Localization ensures that subqueries are executed efficiently by reducing unnecessary data
transfer.

Techniques for Localization:

1. Direct Execution at Local Sites: Run queries directly if data is local.

2. Data Shipping: Move data to a central location for processing.

3. Query Shipping: Move queries to the site where data is stored.

4. Hybrid Approach: Combination of query and data shipping.