Category Hierarchy

Solution¶

To model a product category hierarchy, this solution keeps each category in its own document that also has a list of its ancestors or “parents.” This document uses music genres as the basis of its examples:

Initial category hierarchy

Because these kinds of categories change infrequently, this model focuses on the operations needed to keep the hierarchy up-to-date rather than the performance profile of update operations.

Schema¶

This schema has the following properties:

• A single document represents each category in the hierarchy.
• An ObjectId identifies each category document for internal cross-referencing.
• Each category document has a human-readable name and a URL compatible slug field.
• The schema stores a list of ancestors for each category to facilitate displaying a query and its ancestors using only a single query.

Consider the following prototype:

{ "_id" : ObjectId("4f5ec858eb03303a11000002"),
  "name" : "Modal Jazz",
  "parent" : ObjectId("4f5ec858eb03303a11000001"),
  "slug" : "modal-jazz",
  "ancestors" : [
         { "_id" : ObjectId("4f5ec858eb03303a11000001"),
        "slug" : "bop",
        "name" : "Bop" },
         { "_id" : ObjectId("4f5ec858eb03303a11000000"),
           "slug" : "ragtime",
           "name" : "Ragtime" } ]
}

Read and Display a Category¶

category = db.categories.find(
    {'slug':slug},
    {'_id':0, 'name':1, 'ancestors.slug':1, 'ancestors.name':1 })

>>> db.categories.ensure_index('slug', unique=True)

Add a Category to the Hierarchy¶

To add a category you must first determine its ancestors. Take adding a new category “Swing” as a child of “Ragtime”, as below:

Adding a category

The insert operation would be trivial except for the ancestors. To define this array, consider the following helper function:

def build_ancestors(_id, parent_id):
    parent = db.categories.find_one(
        {'_id': parent_id},
        {'name': 1, 'slug': 1, 'ancestors':1})
    parent_ancestors = parent.pop('ancestors')
    ancestors = [ parent ] + parent_ancestors
    db.categories.update(
        {'_id': _id},
        {'$set': { 'ancestors': ancestors } })

You only need to travel “up” one level in the hierarchy to get the ancestor list for “Ragtime” that you can use to build the ancestor list for “Swing.” Then create a document with the following set of operations:

doc = dict(name='Swing', slug='swing', parent=ragtime_id)
swing_id = db.categories.insert(doc)
build_ancestors(swing_id, ragtime_id)

Change the Ancestry of a Category¶

This section address the process for reorganizing the hierarchy by moving “bop” under “swing” as follows:

Change the parent of a category

db.categories.update(
    {'_id':bop_id}, {'$set': { 'parent': swing_id } } )

def build_ancestors_full(_id, parent_id):
    ancestors = []
    while parent_id is not None:
        parent = db.categories.find_one(
            {'_id': parent_id},
            {'parent': 1, 'name': 1, 'slug': 1, 'ancestors':1})
        parent_id = parent.pop('parent')
        ancestors.append(parent)
    db.categories.update(
        {'_id': _id},
        {'$set': { 'ancestors': ancestors } })

for cat in db.categories.find(
    {'ancestors._id': bop_id},
    {'parent_id': 1}):
    build_ancestors_full(cat['_id'], cat['parent_id'])

db.categories.ensure_index('ancestors._id')

Rename a Category¶

To a rename a category you need to both update the category itself and also update all the descendants. Consider renaming “Bop” to “BeBop” as in the following figure:

Rename a category

First, you need to update the category name with the following operation:

db.categories.update(
    {'_id':bop_id}, {'$set': { 'name': 'BeBop' } } )

Next, you need to update each descendant’s ancestors list:

db.categories.update(
    {'ancestors._id': bop_id},
    {'$set': { 'ancestors.$.name': 'BeBop' } },
    multi=True)

This operation uses:

• the positional operation $ to match the exact “ancestor” entry that matches the query, and
• the multi option to update all documents that match this query.