There are many rules which can be used to transform relational algebra operations to equivalent ones. We will state here some useful rules for query optimization.
In this section, we use the following notation:
- E1, E2, E3,… : denote relational algebra expressions
- X, Y, Z : denote set of attributes
- F, F1, F2, F3 ,… : denote predicates (selection or join conditions)
- Commutativity of Join, Cartesian Product operations
E
1
⊳
⊲
F
E
2
≡
E
2
⊳
⊲
F
E
1
E
1
×
E
2
≡
E
2
×
E
1
E
1
⊳
⊲
F
E
2
≡
E
2
⊳
⊲
F
E
1
E
1
×
E
2
≡
E
2
×
E
1
alignl { stack {
size 12{E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{F} } E rSub { size 8{2} } equiv E rSub { size 8{2} } ⊳ ⊲ rSub { size 8{F} } E rSub { size 8{1} } } {} #
E rSub { size 8{1} } times E rSub { size 8{2} } equiv E rSub { size 8{2} } times E rSub { size 8{1} } {}
} } {}
Note that: Natural Join operator is a special case of Join, so Natuaral Joins are also commnutative.
- Associativity of Join , Cartesian Product operations
(
E
1
∗
E
2
)
∗
E
3
≡
E
1
∗
(
E
2
∗
E
3
)
(
E
1
×
E
2
)
×
E
3
≡
E
1
×
(
E
2
×
E
3
)
(
E
1
⊳
⊲
F1
E
2
)
⊳
⊲
F2
E
3
≡
E
1
⊳
⊲
F1
(
E
2
⊳
⊲
F2
E
3
)
(
E
1
∗
E
2
)
∗
E
3
≡
E
1
∗
(
E
2
∗
E
3
)
(
E
1
×
E
2
)
×
E
3
≡
E
1
×
(
E
2
×
E
3
)
(
E
1
⊳
⊲
F1
E
2
)
⊳
⊲
F2
E
3
≡
E
1
⊳
⊲
F1
(
E
2
⊳
⊲
F2
E
3
)
alignl { stack {
size 12{ \( E rSub { size 8{1} } *E rSub { size 8{2} } \) *E rSub { size 8{3} } equiv E rSub { size 8{1} } * \( E rSub { size 8{2} } *E rSub { size 8{3} } \) } {} #
\( E rSub { size 8{1} } times E rSub { size 8{2} } \) ` times E rSub { size 8{3} } equiv E rSub { size 8{1} } times \( E rSub { size 8{2} } times E rSub { size 8{3} } \) {} #
\( E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{F1} } E rSub { size 8{2} } \) ` ⊳ ⊲ rSub { size 8{F2} } E rSub { size 8{3} } equiv E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{F1} } \( E rSub { size 8{2} } ⊳ ⊲ rSub { size 8{F2} } E rSub { size 8{3} } \) {}
} } {}
Join operation associative in the following manner: F1 involves attributes from only E1 and E2 and F2 involves only attributes from E2 and E3
π
X1
(
π
X2
(
.
.
.
(
π
Xn
(
E
)
)
.
.
.
)
)
≡
π
X1
(
E
)
π
X1
(
π
X2
(
.
.
.
(
π
Xn
(
E
)
)
.
.
.
)
)
≡
π
X1
(
E
)
size 12{π rSub { size 8{X1} } \( π rSub { size 8{X2} } \( "." "." "." \( π rSub { size 8{ ital "Xn"} } \( E \) \) "." "." "." \) \) equiv π rSub { size 8{X1} } \( E \) } {}
σ
F1
∧
F2
∧
.
.
.
∧
Fn
(
E
)
≡
σ
F1
(
σ
F2
(
.
.
.
(
σ
Fn
(
E
)
)
.
.
.
)
)
σ
F1
∧
F2
∧
.
.
.
∧
Fn
(
E
)
≡
σ
F1
(
σ
F2
(
.
.
.
(
σ
Fn
(
E
)
)
.
.
.
)
)
size 12{σ rSub { size 8{F1 and F2 and "." "." "." and ital "Fn"} } \( E \) equiv σ rSub { size 8{F1} } \( σ rSub { size 8{F2} } \( "." "." "." \( σ rSub { size 8{ ital "Fn"} } \( E \) \) "." "." "." \) \) } {}
- Commutativity of Selection
σ
F1
(
σ
F2
(
E
)
)
≡
σ
F2
(
σ
F1
(
E
)
)
σ
F1
(
σ
F2
(
E
)
)
≡
σ
F2
(
σ
F1
(
E
)
)
size 12{σ rSub { size 8{F1} } \( σ rSub { size 8{F2} } \( E \) \) equiv σ rSub { size 8{F2} } \( σ rSub { size 8{F1} } \( E \) \) } {}
- Commuting Selection with Projection
π
X
(
σ
F
(
E
)
)
≡
σ
F
(
π
X
(
E
)
)
π
X
(
σ
F
(
E
)
)
≡
σ
F
(
π
X
(
E
)
)
size 12{π rSub { size 8{X} } \( σ rSub { size 8{F} } \( E \) \) equiv σ rSub { size 8{F} } \( π rSub { size 8{X} } \( E \) \) } {}
This rule holds if the selection condition F involves only the attributes in set X.
- Selection with Cartesian Product and Join
- If all the attributes in the selection condition F involve only the attributes of one of the expression say E1, then the selection and Join can be combined as follows:
σ
F
(
E
1
⊳
⊲
C
E
2
)
≡
(
σ
F
(
E
1
)
)
⊳
⊲
C
E
2
σ
F
(
E
1
⊳
⊲
C
E
2
)
≡
(
σ
F
(
E
1
)
)
⊳
⊲
C
E
2
size 12{σ rSub { size 8{F} } \( E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{C} } E rSub { size 8{2} } \) equiv \( σ rSub { size 8{F} } \( E rSub { size 8{1} } \) \) ⊳ ⊲ rSub { size 8{C} } E rSub { size 8{2} } } {}
- If the selection condition F = F1 AND F2 where F1 involves only attributes of expression E1 and F2 involves only attribute of expression E2 then we have:
σ
F1
∧
F2
(
E
1
⊳
⊲
C
E
2
)
≡
(
σ
F1
(
E
1
)
)
⊳
⊲
C
(
σ
F2
(
E
2
)
)
σ
F1
∧
F2
(
E
1
⊳
⊲
C
E
2
)
≡
(
σ
F1
(
E
1
)
)
⊳
⊲
C
(
σ
F2
(
E
2
)
)
size 12{σ rSub { size 8{F1 and F2} } \( E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{C} } E rSub { size 8{2} } \) equiv \( σ rSub { size 8{F1} } \( E rSub { size 8{1} } \) \) ⊳ ⊲ rSub { size 8{C} } \( σ rSub { size 8{F2} } \( E rSub { size 8{2} } \) \) } {}
- If the selection condition F = F1 AND F2 where F1 involves only attributes of expression E1 and F2 involves attributes from both E1 and E2 then we have:
σ
F1
∧
F2
(
E
1
⊳
⊲
C
E
2
)
≡
σ
F2
(
(
σ
F1
(
E
1
)
)
⊳
⊲
C
E
2
)
σ
F1
∧
F2
(
E
1
⊳
⊲
C
E
2
)
≡
σ
F2
(
(
σ
F1
(
E
1
)
)
⊳
⊲
C
E
2
)
size 12{σ rSub { size 8{F1 and F2} } \( E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{C} } E rSub { size 8{2} } \) equiv σ rSub { size 8{F2} } \( ` \( σ rSub { size 8{F1} } \( E rSub { size 8{1} } \) \) ⊳ ⊲ rSub { size 8{C} } E rSub { size 8{2} } \) } {}
The same rule apply if the Join operation replaced by a Cartersian Product operation.
- Commuting Projection with Join and Cartesian Product
- Let X, Y be the set of attributes of E1 and E2 respectively. If the join condition involves only attributes in XY (union of two sets) then :
π
XY
(
E
1
⊳
⊲
F
E
2
)
≡
π
X
(
E
1
)
⊳
⊲
F
π
Y
(
E
2
)
π
XY
(
E
1
⊳
⊲
F
E
2
)
≡
π
X
(
E
1
)
⊳
⊲
F
π
Y
(
E
2
)
size 12{π rSub { size 8{ ital "XY"} } \( E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{F} } E rSub { size 8{2} } \) equiv π rSub { size 8{X} } \( E rSub { size 8{1} } \) ⊳ ⊲ rSub { size 8{F} } π rSub { size 8{Y} } \( E rSub { size 8{2} } \) } {}
The same rule apply when replace the Join by Cartersian Product
- If the join condition involves additional attributes say Z of E1 and W of E2 and Z,W are not in XY then :
π
XY
(
E
1
⊳
⊲
F
E
2
)
≡
π
XY
(
π
XZ
(
E
1
)
⊳
⊲
F
π
YW
(
E
2
)
)
π
XY
(
E
1
⊳
⊲
F
E
2
)
≡
π
XY
(
π
XZ
(
E
1
)
⊳
⊲
F
π
YW
(
E
2
)
)
size 12{π rSub { size 8{ ital "XY"} } \( E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{F} } E rSub { size 8{2} } \) equiv π rSub { size 8{ ital "XY"} } \( π rSub { size 8{ ital "XZ"} } \( E rSub { size 8{1} } \) ⊳ ⊲ rSub { size 8{F} } π rSub { size 8{ ital "YW"} } \( E rSub { size 8{2} } \) \) } {}
- Commuting Selection with set operations
The Selection commutes with all three set operations (Union, Intersect, Set Difference) .
σ
F
(
E
1
∪
E
2
)
≡
(
σ
F
(
E
1
)
)
∪
(
σ
F
(
E
2
)
)
σ
F
(
E
1
∪
E
2
)
≡
(
σ
F
(
E
1
)
)
∪
(
σ
F
(
E
2
)
)
size 12{σ rSub { size 8{F} } \( E rSub { size 8{1} } union E rSub { size 8{2} } \) equiv \( σ rSub { size 8{F} } \( E rSub { size 8{1} } \) \) union \( σ rSub { size 8{F} } \( E rSub { size 8{2} } \) \) } {}
The same rule apply when replace Union by Intersection or Set Difference
- Commuting Projection with Union
π
X
(
E
1
∪
E
2
)
≡
(
π
X
(
E
1
)
)
∪
(
π
X
(
E
2
)
)
π
X
(
E
1
∪
E
2
)
≡
(
π
X
(
E
1
)
)
∪
(
π
X
(
E
2
)
)
size 12{π rSub { size 8{X} } \( E rSub { size 8{1} } union E rSub { size 8{2} } \) equiv \( π rSub { size 8{X} } \( E rSub { size 8{1} } \) \) union \( π rSub { size 8{X} } \( E rSub { size 8{2} } \) \) } {}
- Commutativity of set operations: The Union and Intersection are commutative but Set Difference is not.
E
1
∪
E
2
≡
E
2
∪
E
1
E
1
∩
E
2
≡
E
2
∩
E
1
E
1
∪
E
2
≡
E
2
∪
E
1
E
1
∩
E
2
≡
E
2
∩
E
1
alignl { stack {
size 12{E rSub { size 8{1} } union E rSub { size 8{2} } equiv E rSub { size 8{2} } union E rSub { size 8{1} } } {} #
E rSub { size 8{1} } intersection E rSub { size 8{2} } equiv E rSub { size 8{2} } intersection E rSub { size 8{1} } {}
} } {}
- Associativity of set operations: Union and Intersection are associative but Set Difference is not
(
E
1
∪
E
2
)
∪
E
3
≡
E
1
∪
(
E
2
∪
E
3
)
(
E
1
∩
E
2
)
∩
E
3
≡
E
1
∩
(
E
2
∩
E
3
)
(
E
1
∪
E
2
)
∪
E
3
≡
E
1
∪
(
E
2
∪
E
3
)
(
E
1
∩
E
2
)
∩
E
3
≡
E
1
∩
(
E
2
∩
E
3
)
alignl { stack {
size 12{ \( E rSub { size 8{1} } union E rSub { size 8{2} } \) union E rSub { size 8{3} } equiv E rSub { size 8{1} } union \( E rSub { size 8{2} } union E rSub { size 8{3} } \) } {} #
\( E rSub { size 8{1} } intersection E rSub { size 8{2} } \) intersection E rSub { size 8{3} } equiv E rSub { size 8{1} } intersection \( E rSub { size 8{2} } intersection E rSub { size 8{3} } \) {}
} } {}
- Converting a Catersian Product followed by a Selection into Join.
If the selection condition corresponds to a join condition we can do the convert as follows:
σ
F
(
E
1
×
E
2
)
≡
E
1
⊳
⊲
F
E
2
σ
F
(
E
1
×
E
2
)
≡
E
1
⊳
⊲
F
E
2
size 12{σ rSub { size 8{F} } \( E rSub { size 8{1} } times E rSub { size 8{2} } \) equiv E rSub { size 8{1} } ⊳ ⊲ rSub { size 8{F} } E rSub { size 8{2} } } {}
