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
ItemID int identity
Name varchar
ParentID int

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
ItemID int identity
Name varchar
1                   many
ItemParents
ChildID int
ParentID int
     

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:

ItemID Name ParentID
3 Back Bar Coolers 2
3 Back Bar Coolers 5
1 Bar  
5 Bar Equipment 4
2 Bar Refrigeration 1
4 Equipment  
6 Glass Door 3
7 Solid Door 3

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.