Bitemporality


Concepts

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 

Queries

There are five important forms of bitemporal query:

1. Individual

	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.

2. Property

	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?

3. Individual history

	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.

3a. Multi-property individual history

	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.

4. Property history

	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.

5. Snapshot

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
	:		:		:		:

Individuals

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.

Representation

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

Implementation

The implementation language is K.

0. Common

	  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_'(&ampx=*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
	`

1. Individual

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@&lt#:'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

2. Property

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

3. Individual history

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@:&ltu:?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)

3a. Multi-property individual history query

	Ih:{[o;p;i]                                     / multi-property individual history
	 t:ih[o;;i]'p                                   / individual histories
	 r:hi . tu[u]@+(tv[u@:&ltu:?,//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]

4. Property history

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]

5. Snapshot

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&lt#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