Building Relational Algebra Expressions

Concept

Individual operators are only half the subject. The examinable skill is composing them into an expression that answers a question, and knowing which rewrites preserve the answer.

A method for writing an expression

1. Identify the relations the question needs. Anything not needed is a cost, not a help.
2. Join them on their common attributes, one at a time.
3. Apply the conditions as selections.
4. Project the attributes actually asked for, last.
5. Then optimise: push selections down and projections down.

Write it correct first, then rewrite it cheap. Trying to do both at once is how errors get in.

Worked example

Names of Computing students who scored more than 80 in a four credit course.

  STEP 1  relations needed: STUDENT, ENROL, COURSE

  STEP 2  join them
            ( STUDENT natural join ENROL ) natural join COURSE

  STEP 3  apply conditions
            SELECT[dept = CS AND marks > 80 AND credits = 4]( ... )

  STEP 4  project
            PROJECT[name]( ... )

  THE CORRECT, UNOPTIMISED EXPRESSION

    PROJECT[name](
      SELECT[dept = CS AND marks > 80 AND credits = 4](
        ( STUDENT natural join ENROL ) natural join COURSE
      )
    )

The expression tree

                 PROJECT[name]
                       |
      SELECT[dept=CS AND marks>80 AND credits=4]
                       |
                  natural join
                    /       
            natural join    COURSE
              /      
        STUDENT    ENROL

  Read a tree BOTTOM UP: leaves are relations, data flows
  upward, the root produces the answer.

  The problem with this tree: the joins run FIRST on the
  full relations, and the selection throws most of it away
  afterwards. Every discarded tuple was joined for nothing.

Equivalence rules

These rewrites always preserve the result. They are what an optimiser is permitted to do.

Optimising the example

  Push each condition down to the relation that owns it:

    dept = CS      belongs to STUDENT
    marks > 80     belongs to ENROL
    credits = 4    belongs to COURSE

  THE OPTIMISED EXPRESSION

    PROJECT[name](
      ( ( SELECT[dept = CS](STUDENT)
          natural join
          SELECT[marks > 80](ENROL) )
        natural join
        SELECT[credits = 4](COURSE) )
    )

  THE OPTIMISED TREE

                 PROJECT[name]
                       |
                  natural join
                    /       
            natural join   SELECT[credits=4]
              /                  |
    SELECT[dept=CS] SELECT[marks>80]  COURSE
          |             |
      STUDENT        ENROL

  Same answer. Every join now receives far fewer tuples.

Why it is faster, with numbers

  Assume 4,000 students, 30,000 enrolments, 200 courses.
  Say 1,500 students are CS, 3,000 enrolments exceed 80
  marks, and 60 courses carry 4 credits.

  UNOPTIMISED
    STUDENT join ENROL     joins 4,000 with 30,000
                           produces about 30,000 tuples
    join COURSE            joins 30,000 with 200
                           produces about 30,000 tuples
    then discards almost all of them

  OPTIMISED
    selections first       1,500 and 3,000 and 60
    first join             1,500 with 3,000  -> far smaller
    second join            small with 60

  The answer is identical. The work is not.
  This is the entire justification for the heuristic
  "push selections down", and Phase 14 formalises it.

More worked expressions

  "Students who have not enrolled in any course"
      STUDENT antijoin ENROL
    or
      PROJECT[roll_no](STUDENT) - PROJECT[roll_no](ENROL)

  "Courses taken by every Computing student"
      needs division, with the divisor being the set of
      CS students:
      ENROL / PROJECT[roll_no](SELECT[dept=CS](STUDENT))
      -- careful: this divides ENROL(roll_no, code) by a
      -- relation over roll_no, so the result is over code

  "Departments having at least one student scoring above 90"
      PROJECT[dept](
        SELECT[marks > 90](STUDENT natural join ENROL) )

  "Pairs of students in the same department"
      needs RENAME, because STUDENT appears twice:
      SELECT[A.dept = B.dept AND A.roll_no < B.roll_no](
        RENAME[A](STUDENT) x RENAME[B](STUDENT) )
      -- the < condition removes self pairs and mirror
      -- duplicates in one stroke

Common mistakes

• Projecting too early. An attribute a later step needs is gone.
• Pushing a selection below a join it depends on. A condition referring to attributes of both relations cannot move below the join.
• Forgetting rename for a self join. The expression is ambiguous without it.
• Optimising before the expression is correct. Get the answer right first.
• Assuming every rewrite is valid. Only the listed equivalences are guaranteed.

Exam and interview questions

1. Give a method for writing an algebra expression from an English question.
2. Draw the expression tree for a three relation query and mark the data flow.
3. State five equivalence rules and say which one drives the main heuristic.
4. Why is pushing selections down beneficial? Justify with cardinalities.
5. Which selections cannot be pushed below a join?

Practice

1. Write and optimise an expression for the titles of four credit courses taken by Electronics students.
2. Draw both trees for that query and mark where the tuple count drops.
3. Write an expression for students enrolled in Databases but not Networks.
4. Write an expression for the student with the same department as student 21, excluding student 21.

Conclusion

Compose an expression by joining, filtering, then projecting, and only then rewrite it. Expression trees make the order visible, and the equivalence rules are exactly the freedom a query optimiser has — which is why Phase 14 begins where this note ends.