Most of practical database systems are relational databases. To understand SML# database integration, this section review the basics notions of relational databases and SQL.

In the relational model, data are represented by a set of relations. A relation is a set of tuples, each of which represents association of attribute values such as name, age, and salary. Such a relation is displayed as a table of the following form.

A relational database is system to manipulate a collection of such tables. A relation $R$ on the sets $A{}_1,A{}_2,\mathrm{\cdots },A{}_n$ of attribute values is mathematically a subset of the Cartesian product $A{}_1\times A{}_2\mathrm{\cdots }\times A{}_n$. Each element $t$ in $R$ is an $n$ element tuple $(a{}_1,\mathrm{\dots },a{}_n)$. In an actual database system, each component of a tuple has attribute name, and a tuple is represented as a labeled record. For example, the first line of the example table above is regarded as a record {name="Joe", age=21, salary=1000}. On these relations, a family of operations are defined, including union, projection, selection, and Cartesian product. A set of tables associated with a set of these operations is called the relational algebra. One important thing to note on this model is that, as its name indicates, the relational model is an algebra and that it is manipulated by an algebraic language. An algebraic language is a functional language that does not have function expression.

In relational databases, the relational algebra is represented by the language called SQL, which is language of set-value expressions. The central construct of SQL is the following SELECT expression.

SELECT $t{}^{\mathrm{1}}\mathrm{.}l{}_{\mathrm{1}}$ as $l{}_{\mathrm{1}}{}^{\mathrm{\prime }}$,$\mathrm{\dots }$, $t{}^m\mathrm{.}l{}_m$ as $l{}_m{}^{\mathrm{\prime }}$
FROM $R{}_{\mathrm{1}}$ as $t{}_{\mathrm{1}}$, $\mathrm{\dots }$, $R{}_n$ as $t{}_n$
WHERE $P\mathrm{(}t{}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}t{}_n\mathrm{)}$

Here we used the following meta variables.

• •

  $R$: relation variables

• •

  $t$: tuple variables

• •

  $l$: labels, or attribute names

• •

  $t.l$: the $l$ attribute of tuple $l$

The operational meaning of a SELECT expression can be understood as follows.

1. 1.

   Evaluate each $R{}_i$ in FROM clause, and generate their Cartesian product $R{}_1\times \mathrm{\cdots }\times R{}_n$

2. 2.

   Let $(t{}_1,\mathrm{\dots },t{}_n)$ be any representative tuple in the product.

3. 3.

   Select the tuples that satisfies the predicate $P(t{}_1,\mathrm{\dots },t{}_n)$ specified in WHERE clause from the product.

4. 4.

   For each element $(t{}_1,\mathrm{\dots },t{}_n)$ in the select set, construct a record {$l{}_{\mathrm{1}}{}^{\mathrm{\prime }}$=$t{}^{\mathrm{1}}\mathrm{.}l{}_{\mathrm{1}}$, $\mathrm{\dots }$, $l{}_m{}^{\mathrm{\prime }}$=$t{}^m\mathrm{.}l{}_m$}.

5. 5.

   Collect all these records.

For example, let the above example table be named as Persons and consider the following SQL.

SELECT P.name as name, P.age as age
FROM Persons as P
WHERE P.salary > 10000

This expression is evaluated as follows.

• •

  The Cartesian product of the soul relation Persons is Persons itself.

• •

  Let P be any tuple in Persons.

• •

  Select from Person all the tuples P such that P.Salary > 10000. We obtain the following set.

  name	age	salary
  ”Sue”	31	20000
  ”Bob”	41	20000

• •

  For each tuple P in this set, compute the new tuple {name=P.name, age=P.age} to obtain the following set.

  name	age
  ”Sue”	31
  ”Bob”	41

  The is the result of the expression.

  This result represent the set (list) of records: {{name="Sue", age=31}, {name="Bob", age=31}}.