Эффективность обработки информации при проведении технической диагностики сложных объектов вычислительных систем (ВС) во многом определяется структурой БД системы технической диагностики [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].
Рецензенты:
Портнов Е.М., д.т.н., профессор кафедры «Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «МИЭТ», г.Москва.
Гагарина Л.Г., д.т.н., профессор, зав. кафедрой «Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «МИЭТ», г. Москва.
Библиографическая ссылка
Баин А.М., Каунг Сан МЕТОДИКА ПРОЕКТИРОВАНИЯ ЭФФЕКТИВНЫХ ЛОГИЧЕСКИХ СТРУКТУР БАЗ ДАННЫХ СИСТЕМ ТЕХНИЧЕСКОЙ ДИАГНОСТИКИ // Современные проблемы науки и образования. – 2014. – № 3. ;URL: https://science-education.ru/ru/article/view?id=12764 (дата обращения: 28.03.2024).