Tree table metadata using an adjacency model (cool recursive code)
Anyhow, anyone who has ever tried to access data using parent IDs will admit, it is a pain, so historically I've just added metadata to the table to permit quicker and easier querying (yeah - I could have added nested set metadata, and may yet next time around). For now, I add an indented title (so I can easily display "- - SubsubPage" indented), a nest level, a global display order (an int which can be ordered by to return the tree in the correct order) and a file path (a concatenation of all parent names "/" delimited - useful for filtering recordsets and for easily displaying cookie crumbs).
I just put together a ColdFusion routine that (when called - after an insert, update or delete) re-creates the metadata for a given table. It works on any generic table with some kind of ID field, name field and title field (they can be called anything). OBVIOUSLY CF is not the place you want to run this as it runs one update per record. It works surprisingly well for a couple of hundred records, but I'm looking for someone to turn this into a MSSQL stored procedure (if anyone is interested, drop me a line :->).
Code after the break . ..
Anyhow, it isn't all that often you get to write recursive code, so I thought it'd be a good example to have out there. And who knows, maybe it'll work as a stopgap for someone else who needs a quick solution to easier access to their tree based data.
Thoughts?
(Oh, if I DO get an SP from someone, I'll post it).
<cfargument name="TableName" required="true" type="string" hint="The name of the database table to operate against.">
<cfargument name="IDFieldName" required="true" type="string" hint="The name of the ID field used to uniquely identify a field.">
<cfargument name="ParentIDFieldName" required="true" type="string" hint="The name of the parent ID field used to uniquely identify a field and its parent. For example, if the ID field name is PageID, the ID field is PageID and the parent ID field is ParentPageID. If the ID field name is CategoryName, the ID Field is CategoryName and the parent ID field is ParentCategoryName.">
<cfargument name="SiblingDisplayOrderFieldName" required="true" type="string" hint="The name of the field to use to order records that have the same parent ID. Perhaps Title or DisplayOrder.">
<cfargument name="NameFieldName" required="true" type="string" hint="The name of the field used to generate the FilePath field. Often the Name field.">
<cfargument name="TitleFieldName" required="true" type="string" hint="The name of the field used to generate the indented title field. Often the Title field.">
<cfargument name="RootID" required="true" type="string" hint="The root ID to start with. Allows recursion.">
<cfargument name="DefaultFilter" required="false" type="string" default="" hint="Allows for a default filter if (for instance) you only want to include records where Deleted=0 or Status=1 or something.">
<cfargument name="GlobalDisplayOrder" requirede="false" type="numeric" default="1" hint="The numeric count for global display order. Used by recursion. Defaults to 1 if not passed.">
<cfargument name="NestLevel" required="false" type="numeric" default="1" hint="The current nest level. Userby recursion. Fedaults to 1 if not passed.">
<cfargument name="ParentFilePath" required="false" type="string" default="" hint="The file path of the parent to concatenate when creating file path. Used for recusrion. Defaults to ''.">
<cfset var GetRecords = "">
<cfset var FilePath = "">
<cfset var NestCount = "">
<cfset var IndentedTitle = "">
<!--- Start by getting all records with this parent --->
<cfquery name="GetRecords" datasource="#variables.Datasource#">
SELECT #IDFieldName#, #NameFieldName#, #TitleFieldName#
FROM #TableName#
WHERE #ParentIDFieldName# = '#RootID#'
<cfif len(DefaultFilter)>
AND #preservesinglequotes(DefaultFilter)#
</cfif>
ORDER BY #SiblingDisplayOrderFieldName#
</cfquery>
<cfoutput query="GetRecords">
<!--- For each record --->
<!--- Update metadata properties --->
<cfscript>
// Set the filepath If (Len(ParentFilePath))
{FilePath = ParentFilePath & "/" & evaluate(NameFieldName);}
Else
{FilePath = evaluate(NameFieldName);};
// Set the indented title IndentedTitle = evaluate(TitleFieldName);
NestCount = NestLevel - 1;
while (NestCount)
{
IndentedTitle = "- " & IndentedTitle;
NestCount = NestCount - 1;
};
</cfscript>
<cfquery name="UpdateRecord" datasource="#variables.Datasource#">
UPDATE #TableName#
SET NestLevel = '#NestLevel#',
GlobalDisplayOrder = '#GlobalDisplayOrder#',
FilePath = '#FilePath#',
IndentedTitle = '#IndentedTitle#'
WHERE #IDFieldName# = '#evaluate(IDFieldName)#'
</cfquery>
<cfset GlobalDisplayOrder = GlobalDisplayOrder + 1>
<cfset RootID = evaluate(IDFieldName)>
<cfset SubNestLevel = NestLevel + 1>
<!--- and recursively call this method --->
<cfset GlobalDisplayOrder = updateTreeMetadata(TableName, IDFieldName, ParentIDFieldName, SiblingDisplayOrderFieldName, NameFieldName, TitleFieldName, RootID, DefaultFilter, GlobalDisplayOrder, SubNestLevel, FilePath)>
</cfoutput>
<cfreturn GlobalDisplayOrder>
</cffunction>
Oh, and yes, I know there are no cfqueryparams. I'll drop them in later *blush*
It handles all this tree parent stuff automatically in the database
No, I didn't know, so thanks for the heads up! Unfortunately though, I don't think an Oracle db is in my or my clients future. I mainly generate sites for SMB's.
Most of the tree-into-database methods I've seen out there are either recursive functions like the one you details, or they store the hierarchy itself in an infix order (with increased costs for inserting/moving nodes).
In a similar theme to your method, I found this article [ http://www.sqlteam.com/item.asp?ItemID=8866 ] which effectively stores the hierarchy using triggers. Might be of some use to you.
For anyone who doesn't wnat to read the whole article, he uses slightly different fields than me, but his solution is:
WHILE EXISTS (SELECT * FROM Tree WHERE Depth Is Null)
UPDATE T SET T.depth = P.Depth + 1,
T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode,6,0)) + '/'
FROM Tree AS T
INNER JOIN Tree AS P ON (T.ParentNode=P.Node)
WHERE P.Depth>=0
AND P.Lineage Is Not Null
AND T.Depth Is Null
When I get a few mins I'll tweak that for the columns I want and will post it.
Many thanks again - exactly the SQL I needed :->
FWIW - May I recommend Joe Celko's book titled: 'Trees and Hierarchies'. It has been a great reference for an designing extensive dynamic 'menuing' systems for me.
It devotes chapter 4 to nested models and, aside from some hurdles when updating huge datasets, provides a very elegant solution me thinks.
It is easy to infer that Joe's views on application code are not the norm for many but it is a worthy recourse nonetheless...
my .02,
Mario
You still have to update every row on a table, but it's only two columns and they're integers. You just have to write a few methods to handle what happens when you delete, insert as child, insert as parent, insert as sibling etc. It's a fun mental exercise to graph out the nesting and figure out what you need to do get the numbers right.
When I saw how it worked I thought, "Man, how did someone figure this out? Brilliant!"
@Josh, Quite possibly, although I remember thinking it through some time ago and there were some cases that were a pain to do with nested sets, but I will revisit.