CO2

🧩 1. Dependency Preservation and Lossless Design

a) Functional Dependency (FD)

 A functional dependency (FD) is a constraint between two sets of attributes in a

relation.
 If A → B, then for any two tuples in the relation, if they have the same value for A,
they must have the same value for B.

b) Lossless (Non-Loss) Decomposition

A decomposition of relation R into R₁ and R₂ is lossless if the original relation can be

reconstructed by joining R₁ and R₂ without generating spurious tuples.

Condition for Lossless Join:

Decomposition of R into R₁ and R₂ is lossless if and only if:

[
(R₁ ∩ R₂) → (R₁ - R₂) \text{ or } (R₁ ∩ R₂) → (R₂ - R₁)
]
That is, the common attributes form a key for at least one of the decomposed relations.

Example:

R(A, B, C)
FDs: A → B
Decompose into R1(A, B) and R2(A, C)
Common attribute = A
A → B (satisfies condition) → Lossless

c) Dependency Preservation

A decomposition is dependency preserving if all the functional dependencies in the original

relation can be derived from the dependencies in the decomposed relations without
performing a join.

Formally:
Let F = set of original FDs, and Fi = projection of F on Ri.
Decomposition is dependency preserving if:

(F₁ ∪ F₂ ∪ ... ∪ Fₙ)⁺ = F⁺

[

Why Important?
  Checking dependency preservation ensures that enforcing FDs on smaller tables
ensures data consistency for the entire relation.

Example:

R(A, B, C), F = {A → B, B → C}
Decompose into R1(A, B), R2(B, C)

(F1 ∪ F2)+ = {A → B, B → C, A → C} = F+ ⇒ Dependency preserved

F1 = {A → B}, F2 = {B → C}

d) Desirable Decomposition

A good decomposition should be:

1. Lossless Join
2. Dependency Preserving
3. Minimizes redundancy

🔍 2. Query Processing and Optimization

a) Query Processing

It refers to the steps used by a DBMS to convert a high-level query (like SQL) into an
efficient low-level execution plan.

Steps:

1. Parsing and Translation: SQL → relational algebra expression.

2. Optimization: Choosing the most efficient execution plan.
3. Evaluation: Execution of the plan to get the result.

b) Evaluation of Relational Algebra Expressions

Different algorithms exist for each relational algebra operation:

Operation Common Evaluation Methods

Selection (σ) Linear search, Binary search, Index scan
Projection (π) Sorting + duplicate elimination
Join (⨝) Nested loop join, Sort-merge join, Hash join
Union / Intersection / Difference Sorting-based or hashing-based methods
Goal:
Minimize I/O cost and CPU time while maintaining correctness.

c) Query Equivalence

Two relational algebra expressions E₁ and E₂ are equivalent if, for every legal database
instance, they produce the same result.

E₁ ≡ E₂ ⇔ for all valid database states, E₁(DB) = E₂(DB)

Examples of Equivalences:

1. Commutativity:

o R⨝S≡S⨝R
o σ₍θ₁₎(σ₍θ₂₎(R)) ≡ σ₍θ₂₎(σ₍θ₁₎(R))

o π₍A₎(π₍B₎(R)) ≡ π₍A₎(R) if A ⊆ B
2. Projection:

o σ₍θ₎(R ⨝ S) ≡ (σ₍θ₁₎(R)) ⨝ S if θ only involves attributes of R

3. Selection with Join:

These equivalences are used in query optimization.

🔗 3. Join Strategies
a) Nested Loop Join

 For each tuple in outer relation (R), compare with each tuple in inner relation (S).
 Cost: O(|R| × |S|)
 Improvement: Block nested loop join or indexed nested loop join.

b) Sort-Merge Join

 Sort both relations on join attributes.

 Merge them like merge-sort.
 Efficient for large, sorted data.

c) Hash Join

 Hash both relations using the join key.

 For each bucket in R, find matching tuples in corresponding bucket of S.
 Works well when relations fit in memory.
⚙️4. Query Optimization Algorithms
a) Heuristic (Rule-Based) Optimization

 Applies transformation rules to algebraic expressions to find a more efficient

equivalent one.
 Example rules:
o Perform selection and projection early.
o Combine Cartesian product + selection into join.
o Use smaller intermediate relations first.

b) Cost-Based Optimization

 DBMS generates multiple equivalent execution plans.

 Estimates cost of each (I/O, CPU, network, memory).
 Selects the least-cost plan.

Components:

1. Statistics: Table size, index info, distinct values.

2. Cost Model: I/O + CPU cost formulas.
3. Plan Enumeration: Different join orders and methods.
4. Plan Selection: Pick plan with minimum estimated cost.

📘 DBMS Notes: Dependency Preservation, Lossless Design, and Query

Processing & Optimization

🧩 1. Dependency Preservation and Lossless Design

1.1 Functional Dependencies (FDs)

 Define relationships between attributes.

 Denoted as X → Y, meaning if two tuples agree on X, they must also agree on Y.
 Used to identify redundancy and help in normalization.

1.2 Decomposition

When a large relation is broken down into smaller relations to achieve higher normal forms,
we must ensure two properties:

1. Lossless Join Property

2. Dependency Preservation Property
1.3 Lossless Join Property

A decomposition of relation R into subrelations R₁, R₂, …, Rₙ is lossless if:

R1⋈R2⋈...⋈Rn=RR₁ ⋈ R₂ ⋈ ... ⋈ Rₙ = RR1⋈R2⋈...⋈Rn=R

(no spurious tuples after joining).

Condition for Lossless Join (for binary decomposition):

Decomposition of R into R₁ and R₂ is lossless if at least one of the following holds:

 (R₁ ∩ R₂) → (R₁ - R₂)

 (R₁ ∩ R₂) → (R₂ - R₁)

That means, the common attributes form a superkey in at least one of the decomposed
relations.

Example:

R(A, B, C), FD = {A → B}
Decompose into: R1(A, B), R2(A, C)
R1 ∩ R2 = {A}
Since A → B (A is a key for R1) → lossless

Importance:

 Guarantees that we can reconstruct the original relation exactly.

 Prevents data loss and anomalies due to decomposition.

1.4 Dependency Preservation Property

A decomposition preserves dependencies if all functional dependencies in the original

relation can be enforced without performing a join.

Formally:
Let F = set of FDs on R, and Fi = projection of F on Ri.
Then decomposition is dependency preserving if:

(F1∪F2∪...∪Fn)+=F+(F₁ ∪ F₂ ∪ ... ∪ Fₙ)⁺ = F⁺(F1∪F2∪...∪Fn)+=F+

Example:

R(A, B, C), F = {A → B, B → C}
Decompose: R1(A, B), R2(B, C)

Closure: (F1 ∪ F2)+ = {A → B, B → C, A → C} = F+

F1 = {A → B}, F2 = {B → C}

→ Dependency preserved
Why it matters:

If dependency preservation is violated:

 Some FDs can’t be checked without joining tables.

 Integrity enforcement becomes expensive.

1.5 Balancing Both Properties

Sometimes, lossless join and dependency preservation cannot both be achieved

simultaneously (especially in BCNF).
In such cases, lossless join is prioritized (since correctness is more critical).

🔍 2. Query Processing
Query processing is the series of steps the DBMS uses to transform an SQL query into an
efficient execution plan and retrieve the result.

2.1 Phases of Query Processing

1. Parsing and Translation

o SQL query → relational algebra expression.
o Check syntax and semantics.
2. Optimization
o Multiple equivalent relational algebra expressions exist.
o Choose the most efficient one using query optimization algorithms.
3. Evaluation
o Execute the final plan using evaluation algorithms.

2.2 Measures of Query Cost

Cost = Time taken to execute a query

Includes:

 I/O cost: Disk read/write operations (dominant factor)

 CPU cost: Computations and comparisons
 Communication cost: In distributed databases
2.3 Evaluation of Relational Algebra Operations

Operation Common Methods Notes

Linear scan, Binary search, Index

Selection (σ) Index helps reduce cost
lookup

Sorting, Hashing to remove

Projection (π) Often combined with selection
duplicates

Join (⨝) Nested Loop, Sort-Merge, Hash Join Most expensive operation

Requires both inputs sorted or

Set Operations (∪, ∩, −) Sort-merge, Hash-based methods
hashed

Aggregation (SUM, AVG,

Sort or hash-based grouping Often part of query optimization
…)

🧮 3. Query Equivalence
Two relational algebra expressions E₁ and E₂ are equivalent if:

E1(D)=E2(D)E₁(D) = E₂(D)E1(D)=E2(D)

for all legal database states D.

3.1 Common Equivalence Rules

Rule Expression Description

Commutativity R⨝S≡S⨝R Join order doesn’t matter

Associativity (R ⨝ S) ⨝ T ≡ R ⨝ (S ⨝ T) Can reorder joins

Selection Cascade σ₍θ₁∧θ₂₎(R) ≡ σ₍θ₁₎(σ₍θ₂₎(R)) Split selection condition

Selection Pushdown σ₍θ₎(R ⨝ S) ≡ (σ₍θ₁₎(R)) ⨝ (σ₍θ₂₎(S)) Apply selection before join

Projection Cascade π₍A₎(π₍B₎(R)) ≡ π₍A₎(R) if A ⊆ B Redundant projection removed

These rules allow query rewriting for efficiency.

🔗 4. Join Strategies
Joins are often the most expensive part of query processing, so different strategies are used:

4.1 Nested Loop Join

For each tuple in R (outer relation), scan S (inner relation).

Cost: O(|R| × |S|)

Optimizations:

 Block Nested Loop Join: Read multiple tuples of R into memory.

 Indexed Nested Loop Join: Use index on S to find matching tuples quickly.

4.2 Sort-Merge Join

Steps:

1. Sort R and S on join attributes.

2. Merge the two sorted lists to find matching tuples.

Cost: O(|R| log |R| + |S| log |S|) for sorting + O(|R| + |S|) for merging.

Best used when:

 Relations are already sorted.

 Useful for range joins.

4.3 Hash Join

Steps:

1. Hash both R and S on the join attribute.

2. For each hash bucket in R, scan corresponding bucket in S.

Cost: O(|R| + |S|)

Best used when:

 Equi-joins or natural joins.

 Hash fits in memory.
4.4 Comparison Summary

Join Type When to Use Advantages Disadvantages

Nested Loop Small relations Simple Expensive for large data

Sort-Merge Sorted data Handles range joins Sorting cost

Hash Join Equi-joins Fast Needs hash function, memory

⚙️5. Query Optimization Algorithms

5.1 Heuristic (Rule-Based) Optimization

 Applies rules of relational algebra to simplify queries.

 Faster, used by many DBMS as a first step.

Common Heuristics:

1. Perform selection and projection early.

2. Replace Cartesian product + selection with join.
3. Use smaller intermediate results first.
4. Apply projection to eliminate unnecessary attributes.
5. Reorder joins using associativity and commutativity.

5.2 Cost-Based Optimization

 DBMS generates multiple equivalent query plans.

 Estimates their costs (based on data statistics).
 Chooses the lowest-cost plan.

Steps:

1. Generate alternative query plans.

2. Estimate cost for each plan using table statistics.
3. Select the plan with minimum estimated cost.

Inputs:

 Table size
 Indexes
 Selectivity of predicates
 Available memory
Example:
Optimizer may choose hash join over nested loop join if relations are large and equi-join is
used.

5.3 Dynamic Programming in Optimization

Used for complex queries with multiple joins.

 Enumerate all possible join orders.

 Use previously computed optimal subplans.
 Example algorithm: System R Optimizer.

CO3
Storage Strategies Overview
Storage strategies in databases are used to organize and access data efficiently. The main
techniques are:

 Indices (Indexes)
 B-Trees
 Hashing

📘 1. Indices (Indexes)
Definition:

An index is a data structure that improves the speed of data retrieval operations on a
database table at the cost of additional space and maintenance time.

Purpose:

 To locate data quickly without scanning every row in a table.

 Works similarly to an index in a book — it helps jump directly to the desired data.

Types of Indices:

1. Primary Index
o Built on a table’s primary key.
o Data is physically ordered according to the key.
o One per table.
 2. Secondary Index
o Built on non-key attributes.
o Does not affect physical data order.
o Multiple secondary indices allowed.
3. Clustered Index
o The order of rows in storage matches the order of the index.
o Usually one per table.
4. Non-clustered Index
o Stores a separate list of key values with pointers to the actual data.

Advantages:

 Faster query performance.

 Efficient sorting and searching.
 Reduces I/O cost.

Disadvantages:

 Extra space overhead.

 Slower write operations (insert, update, delete) due to index maintenance.

🌳 2. B-Trees (Balanced Trees)

Definition:

A B-Tree is a self-balancing tree data structure that maintains sorted data and allows
searches, insertions, deletions, and sequential access in logarithmic time (O(log n)).

Key Features:

 All leaf nodes are at the same level.

 Each node can have multiple keys and children.
 Data is kept sorted within nodes.

Structure:

 Internal nodes contain keys and pointers to child nodes.

 Leaf nodes contain data records or pointers to them.

Operations:

1. Search: Starts from root; traverse down based on key comparisons.

2. Insertion: Insert key in correct node; if full, split node and propagate up.
3. Deletion: Remove key; if underflow occurs, borrow or merge nodes.

Variants:
  B+ Tree (most common in databases):
o All data stored in leaf nodes.
o Leaf nodes are linked, supporting efficient range queries.

Advantages:

 Efficient for range searches.

 Reduces disk I/O due to high branching factor.
 Always balanced.

Disadvantages:

 Slightly more complex to maintain than hashing.

 May be less efficient for single-record lookups.

#️3. Hashing
Definition:

Hashing is a technique to map data of arbitrary size to fixed-size values (hash values) using a
hash function.

How It Works:

 A hash function h(key) computes a bucket address where the record is stored.
 Example:
h(key) = key % number_of_buckets

Types:

1. Static Hashing
o The number of buckets is fixed.
o Performance degrades when data grows.
2. Dynamic Hashing
o Bucket count grows or shrinks as data changes.
o Examples:
 Extendible Hashing
 Linear Hashing

Collisions:

When two keys hash to the same bucket.

 Collision Resolution Techniques:

o Chaining: Linked list of records in the same bucket.
o Open Addressing: Find next free slot (linear or quadratic probing).
Advantages:

 Very fast exact match lookups (O(1) average time).

 Simple to implement.

Disadvantages:

 Poor for range queries.

 Performance depends on a good hash function.
 Rehashing is expensive.

⚖️Comparison Table
Feature Index (General) B-Tree / B+ Tree Hashing
Access Type Sequential / Random Ordered Random
Search Time O(log n) O(log n) O(1) average
Supports Range Queries ✅ Yes ✅ Yes ❌ No
Insertion/Deletion Cost Medium Moderate Low (avg)
Space Overhead High Moderate Moderate
Ideal For General indexing Range & sorted queries Exact match lookups

🧠 Summary
 Indices: General mechanism to speed up data access.
 B-Trees / B+ Trees: Balanced, order-preserving trees; ideal for range queries.
 Hashing: Fast key-based access; best for equality searches.