Быстрый фильтр дерева

Очень часто можно встретить в интерфейсе какого-либо приложения дерево. Это могут быть папки и файлы в проводнике или какие-то специфические объекты, связанные друг с другом. Например, если объекты могут быть вложены друг в друга, то такую связь и навигацию по объектам очень удобно представить в виде иерархии в интерфейсе вашего веб приложения.
Чтобы отобразить такую структуру в коде или хранить ее в базе данных есть старое как мир решение.
Но все меняется, когда дерево большое, а объекты могут быть помечены какими либо внешними атрибутами (через ассоциации). Я покажу пример, как фильтровать дерево по атрибутам объектов с сохранением иерархии (если есть дочерний объект с заданным атрибутом, то объект показывается). Ограничимся только базой данных.

Определим дерево объектов в базе.

1. CREATE TABLE [dbo].[Objects] (
2.  [Id] uniqueidentifier CONSTRAINT [DF_Objects_Id] DEFAULT newid() NOT NULL,
3.  [Name] nvarchar(max) COLLATE Cyrillic_General_CI_AS NOT NULL,
4.  CONSTRAINT [PK_Objects] PRIMARY KEY CLUSTERED ([Id])
5. )
6. ON [PRIMARY]
7. GO
8.  
9. CREATE TABLE [dbo].[Tree] (
10.  [ParentObjectId] uniqueidentifier NULL,
11.  [ObjectId] uniqueidentifier NOT NULL,
12.  CONSTRAINT [Tree_Object] FOREIGN KEY ([ObjectId])
13.  REFERENCES [dbo].[Objects] ([Id])
14.  ON UPDATE NO ACTION
15.  ON DELETE NO ACTION,
16.  CONSTRAINT [Tree_ParentObject] FOREIGN KEY ([ParentObjectId])
17.  REFERENCES [dbo].[Objects] ([Id])
18.  ON UPDATE CASCADE
19.  ON DELETE CASCADE
20. )
21. ON [PRIMARY]
22. GO

* This source code was highlighted with Source Code Highlighter.

Обращаться с таким деревом легко. Можно получить корневые узлы, и далее по ходу движения пользователя подгружать динамически все дерево.
Часто объекты в дереве отличаются друг от друга на какое-то значение, взятое из справочника.

1. CREATE TABLE [dbo].[Categories] (
2.  [Id] int IDENTITY(1, 1) NOT NULL,
3.  [Name] nvarchar(max) COLLATE Cyrillic_General_CI_AS NOT NULL,
4.  CONSTRAINT [PK_Category] PRIMARY KEY CLUSTERED ([Id])
5. )
6. ON [PRIMARY]
7. GO
8.  
9. CREATE TABLE [dbo].[ObjectsCategories] (
10.  [ObjectId] uniqueidentifier NOT NULL,
11.  [CategoryId] int NOT NULL,
12.  [ObjectCategoryId] uniqueidentifier CONSTRAINT [DF_ObjectsCategories] DEFAULT newid() NOT NULL,
13.  CONSTRAINT [ObjectsCategories_pk] PRIMARY KEY CLUSTERED ([ObjectCategoryId]),
14.  CONSTRAINT [ObjectsCategories_Category] FOREIGN KEY ([CategoryId])
15.  REFERENCES [dbo].[Categories] ([Id])
16.  ON UPDATE CASCADE
17.  ON DELETE CASCADE,
18.  CONSTRAINT [ObjectsCategories_Object] FOREIGN KEY ([ObjectId])
19.  REFERENCES [dbo].[Objects] ([Id])
20.  ON UPDATE CASCADE
21.  ON DELETE CASCADE
22. )
23. ON [PRIMARY]
24. GO

* This source code was highlighted with Source Code Highlighter.

Таким образом, все объекты можно отфильтровать по категориям. Не сохраняя структуры дерева, можно даже показать результат фильтрации в иерархическом виде. Сложности будут, когда понадобится показать дерево для какой-то категории, сохраняя его структуру. Например, для категории 1 дерево в интерфейсе должно содержать все ветви, оканчивающиеся объектами с такой категорией. То есть для объекта категории 1 в интерфейсе должна присутствовать ветвь от этого объекта до корневого. Пользователь, естественно, должен иметь возможность просмотреть эту ветвь в другом направлении: от корневого до узла категории 1.
Если объектов очень много, то решение в лоб будет работать очень медленно. При движении пользователя от корневого узла по ветвям в интерфейсе будет приводить к проверке дочерних узлов на наличие объектов с нужной категорией. Если эта категория будет у последнего объекта в последней ветви, то алгоритм пройдет по всем объектам в базе.
Одно из решений - чтобы избавиться от тормозов поиска по дереву, придется принести в жертву объем базы. Сделаем таблицу, в которой будем хранить ветви поиска для каждой категории.

1. CREATE TABLE [dbo].[ReverseTree] (
2.  [ObjectId] uniqueidentifier NOT NULL,
3.  [ChildObjectId] uniqueidentifier NULL,
4.  [ObjectCategoryId] uniqueidentifier NOT NULL,
5.  CONSTRAINT [ReverseTree_ChildObject] FOREIGN KEY ([ChildObjectId])
6.  REFERENCES [dbo].[Objects] ([Id])
7.  ON UPDATE NO ACTION
8.  ON DELETE NO ACTION,
9.  CONSTRAINT [ReverseTree_Object] FOREIGN KEY ([ObjectId])
10.  REFERENCES [dbo].[Objects] ([Id])
11.  ON UPDATE NO ACTION
12.  ON DELETE NO ACTION,
13.  CONSTRAINT [ReverseTree_ObjectCategory] FOREIGN KEY ([ObjectCategoryId])
14.  REFERENCES [dbo].[ObjectsCategories] ([ObjectCategoryId])
15.  ON UPDATE CASCADE
16.  ON DELETE CASCADE
17. )
18. ON [PRIMARY]
19. GO

* This source code was highlighted with Source Code Highlighter.

Тут следует пояснить, как мы будем использовать эту таблицу. [ObjectId] и [ChildObjectId] используются для  хранения ветвей. [ObjectCategoryId] будет одинаково для всей ветви и будет указывать на причину возникновения такой ветви - запись в [ObjectsCategories].
Основная идея в том, чтобы хранить эти ветви не от корня, а от листового объекта, для которого установлена категория. Создадим функцию, чтобы получать такую ветвь из дерева.

1. CREATE FUNCTION dbo.CreateReverseTreeForObject
2. ( @ObjectId UNIQUEIDENTIFIER, @ChildObjectId UNIQUEIDENTIFIER)
3. RETURNS TABLE
4. AS
5. RETURN
6. WITH ObjectTree (ObjectId, ChildObjectId)
7. AS
8. (
9.   SELECT
10.    t.ObjectId
11.   , @ChildObjectId
12.   FROM [Tree] t
13.   WHERE t.ObjectId = @ObjectId
14.   
15.   UNION ALL
16.   
17.   SELECT
18.    t.ParentObjectId
19.   , t.ObjectId
20.   FROM [Tree] t
21.   INNER JOIN ObjectTree ot ON ot.ObjectId = t.ObjectId
22. )
23. SELECT * FROM ObjectTree

* This source code was highlighted with Source Code Highlighter.

Параметр функции @ObjectId указывает на узел, с которого нужно генерировать обратную ветвь, а @ChildObjectId используется только для того, чтобы вызывающий код мог подставить дочерний узел для первого узла в обратной ветви.
Чтобы поддерживать дополнительную таблицу в актуальном состоянии потребуется описать триггеры вставки и обновления для таблицы ObjectsCategories. Триггер добавления выглядит так:

1. CREATE TRIGGER [dbo].[ObjectsCategories_AfterInsert] ON [dbo].[ObjectsCategories]
2. WITH EXECUTE AS CALLER
3. FOR INSERT
4. AS
5. BEGIN
6.  
7.   DECLARE @ObjectCategoryId UNIQUEIDENTIFIER;
8.   DECLARE @ObjectId UNIQUEIDENTIFIER;
9.   DECLARE @CategoryId INT;
10.   
11.   SELECT
12.    @ObjectCategoryId = ins.ObjectCategoryId
13.   , @ObjectId = ins.ObjectId
14.   , @CategoryId = ins.CategoryId
15.   FROM inserted ins
16.   
17.   INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
18.   SELECT
19.    crto.ObjectId
20.   , crto.ChildObjectId
21.   , @ObjectCategoryId
22.   FROM dbo.CreateReverseTreeForObject(@ObjectId, CONVERT(UNIQUEIDENTIFIER, NULL)) crto
23.  
24. END
25. GO

* This source code was highlighted with Source Code Highlighter.

Триггер для смены категории узла и переноса категории от одного узла к другому:

1. CREATE TRIGGER [dbo].[ObjectsCategories_AfterUpdate] ON [dbo].[ObjectsCategories]
2. WITH EXECUTE AS CALLER
3. FOR UPDATE
4. AS
5. BEGIN
6.  
7.   DECLARE @ObjectCategoryId UNIQUEIDENTIFIER;
8.   
9.   SELECT
10.    @ObjectCategoryId = del.ObjectCategoryId
11.   FROM deleted del
12.   
13.   DELETE rt FROM [ReverseTree] rt
14.   WHERE rt.ObjectCategoryId = @ObjectCategoryId
15.   
16.   DECLARE @ObjectId UNIQUEIDENTIFIER;
17.   DECLARE @CategoryId INT;
18.   
19.   SELECT
20.    @ObjectCategoryId = ins.ObjectCategoryId
21.   , @ObjectId = ins.ObjectId
22.   , @CategoryId = ins.CategoryId
23.   FROM inserted ins
24.   
25.   INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
26.   SELECT
27.    crto.ObjectId
28.   , crto.ChildObjectId
29.   , @ObjectCategoryId
30.   FROM dbo.CreateReverseTreeForObject(@ObjectId) crto
31.  
32. END
33. GO

* This source code was highlighted with Source Code Highlighter.

Однако, мы не учли, как на нашей дополнительной таблице должно сказываться изменение настоящего дерева из таблицы [Tree]. Придется и на эту таблицу наложить триггеры. Триггер соединения двух частей дерева получится таким

1. CREATE TRIGGER [dbo].[Tree_AfterInsert] ON [dbo].[Tree]
2. WITH EXECUTE AS CALLER
3. FOR INSERT
4. AS
5. BEGIN
6.  
7.   DECLARE @ObjectId UNIQUEIDENTIFIER;
8.   DECLARE @ParentObjectId UNIQUEIDENTIFIER;
9.   
10.   SELECT
11.    @ObjectId = ins.ObjectId
12.   , @ParentObjectId = ins.ParentObjectId
13.   FROM inserted ins
14.  
15.   INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
16.   SELECT
17.    crto.ObjectId
18.   , crto.ChildObjectId
19.   , rt.ObjectCategoryId
20.   FROM dbo.CreateReverseTreeForObject(@ParentObjectId, @ObjectId) crto,
21.   [ReverseTree] rt
22.   WHERE rt.ObjectId = @ObjectId
23. END
24. GO

* This source code was highlighted with Source Code Highlighter.

То есть будет достаточно получить полную ветвь от места соединения умножить на количество ветвей, в которых участвует подключаемый узел.
Триггер удаления соединения в дереве:

1. CREATE TRIGGER [dbo].[Tree_AfterDelete] ON [dbo].[Tree]
2. WITH EXECUTE AS CALLER
3. FOR DELETE
4. AS
5. BEGIN
6.  
7.   DECLARE @ObjectId UNIQUEIDENTIFIER;
8.   DECLARE @ParentObjectId UNIQUEIDENTIFIER;
9.   
10.   SELECT
11.    @ObjectId = del.ObjectId
12.   , @ParentObjectId = del.ParentObjectId
13.   FROM deleted del
14.  
15.   DELETE rt FROM [ReverseTree] rt
16.   INNER JOIN dbo.GetReverseBranchFromObjects(@ParentObjectId, @ObjectId) grbo
17.       ON rt.ObjectId = grbo.ObjectId
18.       AND rt.ChildObjectId = grbo.ChildObjectId
19.       AND rt.ObjectCategoryId = grbo.ObjectCategoryId
20. END
21. GO

* This source code was highlighted with Source Code Highlighter.

Где функция dbo.GetReverseBranchFromObjects будет генерировать все ветви, начиная с определенного листа:

1. CREATE FUNCTION dbo.GetReverseBranchFromObjects
2. ( @ObjectId UNIQUEIDENTIFIER, @ChildObjectId UNIQUEIDENTIFIER)
3. RETURNS TABLE
4. AS
5. RETURN
6. WITH ObjectTree (ObjectId, ChildObjectId, ObjectCategoryId)
7. AS
8. (
9.   SELECT
10.    rt.ObjectId
11.   , rt.ChildObjectId
12.   , rt.ObjectCategoryId
13.   FROM [ReverseTree] rt
14.   WHERE rt.ObjectId = @ObjectId
15.    AND (rt.ChildObjectId = @ChildObjectId)
16.   
17.   UNION ALL
18.   
19.   SELECT
20.    rt.ObjectId
21.   , rt.ChildObjectId
22.   , rt.ObjectCategoryId
23.   FROM [ReverseTree] rt
24.   INNER JOIN ObjectTree ot
25.       ON ot.ObjectId = rt.ChildObjectId
26.       AND ot.ObjectCategoryId = rt.ObjectCategoryId
27. )
28. SELECT * FROM ObjectTree

* This source code was highlighted with Source Code Highlighter.

Нужно отметить, что эта функция не ожидает, что в качестве последнего параметра может прийти NULL. Если это требуется, то читатель сам может обновить функцию. Триггер использует эту функцию с заполненными параметрами. Оно и понятно, ведь для удаления соединения используются два объекта. Сложим оба триггера и получим триггер смены подключения.

1. CREATE TRIGGER [dbo].[Tree_AfterUpdate] ON [dbo].[Tree]
2. WITH EXECUTE AS CALLER
3. FOR UPDATE
4. AS
5. BEGIN
6.  
7.   DECLARE @ObjectId UNIQUEIDENTIFIER;
8.   DECLARE @ParentObjectId UNIQUEIDENTIFIER;
9.   
10.   SELECT
11.    @ObjectId = del.ObjectId
12.   , @ParentObjectId = del.ParentObjectId
13.   FROM deleted del
14.  
15.   DELETE rt FROM [ReverseTree] rt
16.   INNER JOIN dbo.GetReverseBranchFromObjects(@ParentObjectId, @ObjectId) grbo
17.       ON rt.ObjectId = grbo.ObjectId
18.       AND rt.ChildObjectId = grbo.ChildObjectId
19.       AND rt.ObjectCategoryId = grbo.ObjectCategoryId
20.   
21.   SELECT
22.    @ObjectId = ins.ObjectId
23.   , @ParentObjectId = ins.ParentObjectId
24.   FROM inserted ins
25.  
26.   INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
27.   SELECT
28.    crto.ObjectId
29.   , crto.ChildObjectId
30.   , rt.ObjectCategoryId
31.   FROM dbo.CreateReverseTreeForObject(@ParentObjectId, @ObjectId) crto,
32.   [ReverseTree] rt
33.   WHERE rt.ObjectId = @ObjectId
34.  
35. END
36. GO

* This source code was highlighted with Source Code Highlighter.

Да, товарищи, копипаст. Пример все таки демонстрирует более дизайн решения, так что оставим все в удобочитаемом виде, чтобы не ссылать читателя к разрозненным функциям.
Введем тестовые данные для проверки. Должно получиться вот такое вот дерево

Рисунок 1.

Узел Point будет иметь категорию Red, Sphere - Green, Tangens - Blue, Cosinus - Black. На узле цветами, соответствующими примененным категориям показаны ветви, которые должны быть в вспомогательной таблице [ReverseTree]. Запустим скрипт с исходными данными

1. DELETE FROM [Tree]
2. GO
3.  
4. DELETE FROM [ReverseTree]
5. GO
6.  
7. DELETE FROM [ObjectsCategories]
8. GO
9.  
10. DELETE FROM [Categories]
11. GO
12.  
13. DELETE FROM [Objects]
14. GO
15.  
16. INSERT INTO [Categories] ([Name]) VALUES ('Red')
17. GO
18.  
19. INSERT INTO [Categories] ([Name]) VALUES ('Blue')
20. GO
21.  
22. INSERT INTO [Categories] ([Name]) VALUES ('Green')
23. GO
24.  
25. INSERT INTO [Categories] ([Name]) VALUES ('Black')
26. GO
27.  
28. INSERT INTO [Objects] ([Name]) VALUES ('Cube')
29. GO
30.  
31. INSERT INTO [Objects] ([Name]) VALUES ('Ellipsis')
32. GO
33.  
34. INSERT INTO [Objects] ([Name]) VALUES ('Sphere')
35. GO
36.  
37. INSERT INTO [Objects] ([Name]) VALUES ('Line')
38. GO
39.  
40. INSERT INTO [Objects] ([Name]) VALUES ('Point')
41. GO
42.  
43. INSERT INTO [Objects] ([Name]) VALUES ('Polyline')
44. GO
45.  
46. INSERT INTO [Objects] ([Name]) VALUES ('Radius')
47. GO
48.  
49. INSERT INTO [Objects] ([Name]) VALUES ('Diameter')
50. GO
51.  
52. INSERT INTO [Objects] ([Name]) VALUES ('Sinus')
53. GO
54.  
55. INSERT INTO [Objects] ([Name]) VALUES ('Cosinus')
56. GO
57.  
58. INSERT INTO [Objects] ([Name]) VALUES ('Tangens')
59. GO
60.  
61. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
62. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cube'),
63.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Ellipsis'))
64. GO
65.  
66. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
67. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cube'),
68.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere'))
69. GO
70.  
71. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
72. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Ellipsis'),
73.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Line'))
74. GO
75.  
76. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
77. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Ellipsis'),
78.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Point'))
79. GO
80.  
81. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
82. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere'),
83.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Polyline'))
84. GO
85.  
86. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
87. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius'),
88.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Diameter'))
89. GO
90.  
91. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
92. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius'),
93.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sinus'))
94. GO
95.  
96. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
97. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sinus'),
98.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cosinus'))
99. GO
100.  
101. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
102. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sinus'),
103.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Tangens'))
104. GO
105.  
106. INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
107. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Point'),
108.     (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Red'))
109. GO
110.  
111. INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
112. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere'),
113.     (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Green'))
114. GO
115.  
116. INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
117. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Tangens'),
118.     (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Blue'))
119. GO
120.  
121. INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
122. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Line'),
123.     (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius'))
124. GO
125.  
126. INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
127. VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cosinus'),
128.     (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Black'))
129. GO

* This source code was highlighted with Source Code Highlighter.

Как видно из представленного скрипта, сначала генерируются справочные данные - объекты и категории. Потом начинаем строить дерево. Делаем сначала два сегмента.

Рисунок 2.

Назначаем для узлов Point, Sphere и Tangens нужные категории.
После соединяем узлы Line и Radius. Для узла Cosinus назначаем категорию Black.
При помощи нехитрого скрипта, проверим, какие ветви есть в вспомогательной таблице.

1. SELECT
2.  (SELECT o.[Name] FROM [Objects] o WHERE o.Id = rt.ObjectId) AS 'Object'
3. , (SELECT o.[Name] FROM [Objects] o WHERE o.Id = rt.ChildObjectId) AS 'ChildObject'
4. , (SELECT c.[Name] FROM [ObjectsCategories] oc
5.   INNER JOIN [Categories] c ON c.Id = oc.CategoryId
6.   WHERE oc.ObjectCategoryId = rt.ObjectCategoryId) AS 'Category'
7. , (SELECT o.[Name] FROM [ObjectsCategories] oc
8.   INNER JOIN [Objects] o ON o.Id = oc.ObjectId
9.   WHERE oc.ObjectCategoryId = rt.ObjectCategoryId) AS 'Source Object'
10. FROM [ReverseTree] rt

* This source code was highlighted with Source Code Highlighter.

Вывод:

Source Object - объект, для которого установлена соотвествтующая категория в основной таблице ObjectsCategories. В дополнительной таблице установлены корректные данные. Таким образом, мы получили ветви, которые были обозначены на Рисунке 1.
Удалим связь между узлами Line и Radius.

1. DELETE t FROM [Tree] t
2. WHERE t.ObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius')
3.  AND t.ParentObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Line')

* This source code was highlighted with Source Code Highlighter.

Состояние вспомогательной таблицы:

Собственно, вернулись к варианту, представленному на Рисунке 2.
Удалим категории у некоторых объектов

1. DELETE oc FROM [ObjectsCategories] oc
2. WHERE oc.CategoryId = (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Blue')
3.  AND oc.ObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Tangens')
4.  
5. DELETE oc FROM [ObjectsCategories] oc
6. WHERE oc.CategoryId = (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Green')
7.  AND oc.ObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere')

* This source code was highlighted with Source Code Highlighter.

Во вспомогательной таблице [ReverseTree]

Таким образом, Green и Blue ветви удалились каскадно.

Как использовать на практике такой механизм. Представьте, что пользователь отфильтровал наше дерево (рис. 1) по синему фильтру. Можно либо сразу получить все дерево по заданному фильтру при помощи [ReverseTree] и [ObjectsCategories]. Либо можно найти корневые узлы в таблице [Tree] и узнать опять же при помощи [ReverseTree] и [ObjectsCategories] какие из них отнесены к нужной категории. Ну а далее при движении пользователя по дереву в интерфейсе, можно определять, проходит ли фильтрацию следующий узел или нет.
Единственная сложность в реализации такого дизайна на мой взгляд - нужно аккуратно устанавливать триггеры и внешние ключи.
В посте умышленно используется копипаст (уже говорил). Конечно, приведены не все возможные примеры, которые позволили бы протестировать такой подход в полной мере. Постановку объектов на несколько категорий, замену узлов в дереве, смену категории объекта я оставлю для любопытных.
Естественно, применение такого подхода не ограничено только базой. Все это можно реализовать и в коде приложения.
Ну и конечно же, не делайте циклы в деревьях. Потому что это уже будет не дерево, и есть вероятность впасть в бесконечное выполнение.