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

 

При известной инфологической модели предметной области, наличии вычисли­тельного и информационного графов возникает проблема создания модели накопления данных, в основе которой лежит задача выбора хранимых данных. Пусть совокупность используемых наборов дан­ных 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, получают структурированный граф, в котором возможные точки входа соответствуют групповым элементам первого уровня, конечные вершины — выходным данным. В промежуточных вершинах располагаются групповые элементы различных уровней иерархии.

Выбор ключевых реквизитов

 

Выделение групповых элементов и состава информационных элементов в группах позволяет с помо­щью ориентированного графа построить траекторию доступа к каждому информационному элементу группы. Доступ осуществляется через корневую вершину графа. Для построения ключевых реквизи­тов необходимо проанализировать отношения между групповыми информационными элементами. Поиск информационных элементов в базе осуществляется по требованиям пользователя. Если k- е тре­бование пользователя содержит D_k элементов, выбираемых из об­щего числа структурных элементов инфологической модели предметной области, то можно построить матрицу смежности s_k для информационного требования D_k. Элемент этой матрицы s_ij=1, если существует связь между элементами d_i, d_j в требовании D_k. На основании элементов могут быть названы элементы , соответ­ствующие групповым информационным элементам базы. В зависи­мости от характера групп выделяют , . Этим элемен­там будут соответствовать простые группы. Если , , то получим группы — массивы. Для простых групп образуют про­стой ключ, для групп массивов — составной ключ, включающий в себя основной и вспомогательный ключи. При этом основной ключ определяется терминальным, конечным элементом, входящим в состав группы массива. Выделение основных ключей должно быть неизбыточным, поэтому необходимо установить и устранить дуб­лируемые терминальные конечные элементы данных.

Пусть групповому элементу , соответствует множество тер­минальных элементов , а групповому элементу d) — множест­во терминальных элементов D (d'X Известно, что групповые элеме­нты семантически связаны, если . Соответственно семантическая независимость групповых элементов удовлетворяет условию . Если последнее условие выполняется для всех попарно выбираемых групповых элементов данного уровня иерархии, а затем и для всех более высоких уровней, то дублирова­ние отсутствует. Если условие не выполняется, то имеют место дублируемые терминальные, конечные элементы. Устранение дуб­лируемых терминальных элементов достаточно легко осуществля­йся, если групповые элементы построены на одном и том же типе отношений.

Пусть групповой элемент принадлежит уровню иерархии n, а элемент — уровню иерархии m, причем m<n. При наличии пути на графе из элемента к элементу следует убрать дублиру­емые терминальные элементы из множества . Удаление терми­нального элемента должно быть отражено и в матрице Q. Это означает, что коэффициент q_ij=1, показывающий ранее связь между элементами d_i, d_j, становится равным нулю. Если групповые элементы , построены на разных типах отношений, то устранение терминальных элементов осуществляется эвристически с использованием той же идеи: расположением терминального элемента на более высоком уровне иерархии и устранением дублируемого элемента на нижнем уровне. Размещение терминальных элементов на более высоких уровнях иерархии в графе обеспечивает уменьшение времени доступа к конечному элементу, так как сокращается путь от корневой вершины до терминального элемента в графе.

При построении канонической структуры информационной базы необходимо устранить также избыточные связи между групповыми элементами. При наличии таких связей по одному и тому же ключу могут вызываться разные групповые элементы данных, что являет­ся недопустимым. Избыточная связь между группами , может на графе представляться непосредственно дугой (i,j), соединяющей групповые элементы данных, либо путем, включающим в себя ряд дуг. Если избыточной оказывается дуга (i,j), то она легко об­наруживается по матрице Q для элемента q_ij= 1. Заменяем этот элемент на нулевой, что соответствует устранению избыточной дуги. Если путь, связывающий групповые элементы данных, вклю­чает несколько дуг, то необходимо найти матрицу Q^k, где к=2,3,...,N_k, N_k — максимальное число групповых элементов данных. Тогда получим квадратную матрицу, элемент которой показывает чис­ло путей, ведущих из группы группу . Если в исходной матрице Q элемент q_ij= 1, а в полученной матрице Q^k элемент , то связь является избыточной. Для удаления этой связи заменяем q_ij= 1 на нулевой элемент. Граф, получаемый после удаления избы­точных терминальных элементов и избыточных связей между груп­повыми элементами данных, определяет каноническую структуру информационной базы. Таким образом, каноническая структура задает логически не избыточную информационную базу. Выделение групповых элементов данных в канонической структуре позволяет объединить множество значений конечных элементов (реквизитов) в логические записи и тем самым упорядочить их в памяти ЭВМ. Структура логических записей и связей между ними должна быть такова, чтобы обеспечить минимум суммарного времени работы с наборами данных как при решении функциональных задач, так и при их корректировке. Поэтому необходимо установить харак­теристики канонической структуры информационной базы.

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

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

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

Т= ||t_i||, где t_i — мини­мальное время доступа к терминальным элементам d_i, входящим в группу . Если функциональная задача решается на основе вычис­лительного алгоритма a_j, то время работы алгоритма с реквизита­ми d_i определяется как где — время поиска реквизита d_i при решении задачи на основе алгоритма а_j. Значение этого времени зависит от вида обработки реквизита d_i в выбранном алгоритме (возможна последовательная обработка значений дан­ных либо обработка по ключу). При использовании алгоритмов коррекции корректируются все отношения, которые содержат изме­няемый ключевой реквизит и зависимые от него реквизиты. Значе­ние времени работы алгоритма с данными определяется количе­ством копий, присутствующих в корректируемых реквизитах. На уровне канонической структуры число копий задается количеством экземпляров терминальных элементов, входящих в группу . Обыч­но алгоритм коррекции имеет возможность обращаться по ключу к информационным элементам базы данных

, где , если ; , в противном случае. Методика постро­ения канонической структуры информационной базы практически не меняется в зависимости от того, строится централизованная либо распределенная информационная база. При создании распре­деленной информационной базы матрица Q раскрывается для каж­дого пользователя. На графе для каждого пользователя формиру­ются групповые и терминальные элементы данных. Полное множе­ство групповых элементов находится путем пересечения групповых элементов данных отдельных пользователей. Таким образом, каноническую структуру информационной базы можно считать универ­сальной формой представления мифологической модели предмет­ов, области и безызбыточной формой модели накопления данных. От канонической структуры переходят к логической структуре информационной базы и к физической организации информационных массивов. Каноническая структура является также основой автоматизации основных процессов предпроектного анализа предметной областей пользователей.