Информационный граф системы обработки

 

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

Входные данные отобразим матрицей Н, элемент которой h_ik=1, если входной набор данных N_1i используется вычислительным мо­дулем k. Этот же элемент h_ik=0, если это не имеет места.

Выходные данные формально отобразим матрицей Е, элемент которой e_kj=1, если набор данных N_3j получен в результате работы вычислительного модуля k. Элемент матрицы e_kj=0 — в противном случае.

Матрица взаимосвязи входных и выходных данных Q=HÄE.

Элемент матрицы q_ij=1, если входной набор данных N_1i исполь­зуется для получения выходного набора данных N_3j. Элемент мат­рицы q_ij=0, если это не имеет места. На рис. 3.26 представлена связь вычислительного модуля ВМ_k с входным набором данных N_1i и выходным набором данных N_3j.

Структура модуля по преобразованию данных задается матрицей Q, связь модуля с набором данных N_1i определяется матрицей Н, связь модуля с набором данных N_3j — матрицей Е. Матрица Q соответствует ориентированному графу взаимосвязей между данными (этот граф получил название информационного графа системы). Вершинами графа являются родные, промежуточные и выходные наборы данных. Дуги графа отображают информационные связи между этими наборами (рис. 61).

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

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

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

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

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

Независимо от используемого алгоритма вычислительный мо­дуль выполняет определенные процедуры, включающие в себя дей­ствия над данными. На логическом уровне возникает задача специ­фикации действий, т. е. определение входных и выходных наборов данных для действий, а также взаимосвязей между различными действиями. При этом можно выделить два типа функциональных (логических) элементов: элементы — действия Q и элементы — объекты действий D. Элементы действия Q характеризуются внешними связями и ресурсами. Такой элемент реализует опреде­ленное преобразование над данными с использованием в качестве ресурсов элементов типа Q и элементов типа D. В качестве объектов действий выступают данные, которые характеризуются именем, типом и значением. Тип определяет множество значений, которые принимают объекты данного типа. Объект действий задается струк­турой, т. е. составом компонентов и связей между ними. Элемент Q взаимодействует с элементами D₁, D₂, D₃ через связи типа: 1 — «вход», 2 — «выход», 3 — «вход — выход» (рис. 62).

Совокупность элементов действий Q и элементов объектов дей­ствий, т. е. данных D, образует информационную схему. Естествен­но, что одни и те же данные могут быть использованы различными элементами действий. На рис. 63 представлена информационная схема, включающая элементы действий Q₁…Q­₃ и элементы данных D₁…D₄. В схеме присутствуют связи типа 1 — «вход» и типа 2 — «выход». Связи первого типа формально записываются в виде D in Q, а второго типа — D out Q. Информационная схема отоб­ражается матрицей

.

Матрица В построена непосредственно по информационной схеме. Данные D₁ используются действиями Q₁ и Q₂, что соответствует первой строке матрицы. Данные D₂ формируются действием Q₃ что отображается второй строкой матрицы. Данные D₃ вычисляются действием Q₁ и используются действием Q₂, что соответствует третьей строке. Данные D₄ вырабатываются действием Q₂ и исполь­зуются действием Q₃ (четвертая строка). Исключим из информаци­онной схемы элементы действия Q и найдем связи по данным, что на логическом уровне соответствует информационному графу си­стемы. Учтем при этом частоту активизации действий. При одиноч­ном запросе суммарное количество действий, использующих дан­ные d­­_i, обозначим через z_ii, а суммарное количество действий, использующих данные d_j совместно с данными d_i, определим как z_ij. Члены z_ij, z_ij являются элементами матрицы Z=B´B^t.

Для рассмотренного примера

.

Полученной матрице будет соответствовать граф, изображен­ный на рис. 64.

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

Вводя в матрицу Z частоту активизаций действий f, получим матрицу

ZF=(B·f)´B^t.

Элемент матрицы zf_ij показывает частоту использования данного d_i с учетом частоты активизации действий. Соответственно элемент zf_ij отображает частоту совместного использования данных d_i, d_j. По значениям этих частот данные могут объединяться в запи­си, а записи — в массивы. При этом обеспечивается минимизация числа обращений к записям в процессе обработки и корректировки информации.

При известной частоте активизации действий, заданной мат­рицей — строкой f, нетрудно по приведенной выше методике найти ZF. Например, для f=|1 2 5|

.

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

Если в информационном графе системы содержится N вершин и граф отображает полносвязанную систему, то максимальное чис­ло связей составит N². Для определения степени связности графа, представленного на рис. 64, найдем коэффициент совместного использования данных d_i, d_j в виде . Элемент s_ij=1, если данное d_i всегда используется совместно с данным d_j. При s_ij=0 данные d_i, d_j совместно не используются. Объединяя s_ij при l≤i≤N, j≤l ≤N, находим матрицу коэффициентов совместного использова­ния данных. Для рассмотренного графа N=4 получаем

.

Элементы главной диагонали этой матрицы характеризуют вну­треннюю связность элементов данных, остальные элементы матрицы определяют связность их между собой. При s_ij=0 для i¹j

Получаем разделение данных на независимые компоненты. Коэф­фициент связности , он определяется совокупностью вутренних и внешних связей элементов данных, т. е. k_s=k_{s in}+k_{s оut}.

При отсутствии внешних связей k_{s оut}=0, к_s=к_{s in}. Внутренняя связность данных может быть определена в виде . В качестве критерия реорганизации информационной схемы используют зачастую относительный коэффициент связности . Объединение отдельных сильно связанных элементов данных позволяет увеличить значение относительного коэффициен­та связности. Этот коэффициент может быть изменен, если перераспределяются функции между элементами действий.