The $\theta$-Join as a Join with $\theta$

Abstract

We present an algebra for the classical database operators. Contrary to most approaches we use (inner) join and projection as the basic operators. Theta joins result by representing theta as a database table itself and defining theta-join as a join with that table. The same technique works for selection. With this, (point-free) proofs of the standard optimisation laws become very simple and uniform. The approach also applies to proving join/projection laws for preference queries. Extending the earlier approach of [16], we replace disjointness assumptions on the table types by suitable consistency conditions. Selected results have been machine-verified using the tool.

14 Appendix

For types $T_P, T_Q$ we use the notion of a direct product of $D_P$ and $D_Q$ (e.g. [17]). This is a pair $(\rho _P, \rho _Q)$ of relations with $\rho _P \subseteq (D_P \times D_Q) \times D_P$ and $\rho _Q \subseteq (D_P \times D_Q) \times D_Q$ such that

Using this concept the parallel product can be represented as

(5)

The following properties of direct products are used in the main proof³:

(6)

(7)

Proof of  Lemma 12.5. The proof consists in showing (see Lemma 10.3.3). We do this by showing the stronger property , from which the original claim follows by and isotony of $\mathbin {;}$.

Since “joinable” is defined with $\mathbin {\#}$ and the formula to prove uses , we have to make a connection between the two:

(8)

This is analogous to the conversion of a relation to a vector explained in [17], which would give . The inverse transformation is . Both equations are easily verified. Using restriction (Lemma 2.1.7) and Boolean algebra, the second one can be simplified to . Then by Definition 12.4 and the definition of diamond (Definition 6.1) P is joinable with Q iff

(9)

Now we calculate as follows.