четверг, 15 декабря 2011 г.

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

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

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

  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] какие из них отнесены к нужной категории. Ну а далее при движении пользователя по дереву в интерфейсе, можно определять, проходит ли фильтрацию следующий узел или нет.
Единственная сложность в реализации такого дизайна на мой взгляд - нужно аккуратно устанавливать триггеры и внешние ключи.
В посте умышленно используется копипаст (уже говорил). Конечно, приведены не все возможные примеры, которые позволили бы протестировать такой подход в полной мере. Постановку объектов на несколько категорий, замену узлов в дереве, смену категории объекта я оставлю для любопытных.
Естественно, применение такого подхода не ограничено только базой. Все это можно реализовать и в коде приложения.
Ну и конечно же, не делайте циклы в деревьях. Потому что это уже будет не дерево, и есть вероятность впасть в бесконечное выполнение.

9 комментариев:

  1. Насколько я вижу, у тебя тут не дерево, а граф, поскольку [dbo].[Tree] позволяет делать циклы, и даже добавлять несколько графов, которые между собой не соединены. К тому же, ты используешь триггеры AfterInsert и AfterUpdate - они внутри вызывают процедуру с рекурсивным запросом - это означает, что при существовании цикла возможно переполнение рекурсии, и тогда триггеры не отработают. Я видел, что ты об этом написал - просто как вариант, я предлагаю в триггере Before перед добавлением соединения проверять, создаст ли это соединение цикл - и если создаст, то не применять его. И, да, ты же это решение делал под sql server - там с 2008й версии есть иерархический тип данных, почему ты его не использовал? Мне кажется, в данном случае, это было бы уместным.
    з.ы. Убери у картинок теги width и height, чтобы они показывались в натуральный размер - качество будет лучше, они же и так у тебя небольшого размера. Длинные скрипты добавления данных лучше бы заменить скринами таблиц - так нагляднее и листать меньше. А каскадные операторы в определениях таблиц можно вообще не показывать - это только нагромождает код. Лучше готовые скрипты просто приложить в виде файлов к посту.

    ОтветитьУдалить
  2. "И, да, ты же это решение делал под sql server - там с 2008й версии есть иерархический тип данных, почему ты его не использовал? Мне кажется, в данном случае, это было бы уместным"
    Я знаю, что есть иерархический тип данных, но пост о дизайне.
    Конечно, пример можно соптимизировать и улучшить.
    "Длинные скрипты добавления данных лучше бы заменить скринами таблиц - так нагляднее и листать меньше." Не понял, о чем ты тут пишешь. Как это сделать?
    "А каскадные операторы в определениях таблиц можно вообще не показывать - это только нагромождает код." К сожалению, так делать нельзя. Я написал "Единственная сложность в реализации такого дизайна на мой взгляд - нужно аккуратно устанавливать триггеры и внешние ключи." Посмотри внимательнее, не все внешние ключи каскадные. Это часть решения.
    Думаю, если "готовые скрипты просто приложить в виде файлов", то у читателя будет взрыв мозга, и он не поймет о чем речь, либо ему придется постоянно сверять текст с кодом.

    ОтветитьУдалить
  3. "Не понял, о чем ты тут пишешь. Как это сделать?"
    Имел ввиду вместо горы Insert'ов показать скриншот результата селекта на таблицу с данными

    ОтветитьУдалить
  4. "Я знаю, что есть иерархический тип данных, но пост о дизайне."
    Тогда почему бы в таблице [dbo].[Objects] не сделать поле ParentId - почему ты предпочел хранить все связи иерархии в отдельной таблице?

    ОтветитьУдалить
  5. "Имел ввиду вместо горы Insert'ов показать скриншот результата селекта на таблицу с данными"
    Результат селекта на таблицу [Tree] покажет одни идентификаторы. Нечитаемо это. Скриптом гораздо лучше.
    "Тогда почему бы в таблице [dbo].[Objects] не сделать поле ParentId" Одно дело объекты, другое дело связи между ними. Считай SRP нарушается :-)

    ОтветитьУдалить
  6. "Считай SRP нарушается :-) " Ну ты же реализуешь дерево - объекты как бы его ноды. А по поводу SRP - тебя послушать, так стандартный нод дерева wpf просто жестко нарушает все принципы кодекса
    http://msdn.microsoft.com/en-us/library/system.windows.controls.treeviewitem.aspx
    Тут ведь и инфа по родителю, и по чилдам, и методы отрисовки, и события и много чего, что нарушает SRP -но это не мешает разработчикам пользовать данный класс в своих работах. Я просто хочу донести, что кодекс - это не свод жестких правил...

    ОтветитьУдалить
  7. Cтандартный нод дерева wpf не нарушает SRP. Ты что-то путаешь. [dbo].[Objects] не хранит дерева. [dbo].[Objects] хранит какие-то объекты, которые находят свое отражение в прикладной области. Дерево сделано, чтобы показывать объекты иерархично, а не объекты - чтобы было дерево.

    ОтветитьУдалить
  8. А по моему стандарный нод wpf нарушает SRP по полной программе. Достаточно только взглянуть на иерархию наследования - тут тебе и
    DependencyObject, и UIElement, и ItemsControl - а это уже, как минимум, 3 разные обязанности. Но только благодаря этому данный контрол можно использовать разными способами.
    Что касается задачи в твоём посте - ты же сам её написал "Чтобы отобразить такую структуру в коде или хранить ее в базе данных есть старое как мир решение." - то есть у тебя задача хранить древовидную структуру в базе - так что это не объекты с прикладной областью, это вынесенная инфа по нодам из таблицы [dbo].[Tree] в таблицу
    [dbo].[Objects].
    Я понимаю, что твоё решение было бы боее понятно, если бы задача звучала как "построение различного рода отношений, в том числе древоводных, между сущностями" - однако, задача поставлена обратная.

    ОтветитьУдалить
  9. Это именно объекты из прикладной области. Собственно поэтому таблица и называется [dbo].[Objects].
    Надо хранить информацию о нодах - сделай [dbo].[Nodes].
    Если в [dbo].[Objects] добавить столбец [ParentId], таблица не начнет хранить ноды. Она начнет хранить соединения и их названия.

    ОтветитьУдалить