What is the best practice for hierarchical container – item relationship in a SQL database?

  softwareengineering

I am in the process of designing a database organizing real world items in different storage locations.

One main principle is that items can contain other items.

So the relevant table is:

  • An “items” table in which one column “insideOf” has a FOREIGN KEY restraint to the id of the item containing it.

Setup

the table could look like:

items:

id name insideOf
1 “graue box” 5
2 “rote box” 1
3 “kabel blau” 2
4 “keller”
5 “Regal metall” 4
6 “pappkarton” 5
7 “MacBook Pro” null

My goal is to create item records that include a string path looking like

4/5/1/2

which would be the example for the path of containers of item 3.

I learned so far that i could use a SELECT query with a common table expression like this:

WITH RECURSIVE cte_name(depth,itemid,itemname,itemcontainer) AS(
    SELECT 0, items.id, items.name, items.insideOf -- non-recursive term
        FROM items
        WHERE items.id = '3' -- start item
    UNION
    SELECT depth+1,items.id, items.name,items.insideOf -- recursive term
     FROM cte_name, items
    WHERE items.id=itemcontainer
    AND depth < 5 -- limits depth on request
) SELECT * FROM cte_name;

this works, but delivers me more infos than i need.

So I built a database function getContainerPath that returns only the required path string, that can be then easily queries like

SELECT * FROM getcontainerPath('3')

and looks like:

DECLARE 
 ret TEXT;
BEGIN
    -- QUERY: get all parent items of startitem (reverse tree) and return one value string in path form
    WITH RECURSIVE cte_name(depth,itemid,itemcontainer,path) AS(
        SELECT 0, items.id, items.insideOf, '' -- non-recursive term
            FROM items
            WHERE items.id = startitem -- start item
        UNION
        SELECT depth+1,items.id, items.insideOf, CONCAT_WS('/',itemcontainer,path) -- recursive term
         FROM cte_name, items
        WHERE items.id=itemcontainer
        AND depth < 5 -- limits depth on request 
    ) 
    SELECT path FROM cte_name -- only path
    INTO ret
    WHERE itemcontainer IS NULL -- only last path
    ;RETURN ret;

END;

the actual issue

Works fine as a single query, BUT:

  • items will be queried a LOT. Most item queries will request the parent-child (container-item) tree of this item.
  • Using this function on every standard item query and particular while retrieving lists of items, will quickly get performance heavy
  • I can limit the tree depth to 4 or 5 steps.

Possible Solutions

possible solutions I came up with but am terribly uncertain of:

  1. item CREATES, UPDATES are less common than pure READ queries, yet still fairly common. So I could add the getContainerPath function to CREATE and UPDATE CHECK Event and add an extra column containerPath to the item table containing each items full string path. But then I would have to CHECK the whole old tree as well as the new tree and UPDATE every item accordingly on every UPDATE in the path.
  2. I think I could follow the Nested Set Model described in this article but this also describes a tedious amount of extra work on every item UPDATE, DELETE or CREATE for the left and right neighbour nodes have to be updated. Because items will move a fair amount. I am uncertain if this could ever result in less performance costs than 1. Plus: As a SQL noob and human being I find it extremly hard to read and that will result in faulty queries and functions. And i could only find a tree traversal from the container/parent downwards and am unsure how it would work the other way around in my case.
  3. I could imagine leaving the querying of getContainerPath() to the clients/scripts connecting with the database, to split an item READ query up into 2 distinct queries (one to retrieve basic item info, a second one to retrieve the containerPath if necessary).

I am absolutely unsure if any of those ways would be better or worse for my use case. Maybe I am missing the correct idea or search term to help with this decision?

Or maybe there is a well weathered solution/best practise for the item-container relationship I try to model?

8

LEAVE A COMMENT