Parent-Child Queries Enhancement: Multi-Parented Items

All of the work we’ve done thus far on our parent-child query sorter has made the presumption that each item has but one parent, like so:

Items
ItemIDint identity
Namevarchar
ParentIDint

This is the easiest way to do heirarchical navigation, but it does have its limitations. In the real world, it is often useful to have more than one parent for an item. A reader, Albert, provided the following example and quandary.

  • Bar (1)
    • Bar Refrigeration (2)
      • Back Bar Coolers (3)
        • Glass Door (6)
        • Solid Door (7)
  • Equipment (4)
    • Bar Equipment (5)
      • Back Bar Coolers (3)
        • Glass Door (6)
        • Solid Door (7)

In the online-shopping world, this is of course quite common. You don’t want to force your web site guests to conform to your rigid structure — you want them to be able to find and buy things as easily as they can. So how can we accomplish this with a minimum of fuss?

First, we need to modify our table structure a bit:

Items
ItemIDint identity
Namevarchar
1                   many
ItemParents
ChildIDint
ParentIDint
   

We would then need to modify our query to get our item list:

SELECT
    i.ItemID,
	i.Name,
	ip.ParentID
FROM Items AS i
    LEFT OUTER JOIN ItemParents AS ip ON (i.ItemID = ip.ChildID)
ORDER BY i.Name

This is not a big change. We’re still getting the same columns, but now we’ll now have duplicate items for each parent:

ItemIDNameParentID
3Back Bar Coolers2
3Back Bar Coolers5
1Bar 
5Bar Equipment4
2Bar Refrigeration1
4Equipment 
6Glass Door3
7Solid Door3

If we used the code that we already have, it would be somewhat correct, in that the ItemID and Name columns would come out okay, but the ParentID columns would be a little funky. So what’s the solution?

Since any branch of the tree can now be grafted to any other point, as many times as we have other items in the tree, we need a way of deciding which ParentID is the correct one at any given time. Logically, this shouldn’t be too hard as it all hinges on one thing: as we loop through the items, we had to have already seen the parent, as we couldn’t be on the current item otherwise! Thus, what we need, is another cache structure that holds the most recent parent for a given item. Easy.

In our variable declaration at the top of our function, we’ll need two new items: a local variable to hold the current ParentID, and our cache structure:

<cfset var ThisParentID=0>
<cfset var MostRecentParent=StructNew()>

The easiest place to add to the cache is at the bottom of our loop where we add children to the to-do stack:

        <cfset ArrayPrepend(RootItems, ChildrenIDs[i])>
        <cfset ArrayPrepend(Depth, ThisDepth + 1)>
        <cfset MostRecentParent[ChildrenIDs[i]]=ThisID>
    </cfloop>
</cfif>

We can the move up a bit in the code to the part of the loop where we get the ParentID and try to make a Lineage with it. We just need to check the cache and use that most recent ParentID if we can find one:

<cfset NewRowFromID[ThisID]=Ret.RecordCount>
<!--- Try to find the parent's lineage --->
<cfif StructKeyExists(MostRecentParent, ThisID)>
    <cfset ThisParentID=MostRecentParent[ThisID]>
    <cfset StructDelete(MostRecentParent,ThisID,False)>
<cfelse>
    <cfset ThisParentID=Stuff[Arguments.ParentID][RowID]>
</cfif>
<cfif StructKeyExists(Lineages, ThisParentID)>
    <cfset ThisLineage=Lineages[ThisParentID]>
<cfelse>
    <cfset ThisLineage="">
</cfif>
<!--- Add the parent if there is one --->
<cfif StructKeyExists(NewRowFromID, ThisParentID)>
    <cfset ThisParentRowID=NewRowFromID[ThisParentID]>
    <cfset ThisLineage=ListAppend(ThisLineage, ThisParentRowID)>
    <cfif Arguments.ChildrenRowName NEQ "">

That leaves us with just one last fix to make — we need to make sure that when we copy the row from the source query to the destination query, that we use the correct ParentID:

    <cfset QuerySetCell(Ret, ColName, Stuff[ColName][RowID])>
</cfloop>
<!--- Overwrite the ParentID with the most recent parent --->
<cfset QuerySetCell(Ret, Arguments.ParentID, ThisParentID)>
<cfif Arguments.DepthName NEQ ""><cfset QuerySetCell(Ret, Arguments.DepthName, ThisDepth)></cfif>
<cfif Arguments.ParentRowName NEQ ""><cfset QuerySetCell(Ret, Arguments.ParentRowName, ThisParentRowID)></cfif>

That’s it! Our query sorter now handles multi-parented items.

Published by

Rick Osborne

I am a web geek who has been doing this sort of thing entirely too long. I rant, I muse, I whine. That is, I am not at all atypical for my breed.