When SWRL Rules Are Valid but Wrong: Lessons from Implementing Allen's Interval Algebra

I like to write about mistakes I've made and what I learned from them. If I make a mistake, chances are other people may too. Recently, I revisited an ontology I developed several years ago that uses SWRL (Semantic Web Rule Language) to implement Allen's Interval Algebra using the W3C Time Ontology [5]. In reviewing and testing the rules, I discovered several errors and weaknesses in the original implementation.

What makes these mistakes interesting is they illustrate general issues involving identity versus equality, the distinction between logical correctness and implementation correctness, and the need for systematic testing that goes beyond getting the reasoner to run with no errors.

Background: Allen's Interval Algebra

Allen's Interval Algebra is a formal model for reasoning about temporal intervals, originally developed by James Allen in 1983 [1] [2]. It defines thirteen fundamental relations between two intervals.

For example, consider two intervals representing historical events. The Battle of Gettysburg occurred during the American Civil War, so we can say that the interval representing Gettysburg is during the interval representing the Civil War.

Other relations include before, meets, overlaps, starts, finishes, and equals, together with their inverses. The important thing about Allen's model is that these thirteen relations are mutually exclusive and collectively exhaustive for pairs of proper intervals over a linear time ordering. Given two such intervals, exactly one of the thirteen relations holds.

The W3C Time Ontology [3] and the Basic Formal Ontology (BFO) [5], [6] provide a standard vocabulary for representing temporal entities, including intervals, instants, and their relationships. However, merely defining those relationships in OWL doesn't provide all the computational machinery needed to infer them from the timestamps of two intervals.

That's where SWRL [4] comes in. SWRL allows us to define rules that infer new facts from existing facts. For example, if interval A ends before interval B begins, we can infer that A is before B.

Before we get into implementation details, one other interesting fact about the Allen Intervals: they define a partition of the set of all valid time intervals. A partition (P) of a set (S) is a set of relations (R) such that: For any two elements of S, S1 and S2, for exactly one of the relations R (call that Rx) it is the case that S1 Rx S2.

More formally, a relation R is a partition of S if it is:

1. Jointly exhaustive: Every pair of proper elements of S (in our case valid time intervals) satisfies at least one relation R.

2. Pairwise disjoint (mutually exclusive): No pair of elements in S satisfies more than one relation R.

I.e., any two valid time intervals (in the W3C Time Ontology this is the class time:ProperInterval) are always related by exactly one of the Allen intervals (modeled as object properties). This is an example of how understanding the basics of set theory and logic go a long way to understanding OWL. So much for the theory, now for the implementation issues:

Mistake 1: Confusing identity with equality

This was probably the most interesting problem because it illustrates a fundamental distinction in knowledge representation. In the W3C Time Ontology, an interval can have a beginning instant and an ending instant. Those instants can, in turn, have timestamps.

Suppose we have two intervals:

• Interval A begins at 9:00am and ends at 10:00am.

• Interval B begins at 10:00am and ends at 11:00am.

According to Allen's algebra, A meets B.

Now suppose we represent the ending instant of A and the beginning instant of B as two different OWL individuals. Both individuals have the same timestamp, 10:00am, but they have different identifiers. An implementation that requires the two intervals to share the same instant individual will fail to recognize that A meets B. The problem is that identity of individuals is not the same thing as equality of their timestamp values.

This is particularly important in OWL, where two differently named individuals are not automatically assumed to be different, and sharing a data-property value doesn't automatically establish that two individuals are identical.

The solution

Rather than relying on the identity of instant individuals as I did originally, the corrected rules compare their timestamp values. For example, the essential condition for the meets relation is:

`end(A) = begin(B)`

In SWRL, we can implement that comparison using `swrlb:equal` on the timestamp values.

The essential fragment is:

time:hasEnd(?a, ?endA) ^
time:hasBeginning(?b, ?beginB) ^
time:inXSDDateTimeStamp(?endA, ?t1) ^
time:inXSDDateTimeStamp(?beginB, ?t2) ^
swrlb:equal(?t1, ?t2)

The complete rule also includes conditions establishing that the intervals are valid, and concludes:

time:intervalMeets(?a, ?b)

This approach correctly handles two separately represented instants that denote the same point in time. It also allows comparisons of timestamps with different timezone offsets that represent the same instant, provided the values are interpreted using the appropriate datatype semantics.

General lesson: Don't Confuse Identity with Equality

When modeling relationships, distinguish carefully between the identity of entities and the equality of their properties. These are different logical concepts, even when they often coincide in a particular dataset.

Mistake 2: Inferring the wrong kind of relationship

Another error was more mundane but equally instructive. In the original implementation, one of the rules intended to establish an Allen before relationship between intervals instead generated a before relationship between their endpoint instants. Conceptually, the intended rule was:

IF end(A) < begin(B) THEN intervalBefore(A, B)

But the implementation produced an instant-level relationship instead.

This is a particularly dangerous kind of mistake because the inferred relationship may be perfectly reasonable in isolation. If the ending instant of A precedes the beginning instant of B, then a relationship between those instants can be correct. The problem is that it isn't the relationship we wanted the rule to infer. The rule may execute successfully, and the reasoner may report no inconsistencies. Nevertheless, the intended interval relationship is missing.

The solution

The corrected rule compares the endpoint timestamps and asserts the relationship between the intervals themselves. The essential SWRL fragment is:

time:hasEnd(?a, ?endA) ^ time:hasBeginning(?b, ?beginB) ^
time:inXSDDateTimeStamp(?endA, ?t1) ^ 
time:inXSDDateTimeStamp(?beginB, ?t2) ^ swrlb:lessThan(?t1, ?t2) -> 
time:intervalBefore(?a, ?b)

This also simplifies the implementation. Instead of generating intermediate instant-to-instant relationships and relying on additional rules to derive interval relationships, we can directly infer the intended Allen relation.

Of course, there are situations where explicitly representing relationships between instants is useful. The mistake wasn't using such relationships; it was generating them when the intended result was a relationship between intervals.

General lesson: More to Testing than Running the Reasoner

This brings us to what I think is the most generalizable lesson. One of the reasons these errors persisted is that the ontology was syntactically valid and the rules could be processed by a reasoner. But a reasoner doesn't know what the ontology developer intended.

It can determine whether particular conclusions follow from the axioms and rules it has been given. It cannot independently determine whether those rules faithfully implement Allen's Interval Algebra.

This is analogous to conventional programming. A program can compile successfully, run without exceptions, and still produce incorrect results. The same applies to declarative rules and ontologies. This is also an example of something I often say although not everyone in the ontology community agrees: a complete ontology requires ABox data to be rigorously tested. These errors would never have been found by just examining the rules and running the reasoner on TBox entities alone.

The solution: systematic testing

Rather than testing a few hand-picked examples as in the original ontology, we constructed a systematic test of the Allen relations. The test included 22 intervals, giving: 22 × 22 = 484 ordered interval pairs. For each pair, we computed the expected Allen relation directly from its beginning and ending timestamps, then compared that result with the relationships inferred by the SWRL implementation.

The tests covered all thirteen Allen relations, including equality, as well as cases involving distinct instant individuals and equivalent timestamps. We also tested problematic inputs, including zero-duration intervals, reversed intervals, and intervals with missing endpoint information. The corrected implementation passed all 484 ordered-pair checks. The invalid and incomplete interval cases did not generate inappropriate Allen inferences.

The important thing here is that the expected results were calculated independently of the SWRL rules. Otherwise, we could have reproduced the same conceptual error in both the implementation and the tests.

This is especially important when testing formal systems. Tests based on the same assumptions and implementation decisions as the system being tested may simply confirm those assumptions, including the mistaken ones. What's more, formal concepts such as partitions can help us understand and automate the generation of test data.

A broader point about OWL and rules

There is another interesting issue underlying all these examples. OWL, SWRL, and Allen's Interval Algebra play different roles. Allen's algebra defines the intended temporal relationships and their mathematical properties. OWL provides a language for representing temporal entities, their properties, and logical axioms. SWRL provides a mechanism for deriving relationships from information already represented in the ontology.

These layers are related, but they aren't interchangeable.

An OWL ontology such as BFO or W3C Time may have a good model but without some way to implement the appropriate logic such ontologies are only partial models of domains such as time. Similarly, a SWRL rule can produce a valid inference under its own conditions while failing to capture the intended meaning of a relationship. And even when individual rules are correct, the overall implementation may be incomplete.

For example, Allen's algebra supports reasoning about compositions of interval relations. If A is before B and B is before C, we can infer that A is before C. Our timestamp-based rules address a particular problem: determining interval relationships from known endpoints. That is not the same as implementing every aspect of Allen's algebra, such as general constraint propagation over incompletely specified intervals. Keeping these distinctions clear is important when evaluating what an ontology and its reasoning system actually accomplish.

Conclusion

Revisiting this implementation reminded me of something that is easy to forget when working with formal systems: mathematical precision doesn't automatically guarantee implementation correctness, but it often provides obvious clues as to what needs to bested above and beyond what the reasoner validates.

The original rules were based on a well-established mathematical model and expressed in a formal rule language. Nevertheless, they contained errors that weren't obvious from simply running a reasoner.

The corrections were relatively straightforward once the problems were identified.

The more important lessons were about how to avoid similar problems in the future:

1. Consider the complete logical model required to define the problem and realize that may require more than just an OWL ontology. It may require SWRL, SHACL, or other tools to implement the logic of a model.

2. Distinguish identity from equality, especially when working with entities that represent values or measurements.

3. Verify that inferred relationships have the intended subjects, objects, and semantics. Utilize logical relations such as partitions to guide testing.

4. Test formal implementations against independently derived expected results, rather than relying solely on successful execution.

None of these lessons is specific to SWRL, OWL, or even knowledge graphs. They apply just as well to conventional software, database constraints, business rules, and other systems intended to implement formal models. One of the advantages of knowledge representation languages is that they make semantics explicit. But that advantage only pays off if we verify that the semantics we've implemented are actually the ones we intended.

References

1. Allen, James F. (1983). *Maintaining Knowledge about Temporal Intervals.* Communications of the ACM, 26(11), 832–843.

2. Allens Interval Algebra on Wikipedia

3. W3C. Time Ontology in OWL. https://www.w3.org/TR/owl-time/

4. W3C. SWRL: A Semantic Web Rule Language Combining OWL and RuleML. https://www.w3.org/Submission/SWRL/

5. DeBellis, Michael. W3C Time Ontology With SWRL Rules to Implement Allen Interval Algebra. https://github.com/mdebellis/Time-Ontology-With-SWRL-Rules

6. R. Arp, B. Smith and A. D. Spear, Building Ontologies with Basic Formal Ontology, Cambridge, MA, USA: MIT Press, 2015.