Path Enumeration mySQL Querying to create a bread crumb

Question

I would like to create a bread crumb from a path enumerated column.

Here is an example of the dataset that I have.

https://spreadsheets.google.com/ccc?key=0AsGYQbeSAIgFdGRscFpsZFJpQUtfWGIwYWNUY2ktRHc&hl=en_GB&authkey=CPOuuogF

id woeid parent_woeid country_code name language place_type ancestry

ancestry is the enumerated path, such like 1/23424975/24554868/12602167/12696151 is the path for Brighton in England.

I would like to be able to retreive a breadcrumb by querying the name column, and get all of the parents.

ie. World, Europe, England, [County], [Town], [Region], [Place]

([] = a placeholder)

The data never changes, which is why this table uses Adjacency List and path enumeration.

Answer 1

Several possible approaches. I'll go from what you want to do, to what I suggest you do.

Materialized Path

Unfortunately, enumerated path ancestry (e.g. parentage) is expensive and tricky to do with SQL only (see section on Materialized Path find "An employee FORD and chain of his supervisors"). If you have the path ahead of time and can work with some sort of programming language, the easiest approach is using an IN clause:

SELECT *
FROM woe
WHERE ancestry IN (
    '1', 
    '1/23424975', 
    '1/23424975/24554868', 
    '1/23424975/24554868/12602167', 
    '1/23424975/24554868/12602167/12696151'
)
ORDER BY LEN(ancestry)

Adjacency List

Or, you could take advantage of the Adjacency List aspect of your data and use a Common Table Expression or CONNECT BY instead depending on database (this ignores the ancestry column). See my question about different ways of representing hierarchical data in an RDBMS for information on working with Adjacency List to query ancestry (see the Database Specific Notes section at the end of the question).

Nested Set

You write your data doesn't change and you want to query ancestry. A nested set representation is the perfect approach in this situation because getting the information you want using SQL only is easy, works with any database, and is very cheap operation. Downside is moves and insertions are expensive. Managing Hierarchical Data in MySQL is probably best explanation I can provide for how it works.

Nested Set is what I'd use given your data, what you want to do and that it doesn't change.