<

Expanding a Hierarchical Data Structure

Published on
43,007 Points
28,807 Views
17 Endorsements
Last Modified:
Awarded
Editor's Choice
Community Pick
Introduction

One of the earliest concepts learned by database developers is parent-child (one-to-many) relationships.  These relationships are integral in countless database applications.  A purchase request containing one or more items ordered is a very common example.  

Child records are identifiable through key fields, such as Purchase Order ID, which link them back to the Parent record.    This relationship can easily be displayed using a main form for top-level purchase order information with a subform to list the items ordered.

This scenario gets a little more complex if any of the child records contain children of their own (i.e.,  grandkids).   This type of data structure is common in engineering and manufacturing, where individual parts can make up sub-assemblies which are pieced together to form some final product.  

For example, a bicycle is a top-level assembly that contains parts such as posts, wheels brakes and more.  Each of these parts can also contain multiple parts.   A wheel is a sub-assembly of the bicycle which  is composed of a rim, tire, spokes etcetera.  These sub-assemblies can further contain component parts and sub-assemblies of their own (e.g.,  hubs, chain rings and bearings).    

The connection between each assembly and its parts can be defined with a one-to-many relationship as described previously with the purchase order example.   A Parts List table is used to store child records for the parts, relating them to parent records with a key field such as Parent Assembly ID.   Going a step further than the Purchase Order example, the ID of any component can in turn appear in the Parent Assembly ID field, which defines that part as an assembly having parts of it's own.    

Identifying all parts in a hierarchical structure like this is a common requirement.  Tracking quantities is also important in many applications, for example to determine how much of each part to order when building a given number of a certain assembly.  A listing of materials, sub-assemblies and their associated quantities is called a Bill of Materials (BOM).  Such a listing can be used when ordering parts needed to build the end product.   Additionally, a numeric Indenture Level  which defines each part's place relative to the top of the structure is useful information.  

For example (Indenture Level in parentheses):

                    -Bicycle (0)
                          - Wheel assembly (1)
                                - Rims (2)
                                - Tires (2)
                                - Hub assembly (2)
                                      - Sprockets (3)
                                      - Derailier (3)
                                      - Etc. (3)
                          - Brake assembly (1)
                                - Pads (2)
                                - Cables (2)
                                - Etc. (2)
                         - Etc (1)

A form/subform combination can easily be used to display a top-level parts list for an assembly, with assembly information shown in the main form and its highest level parts shown in the subform.  However reporting the entire structure from the top down goes beyond the capabilities of subforms or subreports.

To report this type of structure, the data for all parts in the hierarchy needs to be extracted from the database.   This can be accomplished in different ways, via code or query.  One advantage of using a code-based method is that other tasks can be accomplished through code at each iteration as the list is being built.

This article focuses on one Visual Basic-based technique that can be used to extract a top-down listing of assemblies and parts while tracking an indenture level defining each part or assembly's place in the hierarchy.  Extracting this data is what is meant by Expanding a Hierarchical Data Structure, in that each sub-assembly is successively expanded to reveal all of the parts that make up the end product.

The Sample Database
ExpandPartsList.mdb

The attached database is a two-table example with Visual Basic code to extract a top-down listing of the parts in an assembly.  The data included with the sample defines a wheel, with sub-assemblies and parts.  The data is not meant to be realistic; it simply is there for visual example.  The sample form and code allow the user to expand a parts listing for the wheel or for any of the sub-assemblies.  The rest of this article dissects the sample to explain the concepts used.
 

1. The Tables

Design and relationships

One table is used for a general parts repository, containing information pertinent to each part.  For this purpose, even assemblies are considered parts.  Continuing with the bicycle example, the bicycle, wheels and brakes are "parts" that should be included in this table along with the nuts and bolts that are used to build them.  The structure of the parts repository table follows:
Design of the parts repository table (tblPartMain)Although not included in this simple sample database, additional fields such as manufacturer information and units would be useful.  The sample assumes that the units for all parts is "Each".  A units field, however would help ensure that the users understood how to enter quantities (e.g.,  feet vs spools of wire).  Keeping units consistent is of particular importance for summing quantities to get totals per assembly.
 
A second table is used to store assembly parts, relating each part to its parent assembly.  While the main Parts List table is simply a collection of all assemblies and piece parts, this component table distinguishes assemblies from simple parts.  A ParentID field is used to relate parts to their associated assemblies.  Any part that appears in this ParentID field is by definition an assembly.  The structure of this table follows:
Design of table listing components of the final product, including subassemblies and piece parts (tblSubAssemblyInfo)
The two tables are linked by a simple one-to many relationship.  The parts which appear uniquely in tblPartMain can occur multiple times in tblSubassemblyInfo, because the same part can appear throughout the overall structure on many different assemblies.  There is also a many-to-many relationship present between the piece parts and parent assemblies in tblSubAssemblyInfo.  Any part can appear on many different assemblies, and assemblies can contain multiple parts.   For this reason, neither the PartID field nor the ParentAssemblyID field can be unique.  The following query output illustrates this point, in that 1/4" Bolts appear on multiple assemblies, and the parent assemblies also appear as having multiple child records.
SELECT tblSubAssemblyInfo.ComponentID, tblPartMain_1.PartDescription AS Part, tblPartMain.PartDescription AS [Next Higher Assembly], tblSubAssemblyInfo.Qty, tblSubAssemblyInfo.MyNotes
FROM (tblSubAssemblyInfo INNER JOIN tblPartMain ON tblSubAssemblyInfo.ParentAssemblyID = tblPartMain.ID) INNER JOIN tblPartMain AS tblPartMain_1 ON tblSubAssemblyInfo.PartID = tblPartMain_1.ID;

Open in new window

Query of typical data in tblSubAssemblyInfo
The relationships between the two tables are shown below.  Note that there are not two subassembly information tables, the relationship diagram just shows a self-join which defines a link between two fields in the same table.
Relationship diagram

Although not needed for expanding a parts list (and not included in this sample), a third table for storing assembly specific details might be useful in some situations.  Such details might include projects that funded the assemblies, approval information for assembly drawings, revision information and more.  Details like these do not really belong in a general parts table.


2. The Code

Data expansion algorithm

The code included in the sample loops through an assembly, extracting data associated with each part and exporting it to an output table that can then be used for reports or other purposes.  The key to extracting data for related sub-assemblies is recursive function calls.  This simply means that the function calls itself to repeat the same steps for parts that are determined to be sub-assemblies (i.e.,  looping through all of the parts in any sub-assembly, sub-sub-assembly, etc).  
 
The data extracted is similar to that stored in the Components Table, but the code also generates an indenture level to define a given part's place in the structure (for example, the bicycle would have an indenture level of 0, and a screw on the brake assembly may have an indenture level of 5).  Also, unlike the quantity shown in the component table, which is per subassembly, the quantity calculated for the exported data applies to the entire structure.  For example, a bicycle may have two identical wheel assemblies.  The part listing for a wheel may show 30 spokes.  The quantity calculated for the bicycle as a whole should be 30 spokes x 2 wheels per bike, or 60 spokes total.

The major steps in the code can be summarized as follows:

1. Select all parts from the component table having this assembly (for example, a wheel) as a parent.

2. Determine whether each selected part is a sub-assembly or simply a piece part.  If the PartID of a part appears in the ParentAssemblyID field for any component record, then that part is a sub-assembly.

3. Expand any sub-assemblies by recursively calling the function to repeat the same steps for each of its component parts.

4. Count the number of indenture levels by keeping track of recursive function calls.  This can be done using a Static variable, which holds its value between repeated function calls.  The indenture level needs to be incremented as the code steps down through subassemblies and sub-subassemblies within the same branch of the structure.  When all the parts in a given subassembly have been extracted, the indenture level needs to be returned to the indenture level of the next higher assembly as the code continues looping through the parts of the parent assembly.  Using this process, the top-level assembly will be assigned an indenture level of 1, and the subassemblies and parts underneath it will have indenture levels of 2 or greater, depending on their depth in the structure.

5. Track quantities of parts in assemblies, so that identical subassemblies that are used multiple times have their parts multiplied by the correct factor to determine the total quantity.  The process for this is similar to that in step 4.   A 'multiplier' needs to be maintained to keep the quantities accurate.  For example, as mentioned earlier, the quantity of any part on a wheel gets doubled because there are two identical wheels on the bicycle.  When iterating through parts on the wheel, a multiplier of 2 is used to calculate quantities.  When the code has finished working with the parts on the wheel, that multiplier needs to be decreased to 1 again (to ensure that parts on the handlebar stem, for example, don't get doubled).

6. Insert a record containing partID, ParentID, Quantity, Indenture Level and any other desired information into an output table.
Function UpdateAssemblyPartsList(strPN As String, intIndenture As Integer, PartID As Long, lngParentAssembly As Long, dblOriginalQty As Double, dblQty As Double, strNotes As String)
    Dim strSQL As String
    strSQL = "INSERT INTO tblAssemblyPartsList (PartID,IndentureLevel,ParentAssemblyID,MfrPN,OriginalQty, AdjustedQty, Notes) "
    strSQL = strSQL & "VALUES (" & PartID & "," & intIndenture & ",'" & lngParentAssembly & "','" & strPN & "'," & dblOriginalQty & "," & dblQty & ",'" & strNotes & "')"
    CurrentDb.Execute strSQL, dbFailOnError
End Function

Open in new window

7. Prevent infinite loops by setting a reasonable maximum indenture level.   Circular references can occur if a user has mistakenly entered an assembly as its own parent.  As the code steps through parts in the assembly, it will see that same assembly in it's own list of parts.  When this happens, the function will call itself to expand the same assembly again (and again and again and again...).  This infinite recursion will eventually result in a stack overflow error.

The maximum indenture level is a sanity check that is used to gracefully stop the program execution when one can safely assume that a circular reference has occurred (for example, if the assembly in question is a pen, an indenture level of 50 would definitely indicate that there is a problem with a circular reference).  This is only one method of handling the potential for infinite recursion.  Another method is mentioned a little later, in the description of the treeview output.
Public Function GetAssemblyPartsListing(lngTopLevel As Long, intQTY As Integer, blRecursiveCall As Boolean)

    Dim rsParts As DAO.Recordset
    Dim db As DAO.Database
    Dim dblQty As Double
    Dim I As Integer
    
    Static intIndentureLevel As Integer
    Static intMult As Integer
    
    On Error GoTo EH
    
    Set db = CurrentDb
    Set rsParts = db.OpenRecordset("Select *, MyNotes as strNotes FROM tblSubAssemblyInfo Inner Join tblPartMain On tblSubAssemblyInfo.PartID = tblPartMain.ID WHERE ParentAssemblyID = " & lngTopLevel)
    'Initialize the multiplier if this is the first function call
    If Not blRecursiveCall = True Then
        intMult = intQTY
    End If
    Do Until rsParts.EOF
        'If this part is an assembly (determined by looking for this part in the ParentAssemblyID field)...
        If DCount("*", "tblSubAssemblyInfo", "ParentAssemblyID = " & lngTopLevel) > 0 Then
            'Calculate the multiplier for parts at the next level
            If IsNumeric(rsParts!Qty) Then
                ' Multiplies the quantity of this part as stored in the table by the quantity of the parent assembly for this part,
                ' and stores it in a static variable so that it's value persists the next time this function is called.
                intMult = intMult * Nz(IIf(IsNumeric(rsParts!Qty), rsParts!Qty, 1), 1)
                dblQty = intMult
            Else
                dblQty = -9999
            End If
            UpdateAssemblyPartsList rsParts!MfrPartNumber, intIndentureLevel + 1, rsParts!PartID, rsParts!ParentAssemblyID, rsParts!Qty, dblQty, rsParts!strNotes
            ' Increment IndentureLevel for subassembly parts
            intIndentureLevel = intIndentureLevel + 1
            If intIndentureLevel > 50 Then GoTo ExitFN   'Indentures > 50 indicate a recursion problem
            GetAssemblyPartsListing rsParts!PartID, Nz(intMult, 1), True
            ' Decrement the indenture level and reduce the multiplier, since we're not
            ' dealing with that subassembly any more
            intIndentureLevel = intIndentureLevel - 1
            ' Divide to return to the quantity needed for the parent assembly.
            If IsNumeric(rsParts!Qty) Then intMult = intMult / Nz(rsParts!Qty, 1)
        Else
            ' Discrete part- not a subassembly... get the total quantity, leaving the multiplier as is.
            If IsNumeric(rsParts!Quantity) Then dblQty = intMult * Nz(rsParts!Qty, 1)
            UpdateAssemblyPartsList rsParts!MfrPartNumber, intIndentureLevel + 1, rsParts!PartID, rsParts!ParentAssemblyID, Nz(rsParts!Qty, 1), dblQty, rsParts!strNotes
        End If
        rsParts.MoveNext
    Loop
    
ExitFN:
    rsParts.Close
    Set rsParts = Nothing
    Exit Function
EH:
    MsgBox "Error " & Err.Number & ": " & Err.Description
    GoTo ExitFN
End Function

Open in new window


3. The Output

Displaying the results

The attached sample database shows several different ways of displaying the output data from expanding a hierarchical data structure, including a treeview and several datasheets showing lists that can readily be shown on Access reports or exported to other formats such as Excel or text files.

Since the data structure defines a “shape”, a treeview control is an ideal way of displaying the structure from the top down.  Each part in the structure is shown as a node in the treeview, and parts that are assemblies themselves can be expanded or collapsed with +/- signs to reveal or hide the parts that define them.  
TreeView control --  displays the part description, part number, indenture level and quantity of parts used to build an assembly
The code used to load the treeview is another example of a recursive function, which calls itself to fill in child nodes under each parent.   For comparison, this function uses a different sanity check than that previously explained to avoid circular references.  The code checks the values of the child and parent IDs prior with each call to the recursive function.  If a child ID is the same as its parent ID, a circular reference has occurred.  The code at that point is aborted.

The actual code has been significantly edited to show the relevant parts below:
Sub AddTreeData(list of parameters)
    
    On Error GoTo EH
    
       ' Test for a circular reference
       If rs(strChildField) = rs(strParentField) Then GoTo EH_CircularReference
    
        ' Do lots of things ...

        ' call this function recursively for "children"
        AddTreeData (List of parameters)
        
        ' Do more things...    

    Exit Sub
    
EH_CircularReference:
    MsgBox "Exiting because of a circular reference in which a child record was determined to be it's own parent."
    Exit Sub
  
EH:
    MsgBox "Error " & Err.Number & ": " & Err.Description
End Sub
    

Open in new window


The second report is a listing of parts to be ordered.  This datasheet is based on a query that excludes parts which appear as “parent” records in the output.  This query limits the output to parts which need to be ordered versus assemblies that need to be built, and provides a total quantity needed for each part -- summed up for the whole structure.  
Example listing parts to order
The indentured Parts List is a listing of all parts and subassemblies needed to build the final product.  The indenture level and order of the parts illustrates how pieces fit together to build the overall structure.  It contains all of the information that the treeview shows, but it is a “flat” display which can easily be exported to Excel or a text file.
Indentured Parts List

The Assembly Listing shows all assemblies that need to be built and pieced together to form the final product (this listing excludes any parts that are not assemblies themselves).  Like the indentured parts list, the assembly listing uses indenture level and the order of the records to show the level and location of assemblies relative to the top of the structure.
Indentured listing of assemblies

In Conclusion

The sample database is a very simple example of how to apply these concepts, but the possibilities are endless.  

The sample simply demonstrates how to expand a Bill of Materials and report the resulting data.  However, these concepts could be integrated into systems that include work orders for building such assemblies and purchasing processes for acquiring the parts needed.  

In a more sophisticated database which includes a purchasing system, data such as that in the “parts to be ordered” report can be combined in a query with previous known costs of these parts.  This query would be a powerful cost estimation tool for future projects.

Other Applications

While the main focus of this article has been on a Bill of Materials example, the same concepts apply to hierarchical data structures in any discipline.  

Some other examples include:
          Family trees:  Parents, children, grandchildren, great-grandchildren...
          Recipe collections:  Ingredients may be recipes containing ingredients of their own
          Organizational hierarchies: Individuals may supervise employees who are supervisors themselves

Acknowledgements

Thanks to the editors who have worked with this article, and to the many people who have taken the time to review this and offer suggestions prior to publication (you know who you are).
 
Special thanks also to JDettman, rockiroads and puppydogbuddy for initially helping me get my brain wrapped around this subject, and puppydogbuddy for later referring me to other EE Members who needed help with this.  Explaining the concepts to other people has helped reinforce my own understanding of the material, and improve on the sample code in the process.   This article and my various posts on the subject are in that sense passing along the benefits that I have received from the community – like modern day storytelling.
17
Comment
Author:mbizup
  • 2
4 Comments
 

Administrative Comment

by:Patrick Matthews
mbizup,

Congratulations!  Following review by the Page Editors, this article has received the Editors Choice designation.

Thank you again for a terrific article.

matthewspatrick
Page Editor
0

Expert Comment

by:Kelzud
This was a wonderful article.  It has pointed me in the right direction for working with hierarchies.  

Quick question:  Is it possible to do the same thing in the reverse order?  Build from the bottom up (e.g. from the children up to the grandchildren?  I am assuming that something like this would allow you to both see everywhere your product was used and also the total required product to build every assembly in your database.

Thank you very much for the amazing work.  I could only find solutions related to self joining a table 3-4 times without recursive code before coming to your article, and it has been the deciding factor for me to join this site.

Kelzud
Amateur Database Designer
0
LVL 61

Author Comment

by:mbizup
Hi Kelzud,

Thanks for your comments - I'm glad you found the article helpful.

<< Quick question:  Is it possible to do the same thing in the reverse order? >>

That's not really such a quick question... there are factors that complicate this, to the extent that  I personally have not ever programmed a "reverse BOM".

These are just a couple of issues that have been roadblocks for me:

1.  Gaps in the structure.  For a complete assembly, you know the parent, and all of its 'descendents'.  However, at least in our production environment, there may be gaps between one assembly and the highest level (you might know the 'great-grandparent', but not know the 'parent'.

2.  Different parent assemblies may have identical child assemblies.  For example - the left wing and right wing of an airplane are similar but different assemblies which may contain identical sub assemblies - which complicates determining which wing is the parent assembly of a given sub assembly.  Depending on the overall project, that distinction may or may not be important.  Our organization uses 'find numbers' to pinpoint the exact location of each part.

Anyhow - I see you have posted a question in the Access Zone, which was a good idea -- it will get more people looking at it, and I'll monitor it to see what others have to say.

http://www.experts-exchange.com/Microsoft/Development/MS_Access/Q_27804073.html

In fact, there might be a couple of people subscribed to this article who may be able to pitch in :)
0

Expert Comment

by:Kelzud
Thank you so much for the input and oversight of the answer.

I will continue the conversation over there,

In quick comment to points 1 and 2 regarding roadblocks:
1.  we have a group that is building BOMs from the top down, which is something that we have enforced to prevent any orphan materials from being created.  Based on the assumption (dangerous) that they are doing what they are supposed to, it follows that the full family tree should be available in reverse order, and by going in the reverse order one would be able to ignore any irrelevant children (except the material / objects that your desired material is nested under).

2.  Our parent assemblies are tracked through location numbers, so regardless of how often it exists it is nested under a unique location each time.  Fortunately for myself, and unfortunately for the customer, the locations have been created to such a granular level by a previous project that nesting of materials and assemblies is almost not required.  The headlights on your car have a fixed location in the customer's location structure, so to speak.

Cheers and thanks again,

Kelzud
1

Featured Post

Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

Join & Write a Comment

Do you want to know how to make a graph with Microsoft Access? First, create a query with the data for the chart. Then make a blank form and add a chart control. This video also shows how to change what data is displayed on the graph as well as form…
A query can call a function, and a function can call Excel, even though we are in Access. This is Part 2, and steps you through the VBA that "wraps" Excel functionality so we can use its worksheet functions in Access. The declaration statement de…

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month