The ORM Foundation

Get the facts!

Modeling intransitivity

Last post Thu, Apr 7 2011 10:16 by JackStoneS. 2 replies.
Page 1 of 1 (3 items)
Sort Posts: Previous Next
  • Wed, Apr 6 2011 3:42

    Modeling intransitivity

    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?
  • Wed, Apr 6 2011 18:23 In reply to

    Re: Modeling intransitivity

    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.



  • Thu, Apr 7 2011 10:16 In reply to

    Re: Modeling intransitivity

    That clarifies a lot. Thank you!
Page 1 of 1 (3 items)
© 2008-2015 The ORM Foundation: A UK not-for-profit organisation -------------- Terms of Service