Query Processing in Distributed Database Systems
Exam-Oriented Notes | [Link] Computer Science
TOPIC 1: What is a Query?
Definition
A query is a command or request sent to a database to extract specific data. The part of DML
(Data Manipulation Language) that deals with retrieving data is called the query language.
Example: SELECT * FROM Customers — fetches all customer data from the
database.
Key Points
• SQL (Structured Query Language) is the most common query language.
• A query abstracts away how data is physically stored.
TOPIC 2: What is a Query Processor?
Definition
A Query Processor is a specialized component of the DBMS that executes and optimizes high-
level user queries internally, without requiring the user to know implementation details.
Key Points
• Users write in non-procedural (high-level) languages like SQL.
• The query processor converts them into efficient execution plans internally.
• It spares users from the complexities of optimization.
TOPIC 3: Objectives / Main Function of Query Processor
Primary Goal
Convert a high-level calculus query → low-level algebraic query
Calculus Query (What to retrieve)
↓
Query Processor
↓
Algebraic Query (How to retrieve it — optimized)
Two Requirements of Conversion:
Requirement Meaning
Accuracy Low-level query must give the SAME result as
the original high-level query
Optimization Low-level query must be efficient in terms of
time, memory, and cost
TOPIC 4: Main Problem in Query Processing
The Core Challenge: Query Optimization
Optimization is difficult because:
• Many execution plans exist for the same query — evaluating all is time-consuming.
• Cost depends on:
• Duration of operations across different sites
• Computing resource usage
• Data transfer time between sites
• Time and memory required to complete the query
TOPIC 5: Characterization of Query Processors
There are 8 characteristics — first 4 apply to both centralized and distributed systems;
next 4 apply only to distributed systems.
Characteristic 1: Languages
Model Language Used
Relational DBMS Relational Calculus (SQL)
Object DBMS Object Calculus (extension of RDBMS)
XML XQuery and XPath
• XQuery — query language for XML data (XQuery : XML = SQL : DB)
• XPath — navigates through nodes/elements in an XML document
• The query processor must efficiently map input language → output language
Characteristic 2: Types of Optimization
Goal: Choose the "best" point in the solution space of all possible execution strategies.
(i) Exhaustive Search Approach
• Search through all possible strategies, predict each one's cost, pick the minimum-cost one.
• Problem: Solution space can be huge even with a small number of relations → Very
expensive.
(ii) Heuristics
• Restricts the solution space to only a few strategies.
• Rules: process unary operators first, then binary operators with increasing sizes.
• Example: Replace JOIN with SEMI-JOIN to minimize data communication cost.
Characteristic 3: Optimization Timing
Type When? Advantage Disadvantage
Static At compile time Good for exhaustive Errors may occur (uses
(before execution) search estimated stats)
Dynamic During query Uses real intermediate Must repeat for every
execution sizes execution — expensive
Hybrid Mostly static + Benefits of both More complex
dynamic where needed
Characteristic 4: Statistics
• Query optimization effectiveness depends on database statistics.
• Dynamic QO needs statistics to choose which operator to execute first.
• Static QO needs to estimate sizes of intermediate relations using statistics.
• In DDB (Distributed DB): Statistics relate to fragments, size, and distinct values per
attribute.
• Histograms are created to reduce probability of errors.
• Periodic updating of statistics may lead to query re-optimization.
Characteristic 5: Decision Sites (Distributed Only)
Who decides the execution strategy?
Approach Description Pros Cons
Centralized Single site generates Simple Needs knowledge of
the strategy entire DDB
Distributed Decision spread across Only needs local info More complex
multiple sites
Hybrid One site makes major Balance of both —
decisions; others make
local ones
Characteristic 6: Exploitation of Network Topology (Distributed Only)
• WAN (Wide Area Network): Cost function = data communication cost → divided into:
1. Global execution strategy (based on inter-site communication)
2. Local execution strategy (based on centralized algorithm)
• LAN (Local Area Network): Communication costs ≈ I/O costs → reasonable to increase
parallel execution.
• Client-Server: Query work divided between server and client — data shipping is
performed.
Characteristic 7: Exploitation of Replicated Fragments (Distributed
Only)
• Distributed relations are divided into relation fragments.
• Queries on global relations are mapped to queries on physical fragments — called
localization.
• Fragments can be replicated at different sites for higher reliability.
• Replicated fragments at run time → minimizes communication time.
Characteristic 8: Use of Semi-Joins (Distributed Only)
• Semijoin reduces the communication cost between different sites.
• It reduces the size of the operand relation before sending it across the network.
• Useful when the main cost is communication (distributed join operations).
Example Comparison: | Query | Type | Output Rows | |---|---|---| | SELECT D.dept_id,
D.dept_name FROM dept D WHERE EXISTS (SELECT 1 FROM emp E WHERE
E.dept_id = D.dept_id) | Semijoin (q1) | 5 (distinct depts) | | SELECT D.dept_id,
D.dept_name FROM dept D, emp E WHERE E.dept_id = D.dept_id |
Conventional Join (q2) | Many (duplicate depts) |
Semijoin gives cleaner, smaller result — less data to transfer between sites.
TOPIC 6: Layers of Query Processing
Overview
Query processing is decomposed into sub-problems, each handled by a layer.
• Input: Query on global data (expressed in relational calculus)
• The query is on global (distributed) relations — data distribution is hidden from the user.
Four Main Layers:
Calculus Query on Global Relations
↓
[1] QUERY DECOMPOSITION ← Global Schema
↓
Algebraic Query on Global Relations
↓
[2] DATA LOCALIZATION ← Fragment Schema
↓
Algebraic Query on Fragments
↓
[3] GLOBAL OPTIMIZATION ← Allocation Schema
↓
Distributed Query Execution Plan
↓
[4] DISTRIBUTED EXECUTION
↓
ANSWER
Layer Performed By Purpose
Layers 1–3 Central control site Map query → optimized
execution plan
Layer 4 Local sites Execute the plan, return answer
• Layers 1 & 2 = Query rewriting
• Layers 1–3 use information from the global directory / global conceptual schema
Layer 1: Query Decomposition
Definition: First phase — transforms a relational calculus query into a relational algebra query.
Steps (4 successive steps):
Step Name What Happens
1 Normalization Rewrite calculus query in
normalized form (logical
operator priority)
Step Name What Happens
2 Analysis Analyze semantically — detect
and reject incorrect queries
early
3 Elimination of Redundancy Simplify query by eliminating
redundant predicates
4 Rewriting Restructure as an algebraic
query (operator tree)
Both input and output refer to global relations — no knowledge of data
distribution. Query decomposition is the same for centralized and distributed
systems.
Operator Tree
An operator tree is a graphical representation of a relational algebra query.
• Leaf nodes = Relations stored in the database
• Non-leaf nodes = Intermediate relations (produced by relational algebra operators)
• Root = Final answer to the query
• Execution flows bottom-up (leaves → root)
How to build an operator tree from SQL:
SQL Clause Maps To
FROM clause Leaf nodes (the base relations)
SELECT clause Root node (projection operation Π)
WHERE clause Internal nodes — sequence of select (σ), join
(⋈), union etc., bottom-up
Example:
Query: "Find names of employees other than [Link] who worked on CAD/CAM
project for either 1 or 2 years"
SQL:
SELECT ENAME
FROM PROJ, ASG, EMP
WHERE [Link] = [Link] AND [Link] = [Link]
AND ENAME != '[Link]' AND [Link] = 'CAD/CAM'
AND (DUR = 12 OR DUR = 24)
Operator Tree (bottom-up):
Π_ENAME ← project (root)
↑
σ_DUR=12 OR DUR=24 ← select
↑
σ_PNAME='CAD/CAM' ← select
↑
σ_ENAME≠'[Link]' ← select
↑
⋈_PNO ← join
/ \
PROJ ⋈_ENO ← join
/ \
ASG EMP
Layer 2: Data Localization
Definition: Maps an algebraic query on global relations → algebraic query on fragments.
• Input: Algebraic query on global relations.
• Main Role: Localize the query's data using fragment schema (data distribution info).
• In DDB, relations are split into disjoint fragments stored at different sites.
• This layer determines which fragments are involved in the query.
Layer 3: Global Query Optimization
Definition: Takes algebraic query on fragments → produces optimized distributed execution
plan.
• Goal: Find an execution strategy that is close to optimal.
• Optimization = Finding the best ordering of operators (including communication
operators).
• Cost function minimizes: Disk I/O, buffer space, CPU cost, communication cost
(bandwidth).
• Uses static optimization (predicts execution cost statistically).
• One key aspect: Join ordering through semijoin operators.
Layer 4: Distributed Query Execution
Definition: Executes the distributed query execution plan across all relevant sites.
• Performed by all sites having fragments involved in the query.
• Each subquery at one site = local query → optimized using local schema → executed.
• At this stage, algorithms for relational operators are chosen.
• Local optimization uses algorithms of centralized systems.
IMPORTANT EXAM POINTS
1. Query Processor = converts calculus query → algebraic query (accurately + efficiently)
2. Main problem = query optimization (large solution space, cost of computing resources)
3. 8 characteristics — first 4 for both, last 4 for distributed only
4. Semijoin reduces communication cost (key concept for distributed QP)
5. 4 layers of query processing — memorize names and what each does
6. Query Decomposition = same for centralized and distributed systems
7. Localization = mapping global relations to physical fragments
8. Static optimization = compile time; Dynamic = runtime; Hybrid = both
9. Operator tree: leaves = FROM, root = SELECT, middle = WHERE
[Link] fragments at runtime minimize communication time
2-MARK REVISION NOTES
Question Answer
What is a query? A command to retrieve data from a database
using DML's query language
What does a query processor do? Converts high-level (calculus) queries to low-
level (algebraic) queries efficiently
What is the main problem in QP? Query optimization — finding the best
execution plan among many possibilities
What is semijoin used for? To reduce communication cost in distributed
DBs by reducing operand relation size
What is localization? Mapping global relations to physical fragments
in distributed query processing
What are the 4 layers of QP? Query decomposition, Data localization, Global
optimization, Distributed execution
What is static optimization? Optimization done at query compile time using
database statistics
What is dynamic optimization? Optimization done at runtime, using actual
intermediate result sizes
What is an operator tree? A tree where leaves = base relations, non-leaf =
intermediate results, root = answer
What is the heuristic approach? Restricting solution space — process unary ops
first, replace join with semijoin
5-MARK EXAM ANSWER
Q: Explain the Layers of Query Processing in a Distributed Database
System.
Query processing in a Distributed Database System (DDB) is decomposed into four main layers,
each solving a specific sub-problem. The input to the entire system is a relational calculus query
on global relations (data distribution is hidden from the user).
Layer 1 — Query Decomposition: This is the first layer performed at the central control site. It
transforms a relational calculus query into a relational algebra query using the global conceptual
schema. The four steps are: (1) Normalization, (2) Semantic Analysis, (3) Redundancy Elimination,
and (4) Rewriting. The output is an algebraic query on global relations, represented as an
operator tree (leaves = FROM clause relations, root = SELECT projection, middle nodes =
WHERE clause operations).
Layer 2 — Data Localization: Also performed at the central control site. This layer takes the
algebraic query on global relations and maps it to an algebraic query on physical fragments using
the fragment schema. In DDB, relations are divided into disjoint fragments stored at different sites.
This layer determines which fragments are involved and translates the query accordingly. This
process is called localization.
Layer 3 — Global Query Optimization: Still at the central control site, this layer takes the
fragment-level query and finds a near-optimal execution strategy. It finds the best ordering of
operators (including communication operators) to minimize a cost function covering disk I/O, CPU,
memory, and communication cost. Typically uses static optimization (predicting cost statistically)
and semijoin operators for join ordering.
Layer 4 — Distributed Query Execution: This final layer is performed at local sites having the
relevant fragments. The distributed execution plan is sent to each site, where subqueries (local
queries) are optimized using the local schema and executed. Local optimization uses centralized
system algorithms. The final results are collected and the answer is returned to the user.
The first three layers together convert the input query into an optimized distributed
execution plan. The fourth layer executes it and returns the answer.
FREQUENTLY ASKED UNIVERSITY EXAM QUESTIONS
1. What is a query processor? What is its main function? (2/5 marks)
2. What are the main problems in query processing? (2 marks)
3. Explain the characterization of query processors with all 8 characteristics. (10 marks)
4. Explain the layers of query processing in distributed database systems with a neat diagram.
(5/10 marks)
5. What is query decomposition? Explain its steps. (5 marks)
6. What is an operator tree? How is it constructed from an SQL query? Give an example. (5
marks)
7. Compare exhaustive search vs heuristic approach in query optimization. (5 marks)
8. Compare static, dynamic, and hybrid query optimization with advantages and disadvantages.
(5 marks)
9. What is semijoin? How does it help in distributed query processing? (2/5 marks)
[Link] is data localization? Explain its role in distributed query processing. (2/5 marks)