Очень часто можно встретить в интерфейсе какого-либо приложения дерево. Это могут быть папки и файлы в проводнике или какие-то специфические объекты, связанные друг с другом. Например, если объекты могут быть вложены друг в друга, то такую связь и навигацию по объектам очень удобно представить в виде иерархии в интерфейсе вашего веб приложения.
Чтобы отобразить такую структуру в коде или хранить ее в базе данных есть старое как мир решение.
Но все меняется, когда дерево большое, а объекты могут быть помечены какими либо внешними атрибутами (через ассоциации). Я покажу пример, как фильтровать дерево по атрибутам объектов с сохранением иерархии (если есть дочерний объект с заданным атрибутом, то объект показывается). Ограничимся только базой данных.
Определим дерево объектов в базе.
Часто объекты в дереве отличаются друг от друга на какое-то значение, взятое из справочника.
Если объектов очень много, то решение в лоб будет работать очень медленно. При движении пользователя от корневого узла по ветвям в интерфейсе будет приводить к проверке дочерних узлов на наличие объектов с нужной категорией. Если эта категория будет у последнего объекта в последней ветви, то алгоритм пройдет по всем объектам в базе.
Одно из решений - чтобы избавиться от тормозов поиска по дереву, придется принести в жертву объем базы. Сделаем таблицу, в которой будем хранить ветви поиска для каждой категории.
Основная идея в том, чтобы хранить эти ветви не от корня, а от листового объекта, для которого установлена категория. Создадим функцию, чтобы получать такую ветвь из дерева.
Чтобы поддерживать дополнительную таблицу в актуальном состоянии потребуется описать триггеры вставки и обновления для таблицы ObjectsCategories. Триггер добавления выглядит так:
Триггер удаления соединения в дереве:
Введем тестовые данные для проверки. Должно получиться вот такое вот дерево
Узел Point будет иметь категорию Red, Sphere - Green, Tangens - Blue, Cosinus - Black. На узле цветами, соответствующими примененным категориям показаны ветви, которые должны быть в вспомогательной таблице [ReverseTree]. Запустим скрипт с исходными данными
Назначаем для узлов Point, Sphere и Tangens нужные категории.
После соединяем узлы Line и Radius. Для узла Cosinus назначаем категорию Black.
При помощи нехитрого скрипта, проверим, какие ветви есть в вспомогательной таблице.
Source Object - объект, для которого установлена соотвествтующая категория в основной таблице ObjectsCategories. В дополнительной таблице установлены корректные данные. Таким образом, мы получили ветви, которые были обозначены на Рисунке 1.
Удалим связь между узлами Line и Radius.
Собственно, вернулись к варианту, представленному на Рисунке 2.
Удалим категории у некоторых объектов
Таким образом, Green и Blue ветви удалились каскадно.
Как использовать на практике такой механизм. Представьте, что пользователь отфильтровал наше дерево (рис. 1) по синему фильтру. Можно либо сразу получить все дерево по заданному фильтру при помощи [ReverseTree] и [ObjectsCategories]. Либо можно найти корневые узлы в таблице [Tree] и узнать опять же при помощи [ReverseTree] и [ObjectsCategories] какие из них отнесены к нужной категории. Ну а далее при движении пользователя по дереву в интерфейсе, можно определять, проходит ли фильтрацию следующий узел или нет.
Единственная сложность в реализации такого дизайна на мой взгляд - нужно аккуратно устанавливать триггеры и внешние ключи.
В посте умышленно используется копипаст (уже говорил). Конечно, приведены не все возможные примеры, которые позволили бы протестировать такой подход в полной мере. Постановку объектов на несколько категорий, замену узлов в дереве, смену категории объекта я оставлю для любопытных.
Естественно, применение такого подхода не ограничено только базой. Все это можно реализовать и в коде приложения.
Ну и конечно же, не делайте циклы в деревьях. Потому что это уже будет не дерево, и есть вероятность впасть в бесконечное выполнение.
Чтобы отобразить такую структуру в коде или хранить ее в базе данных есть старое как мир решение.
Но все меняется, когда дерево большое, а объекты могут быть помечены какими либо внешними атрибутами (через ассоциации). Я покажу пример, как фильтровать дерево по атрибутам объектов с сохранением иерархии (если есть дочерний объект с заданным атрибутом, то объект показывается). Ограничимся только базой данных.
Определим дерево объектов в базе.
Обращаться с таким деревом легко. Можно получить корневые узлы, и далее по ходу движения пользователя подгружать динамически все дерево.
- CREATE TABLE [dbo].[Objects] (
- [Id] uniqueidentifier CONSTRAINT [DF_Objects_Id] DEFAULT newid() NOT NULL,
- [Name] nvarchar(max) COLLATE Cyrillic_General_CI_AS NOT NULL,
- CONSTRAINT [PK_Objects] PRIMARY KEY CLUSTERED ([Id])
- )
- ON [PRIMARY]
- GO
- CREATE TABLE [dbo].[Tree] (
- [ParentObjectId] uniqueidentifier NULL,
- [ObjectId] uniqueidentifier NOT NULL,
- CONSTRAINT [Tree_Object] FOREIGN KEY ([ObjectId])
- REFERENCES [dbo].[Objects] ([Id])
- ON UPDATE NO ACTION
- ON DELETE NO ACTION,
- CONSTRAINT [Tree_ParentObject] FOREIGN KEY ([ParentObjectId])
- REFERENCES [dbo].[Objects] ([Id])
- ON UPDATE CASCADE
- ON DELETE CASCADE
- )
- ON [PRIMARY]
- GO
* This source code was highlighted with Source Code Highlighter.
Часто объекты в дереве отличаются друг от друга на какое-то значение, взятое из справочника.
Таким образом, все объекты можно отфильтровать по категориям. Не сохраняя структуры дерева, можно даже показать результат фильтрации в иерархическом виде. Сложности будут, когда понадобится показать дерево для какой-то категории, сохраняя его структуру. Например, для категории 1 дерево в интерфейсе должно содержать все ветви, оканчивающиеся объектами с такой категорией. То есть для объекта категории 1 в интерфейсе должна присутствовать ветвь от этого объекта до корневого. Пользователь, естественно, должен иметь возможность просмотреть эту ветвь в другом направлении: от корневого до узла категории 1.
- CREATE TABLE [dbo].[Categories] (
- [Id] int IDENTITY(1, 1) NOT NULL,
- [Name] nvarchar(max) COLLATE Cyrillic_General_CI_AS NOT NULL,
- CONSTRAINT [PK_Category] PRIMARY KEY CLUSTERED ([Id])
- )
- ON [PRIMARY]
- GO
- CREATE TABLE [dbo].[ObjectsCategories] (
- [ObjectId] uniqueidentifier NOT NULL,
- [CategoryId] int NOT NULL,
- [ObjectCategoryId] uniqueidentifier CONSTRAINT [DF_ObjectsCategories] DEFAULT newid() NOT NULL,
- CONSTRAINT [ObjectsCategories_pk] PRIMARY KEY CLUSTERED ([ObjectCategoryId]),
- CONSTRAINT [ObjectsCategories_Category] FOREIGN KEY ([CategoryId])
- REFERENCES [dbo].[Categories] ([Id])
- ON UPDATE CASCADE
- ON DELETE CASCADE,
- CONSTRAINT [ObjectsCategories_Object] FOREIGN KEY ([ObjectId])
- REFERENCES [dbo].[Objects] ([Id])
- ON UPDATE CASCADE
- ON DELETE CASCADE
- )
- ON [PRIMARY]
- GO
* This source code was highlighted with Source Code Highlighter.
Если объектов очень много, то решение в лоб будет работать очень медленно. При движении пользователя от корневого узла по ветвям в интерфейсе будет приводить к проверке дочерних узлов на наличие объектов с нужной категорией. Если эта категория будет у последнего объекта в последней ветви, то алгоритм пройдет по всем объектам в базе.
Одно из решений - чтобы избавиться от тормозов поиска по дереву, придется принести в жертву объем базы. Сделаем таблицу, в которой будем хранить ветви поиска для каждой категории.
Тут следует пояснить, как мы будем использовать эту таблицу. [ObjectId] и [ChildObjectId] используются для хранения ветвей. [ObjectCategoryId] будет одинаково для всей ветви и будет указывать на причину возникновения такой ветви - запись в [ObjectsCategories].
- CREATE TABLE [dbo].[ReverseTree] (
- [ObjectId] uniqueidentifier NOT NULL,
- [ChildObjectId] uniqueidentifier NULL,
- [ObjectCategoryId] uniqueidentifier NOT NULL,
- CONSTRAINT [ReverseTree_ChildObject] FOREIGN KEY ([ChildObjectId])
- REFERENCES [dbo].[Objects] ([Id])
- ON UPDATE NO ACTION
- ON DELETE NO ACTION,
- CONSTRAINT [ReverseTree_Object] FOREIGN KEY ([ObjectId])
- REFERENCES [dbo].[Objects] ([Id])
- ON UPDATE NO ACTION
- ON DELETE NO ACTION,
- CONSTRAINT [ReverseTree_ObjectCategory] FOREIGN KEY ([ObjectCategoryId])
- REFERENCES [dbo].[ObjectsCategories] ([ObjectCategoryId])
- ON UPDATE CASCADE
- ON DELETE CASCADE
- )
- ON [PRIMARY]
- GO
* This source code was highlighted with Source Code Highlighter.
Основная идея в том, чтобы хранить эти ветви не от корня, а от листового объекта, для которого установлена категория. Создадим функцию, чтобы получать такую ветвь из дерева.
Параметр функции @ObjectId указывает на узел, с которого нужно генерировать обратную ветвь, а @ChildObjectId используется только для того, чтобы вызывающий код мог подставить дочерний узел для первого узла в обратной ветви.
- CREATE FUNCTION dbo.CreateReverseTreeForObject
- ( @ObjectId UNIQUEIDENTIFIER, @ChildObjectId UNIQUEIDENTIFIER)
- RETURNS TABLE
- AS
- RETURN
- WITH ObjectTree (ObjectId, ChildObjectId)
- AS
- (
- SELECT
- t.ObjectId
- , @ChildObjectId
- FROM [Tree] t
- WHERE t.ObjectId = @ObjectId
- UNION ALL
- SELECT
- t.ParentObjectId
- , t.ObjectId
- FROM [Tree] t
- INNER JOIN ObjectTree ot ON ot.ObjectId = t.ObjectId
- )
- SELECT * FROM ObjectTree
* This source code was highlighted with Source Code Highlighter.
Чтобы поддерживать дополнительную таблицу в актуальном состоянии потребуется описать триггеры вставки и обновления для таблицы ObjectsCategories. Триггер добавления выглядит так:
Триггер для смены категории узла и переноса категории от одного узла к другому:
- CREATE TRIGGER [dbo].[ObjectsCategories_AfterInsert] ON [dbo].[ObjectsCategories]
- WITH EXECUTE AS CALLER
- FOR INSERT
- AS
- BEGIN
- DECLARE @ObjectCategoryId UNIQUEIDENTIFIER;
- DECLARE @ObjectId UNIQUEIDENTIFIER;
- DECLARE @CategoryId INT;
- SELECT
- @ObjectCategoryId = ins.ObjectCategoryId
- , @ObjectId = ins.ObjectId
- , @CategoryId = ins.CategoryId
- FROM inserted ins
- INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
- SELECT
- crto.ObjectId
- , crto.ChildObjectId
- , @ObjectCategoryId
- FROM dbo.CreateReverseTreeForObject(@ObjectId, CONVERT(UNIQUEIDENTIFIER, NULL)) crto
- END
- GO
* This source code was highlighted with Source Code Highlighter.
Однако, мы не учли, как на нашей дополнительной таблице должно сказываться изменение настоящего дерева из таблицы [Tree]. Придется и на эту таблицу наложить триггеры. Триггер соединения двух частей дерева получится таким
- CREATE TRIGGER [dbo].[ObjectsCategories_AfterUpdate] ON [dbo].[ObjectsCategories]
- WITH EXECUTE AS CALLER
- FOR UPDATE
- AS
- BEGIN
- DECLARE @ObjectCategoryId UNIQUEIDENTIFIER;
- SELECT
- @ObjectCategoryId = del.ObjectCategoryId
- FROM deleted del
- DELETE rt FROM [ReverseTree] rt
- WHERE rt.ObjectCategoryId = @ObjectCategoryId
- DECLARE @ObjectId UNIQUEIDENTIFIER;
- DECLARE @CategoryId INT;
- SELECT
- @ObjectCategoryId = ins.ObjectCategoryId
- , @ObjectId = ins.ObjectId
- , @CategoryId = ins.CategoryId
- FROM inserted ins
- INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
- SELECT
- crto.ObjectId
- , crto.ChildObjectId
- , @ObjectCategoryId
- FROM dbo.CreateReverseTreeForObject(@ObjectId) crto
- END
- GO
* This source code was highlighted with Source Code Highlighter.
То есть будет достаточно получить полную ветвь от места соединения умножить на количество ветвей, в которых участвует подключаемый узел.
- CREATE TRIGGER [dbo].[Tree_AfterInsert] ON [dbo].[Tree]
- WITH EXECUTE AS CALLER
- FOR INSERT
- AS
- BEGIN
- DECLARE @ObjectId UNIQUEIDENTIFIER;
- DECLARE @ParentObjectId UNIQUEIDENTIFIER;
- SELECT
- @ObjectId = ins.ObjectId
- , @ParentObjectId = ins.ParentObjectId
- FROM inserted ins
- INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
- SELECT
- crto.ObjectId
- , crto.ChildObjectId
- , rt.ObjectCategoryId
- FROM dbo.CreateReverseTreeForObject(@ParentObjectId, @ObjectId) crto,
- [ReverseTree] rt
- WHERE rt.ObjectId = @ObjectId
- END
- GO
* This source code was highlighted with Source Code Highlighter.
Триггер удаления соединения в дереве:
Где функция dbo.GetReverseBranchFromObjects будет генерировать все ветви, начиная с определенного листа:
- CREATE TRIGGER [dbo].[Tree_AfterDelete] ON [dbo].[Tree]
- WITH EXECUTE AS CALLER
- FOR DELETE
- AS
- BEGIN
- DECLARE @ObjectId UNIQUEIDENTIFIER;
- DECLARE @ParentObjectId UNIQUEIDENTIFIER;
- SELECT
- @ObjectId = del.ObjectId
- , @ParentObjectId = del.ParentObjectId
- FROM deleted del
- DELETE rt FROM [ReverseTree] rt
- INNER JOIN dbo.GetReverseBranchFromObjects(@ParentObjectId, @ObjectId) grbo
- ON rt.ObjectId = grbo.ObjectId
- AND rt.ChildObjectId = grbo.ChildObjectId
- AND rt.ObjectCategoryId = grbo.ObjectCategoryId
- END
- GO
* This source code was highlighted with Source Code Highlighter.
Нужно отметить, что эта функция не ожидает, что в качестве последнего параметра может прийти NULL. Если это требуется, то читатель сам может обновить функцию. Триггер использует эту функцию с заполненными параметрами. Оно и понятно, ведь для удаления соединения используются два объекта. Сложим оба триггера и получим триггер смены подключения.
- CREATE FUNCTION dbo.GetReverseBranchFromObjects
- ( @ObjectId UNIQUEIDENTIFIER, @ChildObjectId UNIQUEIDENTIFIER)
- RETURNS TABLE
- AS
- RETURN
- WITH ObjectTree (ObjectId, ChildObjectId, ObjectCategoryId)
- AS
- (
- SELECT
- rt.ObjectId
- , rt.ChildObjectId
- , rt.ObjectCategoryId
- FROM [ReverseTree] rt
- WHERE rt.ObjectId = @ObjectId
- AND (rt.ChildObjectId = @ChildObjectId)
- UNION ALL
- SELECT
- rt.ObjectId
- , rt.ChildObjectId
- , rt.ObjectCategoryId
- FROM [ReverseTree] rt
- INNER JOIN ObjectTree ot
- ON ot.ObjectId = rt.ChildObjectId
- AND ot.ObjectCategoryId = rt.ObjectCategoryId
- )
- SELECT * FROM ObjectTree
* This source code was highlighted with Source Code Highlighter.
Да, товарищи, копипаст. Пример все таки демонстрирует более дизайн решения, так что оставим все в удобочитаемом виде, чтобы не ссылать читателя к разрозненным функциям.
- CREATE TRIGGER [dbo].[Tree_AfterUpdate] ON [dbo].[Tree]
- WITH EXECUTE AS CALLER
- FOR UPDATE
- AS
- BEGIN
- DECLARE @ObjectId UNIQUEIDENTIFIER;
- DECLARE @ParentObjectId UNIQUEIDENTIFIER;
- SELECT
- @ObjectId = del.ObjectId
- , @ParentObjectId = del.ParentObjectId
- FROM deleted del
- DELETE rt FROM [ReverseTree] rt
- INNER JOIN dbo.GetReverseBranchFromObjects(@ParentObjectId, @ObjectId) grbo
- ON rt.ObjectId = grbo.ObjectId
- AND rt.ChildObjectId = grbo.ChildObjectId
- AND rt.ObjectCategoryId = grbo.ObjectCategoryId
- SELECT
- @ObjectId = ins.ObjectId
- , @ParentObjectId = ins.ParentObjectId
- FROM inserted ins
- INSERT INTO [ReverseTree] ([ObjectId], [ChildObjectId], [ObjectCategoryId])
- SELECT
- crto.ObjectId
- , crto.ChildObjectId
- , rt.ObjectCategoryId
- FROM dbo.CreateReverseTreeForObject(@ParentObjectId, @ObjectId) crto,
- [ReverseTree] rt
- WHERE rt.ObjectId = @ObjectId
- END
- GO
* This source code was highlighted with Source Code Highlighter.
Введем тестовые данные для проверки. Должно получиться вот такое вот дерево
Рисунок 1.
Узел Point будет иметь категорию Red, Sphere - Green, Tangens - Blue, Cosinus - Black. На узле цветами, соответствующими примененным категориям показаны ветви, которые должны быть в вспомогательной таблице [ReverseTree]. Запустим скрипт с исходными данными
Как видно из представленного скрипта, сначала генерируются справочные данные - объекты и категории. Потом начинаем строить дерево. Делаем сначала два сегмента.
- DELETE FROM [Tree]
- GO
- DELETE FROM [ReverseTree]
- GO
- DELETE FROM [ObjectsCategories]
- GO
- DELETE FROM [Categories]
- GO
- DELETE FROM [Objects]
- GO
- INSERT INTO [Categories] ([Name]) VALUES ('Red')
- GO
- INSERT INTO [Categories] ([Name]) VALUES ('Blue')
- GO
- INSERT INTO [Categories] ([Name]) VALUES ('Green')
- GO
- INSERT INTO [Categories] ([Name]) VALUES ('Black')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Cube')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Ellipsis')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Sphere')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Line')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Point')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Polyline')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Radius')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Diameter')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Sinus')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Cosinus')
- GO
- INSERT INTO [Objects] ([Name]) VALUES ('Tangens')
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cube'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Ellipsis'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cube'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Ellipsis'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Line'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Ellipsis'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Point'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Polyline'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Diameter'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sinus'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sinus'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cosinus'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sinus'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Tangens'))
- GO
- INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Point'),
- (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Red'))
- GO
- INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere'),
- (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Green'))
- GO
- INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Tangens'),
- (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Blue'))
- GO
- INSERT INTO [Tree] ([ParentObjectId], [ObjectId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Line'),
- (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius'))
- GO
- INSERT INTO [ObjectsCategories] ([ObjectId], [CategoryId])
- VALUES ((SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Cosinus'),
- (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Black'))
- GO
* This source code was highlighted with Source Code Highlighter.
Рисунок 2.
Назначаем для узлов Point, Sphere и Tangens нужные категории.
После соединяем узлы Line и Radius. Для узла Cosinus назначаем категорию Black.
При помощи нехитрого скрипта, проверим, какие ветви есть в вспомогательной таблице.
Вывод:
- SELECT
- (SELECT o.[Name] FROM [Objects] o WHERE o.Id = rt.ObjectId) AS 'Object'
- , (SELECT o.[Name] FROM [Objects] o WHERE o.Id = rt.ChildObjectId) AS 'ChildObject'
- , (SELECT c.[Name] FROM [ObjectsCategories] oc
- INNER JOIN [Categories] c ON c.Id = oc.CategoryId
- WHERE oc.ObjectCategoryId = rt.ObjectCategoryId) AS 'Category'
- , (SELECT o.[Name] FROM [ObjectsCategories] oc
- INNER JOIN [Objects] o ON o.Id = oc.ObjectId
- WHERE oc.ObjectCategoryId = rt.ObjectCategoryId) AS 'Source Object'
- FROM [ReverseTree] rt
* This source code was highlighted with Source Code Highlighter.
Source Object - объект, для которого установлена соотвествтующая категория в основной таблице ObjectsCategories. В дополнительной таблице установлены корректные данные. Таким образом, мы получили ветви, которые были обозначены на Рисунке 1.
Удалим связь между узлами Line и Radius.
Состояние вспомогательной таблицы:
- DELETE t FROM [Tree] t
- WHERE t.ObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Radius')
- AND t.ParentObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Line')
* This source code was highlighted with Source Code Highlighter.
Собственно, вернулись к варианту, представленному на Рисунке 2.
Удалим категории у некоторых объектов
Во вспомогательной таблице [ReverseTree]
- DELETE oc FROM [ObjectsCategories] oc
- WHERE oc.CategoryId = (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Blue')
- AND oc.ObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Tangens')
- DELETE oc FROM [ObjectsCategories] oc
- WHERE oc.CategoryId = (SELECT c.Id FROM [Categories] c WHERE c.[Name] = 'Green')
- AND oc.ObjectId = (SELECT o.Id FROM [Objects] o WHERE o.[Name] = 'Sphere')
* This source code was highlighted with Source Code Highlighter.
Таким образом, Green и Blue ветви удалились каскадно.
Как использовать на практике такой механизм. Представьте, что пользователь отфильтровал наше дерево (рис. 1) по синему фильтру. Можно либо сразу получить все дерево по заданному фильтру при помощи [ReverseTree] и [ObjectsCategories]. Либо можно найти корневые узлы в таблице [Tree] и узнать опять же при помощи [ReverseTree] и [ObjectsCategories] какие из них отнесены к нужной категории. Ну а далее при движении пользователя по дереву в интерфейсе, можно определять, проходит ли фильтрацию следующий узел или нет.
Единственная сложность в реализации такого дизайна на мой взгляд - нужно аккуратно устанавливать триггеры и внешние ключи.
В посте умышленно используется копипаст (уже говорил). Конечно, приведены не все возможные примеры, которые позволили бы протестировать такой подход в полной мере. Постановку объектов на несколько категорий, замену узлов в дереве, смену категории объекта я оставлю для любопытных.
Естественно, применение такого подхода не ограничено только базой. Все это можно реализовать и в коде приложения.
Ну и конечно же, не делайте циклы в деревьях. Потому что это уже будет не дерево, и есть вероятность впасть в бесконечное выполнение.
Насколько я вижу, у тебя тут не дерево, а граф, поскольку [dbo].[Tree] позволяет делать циклы, и даже добавлять несколько графов, которые между собой не соединены. К тому же, ты используешь триггеры AfterInsert и AfterUpdate - они внутри вызывают процедуру с рекурсивным запросом - это означает, что при существовании цикла возможно переполнение рекурсии, и тогда триггеры не отработают. Я видел, что ты об этом написал - просто как вариант, я предлагаю в триггере Before перед добавлением соединения проверять, создаст ли это соединение цикл - и если создаст, то не применять его. И, да, ты же это решение делал под sql server - там с 2008й версии есть иерархический тип данных, почему ты его не использовал? Мне кажется, в данном случае, это было бы уместным.
ОтветитьУдалитьз.ы. Убери у картинок теги width и height, чтобы они показывались в натуральный размер - качество будет лучше, они же и так у тебя небольшого размера. Длинные скрипты добавления данных лучше бы заменить скринами таблиц - так нагляднее и листать меньше. А каскадные операторы в определениях таблиц можно вообще не показывать - это только нагромождает код. Лучше готовые скрипты просто приложить в виде файлов к посту.
"И, да, ты же это решение делал под sql server - там с 2008й версии есть иерархический тип данных, почему ты его не использовал? Мне кажется, в данном случае, это было бы уместным"
ОтветитьУдалитьЯ знаю, что есть иерархический тип данных, но пост о дизайне.
Конечно, пример можно соптимизировать и улучшить.
"Длинные скрипты добавления данных лучше бы заменить скринами таблиц - так нагляднее и листать меньше." Не понял, о чем ты тут пишешь. Как это сделать?
"А каскадные операторы в определениях таблиц можно вообще не показывать - это только нагромождает код." К сожалению, так делать нельзя. Я написал "Единственная сложность в реализации такого дизайна на мой взгляд - нужно аккуратно устанавливать триггеры и внешние ключи." Посмотри внимательнее, не все внешние ключи каскадные. Это часть решения.
Думаю, если "готовые скрипты просто приложить в виде файлов", то у читателя будет взрыв мозга, и он не поймет о чем речь, либо ему придется постоянно сверять текст с кодом.
"Не понял, о чем ты тут пишешь. Как это сделать?"
ОтветитьУдалитьИмел ввиду вместо горы Insert'ов показать скриншот результата селекта на таблицу с данными
"Я знаю, что есть иерархический тип данных, но пост о дизайне."
ОтветитьУдалитьТогда почему бы в таблице [dbo].[Objects] не сделать поле ParentId - почему ты предпочел хранить все связи иерархии в отдельной таблице?
"Имел ввиду вместо горы Insert'ов показать скриншот результата селекта на таблицу с данными"
ОтветитьУдалитьРезультат селекта на таблицу [Tree] покажет одни идентификаторы. Нечитаемо это. Скриптом гораздо лучше.
"Тогда почему бы в таблице [dbo].[Objects] не сделать поле ParentId" Одно дело объекты, другое дело связи между ними. Считай SRP нарушается :-)
"Считай SRP нарушается :-) " Ну ты же реализуешь дерево - объекты как бы его ноды. А по поводу SRP - тебя послушать, так стандартный нод дерева wpf просто жестко нарушает все принципы кодекса
ОтветитьУдалитьhttp://msdn.microsoft.com/en-us/library/system.windows.controls.treeviewitem.aspx
Тут ведь и инфа по родителю, и по чилдам, и методы отрисовки, и события и много чего, что нарушает SRP -но это не мешает разработчикам пользовать данный класс в своих работах. Я просто хочу донести, что кодекс - это не свод жестких правил...
Cтандартный нод дерева wpf не нарушает SRP. Ты что-то путаешь. [dbo].[Objects] не хранит дерева. [dbo].[Objects] хранит какие-то объекты, которые находят свое отражение в прикладной области. Дерево сделано, чтобы показывать объекты иерархично, а не объекты - чтобы было дерево.
ОтветитьУдалитьА по моему стандарный нод wpf нарушает SRP по полной программе. Достаточно только взглянуть на иерархию наследования - тут тебе и
ОтветитьУдалитьDependencyObject, и UIElement, и ItemsControl - а это уже, как минимум, 3 разные обязанности. Но только благодаря этому данный контрол можно использовать разными способами.
Что касается задачи в твоём посте - ты же сам её написал "Чтобы отобразить такую структуру в коде или хранить ее в базе данных есть старое как мир решение." - то есть у тебя задача хранить древовидную структуру в базе - так что это не объекты с прикладной областью, это вынесенная инфа по нодам из таблицы [dbo].[Tree] в таблицу
[dbo].[Objects].
Я понимаю, что твоё решение было бы боее понятно, если бы задача звучала как "построение различного рода отношений, в том числе древоводных, между сущностями" - однако, задача поставлена обратная.
Это именно объекты из прикладной области. Собственно поэтому таблица и называется [dbo].[Objects].
ОтветитьУдалитьНадо хранить информацию о нодах - сделай [dbo].[Nodes].
Если в [dbo].[Objects] добавить столбец [ParentId], таблица не начнет хранить ноды. Она начнет хранить соединения и их названия.