Results 1 to 3 of 3
  1. #1
    Join Date
    Feb 2004
    Posts
    3

    Hierarchy with varying depth?

    I am designing a system to manage products which exist in a hierarchy of categories. Something like:

    Automobiles->Cars->Convertibles->Corvette

    However, I also have:

    Automobies->Other->VW Thing

    In other words, a varying depth of hierarchy. To complicate the issue, each category and object must be able to belong to more than one category.

    I know that there is a not so difficult solution to this - probably in the canonical employee example of a hierarchy of employees and managers but I haven't been able to find it. Whats the good way to do this?

    Thanks so much,
    Alan

  2. #2
    Join Date
    Jan 2004
    Posts
    6

    Re: Hierarchy with varying depth?

    Originally posted by aweissman
    I am designing a system to manage products which exist in a hierarchy of categories. Something like:

    Automobiles->Cars->Convertibles->Corvette

    However, I also have:

    Automobies->Other->VW Thing

    In other words, a varying depth of hierarchy. To complicate the issue, each category and object must be able to belong to more than one category.

    I know that there is a not so difficult solution to this - probably in the canonical employee example of a hierarchy of employees and managers but I haven't been able to find it. Whats the good way to do this?

    Thanks so much,
    Alan
    The typical design would be your base table containing the list of unique products, another table for the list of unique categories with another table that held the hierarchy of categories; that is the relationships between the different categories. Additionally a bridge table would be built between the products and the category table so a product could be placed within more than one category.

    products
    ========
    product_id (PK)
    product_name

    categories
    ==========
    category_id (PK)
    category_name

    categoryHierarchy
    =================
    category_id (PK)
    category_parentId (PK)
    -----------------------
    Additional Constraints:
    FK- categoryHierarchy.category_id references categories.category_id
    FK- categoryHierarchy.category_parentId references categories.category_id
    Check- categoryHierarchy.category_id <> categoryHierarchy.category_parentId

    productCategories
    =================
    product_id (PK)
    category_id (PK)
    -----------------------
    Additional Constraints:
    FK- productCategories.product_id references products.product_id
    FK- productCategories.category_id references categories.category_id

    This is a typical solution to this problem, but depending upon how you will use (query) this information you may need to adjust the model. Current RDBMs don't have good support for handling complex querries against hierarchical structures without a bit of pain.

    Some RDBMSs have implemented vendor specific functionality to perform recursive queries eliminating the necessity to indefinately self-join, however these solutions are typically questionable at best.

    Depending upon how complex of querries you want to do you may want to adjust this model to include a nested set representation of the hierarchy or at lease an extended adjacency list. That is a more complex concept that may be best understood from referencing external articles such as these:

    http://mark.stosberg.com/Bookmarks/D..._on_Tree_data/
    http://users.starpower.net/rjhalljr/...SQL/traer.html

    Alternately, you can peform simple querries against the strucutre outlined above such as the following:

    Any entry in the categories table which does not contain a hierarchy entry with a parent is a root level category. So, if you wanted to return the root level categories you could create a query:
    SELECT
    *
    FROM
    categories
    WHERE
    category_id NOT IN
    (SELECT category_id FROM categoryHierarchy)

    To retrieve an entire hierarchy of categories you must self join the categoryHierarchy table repeatedly, you can imagine a view that would help simplify this.

    If I wanted to return a section of the category hierarchy I could write a query like this:
    SELECT
    root.category_id,
    root.category_name,
    level1.category_id,
    level1.category_name,
    level2.category_id,
    level2.category_name,
    level3.category_id,
    level3.category_name
    FROM
    viewCategoryHierarchy root
    LEFT OUTER JOIN
    viewCategoryHierarchy level1
    ON root.category_id = level1.category_parentId
    LEFT OUTER JOIN
    viewCategoryHierarchy level2
    ON level1.category_id = level2.category_parentId
    LEFT OUTER JOIN
    viewCategoryHierarchy level3
    ON level2.category_id = level3.category_parentId

    You can now imagine extending this to view the products in a given level of the hierarchy. Two issues should soon become apparent, the requirement for outer joins since we unsure how many levels of categories exists and the need for a number of joins equal to the number of levels in the hierarchy (including the root).

    Alternately depending upon how your application will use this information you could choose to display only the root level categories, and when a user expands a given category, retrieve only its' children. In this way a single procedure could be used to fill in the application representation of the category hierarchy as needed.

  3. #3
    Join Date
    Feb 2004
    Posts
    2

    Thumbs up

    This I very informing and an anser to my post (http://www.dbforums.com/t981236.html), thanks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •