View on GitHub

Relational

Educational tool for relational algebra

Downloads | Screenshots | Query language | Optimizations | Shortcuts |

Optimizations

The optimize module provides a way to perform various optimizations on queries. It assumes that the query is correct.

An optimized query should return the same result of the original query. If you find a non working query please submit a bug.

Usage

This code will perform all the available general optimizations on the expression, and will return the optimized expression.

expression=optimizer.general_optimize(expression)

Working with the tree

The expression tree allows to manipulate the expressions.

To obtain the expression from the tree:

str(root)

To generate the tree: (expression is a valid string representing a relational expression)

optimizer.tree(expression)

Each node will have a name, that corresponds to its string representation. Also a kind variable, that specifies if the node is a relation or an operator.

Constants for kind.

optimizer.RELATION=0
optimizer.UNARY=1
optimizer.BINARY=2

Unary operator

Binary operator

Relation

General optimizations

This class of optimizations do not need to have informations on the relations.

The functions are implemented in the optimizations.py module.

They will work on the expression tree and will modify it. The return value is the number of changes performed on the tree.

Duplicated select

Original Optimized
σ k ( σ k(C)) σ k (C)
σ k ( σ j(C)) σ k ⋀ j (C)

The first one will work only if the expression is exactly the same. If the expression is equivalent but different (for example 3+2 is equivalent but different to 2+3) the 2nd kind of optimization will be used.

Down to unions subtractions intersections

Yes the name is crazy.

Original Optimized
σ k (a ᑌ b) σ k(a) ᑌ σ k(b)
σ k (a ᑎ b) σ k(a) ᑎ σ k(b)
σ k (a - b) σ k(a) - σ k(b)

It is an optimization because the selection is a O(n) operation while unions, subtractions or intersections are O(n2) operations. So pushing down the selection, we hope to reduce the size of the problem that the O(n2) operation will have to solve.

Duplicated projection

Original Optimized
π i ( π j (R)) π i (R)

Doing two projection and in fact ignoring the result of the inner one isn't nice.

Selection inside projection

Original Optimized
σ jk (R)) π kj (R))

Performing the selection first, gives us hope that the projection operation (more complex) will be performed on a smaller set.

Swap rename select

Original Optimized
σ kj(R)) ρ jk(R))

renaming the attributes used in the selection, so the operation is still valid.
This is not really an heavy optimization, select is O(n) and rename is O(1), but it is an improvement and it might make other optimizations possible as well, in the next step.

Futile renames

Original Optimized
ρ k➡k(R) completely removes them. If some renames in the list are valid and some are not, the valid ones will be kept.

This optimization is performed before performing subsequent renames optimization.

Original Optimized
ρ k(R)(ρ j(R)) ρ j,k(R)

hence using a single rename operation.
If j,k will contain things like a➡b,b➡c, they will be replaced with a➡c.
If j.k will contain things like a➡b,b➡a, they will be removed. If all the transformations are removed, the rename itself is removed.

Futile union intersection subtraction

A ⋈ A=A ⧑ A=A ⧒ A=A⧓A = A ᑌ A=A ᑎ A=A.
So this optimization tries to locate unions, intersections and joins that share the same left and right operand, and replaces them with the operand itself.
Also A - A=∅.
So it locates subtractions that share the same left and right operand and replaces them with σ False(A). This is not as fast as replacing with an empty relation, but there is no such operator in relational algebra. Anyway Selection is O(n) and subtraction is O(n2), so we're saving time anyway.

This function locates things like:

Original Optimized
R ᑌ R R
R ᑎ R R
R - R σ False (R)
σ k (R) ᑌ R R
σ k (R) ᑎ R σ k (R)
σ k (R) - R σ False (R)
R - σ k (R) σ ¬k (R)

R doesn't have to be a relation. It can be a subtree too.

Swap union renames

Original Optimized
ρ a➡b(R) ᑌ ρ a➡b(Q) ρ a➡b(R ᑌ Q)
ρ a➡b(R) ᑎ ρ a➡b(Q) ρ a➡b(R ᑎ Q)
ρ a➡b(R) - ρ a➡b(Q) ρ a➡b(R - Q)

This will save the space taken by an extra relation needed to perform the 2nd rename.

Swap rename projection

Original Optimized
π kj(R)) ρ jk(R))

This will let rename work on a hopefully smaller set and more important, will hopefully allow further optimizations.

Union and product

Original Optimized
A * B ∪ A * C A * (B ∪ C)

Select union intersect subtract

Original Optimized
σi(a) ᑌ σq(a) σi ∨ q(a)

This will allow the removal of an O(n2) operation like the union.

Both select must work on the same expression, the selects will be united into one, according to the following table:

original query resulting query
σi(a) ᑌ σq(a) σi ∨ q(a)
σi(a) ᑎ σq(a) σi ∧ q(a)
σi(a) - σq(a) σi ∧ ¬q(a)

Specific optimizations

This class of optimizations requires to have knowledge of the specific relations used (meaning that it will need to have access to real instances of the relations to work).

Projection and union

Original Optimized
π a,b,c(A) ∪ π a,b,c(B)π a,b,c(A ∪ B)

If A and B are union compatible.

Selection and product

Original Optimized
σ k (R*Q) σ lj (R) * σ i (Q))

Where j contains only attributes belonging to R, i contains attributes belonging to Q and l contains attributes belonging to both.

Useless projection

If a projection is done on all the attributes, it can be removed.