The ORM Foundation

In the BBB, the definition of intransitivity is the following: (see p284)
R is intransitive, iff for all x,y,z xRy & yRz -> ~xRz.

An example of an intransitive relation is 'is a parent of'.

Now, given the following model:

Person(.firstname) is a parent of Person
With a spanning uniqueness constraint on the fact type
And an intransitive constraint on the middle of the fact type

I would say that the following population is allowed in the model:
Ann     Bill
Bill      Colin
Colin  Dirk
Ann     Dirk
Is there a way to specify the model so that the last entry is disallowed?

Hi Jack

You are correct in that an intransitivity constraint is too weak to block the data example you cite. Many years ago, Peter Ritson and I formalized a stronger version of intransitivity, which we called an intransitive-jump constraint (ITJ), which would handle such cases. This is designed to block jumps over one or more nodes, so includes intransitivity as a special case (jumping over one node only). This is discussed on page 3-19 of Peter's PhD thesis.

In DatalogLB, you can enforce it by first recursively deriving the isAncestorOf predicate as the transitive closure of the base isParentOf predicate, thus

          isAncestorOf(x,y) <- isParentOf(x,y) ; isParentOf(x,z), isAncestorOf(z,y).

and then applying the following further constraint

          isParentOf(x,y), isAncestorOf(y,z) -> !isParentOf(x,z).

 Here "<-", ";", "," and "!" denote "if", "or", "and" and "not" respectively.

You can also encode it in SQL using recursive union, but it's much longer and there you also need to add checks for nulls.

When I added ring constraints to ORM many years ago, some people complained that the graphical language was too rich, so I didn't include a graphical version of the intransitive jump constraint. However, in practice I've found that most cases of intransitivity are also cases of jump intransitivity, so I'm now considering adding that constraint explicitly to the ORM graphical notation.

Cheers

Terry

That clarifies a lot. Thank you!