Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
So, I've been conferred upon the opinion that:
Union, difference, cross product, selection, projection form the "complete set of relational operations". That is, any other relational operation can be expressed as a combination of these (excluding domain manipulation operations like aggregate functions I assume).
Question 1: Is that true ?
Question 2: If yes, can someone help me break down division in terms of those operations.
Let $R(A,B)$ and $S(B)$ be two relations. Division should find all values of A in R that are connected with all values of B (in S). Think $AB\div B=A$.
Question 1: Yes. $R\div S=\pi_A(R)-\pi_A(\pi_A(R)\times S-R)$
Question 2:
$\pi_A(R)\times S$ : this contains all possible AB pairs.
$R$ : this contains the actual AB pairs.
For the values of A that are connected to all values of B, after we do the difference, those will be gone. In the difference $\pi_A(R)\times S-R$ there are only values of A that are NOT connected to all B.
The rest is obvious.
Q 1: Is that True?
No. It is the conventional minimal set, based on Codd's 1970 paper "Relational Completeness of Data Base Sublanguages". But Codd was wrong. He left out RENAME. Even to define Natural Join in terms of cross product needs RENAME. (Compare that Boolean Algebra's minimal set is usually taken as Union, Difference, Intersection. To achieve Intersection in RA, you can take it as a special case of Natural Join.)
Why did Codd miss out RENAME? Because his claim for completeness was based on the Relational Calculus/language ALPHA; and that had a special way to deal with attribute naming. (Very similar to the SQL dot-prefix <table>.<column> format.) The RA doesn't have that formalism (and no way to translate that from RC to RA). Furthermore that formalism is not extensible to nested operators ((A UNION B) MINUS C) TIMES D. (How do you refer to an attribute in the result from the left operand of TIMES, noting that A, B, C must have the same attributes?)
Note there's nothing 'sacred' about any particular minimal set of operators. You could define EXTEND in terms of RENAME. Or you could define RENAME in terms of EXTEND (and projection).
Another possible minimal set is: Selection, Projection, Rename, Natural Join, Union, Difference.
Q 2: Division
Curiously, Codd's very early writings did include Division as a primitive. He later realised it could be defined in terms of the others. @dimm's answer is good -- providing S's attributes are a subset or R's -- which is the usual presumption. But beware: there's lots of different operators called "Relational Division": Codd's Divide, Todd's Divide, the Great Divide, the Small Divide, ... [See Chris Date's Chapter 12 in 'Database Explorations'] They differ in how they handle corner cases like one of the relations being empty, or having no attributes in common, or having all attributes in common.
Before you try to use a Divide, I'd stop and carefully express what condition you're trying to apply in your query. Perhaps you don't need a Divide at all. Perhaps expressing your query using projection, difference, cross product will actually be easier to understand.
(I think Relational Division is one of those topics that instructors use to torture their students for sheer pedantry/no learning gain.)
I derived this solution using one particular example only, so it might not be full proof. Let R(A,B) and S(A), we want to do R÷S.
