=Paper=
{{Paper
|id=None
|storemode=property
|title=Best-practice Time Point Ontology for Event Calculus-based Temporal Reasoning
|pdfUrl=https://ceur-ws.org/Vol-966/STIDS2012_T03_Schrag_BestPracticeTemporalReasoning.pdf
|volume=Vol-966
|dblpUrl=https://dblp.org/rec/conf/stids/Schrag12
}}
==Best-practice Time Point Ontology for Event Calculus-based Temporal Reasoning==
https://ceur-ws.org/Vol-966/STIDS2012_T03_Schrag_BestPracticeTemporalReasoning.pdf
Best-practice time point ontology for event calculus-
based temporal reasoning
Robert C. Schrag
Digital Sandbox, Inc.
McLean, VA USA
bschrag@dsbox.com
Abstract—We argue for time points with zero real-world time scale consisting of successive steps, two distinct instants
duration as a best ontological practice in point- and interval- may be expressed by the same time point,” and also
based temporal representation and reasoning. We demonstrate (unfortunately, apparently circularly) defines an instant as a
anomalies that unavoidably arise in the event calculus when real- “point on the time axis.” We hope, by demonstrating
world time intervals corresponding to finest anticipated calendar anomalies resulting from incorrect time point treatment and by
units (e.g., days or seconds, per application granularity) are taken presenting effective correct implementation techniques, to
(naively or for implementation convenience) to be time “points.” motivate future best-practice event calculus-based applications.
Our approach to eliminating the undesirable anomalies admits
durations of infinitesimal extent as the lower and/or upper II. EVENT CALCULUS ONTOLOGY AND AXIOMS
bounds that may constrain two time points’ juxtaposition.
Following Dean and McDermott, we exhibit axioms for temporal We have implemented a temporal reasoning engine for an
constraint propagation that generalize corresponding naïve event calculus variant including the following ontological
axioms by treating infinitesimals as orthogonal first-class elements.
quantities and we appeal to complex number arithmetic
• Time intervals are convex collections of time points—
(supported by programming languages such as Lisp) for
intuitively, unbroken segments along a time axis.
straightforward implementation. The resulting anomaly-free
operation is critical to effective event calculus application in • The ontological status of time points is an issue
commonsense understanding applications, like machine reading. contended here. We argue that in the best practice they
are taken to be instants with no real-world temporal
Index Terms—temporal knowledge representation and extent, while naïvely (we argue incorrectly) finest
reasoning, event calculus, temporal ontology best practices, anticipated calendar or clock units—which actually are
temporal constraint propagation intervals—have been taken as time “points.” We take
a time point to be a degenerate time interval—one
I. INTRODUCTION whose beginning and ending points both are the time
point itself.
Machine reading technology recently has been applied to • Fluents are statements representing time-varying
extract temporal knowledge from text. The event calculus [8] properties—e.g., the number of living children a
presents appropriate near-term targets for formal statements person has.
about events, time-varying properties (i.e., fluents), and time
• The events of interest occur at individual time points
points and intervals. While at least one implemented event
and may cause one or more fluents to change truth
calculus-based temporal logic [2] also has included calendar
value. E.g., the event of adopting an only child will
dates and clock times, most classical event calculus treatments
cause the fluent hasChildren(Person, 0) to become
address real-world time only abstractly. None so far has
false and the fluent hasChildren(Person, 1) to become
adopted the carefully crafted formulation of points (instants),
true.
intervals, dates, and times in Hobbs’ and Pan’s RDF temporal
ontology [4]—which correctly treats all time units as intervals. Figure 1 exhibits axioms defining the predicates we use to
We say, “correctly,” because the casual treatment of a calendar say when fluents “hold” (are true) and when events “occur”
or clock unit as a time point unavoidably leads to undesirable (happen).
anomalies. This point may be subtle—ISO standard 8601 [3]
pertaining to representation of dates and times states, “On a
holdsThroughout(fluent, interval) ↔ ∀(point): pointInInterval(point, interval) → holdsAt(fluent, point)
holdsThroughout(fluent, interval) ↔ ∀(sub): hasSubInterval(interval, sub) ˄ holdsThroughout(fluent, sub)
holdsAt(fluent, point) ↔ ∃(interval): intervalIsPoint(interval, point) ˄ holdsThroughout(fluent, interval)
holdsWithin(fluent, interval) ↔ ∃(sub): hasSubInterval(interval, sub) ˄ holdsThroughout(fluent, sub)
occursWithin(event, interval) ↔ ∃(point): pointInInterval(point, interval) ˄ occursAt(event, point)
Figure 1. Axioms relating holds and occurs predicates. Variables appearing on the left-hand side of an initial implication are
universally quantified. Variables introduced on the right-hand side are quantified as indicated. The predicates relating time
points and intervals are defined in the appendix.
Informally, a fluent holds throughout an interval I iff it A given event calculus application also will include axioms
to indicate which transition events initiate or terminate which
holds at every point and throughout every subinterval contained
fluents, as summarized by Schrag [7]. We don’t need that
by I. It holds (or occurs) within I iff it holds (or occurs) within
some subinterval (or point) contained by I. much detail here, however, to demonstrate our concerns about
undesirable anomalies arising from the naïve approach.
In the naïve approach, it’s perfectly acceptable to assert that
a fluent holds or that an event occurs “at” a specific “point” on III. ANOMALIES ARISING FROM THE NAÏVE TIME POINT
the calendar or clock. We believe that under the preferred APPROACH
approach, in which the only (true) points directly accessible
delimit the boundaries of measured time units, such assertions We discuss the following anomalies.
(or even queries) should be rare—perhaps limited to issues of A. Inability to order time points within a finest
legal status (e.g., one reaches the age of majority at exactly represented time unit (e.g., a calendar day—see
12:00 midnight on one’s 21st birthday). Thus, we commend section A)
preferred use of holdsWithin and occursWithin to replace naïve B. Inability to avoid inferred logical contradiction
use of holdsAt and occursAt. when contradictory statements hold at different
Besides being correct, the preferred approach is also more real-world times within a finest represented time
robust. In the naïve approach, supposing an enterprise decides unit (see section B)
to enhance its represented granularity from days to hours, it C. Inability to order real-world events occurring
will need to replace all existing occurrences of holdsAt with within a finest represented time unit (see section
holdsWithin (because its working definition of a “point” will C)
have changed). As such, naïve approach users might as well D. Inability to avoid inferred logical contradiction
avoid holdsAt and just use holdsWithin, which has equivalent when real-world events occur within a finest
semantics when its interval argument is a time point. represented time unit and initiate contradictory
fluents (see section D)
The time map in Figure 2 illustrates these anomalies, as
discussed in the following subsections.
hasMaritalStatus(John, Married)
hasMaritalStatus(John, Unmarried)
hasMaritalStatus(John, Married)
,
,
DivorceEvent(John, Sally) MarriageEvent(John, Mary)
12:00 AM A B 11:59 PM
Figure 2. Time map illustrating naïve approach anomalies. Fluent observations (top) include fluents and the intervals
throughout which they hold. Dark-filled points indicate that associated fluents are known not to hold beyond their intervals’
beginning or ending. Constraint graphics (with arrows) are defined in Figure 9, in the appendix. Transition event occurrences
(middle) include the events and points where these occur. Contradictory fluents cannot overlap temporally, and, per event
calculus convention, initiated fluent observations begin immediately after triggering transition events. The calendar (bottom)
shows the initial and final minutes of a given day, plus two included time points, ordered as shown.
D. Inability to order occurs statements initiating contradictory
A. Inability to order time points
fluents
As is apparent in Figure 2, this basic problem underlies the
Without the ability to order events, we don’t know whether
other three listed above. In the naïve approach, the only way to
any axiom proscribing polygamy has been violated or not. An
order time points is to associate them with distinct finest
implementation might take one position or another, depending
calendar or clock units. Suppose days are the finest time unit
on the order in which it happened to visit the transition events
represented. We’d like to assert the point-wise temporal
and to apply its rules for initiating and terminating fluents,
relations (i.e., constraints) Figure 2 indicates, but in the naïve
detecting contradictions, and propagating constraints.
approach such constraints would be contradictory—all the
points shown would resolve to the same calendar day’s time IV. TEMPORAL CONSTRAINT REPRESENTATION AND
“point,” which cannot precede itself. This anomaly can be PROPAGATION
particularly troubling in the representation of statements
extracted by machine reading from news articles, which Compared to an application’s finest represented calendar or
frequently exhibit only calendar dates but cover sequences of clock unit, available real-world information may be more or
events occurring within single days. The option of discarding less precise. E.g., we may know the year that a given event
such fine ordering information—and treating all within-day occurred but not the month or the day. If our finest represented
events as if they were simultaneous—is equally problematic. units are days, this gives us an earliest and a latest possible date
Rendering event orderings correctly is critical to representing on which the event could have occurred (the first and last days
causality—just one fundamental element of a true of the year given). We use the notation distance(a, b, [x, y]) to
commonsense understanding that machine reading is hoped indicate that the number of finest time units along a path from
ultimately to support. time point a to time point b has as a lower bound x and as an
Even when our representation isn’t fine enough to specify upper bound y.
absolutely when during a given day (e.g.) a time point occurs, Rather than expose our system-internal time units, we
when we can order the points, we can avoid contradictions provide a user interface in terms of calendar and clock units—
resulting from an incorrect presumption of simultaneity. affording users source code-level robustness against future
Absent total (or even partial) ordering, we also can still granularity enhancements. A distinguished calendar/clock
hypothesize orders that might not lead to contradictions. point (e.g., the beginning point of the interval for 12:00
midnight, January 1, 1900) affords a reference against which
B. Inability to order contradictory holds statements the distance to other dates/times is calculated.
A person can’t be both married and unmarried at the same We refer to an asserted distance statement (or to a user-
time, as would be required if all the constraint-linked points in provided statement from which it is derived) as a temporal
Figure 2 were collapsed onto a single day “point.” In the naïve constraint.
approach, it is (from a real-world perspective) as if we forced Real-world information also may give us only qualitative
every marriage or divorce (indeed, every event) to occur at the information about the relationship between two time points—
stroke of midnight. e.g., one is before or one is after the other. The following two
figures exhibit axioms to define qualitative relations among
C. Inability to order events time points—Figure 3 following the naïve approach, Figure 4
In the naïve approach, we can say that a person divorced the preferred one. (See also Figure 9 in the appendix for
one spouse and married another on the same day, but we can’t graphical definitions of these relations.) Notice that the only
say in what order these events occurred. difference between these two axiom sets is in their
representation of the smallest possible distance between any
two time points. In the naïve approach, it is one finest time
unit. In the preferred approach, it is arbitrarily small—taken to
be infinitesimal.
timePointEqualTo(a, b) ↔ distance(a, b, [0, 0])
timePointLessThan(a, b) ↔ distance(a, b, [1, ∞])
timePointGreaterThan(a, b) ↔ distance(a, b, [–∞, −1])
timePointGreaterThanOrEqualTo(a, b) ↔ distance(a, b, [0, ∞])
timePointLessThanOrEqualTo(a, b) ↔ distance(a, b, [–∞, 0])
hasNextTimePoint(a, b) ↔ distance(a, b, [1, 1])
hasPreviousTimePoint(a, b) ↔ distance(a, b, [−1, −1])
timePointTouching(a, b) ↔ distance(a, b, [−1, 1])
timePointGreaterThanOrTouching(a, b) ↔ distance(a, b, [−1, ∞])
timePointLessThanOrTouching(a, b) ↔ distance(a, b, [–∞, 1])
Figure 3. Axioms defining qualitative relations between time points in the naïve approach, where finest time units are treated as
“points” and the smallest possible distance is one such time unit
timePointEqualTo(a, b) ↔ distance(a, b, [0, 0])
timePointLessThan(a, b) ↔ distance(a, b, [ϵ, ∞])
timePointGreaterThan(a, b) ↔ distance(a, b, [–∞, −ϵ])
timePointGreaterThanOrEqualTo(a, b) ↔ distance(a, b, [0, ∞])
timePointLessThanOrEqualTo(a, b) ↔ distance(a, b, [–∞, 0])
hasNextTimePoint(a, b) ↔ distance(a, b, [ϵ, ϵ])
hasPreviousTimePoint(a, b) ↔ distance(a, b, [−ϵ, −ϵ])
timePointTouching(a, b) ↔ distance(a, b, [−ϵ, ϵ])
timePointGreaterThanOrTouching(a, b) ↔ distance(a, b, [−ϵ, ∞])
timePointLessThanOrTouching(a, b) ↔ distance(a, b, [–∞, ϵ])
Figure 4. Axioms defining qualitative relations between time points in the preferred approach, where all time units are treated as
intervals and we use an infinitesimal (denoted ϵ) to separate points that are (in the limit) “adjacent”
Both approaches use infinity (denoted ∞) to represent the difference between the two approaches’ computational
largest possible distance between time points. Handling this in complexity for constraint propagation is that the preferred
temporal constraint propagation (computing tightest distance approach enables finer (and thus more numerous unique)
bounds, considering all constraints) requires axioms defining constraints.
non-standard arithmetic, as in Figure 5. Figure 6 exhibits Implementation is straightforward for addition and
axioms for the constraint propagation process in which Figure arithmetic negation in a programming language such as Lisp
5’s arithmetic axioms are applied. Note that all but the last of that supports complex numbers and arithmetic. While complex
Figure 5’s axioms handle only the infinities specially. By numbers with unequal real and/or imaginary parts are
treating the positive infinitesimal denoted ϵ as the imaginary incomparable with respect to magnitude, in our imaginary-as-
number i (as in [2][5][6]) and by appealing to complex infinitesimal interpretation the real parts always dominate and
arithmetic, we can use the same axioms to support propagation the imaginary parts are compared only when the real parts are
in both approaches. equal—per the last axiom defining finite>, in which the
Note that in the naïve approach using only real numbers all predicates real>, real=, and imaginary> invoke the indicated
the imaginary parts will be zero. The only substantive comparisons on the real and imaginary parts of their arguments.
infinite(–∞)
infinite(∞)
infinite+(–∞, –∞, –∞)
infinite+(∞, ∞, ∞)
infinite+(a, –∞, –∞) ← ¬infinite(a)
infinite+(–∞, b, –∞) ←¬infinite(b)
infinite+(a, ∞, ∞)← ¬infinite(a)
infinite+(∞, b, ∞) ← ¬infinite(b)
infinite+(a, b, a + b) ← ¬infinite(a) ˄ ¬infinite(b)
infinite–(–∞, ∞)
infinite–(∞, –∞)
infinite–(a, –a) ← ¬infinite(a)
infinite>(∞, –∞)
infinite>(a, –∞) ← ¬infinite(a)
infinite>(∞, b) ← ¬infinite(b)
infinite>(a, b) ← ¬infinite(a) ˄ ¬infinite(b) ˄ finite>(a, b)
finite>(a, b) ← real>(a, b) ˅ (real=(a, b) ˄ imaginary>(a, b))
Figure 5. Axioms supporting constraint propagation arithmetic (addition, subtraction, and comparison) over temporal duration
bounds of infinite extent
distance(b, a, [–y, –x]) ↔ distance(a, b, [x, y]) ˄ infinite–(x, –x) ˄ infinite–(y, –y)
distance(a, b, [w, y]) ← distance(a, b, [x, y]) ˄ distance(a, b, [w, z]) ˄ infinite>(w, x)
distance(a, b, [x, z]) ← distance(a, b, [x, y]) ˄ distance(a, b, [w, z]) ˄ infinite>(y, z)
distance(a, c, [mo, np]) ← distance(a, b, [m, n]) ˄ distance(b, c, [o, p]) ˄ infinite+(m, o, mo) ˄ infinite+(n, p, np)
Figure 6. Axioms for propagating lower and upper temporal bounds to infer tightest bounds considering all constraints
[6, 8]
[1, 1]
[6–2ϵ, 7+ϵ]
[2ϵ, 1–ϵ]
[ϵ, 1–2ϵ] [ϵ, 1–2ϵ] [ϵ, 1–2ϵ]
[ϵ, ∞] [ϵ, ∞] [ϵ, ∞] [5, 7]
Day 1 A B Day 2 C
Figure 7. Raw (solid arrow) and inferred/propagated (dashed arrow) constraints, with lower and upper bounds, in the preferred
approach. Constraints have directions indicated by arrows (all oriented from left to right)
A to Day 2, as well as many inferred constraints relating pairs
V. HOW THE PREFERRED APPROACH AVOIDS ANOMALIES of points not connected in the figure. The two-dimensional (in
To see how constraint propagation works—and avoids the implementation, complex) arithmetic treating infinitesimal
anomalies—in the preferred approach, see Figure 7, which and non-infinitesimal quantities orthogonally effectively
supposes days are our finest time unit. maintains qualitative point ordering—both within finest
represented calendar or clock unit boundaries (e.g., relating
By way of raw constraints, we know that points A and B points A and B) and across them (relating B and C). See
both fall between Day 1 and Day 2, that A follows B, and that Figure 8.
point C is between five and seven days after Day 2. For clarity,
Figure 7 omits the [ϵ, ∞] constraint from Day 1 to B and from
[6–2ϵ, 8–2ϵ]
ϵ ϵ 1–2ϵ [5, 7]
Day 1 A B Day 2 C
[5+ϵ, 7+ϵ]
ϵ 1–2ϵ ϵ [5, 7]
Day 1 A B Day 2 C
[5+ϵ, 7+ϵ]
1–2ϵ ϵ ϵ [5, 7]
Day 1 A B Day 2 C
Figure 8. Extreme cases for the time points A and B in Figure 7, including (at the extremes) greatest lower and least upper
bounds in the inferred constraints shown there
As we explained in section III, resolving this time point
ordering anomaly simultaneously resolves the other three REFERENCES
anomalies described there as well. Now, we also can order the [1] J. Allen, “Maintaining knowledge about temporal intervals,” in
events that occur at time points and avoid spurious Communications of the ACM. 26, pp. 832–843, November 1983.
contradictions that arise from the naïve approach’s inability to [2] T. Dean and D. McDermott, “Temporal data base management,”
order events and fluent observations. When our finest time Artificial Intelligence, vol. 32, pp. 1–55, 1987.
units are days, we no longer have to pretend that all events [3] International Standards Organization, “Data elements and
occur at the stroke of midnight. With appropriate ordering of interchange formats—information interchange—representation of
events, we’ll be able to put machine reading in a better position dates and times,” international standard ISO 8601:2004(E), third
to support commonsense understanding of causality. edition, 2004.
[4] J. Hobbs and F. Pan, “An ontology of time for the semantic web,”
VI. SUMMARY ACM Transactions on Asian Language Information Processing,
We have demonstrated temporal reasoning anomalies that Vol. 3, No. 1, pp. 66–85, March 2004.
arise when implementation of the event calculus naively [5] R. Schrag, J. Carciofini, and M. Boddy, “Beta-TMM Manual
follows classical treatments that casually treat finest (version b19),” Technical Report CS-R92-012, Honeywell SRC,
represented calendar or clock time intervals as “points.” We 1992.
have presented axioms and described implementation [6] R. Schrag, M. Boddy, and J. Carciofini. “Managing disjunction
techniques to resolve these anomalies when all time intervals for practical temporal reasoning,” in Principles of Knowledge
are correctly treated as time intervals and when time points are Representation and Reasoning: Proceedings of the Third
taken to be instants with zero real-world duration extent. We International Conference (KR-92), pp 36–46, 1992.
argue that this preferred approach, rather than the naïve one, is [7] R. Schrag, “Exploiting inference to improve temporal RDF
needed for the event calculus to be useful in applications, like annotations and queries for machine reading,” 7th International
machine reading, intended to support commonsense Conference on Semantic Technologies for Intelligence, Defense,
understanding including causality. and Security (STIDS), 2012.
[8] M. Shanahan, “The event calculus explained,” in Artificial
ACKNOWLEDGMENT Intelligence Today, ed. M. Wooldridge and M. Veloso, Springer
Lecture Notes in Artificial Intelligence no. 1600, pp.409–430,
Thanks to other participants in DARPA’s Machine Reading 1999.
research program that supported our temporal reasoning
implementation—especially to other members of the SAIC APPENDIX: TIME POINT AND INTERVAL RELATIONS
evaluation team, including Global InfoTek (the author’s former The set of predicates illustrated in Figure 9 (repeated from
employer). Figure 4) supports every qualitative binary time point relation
over the time point distance landmark values indicating
equality, adjacency, and lack of constraint above or below. (A
user also may specify arbitrary bounds on the number of time
units intervening between any two points.) As illustrated in
Figure 10 selected examples, this point orientation yields a
much broader set of qualitative interval relations than does
Allen’s classical formalism [1], which is purely interval
oriented, without points.
[lower, upper] bounds on the calendar or clock distance (in the
preferred approach) from time point S to time point O
Subject on top timePointEqualTo(S,O) [0, 0] marked
Object on bottom
timePointLessThan(S,O) [ϵ, ∞] time points may
not coincide.
timePointGreaterThan(S,O) [−∞, −ϵ]
timePointLessThanOrEqualTo(S,O) [0, ∞] , marked
time points are
timePointGreaterThanOrEqualTo(S,O) [−∞, 0]
consecutive.
hasNextTimePoint(S,O) , [ϵ, ϵ]
hasPreviousTimePoint(S,O) ‘ [−ϵ, −ϵ] ∞ = Infinite
‘ duration
timePointTouches(S,O) ‘ [−ϵ, ϵ]
timePointLessThanOrTouching ‘ [−ϵ, ∞] ϵ = Infinitesimal
timePointGreaterThanOrTouching
‘
[−∞, ϵ] duration
pointInInterval
pointIsInterval
Figure 9. Qualitative relations over time points, with graphical icons that we use to illustrate the definitions of point-and-interval
relations (here) and interval-interval relations (in Figure 10). Such illustrated definitions include beginning and ending points
super-imposed on interval icons, to elucidate the constraints.
hasSubTimeInterval(S,O)
timeIntervalBefore(S,O)
timeIntervalStarts-X(S,O)
timeIntervalFinishedBy(S,O)
timeIntervalMeets-X(S,O)
,
timeIntervalOverlaps(S,O)
timeIntervalEquals(S,O)
timeIntervalIntersects(S,O)
‘
‘
‘ timeIntervalTouches(S,O)
‘
Figure 10. Selected relations over time intervals (with defined time point relations indicated)