The Division Operator

Concept

Division answers questions of the form which X are related to all Y? Whenever a question contains every, all or each and every, division is the operator being asked for.

Definition

  NOTATION   R divided by S

  Requirement: the attributes of S must be a SUBSET of the
               attributes of R.

  R has attributes ( A, B )
  S has attributes ( B )
  R / S has attributes ( A )

  Result: every value of A that appears in R paired with
          EVERY value of B present in S.

Worked example

  ENROL ( roll_no, code )          CS_COURSE ( code )
  +---------+--------+             +--------+
  |   21    | CS201  |             | CS201  |
  |   21    | CS202  |             | CS202  |
  |   21    | EC101  |             +--------+
  |   22    | CS201  |
  |   22    | CS202  |             "Which students take EVERY
  |   23    | CS201  |              Computing course?"
  |   24    | EC101  |
  +---------+--------+

  ENROL / CS_COURSE

  STEP 1  list what each student takes
            21 -> { CS201, CS202, EC101 }
            22 -> { CS201, CS202 }
            23 -> { CS201 }
            24 -> { EC101 }

  STEP 2  required set from S = { CS201, CS202 }

  STEP 3  keep every student whose set CONTAINS the required set
            21  { CS201, CS202, EC101 } contains it  -> YES
            22  { CS201, CS202 }        contains it  -> YES
            23  { CS201 }               missing CS202 -> no
            24  { EC101 }               missing both  -> no

  RESULT
  +---------+
  | roll_no |
  +---------+
  |   21    |
  |   22    |
  +---------+

  Note that student 21 also takes EC101. Extra courses do
  NOT disqualify - division tests CONTAINMENT, not equality.

That last line is the most common misunderstanding. Division asks whether the required set is contained, not whether the two sets are identical.

Division expressed with primitives

Division is not primitive. The rewrite is worth learning because it explains why the operator works.

  R ( A, B )  divided by  S ( B )

    R / S  =  PROJECT[A](R)  -  PROJECT[A]( ( PROJECT[A](R) x S ) - R )

  Read it from the inside out:

    PROJECT[A](R)              every candidate student
    ... x S                    every candidate paired with every
                               REQUIRED course - the pairs that
                               WOULD have to exist
    ( ... ) - R                the required pairs that DO NOT exist
                               = evidence of a missing course
    PROJECT[A]( ... )          the students who are missing something
    PROJECT[A](R) - ...        all candidates MINUS the deficient ones
                               = the students missing nothing

  Tracing it on the sample data

  PROJECT[roll_no](ENROL)          = { 21, 22, 23, 24 }

  that x CS_COURSE                 = 21-CS201, 21-CS202,
                                     22-CS201, 22-CS202,
                                     23-CS201, 23-CS202,
                                     24-CS201, 24-CS202

  minus ENROL (keep pairs NOT in ENROL)
                                   = 23-CS202, 24-CS201, 24-CS202

  PROJECT[roll_no] of that         = { 23, 24 }   deficient

  { 21,22,23,24 } - { 23,24 }      = { 21, 22 }   ANSWER

  Same result as the direct method, which is the check.

Recognising division in a question

Verifying an answer

Division answers are easy to check by hand, so always check.

1. Write out the set of related values for each candidate.
2. Write out the required set from the divisor.
3. Keep a candidate only if its set contains every required value.
4. Confirm that extra values did not disqualify anyone.

Common mistakes

• Requiring the sets to be equal. Extra values are allowed.
• Dividing when the attributes of S are not a subset of R. The operation is undefined.
• Confusing it with a join. A join answers some, division answers every.
• Forgetting the result attributes. They are the attributes of R that are not in S.
• Assuming an empty divisor gives an empty result. If S is empty, every candidate trivially satisfies the condition, so all of them qualify.

Exam and interview questions

1. Define division and state the requirement on the attributes.
2. Express division using only primitive operators, and explain each step.
3. Give three questions in English that require division.
4. Does a student taking extra courses still qualify? Explain.
5. What are the attributes of the result of R(A,B,C) divided by S(C)?

Practice

1. Given SUPPLY ( supplier, part ) and PART ( part ), compute the suppliers who supply every part, by hand.
2. Add one row to the ENROL example so that student 23 also qualifies, and confirm the result changes.
3. Write the primitive expression for suppliers supplying every part, and trace it step by step.
4. Explain in three sentences why the rewrite works by finding what is missing.

Conclusion

Division answers every questions. It tests containment, not equality, so extra values are fine. It is derived from projection, product and difference by finding the required pairs that are absent, and any answer can be verified by hand in four steps.