An assertion of the form
On o, v = p i from f to t
contains two time-dimensions o and f to t. Accordingly, it is called a bitemporal assertion. There are six variables in the scheme:
o the time on which the assertion is made (sometimes called "transaction time") p a property i an individual v a value of p f the time from which v = p i (sometimes called "beginning valid time") t the time to which v = p i (sometimes called "ending valid time")
For example,
On 1997-1-1 phone of 123 = 555-1234 from 1996-10-15 to 1997-3-1
The assertion is an event which occurs on 1997-1-1. It says that the phone of individual 123 is 555-1234 at all times greater than 1996-10-15 and less than or equal to 1997-3-1. A later assertion, made on 1997-3-10, might say something different about 123's phone: that it is now 555-5678 over that same interval, or that it is 555-1234 over a different interval:
On 1997-3-10 phone of 123 = 555-5678 <- corrected number from 1996-10-15 to 1997-3-1
On 1997-3-10 phone of 123 = 555-1234 from 1996-10-12 <- corrected start time to 1997-3-1
There are five important forms of bitemporal query:
On time o, which individuals x satisfy : v f p x : at time a?
For example,
On 1997-1-1, which individuals x satisfy 555* = phone x 12 = floor x 20000 < salary x at 1997-2-1?
In other words, on 1997-1-1, who did the database say would have 555- phone numbers, offices on the 12th floor, and salaries greater than $20,000 on 1997-2-1? The result of an individual query is a list of individuals which satisfy the query.
On time o, for property p and individuals i, which values x satisfy : x = p i : at time a?
For example,
On 1997-1-1, which offices did individuals 13, 17, and 38 have at 1996-6-1?
Satisfy v, f, and t in: on o v = p i from f to t for o, p, and i.
We hold o, p, and i constant, and find all combinations of v, f, and t which make the scheme true. For example, on 1997-1-1, what phone numbers has 123 had, and when? What phone number does 123 have now? And what phone numbers will 123 have, and when? The result of an individual history query is a table containing three fields:
v f t - - - : : : x y z : : :
A record in the table says that on o, x = p i from y to z. No interval in a record can overlap the interval of any other record, since no individual can have more than one value of a property at any time. Nor can there be gaps, since an individual is a thing which undergoes continuous change through time.
Satisfy v, f, and t in: on o v = pj i from f to t for o, ... pj ..., and i
For example, on 1997-1-1, what is the name- and phone-history of individual 123?
name phone f t ---- ----- - - jack 555-1234 -0i 1994-1-1 john 555-1234 1994-1-1 1995-1-1 john 555-2345 1995-1-1 0i
The individual 123 joined the firm as "Jack" and was assigned 555-1234. Then on 1994-1-1, he changed his name to "John" (but kept his original phone). Then, on 1995-1-1, he changed his phone to 555-2345. The result of the multi-property individual history is a table with a row for each change in the state of any one of the properties involved.
Satisfy i, f, and t in: on o v = p i from f to t for o, p, and v
We hold o, p, and v constant, and find all combinations of i, f, and t which make the scheme true. For example, on 1997-1-1, who had a 555 phone number, and when? Who has one now? And who will have one, and when? The result of a property history is a table containing three fields:
i f t - - - : : : x y z : : :
A record in the table says that on o, v = p x from y to z. An interval in a record can overlap an interval in another record only if the individuals are distinct. There can be gaps in the history of an individual.
Snapshot and individual queries have the same inputs. The result of a snapshot query is a table whose keyfield is the result of the individual query, and whose fields are properties in the individual query:
i phone floor salary - ----- ----- ------ : : : : 101 555-1234 12 21500 : : : :
What we have been calling an "individual" is a structural property of the database, a way of grouping assertions within and across property tables. Suppose we form the individual history query:
What is the name-history of individual 123?
How did we come up with individual 123? Why do we think we are interested in that individual? It can only be that 123 was the result of some previous individual query; for example:
Which individual has phone number 555-1234?
Our access to individuals is by way of properties, asserted on a time to hold for an interval. The designer of a bitemporal database may decide that certain properties must not change over time. For example, while an employee's name or phone number may change, his company id may not. That property is used to track him through history. If it were allowed to change, we could not frame our queries with any confidence that we were talking about the same person. To allow for uniform error-correction, properties such as company id should still be implemented bitemporally. The user-interface can "know" that history queries are always framed in terms of company id:
What is the name of the individual with company id 999?
should be translated into an individual subquery:
What is the name of individual i where i is the unique individual who has company id 999?
Similarly, in reporting query-results, columns which refer to individuals should be formatted to the values of fixed properties. For example, the result of the property history query
Which individuals have occupied office 22?
should be reported as:
i f t company-id - - - ---------- : : : : x y z w : : : :
where w is the value (now and ever) of the company-id property for individual x.
A bitemporal table is represented as a set of bitemporal property tables. Each property table has five fields:
i: individual v: value f: from t: to o: on
For example, suppose we want to convert the atemporal table below to bitemporal form:
name office phone ---- ------ ----- tom 22 555-1234 dick 34 555-2345 harry 17 555-3456
Generate three individuals 0, 1, and 2, and create the following three property tables:
name:
i v f t o - - - - - 0 tom -0i 0i _T 1 dick -0i 0i _T 2 harry -0i 0i _T
office:
i v f t o - - - - - 0 22 -0i 0i _T 1 34 -0i 0i _T 2 17 -0i 0i _T
phone:
i v f t o - - - - - 0 555-1234 -0i 0i _T 1 555-2345 -0i 0i _T 2 555-3456 -0i 0i _T
A record in a property table p is an assertion that on o, v = p i from f to t. i groups assertions within and across property tables. Every individual occurs in every property table. o records when the assertion was added to the table. Property tables are ordered by o. 0i is infinity, and denotes the infinite future. -0i is negative infinity, and denotes the infinite past. _T is "now", the current time. Null may occur in v, but not in i, f, t, or o. Non-stratified properties: for any property p, ?p.i (unique p.i) is the universe of individuals. When, on x, an individual y is added to the universe, the assertion
on x, null = p y from -0i to 0i
is appended to every property table:
i v f t o - - - - - : : : : : y null -0i 0i x
The implementation language is K.
d:{(_dj _ x%86400.;100_sv 24 60 60_vs _ x!86400.)}
t:{(24 60 60_sv 0 100 100_vs y)+86400.*_jd x}
sp:{1_'(&x=*x)_ x}
dt:{{t . 100_sv'0$(sp"-",x;sp":",y)}. 2#sp" ",x," 0"}
na:(;0N;0n;;`)@__abs 4::
dt"1995-01-02 17:30:26"
-1262154574.0
dt"1995-01-02"
-1262217600.0
na 1 2 3
0N
na 1 2 3.
0n
na `one`two`three
`
The individual query function takes four arguments:
o: on time a: at time p: property symbol v: f[x] a boolean function f of property value x
and returns the indices of those assertions in p which for which f[x] at a is true on o.
ti:{[o;a;p] / individual index
k:!p[`o]_bin o / assertions made on times < o
k@:&a>p[`f;k] / assertions about a time beginning a
k@:&~a>p[`t;k] / assertions about a time ending on or after a
k@(*|:)'=p[`i;k]} / latest assertion for each individual
qi:{[o;a;p;v] / query index
k:ti[o;a]p / temporal indices
k:[~_n~v;&v p[`v;k]]} / assertions which satisfy non-null f[x]
Given indices and property, the 'id' function returns the individuals which are the subjects of those assertions:
id:{[p;k]p[`i;k]}
Given a list of vectors of individuals, the 'is' function computes the intersection of the vectors:
is:{:[#x;{x@&x _lin y}/x@<#:'x;x]}
The individual query function: intersect the individuals which satisfy the bitemporal query (o;a;q):
iq:{[o;a;q]is(!q)id'qi[o;a]'[!q;q[]]}
For example, suppose we have property tables name, phone, dept, office, and title. And we have 1000 individuals 0 ... 999. We want to know which vice-presidents (if any) were believed on 1996-10-15 to have occupied office 12 at 1996-10-12:
q[`office`title]:(10=;`VP=) iq[dt"1996-10-15";dt"1996-10-12"]q 101 117
Since vice-presidents rate single offices, there is probably an error, which was corrected later:
iq[dt"1996-11-1";dt"1996-10-12"]q ,117
The property query function takes four arguments:
o: on time a: at time p: property symbol i: vector of indivduals
and returns a vector of values v of p s.t. &/i = p i on o at a:
pq:{[o;a;p;i] / property query
k:ti[o;a;p]v / temporal indices
(p[`v;k],na p`v)p[`i;k]?/:i} / property values for individuals
i:iq[o;a;.,(`p;v=)] / i:v = p x
((#i)#v)~pq[o;a;`p]i / v:x = p'i
1
The individual history function takes three arguments:
o: on time p: property symbol i: individual
and returns a list of three vectors:
(... v ... ... f ... ... t ...)
where each column says that on o, v = p i from f to t. Note that the first element of f is -0i and the last element of t is 0i, since individuals are eternal. Also note that the f k = t k-1, since there are no times during which the individual did not exist.
ih:{[o;p;i]
k:!p[`o]_bin o / assertions <= o
k@:&i=p[`i;k] / assertions about i
hi . tl . p[`v`f`t;k]} / history of timeline
tl:{[v;f;t]tu[u]tv[u@:<u:?f,t;v;f]t} / timeline
tv:{[u;v;f;t] / time vector
j:i+!:'(u _binl t)-i:u _binl f / enumerated t-f
@[(#u)#na v;j;:;v]} / amend value state
tu:{[u;s](u;s)@\:&~0(=;~)[~4:s]':s} / fuse partial assertions
hi:{[u;s](,-1_ s),+{y,x}':u} / history
it:{@[_n;`v`f`t;:;x]} / matrix (v;f;t) -> table[`v`f`t]
The timeline function tl take as arguments three vectors of equal lengths: v (values), f (from times), and t (on times). u is a vector of sorted unique timepoints in f and t. The time vector function tv takes u, v, f, and t. Endpoints of the f-t intervals are identified (by replacing times with indices into u), and the integer differences t-f are then enumerated (e.g. 7-3 -> 4 -> 0 1 2 3 + 7 -> 8 9 10 11). The list of index vectors is then used to populate contiguous stretches of the state vector with successive values of v. The time unique function tu takes u and the amended state vector s and fuses partial assertions. Input to tu is a pair of vectors, u and s, which describes a timeline of the form
u:-0i x ... y 0i s:null z ... w null
Where adjacent s-values are identical, the timeline can be compressed. For example,
u:... a b c ... s:... v v w ...
says that v from a to b, and that v from b to c, which is more compactly expressed as
u:... a c ... s:... v w ...
which says that v from a to c. The history function takes u and s and folds u into successive intervals:
u:a b c d s:x y z z hi[u]s (x y z;a b c;b c d)
Ih:{[o;p;i] / multi-property individual history
t:ih[o;;i]'p / individual histories
r:hi . tu[u]@+(tv[u@:<u:?,//t[;1 2]].)'t / (value tuples;f;t)
(+*r),1_ r} / (v1;...;vn;f;t)
It:{[p;x]@[_n;p,`f`t;:;x]} / (v1;...;vn;f;t) -> [`p1;...;`pn;`f`t]
The property history function takes three arguments:
o: on time p: property symbol v: value
and returns a list of three vectors:
(... i ... ... f ... ... t ...)
consisting of appended individual histories. Each history consists of non-overlapping segments, possibly containing time-gaps. Each segment is an assertion to the effect that v = P i from f to t.
ph:{[o;p;v] / property history
t:@[_n;!p;:;p[;&v=p`v]] / restrict to assertions that v = p
,'/i pi'ih[o;t]'i:?t`i} / append individual histories
pi:{.[y;(0;);:;x]} / replace v with i
pt:{@[_n;`i`f`t;:;x]} / matrix (i;f;t) -> table[`i`f`t]
A snapshot of a series of bitemporal properties p1,...,pn is a table with fields
i: individual (key) p1: property : pn: property
derived by intersecting the subtables !q which satisfy query (o;a;q). For example, the result of the snapshot query
sq[dt"1999-1-1";dt"1995-1-1";.((`name;);(`age;))]
is a table with fields i, name, and age. A row, for example,
i name age - ---- --- 101 fred 22
is an assertion that on 1999-1-1, 101's name was fred and 101's age was 22 at 1995-1-1. We do not know over what specific intervals this individual had these properties. The result assertion is consistent with any one of the following temporal assertions:
i v f t - - - - 101 fred 1994-1-1 1996-1-1 101 fred -0i +0i 101 fred -0i 1996-1-1
The snapshot query function takes three arguments:
o: on time a: at time q: query dictionary
and returns a table with key-field i and value-fields !q:
sq:{[o;a;q]in/(!q)st'qi[o;a]'[!q;q[]]} / intersect atemporal property-tables
st:{[p;k]@[_n;`i,p;:;p[`i`v;k]]} / project, select
in:{ / intersect tables x[`i`v1] and y[`i`v2]
x:@[x;_n;@[;&x[`i]_lin y`i]] / restrict x to individuals in y
i:x[`i]?/:y`i / index of y-individuals in x-individuals
i@:&i<#x`i / restrict y-individuals to ones in x
j:(!y)1 / name of value field in y
@[x;j;:;y[j;i]]} / insert y value field in x