Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

EFFECTIVE TECHNIQUE FOR DESIGNING LOGICAL DATABASE STRUCTURES OF TECHNICAL DIAGNOSTICS SYSTEMS

Bain A.M. 1 Kaung San 1
1 National Research University of Electronic Technology
Effective systems of technical diagnostics, performance information exchanges largely determines the optimal construction of their constituent structures of local databases. This paper proposes a formal approach, which al-lows you to design effective database structure for use in technical diagnostics. Proposed article approach is based on solving the problem of normalization of the logical structure of the graph, each node of a computer system; determination disconnected and weakly connected components (subgraphs) of the graph of the logical structure of each node, the design of local databases, supported by specific database management system. The simulation showed that the overall query processing time for the proposed structure of the database has decreased on average by 15 % compared with the traditional approach to their design.
performance
mathematical model
design
database management system
technical diagnostics

Эффективность обработки информации при проведении технической диагностики сложных объектов вычислительных систем (ВС) во многом определяется структурой БД системы технической диагностики [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].

Рецензенты:

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

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