Автореферат (Методика формирования реляционных таблиц на основе информации табличного вида), страница 3

Пусть имеется отношение R:R=(A1, …, Ai, …, Am, …, Ak), i  1, k , где к − степень отношения; Ai − атрибутотношения.Аi  {ei1 ,..., ei j ,..., ein } j  1, n , где n − мощность отношения, ei j − j - й элементатрибута Ai;Am  {em1 ,..., em j ,..., em n } j  1, n , где n − мощность отношения, em − j - й элементатрибута Am.Необходимо найти такие атрибуты Аi ,…, Аm чтобы обеспечилась истинностьвыражения: concat( ei , …, em ) ,...,  concat( ei ,…, em ) ,...,  concat( ei ,…, em n )Необходимо найти такое сочетание атрибутов, чтобы конкатенация их значенийбыла уникальна. При этом:− проверяемый кортеж атрибутов может включать несколько атрибутов;− число возможных сочетаний атрибутов может быть очень большим − этозависит от степени отношения (общего числа атрибутов в отношении);− ключевой атрибут может быть только один;− может не найтись таких атрибутов, в этом случае назначают суррогатныйключ.Минимальность.

Минимальность ключевого поля рассматривается в двухаспектах.В первой части требования во главу угла ставится объем памяти, которыйнеобходим для хранения значений атрибутов, входящих в первичный ключ.Поэтому самая очевидная целевая функция – минимальное число атрибутов,min A1, , Ai, , Ak , i  1, k , где к − числовходящих в первичный ключ:атрибутов, входящих в ключ; Ai − атрибут отношения, входящий в ключ.Строго говоря, целевая функция следующая: min(Length(Ai )+…+ Length(Aк )).Во второй части требования под минимальностью первичного ключаподразумевается отсутствие в составе ключа атрибута, значения которогоуникальны.

Пусть первичный ключ К представлен множеством атрибутов:j11j12jnK  ( A1 ,..., Ai ,..., Aj ,..., Ak ) , i  1, k , где k – число атрибутов, входящих в первичныйключ; Ai – i - й атрибут отношения, входящий в первичный ключ. Тогда должнобыть истинно выражение  ( ei , …, ,..., ei ,…, ,..., ei ).Алгоритмы назначения первичных ключей в ИТВ. Предложенынеформальные (описательные) и формальные алгоритмы назначения первичныхключей. Из соображений объема приводится только один неформальный алгоритм– алгоритм поиска ключа, включающего пару атрибутов:1njMKA 2   , где MKA 2 − множество пар атрибутов, которые претендуют на рольпервичного ключа.Пусть имеется отношение R: R=(A1, …, Ai, …, Ak), i  1, k , где к – степень отношения;Ai –атрибут отношения.

MPA   .Ищутся все возможные сочетания пар атрибутов и запоминаются в MPA :Cnt=0S = Concat (Ai , Аj)DO i = 1 to k-1MPA (Cnt) = MPA + SDO j = i+1 to kEND jCnt = Cnt + 1END iТаким образом, в массиве MPA сформируются все возможные пары атрибутов, а всчетчике Cnt хранится их количество.Проверяются все пары на уникальность.MUP =  /* Массив пар атрибутов, представляющих собой атрибуты, всесоответствующие пары значений которых уникальны */Cnt1 = 0DO i = 1 to CntS = MPA(Cnt)/* По сути S представляет собой пару атрибутов (Ai, Аj)Ai  ( ei1 ....eim ) , где ei1 − 1-й элемент домена с атрибутом Ai , eim − m-й элемент домена сатрибутом Ai .Aj  (e j1 ....e jm ) , где e j1 − 1-й элемент домена с атрибутом A j , e jm − m-й элементдомена с атрибутом A j , m − мощность отношения.

*/DO n = 1 to m/* Для каждой пары атрибутов (Ai, Аj)e j1 )  ....  Concat( ( e j1 , e jm ) */выполняется проверка условия Concat( e i1 ,END n/* Если текущая пара атрибутов имеет все соответствующие пары значенийуникальными, то эта пара добавляется к массиву пар с уникальными значениями: */Cnt1 = Cnt1 + 1MUP( Cnt1) = S13END iЕсли претенденты на ключевой атрибут найдены, т.е.

MUP   , то для проверкивторого требования минимальности выполняется переход к алгоритму поиска первичногоключа на основе 3-х атрибутов и далее по аналогии. Разработчик на любом шаге поискаможет принять решение о назначении суррогатного ключа.Алгоритмы назначения внешних ключей в ИТВ. В диссертациипредложены неформальные и формальные алгоритмы назначения внешнихключей в заполненных таблицах. Ниже приведен формальный алгоритм.П1. Осуществляется поисквсех возможных сочетаний пар таблицанализируемой БД.Пусть имеется табличное пространство Т:/* Т=(Т1, …, Тi, …, Тm, …, Тk), i  1, k , где к – число прикладных таблиц БД */МРТ =  _ _ Массив всех пар таблиц БД/* Ищутся все возможные сочетания пар таблиц */Cnt=0DO i = 1 to k-1 _ _ к – число таблиц БДDO j = i+1 to kCnt = Cnt + 1_ _ счетчик числа пар таблицS = Concat (Тi , ТJ)MPT (Cnt) = SEND jEND iП2.

Для каждой пары таблиц из массива MPT выполняется поиск внешнего ключаF = 0 _ _ флажок наличия связанных ключейCnt1 = 0 _ _ счетчик совпаденийDO i = 1 to Cnt _ _ – число пар таблиц БДDO l = 1 to C1_ _ – степень 1-й таблицы из i-й парыDO m= 1 to C2 _ _ – степень 2-й таблицы из i-й парыDO j= 1 to M1_ _ −мощность 1-й таблицы из i-й парыDO k= 1 to M2_ _ −мощность 2-й таблицы из i-й парыIf el j = emk Then Coun1 = Coun1 + 1END kEND jIf Coun1 >= Max(M1, M2) ThenBeginРrint (“Для пары таблиц ”, i, “столбцы”, l, “ и ”, m)Рrint (“ претендуют на первичный и внешние ключи”)Cnt1 = 0F=1EndEND mEND l14END iIf F = 0 Then Рrint (“ внешних ключей не обнаружено не для одной из таблиц”)Следует обратить внимание на то, что атрибуты, предложенные алгоритмом вкачестве связанных атрибутов, могут не удовлетворять разработчика, поэтомунеобходимо предоставить ему возможность окончательного решения.Суть метода назначения ключевых полей в ИТВ состоит впреобразованииобъектовсоответствующихИТВРвобъектысоответствующие РТР на основе использования требований к ключевымполям, предложенного комплекта алгоритмов и процедур, методикивзаимодействия разработчика и подсистемы.В четвертой главе «Методика формирования РТ на основе использованиязаполненных ИТВ» решена задача формализации методики формирования РТР наоснове использования заполненных ИТВР.

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

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

Укрупненная операторная модель формирования РТР на основеиспользования заполненных ИТВР приведена на рисунке 5.Рис. 5. Укрупненная операторная модель формирования РТР на основеиспользования заполненных ИТВРОператор операторной модели (элипс) соответствует одной или болеечеловеко-машинной процедуре. Состояние операторной модели (прямоугольник)соответствует начальному, промежуточному и окончательному состоянию ИТВР.15В диссертации выполнено 11 итераций построения операторной моделиметодики преобразования ИТВР в РТР. Модель анализировались и уточнялась. Врезультате получена результирующая операторная модель процессапреобразования ИТВР в РТР, представленная на рис. 6.Рис.

6. Операторная модель процесса преобразования ИТВР в РТРЗдесь: ОППс − оператор формирования связей между таблицами ИТВ;СООПс − состояние модели, соответствующее автоматической генерации системыоценок результатов импорта; ОПРУс − оператор принятия решений относительноуправляющих воздействий после анализа системы оценок результатовформирования связей; ПППРс − состояние модели, соответствующееформированию системы оценок результатов формирования связей разработчикомРТ.В соответствии с моделью после каждого выполнения оператора с помощьюавтоматизированных средств выполняется проверка промежуточного состояниятаблицы ИТВР на соответствие модели РТР.

Успешным завершением работы врамках разработанной модели методики считается полное соответствие таблицы,описываемой моделью ИТВР, таблице, описываемой моделью РТР.Мотивация перехода от операторной модели к модели, построенной наоснове аппарата сетей Петри. Операторная модель, построенная на основеанализа отличий моделей ИТВР и РТР, позволила выделить основные компонентычеловеко-машинной подсистемы преобразования, определить порядок ихиспользования, сформировать связи между ними.

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