автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методика оценки эффективности способов реляционного моделирования систем управления иерархическими данными

На правах рукописи □ОЗОБ2548 /

Гребенщиков Николай Николаевич

МЕТОДИКА ОЦЕНКИ ЭФФЕКТИВНОСТИ СПОСОБОВ РЕЛЯЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ УПРАВЛЕНИЯ ИЕРАРХИЧЕСКИМИ ДАННЫМИ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук по специальности 05 13 11-«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Красноярск - 2007

003062548

Работа выполнена в Институте информатики и телематики Хакасского государственного университета им НФ Катанова на кафедре информационных технологий и систем

Научный руководитель

кандидат технических наук, доцент Швец Сергей Викторович

Официальные оппоненты

доктор технических наук, доцент Легалов Александр Иванович

кандидат технических наук, профессор

Сорокин Владимир Афанасьевич

Ведущая организация

ИВМ СО РАН

Защита состоится 17 мая 2007 г в 14 часов на заседании диссертационного совета Д212 099 05 при Сибирском федеральном университете по адресу 660074, г Красноярск, ул Киренского, 26

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета (Политехнического института)

Автореферат разослан «14» апреля 2007 г

Ученый секретарь

диссертационного совета, кандидат технических наук

Вейсов Е А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Способ реализации управления данными является важным архитектурным решением Благодаря простоте, естественности структуры данных и манипулятив-ных операций, реляционные СУБД заняли доминирующее положение на рынке и используются при создании большого круга программных систем Однако при разработке программного обеспечения часто приходится сталкиваться с данными, которые имеют иерархическую структуру Такие данные обычно являются дополнительными иерархическими онтологиями, которые имеют тесную связь с данными, расположенными в реляционной СУБД Вследствие такого положения прикладываются значительные усилия по изучению вопросов реляционного моделирования иерархий В настоящий момент можно с уверенностью констатировать, что существует целый спектр теоретических разработок, технологических решений и конкретных реализаций в области построения иерархических справочников Этот факт позволяет утверждать, что данное направление находится в активной стадии своего развития Большой вклад в решение проблемы реляционного моделирования иерархических систем внесли Виноградов С А , Курчидис В А , Чиркунов В А , Назанский А С , Гладков М В , Сажин А С , Голованов М , J Celko, Т Haughey, М Hillyer, L Jonsson, S Deleurme, D Forbes, N Gassiep, V Tropashko, I Ben-Gan Однако, окончательное формирование данного направления еще не произошло Можно выделить ряд теоретических и технологических проблем, требующих разрешения, и еще большее количество конкретных, прикладных задач, которые ждут реализации

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

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

В соответствие с целью работы были поставлены и решены следующие научные задачи

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

- разработка способа математического моделирования требований к системам управления иерархическими данными,

- определение критериев эффективности способов реляционного моделирования систем управления иерархическими данными,

- разработка методики оценки эффективности способов реляционного моделирования систем управления иерархическим данными,

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

Методы исследования. Для решения поставленных в диссертационной работе задач были применены методы системного анализа, методы объектно-ориентированного анализа и проектирования, методология UML, методы реляционного моделирования, теория чисел, статистические и численные методы, элементы имитационного моделирования

Объектом исследования является моделирование систем управления иерархическими данными

Предмет исследования, оценка эффективности способов реляционного моделирования систем управления иерархическими данными Научную новизну работы составляют

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

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

- алгоритм генерации дерева и алгоритм генерации сценария нагрузочного тестирования по разработанным математическим моделям, основной чертой которых является применение подхода «разделяй и властвуй» для распределения дискретной величины (количество элементов) в соответствии с непрерывными функциями плотности ее распределения

Практическая значимость

Разработана и внедрена автоматизированная система «Бизнес-справочник SIB-INFO RU» Данная автоматизированная система является центральным звеном организации регионального бизнес-справочника по Республике Хакасия На нее возложены задачи по хранению справочной информации, учету клиентов бизнес-справочника и обеспечению процесса расчетов, публикации справочной информации в сети Интернет, формирование информационного макета печатного издания бизнес-справочника

Применение разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными при разработке автоматизированной системы «Бизнес-справочник «Товары и услуги Хакасии и юга Красноярского края» позволило эффективным способом реализовать иерархический справочник видов деятельности

Разработана и внедрена автоматизированная система «Реестр субъектов малого предпринимательства Республики Хакасия» Данная автоматизированная система построена по Принципам объектно-ориентированного анализа, проектирования и программирования Для организации объектно-реляционного отображения, которое бы позволило осуществлять группировку данных, была использована древовидная структура, помещенная в реляционную базу данных Хранение иерархии в реляционной базе данных позволяет использовать как преимущества

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

Применение разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными при разработке автоматизированной системы «Реестр субъектов малого предпринимательства» позволило эффективным образом реализовать реляционно-иерархическое хранилище объектной модели На защиту выносятся

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

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

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

- способ применения разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными для адаптации архитектуры таких систем к условиям эксплуатации Апробация работы

Основные положения и результаты работы докладывались на следующих научно-технических конференциях Межвузовская научно-техническая конференция «Развитие средств и комплексов связи» (24 ноября 2005 года, г Новочеркасск), Межвузовская научно-техническая конференция «Военная электроника опыт использования и проблемы подготовки специалистов» (22 ноября 2005 года, г Воронеж), Конференция-конкурс «Технологии Microsoft в теории и практике программирования» (23 февраля 2006 года, г Новосибирск), Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций» (27 апреля 2006 года, г Новосибирск), Конференция-конкурс «Технологии Microsoft в теории и практике программирования» (25 февраля 2007 года, г Новосибирск)

Теоретические результаты, отдельные положения, а также результаты конкретных прикладных исследований и разработок обсуждались на научных семинарах Института Информатики и Телематики Хакасского Государственного Университета им Н Ф Катанова (2003-2007 гг )

Результаты исследований обсуждались на многочисленных рабочих совещаниях и семинарах с профильными специалистами и научными сотрудниками институтов города Абакана (Республика Хакасия) и города Красноярска (Красноярский край)

Публикации

Основное содержание диссертационной работы отражено в 9 печатных работах В том числе две работы опубликованы в журналах, рекомендуемых ВАК Личный вклад автора

Автором проведен анализ подходов к моделированию иерархических систем, разработан способ моделирования нагрузки для систем управления иерархическими данными, разработана методика оценки эффективности способов реляционного моделирования иерархических систем, разработан способ перехода от математиче-

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

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

В ходе разработки автоматизированной системы «Бизнес-справочник SIB-INFO RU» автор участвовал в постановке задачи для Интернет версии справочника, создании методики сбора и заполнения справочной информации, разработке системы управления прайс-листами компаний, разработал общую технологическую архитектуру системы, схемы баз данных, программное обеспечение для трансформации существующей структуры базы данных, технологию и программное средство выгрузки данных бизнес-справочника для создания печатных версий справочника, внутренние технические задания на элементы программного обеспечения, участвовал в оформлении документации на систему

В ходе разработки автоматизированной системы «Реестр субъектов малого предпринимательства» автор участвовал в постановке задачи, анализе предметной области, разработал архитектуру системы, схемы баз данных, реализовал основные программные модули системы Структура работы

Диссертационная работа выполнена на 108 страницах машинописного текста, включающего в себя введение, четыре раздела, заключение, 30 рисунков, 10 таблиц и библиографический список из 129 наименований

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В диссертационной работе проводится анализ состояния вопроса моделирования иерархических структур Разрабатывается методика оценки эффективности способов реляционного моделирования систем управления иерархическими данными на основе нагрузочного тестирования Описывается модель нагрузки для систем управления иерархическими данными Приводятся критерии эффективности Описывается апробация разработанной методики в реальных проектах по разработке программных систем

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

Первый раздел диссертации посвящен изучению состояния вопроса разработки реляционных моделей иерархических систем и реляционной реализации иерархических операций

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

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

Среди методов реляционного моделирования древовидных иерархий выделяют две группы иерархические/рекурсивные расширения SQL и методы кодирования элементов дерева Также можно выделить метод, который не относится к описанным выше двум группам Данный метод подразумевают хранение всех пар элементов, между которыми определено транзитивное отношение Этот метод будем назвать методом транзитивного замыкания

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

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

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

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

MD = {n,flcvcl(x),C,MEMm„}, где п - общее количество элементов в иерархии, fiLVCi(x) - функция плотности распределения элементов по уровням н хе [0,1] » C = {Lh,ldrenAx),fch„dre„1(x), ,fcMdrenm{x)} - множество, г/МЛеп/х) - функция

плотности распределения количества сыновей у элементов j-го уровня и х е [0,1] > МЕМтах - верхнее ограничение по использованию памяти в пересчете на один элемент иерархии

Для идентификации элемента в дереве применяются следующие координаты номер уровня, на котором находится элемент, и порядковый номер элемента среди элементов данного уровня На рис 1 представлен пример дерева с расставленными координатами элементов

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

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

Мг = {, , ,Рп , Р у где Р/ - единица функциональности системы

управления иерархическими данными, а и - общее количество таких функций

р=(к Т НЛ» где к, - коэффициент важности данной функции для сис-

I I /' ШЗХ^ ' I *

темы, Ттах, - верхнее ограничение по времени выполнения рассматриваемой функции, Н, - множество описаний вызовов элементарных иерархических операций, Я, = Я,(*,>),о,), ,(И„^„{х,у),от)}, где т - количество описываемых в множестве вызовов, о] ~ вид элементарной иерархической операции, -весовой коэффициент в контексте задачи Г, для у-го вызова операции, ^¡(х.у) — двумерная функция плотности распределения выборки дляу-го вызова операции

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

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

б'=£(*, б'') О)

Производительность функциональной единицы системы рассчитывается на основе данных измерений Пусть Г' ~ время выполнения элементарной иерархической операции о1 заданное количество раз, с учетом, распределенных по закону ё](х>У)' входных данных Тогда производительность при выполнении функциональной единицы системы рассчитывается последующей формуле

" И'

(2)

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

При применении разработанной модели в процессе нагрузочного тестирования возникают следующие задачи

- задача построения реального дерева на основании заданной модели,

- задача построения списка тестовых испытаний для построенного по разработанной модели дерева

Л/й =Ч20,Л„,(х)

1

(1-0 8)

Распределение элементов по уровням

я

8 к

и 5

и §

о

в

о 1>

§

ПеуеКх)

Номер уровня Распределение детей среди элементов одного уровня

« &

о

в

о

0)

§

Номер элемента

Уровень 1

Уровень 2

Уровень 3

Уровень 4

Уровень 5

1 В \ г 1 » 1 « 8 » I « 7

Рис 1 Пример модели данных системы управления иерархическими

данными

Алгоритм построения дерева по заданным функциям плотности распределения элементов дерева по уровням и по количеству детей среди элементов уровня

Для построения дерева, у которого количество элементов было бы равно п и распределено согласно fimu а количество детей у элементов на каждом уровне согласно /снмгет гДе find и /мы, определены на промежутке [0,1] применяется следующий алгоритм

Шаг 1 Определение количества уровней в дереве

Шаг 2 Определение количества элементов на каждом уровне дерева

Шаг 3 В цикле для элементов каждого уровня определяется количество де-

Шаг 1 Определение количества уровней в дереве

На основе первоначальных данных можно сказать, что /¡^¡(х) определяет

а

распределение по о уровням 1(х)сЬс элементов Соответственно необходимо

найти такой коэффициент к, что

j*

nyCTbb/;Jr = *(*,*)

Для поиска к используем алгоритм, основанный на бинарном поиске Шаг 2 Определение количества элементов на каждом уровне Данная задача может быть перефразирована следующим образом Дано X шаров, N пронумерованных от 1 до N корзин и некоторый закон распределения заданный функцией плотности Необходимо распределить шары по корзинам по данному закону распределения Решение задачи

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

Пусть/(.х) - функция плотности распределения определена на промежутке [а, 6] Тогда алгоритм решения рассматриваемой задачи можно записать следующей рекурсивной функцией (см рис 3 ), принцип которой рассмотрен на рис 4 Пусть а,Ь - целые, неотрицательные числа, т = Ь - а,т > 0 Тогда, если ш=1, то на а-ом уровне будет находиться п элементов, иначе распределяем т Определяем, что в

промежутке

а + Ь

а + Ь

,Ь

а,

находится

находится

шаров, а в промежутке

Si+S2

Остаток распределяется в зависимости от ве-

личины дробной части В нашем случае, для распределения элементов по уровням, описанная выше функция должна быть вызвана следующим образом Распреде-литьШары (1, а к ,п)

Шаг 3 Определение количества детей у каждого элемента Распределение детей среди элементов уровня также сводится к решению задачи размещения шаров по корзинам с заданной функцией распределения

center —

4

left + right

factor -

b-a

Knaqe M b «Qp3nny c HOMep left k tuapoa

{ BbiKOA us ct>yHK4Hn

right/actor

total _coum- | f{x)cix

\iifi-xyJ<XKr

[mpw fate \ f -f";- m \

J/(jf)(fc \f{»dx\-k

total __count ~ tmal count

__I____

Pacnpeden itn blUaptAleft, center, [left count § PacnpedesvrmJUapu (center, right, [right __ count\

Pmc. 3. (PyHKUHs PacnpedejiumbLUapbi (left, right, k)

Рис. 4, Иллюстрация работы функции РаспредеяитьШары (а.Ь.п).

Количество элементов на текущем уровне будет равно количеству корзин, а количество элементов на следующем уровне количеству шаров.

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

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

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

- двумерная функция плотности распределения выборки f(x,y), заданная на прямоугольной области [0,a\[0,b]'t

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

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

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

(max level max on level ^ , f x у Л

factor = max^ = —, J factor

Алгоритм распределения тестов может быть описан рекурсивной функцией РаспределитьТесты(f(x,y), tree, п, а, Ь, с, ф (см. рис. 5). В данном вызове f(x,y) -функция плотности распределения выборки; tree - двумерный массив, определяющий дерево; и - количество тестов; [д, 6] [с, d] - область дерева, на которой необходимо распределить п тестов по закону распределения, описываемому функцией плотности f(x,y). После выполнения описанной выше функции мы получим список элементов дерева. Теперь необходимо равномерно перемешать данный список. Этого можно добиться, перемещая элементы в другой список, выбирая элементы из существующего списка случайным образом с равномерным распределением.

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

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

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

- описание модели нагрузки,

- создание плана тестирования,

- тестирование,

- получение оценок критериев эффективности в разрезе функциональных единиц,

- получение интегральной оценки критериев эффективности

Затем анализируется процесс выполнения реляционных операций в рамках системы «клиент-сервер» В основе процесса выполнения операций в системе «клиент-сервер», где в качестве сервера выступает реляционная СУБД, является SQL-запрос, обращенный от клиента серверу, и ответ на него, особенно важно рассмотреть процесс обработки такого запроса Обычно процесс выполнения SQL-запроса обобщают, выделяя следующие четыре фазы декомпозиция, оптимизация, генерация кода, выполнение В нашем случае система управления иерархическими данными содержит в себе РСУБД (далее, СУБД) как самостоятельную подсистему Значит, в обобщенный процесс обработки SQL-запроса следует добавить еще три фазы подготовка запроса, посылка запроса, получение ответа Соответственно, стоимость выполнения SQL-запроса можно представить в следующем виде

1*sq] Тргераге Tjgnd + T0ptimization ' fVun\ Treceive (4)

где Tsqi - общее время выполнения SQL-запроса, Tprepare - время на подготовку SQL-запроса внешней по отношению к СУБД системой, а также сюда следует включить время на генерацию различных производных от хранящихся в базе данных параметров необходимых для обработки запроса, Tse„d - время затрачиваемое на посылку запроса (возможно инициализацию соединения с СУБД), T0pIlmlzatI0n -время на оптимизацию запроса самой СУБД, Tpttfotm - время обработки запроса (выполнения операций реляционной алгебры), Treceive - время затрачиваемое, на получение результатов запроса

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

п

^operation ^Li ft'sql X /-I

где (T^i),- время выполнения i-го SQL-запроса, Торега|ю„ - общее время выполнения операции, п - количество запросов, необходимое для выполнения операции

Исходя из оценки Toperat,on и описанных формул разработчики могут найти причину недостаточной производительности системы Для оценки описанных во ранее критериев эффективности была разработана система тестирования

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

о

Вход 8 функцию^

Находим середину области [а, Ь][с,d] т _ Р координатами [т.* ш} ] а+Ь 2 c + d 2

_____________ *___________

Находим, для каждой т четырех получившихся областей, количество находящихся в них элементов дерева е1епкм_соипЬ и координаты первого элемента дерева в данной области (х^гм.у^щ)

_______ .__________т_

По закону распределения, описываемому^ху), находим интегралы для каждой из четырех областей зит1

Находим количество тестов для каждой области - test count,

Определяем остаток после remainder е [0,4] ,

распределения тестов - remainder remainder-п-¿^test _ count,

Распределяем остаток sum,

тестов по областям в « по одному тесту

порядке убывания / ,sumi

J-1

Дальнейшее распределение тестов Пытаемся по каждой области распределить выделенные для нее тесты

Нет

Да

^ Выход из функции

о

Вызываем функцию Рас предел urn ьТссты([(х,у) tree, testjeounii, DJ

В набор тестов записываем Элемент дерева с координатами

faj)nt.yijlrsj tCSfjCOUnt,

Рис 5 Функция Рас пред ем ить Тест ы (f(x,y), tree, п, а, Ь, с, d)

Также важно обеспечить возможность задания различных планов тестирования, абстрагирование от используемой системы управления базами данных, возможность использования различных исходных данных, также и возможность генерирования исходных данных, совместимость формата выходных данных тестирующей системы с математическими пакетами программ Например, МаШСас)

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

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

Математические функции

Моделирование промежуточной иерархии

Планирование тестирования

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

Реляционное моделирование иерархий

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

Рис 6 иМЬ диаграмма компонентов системы тестирования

Задачей подсистемы тестирования реляционной модели является выполнение плана тестирования на сгенерированном по модели дереве, замер времени выполнения и вычисление критериев производительности

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

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

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

В ходе разработки автоматизированной системы «Бизнес-справочник SIB-INFO RU» разработанная методика оценки эффективности способов реляционного моделирования систем управления иерархическими данными была использована для выбора способа реализации иерархического справочника видов деятельности

Среда эксплуатации

Рис 7 Адаптация архитектуры системы управления иерархическими данными основанной на РСУБД к среде эксплуатации

В ходе разработки автоматизированной системы «Реестр субъектов малого предпринимательства Республики Хакасия» разработанная в данной работе методика оценки способов реляционного моделирования систем управления иерархическими данными была использована для оценки эффективности способов реализации реляционно-иерархического хранилища объектной модели

Ниже описывается использование разработанной методики для разработки автоматизированной системы «Реестр субъектов малого предпринимательства Республики Хакасия» Для определения данных хранилища объектной модели была использована следующая модель

MD = {160000,/^(х) = 120000 х + 20000,{fMJrm{x) = —4== 2051 "},«>}

0 5 л/2-/г

Mb **~ {^det ail » ^general » ^direct _del ail }

-{'•"•f^-owoi'vTT +

ceston ~~ операция поиска множества предков

f f 1 11 Fa, , =4l, «Ml, fix, y) =- , e 2000°'2 +l,o, , где odiSCe„

de,«,/ 'I 0 0001 л/2^ '

dann— операция поиска множества потомков

1 1 ]

I f(x v1 =_ _ r 20шоI2 ,1 „ II, где ochMre„ ~

'П'У) ООООЬл/2^

операция поиска множества сыновей

На основании описанной выше модели было произведено тестирование реляционных реализаций реляционно-иерархического хранилища объектной модели автоматизированной системы «Реестр субъектов малого предпринимательства» Результаты оценки производительности и использования памяти представлены в таблицах 1 и 2

Таблица 1

Результаты оценки производительности автоматизированной системы

«Реестр субъектов малого предпринимательства»

Методы Оценка эффективности для функций Интегральная оценка эффективности

Поиск родителей Поиск сыновей Поиск потомков

Список смежности 0 171 0 064 0 147 0617

Материализация пути 0217 0 135 0 122 0 826

Вложенные множества 15 724 178 475 0 112 388 51

Транзитивное замыкание 0 075 0 066 0 06 0 341

Вложенные интервалы 41 046 30 562 30 504 173 716

Объединенный метод списка смежности и материализации пути 0 071 0 064 0 13 04

Таблица 2

Результаты оценки использования памяти автоматизированной системы _«Реестр субъектов малого предпринимательства»_

Методы Размер, Кб

Список смежности 20144

Материализация пути 45320

Вложенные множества 56086

Транзитивное замыкание 36634

Вложенные интервалы 53904

Объединенный метод списка смежности и материализации пути 35232

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

результат показал метод списка смежности Еще два метода показали несколько худший результат На основании проведенного тестирования было принято решение о реляционной реализации реляционно-иерархического хранилища объектной модели автоматизированной системы «Реестр субъектов малого предпринимательства» по объединенному методу списка смежности и материализации пути

В заключении перечислены основные научные и практические результаты работы

В приложениях описываются методы реляционного моделирования иерархий

ОСНОВНЫЕ НАУЧНЫЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

3 Разработаны алгоритм генерации дерева и алгоритм генерации сценария нагрузочного тестирования по разработанным математическим моделям, основной чертой которых является применение подхода «разделяй и властвуй» для распределения дискретной величины (количество элементов) в соответствии с непрерывными функциями плотности ее распределения Применение данного подхода позволяет пропорционально распределить точное количество элементов

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

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

6 Произведена апробация разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными в процессе разработки реальных программных приложений Применение рассматриваемой методики оценки позволило эффективным способом реализовать иерархический справочник видов деятельности для автоматизированной системы «Бизнес-справочник «Товары и услуги Хакасии и юга Красноярского края» и реляционно-иерархического хранилище объектной модели для автоматизированной системы «Реестр субъектов малого предпринимательства»

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Гребенщиков Н Н, Применение современных Интернет-технологий при разработке сайта ХГУ Вестник Хакасского государственного университета им НФ Катанова Выпуск 4 Серия 1 Информатика - Абакан Издательство Хакасского государственного университета им Н Ф Катанова, 2001 -251 с

2 Гребенщиков Н Н, Пример подхода к процессу разработки интерактивного Интернет-сайта Вестник Хакасского государственного университета им Н Ф Катанова Выпуск 4 Серия 1 Информатика - Абакан Издательство Хакасского государственного университета им Н Ф Катанова, 2003 - 280 с

3 Гребенщиков Н Н, Способ сравнения эффективности методов реляционного моделирования иерархических структур. Вестник Хакасского государственного университета им Н Ф Катанова Информатика - Абакан Издательство Хакасского государственного университета им Н Ф Катанова, 2006

4 Гребенщиков Н Н, Сравнение эффективности методов реляционного моделирования древовидного классификатора бизнес-справочника Вестник Хакасского государственного университета им Н Ф Катанова Информатика - Абакан Издательство Хакасского государственного университета им Н Ф Катанова, 2006

5 Гребенщиков Н Н , Масштабируемое реляционно-иерархическое хранилище объектной модели // Тезисы докладов конференции конкурса «Технологии Microsoft в теории и практике программирования» - НГУ, Новосибирск, 2006

6 Гребенщиков Н Н, Метод реляционного моделирования иерархий // Информатика и проблемы телекоммуникаций - СибГУТИ, Новосибирск, 2006

7 Гребенщиков Н Н, Программа «Нагрузочное тестирование реляционных реализаций систем управления иерархическими данными», Свидетельство об отраслевой регистрации разработки №7440 от 26 12 2006 выдано Отраслевым фондом алгоритмом и программ

8 Гребенщиков Н Н, Моделирование систем управления иерархическими данными для нагрузочного тестирования на начальных этапах разработки программных систем // МИТС-НАУКА международный научный вестник сетевое научное издание, №1, 2007 Зарегистрировано ФГУП НТУ «Информрегистр» 13 02 2007 №0420700032/0007

9 Гребенщиков Н Н , Метод генерации древовидных данных // Тезисы докладов конференции конкурса «Технологии Microsoft в теории и практике программирования» - НГУ, Новосибирск, 2007

Соискатель

Подписано в печать 06 04 2007

Формат 60x84/20 Уел Печ Л 1 Тираж 120 экз

ЗЛО «Инфоцентр Плюс» г Абакан, ул Хакасская 71

1. РЕЛЯЦИОННОЕ МОДЕЛИРОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ ИЕРАРХИЧЕСКИМИ ДАННЫМИ.

1.1. Определение системы управления иерархическими данными.

1.2. Реляционное моделирование систем управления иерархическми данными.

1.3. Оценка эффективности способов реляционного моделирования систем управления иерархическими данными.

Выводы.

2. НАГРУЗОЧНОЕ ТЕСТИРОВАНИЕ КАК МЕТОД ОЦЕНКИ ЭФФЕКТИВНОСТИ СПОСОБОВ РЕЛЯЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ УПРАВЛЕНИЯ ИЕРАРХИЧЕСКИМИ ДАННЫМИ.

2.1. Роль нагрузочного тестирования в оценке архитектурных решений.

2.2. Модель нагрузки для оценки эффективности способов реляционного моделирования систем управления иерархическими данными.

2.3. Критерии эффективности способов реляционного моделирования систем управления иерархическими данными.

2.4. Математическое обеспечение реализации модели нагрузки.

Выводы.

3. МЕТОДИКА ОЦЕНКИ ЭФФЕКТИВНОСТИ СПОСОБОВ РЕЛЯЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ УПРАВЛЕНИЯ ИЕРАРХИЧЕСКИМИ ДАННЫМИ.

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

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

3.3. Применение разработанной методики для адаптации системы к условиям эксплуатации.

Выводы.

4. АПРОБАЦИЯ МЕТОДИКИ ОЦЕНКИ ЭФФЕКТИВНОСТИ

СПОСОБОВ РЕЛЯЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ УПРАВЛЕНИЯ ИЕРАРХИЧЕСКИМИ ДАННЫМИ.

4.1. Разработка и внедрение автоматизированной системы «Бизнес-справочник SIB-INFO.RU».

4.2. Разработка и внедрение автоматизированной системы «Реестр субъектов малого предпринимательства Республики Хакасия».

Выводы.

Актуальность темы

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

Способ реализации управления данными является важным архитектурным решением. Благодаря простоте, естественности структуры данных и манипуля-тивных операций, реляционные СУБД заняли доминирующее положение на рынке и используются при создании большого круга программных систем [101]. Однако при разработке программного обеспечения часто приходится сталкиваться с данными, которые имеют иерархическую структуру. Такие данные обычно являются дополнительными иерархическими онтологиями, которые имеют тесную связь с данными, расположенными в реляционной СУБД. Вследствие такого положения прикладываются значительные усилия по изучению вопросов реляционного моделирования иерархий. В настоящий момент можно с уверенностью констатировать, что существует целый спектр теоретических разработок, технологических решений и конкретных реализаций в области построения иерархических справочников. Этот факт позволяет утверждать, что это направление находится в активной стадии своего развития. Большой вклад в решение проблемы реляционного моделирования иерархических систем внесли Виноградов С.А., Курчидис В. А., Чиркунов В.А., Назанский А.С., Гладков М.В., Сажин А.С., Голованов М., J. Celko, Т. Haughey, М. Hillyer, L. Jonsson, S. Deleurme, D. Forbes, N. Gassiep, V. Tropashko, I. Ben-Gan. Однако, окончательное формирование данного направления еще не произошло. Можно выделить ряд теоретических и технологических проблем, требующих разрешения, и еще большее количество конкретных, прикладных задач, которые ждут реализации.

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

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

В соответствие с целью работы были поставлены и решены следующие научные задачи:

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

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

- определение критериев эффективности способов реляционного моделирования систем управления иерархическими данными;

- разработка методики оценки эффективности способов реляционного моделирования систем управления иерархическим данными;

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

Методы исследования. Для решения поставленных в диссертационной работе задач были применены методы системного анализа, методы объектно-ориентированного анализа и проектирования, методологии UML и IDEF, методы реляционного моделирования, теория чисел, статистические и численные методы, элементы имитационного моделирования.

Объектом исследования является моделирование систем управления иерархическими данными.

Предмет исследования; оценка эффективности способов реляционного моделирования систем управления иерархическими данными. Научную новизну работы составляют:

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

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

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

Разработана и внедрена автоматизированная система «Бизнес-справочник SIB-INFO.RU». Данная автоматизированная система является центральным звеном организации регионального бизнес-справочника по Республике Хакасия. На нее возложены задачи по хранению справочной информации, учету клиентов бизнес-справочника и обеспечению процесса расчетов, публикации справочной информации в сети Интернет, формирование информационного макета печатного издания бизнес-справочника.

Применение разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными при разработке автоматизированной системы «Бизнес-справочник «Товары и услуги Хакасии и юга Красноярского края» позволило эффективным способом реализовать иерархический справочник видов деятельности.

Разработана и внедрена автоматизированная система «Реестр субъектов малого предпринимательства Республики Хакасия». Данная автоматизированная система построена по принципам объектно-ориентированного анализа, проектирования и программирования. Для организации объектно-реляционного отображения, которое бы позволило осуществлять группировку данных, была использована древовидная структура, помещенная в реляционную базу данных. Хранение иерархии в реляционной базе данных позволяет использовать как преимущества иерархии, так и плюсы реляционных баз данных в обращении с линейными структурами.

Применение разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными при разработке автоматизированной системы «Реестр субъектов малого предпринимательства» позволило эффективным образом реализовать реляционно-иерархическое хранилище объектной модели. На защиту выносятся;

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

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

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

- способ применения разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными для адаптации архитектуры таких систем к условиям эксплуатации. Апробация работы

Основные положения и результаты работы докладывались на следующих научно-технических конференциях: Межвузовская научно-техническая конференция «Развитие средств и комплексов связи» (24 ноября 2005 года, г.Новочеркасск), Межвузовская научно-техническая конференция «Военная электроника: опыт использования и проблемы подготовки специалистов» (22 ноября 2005 года, г.Воронеж), Конференция-конкурс «Технологии Microsoft в теории и практике программирования» (23 февраля 2006 года, г.Новосибирск), Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций» (27 апреля 2006 года, г. Новосибирск), Конференция-конкурс «Технологии Microsoft в теории и практике программирования» (25 февраля 2007 года, г.Новосибирск).

Теоретические результаты, отдельные положения, а также результаты конкретных прикладных исследований и разработок обсуждались на научных семинарах Института Информатики и Телематики Хакасского Государственного Университета им. Н.Ф. Катанова (2003-2006 гг.)

Результаты исследований обсуждались на многочисленных рабочих совещаниях и семинарах с профильными специалистами и научными сотрудниками институтов города Абакана (Республика Хакасия) и города Красноярска (Красноярский край).

Публикации

Основное содержание диссертационной работы отражено в 9 печатных работах. В том числе две работы опубликованы в журналах, рекомендуемых ВАК.

Личный вклад автора

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

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

В ходе разработки автоматизированной системы «Бизнес-справочник SIB-INFO.RU» автор участвовал в постановке задачи для Интернет версии справочника, создании методики сбора и заполнения справочной информации, разработке системы управления прайс-листами компаний, разработал общую технологическую архитектуру системы, схемы баз данных, программное обеспечение для трансформации существующей структуры базы данных, технологию и программное средство выгрузки данных бизнес-справочника для создания печатных версий справочника, внутренние технические задания на элементы программного обеспечения, участвовал в оформлении документации на систему.

В ходе разработки автоматизированной системы «Реестр субъектов малого предпринимательства» автор участвовал в постановке задачи, анализе предметной области, разработал архитектуру системы, схемы баз данных, реализовал основные программные модули системы.

Структура работы

Диссертационная работа выполнена на 108 страницах машинописного текста, включающего в себя введение, четыре раздела, заключение, 30 рисунков, 10 таблиц и библиографический список из 129 наименований.

Содержание работы

Выводы

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

1. Разработана и внедрена автоматизированная система «Бизнес-справочник SIB-INFO.RU». Данная автоматизированная система является центральным звеном организации регионального бизнес-справочника по Республике Хакасия. На нее возложены задачи по хранению справочной информации, учету клиентов бизнес-справочника и обеспечению процесса расчетов, публикации справочной информации в сети Интернет, формирование информационного макета печатного издания бизнес-справочника.

2. Применение разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными при разработке автоматизированной системы «Бизнес-справочник «Товары и услуги Хакасии и юга Красноярского края» позволило эффективным способом реализовать иерархический справочник видов деятельности.

3. Разработана и внедрена автоматизированная система «Реестр субъектов малого предпринимательства Республики Хакасия». Данная автоматизированная система построена по принципам объектно-ориентированного анализа, проектирования и программирования. Для организации объектно-реляционного отображения, которое бы позволило осуществлять группировку данных, была использована древовидная структура, помещенная в реляционную базу данных. Хранение иерархии в реляционной базе данных позволяет использовать как преимущества иерархии, так и плюсы реляционных баз данных в обращении с линейными структурами.

4. Применение разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными при разработке автоматизированной системы «Реестр субъектов малого предпринимательства» позволило эффективным образом реализовать реляционно-иерархическое хранилище объектной модели.

ЗАКЛЮЧЕНИЕ

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

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

3. Разработаны алгоритм генерации дерева и алгоритм генерации сценария нагрузочного тестирования по разработанным математическим моделям, основной чертой которых является применение подхода «разделяй и властвуй» для распределения дискретной величины (количество элементов) в соответствии с непрерывными функциями плотности ее распределения. Применение данного подхода позволяет пропорционально распределить точное количество элементов.

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

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

6. Произведена апробация разработанной методики оценки эффективности способов реляционного моделирования систем управления иерархическими данными в процессе разработки реальных программных приложений. Применение рассматриваемой методики оценки позволило эффективным способом реализовать иерархический справочник видов деятельности для автоматизированной системы «Бизнес-справочник «Товары и услуги Хакасии и юга Красноярского края» и реляционно-иерархического хранилище объектной модели для автоматизированной системы «Реестр субъектов малого предпринимательства».

1. Agile Data Home Page. Электронный ресурс. Режим доступа: http://www.agiledata.org

2. Amber Scott W., The Process of Database Refactoring, Электронный ресурс. Режим доступа: http://www.agiledata.org/databaseRefactoring.html

3. Ambler Scott, Sadalage Pramod, Database refactoring. Электронный ресурс. Режим доступа: http://www.databaserefactoring.com

4. Ben-Gan Itzik, Maintaining Hierarchies. Электронный ресурс. Режим доступа: http://www.winnetmag.com/SOLServer/Articles/ArticleID/8826/

5. Beng Chin Ooi, Jiawei Han, Hongjuin Lu, Kian Lee Tan. Index nesting an efficient approach to indexing in object-oriented databases // The VLDB Journal, 1996.

6. Bjorn Regnell, Requirements Engineering with Use Cases a Basis for Software Development, Ph.D. Thesis, Department of Communication Systems, Lund University, 1999.

7. Brandon Daniel, Recursive database structures // Journal of Computing Sciences in Colleges, Volume 21, Issue 2,2005, pp. 295 304.

8. Brian Marick, Methodology Work Is Ontology Work, ma-rick@visibleworkings.com

9. Business directory search engine. US Patent number: 6523021; Inventors: Monberg; James C. (Seattle, WA); Mariani; Rico (Kirkland, WA); Staab; Sanford A. (Woodinville, WA); Applicant: Microsoft Corporation (Redmond, WA); Publication date: 2003-02-18.

10. BUSINESS DIRECTORY. Inventors: INSTANT PAGES PTY LTD (AU), SUDHINDRA RAO (AU); Patent number: W00201406; Publication date: 200201-03. Электронный ресурс. - Режим доступа:http://v3 .espacenet.com/textdes?DB=EPODQC&IDX=W00201406&F=Q&OPN=WOO 201406

11. Celko Joe, Hierarchical SQL. 2004. Электронный ресурс. - Режим доступа: http://www.onlamp.corn/pub/a/onlamp/2004/08/05/hierarchical sql.html

12. Celko Joe, Trees and Hierarchies in SQL for Smarties .- Morgan Kaufmann 2004.- 240pp.http://www.dbazine.corn/ofinterest/oi-articles/celko24 http://www.sqlsummit.com/AdiacencyList.htm

13. Celko Joe, Trees in SQL // Intelegent Enterprise. Электронный ресурс. -Режим доступа:http://www.intelligententerprise.com/OQ 1020/celko.ihtml? requestid=697912

14. Celko Joe, Some answers to some common questions about SQL trees and hierarchies, http://www.intelligententerprise.com/OQ1020/celko 1 2.jhtml

15. Codd E.F. A Relational Model of Data for Large Shared Data Banks. Comm. Of the ACM< 1970, v. 13, no. 6, pp. 377-387. (Пер.: Кодд. Е.Ф. Реляционная модель для больших совместно используемых банков данных // СУБД. 1995. -Ш.-С. 145-160.)

16. Damiani Е., Fugini M.G., Bellettini С. A hierarchy-aware approach to faceted classification of object-oriented components // ACM Transactions on Software Engineering on Methodology, Vol. 8, No. 3, July 1999.77

17. Deleurme Shawn, A Nested Set Implementation in Java and PostgreSQL Электронный ресурс. Режим доступа: http://threebit.net/tutorials/nestedset/tutorial 1 .html

18. Donald Bradley Roberts, Practical analysis for refactoring, Ph.D. Thesis, the Graduate college of University of Illinois at Urbana-Champaign, 1999.

19. Dong G., Libkin L., Su J. and Wong L. Maintaining the transitive closure of graphs in SQL. In Int. J. Information Technology, 1999. Электронный ресурс. Режим доступа: http://citeseer.ifi.unizh.ch/dong99maintaining.html

20. Dong Gouzhu, Su Jianwen. Incremental Maintenance of Recursive Views Using Relational Calculus/SQL // SIGMOD Record, Vol. 29, No. 1, March 2000.

21. Eric W. Weisstein. "Linear Fractional Transformation." From MathWorld-A Wolfram Web Resource. Электронный ресурс. Режим доступа: http://mathworld.wolfram.com/LinearFractionalTransformation.html

22. Forbes Dennis, Versatile High Performance Hierarchies in SQL Server: How to implement the Nested Set Model Электронный ресурс. Режим доступа: http://www.vafla.com/papers/sqlhierarchies/sqlhierarchies.htm

23. Fowler Martin, Pramond Sadalage, Evolutionary Database Design, 2003. Электронный ресурс. Режим доступа: http://www.martinfowler.com

24. Gassiep Naz, Working with hierarchies in relational databases Электронный ресурс. Режим доступа: http://old.mrnaz.com/notes/nestedsets/

25. Goodman Nathan, Oded Shmueli. Tree queries: a simple class of relational queries // ACM Transactions of database systems, Vol. 7, No. 4, December 1982.

26. Haughey Tom, Modeling Hierachies Электронный ресурс. Режим доступа: http://www.tdan.com/special031 .htm

27. Hillyer Mike, Managing Hierarchical Data in MySQL Электронный ресурс. Режим доступа: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

28. Jagadish H.V. Incorporating hierarchy in a relational model of data // SIGMOD Report, 1989.

29. Jonsson Lennart, Representing Trees in a relational DB Электронный ресурс. Режим доступа:http.7/fungus.teststation.com/~ion/treehandling/TreeHandling.htm

30. Larry McCay, If(extremeProgramming.equals(scientificMethod)) Programming as theory building, Электронный ресурс. Режим доступа http://www.java.sys-con.com

31. Libkin Leonid, Wong Limsoon. SQL Can Maintain Polynomial-Hierarchy Queries, 1997. Электронный ресурс. Режим доступа: http://citeseer.ifi.unizh.ch/libkin97sql.html

32. Lu Hongjun. New strategies for computing the transitive closure of a database relation // Proceedings of the 13th VLDB Conference, Brighton, 1987.

33. Ltree PostgreSQL module for materialized path trees Электронный ресурс. Режим доступа: http://www.sai.msu.su/~megera/postgres/gist/ltree/

34. Mackey Aaron, Relational Modeling of Biological Data: Trees and Graphs, 2002. Электронный ресурс. Режим доступа: http://www.oreillynet.eom/pub/a/network/2002/ll/27/bioconf.html

35. Marcio Lopes Cornelio, Refactorings as formal refinements, Ph.D. Thesis, Universiade Federal de Pernambuco, Centro de Informatica, Recife, 2004.

36. Mathews, J. The Moebius Transformation. Электронный ресурс. Режим доступа: http://www.ecs.fullerton.edu/~mathews/fofz/mobius/

37. More Trees & Hierarchies in SQL. Электронный ресурс. Режим доступа: http://www.sqlteam.com/item.asp?ItemID=8866

38. Refactoring Home Page. Электронный ресурс. Режим доступа: http://www.refactoring.com

39. Rick Mugridge, Test Driven Development and the Scientific Method, Department of Computer Science, University of Auckland, New Zealand, r.mugridge@auckland.ac.nz

40. Sander Tichelaar, Modeling Object-Oriented Software for Reverse Engineering and Refactoring, Inauguraldissertation der Philosophisch-naturwissenschaftlichen Fakultzjt, der University Bern, Bern, 14. Dezember 2001

41. Storing Hierarchical Data in a Database Электронный ресурс. Режим доступа: http://www.sitepoint.eom/print/l 105

42. Tree In Sql. Электронный ресурс. Режим доступа: http://c2.com/cgi/wiki7TreeInSql. - Загл. с экрана.

43. Troels' links: Relational database systems. Электронный ресурс. Режим доступа: http://troels.arvin.dk/db/rdbms/links. - Загл. с экрана.

44. Tropashko Vadim, Integer Labeling in Nested Intervals Model Электронный ресурс. Режим доступа: http://www.dbazine.com/oracle/or-articles/tropashko6

45. Tropashko Vadim, Nested Intervals with Farey Fractions .- 2004 Электронный ресурс. Режим доступа: http://arxiv.org/html/cs.DB/0401014

46. Tropashko Vadim, Nested Intervals Tree Encoding with Continued Fractions // SIGMOD Record June 2005, Volume 34, Number 2 Электронный ресурс. Режим доступа: http://arxiv.org/abs/cs.DB/0402Q51

47. Tropashko Vadim, Relocating Subtrees in Nested Intervals Model2003 Электронный ресурс. Режим доступа: http://www.dbazine.com/tropashko5.shtml

48. Tropashko Vadim, Trees in SQL: Nested Sets and Materialized Path2003 Электронный ресурс. Режим доступа: http://www.dbazine.com/tropashko4.shtml

49. William F. Opdyke, Refactoring object-orientired frameworks, Ph.D. Thesis, the Graduate college of University of Illinois at Urbana-Champaign, 1992.

50. Wood William A., Kleb William L. Exploring XP for Scientific Research, IEEE Software, vol. 20, no. 3, pp. 30-36, May/June, 2003.

51. XML для профессионалов, Мартин Д., Бирбек М., Кэй М., Лозген Б., Пинок Д., Ливингстон С., Старк П., Уильяме К., Андерсон Р., Мор С., Балилес Д., Пит Б., Озу Н. М: Издательство «Лори», 2001.

52. Алистер Коберн, Современные методы описания функциональных требований к системам, Издательство «Лори», 2002

53. Андерсон, Джеймс А., Дискретная математика и комбинаторика: Пер. с ангол. М.: Издательский дом «Вильяме», 2003. - 960 с.: ил. - Парал. тит. англ.

54. Архангельский А. Древовидные (иерархические) структуры данных в реляционных базах данных, 2005. Электронный ресурс. Режим доступа: http://www.az-design.ru/Support/DataBase/DBTreeToc.shtml

55. Ахо А.В., Хопкрофт, Д., Ульман Д.Д. Структуры данных и алгоритмы. М.: Издательский дом «Вильяме», 2000. - 384 с.

56. Бен-Ган Ицик, Иерархические структуры, не требующие сопровожде-ния/ZSQL Server Magazine №10,2001. Электронный ресурс. Режим доступа: http://www.osp.ru/win2000/sql/967 print.htm

57. Берзин Вячеслав, Технология нагрузочного тестирования информационных систем с большим объемом данных // ORACLE Magazine, декабрь 2004. Электронный ресурс. Режим доступа:http://www.oracle.com/global/ru/oramag/dec2004/gen loadtestit.html

58. Бизнес//Википедиа свободная энциклопедия. Электронный ресурс. -Режим доступа:http://ru.wikipedia.org/wiki/%25D0%2591%25D0%25B8%25D0%25B7%25D0%25B D%25D0%25B5%25D 1 %25 81

59. Бизнес-справочник «Товары и услуги Хакасии и юга Красноярского края» Электронный ресурс. Режим доступа: http://www.sib-info.ru

60. Буч. Г., Рамбо Д., Джекобсон А. Унифицированный процесс разработки программного обеспечения. СПб.: Питер, 2002. 496 с.

61. Буч. Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. М: ДМК, 2000.432 с.

62. Буч.Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд.СПб.: Невский диалект, 1998. 560 с.

63. Виноградов С. А., Моделирование иерархических объектов (04.06.2001 г.) Электронный ресурс. Режим доступа: http://www.citforum.ru/database/articles/tree.shtml

64. Гаврилов В.Р., Иванова Е.Е., Морозова В.Д. Кратные и криволинейные интегралы. Элементы теории поля : Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. - 492 с.

65. Гайнов А.Т. Теория чисел. Часть 1. Методическое пособие. Новосибирский Государственный университет. Механико-Математический факультет. 1999.

66. Гайнов А.Т. Теория чисел. Часть 2. Методическое пособие. Новосибирский Государственный университет. Механико-Математический факультет. 1999.

67. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. СПб: Питер, 2001. - 368 е.: ил.

68. Гладков М.В. Методы и средства обработки информации в реляционных базах данных : Автореферат диссертации на соискание ученой степени канд. техн. наук :05.13.01,05.13.11/М.В. Гладков. -Пенза, 2004.-21 с. :ил.

69. Гмурман, В.Е. Теория вероятностей и математическая статистика. М.: Высш. Шк., 2005. - 479 е.: ил.

70. Голованов Михаил, Иерархические структуры данных в реляционных БД// RSDN Magazine #0,2002. Электронный ресурс. Режим доступа: http://www.rsdn.ru/mag/main.htm

71. Гребенщиков Н.Н., Гузов М., Развитие методов реализации древовидной иерархии в реляционных базах данных // Материалы конференции «Развитие средств и комплексов связи» Новочеркасск, 2005.

72. Гребенщиков Н.Н., Гузов М., Критерии оценки методов реализации абстрактных типов данных в реляционной модели // Материалы конференции «Военная электроника: опыт использования и проблемы подготовки специалистов» -Воронеж, 2005.

73. Гребенщиков Н.Н., Масштабируемое реляционно-иерархическое хранилище объектной модели. // Тезисы докладов конференции конкурса «Технологии Microsoft в теории и практике программирования» НГУ, Новосибирск, 2006.

74. Гребенщиков Н.Н., Метод реляционного моделирования иерархий. // Информатика и проблемы телекоммуникаций СибГУТИ, Новосибирск, 2006.

75. Громов Ю.Ю., Татаренко С.И. Введение в методы численного анализа: Курс лекций.- Тамбов, госуд. техн. ун-т. 2001.

76. Дейт К. Дж. Введение в системы баз данных, 6-е издание: Пер. с англ. -К.; М.; СПб.: Издательский дом «Вильяме», 2000. 848 с.

77. Долинко В.В., Основы экономики предприятия. Электронный ресурс.- Режим доступа: http://www.ukrlib.boom.ru/ekpr/ekpredpr.html

78. Дьяконов В. Mathcad 8-12 для всех. Полное руководство. Солон,2005.

79. Закон Республики Хакасия «О государственной поддержке малого предпринимательства в Республике Хакасия» от 22.05.1996, №62.

80. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 е.: ил.

81. Келин Ю.Е., Классификация предприятий. Электронный ресурс. Режим доступа: http://www.eabc.edu.ee/~iurikelin/

82. Кельтон Дэвид В., Лоу Аверилл М. Имитационное моделирование. Классика CS. 3-е изд. СПб.: Питер; Киев: Издательская группа BHV, 2004. - 847 е.: ил.

83. Классификатор//Новый словарь русского языка. Электронный ресурс.- Режим доступа: http://www.rubricon.com

84. Классификация (систематизация)//Болыпая советская энциклопедия. Электронный ресурс. Режим доступа: http://www.rubricon.com

85. Книга А.С. Статистика: Учебное пособие/ Алт. госуд. технич. ун-т. И.И. Ползунова. Барнаул: 2003. - 150 с. Издание 2-е, исправленное и переработанное.

86. Кнут, Дональд, Эрвин, Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. Уч. Пос. М.: Издательский дом «Вильяме», 2000.-720 е.: ил.

87. Кнут, Дональд, Эрвин, Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ. Уч. Пос. М.: Издательский дом «Вильяме», 2000. - 720 е.: ил.

88. Кнут, Дональд, Эрвин, Искусство программирования, том 3. Сортировка и поиск, 3-е изд.: Пер. с англ. Уч. Пос. М.: Издательский дом «Вильяме», 2000. - 720 е.: ил. Кнут 3 том

89. Коберн А. Быстрая разработка программного обеспечения. М.: Лори, 2002.314 с.

90. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. - 800с.: ил. »

91. Коннолии Томас, Бегг Каролин, Страчан Анна, Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд.: Пер. с англ. -М.: Издательский дом «Вильяме», 2001. 1120 с.

92. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ / Пер. с англ. под ред. А Шеня. М.: МЦНМО, 2002. -960 е.: 263 ил.

93. Куликов Алексей, Посадим дерево? Электронный ресурс. Режим доступа: http://dull.ru/2Q04/11/11/posadim derevo/

94. Кэй М. XSLT. Справочник программиста. Пер. с англ. -СПб: Символ-Плюс, 2002.- 1016 е., ил.

95. Макаров Е. Инженерные расчеты в MathCad. СПб: Питер, 2003. -448с.

96. Макгрегор Дж., Сайке Д. Тестирование объектно-ориентированного программного обеспечения. К.: ООО «ТИД «ДС», 2002.

97. Малый энциклопедический словарь Брокгауза и Ефрона. Электронный ресурс. Режим flocTvna:http://slovari.yandex.ru

98. Мартыненко С. Объемное тестирование на стадии выбора архитектуры, 2005. Электронный ресурс. Режим доступа: http://software-testing.ru/lib/martvnenko/volume-tesing.htm

99. Мартыненко С. Терминология. Нагрузочное тестирование, 2005. Электронный ресурс. Режим доступа: http://software-testing.ru/lib/martvnenko/term-perf-tesing.htm

100. Мишулович А. Проблема нагрузочного тестирования компонентов биллинговых систем, 2005. Электронный ресурс. Режим доступа: http://software4esting.rit/lib/mishulovir^illing-components-performance-testing.htm

101. Новиков Ф.А. Дискретная математика для программистов СПб.: Питер, 2001.

102. Орлов С. Технологии разработки программного обеспечения. Учебное пособие. СПб.: Питер, 2003. 480 с.

103. Постановление Правительства Российской Федерации от 10.11.2003 № 677 "Об общероссийских классификаторах технико-экономической и социальной информации в социально-экономической области".

104. Постановление Совета Министров Республики Хакасия «О положении о комитете по поддержке и развитию малого предпринимательства при Совете Министров Республики Хакасия и о фонде поддержки малого предпринимательства Республики Хакасия» от 10.01.1996, №8.

105. Постановление правительства Республики Хакасия «О реестре субъектов малого предпринимательства Республики Хакасия» от 17.07.1998, №114.

106. Смирнов С.Н. Задворьев И.С. Работаем с Oracle. Гелиос АРВ, 2002.

107. Смит Артур Б. Реляционные, древовидные и объектно-ориентированные базы данных//М Computing May/June 1996, v.4 п.2, стр.8. Электронный ресурс. Режим доступа: http://inftech.webservis.ru/it/database/oo/index.html

108. Справочник//Болыпая советская энциклопедия. Электронный ресурс. -Режим доступа: http://www.rubricon.com

109. Таха, Хэмди, А. Введение в исследование операций, 6-е издание.: Пер. с англ. М.: Издательский дом «Вильяме», 2001. - 912 с.: ил.

110. Фаулер Мартин, Рефакторинг: улучшение существующего кода. СПб: Символ-Плюс, 2003. 432 е., ил.

111. Фаулер М. Архитектура корпоративных программных приложений. -М.: Издательский дом «Вильяме», 2004.

112. Фаулер Мартин. UML. Основы. 3-е издание. Символ-Плюс, 2005.

113. Федеральным закон № 184-ФЗ "О техническом регулировании" от 27 декабря 2002 года.

114. Эд Барнфилд, Брайен Уолтере, Программирование «клиент-сервер» в локальных вычислительных сетях. М.: Информационно-издательский дом «Фи-линъ», 1997. - 424 с.

115. Экономические и финансовые словари от Глоссарий.ру. Электронный ресурс. Режим доступа: http://slovari.vandex.ru

116. Якобсон А., Буч. Г., Рамбо Дж. Унифицированный процесс разработки программного обеспечения. СПб.: Питер, 2002. 496 с.