-
Notifications
You must be signed in to change notification settings - Fork 41
ModellingTime
This page gives a brief introduction to some standard concepts used when modeling time. The SWRLAPI uses these concepts in its implementation of an OWL- and SWRL-based temporal model.
Time has a standard geometric metaphor: time itself can be compared to a line; a point on this line is called an instant; the time between two instants is known as a time period; and a length, or unanchored segment, of the time-line is called an interval.
In general, three basic models of time can be chosen:
- a continuous model, where time is viewed as being isomorphic to the real numbers
- a dense model, where time is seen as being isomorphic to the rationals
- and a discrete model, with time being seen as isomorphic to the integers
Typically the discrete model is chosen because it is most efficiently modeled on a discrete computing device. This choice is, however, not crucial (apart from efficiency considerations) and does not limit the power of the temporal model.
Times are stored in a structure called a timestamp. Typically, a bounded time model will be chosen because an unbounded timestamp representation would be impractical. For example, SQL-92's calendar can only represent time from 1 A.D. to 9999 A.D. In any case, we usually operate on time as though it has some sort of bounds, so this model is not restrictive in practice.
Times on this bounded time segment are obtained by reading a time-line clock, the units of which are referred to as time-line chronons. The time-line is normally partitioned into a finite set of smaller segments called granules.
The partitioning function that maps time-line clock chronons into granules is referred to as the granularity. The smallest possible granularity is the time-line clock chronon; the largest granularity is the entire (bounded) length of time.
An instant is a point on a time-line, as opposed to granules, which are segments on the time-line. A period is the time between two instants. An interval is an unanchored duration of time; it will have a known length but no start or stop instants.
A datetime is an isolated point in time known to have a given granularity.
The following are examples of the use of datetime, intervals, and periods:
- Datetime When did the patient visit the clinic?
- Interval How long was the patient in the clinic?
- Period Did the patient visit the clinic between October and November?
Times on the time-line clock are related to more familiar temporal descriptions using calendars. The most familiar calendar would be the Gregorian calendar (a variant of which is used by SQL), though many others are possible, including user-defined calendars.
An instant timestamp records that an instant is located sometime during a particular granule, but we often do not know the exact granule during which it is located. Such an instant is termed indeterminate. Periods and intervals may also be indeterminate. The exact start and stop times of an indeterminate period are not reliably known. Similarly, the length (in time) of an indeterminate interval is not precisely known.
The following sections give a more detailed definition of some of the terms outlined above.
Granularity is the unit of measure for a temporal datum. The most familiar granularities that we deal with are seconds, minutes, days, weeks, and so on. Abstractly, a granularity may be seen a partitioning function that maps time-line clock chronons into granules. The smallest possible granularity is that of time-line clock chronons. The largest possible granularity is �all of time�, the entire time-line considered as a single granule.
A standard assumption is that the set of granules is well ordered within a given granularity. If we assume that we are using a bounded time model then we can use beginning and forever as two special values in this ordering. These value exist just outside the closed period of time. They represent the lowest and greatest values, respectively, in the ordering. Operationally, they are treated and minus and plus infinity. These special values will typically be used extensively in comparisons involving time. The model may also use a distinguished time called now to refer to the current time. �Now� is a special kind of datetime, rather than an interval or period.
Granularity and indeterminacy are related features of temporal data. Granularity is the unit of measure for a temporal datum, while indeterminacy represents partial information about finer units of measure. For example, an instant known at the granularity of an hour has an hour-long period of indeterminacy. We do not know, for example, in what second or minute the instant occurred. In other words, an instant measured at a particular granularity in indeterminate at all finer granularities.
The smallest granularity in a system will be the granularity of the time-line clock chronon. All other granularities will ultimately be described in terms of this granularity.
Not all temporal information will be known with certainty. For example, we may only know that some event happened �between 1 AM and 6 AM�, �sometime in late June�, or �sometime last year�. These are examples of temporal indeterminacy - we know that some event occurred but we do not know exactly when it occurred.
This indeterminacy can arise for several reasons: many dating techniques are inherently imprecise; the time of many events is often imprecisely specified; often, we just plain do not know when an event occurred.
In the abstract, all temporal information has some degree of uncertainty associated with it: the degree of accuracy of any measurement is at the very least limited by the resolution of our measurement device. This resolution must be specified at some granularity, and thus, by definition, the measurements will be imprecise at all finer granularities.
However, if we specify that we are interested in time information only at a particular granularity, then we can consider certain times specified at that granularity to be determinate. If we did not adopt this approach, we could never make any definite conclusions using the temporal information in our database. Note that we are dealing with uncertainty only in terms of when an event happened: we assume that the event did in fact happen � we just do not know exactly when. We are not dealing with the uncertainty of whether an event did in fact take place.
An instant is a point on the time-line, whereas a granule is a segment (however short) on the time-line. An instant timestamp records that an in instant is located in a particular granule. In many cases, however, we may not know the exact granule in which the event occurred - we may only know that the instant occurred some time during a range of granularities. We term this instant an indeterminate instant.
A determinate instant is a special version of an indeterminate instant with a one granule period of indeterminacy. In the abstract, all instant timestamps are indeterminate in that - beyond the resolution of the finest granularity (which will be the resolution of the timeline clock) - we can never know with absolute certainty when they occurred. This uncertainty is representative of the real world in that absolute precision is impossible - our measuring equipment will always have a limited resolution.
A calendar is a human abstraction of some portion of physical time. Thus, every calendar has an origin, which describes the point before which the calendar is not valid, and an end point, which describes the point after which a calendar is not valid. For example, the SQL calendar uses a variant of the Gregorian calendar with an origin of 1 A.D. Thus, the SQL calendar is unable to represent times before this date.
Within each calendar will be a finite set of granularities. For example, the Gregorian calendar supports granularities of seconds, minutes, hours, days, weeks, months, years, and decades; the Business calendar supports granularities of years, quarters, weeks, and days. The SQL-92 calendar supports the granularities of year, month, day, hour, minute, second, and fractions of a second.
A calendar is responsible for defining mappings between the different granularities that it contains. The Business calendar, for example, must be able to map between quarters and days. To perform this mapping, the calendar will first map from the coarsest granularity to successively finer granularities until it reaches the target granularity. Some mappings are straightforward or regular. The conversion of minutes to seconds is an example of a regular mapping. Other mappings are more complex and are termed irregular. The conversion of days to months would be an example of an irregular mapping. Irregular mappings are typically described by functions.
As mentioned, a calendar is responsible for defining the granularities that it contains and for defining the mapping functions from one granularity to another. These mapping functions will be exercised regularly because the mixing of temporal data at different granularities is common. This mixing creates various problems:
- What are the semantics of operations with operands at different granularities?
- Can times at different granularities be ordered?
- Can times be converted from one granularity to another?
- How expensive are temporal operations at mixed granularities?
- Can multiple granularities be stored as efficiently as a single granularity?
The relationship between granularities within a calendar is usually represented using a lattice. Each connecting arrow in the lattice describes the mapping between the granularities at each end of the arrow.
Granularities are calendar-dependent but they may be related by a single multi-calendar granularity lattice. In other words, different calendars may share the same granularities. In some cases, we may wish to specify calendars that are tailored to particular domains. For example, in the diabetes domain, we are frequently interested in the cycle of hours within a day, and are less interested in absolute time. Similarly, for other domains, we may be more concerned with the cycle of weeks within a month.
Regular and irregular mapping functions are provided by calendars to convert between granularities. Some irregular mappings may be quite complex. For example, a mapping from days to months must accommodate months that have different numbers of days, and must also consider leap years. In some calendars, there may even be an irregular mapping from minutes to seconds to account for leap second insertions.
The calendar must also specify an anchor point for each granularity it defines. At first sight, it does not seem obvious that all granularities do not share the same anchor point � we would expect the anchor point of all granularities to be the earliest time defined by the associated calendar. However, in many cases this assumption proves to be false.
For example, the origin of the Gregorian calendar is midnight, January 1, A.D. 1. If we adopted this time as the anchor point of the decade granularity, then the 10 years between 1971 and 1980, inclusive, would be a decade, rather than the 10 years between 1970 and 1979, inclusive. The latter, and not the former, fits the common definition of decade. Consequently, we cannot adopt the Gregorian calendar origin as the anchor point for decades. Instead we must pick a decade boundary as our anchor point. An example anchor point would be the start of the year A.D. 1000.
When anchor points differ between two granularities, semantic checking is performed to determine if the anchor point of the coarser granularity is on a granule boundary of the finer granularity.
The semantics of temporal predicates are modified by the granularities of the temporal elements in the predicate. For example, how do we compare a timestamp at the granularity of an hour with one at the granularity of a day? There are several possible approaches:
- Give a mismatched granularity error. Given that operations over different
- Perform the operation at the granularity of the first operand. Thus, the granularity of
- Perform the operation at the finest granularity. All instants are thus converted to the
- Alternatively, we could perform the operation at the coarsest granularity. We thus
With the exception of the first approach, all the above solutions rely on operations that move times within the granularity lattice. The following subsection describes an operation called scale that moves time up and down the granularity lattice.
Scale uses the regular and irregular mappings between granularities to convert a time from one granularity to another. The mechanics of scale depends on whether we are converting to a finer or coarser granularity. We discuss converting from a finer to a coarser scaling first, followed by the conversion of a coarse to a fine scaling.
Scaling a determinate instant from a finer to a coarser granularity results in a determinate instant. We use the mapping function provided in the lattice to scale from the fine to the coarse granularity; we must also consider differences between the anchor points of both granularities.
For example, suppose that we wish to scale an instant, time, from finer granularity, f, to coarser granularity c. In this example, we assume that there are no intermediate granularities between f and c. Let df,c be the difference between the granularity anchor points f and c, expressed in the finer granularity, f. Let mapf_to_c be the mapping (regular or irregular) from the finer to the coarser granularity. Then we can define scale as follows:
scale(timef, c) = mapf_to_c(timef � df,c) = timec
If an intermediate granularity, i, lies between f and c in the granularity lattice, we can compose the mapping functions as follows:
scale(timef, c) = mapi_to_c (mapf_to_i(timef � df,i) � di,c) = timec
Using the above approach we can move time any number of levels in the granularity lattice. Note that we lose information when we scale from a fine to a coarser granularity.
Scaling a determinate instant from a coarser to a finer granularity generates an indeterminate instant. The mechanics of scaling are similar to the approach used in the fine-to-coarse mapping outlined above, but now our result will be an indeterminate period.
Assuming a mapping from a coarse granularity, c, to finer granularity, f, we define our mapping as follows:
scale(timec, f) = (mapc_to_f (timec � dc,f)) ~(mapc_to_f ((timec + 1) � dc,f) - 1)
The upper and lower bounds are scaled separately and our result is a pair of times representing an indeterminate period.
With minor modifications, we can adopt the above approach to scaling both periods and intervals.