Building Parsers with Java™

13.11. Modeling Transitive and Symmetric Relations

A transitive relation is a relation such as “taller,” where a pair of relations can imply a third relation. For example, if Alan is taller than Britta, and Britta is taller than Chuck, then Alan is taller than Chuck. This kind of relation differs from, say, “owes a favor to,” which is not transitive. If Alan owes Britta and Britta owes Chuck, Alan may or may not owe Chuck. The “owes a favor to” relation is not transitive.

A common transitive relation is “in.” If A is in B and B is in C, then A is in C. This is true, for example, of boxes and geographical places. It is tempting to write, for transitive relations, a rule such as the following:

in(A, C) :- in(A, B), in(B, C); // wrong 

If this ...