1 Reply Latest reply on Aug 11, 2011 9:56 AM by philmodjunk

    Single Table Tree Structure Database - Recursive Search

    AnthonyWolfenden

      Title

      Single Table Tree Structure Database - Recursive Search

      Post

      Started with a Single Table Tree Structure Database.
      Every record has a unique ID and a Parent ID.
      The Parent ID always matches some other records unique ID
      A record can have multiple other records that record it as parent.
      A record can only have a single parent.
      The root record has a Parent ID that matches it's own unique ID (or zero if you like)

      Given any records ID I need to be able to search up through the tree to find the first parent record or parents parent record etc that has a characteristic field = "Diamond". If not found I need to be able to return the root record.

      Given the same ID I need to be able to provide a list of all the children, childrens children etc of the given record ordered by name or ID.

      These two functions would be used to display for any given record...

      1. Its "diamond" parent and

      2. A list of it's children.

      Both functions would seem to require recursion but this is a little beyond me.

        • 1. Re: Single Table Tree Structure Database - Recursive Search
          philmodjunk

          Traversing a Tree Data structure often requires conversion. However, in this case, we can actually traverse from child to ultimate ancestor in a pretty simple loop.

          Define these self Join Relationship:

          Tree::ParentID = Parent::ID  
          ParentID::gFamily = Family::ID

          Parent is a second occurrence of Tree. You can create this by selecting Tree, then clicking the button with 2 green plus signs. The new occurence will be named Tree 2, but you can double click it to bring up a dialog where you can rename it to "Parent". Use the same method to create an occurrence for Family. gFamily is a global text field for listing the ID's of a given record's "family".

          The Following Loop will traverse from Child to Root:

          Loop
             Exit Loop If [ IsEmpty ( Tree::ParentID ) ]
             Go To Related Record [Show only related records; From table: Parent; Using layout: <Current Layout>]
          End Loop

          Say this script is labeled "List Children":

          #Script must be performed from a layout to "Parent", not "Tree"
          If [ Not IsEmpty ( Tree::ParentID ) //If ID fields are number, just use Tree::ParentID ]
             Set Variable [$Children ; List ( Tree::ID ) //make a list of all the children ]
             Loop
                Set Variable [$I ; value: $I + 1 ]
                Enter Find Mode []
                Set Field [Parent::ID ; Get Value ($Children ; $I ) ]
                Perform Find []
                Perform Script ["List Children"] //recursive call to same script
                Set Variable [$GrandChildren ; value: List ( $GrandChildren ; Get ( ScriptResult ) )]
                Exit Loop If [ $I = ValueCount ( $Children ) ]
             End Loop
             Exit Script [List ( $Children ; $GrandChildren ) ]
          End If

          Use this script to produce a found set of the current record's children:

          Perform Script ["List Children"]
          Set Field [Parent::gFamily ; Get ( ScriptResult )]
          Go To Related Record [Show only related records; From table: Family ; Using layout: <Current Layout>]
          #At this point you can sort the records in any order and on any field that you choose with a sort Records step.