Finding the lowest node in a given sub-tree of hierarchical data

Question

Consider a database with these three tables:

category:

cat_id  name        parent_id
-----------------------
1       drinks      0
2       carbonated  1
3       cola        2
4       water       1
5       rc-cola     3

product:

prod_id  name           default_cat
-----------------------------------
1        cola-zero      2
2        mineral water  4

cat_prod:

cat_id  prod_id
---------------
1       1
2       1
3       1
4       2

We have category hierarchy and a product, which may belong to several categories.

Also, each product has a default category. In this case cola-zero product has default category 2 - carbonated, which is a mistake. Default category has to be 3 - cola. I.e., the lowest category in the category tree. However, I may consider only a subset of the category tree: only those categories that the product belongs to.

I need to update the default category of each product in the product table and ensure that product's default category is the most "defined" one, i.e., the lowest for a given product.

I can write a script, which would retrieve all categories, build the tree in memory and then for each product check the default category against this tree. But I hope there is a smarter way to do this via SQL only.

Is it even possible to do it in pure SQL?

Thanks.

What's wrong with your approach? You are trying to fix records in the db so this is a once in a lifetime (hopefully) kind of thing. I think you are fine. You could also write a stored procedure to do the same kind of thing. — Alex, Mar 12 '14 at 06:49
not sure if it helps directly, but see http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ — Barmar, Mar 12 '14 at 06:50
@Alex, there is nothing wrong with this approach, but it's more complex. It requires a script interpreter to be available, DB connectivity being set up, and more code to write. With a pure SQL solution the query can be just pasted into phpMyAdmin form from anywhere without any prior setup. I'll use the script though if I fail to come up with something practical. — Alex Blekhman, Mar 12 '14 at 11:30
@Barmar, thanks for the link. Looks very promising. I'll try to make it work, then post solution here. — Alex Blekhman, Mar 12 '14 at 11:31
@AlexBlekhman Fair point. I usually use SPs but it all depends on what tools you have available. — Alex, Mar 12 '14 at 11:51

Alex Blekhman · Accepted Answer · 2014-05-04T10:55:51.337

I finally solved it. A bit dirty, since I have to create a temporary table to hold intermediate results, but it works.

Here is the full code:

-- schema
CREATE TABLE category
(
  cat_id INT NOT NULL,
  name VARCHAR(255) NOT NULL,
  parent_id INT NOT NULL,
  PRIMARY KEY (cat_id)
);

GO

CREATE TABLE product
(
  prod_id INT NOT NULL,
  name VARCHAR(255) NOT NULL,
  default_cat INT NOT NULL,
  PRIMARY KEY (prod_id)
);

GO

CREATE TABLE cat_prod
(
  cat_id INT NOT NULL,
  prod_id INT NOT NULL,
  PRIMARY KEY (cat_id, prod_id),
  FOREIGN KEY (cat_id) REFERENCES category(cat_id),
  FOREIGN KEY (prod_id) REFERENCES product(prod_id)
);

GO

-- data
INSERT INTO category (cat_id, name, parent_id)
VALUES
  (1, 'drinks', 0),
  (2, 'carbonated', 1),
  (3, 'cola', 2),
  (4, 'water', 1),
  (5, 'rc-cola', 3)
;

GO

INSERT INTO product (prod_id, name, default_cat)
VALUES
  (1, 'cola-zero', 2), -- this is a mistake! must be 3
  (2, 'mineral water', 4) -- this one should stay intact
;

GO

INSERT INTO cat_prod (cat_id, prod_id)
VALUES
  (1, 1),
  (2, 1),
  (3, 1),
  (4, 2),
  (4, 1)
;

GO

-- stored proc
CREATE PROCEDURE iterate_products()
BEGIN
    DECLARE prod_id INT;
    DECLARE default_cat INT;
    DECLARE new_default_cat INT;
    DECLARE done INT DEFAULT FALSE;
    DECLARE cur CURSOR FOR SELECT p.prod_id, p.default_cat FROM product p;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

    -- temporary table to hold the category subtree for a given product
    CREATE TABLE IF NOT EXISTS tmp_category_sub_tree
    (
        cat_id INT NOT NULL,
        parent_id INT NOT NULL
    );

    OPEN cur;

    UPDATE_LOOP: LOOP
        FETCH cur INTO prod_id, default_cat;
        IF done THEN
            LEAVE UPDATE_LOOP;
        END IF;

        TRUNCATE TABLE tmp_category_sub_tree;

        -- select all cateries this products belongs to
        INSERT INTO tmp_category_sub_tree (cat_id, parent_id)
            SELECT category.cat_id, category.parent_id
            FROM category
            INNER JOIN cat_prod
              ON category.cat_id = cat_prod.cat_id
            WHERE
              cat_prod.prod_id = prod_id;

        -- select a leaf (only one)
        SELECT t1.cat_id FROM
            tmp_category_sub_tree AS t1 LEFT JOIN tmp_category_sub_tree AS t2
        ON t1.cat_id = t2.parent_id
        WHERE
            t2.cat_id IS NULL
        LIMIT 1
        INTO NEW_DEFAULT_CAT;

        -- update product record, if required
        IF default_cat != new_default_cat THEN
            UPDATE product
            SET default_cat = new_default_cat
            WHERE
                product.prod_id = prod_id;
        END IF;

    END LOOP;

    CLOSE cur;

    DROP TABLE tmp_category_sub_tree;
END;

GO

Here is the SQLFiddle link: http://sqlfiddle.com/#!2/98a45/1

score 0 · Answer 2 · edited May 23 '17 at 12:21

0

If you store the hierarchy in a Closure Table, it's really easy to find the lowest node(s) in the tree:

SELECT c.descendant FROM closure c
JOIN (SELECT MAX(pathlength) AS pathlength FROM closure) x USING (pathlength);

Finding the lowest node of a subtree, you just need to be specific about the starting node of the branch you want to search:

SELECT c.descendant FROM closure c
JOIN (SELECT MAX(pathlength) AS pathlength FROM closure) x USING (pathlength)
WHERE c.ancestor = 2;

edited May 23 '17 at 12:21

Community

1
1

answered Mar 14 '14 at 00:57

Bill Karwin

538,548
86
673
828

Thanks for the answer. The closure tables methods looks neat. I'll definitely use it in the future. – Alex Blekhman Mar 15 '14 at 23:45

Finding the lowest node in a given sub-tree of hierarchical data

2 Answers2