Managing hierarchies is a common problem for developers. One example might be a country/state/city or an organizational chart of employees where managers have multiple direct reports and those direct reports may have direct reports, and so on. As in most programming situations, there are many solutions to this problem. First, we will discuss the use of separate tables, and then ActiveX Data Objects (ADO) MSDataShaping, how to use it, and why it is limited. I also will explain how to implement infinite hierarchies. (Download Source code for this article)
This article will experiment with a commonly seen hierarchy -- country/state/city. Our goal will be to store the information and retrieve it in an HTML list that looks something like this:
Let's first examine how to approach a simple country/state/city hierarchy using a multitable structure and ADO shaping. First, the data needs to be stored in a logical, normalized database. So, we will create a typical design for storing this information:
Next we have to retrieve the data and format it using ADO's MSDataShape provider. The MSDataShape provider is a wonderful tool if you have a simple two-tier hierarchy, but it becomes much more complex when you need to do three-tier, aggregates, grand totals, or other difficult operations. The syntax required is certainly not the cleanest or easiest to understand. As you can see from the example, it may appear that there is an extra parenthesis, but in fact the syntax is correct. Here's what the SQL looks like for our simple case:
SHAPE { SELECT * FROM COUNTRY ORDER BY CountryName }
APPEND
(
(
SHAPE { SELECT * FROM STATE ORDER BY StateName} as RSState"
APPEND
(
{SELECT * FROM CITY ORDER BY CityName} AS RSCity
RELATE StateID TO StateID
)
)
RELATE CountryID TO CountryID
)
And the code for displaying the hierarchy follows here:
Response.Write "<PRE>"
Do Until oRSCountry.EOF
Response.Write oRSCountry( "CountryName" ) & " - " & oRSCountry( "Population" ) & vbCRLF
Set oRSState = oRSCountry.Fields( "RSState" ).Value
Do Until oRSState.EOF
Response.Write " " & oRSState( "StateName" ) & " - " & oRSState( "Population" ) & vbCRLF
Set oRSCity = oRSState.Fields( "RSCity" ).Value
Do Until oRSCity.EOF
Response.Write " " & oRSCity( "CityName" ) & " - " & oRSCity( "Population" ) & vbCRLF
oRSCity.MoveNext
Loop
oRSState.MoveNext
Loop
oRSCountry.MoveNext
Loop
Response.Write "</PRE>"
'Code can be found in ADOShape.asp
That's an overview of doing hierarchies with ADO DataShaping and multiple tables. Although it's not the easiest interface to use or the most flexible, Data Shaping is very good at what it does. When used to solve a problem it is suited for, it may be the right choice. However, some of the more perceptive readers might notice a few problems with this approach:
1. It's not easily scalable.
If you need to add another level, such as Continent at the top of the hierarchy or locale at the bottom, you need to create another table for each new level. The Shape statement becomes inherently more complex, and even more nested loops are required to retrieve the data.
2. There is a lot of redundant code.
For each level down, you need another do until/loop to manage that level, when in essence each loop is doing the same thing for each entity.
3. What happens if I'm running Apache and PHP Hypertext Preprocessor (PHP)?
Another problem with using the Shape language is that the code cannot be translated for use on a different platform. For example, methods of data access with ADO are very similar to the PHP/mySQL database access on Linux. Open a connection, execute SQL, retrieve the recordset, and display the recordset. If you introduce the SHAPE command into the mix, you have no corresponding command on other platforms to convert to.
The Infinite Hierarchy
The above are all valid points against using Data Shaping for the issue at hand. We will now design and build the infinite hierarchy to overcome these issues and some others as well. First let's step back and look at a bit of object oriented theory. When designing objects, you think in terms of commonality. -- What does this object have in common with that object? If commonalities are found, base objects can be created and child objects can inherit the parent's properties and methods. In this situation, there are quite a few commonalities. Each of the database entities, Country, State, and City are places with populations. For our example, the only difference between each entity is the where in the hierarchy they lie. In other words, the State is level down from Country, and the City is a level down from State. Each entity has a null parent if it is at the top of the chain, or one parent if it is a level below. This introduces a pattern called a parent/child hierarchy. The database design for this is quite simple:
We've broken down the country/state/city hierarchy into a fundamental type called a region. We could easily add a descriptor field to this table to show whether this region was a country, state, or city. However, for this example, it's not necessary. We simply need to show each region, its population, and its relation to a parent. Here is an example of what the data in the table might look like:
RegionID
RegionName
Population
ParentRegionID
1
USA
276059000
2
Texas
20044141
1
3
Illinois
12128370
1
4
Florida
15111244
1
5
Austin
1146050
2
6
Dallas
3280310
2
7
Miami
2175634
4
8
Chicago
8008507
3
9
Rockford
358640
3
USA is the top of the hierarchy in this case. The USA's direct children, or states, are those that have a ParentRegionID of 1. From there, we can see that each state has a ParentRegionID that corresponds to the USA RegionID of 1. Each city's ParentRegionID points to one of the state's RegionIDs. Notice that from this structure we could easily expand the bottom of the hierarchy to include the zip code as a child to City, a street as a child to Zip Code, an address as a child to Street, and so on. This is where we get the notion of an infinite hierarchy, or a simple parent/child relationship.
Now that we have the data structure, we need a way to retrieve the data in the hierarchical format we desire. Before delving into how to solve this problem, we need to bring out our Programming 101 books and revisit the notion of recursion. In the simplest form, recursive functions are functions that call themselves. One of the most common examples of recursion is the factorial. A simple recursive function to find the factorial is:
Sub Function factor( n as Integer )
IF n = 0 THEN
Factor = 1
ELSE
Factor = n * factor( n - 1 )
END IF
End Function
To contrast the recursive version, there is another much more efficient way to find a factorial using a nonrecursive method, as follows:
Sub Function factor( n as integer )
DIM nCount as integer
DIM nProduct as Integer
For nCount = 1 to n
nProduct = nProduct * nCount
Next
Factor = nProduct
End Function
Recursive functions are not used very often, and many people will advise you to stay away from them at all costs because they tend to be slower, take up more stack space, etc. The best advice is to use the right tool for the right job. Computers are becoming faster, memory is getting cheaper, and we, as programmers, still have to get the job done. If a recursive function is the best solution for the problem at hand, use it. In the case of the factorial, if we call the recursive factor function with the number 200, it will result in 200 calls to the function on the stack. In this case a FOR . . .NEXT loop is going to be significantly faster than the recursive method.
We have chosen to use a recursive function for our infinite hierarchy because it works well to solve the problem. There will be a minimum level of nesting ( in this case, three) so the stack should not be overworked. This also appears to be the most elegant solution at this point, and without further experimentation, there appears to be no easy way to do it nonrecursively. Even if the hierarchy were to reach 10 or 20 levels deep, it would not pose undue stress on the system, compared to the recursive factorial with the number 200.
First, the SQL statement is much simpler than the SHAPE command:
SELECT * FROM Region ORDER BY RegionName
The code to display the data is:
CONST REGION_ID = 0
CONST REGION_NAME = 1
CONST POPULATION = 2
CONST PARENT_REGION_ID = 3
sSQL = "SELECT * FROM Region ORDER BY RegionName "
oRS.Open sSQL
Response.Write "<PRE>"
g_arrRows = oRS.GetRows()
g_nCount = oRS.RecordCount
oRS.Close
' Find the top-level entities in the hierarchy
For nIndex = 0 To g_nCount - 1
' If the Parent is NULL, we have a top level
If IsNull(g_arrRows(PARENT_REGION_ID, nIndex)) Then
' Start looking for children
PrintRow g_arrRows(REGION_ID, nIndex), g_arrRows(REGION_NAME, nIndex), g_arrRows( POPULATION, nIndex ), 0
End If
Next
Sub PrintRow(nRegionID, sRegionName, nPopulation, nLevel )
DIM nIndex
'Write out the current level
Response.Write String(nLevel, " ") & sRegionName & " - " & nPopulation & vbCRLF
For nIndex = 0 To g_nCount - 1
' IF the row we're looking at has a parent of the region passed in, then delve into its children.
If g_arrRows(PARENT_REGION_ID, nIndex) = nRegionID Then
' Call our PrintRow function to find the children of this record and so on.
PrintRow g_arrRows(REGION_ID, nIndex), g_arrRows(REGION_NAME, nIndex), g_arrRows( POPULATION, nIndex ), nLevel + 1
End If
Next
End Sub
We take the results of the recordset and place them into a multidimensional array. We chose to manipulate the data in an array instead of using the Recordset.MoveFirst and Recordset.MoveNext because using ADO cursors tends to be expensive. Arrays have always had advantages over collections of objects in terms of speed.
We then walk through the array sequentially to find the regions with NULL in their ParentRegionID field. This signifies that we have a top-level record. Once we have a top-level record, we call the PrintRow function to start walking the hierarchy. Each time PrintRow is called, it will print the current row and see if that row has any children. If it does, it will call the PrintRow subroutine with that row's information and start the process over again. As you might guess, there is no limit to the number of levels one could have if the hierarchy was implemented in this way. Through good database and OO design, a recursive function, and a bit of finesse, you have the infinite hierarchy.
Further Exercises
There will be other astute readers who will notice that the infinite hierarchy algorithm presented here will execute more slowly as more items are added to the table. This is true because the example uses sequential searches to determine whether or not we have a match. It will slow considerably after thousands of records are placed into the table. For simplicity, I left the example as is. In a real-world application with thousands of records, one may wish to create a hash table of RegionIDs and ParentRegionIDs to implement much faster searching, an exercise I will leave to the more experienced reader.
About the Author
Craig Huber is a programmer analyst for Dell Computers in Austin, Texas. He has spent many years working with Microsoft technologies, designing, developing, and implementing three-tier applications with ASP, VB, COM+, SQL Server, or Oracle. He also has a broad range of knowledge in many different areas, including Windows administration, Linux administration, PHP, Perl, and mySQL. He can be reached at craig@huber.ws or www.huber.ws.
Proposion N2N connects Microsoft .NET applications to Lotus Notes and Lotus Domino databases. This ADO.NET managed data provider allows you to perform blindingly fast queries and updates of Notes data from ASP.NET pages, .NET web services, Windows, or Mobile applications. An innovative SQL-like query language leverages the unique features of Notes and makes collaborative software accessible to relational database programmers.
Unlike text-based file formats image files aren't made up of words, which makes searching for an image file by keyword difficult. Instead of being able to simply open the file to see what it contains, we're stuck looking at the text around it and other metadata to determine the image's meaning. In this article, Ziran Sun shows you how to build a simple database-based image keyword system that allows you to associate keywords with images and use these keywords to make finding images easier. [Read This Article][Top]
In the second part of of his article on using MySQL with ASP.NET, Ziran Sun covers how to add a new MySQL user to the database server, assign the user the appropriate permissions, connect to the database, and build a simple ASP.NET page to perform a query. [Read This Article][Top]
Back in the days of classic ASP, if you were building a database-driven
web site, your choice was either to invest a lot of money to get a copy of Microsoft SQL Server
(or some other enterprise-ready database) or invest a lot of time finding a way to deal with the
performance and scalability limitations of Microsoft Access. Luckily these days there's
another viable alternative: MySQL. [Read This Article][Top]
Moving or copying a SQL Server database from one machine to another requires a lot of preparation in order to ensure a smooth transfer. In this article, Dina Fleet Berry examines the different methods and highlights the different issues associated with each of them. [Read This Article][Top]
There are many times when using SQL Server 2000 Query Analyzer to debug SQL statements is a better choice than debugging in Visual Studio .NET. In this article, Dina Fleet Berry explains why and walks you through the debugging process step-by step. [Read This Article][Top]
As a follow up to his article on retrieving objects from SQL Server using SQLXML and serialization, Gianluca Nuzzo discusses saving objects back to SQL Server using a schema definition file and updategrams. [Read This Article][Top]
One area that stands out when comparing ADO.NET 1.x to ADO.NET 2.0 is transaction processing. Bill Ryan shows just how easy transaction processing has become with the TransactionScope object in ADO.NET 2.0. [Read This Article][Top]
Developers often use brute force coding to marshal data between the GUI and application objects. In this article, Luther Stanton explains how to use .NET's out-of-the box data-binding functionality to make this job much easier. [Read This Article][Top]
Learn how to create a console application to queue a message in Microsoft Message Queuing (MSMQ) and then use an extended stored procedure to call the console application from a SQL Server trigger. [Read This Article][Top]
Connection pooling increases the performance of Web applications by reusing active database connections instead of creating a new connection with every request. This article shows how to monitor the connection pool, diagnose a potential problem, and apply the appropriate fix. [Read This Article][Top]
Mailing List
Want to receive email when the next article is published? Just Click Here to sign up.
