Search code examples
mysqltransitive-closure-table

How to get only the first level of depth child nodes?


I am using tree storage. Closure Table pattern.

https://towardsdatascience.com/closure-table-pattern-to-model-hierarchies-in-nosql-c1be6a87e05b

How to get child nodes without grandchildren and great-grandchildren? For example, from ancestor C, get descendants G, H and F.

enter image description here

Below I show the Closure Table database as an example.

DB Closure Table

-- phpMyAdmin SQL Dump
-- version 5.1.0
-- https://www.phpmyadmin.net/
--
-- Host: localhost
-- Generation Time: Aug 02, 2021 at 01:15 PM
-- Server version: 8.0.25
-- PHP Version: 8.0.3

SET SQL_MODE = "NO_AUTO_VALUE_ON_ZERO";
START TRANSACTION;
SET time_zone = "+00:00";


/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
/*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
/*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
/*!40101 SET NAMES utf8mb4 */;

--
-- Database: `closure_table`
--

-- --------------------------------------------------------

--
-- Table structure for table `category_name`
--

CREATE TABLE `category_name` (
  `id` bigint NOT NULL,
  `name` varchar(255) COLLATE utf8mb4_ru_0900_ai_ci DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_ru_0900_ai_ci;

--
-- Dumping data for table `category_name`
--

INSERT INTO `category_name` (`id`, `name`) VALUES
(1, 'Electronics'),
(2, 'Computers'),
(3, 'Accessories & Supplies'),
(4, 'Camera & Photo'),
(5, 'Computer accessories and peripherals'),
(6, 'Computer components'),
(7, 'Audio & Video Accessories'),
(8, 'Camera & Photo Accessories'),
(9, 'Accessories'),
(10, 'Bags & Cases'),
(11, 'Audio & Video Accessories'),
(12, 'Blank Media'),
(13, 'Computer screws'),
(14, 'Table Barebones'),
(15, '3D Glasses'),
(16, 'Antennas'),
(17, 'Accessory Bundles'),
(18, 'Bags & Cases'),
(19, 'Accessory Kits'),
(20, 'Bags & Cases'),
(21, 'Bag & Case Accessories'),
(22, 'Binocular Cases'),
(23, 'Computer headsets'),
(24, 'Computer microphones'),
(25, 'Discs BD-R'),
(26, 'Discs BD-RE'),
(27, 'bolts'),
(28, 'frame'),
(29, 'lamps'),
(30, 'coasters');

-- --------------------------------------------------------

--
-- Table structure for table `tree_path`
--

CREATE TABLE `tree_path` (
  `children` bigint NOT NULL,
  `parent` bigint NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_ru_0900_ai_ci;

--
-- Dumping data for table `tree_path`
--

INSERT INTO `tree_path` (`children`, `parent`) VALUES
(1, 1),
(3, 1),
(4, 1),
(7, 1),
(8, 1),
(9, 1),
(10, 1),
(15, 1),
(16, 1),
(17, 1),
(18, 1),
(19, 1),
(20, 1),
(21, 1),
(22, 1),
(2, 2),
(5, 2),
(6, 2),
(11, 2),
(12, 2),
(13, 2),
(14, 2),
(23, 2),
(24, 2),
(25, 2),
(26, 2),
(27, 2),
(28, 2),
(29, 2),
(30, 2),
(3, 3),
(7, 3),
(8, 3),
(15, 3),
(16, 3),
(17, 3),
(18, 3),
(4, 4),
(9, 4),
(10, 4),
(19, 4),
(20, 4),
(21, 4),
(22, 4),
(5, 5),
(11, 5),
(12, 5),
(23, 5),
(24, 5),
(25, 5),
(26, 5),
(6, 6),
(13, 6),
(14, 6),
(27, 6),
(28, 6),
(29, 6),
(30, 6),
(7, 7),
(15, 7),
(16, 7),
(8, 8),
(17, 8),
(18, 8),
(9, 9),
(19, 9),
(20, 9),
(10, 10),
(21, 10),
(22, 10),
(11, 11),
(23, 11),
(24, 11),
(12, 12),
(25, 12),
(26, 12),
(13, 13),
(27, 13),
(28, 13),
(14, 14),
(29, 14),
(30, 14),
(15, 15),
(16, 16),
(17, 17),
(18, 18),
(19, 19),
(20, 20),
(21, 21),
(22, 22),
(23, 23),
(24, 24),
(25, 25),
(26, 26),
(27, 27),
(28, 28),
(29, 29),
(30, 30);

--
-- Indexes for dumped tables
--

--
-- Indexes for table `category_name`
--
ALTER TABLE `category_name`
  ADD PRIMARY KEY (`id`);

--
-- Indexes for table `tree_path`
--
ALTER TABLE `tree_path`
  ADD PRIMARY KEY (`children`,`parent`),
  ADD KEY `FK_PARENT` (`parent`);

--
-- AUTO_INCREMENT for dumped tables
--

--
-- AUTO_INCREMENT for table `category_name`
--
ALTER TABLE `category_name`
  MODIFY `id` bigint NOT NULL AUTO_INCREMENT, AUTO_INCREMENT=31;

--
-- Constraints for dumped tables
--

--
-- Constraints for table `tree_path`
--
ALTER TABLE `tree_path`
  ADD CONSTRAINT `FK_CHILDREN` FOREIGN KEY (`children`) REFERENCES `category_name` (`id`) ON DELETE CASCADE,
  ADD CONSTRAINT `FK_PARENT` FOREIGN KEY (`parent`) REFERENCES `category_name` (`id`) ON DELETE CASCADE;
COMMIT;

/*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */;
/*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */;
/*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */;

Solution

  • Here's a solution:

    select p1.* from tree_path as p1
    left outer join (tree_path as p2 join tree_path as p3 on p2.children = p3.parent)
     on p2.parent = p1.parent 
     and p3.children = p1.children 
     and p2.parent <> p2.children 
     and p3.parent <> p3.children
    where p1.parent = 3 and p2.parent is NULL;
    +----------+--------+
    | children | parent |
    +----------+--------+
    |        3 |      3 |
    |        7 |      3 |
    |        8 |      3 |
    +----------+--------+
    

    Change the p1.parent=7 and you get this output:

    +----------+--------+
    | children | parent |
    +----------+--------+
    |        7 |      7 |
    |       15 |      7 |
    |       16 |      7 |
    +----------+--------+
    

    Here's the way it works: immediate children are descendants where there is a path from parent to child, but there is no path from parent through a third node to the child. So we try to join to such a path (p2->p3) and if none is found, then all columns of p2 and p3 will be NULL.