How to understand `u=r÷s`, the division operator, in relational algebra?

Question

let be a database having the following relational-schemes: R(A,B,D) and S(A,B) with the attributes of same name in the same domain and with the instances r and s respectively.

An instance of r

An instance of s

What is the scheme and what are the tuples of u=r÷s? How to define them in English with r and s?

My attempt

I know that

u=r÷s=

Which leads me to think that it would only be an array of one column A, but I'm not sure enough to know what will be ther result within the array.

Can you help me understand u=r÷s?

Answer 1

An intuitive property of the division operator of the relational algebra is simply that it is the inverse of the cartesian product. For example, if you have two relations R and S, then, if U is a relation defined as the cartesian product of them:

U = R x S

the division is the operator such that:

U ÷ R = S

and:

U ÷ S = R

So, you can think of the result of U ÷ R as: “the projection of U that, multiplied by R, produces U”, and of the operation ÷, as the operation that finds all the “parts” of U that are combined with all the tuples of R.

However, in order to be useful, we want that this operation can be applied to any couple of relations, that is, we want to divide a relation which is not the result of a cartesian product. For this, the formal definition is more complex.

So, supposing that we have two relations R and S with attributes respectively A and B, their division can be defined as:

R ÷ S = π_A-B(R) - π_A-B((π_A-B(R) x S) - R)

that can be read in this way:

1. π_A-B(R) x S: project R over the attributes of R which are not in S, and multiply (cartesian product) this relation with S. This produces a relation with the attributes A of R and with rows all the possible combinations of rows of S and the projection of R;

2. From the previous result subtract all the tuples originally in R, that is, perform (π_A-B(R) x S) - R. In this way we obtain the “extra” tuples, that is the tuples in the cartesian product that were not present in the original relation.

3. Finally, subtract from the original relation those extra tuples (but, again, perform this operation only on the attributes of R which are not present in S). So, the final operation is: π_A-B(R) - π_A-B(the result of step 2).

So, coming to your example, the projection of r on D is equal to:

(D)
d1
d2
d3 
d4

and the cartesian product with s is:

(A,  B,  D)
 a1  b1  d1
 a1  b1  d2
 a1  b1  d3
 a1  b1  d4

Now we can remove from this set the tuples that were also in the original relation r, i.e. the first two tuples and the last one, so that we obtain the following result:

(A,  B,  D)
 a1  b1  d3

And finally, we can remove the previous tuples (projected on D), from the original relation (again projected on D), that is, we remove:

(D)
d3

from:

(D)
d1
d2
d3
d4

and we obtain the following result, which is the final result of the division:

(D)
d1
d2
d4

Finally, we could double check the result by multiplying it with the original relation s (which is composed only by the tuple (a1, b1)):

(A  B  D)
 a1 b1 d1
 a1 b1 d2
 a1 b1 d4

And looking at the rows of the original relation r, you can see this fact, that should give you an important insight on the meaning of the division operator:

the only values of the column D in r that are present together with (a1, b1) (the only tuple of s), are d1, d2 and d4.

You can also see another example in Wikipedia, and for a detailed explanation of the division, together with its transformation is SQL, you could look at these slides.