Схема базы данных для иерархических групп

Question

Я работаю над дизайном базы данных для иерархии групп, используемой в качестве основы для более крупной системы. Каждая группа может содержать другие группы, а также «устройства» в виде листовых объектов (ничего не происходит ниже устройства).

Используемая база данных - MS SQL 2005. (Хотя работа в MS SQL 2000 была бы бонусом, решение, требующее MS SQL 2008, к сожалению, сейчас невозможно).

Существуют различные типы групп, и они должны быть динамическими и определяемыми во время выполнения пользователями. Например, типами групп могут быть «клиент», «учетная запись», «город» или «здание», «пол», и каждый тип будет иметь другой набор атрибутов, определяемый пользователем. Также будут применяться бизнес-правила - например, «пол» может содержаться только под группой «здание», и, опять же, они определяются во время выполнения.

Многие функциональные возможности приложений поступают от запуска отчетов на основе этих групп, поэтому должен быть относительно быстрый способ получить список всех устройств, содержащихся в определенной группе (и всех подгруппах).

Хранение групп с использованием метода modified pre-order tree traversal имеет тот потенциал, что он быстрый, но недостаток, что он довольно сложный и хрупкий - если внешние пользователи/приложения изменяют базу данных, есть потенциал для полного поломки. Мы также реализуем уровень ORM, и этот метод, похоже, усложняет использование отношений в большинстве библиотек ORM.

Использование common table expressions и «стандартное» отношение групп id/parentid представляют собой мощный способ избежать запуска нескольких рекурсивных запросов. Есть ли недостатки в этом методе?

Что касается атрибутов, что их лучше всего хранить? Длинный узкий стол, который относится к группе? Должен ли общий атрибут, например «имя», быть сохранен в таблице групп, вместо таблицы атрибутов (много времени, это будет все, что требуется для отображения)?

Будут ли возникать проблемы с производительностью с использованием этого метода (предположим, что среднее среднее из 2000 групп со средним значением по 6 атрибутов и средними 10 одновременными пользователями на разумном аппаратном уровне, например, четырехъядерный Xeon 2 Ghz, 4GB RAM, дисконтирование любых других процессов)?

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

Answer 1

Я бы рекомендовал вам на самом деле построить самый простой в использовании способ («стандартная» настройка родителя/ребенка) и запустить по крайней мере некоторые базовые эталоны.

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

Предполагая 6 атрибутов на группу, группы 2000 и 30 байт/атрибут, вы говорите 360 КБ * ожидаемые элементы/группа - показатель 400 КБ. Если вы ожидаете иметь 1000 элементов/групп, вы смотрите только на 400 МБ данных, которые будут помещаться в память без проблем, а базы данных - быстро при подключении, когда все данные находятся в памяти.

Answer 2

Общие выражения таблиц позволят вам получить список групп с отношениями родитель-ребенок. Here - пример sproc с использованием CTE для другого приложения.Это разумно эффективно, но остерегайтесь следующих оговорок:

1. Если какая-либо часть происходит более одного раза в иерархии, она будет сообщаться в каждом месте. Возможно, вам придется опубликовать результаты.
2. CTE несколько тупые и предлагают ограниченный объем для фильтрации результатов в запросе. CTE может не отображаться более одного раза в операторе select.

CONNECT BY от Oracle является несколько более гибким, так как он не накладывает почти столько ограничений на структуру запросов, как это делает CTE, но если вы используете SQL Server, это не будет вариантом.

Если вам нужно сделать что-нибудь умное с промежуточными результатами, тогда напишите sproc, который использует CTE, чтобы получить необработанный запрос во временную таблицу и работать с ней оттуда. SELECT INTO минимизирует трафик, вызванный этим. Полученная таблица будет в кеше, поэтому операции над ней будут достаточно быстрыми.

Некоторые возможные физические оптимизаций, которые могут помочь:

• кластерные индексы по материнской, так , что получение из дочерних узлов для родителя использует меньше I/O.
• Много оперативной памяти и (в зависимости от размера вашей таблицы спецификации) 64-разрядные серверы с еще большим объемом оперативной памяти, так что основная база данных может быть кэширована в ядре. На 32-битном O/S загрузочный переключатель/3G - ваш друг и не имеет реального недостатка для сервера базы данных.
• DBCC PINTABLE может помочь заставить менеджера баз данных удерживать таблицу в кеше.

Таблицы кодирования атрибутов атрибутов родительского атрибута не будут хорошо воспроизводиться с помощью CTE, так как вы включите комбинаторный взрыв в строке, если вы включите таблицу атрибутов. Это исключает любую бизнес-логику в запросе, который фильтруется по атрибутам. Вам будет намного лучше хранить атрибуты непосредственно в записи таблицы спецификации.

Answer 3

Предпросмотр Tree Traversal очень удобен. Вы можете сделать это надежным, сохранив номера обхода с помощью триггеров.

Подобный метод, который я использовал, состоит в том, чтобы сохранить отдельную таблицу (ancestor_id, descendant_id), в которой перечислены все предки и потомки. Это почти так же хорошо, как и порядковые номера обхода.

Использование отдельной таблицы удобно, потому что, даже если она вводит дополнительное соединение, она удаляет сложность в отдельной таблице.

Answer 4

Модифицированный предварительный заказ - это, по существу, метод вложенных наборов Джо Целько. Его книга «Деревья и иерархии ...» охватывает как список смежности, так и NS, с описанием преимуществ и недостатков каждого. При правильной индексации CTE списков смежности получает самую сбалансированную производительность. Если вы собираетесь читать в основном, то NS будет быстрее.

Что вы, должно быть, описываете, это процессор технических характеристик. В то время как не M $, у Graeme Birchall есть бесплатная книга DB2 с главой по обработке иерархии с использованием CTE (синтаксис практически идентичен, IIRC, в том, что синтаксис ANSI принял DB2, который затем был принят M:) http://mysite.verizon.net/Graeme_Birchall/cookbook/DB2V95CK.PDF