Why Faceted Navigation is Hard

I was thinking about the relational model today, and I realized that a lot of people probably don't realize that faceted navigation is an example of an application that simply doesn't fit comfortably in the relational model. It also occurs to me that most of you don't care. But I'm going to tell you why anyway.

Faceted navigation is built on faceted classification, which is conceptually very simple. You've got two things: records and categories, and those two things have a many-to-many relationship.

I like to work with concrete examples, so let's take the US states as our dataset. We've got one record for each state. For our categories, let's use adjacent states. That means Massachusetts has the following categories: adjoins-NH, adjoins-VT, adjoins-CT, adjoins-RI, and adjoins-NY. Obviously there are a lot of states that belong to the adjoins-NY category: Pennsylvania, New Jersey, Connecticut, Massachusetts, and Vermont. So clearly this is many-to-many. That's faceted classification.