Алгоритм сравнительного анализа формальных описаний предметных областей

АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ

УДК 004.652.4

АЛГОРИТМ СРАВНИТЕЛЬНОГО АНАЛИЗА ФОРМАЛЬНЫХ ОПИСАНИЙ ПРЕДМЕТНЫХ ОБЛАСТЕЙ

А.И. Баранчиков, И.И. Яковлев, А.Ю. Громов

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

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

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

- высокую скорость обработки запросов;

- меньший занимаемый объём памяти;

- правильное функционирование;

- отсутствие избыточности;

- понятность и определённость [1-3].

Задача проверки правильности построения логической структуры до сих пор остаётся открытой, поскольку цена ошибки, заложенной в неверном формальном описании предметной области, крайне высока: по оценкам исследований, стоимость исправления ошибки этапа проектирования базы данных до 10 раз выше, чем, например, ошибки при разработке прикладной реализации. Некоторые ошибки проектирования можно скорректировать позже, в процессе эксплуатации, с помощью средств реструктуризации и реорганизации БД, но такие операции являются весьма трудоемкими и дорогостоящими [4-6].

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

Теоретические исследования

Входными данными для разрабатываемого алгоритма являются:

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

- описание предметной области в виде совокупности работающих БД (либо одной БД).

Необходимым условием для успешного анализа является единый способ описания моделей данных моделей. Из известных способов формального описания наиболее подходящим является описание в терминах реляционной алгебры, например, в виде множества функциональных зависимостей (Б-зависимостей).

В простейшем виде БД

г = (цДК,, 5,), г2 (К2, г (К,Б,),...,ц (Кк,^)) задается множеством отношений ц, характеризуемым множеством ключей К, и множеством атрибутов Б,, на основе которых строится множество функциональныхзависимостей:

Г = {К,  Б,,К2  52,...,К,  Б,,...,Кк  Бк}.

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

выявление различий в формальном описании предметной области;

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

анализ возможных причин возникновения различий;

формирование и представление предложений по ликвидации этих различий.

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

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

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

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

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

В результате выполнения алгоритма и анализа его результатов экспертом будет получено уточненное формальное описание предметной области, которое является основой для проектирования схемы РБД (либо её корректировки).

В общем виде схема алгоритма сравнительного анализа формальных описаний предметных областей представлена на рис. 1 и 2.

Рис. 1. Схема алгоритма сравнительного анализа формальных описаний предметных областей

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

Рис. 2. Схема алгоритма сравнительного анализа формальных описаний предметных областей

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

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

отвечающая за синтез формального описания на основе базы данных, являющегося одним из входных данных для работы алгоритма.

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

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

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

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

БД.

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

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

Идентичные атрибуты - атрибуты, относящиеся к одной предметной области и имеющие одинаковые домены [3].

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

На предыдущем этапе работы алгоритма сравнительного анализа

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

Разработка модуля оценки полученной модели

Когда основные классы ошибок определены, можно переходить непосредственно к оценке полученных моделей. Следует отметить, что, помимо рассмотренных выше аспектов сравнительного анализа формальных описаний, важным является то, что формальные описания представляют собой множества ФЗ, а левая и правая части каждой функциональной зависимости представляют собой множества атрибутов. Из определения множества нам известно, что порядок элементов в нём не играет роли. Следовательно, алгоритм должен учитывать то, что порядок функциональных зависимостей в формальном описании и порядок атрибутов в левой и правой частях функциональных зависимостей могут быть произвольными.

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

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

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

/Вывести уникальные ФЗ

каждого описания -1

Выход ^

Рис. 4. Детализация алгоритма сравнения полученных описаний

Заключение

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

Список литературы

1. Дейт К.Дж., Дарвен Хью. Основы будущих систем баз данных. Третий манифест / пер.: С.Д. Кузнецов, Т.А. Кузнецова. Изд-во Янус-К, 2004. 656 с.

2. Крёнке Д. Теория и практика построения баз данных. 8-е изд. Питер, 2003. 800 с.

3. Мейер Д. Теория реляционных баз данных / пер. с англ. М.: Мир, 1987. 608 с.

4. Rolland F.D. The Essence of Databases. Вильямс, 2002. 256 с.

5. Диго С.М. Базы данных: проектирование и использование: учеб. пособие для вузов. М.: Финансы и статистика, 2005.

9

6. Баранчиков А.И. Синтез информационных структур хранения данных на основе анализа предметных областей. Рязань: ГУП РО «Рязанская областная типография», 2014. 231 с.

Баранчиков Алексей Иванович, канд. техн. наук, доц., alexibainbox.ru, Россия, Рязань, Рязанский государственный радиотехнический университет,

Яковлев Иван Игоревич, магистрант, ivan.formatagmail.com, Россия, Рязань, Рязанский государственный радиотехнический университет,

Громов Алексей Юрьевич, канд. техн. наук, доц., gromov.a.ya evm.rsreu.ru, Россия, Рязань, Рязанский государственный радиотехнический университет

THE AN ALGORITHM OF A COMPARA TIVE ANALYSIS OF FORMAL DECRIP TIONS OF SUBJECT AREAS

A.I. Baranchikov, I.I. Iakovlev, A. Y. Gromov

The comparative analysis algorithm of formal descriptions of subject areas is proposed. The algorithm allows to draw a conclusion about the correctness of the construction of the logical structure of the domain, based on the structure of existing databases and models prepared by the expert.

Key words: subject area, database, functional dependence, attributes, comparative analysis, formal description.

Baranchikov Alexey Ivanovich, candidate of technical science, docent, alex-ib a inbox.ru, Russia, Ryazan, Ryazan State Radio-Engineering University,

Iakovlev Ivan Igorevich, undergraduate, ivan.formatagmail.com, Russia, Ryazan, Ryazan State Radio-Engineering University,

Gromov Aleksey Yurievich, candidate of technical science, docent, gromov. a.ya evm.rsreu.ru, Russia, Ryazan, Ryazan State Radio-Engineering University