Hierarchical Data, Self Referencing Tables, and Recursion Part 2 (1 Viewer)

[MajP]

This is part two to this thread.

Hierarchical Data, Recursion, Tree-Views, and a Custom Class to Assist

I have had some people ask questions on working with Hierarchical data and Tree Views, which often involves using recursion. If not familiar with recursion this is where a procedure repeatedly calls itself until hitting a condition where it is told to stop. This is used often where you have to...

www.access-programmers.co.uk

However the original thread dealt more specifically with tree views. This does not.
The above threads has many links to other treeview and recursion demos.

The example used in this thread started from the below thread.

link record to another record in the same table

Two things 1. rsProcessed!RoyaltyAgent_ID_FK = DLookup("agentPK", "tblAgents", "AgentName = 'Capital'") This line needs to have the correct name of the Main Agency. If the main agency is Captial1 then this has to match. They do not currently match 2. The rule is that if the inactive date is...

www.access-programmers.co.uk

1. Self Referencing Table. A self referencing tables is a table that has both Parent and Child records in the same table. So each record has a foreign key storing the Parent ID. This is mostly associated with Hierrachical data where the depth of the levels is unknown. This can be used to model Systems and Subsystems, People (or animal) Genealogy, File structures, etc.
The below table shows Sales Agents and who they report to. At the highest level you have some options on how to model this. I always have the top level parent (reportsTo) report to no one. I leave this field null. You can have them report to themselves. Either will work and support referential integrity. See discussion here

Reflexive table and the usual message : You can not add or change record because...

Hello. I have to model a stable, and so stallions, which belong to an owner at a date t etc ... so far so good. Except that the person responsible imposes that only Stallions - not mare, why? I know it's weird, but do not ask me why, this is so - have to be modeled, and so have only one father...

www.access-programmers.co.uk

tblAgents tblAgents

AgentPK	AgentName	ReportsTo
1​	Allen	​
3​	Charlie	​
4​	Debbie	13​
5​	Earl	13​
6​	Fred	1​
7​	Gary	1​
13​	Bethany	​
15​	Harry	3​
16​	Ingrid	6​
17​	James	16​

Notice that at the top level Allen, Charlie, and Bethany report to no one.

2. Self Referencing tables make working with hierarchical data very easy to add, edit, and delete. However, this structure is hard to pull out results and display information. To get information out requires recursion. Using recursion and persisting information to a table allows one to show this information in a logical way with or without a tree view.
qryAgentTree qryAgentTree

Agent	Level	Tree Sort
Allen	0​	1​
----Fred	1​	2​
--------Ingrid	2​	3​
------------James	3​	4​
----Gary	1​	5​
Bethany	0​	6​
----Debbie	1​	7​
----Earl	1​	8​
Charlie	0​	9​
----Harry	1​	10​

Once the Level and Tree sort are calculated the 1st column can be made. ( Specifically once the level is calculated the query can put in the correct number of dashes, once the tree sort is calculated the query is sorted properly)

3. Referential Integrity. You can in fact even enforce referential integrity to include cascade deletes and cascade updates.

4. Recursing a Recordset. When working with selfrefencing data in an Access table you need to know how to recurse a recordset and span all the records in hierarchical order. You can use that to populate a tree view or sum/calculate values over a branch. For example you can calculate the number of documents in a folder to include all subfolders. Calculate the number of descedants for a given person in a family tree.

I found to make working with this data much easier is to recurse the data and then store two values. The level at which an item resides and the order that item would appear in a tree if read from top down. I added these to the table.

Public Sub RecurseLevels(Optional ParentID As Variant = -1, Optional RS As dao.Recordset = Nothing, Optional Level As Integer = 0, Optional TreeSort As Integer = 0)
  'This assigns the levels and tree sort
  'if the top level parent ID is null do not pass in anything
 
  Dim strCriteria As String
  Dim bk As String
  
  If RS Is Nothing Then
    'On the first call to the method open a recordset then pass it in recursion
    Dim strSql As String
    strSql = "Select * from tblAgents order by AgentName"
    Set RS = CurrentDb.OpenRecordset(strSql, dbOpenDynaset)
    If ParentID = -1 Then
      'in this example our top level parent is null
      strCriteria = "ReportsTo is Null"
      'If not null then simply
      'strCriteria = "ReportsTo = " & parentID
      RS.FindFirst (strCriteria)
      If RS.NoMatch Then
         MsgBox "There is no record with a Parent ID of " & ParentID
         Exit Sub
      End If
    End If
    
  Else
    'all other calls you pass in the parentID
    strCriteria = "ReportsTo = " & ParentID
  End If
  
  RS.FindFirst (strCriteria)

  Do Until RS.NoMatch
   bk = RS.Bookmark
   'The tree sort gets updated on every record
   TreeSort = TreeSort + 1
   RS.Edit
     RS!AgentLevel = Level
     RS!TreeSort = TreeSort
    RS.Update
     'The current Record is passed as the parent. The level only gets updated on a recursive call
     RecurseLevels RS!AgentPK, RS, Level + 1, TreeSort
     RS.Bookmark = bk
     RS.FindNext (strCriteria)
  Loop
End Sub

In this recursion each call passes in a potential parent, starts to read through the child records, and at each child it then calls itself.
In the first pass it loops all records whose ReportTo is Null. It reaches the first record Allen, and then calls itself passing Allen as the parent. Then it loops all records whose parent is allen. It loops to fred then calls itself passing in fred. Then begins to loop all records whose parent is Fred....

All of those loops are still open until it gets out to James. Since it cannot go any further each open call begins to end and it works itself backwards. Once it works back to the call where Parent was Allen it reads Gary.

I see lots of bad versions of recursive recordsets. Often the code is written to open a new recordset on each call to the procedure. This can be extremely slow and eat up a lot of resources. This version opens a recordset on the first call and passes a reference to the recordset on subsequent calls. Storing the BK is important prior to making a recursive call. As the code works it ways back up the branch the code needs to know where it left off before the recursive call.

 

[MajP]

Continued due to Length

5. Descendant Tree. The next trick I found to doing any calculations easily is to build a "Descendant Tree". This table hold Every record and all of its descendants. This uses a similar recursive code.
tblAgentDescendants tblAgentDescendants

SalesTreeID	AgentID	AgentLevel	DescendantID	DescendantLevel
3327​	1​	0​	1​	0​
3328​	1​	0​	6​	1​
3329​	1​	0​	16​	2​
3330​	1​	0​	17​	3​
3331​	1​	0​	7​	1​
3332​	3​	0​	3​	0​
3333​	3​	0​	15​	1​
3334​	13​	0​	13​	0​
3335​	13​	0​	4​	1​
3336​	13​	0​	5​	1​
3337​	4​	1​	4​	1​
3338​	5​	1​	5​	1​
3339​	6​	1​	6​	1​
3340​	6​	1​	16​	2​
3341​	6​	1​	17​	3​
3342​	7​	1​	7​	1​
3343​	15​	1​	15​	1​
3344​	16​	2​	16​	2​
3345​	16​	2​	17​	3​
3346​	17​	3​	17​	3​

With this table very complicated rollup calculations are easy. For example for Agent 1 records 6,16,17, and 7 are all descendants at various levels. If the descendants had related records then they could be rolled up to the parent 1. If agent 1 represented a System instead, then the descendant records would represent a parts list for all levels.

The demo allows you to add, edit, and delete Agents and it calculates the Level, Tree Sort, and Descendent Tree.

 

[MajP]

To demonstrate the use of the "Descendant Tree" for calculating rollups I Included the ability for agents to make sales and then show the roll up of sales to the top of the branch (right subform). Once the descendant tree is made this is a trivial query.

 

[MarkK]

Here's how I've been driving data into treeviews lately. Riffing off what you wrote, above, I've made a cAgent class, which has an object reference to its 'ReportsTo' parent agent, and a collection of 'descendent' agents. Once that in-memory hierarchy is created, creating the tree is simple.

Here's a quick and dirty sample..

This sample also shows how to implement an interface in VBA.

 

[json5545]

@MajP can you elaborate on what is happening between the subs UpdateDescendants and UpdateAgentdescendants?
UpdateAgentdescendants seems redundant. I commented out the line in the sub UpdateDescendants that calls UpdateAgentdescendants and it seemed to work just fine.

Public Sub UpdateAgentdescendants(AgentID As Long, StartingAgentID As Long)
  Dim RS As dao.Recordset
  Dim strSql As String
  strSql = "Select * from tblAgents where ReportsTo = " & AgentID
  Set RS = CurrentDb.OpenRecordset(strSql)
  Do While Not RS.EOF
      AgentID = RS!AgentPK
      strSql = "Insert INTO tblAgentdescendants (AgentID, descendantID, AgentLevel, descendantLevel) VALUES (" & StartingAgentID & ", " & AgentID & ", " & GetStoredLevel(StartingAgentID) & ", " & GetStoredLevel(AgentID) & ")"
      Debug.Print strSql
      CurrentDb.Execute strSql
      'UpdateAgentdescendants AgentID, StartingAgentID
      RS.MoveNext
  Loop
End Sub

 

[MajP]

I commented out the line in the sub UpdateDescendants that calls UpdateAgentdescendants and it seemed to work just fine.

No it definitely did not work. The "tree" works, but the desendant table will not work. If you read the note above the code it says that

'This is another recursion but instead of doing this all at once I use the results from the first recursion. However this could all be done at once

The code to work in a single procedure would have to be completely rewritten similar to the code for doing the levels.

UpdateDescendants loops all the records and kick it off. It makes a pass through the recordset. The Sql is different and the insert is different since it assigns the parent ID as being the same as the agent id. For each Agent it then recurses the descendants. Without a very long explanation I find it easier to loop the base level in one procedure and then use that to call the recursion for each record. Combining this into one procedure is a little more difficult to see how it works. What often happens is that you read the first record and get all of its children then, you get stuck at the first record.

But if you look there is a very big difference from the techniques to finding the levels. In that case it open the RS once. In the Descendant method it opens a local RS for each call (less efficient but easier to follow).

 

[json5545]

I re-ran it through multiple levels and I see what you mean now. Ignoring the second loop only captures the child, but not the grandchildren and so on after that.

Thank you for doing this. I've been looking for a simple solution to this very problem for some time now. What I'm currently doing for my database follows much of the same logic as what you put together, but I'm doing it with UNION queries and with more steps. Your solution is way more efficient and I don't have limits on the number of levels. Thanks!