Querying now-relative data

Abstract

Now-relative temporal data play an important role in most temporal applications, and their management has been proved to impact in a crucial way the efficiency of temporal databases. Though several temporal relational approaches have been developed to deal with now-relative data, none of them has provided a whole temporal algebra to query them. In this paper we overcome such a limitation, by proposing a general algebra which is parametrically adapted to cope with the relational approaches to now-relative data in the literature, i.e., MIN, MAX, NULL and POINT approaches. Besides being general enough to provide a query language for several approaches in the literature, our algebra has been designed in such a way to satisfy several theoretical and practical desiderata: closure with respect to representation languages, correctness with respect to the “consensus” BCDM semantics, reducibility to the standard non-temporal algebra (which involves interoperability with non-temporal relational databases), implementability and efficiency. Indeed, the experimental evaluation we have drawn on our implementation has shown that only a slight overhead is added by our treatment of now-relative data (with respect to an approach in which such data are not present).

Appendix

Property 2

(Correctness of the MIN, MAX, NULL and POINT algebrae) The MIN, MAX, NULL and POINT algebrae are correct, since they provide (in the MIN, MAX, NULL and POINT representations) all and only the results that would be obtained by the underlying BCDM semantic approach.

Proof

The correctness of the MIN, MAX, NULL and POINT algebrae is proved by showing that, given the relations r ^N and s ^N and any binary operator Op ^N in the MIN, MAX, NULL or POINT approaches (the proof is analogous when considering unary operators), the application of the operator in MIN, MAX, NULL or POINT algebrae gives a result equivalent to the application of the corresponding operator in the BCDM algebra (indicated by Op ^B):

$$ to\_BCDM^{c_{\rm NOW}}\left(r^N Op^N s^N\right) = to\_BCDM^{c_{\rm NOW}}\left(r^N\right) Op^B to\_BCDM^{c_{\rm NOW}}\left(s^N\right) $$

We prove the result for the operation of Cartesian product by proving the two inclusions, that is we prove that:

$$ to\_BCDM^{c_{\rm NOW}}\left(r^N \times^N s^N\right) \subseteq to\_BCDM^{c_{\rm NOW}}\left(r^N\right) \times^B to\_BCDM^{c_{\rm NOW}}\left(s^N\right) $$

and

$$ to\_BCDM^{c_{\rm NOW}}\left(r^N \times^N s^N\right) \supseteq to\_BCDM^{c_{\rm NOW}}\left(r^N\right) \times^B to\_BCDM^{c_{\rm NOW}}\left(s^N\right) $$

Let x be a BCDM tuple in $to\_BCDM^{c_{\rm NOW}}(r^N \times^N s^N)$ and let R = (A ₁, ..., A _a , B ₁, ..., B _b |T) be the schema of $to\_BCDM^{c_{\rm NOW}}(r^N \times^N s^N)$. We denote as A the attributes A ₁, ..., A _a and as B the attributes B ₁, ..., B _b . Then, by the definition of the $to\_BCDM^{c_{\rm NOW}}$ function, there exists a maximal set of (possibly now-relative) tuples {y ₀, y ₁, ..., y _k } in r ^N ×^N s ^N (k ≥ 0) such that x[AB] = y ₀[AB] = ... = y _k [AB] and that, considering the rectangles resulting from the extension of their timestamps (with now = c _NOW), their union corresponds to x[T], i.e., $x[T] = EXT^{c_{\rm NOW}}(y_0[T]) \cup \ldots \cup EXT^{c_{\rm NOW}}(y_k[T])$. If such tuples {y ₀, y ₁, ..., y _k } belongs to r ^N ×s ^N, by the definition of ×^N, for each y _i  ∈ {y ₀, y ₁, ..., y _k } there must be a tuple ${w}_{i'}' \in r^N$ and a tuple ${w}_{i''}'' \in s^N$ such that x[A] = y _i [A] = w _i′′[A], x[B] = y _i [B] = w _i′′′′[B] and the bitemporal chronons of y _i correspond to the intersection of the bitemporal chronons of w _i′′ and w _i′′′′, i.e.:

$$ EXT^{c_{\rm NOW}}\left(y_i[T]\right) = EXT^{c_{\rm NOW}}\left(w'_{i'}[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_{i''}[T]\right) $$

In the following, let {w ₁′, ..., w _l ′} and {w ₁′′, ..., w _m ′′} the sets of all and only the tuples in r ^N and in s ^N respectively that generate the above tuples {y ₀, y ₁, ..., y _k }.

Let us consider the tuples w ₁′, ..., w _l ′ in r ^N. Applying the to_BCDM function, since these tuples have the same values for the explicit attributes, by definition of to_BCDM, to_BCDM returns one BCDM tuple y ∈ to_BCDM(r ^N) such that:

$$y[A] = \emph{w}_1'[A] = \ldots = \emph{w}_l'[A] $$

and

$$ y[T] = EXT\left(\emph{w}_1'[T]\right) \cup \ldots \cup EXT\left(\emph{w}_l'[T]\right) $$

If we consider the tuples $\emph{w}_1'', \ldots, \emph{w}_m''$ in s ^N, the function to_BCDM returns one BCDM tuple z ∈ to_BCDM(s ^N) such that:

$$ z[A] = \emph{w}_1''[A] = \ldots = \emph{w}_m''[A] $$

and

$$ z[T]=EXT\left(\emph{w}_1''[T]\right) \cup \ldots \cup EXT\left(\emph{w}_m''[T]\right) $$

Applying the ×^B operator to y and z, by definition of the operator, we obtain a relation on schema R(AB |T) containing a tuple $x' \in to\_BCDM^{c_{\rm NOW}}(r^N) \times^B to\_BCDM^{c_{\rm NOW}}(s^N)$ such that x′[A] = y[A] = x[A] and x′[B] = z[B] = x[B] and:

$$ \begin{aligned} \mbox{x'[T] }={} & y[T] \cap z[T] = \left(EXT^{c_{\rm NOW}}\left(\emph{w}_1'[T]\right) \cup \ldots \cup EXT^{c_{\rm NOW}}\left(\emph{w}_l'[T]\right)\right) \cap \\ & \left(EXT^{c_{\rm NOW}}\left(\emph{w}_1''[T]\right) \cup \ldots \cup EXT^{c_{\rm NOW}}\left(\emph{w}_m''[T]\right)\right) \end{aligned} $$

For the distributive property of intersection over union:

$$ \begin{aligned} \mbox{x'}[\mathrm{T}]={} & \left(EXT^{c_{\rm NOW}}\left(\emph{w}'_1[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_1[T]\right)\right) \cup \ldots \cup \\ & \left(EXT^{c_{\rm NOW}}\left(\emph{w}'_1[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_m[T]\right)\right) \cup \ldots \cup \\ & \left(EXT^{c_{\rm NOW}}\left(\emph{w}'_l[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_1[T]\right)\right) \cup \\ & \ldots \cup \left(EXT^{c_{\rm NOW}}\left(\emph{w}'_l[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_m[T]\right)\right) \end{aligned} $$

Since by construction {w ₁′, ..., w _l ′} and {w ₁′′, ..., w _m ′′} are all and only the tuples that generates {y ₀, y ₁, ..., y _k }, i.e., such that for each i, 0 ≤ i ≤ k, x[A] = y _i [A] = w _i′′[A], x[B] = y _i [B] = w _i′′′′[B] and $EXT^{c_{\rm NOW}}({w}'_{i'}) \cap EXT^{c_{\rm NOW}}({w}''_{i''}) = EXT^{c_{\rm NOW}}(y_i[T])$, we have that, $x'[T] = EXT^{c_{\rm NOW}}(y_1[T]) \cup \ldots \cup EXT^{c_{\rm NOW}}(y_k[T]) = x[T]$. Therefore, x = x′.

Now we prove the other direction of the inclusion.

Let x′ be a BCDM tuple in $to\_BCDM^{c_{\rm NOW}}(r^N) \times^B to\_BCDM^{c_{\rm NOW}}(s^N)$. By definition of the ×^B operator, there exist a tuple $y \in to\_BCDM^{c_{\rm NOW}}(r^N)$ and a tuple $z \in to\_BCDM^{c_{\rm NOW}}(s^N)$ such that x′[A] = y[A], x′[B] = z[B] and x′[T] = y[T] ∩ z[T] ≠ ∅.

By definition of to_BCDM function, if $y \in to\_BCDM^{c_{\rm NOW}}(r^N)$ then there exists a (maximal) set of (possibly now-relative) tuples {w′₀, ..., w′ _l } that are in r ^N such that y[A] = w′₀[A] = ... = w′ _l [A] and $y[T] = EXT^{c_{\rm NOW}}({w}'_0[T]) \cup \ldots \cup EXT^{c_{\rm NOW}}({w}'_l[T])$.

The same holds for z: there exists a (maximal) set of (possibly now-relative) tuples {w′′₀, ..., w′′ _m } that are in s ^N such that z[A] = w′′₀[A] = ... = w′′ _m [A] and $z[T]=EXT^{c_{\rm NOW}}({w}''_0[T]) \cup \ldots \cup EXT^{c_{\rm NOW}}({w}''_m[T])$.

If we apply the ×^N operator to r ^N and s ^N, because $\{{w}'_0, \ldots, {w}'_l\} \subseteq r^N$ and $\{{w}''_0, \ldots, {w}''_m\} \subseteq s^N$, we obtain, among the other tuples, a set of (possibly now-relative) tuples {y ₁, ..., y _k } such that y _i [A] = w′ _i′[A], y _i [B] = w′′ _i′′[B] and:

$$ EXT^{c_{\rm NOW}}\left(y_i[T]\right) = EXT^{c_{\rm NOW}}\left({w}'_{i'}[T]\right) \cap EXT^{c_{\rm NOW}}\left({w}''_{i''}[T]\right) $$

Because w′ _i′[A] = y[A] and w′′ _i′′[B] = z[B], the to_BCDM function coalesces these tuples in one BCDM tuple x such that:

$$ x[A] = y_0[A] = \ldots = y_k[A] = y[A], x[B] = y_0[B] = \ldots = y_k[B] = z[B] $$

and $x[T]~=~EXT^{c_{\rm NOW}}(y_0[T])~ \cup~\ldots~\cup~EXT^{c_{\rm NOW}}(y_k[T])$.

Since for each i, 0 ≤ i ≤ k:

$$ \begin{aligned} EXT^{c_{\rm NOW}}\left(y_i[T]\right) ={} & EXT^{c_{\rm NOW}}\left(\emph{w}'_{i'}[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_{i''}[T]\right),\\ x[T] ={}& EXT^{c_{\rm NOW}}\left(y_0[T]\right) \cup \ldots \cup EXT^{c_{\rm NOW}}\left(y_k[T]\right) \\ ={}& \left(EXT^{c_{\rm NOW}} \left(\emph{w}'_{i_0'}[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_{i_0''}[T]\right)\right)\\ & \cup \ldots \cup \left(EXT^{c_{\rm NOW}}\left(\emph{w}'_{i_k'}[T]\right) \cap EXT^{c_{\rm NOW}}\left(\emph{w}''_{i_k''}[T]\right)\right) \end{aligned} $$

For the distributive property of union of sets over intersection of sets,

$$ \begin{aligned} x[T]={} & \left(EXT^{c_{\rm NOW}}\left(\emph{w}'_{i_0'}[T]\right)~\cap~~EXT^{c_{\rm NOW}}\left(\emph{w}''_{i_0''}[T]\right)\right) \\ & \cup \ldots \cup \left(EXT^{c_{\rm NOW}}\left(w'_{i_k'}[T]\right)~\cap~EXT^{c_{\rm NOW}}\left(\emph{w}''_{i_k''}[T]\right)\right)\\ ={}&\left(EXT^{c_{\rm NOW}}\left(\emph{w}_1'[T]\right)~\cup~\ldots \cup EXT^{c_{\rm NOW}}\left(w_l'[T]\right)\right)\\ &\cap \left(EXT^{c_{\rm NOW}}\left(\emph{w}_1''[T]\right) \cup \ldots \cup EXT^{c_{\rm NOW}}\left(\emph{w}_m''[T]\right)\right) \end{aligned} $$

Since y[T] = $EXT^{c_{\rm NOW}}({w}'_0[T])$ ∪ ... ∪ $EXT^{c_{\rm NOW}}({w}'_l[T])$ and z[T] = $EXT^{c_{\rm NOW}}$ (w′′₀[T]) ∪ ... ∪ $EXT^{c_{\rm NOW}}({w}''_m[T])$, we have that x[T] = y[T] ∩ z[T] = x′[T]. Therefore, x = x′.

The proof for the other operators is similar.□

Property 3

(Reducibility of MIN, MAX, NULL and POINT algebrae to the standard (non-temporal) algebra) The MIN, MAX, NULL and POINT algebrae reduce to the standard algebra, i.e., the non-temporal relation obtained by applying extended temporal operators to temporal relations and then taking a snapshot is equivalent to the standard (non-temporal) relation obtained by first taking a snapshot of the temporal relations and then applying a standard (non-temporal) operator.

More formally, let r ^N and s ^N be bitemporal relations defined over a schema $R^N = (A_1, \ldots, A_n \mid TT_S, TT_E, VT_S, VT_E)$, c _T an arbitrary time value not exceeding current time and c _V an arbitrary time value, $\rho_{c_T}(\tau_{c_V}(r^N Op^N s^N)) = \rho_{c_T}(\tau_{c_V}(r^N)) Op^S \rho_{c_T}(\tau_{c_V}(s^N))$, where Op ^N is a temporal operator and Op ^S is a standard (non-temporal) operator. The statement is analogous for unary operators.

Proof

We prove the property for the operator of Cartesian product. The proofs for the other operators are analogous.

The equivalence is proved by proving the two inclusions.

First we prove that $\rho_{c_T}(\tau_{c_V}(r^N~\times^N~ s^N))~\subseteq~\rho_{c_T}(\tau_{c_V}(r^N))~\times^S~\rho_{c_T}(\tau_{c_V}(s^N))$.

Let R = (A ₁, ..., A _a , B ₁, ..., B _b |TT _S , TT _E , VT _S , VT _E ) be the schema of r ^N ×^N s ^N. We denote as A the attributes A ₁, ..., A _a and as B the attributes B ₁, ..., B _b . Let $x \in \rho_{c_T}(\tau_{c_V}(r^N \times^N s^N))$. Then, by definition of slice operators, there is a tuple x′ ∈ r ^N ×s ^N such that x′[AB] = x[AB] and $(c_T, c_V) \in EXT^{c_{\rm NOW}}((r^N \times$ ^N s ^N)[T]). Therefore, by definition of the ×^N, there exist a tuple y ∈ r ^N and a tuple z ∈ s ^N such that y[A] = x′[A], z[B] = x′[B], $(c_T, c_V) \in EXT^{c_{\rm NOW}}(y[T])$ and $(c_T, c_V) \in EXT^{c_{\rm NOW}}(z[T])$.

Therefore, by definition of slice operators, there exist a tuple $w' \in \rho_{c_T}(\tau_{c_V}(r^N))$ and a tuple ${w}'' \in \rho_{c_T}(\tau_{c_V}(s^N))$ such that w′ = y[A] = x′[A] and w′′ = z[B] = x′[B].

By definition of standard Cartesian product, there exists a tuple $x'' \in \rho_{c_T}(\tau_{c_V}(r^N)) \times^S \rho_{c_T}(\tau_{c_V}(s^N))$ such that x′′[A] = w′ = y[A] = x′[A] and x′′[B] = w′′ = z[B] = x′[B]. Therefore, x = x′′.

Now we prove that $\rho_{c_T}(\tau_{c_V}(r^N \times^N s^N)) \supseteq \rho_{c_T}(\tau_{c_V}(r^N)) \times^S \rho_{c_T}(\tau_{c_V}(s^N))$.

Let us assume that $x'' \in \rho_{c_T}(\tau_{c_V}(r^N)) \times^S \rho_{c_T}(\tau_{c_V}(s^N))$. By definition of ×^S operator, there exist a tuple $w' \in \rho_{c_T}(\tau_{c_V}(r^N))$ and a tuple ${w}'' \in \rho_{c_T}(\tau_{c_V}(s^N))$ such that x′′[A] = w′ and x′′[B] = w′′. By definition of the slice operators, there exist a tuple y ∈ r ^N and a tuple z ∈ s ^N such that y[A] = w′, z[B] = w′′, $(c_V, c_T) \in EXT^{c_{\rm NOW}}(y[T])$ and $(c_V, c_T) \in EXT^{c_{\rm NOW}}(z[T])$.

By definition of ×^N operator, there exists a tuple x′ ∈ r ^N ×^N s ^N such that:

$$ x'[A] = y[A], x'[B] = z[B] {\rm and} (c_V, c_T) \in EXT^{c_{\rm NOW}}(x'[T]) $$

By definition of slice operators, there exists a tuple $x \in \rho_{c_T}(\tau_{c_V}(r^N Op^N s^N))$ such that x = x′[AB]; therefore, since:

$$ x[A] = x'[A] = y[A] = \emph{w}' = x''[A] {\rm and} x[B] = x'[B] = z = \emph{w}'' = x''[B] $$

we have that x = x′′.□

Property 4

(Consistent extension) The temporal algebrae are consistent extensions of the standard (non-temporal) algebra, i.e., the standard relational operators have a counterpart in the temporal relational operators.

Proof

We have to prove that, let r ^N and s ^N be standard (non-temporal) relations defined over a schema: R = (A ₁, ...,  A _n ) and $tt\_start,~tt\_end,~\emph{v}t\_start,~\emph{v}t\_end$ timestamps,

$$ \begin{array}{rll} &&\mathit{transform}(r~Op~s,~tt\_start,~tt\_end,~ \emph{v}t\_start,~\emph{v}t\_end) = \\ &&\quad \mathit{transform}(r,~tt\_start,~tt\_end,~\emph{v}t\_start,~\emph{v}t\_end) Op^N\\ && \qquad ~transform(s,~tt\_start,~tt\_end, \emph{v}t\_start,~\emph{v}t\_end) \end{array} $$

where Op is a standard (non-temporal) operator and Op ^N a temporal operator. The statement is analogous for unary operators.

We prove the two inclusions separately for the Cartesian product. The proofs for the other operators are analogous.

Let x ∈ transform(r ×s, tt_start, tt_end, vt_start, vt_end). Then, by definition of transform function, x[AB] ∈ r ×s and x[T] = (tt_start, tt_end, vt_start, vt_end). By definition of ×, there exist a tuple y ∈ r and a tuple z ∈ s such that x[A] = y and x[B] = z. Applying the transform function to y, we obtain a bitemporal tuple y′ such that y′[A] = y and y′[T] = (tt_start, tt_end, vt_start, vt_end). The same holds for z: applying the transform function to z, we obtain a bitemporal tuple z′ such that z′[B] = z and z′[T] = (tt_start, tt_end, vt_start, vt_end). By definition of the ×^N operator, there exists a bitemporal tuple x′ such that x′[A] = y′[A], x′[B] = z′[B] and:

$$x'[T] = (tt\_start, tt\_end, {v}t\_start, {v}t\_end)$$

Then, x = x′.

Now we assume that x′ ∈ transform(r, tt_start, tt_end, vt_start, vt_end) ×^N transform(s, tt_start, tt_end, vt_start, vt_end). Then, by definition of ×^N, there exist a tuple y′ ∈ transform(r, tt_start, tt_end, vt_start, vt_end) and a tuple z′ ∈ transform(s, tt_start, tt_end, vt_start, vt_end) such that x′[A] = y′[A] and x′[B] = z′[B], and z′[T] ∩ y′[T] ≠ ∅. By definition of the transform function, there exist a tuple y ∈ r and a tuple z ∈ s such that y = y′[A] and z = z′[A], and y[T] = (tt_start, tt_end, vt_start, vt_end) and z[T] = (tt_start, tt_end, vt_start, vt_end). By definition of the × operator, there exists a tuple x′′ ∈ r ×s such that x′′[A] = y, x′′[B] = z. By definition of the transform function, there exists a tuple x ∈ transform(r ×s, tt_start, tt_end, vt_start, vt_end) such that x[A] = x′′[A] = y′[A] = y = x′[A], x[B] = x′′[B] = z′[B] = z = x[B] and $x[T] = z'[T] = y'[T] = x[T] = (tt\_start, tt\_end, {v}t\_start, \emph{v}t\_end)$.□