eyeprolog

Allen’s interval calculus

How do two time intervals relate?

Two intervals of time can relate in exactly thirteen ways: one is before the other, meets it, overlaps it, starts it, and so on. James Allen’s 1983 interval calculus names them. This example derives every relation between eleven intervals from their start and end hours.

Run it in the playground · Source

The question

Given eleven intervals on a day, each with a start and end hour, which of Allen’s relations hold between each pair?

Scheduling, logistics, and medical timelines all ask this question: did the treatment start during the episode, does one shift meet the next, are two meetings equal?

The data as one table

interval_table([
  interval(a, 10, 12),
  interval(b, 13, 15),
  interval(c, 12, 14),
  interval(d, 11, 13),
  interval(e, 10, 12),
  interval(f, 10, 11),
  interval(g, 11, 12),
  interval(h, 9, 16),
  interval(i, 16, 18),
  interval(j, 15, 16),
  interval(k, 13, 14)
]).

start(I, Start) :- interval_table(Table), member(interval(I, Start, _end), Table).
end(I, End) :- interval_table(Table), member(interval(I, _start, End), Table).

The intervals are one term, a list of records, rather than many unrelated global facts. start/2 and end/2 read fields out of it.

Seven relations and their inverses

relation(I, before, J) :- end(I, Ei), start(J, Sj), (Ei < Sj).
relation(I, meets, J) :- end(I, E), start(J, E).
relation(I, starts, J) :-
  start(I, S), start(J, S),
  end(I, Ei), end(J, Ej),
  (Ei < Ej).
relation(I, equals, J) :-
  start(I, S), start(J, S),
  end(I, E), end(J, E).

relation(J, after, I) :- relation(I, before, J).
relation(J, metBy, I) :- relation(I, meets, J).

Each relation is a comparison of endpoints. The six inverse relations (after, metBy, overlappedBy, startedBy, contains, finishedBy) are defined from the forward ones, so no comparison is written twice. overlaps, during, and finishes follow the same pattern.

The answer

eyeprolog examples/allen-interval-calculus.pl

statement(a, before, b).
statement(a, meets, c).
statement(a, equals, e).
statement(f, meets, g).
statement(f, starts, a).
statement(g, finishes, a).
statement(h, contains, a).

A selection from 154 answers: 11 starts, 11 ends, 11 durations, and 121 relation statements. Interval a (10–12) meets c (12–14), equals e, is started by f (10–11), finished by g (11–12), and lies during h (9–16).

The reason

eyeprolog --proof examples/allen-interval-calculus.pl

step(relation(f, starts, a),
     rule(8),
     ['I' = f, 'J' = a, 'S' = 10, 'Ei' = 11, 'Ej' = 12],
     [start(f, 10), start(a, 10), end(f, 11), end(a, 12), 11 < 12]).

Interval f starts a because both start at 10 (S = 10) and f ends first, at 11 against 12. Each endpoint fact is in turn read from the table through a member/2 built-in step.

The check

condition('C1', resolution, ok, 276).
condition('C5', re_decision, ok, 40).
condition('C7', relevance, ok, 470).
recomputed(40).
trusted(0).
claims(154).
verdict(checked).

All 154 claims are covered by 316 steps: 276 checked against the program and 40 built-in steps recomputed by the checker. Nothing is taken on trust.

Try it

Add interval(l, 12, 13) and predict its relations to a, c, and d.
Which of Allen’s thirteen relations never appears for this data? Add an interval that produces it.
Write disjoint(I, J) as “before or after”, and intersects(I, J) as its negation over the known intervals.

Learn more in The Art of EyeProlog, Chapter 9.

This site is open source. Improve this page.