Relational Calculus

The RelationalCalculus is descriptive/non-procedural, specifying relations via logical predicates, e.g. forall X, Y such that EQUAL(X.name, Y.name) there-exists Y.salary.

Contrast with the RelationalAlgebra, which is prescriptive/constructive, specifying a (very high level) procedure for solving a problem/finding values, e.g. restrict X,Y via EQUAL(X.name, Y.name) projecting Y.salary.

The RelationalCalculus and RelationalAlgebra are not only conceptually similar, they are logically equivalent: any statement in the RelationalCalculus can be converted to a (composite) operation in the RelationalAlgebra, and vice-versa, as proven originally by DrCodd (in part via CoddsReductionAlgorithm?) with a bit of touch up a little later.

SqlLanguage contains features from both the RelationalCalculus and the RelationalAlgebra, as well as features that derive from neither (in some cases for good reasons, in other cases not); this is true for most real world relational query languages.

The original RelationalCalculus described by Codd featured range variables whose values are tuples, and is therefore also known as the TupleCalculus?. A later version featured range variables whose values are domains (briefly: defined by ChrisDate to be DateTypes? such as integers and strings, see section 5.2, Top ;-) and is therefore known as the DomainCalculus?.

The above is loosely paraphrased from ChrisDate's AnIntroductionToDatabaseSystems, 7th edition, in particular from the first two pages of chapter 7.

The RelationalAlgebra (and SqlLanguage) are often called descriptive languages, even though it is actually procedural; this is defensible for two reasons:

• it is procedural at a very high level; no mucking about with low level data structures and traversal algorithms is necessary. This makes it very "descriptive" relative to doing the same thing in a lower-level procedural language such as, oh, CeeLanguage.
• it is convertible into the descriptive RelationalCalculus, so in some sense it is equivalent to a descriptive language.

This is rather interesting since it tends not to be true in other areas of math and CS. The problem of determining whether an arbitrary predicate is satisifiable is intractable; it can't generally be converted into an effective algorithm for finding a solution.

For example, it's easy to test whether A is a divisor of X, given both values, so IS_DIVISOR_OF(X, A) is a predicate that is very fast to test. But there is no known way to quickly find an A that satisfies the predicate for a given X (i.e. find an A that is a factor of X), and it was only recently proven that one can determine the mere existence/non-existence of such an A (i.e. find whether X is prime or composite) in deterministic polynomial time (and without taking as a hypothesis the unproven RiemannHypothesis? nor its extensions).

(The satisfiability problem has been proven to be NP-complete, unlike the problem of factoring integers, whose status is unproven, so this is intended as an accessible example rather than a perfect example.)