How does a query tree represent a relational algebra expression? Discuss any three rules for query optimisation, giving example as to when should each rule be applied.
Ans: A query tree is a tree structure which refers to a relational algebra expression. It denotes the input relations as leaf nodes of the tree, and denotes the relational algebra operations as internal nodes. An execution of the query tree contains executing an internal node operation while its operands are available and after that replacing that internal node by the relation which results from executing the operation. The execution terminates while the root node is executed and generates the result relation for the query. For instance, the query tree for the relational algebra expression
∏E_No =(σp_No = 'DB2003' (Assigned_To) :
The three rules for query optimization are like this:
- In a cascade (sequence) of ∏ operations, each one but the last one can be ignored :
∏1(∏2(......∏n ( R))) ≡ ∏1(R )
- If a selection condition c includes just only those attributes A1, A2, .... An in the projection list, the two operations can be commuted :
∏A1, A2,......An (σC (R ) ≡ σC (∏A1, A2, ......An (R ))..... ))
- A conjunctive selection condition can be split up into a cascade of individual σ operations:
σC1 AND C2 AND ....AND Cn (R ) ≡ σC1 (σC2(....(σCn (R ))....))