Transforming Relational Expressions

The first step of the optimizer says to implement such expressions that are logically equivalent to the given expression. For implementing such a step, we use the equivalence rule that describes the method to transform the generated expression into a logically equivalent expression.

Although there are different ways through which we can express a query, with different costs. But for expressing a query in an efficient manner, we will learn to create alternative as well as equivalent expressions of the given expression, instead of working with the given expression. Two relational-algebra expressions are equivalent if both the expressions produce the same set of tuples on each legal database instance. A legal database instance refers to that database system which satisfies all the integrity constraints specified in the database schema. However, the sequence of the generated tuples may vary in both expressions, but they are considered equivalent until they produce the same tuples set.

Equivalence Rules

The equivalence rule says that expressions of two forms are the same or equivalent because both expressions produce the same outputs on any legal database instance. It means that we can possibly replace the expression of the first form with that of the second form and replace the expression of the second form with an expression of the first form. Thus, the optimizer of the query-evaluation plan uses such an equivalence rule or method for transforming expressions into the logically equivalent one.

The optimizer uses various equivalence rules on relational-algebra expressions for transforming the relational expressions. For describing each rule, we will use the following symbols:

θ, θ₁, θ₂ … : Used for denoting the predicates.

L₁, L₂, L₃ … : Used for denoting the list of attributes.

E, E₁, E₂ …. : Represents the relational-algebra expressions.

Let's discuss a number of equivalence rules:

Rule 1: Cascade of σ

This rule states the deconstruction of the conjunctive selection operations into a sequence of individual selections. Such a transformation is known as a cascade of σ.

σ_{θ1 ᴧ θ 2} (E) = σ_θ1 (σ_θ2 (E))

Rule 2: Commutative Rule

a) This rule states that selections operations are commutative.

σ_θ1 (σ_θ2 (E)) = σ _θ2 (σ_θ1 (E))

b) Theta Join (θ) is commutative.

E₁ ⋈ _θ E ₂ = E ₂ ⋈ _θ E ₁ (θ is in subscript with the join symbol)

However, in the case of theta join, the equivalence rule does not work if the order of attributes is considered. Natural join is a special case of Theta join, and natural join is also commutative.

However, in the case of theta join, the equivalence rule does not work if the order of attributes is considered. Natural join is a special case of Theta join, and natural join is also commutative.

Rule 3: Cascade of ∏

This rule states that we only need the final operations in the sequence of the projection operations, and other operations are omitted. Such a transformation is referred to as a cascade of ∏.

∏L1 (∏L2 (. . . (∏Ln (E)) . . . )) = ∏L1 (E)

Rule 4: We can combine the selections with Cartesian products as well as theta joins

Rule 4: We can combine the selections with Cartesian products as well as theta joins

1. σ_θ (E₁ x E₂) = E_1θ ⋈ E₂
2. σ_θ1 (E₁ ⋈ _θ2 E₂) = E₁ ⋈ _θ1ᴧθ2 E₂

Rule 5: Associative Rule

a) This rule states that natural join operations are associative.

(E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3)

b) Theta joins are associative for the following expression:

(E₁ ⋈ _θ1 E₂) ⋈ _θ2ᴧθ3 E₃ = E₁ ⋈ _θ1ᴧθ3 (E₂ ⋈ _θ2 E₃)

In the theta associativity, θ2 involves the attributes from E2 and E3 only. There may be chances of empty conditions, and thereby it concludes that Cartesian Product is also associative.

Note: The equivalence rules of associativity and commutatively of join operations are essential for join reordering in query optimization.

Rule 6: Distribution of the Selection operation over the Theta join.

Under two following conditions, the selection operation gets distributed over the theta-join operation:

a) When all attributes in the selection condition θ₀ include only attributes of one of the expressions which are being joined.

σ_θ0 (E₁ ⋈ _θ E₂) = (σ_θ0 (E₁)) ⋈ _θ E₂

b) When the selection condition θ₁ involves the attributes of E₁ only, and θ₂ includes the attributes of E₂ only.

σ_{θ1ꓥ θ2} (E₁ ⋈ _θ E₂) = (σ_θ1 (E₁)) ⋈ _θ ((σ_θ2 (E₂))

Rule 7: Distribution of the projection operation over the theta join.

Under two following conditions, the selection operation gets distributed over the theta-join operation:

a) Assume that the join condition θ includes only in L₁ υ L₂ attributes of E₁ and E₂ Then, we get the following expression:

∏_L1υL2 (E₁ ⋈ _θ E₂) = (∏_L1 (E₁)) ⋈ _θ (∏_L2 (E₂))

b) Assume a join as E₁ ⋈ E₂. Both expressions E₁ and E₂ have sets of attributes as L₁ and L₂. Assume two attributes L₃ and L₄ where L₃ be attributes of the expression E₁, involved in the θ join condition but not in L₁ υ L₂ Similarly, an L₄ be attributes of the expression E₂ involved only in the θ join condition and not in L₁ υ L₂ attributes. Thus, we get the following expression:

∏_L1υL2 (E₁ ⋈ _θ E₂) = ∏_L1υL2 ((∏_L1υL3 (E₁)) ⋈ _θ ((∏_L2υL4 (E₂)))

Rule 8: The union and intersection set operations are commutative.

E₁ υ E₂ = E₂ υ E₁

E₁ ꓵ E₂ = E₂ ꓵ E₁

However, set difference operations are not commutative.

Rule 9: The union and intersection set operations are associative.

(E₁ υ E₂) υ E₃ = E₁ υ (E₂ υ E₃)

(E₁ ꓵ E₂) ꓵ E₃ = E₁ ꓵ (E₂ ꓵ E₃)

Rule 10: Distribution of selection operation on the intersection, union, and set difference operations.

The below expression shows the distribution performed over the set difference operation.

σ_p (E₁ − E₂) = σ_p(E₁) − σ_p(E₂)

We can similarly distribute the selection operation on υ and ꓵ by replacing with -. Further, we get:

σ_p (E₁ − E₂) = σ_p(E₁) −E₂

Rule 11: Distribution of the projection operation over the union operation.

This rule states that we can distribute the projection operation on the union operation for the given expressions.

∏_L (E₁ υ E₂) = (∏_L (E₁)) υ (∏_L (E₂))

Apart from these discussed equivalence rules, there are various other equivalence rules also.