Steps To Make a Query Tree
Step 1: Execute the leaf nodes with their corresponding internal nodes having the relational algebra operator with the specified conditions to get the resulting tuples that we use for the execution of the next operation.
Step 2: This process continues until we reach the root node, where we PROJECT (π) the required tuples as the output based on the given conditions.
Let’s understand this using some examples:
Example 1: Consider a relational algebra expression:
πp (R ⋈ R.P = S.P S)
Step 1: Write the relations you want to execute as the tree’s Leaf nodes. Here R and S are the relations.
Two Relations R and S
Step 2: Add the condition (here R.P = S.P) with the relational algebra operator as an internal node (or parent node of these two leaf nodes).
JOIN R and S where R.P = S.P
Step 3: Now add the root node that on execution gives the output of the query.
Execution Output
Example 2: Suppose we have a query:
For every project located at ‘Stanford’, list the project number (Pnumber), the controlling department number (Dnum), and the department manager’s last name (Lname), address (Address), and birth date (Bdate). [1]
The relational algebra expression corresponding to this query:
πPnumber, Dnum, Lname, Address, Bdate(((σPlocation = ‘Stanford’(PROJECT)) ⋈
Dnum=Dnumber(DEPARTMENT)) ⋈ Mgr_ssn=Ssn(EMPLOYEE))
Step 1: We will begin with executing the first leaf node PROJECT, and the corresponding internal node σPlocation = ‘Stanford’ as we need these resulting tuples to execute the next operation.
Step 2: Similarly, we will execute the leaf node DEPARTMENT and the intermediate/internal node ⋈ Dnum=Dnumber so that we can move to the next operation.
Step 3: We execute the next operation with the leaf node EMPLOYEE and intermediate node ⋈ Mgr_ssn=Ssn.
Step 4: Now add the root node i.e., πPnumber, Dnum, Lname, Address, Bdate to get the output of the query on execution.
Query Tree in Relational Algebra
A Query Tree is a data structure used for the internal representation of a query in RDBMS. It is also known as the Query Evaluation/Execution Tree. The leaf nodes of the query tree represent the relations, and the internal nodes are the relational algebra operators like SELECT (σ), JOIN (⋈), etc. The root node gives the output of the query on execution.