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.

You can think of each category as a predicate that defines a subset of records -- all the records that have that category. Faceted navigation is based on taking as input a given set of categories, and producing as output all the categories that, if you added them to the input set, would define a smaller, yet non-empty, record set. For example, if I start with the set of states that adjoin Massachusetts, then I could narrow down to states that also adjoin Rhode Island, or states that also adjoin Vermont. But I couldn't narrow down to states that also adjoin California, since that would create an empty record set.

In math terms, if S is the input set of selected categories, then what you want is the set of categories c such that c is not in s, and such that there exists at least one record r such that r has c and r also has every category in S. Or, more tersely:

    {c : (∃r : c(r) ∧ (∀s in S : s(r)))} - S

If you map this to a straightforward relational structure, and then try to use SQL to compute the set described above, you will find that you basically end up thrashing the database to the point that you'd do better to suck out the entire database into memory and forget SQL entirely.

The problem is that SQL isn't really capable of expressing set intersections. Suppose we merely want to get the set of records that have our input set of selected categories. We'd have to do something like this:

  SELECT DISTINCT record_id FROM Facets WHERE 
          record_id in (SELECT record_id FROM Facets WHERE category_id=1) 
      AND record_id in (SELECT record_id FROM Facets WHERE category_id=2)    
      AND ...

No database that I know of will implement the above query efficiently, even though they could -- all they would need to do is intersect the index for category ids 1 and 2. But even if the above query were done efficiently, we're still not done. What we actually want is not a list of records, but a list of categories that would provide further refinements:

  SELECT DISTINCT category_id FROM Facets WHERE
      record_id in (
          SELECT record_id FROM Facets WHERE
                   record_id in (SELECT record_id FROM Facets WHERE category_id=1)
               AND record_id in (SELECT record_id FROM Facets WHERE category_id=2)
               AND ...)

And we're still not done, because we want to remove categories that, if we added them to the input category set, wouldn't reduce the size of our record set. That is, we want to remove "redundant" categories. I'm not even going to bother working that into the above SQL query, because it's more likely you'd implement it as a second pass, in order to keep from increasing the exponent on the query processor's big-O processing time.

It's interesting to note that every text search engine is optimized for handling the first SQL query -- text search is all about intersecting sets of documents, where those sets are defined as all the documents that contain a given word. There's a reason that relational databases aren't usually used to implement text search. For example, SQL Server requires you to explicitly state which fields you want indexed for full-text search.

Hmmm... It might be interesting to see if I could abuse SQL Server's full-text search support to get it to support faceted navigation...

Followups to Why Faceted Navigation is Hard:

Posted on September 29, 2003 08:31 PM
More projects articles

Comments

Can you explain these examples in more detail please? The first query would have been better written as (i.e. is equivalent to):

  SELECT DISTINCT record_id FROM Facets WHERE category_id in (1, 2, ...) 
... while the second query would have been better written as:

  SELECT DISTINCT category_id FROM Facets WHERE category_id in (1, 2, ...)

These are so trivial that I assume I must have misunderstood what you were trying to say. It might be easier if you provide table definitions, example data, and example queries with results.

Posted by: Alistair Bayley at September 30, 2003 07:56 AM

Your first example is doing a set union instead of a set intersection. That is, it's asking for record ids that have category id 1 or 2 or 3, when what you want is record ids that have category id 1 and 2 and 3.

As for the second query, the purpose is to take the records returned by the first query, and use it to get a larger set of category ids (using set union). Your version kind of short-circuited it, so that you'd end up with the same set of category ids as you started with.

To use the states example, suppose our input category set is {adjoins-MA}. Then we'd expect the first SQL query to return {NH, VT, CT, RI, NY}. Now for the second query, we want to get the set of all categories that belong to NH or VT or CT or RI or NY:

  SELECT DISTINCT category_id FROM Facets WHERE
      record_id in ("NH", "VT", "CT", "RI", "NY")

This is the same as the second SQL query, except that in the original article I combined the first and second SQL queries so that I could do everything in a single pass. I suppose that made it harder to read, but then the point was to explain how ill-suited this problem is to the relational model, and breaking the problem into two passes would kind of have been cheating.

Posted by: kim at September 30, 2003 10:05 AM

Ah, much clearer - thanks for the additional information. That really helps us SQL neophytes follow along a little more closely.

Also, interesting use of logical connectors there! I didn't know that the character entities were so simple; if I had, they would find much more use in my own writing. Thanks for the unintentional tip!

Posted by: Gnomon at September 30, 2003 10:34 AM

Welcome to our website:http://www.llikeonline.com.
Find cheap uggs and buy Cheap Ugg Boots online is your best choice. We can provide Fashion design and High quality UGG boots,ugg sandals,ugg shoes cheap for people of all ages ,UGG for men, ugg for women,ugg for kids, authentic UGGs.
BIG SURPRISE! exclusive ugg boots online store, recently we have a pomotion for all the customers, Everyone just buy two ugg boots.then you can get a pair of UGG slipperfor free! Limited stock, hurry up!
Free Shipping, Delivery by EMS in 6-9 business days.

Posted by: zsq at October 17, 2009 12:35 PM

Ugg boots (sometimes referred to as uggs or ug boots) are a style of sheepskin boot, with wool as the inner lining and a tanned outer surface worn by both men and women. Ugg boots often have a synthetic sole, although this is not universal. Uggs have been identified as a fashion trend for men and women since the early 2000s. In late 2008, Ugg boots grew again in popularity with men as male celebrities were seen in them.
http://www.llikeonline.com

Posted by: zsq at October 17, 2009 12:47 PM

To bug authentic UGG Classic Tall,UGG Sheepskin Bag,UGG Classic Shtor is very easy and smooth, even if you have never placed an order on the Internet before. You will receive a confirmation email after you place your order and a shipping confirmation email with tracking number after we ship your order. You can monitor your order status in our Online Order Tracking System.Welcome to come here.

Posted by: dogerlase at October 20, 2009 02:43 AM

As humans, we're simply born into one of these dog training classes: chief or follower. As these couple types are extremes of one another, you may simply be a chief, or a buff, tiny is there of any fashion in between these puppy training.Some might contest though, that you could be both at one time, the chief to numerous and a buff to one.There are more teach dog tricks to outlook out for to review if or not you're a chief or a follower. The bulk all over individual aspect is the abilities to generate determinations not simply for yourself, but in supplement for remnant as prolonged as dog behavior training.Take this covering for example; each post-graduate learner is rewarded a cubicle each, which doesn't draw seal for loose though. Most would just announce no just because it doesn't draw seal free to wholesale dog supplies. The actual justification behind their tenacity is the portion that none wants to act on away from the crowd.When one or couple of them creates a tenacity to receive one cubicle in any dog supplies, remnant in the past prolonged followed not far behind. One later another, the cubicles are being filled. Sadly, there just isn't passable room for everyone to wholesale pet supplies. Even as learners with very competent standings and privileges, not all are competent to take find how to lose weight and generate stern life correcting determinations on their own. A buff would perpetually have determinations organised for them, perpetually staring to lose weight to play-act first after the time arises. If you're one of those any person who essentially have a darling to move out with the accumulation, it's come seal time to commence correcting and take find fault for once. belly fat is a yardstick journalist for a many cluster of themes and subjects. He in supplement drafts on braun bathe and transform and braun bathe and charge.

Posted by: dogtraining at October 21, 2009 08:47 PM

Well said.

Posted by: free games at October 25, 2009 04:05 PM

These Women's Classsic Tall 5815 Boots in pink flower print can either be worn at their normal height if you want Ugg boots, but in order for you to create a more casual look to what you are wearing they can be pushed down Women's UGG Classic Tall 5815 Boots in Baked Clay

Posted by: ugg boots on sale at October 27, 2009 02:37 PM

Love this man. Great stuff, great prices, free shipping. Email him if you cant find what you are looking for and he will look for you. Good customer service.louis vuittonSomeone who is knowledgeable in louis vuitton.Another guy from hong Kong (Largest louis vuitton second hand city, I believe) he has great stuff at fair prices but his shipping is insane

Posted by: louis vuitton at October 29, 2009 08:33 AM

Ugg dakota shoes can be worn all year round, It can keep your feet dry at summer and give you warm in winter , uggs outlet ,whether in appearance or quality are first rate. ugg boots online choose a pair of good shoes to your feet.
http://www.elegantugg.com/

Posted by: ugg dakota at November 9, 2009 08:50 PM

Eliminating the need for the extra trouble to wear ugg boots saleugg saleugg boots uk, in the extreme sports, look for happiness in life, with uggs showed off your tall body, do not worry about being laughed at, dancing new style UGG Classic boots . The flavor of life that is colorful, there are UGG cardy boots, pick your favorite, do not hesitate!

Posted by: ugg boots uk at November 11, 2009 03:34 AM

Eliminating the need for the extra trouble to wear ugg boots uk
ugg boots saleuggs, in the extreme sports, look for happiness in life, with UGG Classic boots and nike sb showed off your tall body, do not worry about being laughed at, dancing new style ugg australia and nike sb dunk . The flavor of life that is colorful, there are Christian Louboutincheap nike dunksUGG cardy boots、and nike sb for sale also used fear to creep away money from your pocket Mody ? Love beauty, you might even love UGG Classic tall bootsUGG Nightfall bootsUGG Classic short bootsnew nike sb。There are an infinite high power drivers of popular front ugg boots saleugg saleuggsnike dunkdiscount ugg bootsnike dunk sb, our website also have UGG Nightfall bootsbutton ugg bootsbailey button uggugg button bootsbailey button bootsnike dunk midnike dunk highChristian Louboutin Boots, pick your favorite, do not hesitate!

Posted by: ugg boots sale at November 12, 2009 04:02 AM

People all over the world know the abercrombie and fitch,but not everyone really knows how fashion the abercrombie is,hollister is the Legend maker. Everybody wears the hollister clothing would be the abercrombie mensand the abercrombie womens, if you want know you can search the Ruehl No.925 or abercrombie outlet in the www.google.com .

Posted by: anf at November 13, 2009 12:52 AM

Uggs on sale now.UGG Classic Cardy Boot makes me different form the other

girls. The UGG Bailey Button Boot is a good choice for female.

Posted by: ugg classic cardy boots at November 16, 2009 11:54 PM

UGG Bailey Button bootsis a new style in 2009.The classic cardy uggs boots is another hot boots that worth of buying.And the classic tall ugg boots will make your winter amusing.And now uggs on sale,if you are looking for such a boot,the ugg boots is good choice this year.

Posted by: UGG Bailey Button Boots at November 17, 2009 02:01 AM

I love Women's UGG Classic Cardy Boot 5819 very much. And the new style UGG Mayfaire Boots is aslo a good choice this year.

Posted by: UGG Bailey Button Fancy Boots at November 17, 2009 03:15 AM

I bought a pair of ugg boots last year, so pretty! the quality of it is also good, I have wear it for a long time without any problem.you don't need to worry about its quality at all. with a reasonabal price and good quality ,I think it deserve you to own uggs boots on sale.

Posted by: uggs at November 17, 2009 08:34 PM

lxjuan08ed hardyis a famous ed hardy store which sell directly ed hardy clothing, shoes, boots, swim suit and other cheap ed hardy.

Browse through our catalogue of hundreds of ed hardy clothing,Ed hardy Shirt,Ed hardy ... Buy Ed Hardy today for a gift, for a friend, or for yourself.

ED HARDY Online Shop,Ed Hardy Store by Christian Audigier,coach handbags,rolex watches.We supply cheapest Newest ed hardy discount 2009 Commodity New styles.


ed hardy sale

Posted by: ed hardy at November 18, 2009 08:19 PM


My wife has very cute, nice and beautiful feet, and when she wears

his

99.htmlugg-napoule-sandal-c-35.html">ugg mayfaire

boots

after her pedicure I go crazy.

Posted by: dfhtht at November 19, 2009 08:23 PM

We are the best online sales for the china wholesale . Here you can have a large of choices of kinds Ugg Boots,Converse Shoes,Timberland Boots,puma shoes,Nike Shox Shoes ,Nike Dunk SB Shoes,Nike Air Max,Links Of London,Tiffany Jewelry,Dior Handbags?,jimmy choo handbags ,Cartier Watches, 8GB Mp4 Players,Bluetooth Car DVDs. All our cheap online cheap goods are high quality and original packages, and best service. We offer our customers the best service, 7 days arrive at your door.Enjoy your easy and happy shopping with us.

Posted by: cheap goods sale. at November 20, 2009 12:23 AM


louis vuitton has affirmed itself over the past decades as a world leading brand name in the fashion industry.


Throughout their stay as one of the best brands, louis vuitton designer handbags have managed to mesmerize the mass with their style, grace and finesse.

Posted by: lala at November 20, 2009 02:26 AM


louis vuitton has affirmed itself over the past decades as a world leading brand name in the fashion industry.


Throughout their stay as one of the best brands, louis vuitton designer handbags have managed to mesmerize the mass with their style, grace and finesse.

Posted by: hai at November 20, 2009 02:26 AM

Do you like sports? If you like it,the NIke Air Max TN and Nike Air Max 360 is a good choice for you.And now the there is a good news,CheapNike Air Max running Shoes is waiting for you.I think The New Nike Air MAX 2009 Running Shoes makes you great comfortable.

Posted by: Nike Air Max shoes at November 20, 2009 03:40 AM

Do you think I can stay timberland boots uk to become nothing to you ? Do you think I am a timberland boot automaton ? --a discount timberland boots machine without feelings ? and can bear classic timberland boots to have my morsel of bread snatched from my lips, and my drop of kids timberland boots living water dashed from my cup? Do you think, because I am timberland mens shoes poor, obscure, plain, and little, I am soulless and heartless? You think timberland 6 inch boots wrong!--I have as much timberland custom boots soul as you,--and full as much timberland roll top boots heart! And if God had timberland womens shoes gifted me with some beauty and much wealth, I should have made it as hard for you to leave me, as it is now for me to leave you. I am not talking to you now through the medium of timberland hiking boots custom, conventionalities, nor even of mortal flesh.

Posted by: ugg boots at November 22, 2009 11:06 AM

Do you think I can stay timberland boots uk to become nothing to you ? Do you think I am a timberland boot automaton ? --a discount timberland boots machine without feelings ? and can bear classic timberland boots to have my morsel of bread snatched from my lips, and my drop of kids timberland boots living water dashed from my cup? Do you think, because I am timberland mens shoes poor, obscure, plain, and little, I am soulless and heartless? You think timberland 6 inch boots wrong!--I have as much timberland custom boots soul as you,--and full as much timberland roll top boots heart! And if God had timberland womens shoes gifted me with some beauty and much wealth, I should have made it as hard for you to leave me, as it is now for me to leave you. I am not talking to you now through the medium of timberland hiking boots custom, conventionalities, nor even of mortal flesh.

Posted by: ugg boots at November 22, 2009 11:07 AM

Your article is write very well, I like it very much ~
ghd Hair Straightener
ghd Hair Straighteners
ghd straighteners
GHD
hair straighteners
bose in ear headphones
bose on ear headphones
bose headphones
nike sb dunks
nike dunks
I wish you have a wonderful day!Thank you.

Posted by: ghd straighteners at November 22, 2009 08:51 PM

Timeberland boots on sale now! Do you want moreTimeberland boots information?Just move your mouse and press it to our Timberland shoes online store.

Posted by: Timberland uk at November 23, 2009 01:16 AM

Laptop Battery Laptop Battery Laptop Batteries
Laptop Batteries discount laptop battery
discount laptop battery
notebook battery notebook battery
computer battery computer battery
replacement laptop battery replacement laptop battery
notebook batteries notebook batteries

Posted by: Laptop Battery at November 23, 2009 10:17 PM

UGG Classic Cardy

Posted by: asdfeg at November 24, 2009 10:13 PM

[url=http://www.buddyugg.com/ugg-hammond-sandals-c-28.html]UGG Hammond Sandals[/url]
[url=http://www.buddyugg.com/ugg-layback-slipper-c-29.html]UGG Layback Slipper[/url]
[url=http://www.buddyugg.com/ugg-matala-sandal-c-30.htm]Ugg Matala Sandal[/url]
[url=http://www.buddyugg.com/ugg-napoule-sandal-c-31.html]Ugg Napoule Sandal[/url]
[url=http://www.buddyugg.com/ugg-persephone-sandal-c-33.html]Ugg Persephone Sandal[/url]
[url=http://www.buddyugg.com/ugg-baby-boots-c-41.html]UGG Baby Boots[/url]
[url=http://www.buddyugg.com/ugg-bags-c-69.html]UGG Bags[/url]
[url=http://www.buddyugg.com/ugg-gifts-c-61.html]UGG Gifts[/url]

Posted by: [url=http://www.buddyugg.com/]ugg cardy boots[/url] at November 25, 2009 01:59 AM

chaoying nfl jerseys
Troy Polamalu Jersey
Hines Ward Jersey

Posted by: jerseysleague at November 29, 2009 04:29 AM

Paul Smith has been collaborating with a few different organizations recently and his latest venture sees him teaming up with Japanese bicycle saddle, Paul Smith bag, on a limited edition leather saddle. The release features Smith’s signature stripes where only 20 will be available at Paul Smith Clothing store in Japan and 8 at the Floral Street store in London. Get on it quick

Posted by: fasf at November 29, 2009 11:23 AM

Spring is near,every girl wants to be the bride in the special season.They are eager to put on beautiful Wedding Dresses or the Bridal gowns.During the day the Wedding gowns is the good choose,and the night,if you want radiant,you need the Evening gowns.
About the bridesmaid,they have to wear Bridesmaid Dresses in order to avoid grab limelight with the bride.And the Flower Girl has the Flower Girl Dresses,too.In the wedding,the Cocktail Dresses and the Evening Dresses is necessary,too!And remember,the Wedding Dress of the Bridal Dress must be the most glaring!

Posted by: weddingdressclub at December 1, 2009 12:36 AM

It is no doubt that Replica Louis Vuitton Speedy 30 enjoys highest reputation in the world. Louis Vuitton Speedy 30, purses, shoes, watches, clothes, and belts successfully seize loving heart of a majority of people. Speedy 30 is filled with romantic and fantasy, and it is a symbol of noble and high quality of life for gucci ever! Today, let us talk about Tivoli PM.belts have different styles and colors, such as Monogram series belts, Graffiti series belts, both men and women love them crazily. All of them match with various leisure clothes, formal business suits, and beautiful clothes very well. Whenever you wear a Louis Vuitton belt to make your public appearance, you will be naturally concerned and admired by every body. When we talk of high quality, there is no other company to compare with Louis Vuitton Replica Speedy 30. All Louis Vuitton belts adopt top quality cow leather, high quality hard ware, and the color will never be faded. The belts are so durable, and you can wear them to match your clothes for several years. Also, you can clearly see an obvious LV logo as a buckle of each belt.

Posted by: fanqin at December 1, 2009 01:26 AM

ugg boots sale at a time when large heat has set off a winter 08/09 to Ewha.Outlines the

warm wool winter fashion degree to wool crocheted wool ugg boots uk to join after the

body does not stimulate your skin soft, soft comfort UP. Fashion can not without
ugg boots presence in Winter.and ugg boots have many series.such as:
ugg classic
UGG Bailey Button boots
ugg nightfall
ugg kids

Posted by: uggboots at December 2, 2009 08:31 PM
Post a comment









Remember info?




Prove you're human. Type "human":