Представление древовидной зависимости в реляционной базе данных

ти автономный сервис, выполняющий архивацию для определенных документов в соответствии с заданными заранее параметрами. Сервис может быть как локальным, работающим на одном ПК с Asys TSW, так и сетевым, то есть взаимодействующим через вычислительную сеть с другими сервисами и программами. Использование сервисов позволяет уйти от концепции монолитного программного обеспечения, где все функции заключены в одной большой программе. Однако такой подход имеет недостатки, связанные, в частности, с тестированием взаимодействия сервисов.

Часто возникает необходимость в использовании одних и тех же задач в разных БП. Такие задачи характеризуются уже определенным исполнителем, назначенным сервисом и указанными входными и выходными результатами. Asys Designer позволяет определять данные задачи как типовые и, соответственно, помещает их в специальный репозиторий для дальнейшего использования в других БП. Помимо задач, в качестве типовых элементов могут быть определены группы задач или целые процессы. Репозиторий хранит типовые объекты в БД. В компоненте Asys Designer у репозитория типовых элементов есть специальная панель, где в виде списка, разделенного по категориям, представлены графические изображения и названия типовых элементов. Данные элементы добавляются на область формирования схемы БП с помощью процедуры Drag and Drop. После добавления пользователю для включения типового элемента в схему БП необходимо соединить входные и выходные связи элемента с задачами в схеме. Использование типовых элементов позволяет в дальнейшем сократить время на разработку схем БП.

Типовые элементы, находящиеся в схеме БП, не могут редактироваться как обычные задачи. Для этого предусмотрен специальный "тестовый" режим в Asys Designer. Изменения, произведенные в этом режиме с типовым элементом, распространяются на экземпляры данного элемента во всех БП, где он указан. Помимо редактирования, в данном режиме существует возможность тестирова-

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

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

Кроме того, в компоненте Asys Designer предусмотрены возможности по анализу построенных схем БП. Для каждой задачи конструктором БП задается планируемое время ее выполнения. На основе этих данных производится сетевой анализ схемы БП и вычисляются ранний и поздний сроки начала выполнения для каждой задачи. Для всего процесса в данном случае вычисляется ранний срок завершения, поздний и наиболее реальный. Помимо этого, в компоненте Asys Designer предусмотрена функция нахождения кратчайшего пути от начальной задачи к конечной с использованием алгоритма Беллмана-Форда. Это особенно полезно, если схема насчитывает несколько десятков элементов.

Следует отметить, что Asys BPM использует два развивающихся в рамках информационных систем направления - сервис-ориентированую архитектуру и технологию управления БП. Использование сервисов позволяет таким BPM-системам наилучшим образом интегрироваться с другими информационными системами.

ПРЕДСТАВЛЕНИЕ ДРЕВОВИДНОЙ ЗАВИСИМОСТИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ

Н.Н. Гребенщиков

При построении реляционной базы данных (РБД), где между данными существует древовидная зависимость, разработчики встают перед выбором метода представления такой зависимости в реляционной модели. Существует несколько ме-

тодов: например, авторы Joe Celko и Vadim Tropashko описывают методы, в которых используются список смежности, материализация пути в дереве, вложенные множества и интервалы, транзитивное замыкание. В ходе разработки структуры

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

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

Р(8,Э,К,и)= Е

_ ^, О

йт^А^)

где Р - критерий производительности; 8 - тестируемая программная система; Б - данные, находящиеся в БД; К={к1,к2,...,к^...,к„_1,к„} - множество весов для сценариев использования; и= ={и1,и2,...,и1,...,и„_1,и„} - множество программ, имитирующих действия пользователя в сценариях использования; Т^АиО - время выполнения программы и! для системы 8 и данных Б.

Рассмотрим описанный процесс тестирования производительности на следующих этапах разработки: эксплуатация, тестирование, проектирование.

Во время эксплуатации для тестирования каждого метода представления древовидной зависимости необходимо изменять тестируемую систему в части управления древовидными зависимостями и форму представления зависимостей в БД.

На этапе тестирования программной системы процесс тестирования производительности осложняется тем, что во многих случаях характеристики данных, находящиеся в БД, не соответствуют характеристикам эксплуатации. Для древовидной зависимости значимыми характеристиками данных являются количество узлов в дереве и их распределение внутри дерева.

На этапе проектирования неопределенность возрастает. Отсутствуют не только данные, но сама программная система. В то же время проблема

выбора метода представления древовидной зависимости на этом этапе стоит особенно остро, так как именно на этапе проектирования формируется структура БД.

В итоге получаем, что выбор метода представления древовидной зависимости в РБД является решением, определяющим архитектуру программной системы. Изменения, вносимые в архитектуру на этапах кодирования и тестирования, требуют значительных материальных вложений. Поэтому так важно сделать обоснованный выбор метода уже на этапе проектирования. Но на данном этапе невозможно организовать полноценное тестирование производительности программной системы, ввиду отсутствия как самой программной системы, так и данных, управляемых рассматриваемой системой.

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

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

Рассматриваемые операции имеют один или два аргумента. В качестве аргументов передаются идентификаторы узлов в дереве. Результатом выполнения рассматриваемой операции является множество узлов дерева.

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

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

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

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

Модель данных. На этапе проектирования данные, ввиду их отсутствия, требуется генерировать. Для генерации древовидных данных применяется модель дерева, которая включает такие характеристики, как количество узлов в дереве и закон случайного распределения количества детей среди узлов дерева. Данная модель используется в генераторе древовидных данных ToXgene (разработчики: университет Торонто и лаборатория IBM Торонто, http://www.cs.toronto.edu/tox/toxgene). Дерево генерируется по шагам, от корня к кроне. Для каждого узла случайным образом выбирается количество детей. Процесс продолжается, пока в дереве не будет заданного количества узлов. В качестве замечания к данному способу генерации можно выделить то, что с помощью него генерируются только симметричные деревья.

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

m k:

Рсц

сц i=lT

где Рсц - критерий производительности системы на определенном сценарии; S - тестируемая программная система; D - данные, находящиеся в БД; O - множество кортежей <о:,а:,к:>, где o: определяет вид древовидной операции, ai и к - ее аргументы и весовой коэффициент соответственно; T(S,D,<oi,ai,ki>) - время вызова операции для системы S и данных D.

Для каждого сгенерированного дерева необходимо подбирать узлы с нужным для тестирования расположением. Решением данной проблемы является выбор узлов в дереве, исходя из какой-либо нормированной модели, масштабируемой

для каждого конкретного дерева. Предлагается описывать зоны выборки двухмерными функциями плотности распределения, определенными в следующих координатах: номер уровня, на котором находится узел, и порядковый номер узла среди узлов одного уровня. Функции плотности следует определять на квадрате с вершинами (0,0), (0,1), (1,1), (1,0).

Задача построения множества узлов дерева по заданной модели выборки заключается в следующем. Дано:

- множество элементов дерева, заданных двумя координатами (номером уровня и номером внутри уровня), номер максимального уровня max_level, максимальный номер элемента внутри уровня max_on_level;

- двухмерная функция плотности распределения выборки f(x,y), заданная на квадратной области [0,1][0,1];

- необходимое количество вызовов n.

Необходимо найти псевдослучайную последовательность узлов заданного дерева, закон распределения которых совпадал бы с законом, заданным функцией плотности f(x,y).

Для решения данной задачи используется прием «разделяй и властвуй». Перед началом распределения элементов необходимо нормировать f(x,y) для прямоугольной области [1,max_level] [1,max_on_level]. Пусть g(x,y) будет функцией плотности распределения и находится следующим образом:

factor = max(max_level,max_on_level),

g(x,y) = factorxf

y

factor factor,

Алгоритм выбора узлов дерева описывается рекурсивной функцией, на вход которой передается функция плотности распределения выборки -f(x,y); двухмерный массив, определяющий дерево - tree; количество тестов - n; область дерева -[a,b][c,d], на которой необходимо распределить n тестов по закону распределения, описываемому функцией плотности f(x,y). Данная функция разделяет заданную область [a,b][c,d] на четыре равных подобласти: D1, D2, D3, D4. Затем определяет количество тестов для каждой получившейся области пропорционально jjj f(x,y). После чего дан-

Di

ная функция вызывается для каждой из областей. И так до тех пор, пока в области не останется один узел дерева. Данный узел попадает в список тестирования столько раз, каково было значение n при вызове функции для данной области.

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

x

-с

Тестирующая подсистема

Реляционное представление деревьев

Работа с РСУБД

Компоненты системы тестирования

Система тестирования. Процесс выбора метода представления древовидных данных в реляционной модели можно разбить на этапы:

- определение тестируемых методов;

- создание программных модулей (прототипов) для использования в системе тестирования;

- описание данных и описание сценариев тестирования;

- тестирование сценариев;

- получение интегральной оценки критериев производительности различных прототипов;

- анализ результатов тестирования и осуществление выбора наилучшего метода.

Центральным звеном процесса выбора метода является система тестирования. Ключевыми требованиями к архитектуре системы тестирования являются:

- абстрагирование от метода представления древовидных данных, то есть тестирующая система должна выполнять эксперимент одинаково, вне зависимости от метода тестирования;

- абстрагирование от используемой СУБД;

- возможность использования и генерирования различных исходных данных;

- совместимость формата выходных данных тестирующей системы с математическими пакетами программ.

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

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

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

Данная система тестирования разработана и имеет свидетельство об отраслевой регистрации разработки №7440 от 26.12.2006, выданное Отраслевым фондом алгоритмов и программ.

В ходе работы над системой тестирования был разработан метод описания сценариев взаимодействия с системой управления древовидными данными и алгоритм преобразования модели сценария в набор данных для тестирования.

Разработанная система тестирования предоставляет возможность разработчикам уже на этапе анализа требований и проектирования программной системы совершать обоснованный выбор в пользу того или иного метода представления древовидных данных в реляционной модели. Необходимо отметить и другие сферы применения системы тестирования. В силу абстрагирования системы от конкретной СУБД она может быть использована для сравнения производительности различных СУБД при решении одной и той же задачи на древовидных данных. Кроме того, может рассматриваться возможность использования разработанной системы тестирования в качестве средства адаптации архитектуры программных систем к условиям среды эксплуатации. В ходе мониторинга системы замеряются характеристики данных и показатели использования сценариев пользовательского взаимодействия. Эти данные становятся отправной точкой для сравнения используемого в системе метода представления древовидных данных с другими. Данное сравнение может показать, что в сложившейся при эксплуатации ситуации использование другого метода может увеличить производительность операций с древовидными данными, и необходимо заменить соответствующий модуль в архитектуре (конечно, если возможность такой замены была предусмотрена при проектировании программной системы).