Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

How to model an ordered tree

Anonymous
2012-07-21
2013-05-28

  • Anonymous
    2012-07-21

    Suppose you are trying to model a bunch of trees where the order of the trees and their children matter. You might do something as simple as this…

    (a) Node(id)  is child of 0 or 1 Node
    (b) Node(id) has exactly one SiblingIndex

    My question is how to handle the uniqueness constraint on (b). I can create an external uniqueness constraint that spans Parent and SiblingIndex. This ensures that the within each parent node there are never two children with the same SiblingIndex. But this doesn't work for the root Nodes since those nodes don't have a Parent role. I can think of some solutions…

    (1) Remove the SiblingIndex fact type from Node. Instead create two subtypes of Node called RootNode and ChildNode. On "RootNode has SiblingIndex" create a 1-1 uniqueness constraint. On "ChildNode has SiblingIndex" create an external uniqueness constraint that spans it's parent and its SiblingIndex. This is quite an ugly diagram.

    (2) Create a subtype of Node called RootNode. Add a "RootNode has ChildIndex" fact type that is marked as derived since all nodes have a sibling index. But add a 1-1 uniqueness constraint on this derived fact type. In other words, we're adding a new constraint to the fact type Node has SiblingIndex when Node has no parent.

    (3) Create a derived fact on Node called something like "Node has parent identified by NodeIdText". If the node actually has a parent then NodeIdText will be the ID of the parent. And if the node does not have any parent then NodeIdText is an empty string. Create an external uniqueness constraint that spans the NodeIdText role and SiblingIndex role.