This document describes the design of a Temporal Abstract Data-type (TADT). The design is based on a C and C++ design of a TADT in the MultiCal system.
The following sections outline each of the major pieces of the design and give a rationale as to the importance of each. The design has been implemented and is in the public domain.
TimeValueThe TimeValue Interface is an API for a set of primitive operations on time-values from some underlying temporal domain. This domain could be bounded or unbounded, discrete or continuous, have exact values or fuzzy, inexact values, etc. The TimeValue interface has just a minimal set of operations on TimeValues needed to support higher-level, richer semantics. The interface permits a complete encapsulation of the domain-dependent code, isolating it from other parts of the TADT.
The TimeValue API is implemented in the desired domain. For example, we have implemented a discrete, unbounded domain with two special values (effectively the integers plus Beginning and Ending of Time, the latter two values have special semantics). The domain is unbounded since it uses Java's built-in BigInteger class (which does not limit the size of integers).
SemanticsThe Semantics Interface defines a set of basic operations that should be supported by a Temporal Semantics (perhaps a better name would be TemporalSemantics).
The general idea behind the Semantics interface is to abstract the operations on temporal entities. Such operations have a variety of meanings or interpretations. Each implementation of the Semantics interface imbues temporal operations with a different meaning.
For example, a Semantics should support an operation that determines whether one instant precedes another. For the purpose of this example, we will assume that an instant is represented as a point on an underlying discrete time-line. Several alternative semantics for this simple operation
LeftOperandSemantics which casts the second operand to the granularity of the first operand in all operations). Here is an example using the LeftOperandSemantics.
Instant i = new Instant(...); Instant j = new Instant(...); Interval k = new Interval(...); // A Semantics is just a name space Semantics ops = new LeftOperandSemantics();Note that to change to a different semantics for the operations, all we have to do is change one line, e.g.,
// Scale to the coarser operands Semantics ops = new CoarserOperandSemantics();All the other code remains exactly the same.
Instead of using an interface and allowing dynamic switching between semantics, one could use a package to encapsulate the semantics and call operations statically. For example, assume the LeftOperandSemantics package has the Ops class that statically defines all the available operations. Then the code given above would look like the following.
import LeftOperandSemantics.*; ... Instant i = new Instant(...); Instant j = new Instant(...); Interval k = new Interval(...); // A Semantics is just a name spaceBy using the package, the semantics is fixed at compile-time (or more correctly class loading time), whereas using an interface supports run-time switching of the Semantics and provides a general template for what operations a Semantics should support (at a minimum). I chose the latter.
We didn't add the ability to use different Semantics to the previous versions of MultiCal (and it is not in the C++ OO design) because at the back of our minds we had what we wrote in the granularity paper: the SQL compiler will generate the proper code with the casts and scales done prior to the operation. There are two reasons why this won't be best in this context.
Instant i = new Instant(...); Instant j = new Instant(...); Interval k = new Interval(...); // A Semantics is just a name space IndeterminateSemantics ops = new LeftOperandIndeterminateSemantics();On the user's side, only two lines change, one to establish the new semantics, and one to set the plausibility.
I'm certain that not every new semantics can be accommodated so easily within this framework, but all the ones that I currently know about can. And it gives us some leverage for accommodating other as yet unthought of, temporal semantics.
I anticipate that TSQL2 semantics will be just another implementation of a Semantics, exactly as any other semantics, although it will perhaps support a lot more methods than are outlined in the basic Semantics Interface, but that is not a worry, as one can always add to an interface.
Anchorables and UnanchorablesThis section outlines the basic kinds of temporal values available. I wanted to be able to deal with new kinds of basic temporal entities. So I identified a minimal set of requirements that temporal entities such as Instants and Periods must have to support a Semantics and put those requirements into an Anchorable Interface. The requirements for Interval-like things is the Unanchorable Interface. Things like Instants and Intervals are implementations of the temporal entities, although these two classes are very special implementations since many of the operations in a Semantics are carried out with respect to arrays of Instants/Periods and Intervals.
But before I talk about those two classes, suppose one wanted to add an PeriodicInstant temporal entity which is a periodic instant. Basically, all they have to do is implement the Anchorable interface and then you should be able to add PeriodicInstants to TemporalElements without any problems. Anyways, that is the goal, and in theory, if I've done the design correctly, that is how it should work. Note that Semantics are defined with respect to operations on Anchorables and Unanchorables, so the Semantics should work no matter what kinds of Anchorables and Unanchorables you give it, as long as they correctly implement the Anchorable/Unanchorable interface.
As an aside, suppose you didn't want your LeftOperandSemantics to add PeriodicInstants and Intervals. My view is that you are making an arbitrary decision in your semantics (which could be perfectly OK in a different semantics) so to handle this restriction you just overload the add method in your implementation of the semantics to detect this combination and either die if the user tries it or throw the appropriate exception. So the design allows restrictions of general operations (needed for TSQL2).
The Instant, Period, and Interval, classes are special implementations and support all the operations on that are needed to implement a Semantics. To be truly orthogonal, I should define them as an Point, Segment, and a Distance interface, respectively, and then implement the interface appropriately. But I slanted the names to just a Temporal domain. For BiTemporalElements a "Region" class will be needed to support operations on regions.
ExtendedBooleanThe ExtendedBoolean class encapsulates boolean operations on some underlying multi-valued domain. I've currently implemented it on a 2-valued domain, but a 4-valued domain is needed for indeterminacy, and I suspect a 3-valued domain is really what you need for a determinate TSQL2 Semantics. New implementations are easy to do and plug in. Rather than implement it as an interface, my plan is to put it into it's own package so that a semantics can import the appropriate ExtendedBoolean package, but perhaps it might be cleaner to just do it as an interface.
C/C++/Java APIA unified API of just the TSQL2 semantics that doesn't use overloading or constructors can be written using calls to the appropriately implemented Semantics, Anchorables, and Unanchorables, with everything packaged in a TSQL2 package. For example, the add operation in the TSQL2 API might be (assume the Semantics implementation is provided by the tadt.standard package):
package TSQL2.API; import TSQL2.Instant.*; import TSQL2.Interval.*;and an Instant constructor could be:
package TSQL2.API; import TSQL2.Instant.*;
ConclusionThis is just a brief outline of the design, the API is on-line. It is not a radical departure from the earlier C and C++ designs, rather it generalises those designs to make them more flexible, and hopefully of more use. At the same time, it does not sacrifice efficiency; this design incorporates the previous C design that I sent you recently except for the fancy stuff involving interfaces and (lots of) method overloading (neither of which should have much of an impact, if any). Neither of these designs have any mutators (so when you add two intervals, you get a new interval), I believe that allocating objects as needed makes the code easier to write. Of course, one could always implement a MutatingInstant as an Anchorable and use it in an implementation of a Semantics called the SuperEfficientLeftOperandSemantics. The design allows you to do these kinds of things if you really, really want to.
Copyright © 1996 Curtis E. Dyreson. All rights reserved.
Curtis E. Dyreson © 1993-2001. All rights reserved.
|E-mail questions or comments to Curtis.Dyreson at usu.edu|