Best method to search hierarchical data

Question

I'm looking at building a facility which allows querying for data with hierarchical filtering. I have a few ideas how I'm going to go about it but was wondering if there are any recommendations or suggestions that might be more efficient.

As an example imagine that a user is searching for a job. The job areas would be as follows.

1: Scotland
2: --- West Central
3: ------ Glasgow
4: ------ Etc
5: --- North East
6: ------ Ayrshire
7: ------ Etc

A user can search specific (i.e. Glasgow) or in a larger area (i.e. Scotland).

The two approaches I am considering are:

1. keep a note of children in the database for each record (i.e. cat 1 would have 2, 3, 4 in its children field) and query against that record with a SELECT * FROM Jobs WHERE Category IN Areas.childrenField.
2. Use a recursive function to find all results who have a relation to the selected area.

The problems I see from both are:

1. Holding this data in the db will mean having to keep track of all changes to structure.
2. Recursion is slow and inefficent.

Any ideas, suggestion or recommendations on the best approach? I'm using C# ASP.NET with MSSQL 2005 DB.

Answer 1

Here is an approach i have seen used:

Create a varchar(max) field called hierarchyid. Generate base ids for all root objects. For each child object generate an id and prepend it with the parent(s) ids.

Example Table

ID(PK) HierarchyID Area
1       sl           Scotland 
2       slwc        West Central
3       slwcgg       Glasgow 

Example Query

SELECT * FROM Areas Where HierarchyID LIKE 'sl%'

Answer 2

You should use nested sets. Here's an implementation in MySQL. http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/