Каноническая структура информационной базы

При известной инфологической модели предметной области, наличии вычисли­тельного и информационного графов возникает проблема создания модели накопления данных, в основе которой лежит задача выбора хранимых данных. Пусть совокупность используемых наборов дан­ных N разделена на N₁ первичных (входных), N₂ промежуточных и N₃ выходных наборов данных, т. е. N=N_lÈN₂ÈN₃. Получение наборов данных N₃ осуществляется на основе вычислительных ал­горитмов и алгоритмов корректировки. Вычислительный алгоритм представляется вычислительной схемой, т. е. подграфом вычислительного графа. Алгоритм корректировки базируется на множестве первичных данных N₁. Даже при наличии лишь двух классов ал­горитмов возникает задача выбора типа алгоритма в соответствии с запросом пользователя. Если по запросу необходимо получить некоторый набор данных, то в качестве критерия выбора типа алгоритмов можно использовать полное время создания этого на­бора по данному запросу. При использовании вычислительного алгоритма это время складывается из времени, которое затрачива­ется на получение входных наборов данных для выбранного вычис­лительного модуля, и времени вычислений набора данных этим модулем. Для сравнения необходимо найти время, которое затрачи­вается в случае применения алгоритма корректировки. Корректи­ровка набора целесообразна, если структура данных уже ранее была задана в одном из предыдущих запросов. В качестве дополнитель­ного ограничения при решении задачи выступает объем использу­емой памяти. Рациональное сочетание вычислительных алгоритмов и алгоритмов корректировки данных позволяет уменьшить суммар­ное время реализации всех запросов при накоплении данных.

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

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

2) формирование логических записей на основе объединения значений реквизитов;

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

Упорядочение ключевых реквизитов отношений должно базиро­ваться на возможности физической реализации информационной базы. Учитывая, что современные СУБД не могут реализовать n-арные отношения между данными, представим любое отношение в виде совокупности бинарных отношений. Это означает упорядоче­ние реквизитов, входящих в ключ каждого функционального от­ношения Ф, что можно осуществить на основе построения графа, отображающего (d_i d_j)², где l¹j; ij=1-N; 1≤r≤N-1. Для этого графа матрица Q, отображающая взаимосвязь между отдельными данными и группами данных, имеет вид

В общем случае под d_i, d_j можно понимать некоторые обобщенные информационные элементы, представляющие собой элементы данных либо группы, составленные из этих элементов: q_ij=l, если существует взаимосвязь (в том числе возможна и семантическая) между элементами d_i, dj q_ij=0 при отсутствии взаимосвязи. Если строка матрицы Q содержит все нулевые элементы, то этой строкой отображаются входные данные. В информационном графе эти данные соответствуют корневым вершинам. Если столбец матрицы Q содержит все нулевые элементы, то он отображает терминальные, т. е. выходные, данные. На информационном графе эти данные соответствуют концевым вершинам. Остальные информационные элементы, отображаемые строками и столбцами матрицы Q, отне­сем к групповым элементам. На информационном графе они располагаются в промежуточных вершинах. Объединение множеств значе­ний реквизитов можно выполнить на основе оценки взаимосвязи групповых элементов с подчиненными им выходными. Тогда для группы конечных вершин (терминальных элементов) выделяется множество групповых висячих вершин d^r, d^rÎD. Для множества d^r может быть построена матрица достижимости вида Q^r, представ­ляющая собой квадратную матрицу с числом строк и столбцов, соответствующим количеству элементов в выделенном множестве d^r. При переходе к логическому уровню представления информацион­ной базы информационные элементы и взаимосвязи между ними упорядочиваются по уровням иерархии. Для этого определим мно­жество предшествования и множество достижимости. Для информа­ционного элемента d_j матрицы Q множество предшествования П(d_j) определяется из совокупности информационных элементов d_i соот­ветствующих единичной записи в j-м столбце. Анализируя множест­во H(d_j), устанавливают базовые типы структурных элементов, на основе которых формируются информационные группы. Элементам, для которых П(d_j)=Æ, соответствуют промежуточные вершины графа. Из матрицы Q для элемента d_j выявляют и множество достижимости этих данных D(d_j). Это множество формируется за счет элементов d_i, которым соответствуют единичные записи в j-й строке матрицы Q. Тогда элементы данных d_j принадлежат группе r, т. е. определяются как d_j, если . На основе этого условия группы итеративно разбиваются по уровням иерархии, начиная с верхнего уровня. Группы самого верхнего уровня называ­ются корневыми группами, поскольку они располагаются в корне­вых вершинах графа. Группы следующих рангов располагаются в промежуточных вершиных, доступ к которым возможен через корневые группы. Поэтому с помощью корневых групп определяются точки входа к данным информационной базы. Состав информационных элементов, входящих в группу , можно определить, включив в нее элементы d_i которым соответствуют единичные записи в j-м столбце матрицы Q. Упорядочивая таким способом элементы матрицы Q, получают структурированный граф, в котором возможные точки входа соответствуют групповым элементам первого уровня, конечные вершины — выходным данным. В промежуточных вершинах располагаются групповые элементы различных уровней иерархии.