автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Разработка методов оценки эффективности доступа к данным в информационных системах

кандидата технических наук
Грановский, Юрий Исаакович
город
Куйбышев
год
1990
специальность ВАК РФ
05.25.05
Автореферат по документальной информации на тему «Разработка методов оценки эффективности доступа к данным в информационных системах»

Автореферат диссертации по теме "Разработка методов оценки эффективности доступа к данным в информационных системах"

Куйбышевский ордена Трудового Красного Знамени политехнический институт имени В. В. Куйбышева

На правах рукописи

ГРАНОВСКИЙ Юрий Исаакович

УДК G81.32.0C

разработка методов оценки эффективности доступа к данным в информационных системах

Специальность 05.25.05 — Информационные системы и процессы

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Э

КУЙБЫШЕВ 1000

/

Работа выполнена в Пензенском политехническом институте.

Научный руководитель — кандидат технических наук, доцент Леонид Константинович Коблов.

Официальные оппоненты — доктор технических наук, профессор Виталий Константинович Морозов; кандидат технических, паук, доцепг Владислав Васильевич Мотов.

1

Ведущее предприятие — Научно-исследовательский институт математических машин, г. Пенза.

Защита диссертации состоится 26 декабря 1990 года, в 10 часов, в аудитории 23 на заседании специализированного совета Д 063.10.01 Куйбышевского ордена Трудового Красного Знамени политехнического института имени В. В. Куйбышева по адресу: 443010, г. Куйбышев, ул. Га-лактионовская, 141.

С диссертацией можно ознакомиться в библиотеке Куйбышевского политехнического института, ул. Первомайская, 18.

Автореферат разослан • »____ 1990 г.

Ученый секретарь специализированного совета Д 063.16.01 к. т. н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

ктуальность темы. При проектировании информационных систем /ИС/ любой области их применения возникает задача выбора эффективного арианта фиглческой организации банков данных /В$/» обеспечиваю-его хранение, модификацию и поиск данных в соответствии к инфоло-ической моделью предметно»"! области /в дальнейшем:доступ к данным/, 'т успешного решения этой задачи в значительной степени зависит ыполнение требований, предъявляемых к информационным системам, так ак доля временных затрат на обмен с БнД составляет более 75Я от бщего времени выполнения ^вычислительных- работ при эксплуатации ИС. связи с этим еопросу проектирования доступа к дурным посвящается ольшое число исследований. В частности,работы"В.М. Савинкова, .В. Бойко, Б. С. Керебина и других учены}- создали ^направление по втоматизации проектирования физических моделей Е;-Д. Указанное на-равление является перспективным и сравнительно новым,, чем объяснятся появление в настоящее время разнообразных методов, методик и екомеадаций по эффективной организации хранения, модификации и лоска информации в БнД, на основе которых строятся модели представ-ения знаний в экспертных -системах проектирования 5Д. 'Автоматиза-ия проектирования'доступа тс данным" вызывает необходимость в повы-ении требований, предъявляемых к методам оценки его /доступа/ эф-ективности: они должны легко подвергаться автоматизации,' быть уни-ерсальными и давать точные результаты. В настоящее вреьет не сущес-вует такого метода, который отвечал бы указанным требованиям. Ана-итическое моделирование сопровождается принятием ряда существенно: допущений, что делает возможным его использование лишь для кс-яедования ограниченного "класса дгтустимых вариантов доступа. ibm-зционное моделирование, позволяющее детально учитывать физическую рганизацию данных, ачгорттм доступа к ним и статистические харак-зристики запросов к БнД в предметной области, является наиболее -п-шерсальным. Однако применение методов имитационного ыоделирова-1я для оценки эффективности доступа к данным в КС обнаруживает и с существенный недостаток: для каждого-варианта организалки досту-1 к данным необходимо по-существу строить нозуп модель, йленпо гот недостаток является основной пришлой крайне редкого приквяе- . га имитационного моделирования при проектировании БнД. .

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

Пель работы заключается в разработке метода и программного обеспечения имитационного моделирован:«', позволявших автоматизировать процесс получения оценки производительности доступа к данным в информационных системах.

В диссертационной работе для достижения поставленной цели сформулированы и решены следующие основные задачи: формальное определение системы доступа /СД/ как математического объекта исследования методом имитационного моделирования; разработка универсальной автоматизированной имитационной модели СД /УАИ-модели/ для автоматизации программирования имитационных моделей; разработка программных средств для реализации УАИ-модели; практическая реализация результа тов исследования1.

Диссертационная работа является частью межвузовской научно-технической программы "Повышение качества, надежности продукции, программного обеспечения ЭВМ и технических средств обучения" на 19861950гг., выполняемой на кафедре "Прикладная математика" Пензенского политехнического института по теме "Разработка сервисных программ к типовым СУЗД".

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

Научная новизна диссертационной работы состоит в разработке метода имитационного моделирования доступа к данным, основанного на автоматизации программирования, и обусловлена следующими результатами, полученными впервые лично автором:

I. Предложено и обосновано научно-техническое решение целесообразности построения системы автоматизации моделироЕ ония доступа к данным в информационных системах.

Разработан формальный аппарат описания доступа к данным, который-явился основой разработки и реализации УАИ-модели.

3. Предложена стохастическая модель-доступа к данным, зада-■ щая предметную область информационных систем в части организации

информационного обмена..

4. Разработана универсальная агрегатявная модель' доступа, задающая алгоритм'поиска и модификации информации в рамках любых систем доступа.

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

Практическая ценность и реализация работы. Разработан пакет поог раым имитационного моделирования систем доступа к данным СЩЩл-"

4

на основе использования которого ар^ором предлагаются:

- метод оценки эффективности доступа к данным в информационных системах; '

- методика определения размера буферного пула оперативной памяти систем доступа к данным, входящим в автоматизированные информационные системы /АИС/ реального времени;

- методика определения целесообразных сроков реорганизации данных, снижающая затраты машинного времени при эксплуатации информационных систем с независимыми областями переполнения на 7-16& по сравнению с использованием традиционных методйк.

ПП СВДВИМ-1 принят в программную часть межотраслевого фоцца алгоритмов и программ М05АП ВДЙИпроект Госстроя СССР, /г.Москва/, зарегистрирован в ГосФАПе /№ 50870000329/ и внедрен в ПО ЭРА /г.Пенза/. В соответствии с прилагаемым к диссертации актом о внедрении, применение ПП СВДЗИМ-1 в 3-5 раз сокращает трудоемкость оценки производительности доступа с требуемой точностью эксперимента. Внедрение пакета программ обеспечило возможность определения варианта организации доступа к данным, размещенным на ВЗУ, удовлетворяющего заданным временным ограничениям, еще на этапе проектирования.

Результаты диссертационной работы были использованы яри проведении хоздоговорных работ /КГР: 01.84.0034055;01.86.0099213; , 01.89.0016510/, работ по договорам о творческой? содружестве /421-Н, 106-88/ с 'промышленным предприятии, научной организацией и ВУЗом страны по проектированию отдельных подсистем АИС, а такзе з процессе эксплуатации подсистем АСУ ВУЗ з Пензенском политехническом институте при определении сроков реорганизации данных. Апробация' работы. Основные материалы дгссертационной работы были доложены и полумили положительную оценку на зональной научно-технической конференции "Математические методы в задачах управления" /Пенза,1981/, на межвузов^дих научно-методических семинарах "Применение ЭВМ в учебном процессе и научных исследованиях" /Иваново 1Э82,Пенза 1985/, на .'зональных научно-технических конференциях . - / "Математические и программные метода проектирования управлявши ' ■ ■ систем" /Пенза 1986,1990/, на зональной научно-технической конфе-рёнции "Практика применения баз данных для решения информационно-- ^' поисковых задач и задач управления" /Пенза 1990/, ка научно-технических конференциях профессорско-преподавательского состава ЯензенпкЬ- ■ го политехничесггого института /1981-1987гг./. •.. ; .. "

Публикации . Основные результаты диссертации отражены в 10 пвчеткгос заботах.

Структура и объем работы. Диссертация состоит из введения, пяти глав, основных результатов,'списка использованной литературы /103 наименования/ и трех приложений, включает 130 страниц основного текста, содержит 10 рисунков, 7 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность.разработки и исследования средств оценки производительности доступа к данным, размещенным на ВЗУ, определены цель и задачи диссертационной работы, приводится аннотация по главам, перечислены научные и.практические результаты, выносимые на защиту. • .

В первой главе определяется система доступа к данным /СД/ и параметры ее производительности. На основе анализа традиционных методов и моделей, позволяющих оценивать эффективность доступа к данным в информационных системах,.делается вывод о целесообразности, разработки нового метода, основанного на автоматизации программирования имитационных моделей СД. Определяется УАЙ-модель СД и описывается сущность предлагаемого метода оценки производительности СД. СД представляется динамической системой

5=<Е/Г.С.С0> ^

одесь £ - каркас системы: е* {<д., &>, <рв, л< С б . а где класс логической структуры СД;

- разбиение множества-записей СД в соответствии с типами отображаемых объектов предметной области;

& - характеристика логической организации данных; <£а,- класс физической структуры СД;

- разбиение множества записей СД, индуцируемое отношением эквивалентности ¿£оск'.Сх,у)е6&гек(^> -записи СД с одним Физическим адресом на ВЗУ;

Ж - характеристика физической организации данных; ЗЦв»)} я <а- множество запросов; & - цепь доступа по запросу % , элементы которой упорядочены отношением^: Ж

число обращений к ВЗУ для доступа к записи X ; & - характеристика запросов и алгоритма их обработки; Т - существование СД, ТС, N - момент обмена /0П«-*ВЗУ/;

с - булева функция,С:Х*Г-*{±гие,тЪ&е), X - поле СД;

. - элемент х существует /отсутствует/ в

момент '¿в 7" ;

' булева функция, О,:В хГ-^Ъгие.УЬ&е} , В _ множество записей с

запись X существует /отсутствует/ в ОП.

Условия системы доступа :

51 3 в а '•€,(£,£) •£ а "Г

где ££ - интерв*т времени обработки запроса

££ = Г/Сад * . ¿3}

Структурно СД состоит из буферного пула оперативной памяти /БОЛ/, системы управления данными /СУД/ и внешней памяти, на которой размещается БнД /см. рис. Т/. В БОП содержимся информация, -непосредственно доступная программе. Именно через БОП осуществляется взаимосвязь программ с ЕнД! Программным обеспечением СД яз-ляется СУД, представляющая собой комплекс программ, обеспечивающих' возможность размещения, выборки и модификации данных на ЗоУ.

В качестве параметров производительности СД предлагается время доступа и коэффициент полезного действия доступа к данным. Последний вводится автором впервые, он определяется произведением/Я^лт,, где/г^- доля шсла обращений к БОП от числа г^.ех обращений СД в процессе обработки запросов;/77д - доля числа требуемых по каждому запросу записей от числа всех записей, входящих в соответствующие запросам цепи доступа. Отличительным сво; ством указанного параметра является возможность априорного нахождения его максимального значения для информационно-поисковы,. задач конкретной предметной области, что позволяет оценивать анализируемый вариант организации доступа по отношению к оптимальному.

Существующие методы оценки предлагаемых параметров производительности СД делятся на две основные группы: методы измерения и методы моделирования. Среди методов измерения наибольшее распространение получило включение измерительных моделей в среду операционной система или в ядро системы управления базами данных /СУБД/, предназначенных для определения характеристик доступа к данным в процессе эксплуатации ЙС. Использование методез измерения предполагается на этапе сопроволщения ЙС, когда проведение изменений СД, как правите, требует значительных трудозатрат. Методы ;.'одзлироЕан;гг еестоят ;'3 аналитических и основанных на"имитационном стделирозачик. Традиционные аналитические методы оценки производительности Сд предусматривают нахождение временных характеристик доступа к дажыг; по числу обращений к ВЗУ. Под обращением к ЗИУ понимается процесс , з&зэр-

ВНЕШНЯЯ ПАМЯТЬ

|БДОК 1-1

л

ЗАПИСЬ

Рисунок I.

таящийся установкой механизма доступа на начало требуемого блока, размещаемого на некотором участке внешней памяти.

Каздое ВЗУ характеризуется своим временем доступа к блоку при обращении к нему по адресу /произвольное обращение/ при обращении к блоку, непосредственно размещаемому за текущим /последовательное обращена/. Для основных методов доступа известны зависи- ' мости среднего числа последовательных ж произвольных обращений при поиске информации от параметров физической организации данных. Однако указанные зависимости основаны на допущении равномерности распределения запросов к тем или иным данным БнД/

В работах, представляющих процесс информационного доступа в виде марковских и полумзрковских'моделей, время доступа к запрашиваемым данным определяется как • •

гдеуГ^ - предельная вероятность того, что механизм доступа нахо--дится на I - м участке внешней памяти;р¡^ - вероятность перехода, а- вг перехода с и -го на -й у^ясток внешней памяти. В полумарковских моделях с каздым переходом связывают ряд распределения вероятностей.

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

Автором проводится анализ существующих методов и средств построения имитационных моделей СД, на основе которого определяется необходимость в разработке нового гетода лмитационпого моделирования СД, так как применение существугачих либо в недостаточной сте- ' пени учитывает алгоритм доступа к даншм, либо требует трудозатрат, соизмеримых с трудозатратами на построение и анализ реальных СД.

В основу предлагаемого автором метода положен принцип агрегз-.ч. тивности построения сложных систем, определяемый Н.П. Бусленко,-.* ..;*•" Система доступа рассматривается как словяая система, состоящая /,з - ■ совокупности взаимосвязанных агрегатов, кат^ый из которых описывает \

д : . •• •

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

Дяя реализации предлагаемого метода оценки производительности СД автором разработан пакет программ имитационного моделирования систем доступа к дачным ПП СВДВЙМ-1 /Сйстемы Доступа В Имитационных Моделях/. Входные данные задаются в параметрическом в де. На основе значений входных параметров автоматически строится • имитационная модель, при выполнении которой определяются статистические характеристики времени доступа к данным в рамках моделируемой СД.

Зо второй главе описывается информацизнйо-пйисковуя стохастическая модель систем доступа, статкстическй определяющая дачные, , хранящиеся на ЗЗУ, и запросы к ним в конкретной'предметной области. Дается определение канонических запросов, приводится правило .преобразования запросов общего вэда в канонические. Для канонических запросов автором обосновывается возможность представления информационно-поисковой стохастической модели /ИПС-модели/ множеством одномерных дискретных случайных величин,.

В имеющейся литературе, по проектированию доступа к данным в ряде случаев используется различная терминология. Автор продергивается следующей :

Информационный объект - вдентифицируемый объект предметной области, о котором хранятся описательные данные. Объекты описывают ся с помощью- заданных атрибутов, которым присваиваются конкретные значения: символы, числа, кода. Атрибут определяется как функция,'

отображающая множество объектов во множество значений

£

гДе ж - множество объектов предметной области, множество

значений, принимаемых атрибутом 0£ . Данные об объектах хранятся . на ЗЗУ в виде записей, определяемых как

где 'f - функция, ставящая в соответствие объекту- предметной' области запись об объекте. Таким образом,'*/ определяет содержимое БнД.

В диссертационной работе предлагается заменить ¡ункцию на Функцию вида . /■ » ->

где W<L> J - нумерация, заданная на множест-

ве значений L -го атрибута; ¿¿¿J - вероятность тоге, что

значение величины , соответствующее номеру конкретного значе-

ния ¿ -го атрибута, меньше заданного числа .''Поскольку нумерация дискретна и измерила относительно указанной вероятности, величину ^Jможно рассматривать как дискретную случайную велшпку с функцией распределения

s:^ <-с с с

Тогда функция (i) является функцией распределения ft. -мерной дискретной случайной величины, а запись об объекте может быть предстзз-лена точкой п. -мевного евклццова пространства с координатами

На этапе концептуальк.го проектирования БнД определяются требуете приложения /справки, отчеты, таблицы и т.д./, получаемые при выполнении прикладных программ, взаимодействующих с ЕнД. С "~:ат-дым приложением связывается определенный формат' запросов к данным, специфицирующих значения, по которым осуществляется поиск информации.

Условие атрибута - некоторая высказывателькая функция , выделяющая из множества значений атрибута подмножество

= V/(LK , L -^Mcl

где Ng - множество номеров атрибу. эв, по значениям которых осуществляется поиск информации в рамках запроса & /поисковых атрибутов/. Элементы множества

ж-ываются атомными условиями. Условие запроса определяется как

где В - множество fcex записей БнД, «В^*- иожество записей» удовлетворяюще запросу .

В работе аналогично определению вероятностей встречаемости значений ¿ -го атрибута в записях БнД задаются вероятности ветре-, чаемости значений С -го атрибута в качестве атожых условий, на основании которых вводятся случайные величины L s i, Н , '( -число ключевых атрибутов, описывающих объекты рассматркз&змой предметной области. Значение величины , та*. же на : , coll - - . ■ ' • . :

ответствует номеру конкретного значения' ¿.-го атрибута. Условие запроса геометрически представляется точкой - к -мерного евклидова пространства с координатами^, i-i,K , а всевозможные условия запросов определяются К -мерной дискретной случайной величины с функцией распределения, имеющей вид :

Ffri Р&(<)<*< »< ХК} С2)

' Сложность функций (I) и (2) практически не дает возможность юс использования при моделировании доступа к данным. В работе обосновывается допустимость рассмотрения только одномерных функций распределения. При этом автор вводит следующие определения:

- информационно-поисковое состояние системы доступа;

- каноничность запросов.

Информащ. -нно-поисковое состояние определяется функциями ^, i- Çk , i- номер ключевого атрибута, J-*■ Б Значение/¿(^задает множество'записей БнД, ¿-й атрибут в которых принимает значение ifr .

Большинство предметных областей содержат объекты разных ти" пов, между которыми существуют взаимосвязи вида i: M и N:tA Каждый тип объектов задается множеством атрибутов, описывающих объекты этого типа, тогда множество всех атрибутов ^ /в соответствии с информационно-поисковым состоянием рассматриваются только ключезые атрибуты/ разбивается на подмножества, к&чщое из которых определяет конкретный тип, образуя некоторую подсистему¿'с 2А . На множестве А вводится такая нумерация^ , при которой элементы ¿Ç, можно было бы кодировать интервалами. Этим самым наУл накладывается условие, требующее непрерывность нумераций элементов¿£ . Такое условие выполнимо, так как предполагается, что : ¿0« , где m - число типов. Таким образом, тип

объектов идентифицируется значением j ■ , определяемым как :

(At)} > где - множество атрибутов, описывающих объекты, данного типа.

' Каноничность запросов определяется требованием независимости условий атрибутов, описывающих объекты одного типа. Правило преобразования запросов к каноническому виду, приводимое автором в работе, заключается в том, что все условия атрибутов, являющиеся зависимыми для объектов одного типа, заменяются одним условием атрибута с наибольшей областью значений. Это правило обосновывается следующим образом :

бФ = [) В(е)й => таг {| ;

где обозначением ( | определяется число элементов множества; &«Ч) , - гдютества записей, удовлетворяющих, соответственно,

атомному условию и условию запроса.

Формат запроса ^ определяется множеством номеров поисковых атрибутов Л/^I . Для идентификации форматов запросов вводите.-;^ку-мерация на множестве, элементами которого являются.

3 работе показано, что введенные определения позволяют оперировать одноуерными функциями распределения случайных величин, статистически задающих: L = ^,K - значения С -го атрибута, встречающиеся в записях Бнд.эвф, и^, [ 1, ~ числа объектов типа, связанных с одним объектом (. -го типа,

= значения ¿_-го атрибута, встречающиеся з качестве атомных условий~ числа атомных условий, входящих з условие ¿ -го атрибута, 5 ~ номера форматов запросов. Указанные случайные величины образуют информационно-поисковую стохастическую модель СД /ИПС-:'эдель/, которая задает рабочую нагрузку при проведении имитационного моделирования для оценки производительности доступа к данным.

В третьей глазе определяется модель доступа к данным и приводится формальное описание основных методов доступа.

Существующие методы доступа к данным, как правило, основываются на построении деревьев поиска, в которых вершина отождествляется с блоком ВЗУ, а дуга, соединяющая две вершины, определяет направление и порядок поиска требуемых данных, деревья поиска полностью определяют методы доступа, однако для их задания требуется построение информационных массивов. Автором разработана новая модель доступа к БнД, исключающая необходимость организации информационных массивов и позволяющая автоматизировать процесс построения имитационных моделей СД. Для описания методов доступа предлагается использовать аппарат агрегатов, при этом агрегаты общего вида, определяемые в теории сложных систем, сводятся к агрегатам, инвариантным относительно моментов времени. СД рассматривается как сложная система, состоящая из взаимосвязанной совокупности агрегатов, каждый из которых описывает отдельный метод доступа. Агрегат представляется следующим образом (т=(£.30 А, \ где 5 - множество состояний агпегата :

тя

Состояние агрегата определяет запись об объекте, для доступа к которой требуется ¡^ последовательных и £ произвольных обращений к ВЗУ, а также и обращений к БОП ; значение поискового атрибута в рассматри аемой записи генерируется с помощью функции распределения случайной величии-: , где с - номер поискового атрибута; множество начальных состояний агрегата, определяющих записи, с которых начинается поиск записей, определяемых множеством ; - множество конечных состояний агрегата; Р-отображение, задающее преобразование состояний с учетом входного сигнала ЗСвХ : Г -*•£ ;

множество входных сигналов, элементами которого являются векторы с координатами, определяющими: длины залрисей об объектах и блоков ВЗУ, размеры БОП и областей поиска на ВЗУ, диапазон номеров значений поискового атрибута, а также атомное условие запроса; У - множество выходных сигналов, элементами которого являются векторы с координатами, определяющими: суммарные числа последовательных и произвольных обращений к ВЗУ, а также число записей со значением поискового атрибута, удовлетворяющим атомному условию запроса; Н - оператор выхода, формирующий выходной сигнал на основании конечного состояния агрегата: И : 3 У

■ Отображение Р* определяет метод доступа как автономную динамическую систему. Автономность системы определяется независимостью входного сигнала от времени. Структура К' следующая: определено конечное множество правил преобразования -[с1т ** Ы.Гг : 3

/7? £ [{, р] и на множестве определен

упорядоченный набор булевых функции/у, , гд

Выбор конкретного правила преобразования определяется функцией /V} , значение которой соответствует номеру требуемого правила:

Таким образом, переходы из одного состояния в другое определяются как х) (£) ' Применение конкретного правила

определяет переход из одного состояния агрегата в другое. Переход агрегата е состояние В& & соответствует выполнению атомного условия запроса. Конечное состояние Лвляется поглощающим :

^кон • У£>кои ^ и ПРИ переходе агрегата в опе-

ратор выхода формирует выходной сигнал.

В диссертационной работе принята классификация методов доступа на элементарные и составные. Для элементарных выполняется условие

ё&В , все остальные методы доступа яв-

лягатся составными. Здесь $ запись, а и - числа, соответственно, произвольных и последовательных обращений к § . Автор утверждает, что всего существует 14 разновидностей элементарных методов доступа, и для каждой из них приводится описание агрегата. На примере описания индексно-последовательного метода доступа показывается, что любой составной метод доступа может быть предстаьтен совокупностью элементарных введением в состояние агрегата дополнительных координат , и определением соответствующих правил преобразования из одного состояние з другое. Здесь Ш* - верхняя, а - нижняя граница номеров эначени:": поискового атрибута, допустимых в записи об объекте, интерпретируемой текущим состоянием агрегата, то есть случайная величина принимает значения з интервале

Взаимосвязь агрегатов при описании доступа к записям по запросу, включающему несколько услозий атрибутов, определяется отображением , структура которого задается конечным множеством опера-.торов сопряжения> ГДЭ :У-5*-Х , /ь з и упорядочен-

ным набором булевых функций -С^ ^г ^ 3

Оператор сопряжения определяет очередной агрегат и формирует для него входной сигнал на основании выходного сигнала текущего агрегата. Таким образом, поиск требуемых по запросу данных представляется цепочкой последовательно активизируемых агрегатов, 1 выбор конкретного оператора сопряжения определяется функцией X » имеющей следующий вид:. , \ Л 7?

лип^Сх, и)=1},

где Я и входной и еыходной сигналы текущего агрегата.

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

Предлагаемая модель доступа является универсальной автоматизированной имитационной моделью СД, так как она позволяет автоматизировать процесс построения имитационных моделей, состоящих из взаимосвязанных агрегатов, для любых систем доступа. В четвертой главе описывается разработанный автором пакет программ имитационного моделирования систем доступ . к данным ПП СЦЦЗИМ-1, представляющий собой программные средства реализации моделей, определенных во второй и третьей главах диссертации, и предназначенный

для автоматизированной оценки времени доступа к записям об объектах, хранящимся на ВЗУ.

Каждому агрегату, описывающему доступ к данным в рамках конкретного метода доступа, соответствует программный блок имитации - ПБИ, который имеет один вход и чцин выход. Вход в ПБИ определяется входным сигналом, а выход - выходным сигналом, являющимися элементами, соответственно, множеств X. , ТГ . Алгоритм функционирования ПБИ, задается отображением Р . Построенная имитационная модель СД состоит из одного или нескольких ПБИ и управляющего модуля, в качестве которого используется программный блок взаимосвязи - ПБЗ, реализующий отображение & . В модели процесс имитации обработки запроса осуществляется следующим образом:

I. Генерируется номер формата запроса, по котопому определяются номера поисковых атрибутов. Для калдого поискового атрибута генерируется число атомны условий. Активизируются ПБИ, определяющие доступ к данным по значениям поисковых атрибутов.

'¿. Выполняется ПБЗ : проверяется условие завершения имитации обработки запроса /число вызовов активизируемых ПБИ должно равняться суммарному числу атомных условий для всех поисковых атрибутов/, при выполнен™ которого'определяется время доступа к данным на основе суммы значений выходных параметров ПБИ, соответствующих числам последовательных и произвольных обращений к ВЗУ, в противном случае, определяется очередной ПБИ, которому передается управление со сформированными входными значениями.

3. Выполняется ПБИ:'генерируется атомное условие и в соответствии с отображением А* осуществляются переходы из одного состояния агрегата в другое, до тех пор, пока не будет достигнуто конечное состояние, интерпретирующее выполнение атомного условия; формируется вектор выходных параметров и управлетче передается в ГШВ,

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

Пользовательское описание доступа'к данным, называемое ГТМ-мо-делью, включает в себя ввод: числа обрабатываемых запросов, интервалов частотного распределения значений времени доступа к данным, ко- -дов ПБИ и ПЕВ, пространственно-временных характеристик ВЗУ, пера-

метров физической организации данных, размещаемых на ВЗУ, законов распределения случайных величин. Последние задаются интервалами равномерности с указанием вероятности попадания в них конкретной случайной величины. С помощью макрогенератора ГГМ-мо-дель транслируется, образуя при этом имитационную модель ОД, готовую к выполнении. Г процессе трансляции ГГМ-модели осуществляется синтаксическая и-семантическая проверка вводимых параметров. В пятой главе определяется область применения ПП СЗДВИМ-1 и предлагаются методики использования пакета программ при проектировании и эксплуатации ИС.' "

Основным назначением ПП СВДВИМ-1 является проведение быстрой и точной оценки времени доступа к Дсишым. Наибольшая эффективность от использоьания ПП СВДВИМ-1 достигается при проектировании обмена с большими базами данных, характеризующимися жесткими временными требованиями. В качестве примера такой ИС в работе рассматривается авиационный тренажерно-моделиругащий комплекс /ТМК/, использующий для имитации визуальной обстановки полета синтезирующую систему визуализации /ССВ/. Вся необходимая для синтеза изображений информация размещается во внешней памяти, образуя базу данных /БД/, запись которой содержит данные о потенциально водимых пилотом объектах. В зависимости от имитируемых координат объектов, /.спользуемкх для управления самолетом, формируется запрос к БД. Информация, удовлетворяющая услозию запроса, поступает в БОП, где преобразуется в видеоизображения. Если время доступа к ДЦ превышает время проебра-зования информации, то для восполнения данных с привязкой к жестко' синхронизированной телевизионной системе на монитор выводятся фиксированные заставки,'снижающие точность синтезируемого изображения. Автор предлагает методику определения числа буферов БОП с учетом допустимой вероятности появления телевизионных заставок, основанную на получении временной границы доступа к данным, превышение которой вызывает необходимость в телевизионной зяставке. Приводимая методика при простоте использования обеспечивает высокую точность и может быть применена не только для рассматриваемого ТМК, но и для любой информационной системы, в которой время доступа к БД является критичным. На конкретном■ примере в работе показано, иго ис-прльзование ПП СВДВИМ-1 для реализации указанной методики позволяет уменьшить трудозатраты в 3.-5 раз по сравнению с существующими программными средствами имитационного моделирования.

В процессе эксплуатации СД время доступа « данным может быть значительно'увеличено' за счет внесения новых данных в область пере-

17

полнения, где доступ осуществляется по цеаачке связанных записей. В некоторых случаях без реорганизации данных /переписи данных из области перепо 'нения в основную область/ невозможно д.-.льнейшее функционирование ИС. 3 работе на основе разработанного метода оценки производительности ОД автором предлагается методика определения целесообразных сроков реорганизации данных. Ее сущность заключается в следующем: строятся графики зависимостей времени доступа от периода функционирования ИС при отстутствии реорганизации

, при постоянной реорганизации к при проведении реор-

ганизаций в те моменты, когда время доступа превышает допустимое значение ; , ;ля каждого интервала , £¿3» гДе ^ " момент

превышения допустимого значения времени доступа, находятся фиксированные интервалы реорганизации

где-время на реорганизацию в период^ . Предлагаемая методика иллюстрируется примером, показывающим, ее эффективность.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

В работе получены следующие основные результаты: X. Доступ к данным в ИС представляется системой доступа, чю позволило •эффективно применить основные положения системного подхода для исследования физических свойств БцЦ методом имитационного моделрфо-вания.

2. В терминах теоретико-множественных операций СД определяется как динамическая система, учитывающая логическую и физическую организации данных, запросы к требуемой информации и алгоритм их обрг^отки, на основе которой /системы/ предлагается и реализуется УАИ-модель, позволяющая автоматизировать программирование имитационных моделей доступа к данным.

3. Предложен новый показатель производительности СД - коэффициент полезного действия ВД, обеспечивающий возможность априорного нахождения "его максимального значения для информационно-поисковых задач конкретной предметной области. Что позволяет оценивать анализируемый вариант СД по отношению к оптимально:,"/.

" 16

4. В качестве внешнего представления УАИ-модели предложена ЙПС-модель, задающая предметную область в части организации информационного обмена. Реализация ШС-модели позволяет характеристики статистических свойств данных и запросов к ним представлять в сжатом виде. ИПС-модель определяет рабочую нагрузку имитационной модели.

5. 3 качестве внутреннего представления УАИ-модели разработана Д-модель, задающая алгоритм доступа к данным в соответствии с агре-гатквно-модульным принципом. Реализация Д-модели дает технологическую гибкость построения имитационных моделей СД.

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

7. Разработан пакет программ имитационного моделирования систем .доступа к данным - ГШ СДЦВШ-I /СИстемы Доступа В Имитационных Мо-

• делях/, который включен в межотраслевой фонд алгоритмов и программ и внедрен на предприятии министерства авиационной промышленности. Его использование позволяет реализовать УАИ-модель, сокращая при этом трудозатраты оценки производительности доступа к данным в 3-5 раз по сравнению с применением существующих средств.

8. На основе использования Ш СЩВИМ-I разработана методика определения минимального числа буферов ввода-вывода, обеспечивающего нормальное функционирование информационных систем реального времени, в которых доступ к данным совмещается с их обработкой. Методику отличают от известных простота использования и высокая точность получаемых результатов.

9. На основе предлагаемого метода оценки производительности доступа к данным разработана методика определения целесообразных сроков реорганизации данных, позволяющая снизить затраты машинного времени при эксплуатации Ш с независимыми областями переполнения на 7-1654 по сравнению с применением традиционных методик

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

I. Сивохин A.B., Сорокин В.Н., Грановский ¡и.И. К вопросу сокращения,времени обработки файлов с последовательной организацией // Вопросы радиоэлектроники. - вып. 4, 1979. • с. 96-107. а. Сорокин В.Н.,Рябов B.C.»Мамаев В.А.»Грановский й.И. Влияние коэффициента блокирования на время обработки индексно-последователь-ного файла //Вопросы радиоэлектроники. - вып. 2, 1982.-с.59-65.

3. Грановский Ю.И. Применение имитационного моделирования при определении оптимальных сроков реорганизации индексно-последователь-ных файлов //Оптимальные методы вычислений и их примпение.-Межвуз. сб.- Пенза: ПЛИ.-вып. 7, 1985.-с.84-88.

4. Коблов Л.К., Грановский Ю.И. Информационно-поисковая стохастическая модель базы данных //Тезисы к зональной конференции "Математические и программные методы проектирования управляющих систем"*' Пенза: ПДНТП, 1986.-е. 57.

5. Грановский Ю.И. Структурная организация модели физической базы данных. - Пенза, 1986. - 7с. - рукопись представлена Пенз.ПИ. Деп. в ВИНИТИ Г мая 1986, № 3538-386.

6. Грановский Ю.И. Вероятностная модель обработки запросов к базе данных. - Пенза, 1986. - 12с. - ^копись представлена ПензПИ. Деп. в ВИНИТИ 15 мая 1986, № 3539-В66.-

7. Коблов Л.К., Грановский Ю.И. Анализ производительности обмена

с базой данных методом имитационного моделирования //Вопросы радиоэлектроники. - вып. 8, 1986. - с. 68-72.

8. Грановский Ю.И. Пакет программ имитационного моделирования систем доступа к данным ПП СДЦВИМ-1. - М: ЦНИИпроект, 1987. - 57с.'-Зарегистрирован в ГосФАПе 1987,№50870000329.

9. Грановский Ю.И. Универсальная автоматизированная имитационная модель доступа к данным в АИС // Тезисы к зональной конференции "Математические и программные методы проектирования управляющих и информационных систем". - Пенза: ЦДНТП, I990. - с. 53-55.

10. Грановский Ю.И. Пакет программ имитационного моделирования доступа к данным СДЦВЖ-1 и его применение для оценки производительности баз данных // Тезисы к зональной конференции "Практика применения баз данных для решения информационно-поисковых задач •и задач управления". - Пенза: ЦЦНГП, 1990. - с.34-35.