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?

Aubry

I’m voting to close this question because this is about fundamental theoretical concepts, not about programming. As such, this might be a better fit for our sibling site Computer Science – Luftwaffe

This question is on-topic, because it is directly relevant to writing programs. (So you can see people disagree re topicality) Please use text, not images/links, for text--including tables & ERDs. Paraphrase or quote from other text. Give just what you need & relate it to your problem. Use images only for what cannot be expressed as text or to augment text. Include a legend/key & explanation with an image. PS Relations are not arrays. "leads me to think" & "I'm not sure enough" are not very helpful Why? Where are you 1st stuck or unsure? – Lacy

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.

Burlburlap

Thank you for that very clear and pedagogical answer on a challenging topic! I thonk I'm close to understand the division. Yet, why (π_A-B(R) x S) - R = (π_A-B(R) x S) - (π_A-B,A(R)) if I take the formula given during my lecture? And why does the only values of D that are paired with r, that is the tuple (a1, b1), are d1 and d2. ? What does pairing means from the first array? – Aubry

Actually the formulas are identical: if you see, in your formula the only difference is in the last term, which is R in my formula, and πR-S,S(R) in your formula, that means: project over the attributes (R-S) U (S), which simply means: project over the attributes R, that is all the attributes of the relation R (I named differently the attributes from the relation name, while in your formula they have the same name). (Continue) – Burlburlap

For the second question, I have seen now that I made a mistake, since in the original relation there is also the tuple a1, b1, d4, that I did not considered. I correct my answer. – Burlburlap

So, I have corrected the answer. There were three tuples in r with a1, b1, so the result is the set of three values d1, d2, and d4, that is all the values in D that are together to (a1, b1) in r. – Burlburlap