Relational Algebra

RelationalWeenies jabber about this all the time. What is it, exactly?

See SetTheory. RelationalAlgebra is to SetTheory as algebra is to NumberTheory.

You mean as number theory is to algebra, or as algebra is to arithmetic, right? Number theory is just about impossible without algebra, and the deeper you go the more you need.
That's not an introduction or explanation, that's an analogy. Can you point at a serious reference?

SetTheory is as serious a reference as I know of on this wiki (but see and is the natural starting point for an enquiry of this nature, since RelationalAlgebra is as meaningless without a basic understanding of SetTheory as algebra is without a basic understanding of NumberTheory. It also contains some examples of modified RelationalAlgebra.

I guess I'm looking for something that comes from it that's (a) useful and (b) non-obvious. I've never seen any examples of that so I'm left wondering why the huge fuss is made of it. Coming from a formal mathematics background it seems a bit light-weight to me.

That it is no less light-weight than the RelationalCalculus is proven by the correctness of CoddsReductionAlgorithm?. Whether the algorithm is correct and the two are isomorphic, I couldn't say, but it has always been my working hypothesis. Whether anything useful and non-obvious has ever come from the Relational Calculus (or SetTheory... or CategoryTheory...) is another imponderable.

Set theory has given non-obvious results - whether useful or not depends on what you are trying to do. Category theory is more like a refactoring of mathematics, a way to discuss different things in the same terms.

Relational Algebra has given useful results* - whether non-obvious or not depends on who you are and when. Category theory is more like a refactoring of set theory than of mathematics, since, by GoedelsTheorem, mathematics cannot be wholly refactored except into a system that allows contradictory propositions.

* RelationalDataBaseManagementSystems and StructuredQueryLanguage
DateAndDarwen, in their book Foundation for Future Database Systems: TheThirdManifesto, describe a drastically simplified relational algebra which is very useful for reasoning about relational operations. They call their algebra 'A', short for 'ALGEBRA', which in turn stands for A Logical Genesis Explains Basic Relational Algebra. Cute. Now there's a back-asswards BackroNym if I've ever heard one. Almost as bad as what the D in TutorialDee stands for. :)

The algebra emphasizes relational theory's roots in predicate logic rather than set theory. (Many practitioners tend to reason about relational operations in terms of sets, which can lead to confusion. But not as much confusion as SQL causes, since SQL's tolerance for duplicate rows implies that it works with bags rather than sets.) SmalltalkCulturalAssumption? here?

Some notation conventions used below: Primitive operators: Note that some expressions can not be practically computed; the relational algebra is thus more expressive than a query language based on it can be. In particular, (NOT a) cannot, in general, be computed in isolation. Likewise, (a OR b) cannot usually be computed unless (H(a) = H(b)).

Additional operators: Here are some useful transformations involving the primitive operators. Analogies to Boolean algebra are obvious in some places: Many of their operations are not very user-friendly in my opinion. Sure, one can get used to them over time, but I think a more "natural" set would be appropriate. For example, we use AND, OR, and NOT as our "primary" Boolean operators because they reflect spoken language, but in theory we only need NAND. -- top

The primitive set of operations given above is, of course, not the only possible set to start from. However, I find AND, OR, NOT, and REMOVE all very easy to understand, and easily related to SQL. I'm curious which you find to be "unfriendly" -- the analogies to spoken language hold here as well as they do in Boolean algebra, up to a point. REMOVE (projection) doesn't map quite so easily, but it's essential to relational algebra in some form.

The result of NAND on two finite relations would, in general, not be practically computable, so I don't think it would be a very useful choice -- despite the similarities, this isn't quite the same as Boolean algebra. (Although in fairness, computing OR is similarly impractical in the general case.) -- DanMuller


Of? The non-computability of NAND? Note that NAND is equivalent to NOT AND. Note that the complement (NOT) of a relation a is a relation with all possible tuples not in a. If the types of the attributes of a relation all have finite bounds, the result of NOT a will be finite (but possibly very large). If any of the types are infinite (for instance a string without a length constraint), then the result will have infinitely many tuples.

The above discussion seems to involve some issues that were dealt with in the early 20th century in the context of the RussellParadox, and which resulted in the slogan "there is no universe (of discourse)". One stays out of trouble if and only if one insists that NOT {set A} is defined only for the case where A is a subset of B, in which case NOT A is defined to be B minus A.

Unconstrained approaches were demonstrated to allow the RussellParadox. -- DougMerritt

[...aha, I should have realized there are related pages here: SetOfAllSets UniversalSet NewFoundations]

Note that the "base" operations and the operations actually used in a language do not necessarily have to be the same, as long as the derived operations can be defined in terms of the base operations. Thus, perhaps a more "user friendly" set of operations can be derived. Also, a set of hierarchical traversal operations would be nice, but were not in the original set. The result is still a result set (table). An analogy would be AND and OR from BooleanLogic. In theory we only need NAND (NOT AND), but create the others from combinations of NAND to fit spoken language in order to make it easier for humans to relate to. I have been working on a set of "human friendly" relational operators, but am not satisfied with it enough to "publish" it yet. -- top

Contributors: DanMuller
See also: relationalCalculus CriteriaForGoodMathOrCompactNotation, RelationalLanguage, QueryTraversalVersusRecursion

View edit of February 16, 2009 or FindPage with title or text search