Relational Algebra Division

Question

I'm currently dealing with a relational algebra division issue. I have the following two relations:

              A | B | C                 B
              --|---|--                ---
              1 | 2 | 3                 2
Relation R =  1 | 2 | 6   Relation T =  
              4 | 2 | 2
              4 | 5 | 6

Now I'm doing the following operation: R ÷ T

When I calculate this, my result is as follows:

              A | C                
              --|--               
              1 | 3               
R ÷ T =       1 | 6    
              4 | 2 

For me it is because for the division I look at those tuples in R which are present in combination with all tuples in T. But when I use a relational algebra calculator, such as RelaX it returns

              A | C                
              --|--               
  R ÷ T =     4 | 2                

Where did I make a mistake? Thanks in advance for any help.

Is there anybody who can help?

Answer 1

Performing division on these schema is not good to fully understand how the operator works. Definitions of this operator are not very clear, and the operation is usually replaced by a combination of other operators.

A clear way to see how this works in your case would consist on create a new instance of R with columns ordered properly defining a new schema: (A,C,B). This is, making the attribute of T appear as the last attribute in A. In this case where you are performing a really simple division, it's pretty straightforward to see the result, but imagine if you had schema R(A,D,B,C) and T(B,D). Here the attributes of T appear with a different order in R, and given some instances with not many tuples would already make it difficult to check just by looking them up.

This might be the most difficult operator defined in relational algebra as a query usually involves concepts from selection, projection and join. Also it's complicated to put it out only on words. A good way of thinking about this operator, is to think about the GROUP BY on SQL. In your example this means using GROUP BY attributes A,C - which would create groups with every combination of different values for these attributes that appear on the schema instance. Each of these groups will have a set of all the values of B associated with the combinations of values of A, C. If you think of the values of the attribute B in the instance of T as a set, you can quickly verify: for each group obtained by grouping by A,C, if the set of values of B in T is included in the set of values of B in R, then the values of A,C are a tuple of the resulting relation.

I know I'm a bit late to this question but I've seen many people confused about this. If it's not clear enough, I leave reference to a document I wrote explaining it much more in detail and with a really good example, HERE.