Relational basics

This page describes the necessary background on relational theory to understand Alf. Note that it only covers the concepts needed to understand the relational algebra; that is, nothing is said about database schemas, normal forms, transactions, ACID properties, and so on. Refer to standard database literature for those.

The background given below is a rephrasing of what can be found in The Third Manifesto (TTM), by Hugh Darwen and C.J. Date. See www.thethirdmanifesto.com or the TTM book.

A theory of types

To understand what relational algebra is about, we need to briefly review a few concepts about types. Forget about object-oriented programming for a moment (if you are a developer) and examine the following definitions:

A type is a (finite) set of values. A subtype is a subset. Sets are not ordered and have no duplicates.
A value is an element of a type. We say that the value belongs to the type.
A value is immutable, intrinsically typed, has no localization in time and space, and can be of arbitrary complexity.
A type is always accompanied with an equality operator, say ==, that allows checking if two of its elements actually denote the same value. The notion of 'duplicate' precisely relies on this operator in an obvious way.

Oh! and,

NULL is not a value. Precisely, ''treating NULL as a value'' on one side and ''keeping a theory simple enough to be of any practical yet sound use'' on the other side are conflictual requirements. Therefore, here, NULL is not a value.

A few examples

The simplest scalar types are well known:

(the set of) Boolean(s), Integer(s), Decimal(s), String(s), ...

There are others, of course:

(the set of) Color(s), Size(s), Weight(s), Range(s), Coordinate(s), ...

And even a few that people don't always expect to be types:

(the set of) List(s), Set(s), Tree(s), Graph(s), ...

Roughly, surrounding a set of immutable elements for which an equality operator makes sense is defining a type. Implementing it is another story, of course.

Tuples and Relations

Tuples and relations are values as well. In contrast to integers or strings however, tuples and relations are not scalar; they have an internal ''structure''. Apart from that, they are values and they have a type. Let's have a closer look at that.

Tuple

A tuple is a set of attribute (name, value) pairs. It is such that no two pairs have the same name.
A tuple being a set, it is not particularly ordered.
A tuple being a value, it is immutable.

We will denote tuple literals as follows (we assume that a Color type exists):

# The product whose id is 'P1',
#  * is named 'Nut', 
#  * has a color denoted by 'red', and 
#  * is known to be heavy.
Tuple(pid: 'P1', name: 'Nut', color: Color('red'), heavy: true)

The type of a tuple is simply defined in terms of its heading. A heading is defined as a set of attribute (name, type name) pairs. For example, the heading of the tuple show above is:

Heading(pid: String, name: String, color: Color, heavy: Boolean)

Relation

A relation is a set of tuples of same heading
A relation being a set, it is not particularly ordered and does not have duplicates.
A relation being a value, it is immutable.

We will denote relation literals as follows:

Relation([
  Tuple(pid: 'P1', name: 'Nut',   color: Color('red'),   heavy: true),
  Tuple(pid: 'P2', name: 'Bolt',  color: Color('green'), heavy: false),
  Tuple(pid: 'P3', name: 'Screw', color: Color('blue'),  heavy: false)
])

The type of a relation is simply defined in terms of its heading. For example, the heading of the relation show above is:

Heading(pid: String, name: String, color: Color, heavy: Boolean)

A few consequences

The following list of bullets are logical consequences of the definitions above. Alf considers them as part of its specification; if you see Alf behaving differently from what is being said here, then it's a bug or a limitation of the current version... for which patches are welcome!

Tuples and relations may contain values of any complexity, provided that the corresponding type is consistent with the theory of types stated above.
In particular, tuples and relations may contain... tuples and relations.

The following points are other logical consequences of the definitions above. Alf considers them as pre-conditions of all relational operators, without necessarily enforcing them:

All tuples that are member of a relation must have the same "structure", precisely, the same heading than the relation itself
Tuples and relations never contain NULL
No left-right ordering of attributes applies to tuples and relations
No tuple ordering applies to relations

That said, Alf does however provide a few facilities that make it more comfortable for the user to deal with any deviations from the theory stated here, as they might occur in any SQL product(s) you might be using as a data source.

Relational algebra

Relational algebra is to relations what elementary algebra is to numbers and quantities in formulae and equations. Consider the following elementary formula:

z = 2 * (x + y)

Evaluating this formula with x = 5 and y = 3 yields a value for z:

16 = 2 * (5 + 3)

Thanks to known properties of the operators, like associativity or commutativity, formulae can be manipulated. For example, the formula above can be rewritten into the following equivalent form:

z = (2 * x) +  (2 * y)

Relational algebra is similar, but applies to relations. For example:

#  Who are supppliers located in London or in Paris?
union(
  restrict(suppliers, city: 'Paris'),
  restrict(suppliers, city: 'London'))

Try it!

Can be rephrased/rewritten as

restrict(suppliers, eq(:city, 'Paris') | eq(:city, 'London'))

Try it!

This is kind or rewriting is of particular importance for query optimization, but that's far beyond the basics!