Relational Model vs. Logic Programs

A relational database can be represented as a logic program which consists of bare facts (see Chapters 4 and 6). The relational model and the logic program (expressed by Datalog or Prolog), are isomorphic unless the names of the columns in the tables are considered [17].

From the mathematical point of view, there is no difference between these two representations. When the mathematical basis of the relational model is extended with attributes, then a difference appears. In the extended relational model a value is referred by the attribute name, or its position in the relation schema^9.1. For the logic program, a predicate has no attribute. The only way a value may be referred to, is its position (see Section 4).

The basic operations of relational algebra which are: union, set difference, Cartesian product, projection, and selection (see Section 3.2), may be expressed with logic programs. So Logic programs have at least the computational power of relational algebra [17].

The Union of relations $R$ and $S$ which is denoted as: $R \cup S$ (see Section 3.2, Definition 3.2) can be expressed by two rules (regarding rules see Chapter 4), assuming that predicates $r/n$ and $s/n$ denote relations $R$ and $S$ respectively:

$$\begin{array}{l} rs(X_1,\ldots, X_n) \leftarrow r(X_1,\ldots... ... rs(X_1,\ldots, X_n) \leftarrow s(X_1,\ldots, X_n). \end{array}$$ (9.1)

A relation, which is represented by the predicate $rs/n$ holds the resulting union. A right-to-left implication is used, instead of left-to-right as it is given in Chapter 4, to indicate a relationship between logic and Prolog language.

The difference of two relations $R$ and $S$ which is denoted as: $R - S$ (see Section 3.2, Definition 3.3) is expressed using a negation ($not$) (for the meaning of $not$ in Prolog refer to Section 6.1). Assuming that $rs/n$ is a predicate representing the resulting relation, and $r/n$, $s/n$ are predicates representing relations: $R$ and $S$ respectively, the difference can be expressed as follows:

$$rs(X_1,\ldots, X_n) \leftarrow r(X_1,\ldots, X_n), not\; s(X_1,\ldots, X_n).$$ (9.2)

The Cartesian product of two relations $R$ and $S$, denoted as $R \times S$ (see Section 3.2, Definition 3.4) is represented by the following rule:

$$rs(X_1,\ldots,X_n,Y_1,\ldots,Y_m) \leftarrow r(X_1,\ldots,X_n), s(Y_1,\ldots,Y_m).$$ (9.3)

The projection and selection can be expressed as well. Assuming that there is a relation schema $R(T)$, and $T$ is an ordered set of attributes: $T=\langle X_1,\ldots,X_n \rangle$. The projection is denoted as:

$$S = \pi_{i_1,i_2,\ldots,i_m}(R)$$

where $S$ is of schema: $S(U)$, where $U$ is an ordered set of attributes, that $U=\langle i_1,\ldots,i_m \rangle$ and each of $i_p$, $p \in 1 \ldots m$, is in $T$ (see Section 3.2, Definition 3.5). For example, assuming that there is a relation schema $Parent(child\_name, parent\_name)$, the projection:

$$S = \pi_{parent\_name}(Parent)$$

can be expressed by:

$$s(Y) \leftarrow parent(X,Y).$$ (9.4)

The selection is denoted as:

$$S = \sigma_F(R)$$

where $F$ is a logic formula (see Section 3.2, Definition 3.6). The selection may be obtained using the formula as a part of the rule. For example, having a relation schema $Income(name, amount)$, the selection of all people who earn more than $1,000,000:

$$Millionaire = \sigma_{amount > 1000000}(Income)$$

can be written as:

$$millionaire(X,Y) \leftarrow income(X,Y), Y > 1000000.$$ (9.5)

All other relational algebra operations can be expressed with these basic ones, so logical programs can be used to express any relational algebra operation.

There is another issue which has to be pointed out. The domains for relations are explicitly stated in the relational model. If the elements are not enumerated, at least their types are stated as integers, characters etc. Prolog does not have such a typing system. Originally, it does not provide any restrictions to what a term is^9.2. While the terms are being instantiated, certain values become valid for them. So there is a single domain of terms.