Эффективность обработки информации при проведении технической диагностики сложных объектов вычислительных систем (ВС) во многом определяется структурой БД системы технической диагностики [1-4]. Локальные БД являются функционально законченными эле­ментами и для них должны быть спроектированы логические и физические структуры, поддерживаемые конкретными типами систем управления базами данных (СУБД) и операционных систем [6] .

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

, (1)

где – время реализации р-го запроса пользователя, а – время реализации p-го задания на корректировку.

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

Время реализации р-го запроса пользователя складывается из следующих составляющих:

, (2)

где – время работы программ прикладного и сеансового уровней протоколов, обеспечивающих декомпозицию запроса на под­задачи и управление их реализацией;

– время реализации р-го запроса в локальной БД;

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

– время иниции­рования и передачи запроса (подзадачи) в локальную БД (узел ВС).

Время работы программ прикладного и сеансового уровней протоколов определяется как

, (3)

где – время формирования одной подзадачи;

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

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

, (4)

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

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

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

, (5)

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

– количество процедур сборки, опреде­ляемое количеством порожденных подзадач.

Время поиска требуемых типов записей определяется как

, (6)

где – время поиска требуемых записей (блоков) в локальной БД; – время ожидания доступа и считывания информации из БД; – время обмена между ВЗУ и оперативной памятью; – количество считываемых блоков при выполнении р-го запро­са.

Обозначим

, (7)

где – время ожидания доступа к БД и поиска требуемых записей (блоков).

Время поиска и время обмена определяют общее процессорное время, т.е.

. (8)

Время поиска информации в локальной БД определяется ха­рактеристиками физических методов организации данных и параметрами устройств ВС [5].

Время обмена данными между локальной БД и оператив­ной памятью определяется характеристиками процедур считыва­ния (записи) информации и объемом считываемой информации:

, [9]

где – время считывания (записи) единицы инфор­мации из локальной БД;

– объем считываемой информации.

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

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

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

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

Н = {} – множеству типов записей; II – матрице раз­мещения типов записей по узлам ВС; – матрице семантической смежности типов записей; – матрице типов отношений между логическими записями; I –матрице состава типов записей – необходимо определить количество ло­кальных БД, расположенных на каждом узле ВС, их логические структуры, обеспечивающие оптимальное функционирование БД (в смысле критерия эффективности оптимальной логической струк­туры БД) и удовлетворяющие структурным и системным огра­ничениям, накладываемым конкретными системами управления базой данных (СУБД) и операционными системами.

Для определения оптимального количества локальных БД в узлах ВС необходимо решить задачи нормализации графа логической структуры , r-го узла ВС; определения несвязных и слабо связных компонентов (подграфов) графа логической струк­туры r-го узла; проектирования локальных БД, поддерживаемых конкретными системами управления базой данных (СУБД).

Граф логической структуры r-го узла ВС определяется как множество типов записей, размещенных на r-м узле ВС, которые соединены между собой множеством логических связей.

На основании информации, зафиксированной в сетевом ката­логе, характеризующей распределенность типов записей по узлам ВС и формализованной в виде матрицы , определим подмножество типов записей , расположенных на r-м узле ВС: .

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

Для определения подграфов графа логической структуры r-го узла ВС решается следующая задача. Пусть – мно­жество типов записей первого уровня иерархии графа . Мно­жество есть минимальное множество вершин графа , из которого достижимы все вершины, т. е. является базой графа [3]. Пусть – множество достижимости базы , тогда , и . Определим множество достижимости для каждого типа записи множества :

,

где n.

Анализ попарных пересечений множеств достижимости позволяет выявить несвязные компоненты (подграфы) в графе логичес­кой структуры r-го узла ВC. Два подграфа и , графа , такие что и где и – корневые вершины графов и являются несвязными, если

.

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

Для выделения несвязных компонент графа используется следующая процедура:

1. Определяется множество типов записей первого уровня иерархии для i-й связной компоненты графа .

2. Определяется множество достижимости для каждого типа записи

.

3. Определяется множество попарных пересечений множеством достижимости .

4. Анализ элементов множества . Если множество попар­ных пересечений состоит из пустых подмножеств, то перейти к пункту 7, иначе – к пункту 5.

5. Выбирается минимальное подмножество множества , , элементы которого составляют множество вершин выделяемого подграфа графа .

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

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

Необходимость выделения слабосвязных компонент графологической структуры r-го узла, т. е. выделение подграфов логических структур локальных БД, определяется ограничениями на объем хранимой информации в узлах ВС, требованиями к опе­ративности копирования и восстановления БД и др.

Пусть граф , вершинами которого являются корневые вер­шины выделенных подграфов, а дугами – связи между ними, есть остовной граф или остов графа логической структуры r-гo узла. С целью определения возможности разрезания остов­ного графа определяется степень связности его вершин. В качестве оценки степени связности вершин остовного графа применяется суммарная частота использования дуг остовного графа запросами и корректировками пользователей.

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

На основе информации о типах записей и их взаимосвязи, определяющих выделенный подграф, проектируется логическая структура локальной БД. При этом учитываются особенности и ограничения конкретных система управления базами данных (СУБД ).

Для подтверждения эффективности предложенной методики проведено моделирование обработки запросов к БД при использовании существующей и предложенных структур БД, результаты которого представлены на рисунке [4,5]. Как видно из рисунка, общее время обработки запроса для предложенной структуры БД – tБД уменьшилось в среднем на 15 % .

Рисунок. Эффективность методики проектирования структур БД

Таким образом, предложенная методика позволяет проектировать эффективные структуры БД для использования в системах технической диагностики и уменьшать время обработки запросов по сравнению с традиционной [1,4].

Рецензенты:

Портнов Е.М., д.т.н., профессор кафедры «Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «МИЭТ», г.Москва.

Гагарина Л.Г., д.т.н., профессор, зав. кафедрой «Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «МИЭТ», г. Москва.