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



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

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

мухоб Сергей Владимирович

УДК 681.3

проблемы)- ориентированные модели динауических баз данных и их программная реализация в системах обработку! экспериментальной ижгормагоя

05.13.15 - применение вычислительной техники, математического моделирования и математических штодов в научных исследованиях

АВТОРЕФЕРАТ диссертации ка соксканиэ ученой степэни кандидата тэхничэских наук

1&нск - 1992

Работа выполнена в ордена Трудового Красного Знамени Институте технической кибернетики АН Беларуси.

Научный руководитель:

кандидат технических наук, старший научный сотрудник Иатюшков ЛИ.

Официальные оппоненты: доктор технических наук,

профессор Ярмош Н. А.

кандидат физикс-матеыати-ческих наук,

старший научный сотрудник Столяров Г. И.

Защита состоится "/О^йка^р^ 1992 г. в

Ведущая организация: Белорусская государственная

политехническая ъчадемия

часов

на заседании специализированного совета Д 006.24.01 в Институте технической кибернетики АН Беларуси (220012, Ыинск, ул. Сурганова, 6).

С диссертацией можно ознакомиться в библиотеке Института технической кибернетики АН Беларуси.

■■¿У ■■ н^Гр.?

Автореферат разослан _" п л»г'Т 1992 г

Учёный секретарь специализированного совета, ^ доктор технических наук

/Алексеев Г. И. /

■>'0 V .ч

седая хдрАтажгеьлА ршяа

те?ц. Пря!Л2.! сл-здстьнзк каучпо-технического прогресса является узелкчзни? обг^-оз и дина^сх:: сСраОотк:; данных при ресзнпн эе.'.ач азтсь'Д'Гпоацза схо;-г:шх -зкспгр5о:затоЕ, прсзгсирсгакга и упразлзнил производством. Процзсс развптгл ::к*ср>.'а!л:?нкь^: т^хколэгй! полагал, тао гсегда- суцзствупт систем обработки дая:щя (СОЛ) длл которк:: крктзг-с-гы грэ^нккз парадатрн. Ссо могут быть прсмьсдлзянкэ СОД, снстэьа обработал зкспэриузнтазпьных дайны* ГСОЭ"), автоштизированнш систэум научных исследования (/¡СЕЯ), система азтсматчз5-!рс2ант;ого про-е!-"кроз.^;:я (САПР), азтсматкзкрованкь.'э систеш нау-.'нэ-те-гни-чэс:-:ой жфзрмздии (АСХТИ), аксперткыз сястэаы (50) и т.д. Актуальна раэрз5огнз инетрумэнтвщ юзе средств сбзспг-гания эФ1вк-. тизпой поддер.»:и 6о.еь:е:< динамичзсгасс баз данякг (Ба), связанных с автощткзацизй обработки рзчультгтсз наблсдзшй при проведении крупномгоптабкых эиспзркмзЕтэз, прохоядокиэ которюс гзракт-зрлзуэтся Солъпнм потокои данкьа.

СрОЫЬШГЗННЬ'Э 2 эре; Ж скстэм упрЗЗЛЭИИЯ ба ЗИЛ! Д2ЯК1-С-: (СУБД), сбеспэчзйзя езкя шшту.в:ро2зкхя дзяньза (ЯЗД> загско-го уровня з ра'-сл:; реляционной, перзрхкчэсгай или езтэво? га-д-эл'Зй, кс- ззагда удовлэтзоряго погьаогзтэля по зремзккъм параметрам. Одн::м из рзсэнкЛ данной проблемы является каподьзега-ниэ сп-зцпгл^вирсааннюс об1е:лткй-ори~кг::рсга-1Ных баз данных (СОБД). При зтем пгрспэтивко испольгованг.э :.:зтодоз рандомизация а качзстзг ерздегна кавитация при работе с СолызпдI дияа-1г.:че?у-цй: СОЕД. 3 ггом случаэ физкчзс:-:оэ ьнсто ргеполояэвия данных опр-здзллетел с помолчи некоторой Функции от самих данных, что позволяет перейти к кокцзпцга логического кляча, зы-полклггзго фун:сЦ/25 физического указатзлл, я сбзспечнть мо'шгь-кость данных вплоть до функционирования в различных системных средах. ¡йбяанссть преград,кого продукта и данных, яздлггэяся слэдс-твизм использования аппаратных модэлей доступа :: данным, значила в силу узэ лг-^зннн уровня интеграции СОД на еззэ раз-дшис аппаратных сред или спзрацнонних систем (ОС).

Е0Л5И9 гяачеяпэ при разработке специаллгирсзакнгд БД кыэзт простота реализации внутрек:-:;::: структур хранения данных. Такиэ систем позволяют аольвогагел» при лалнчия узких мэст"

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

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

Тема диссертационной работы связана с плазом научно-исследовательских работ, проводимых в рамках комплексных программ фундаментальных исследований Республики Беларусь "Информатика" и "Электроника-2".

Цель м задачи райоты. Целью диссертационной работы является разработка инструментальных средств, обеспечивающих эффективный доступ к данным в СОД (СОЭД, АСЖ, САПР, АСКГИ н др.) с большими динамическими ООЕД с учётом особенностей функционирования, и их реализация е виде программного Обеспечения (Ю). Для достижения поставленной цели должны быть решены следующие задачи:

1. Ешолнеко исследование эффективности применения промышленных версий СУБД в информационно-емких динамических СОД с учётом специфики проведения эксперимента в системах с большим потоком данных.

2. Построена математическая модель специализированной ООБД, предназначенной для работы в условиях эксперимента на-информационно-ёмких динамических системах.

3. Разработаны алгоритмы выполнения операторов ЯЫД в разках предложенной модели с использованием специального метода доступа, обеспечивающего эффективность за счёт учёта специфики работы в информационно-ёмких динамических системах.

4. Сделана оценка временных затрат при выполнении операторов ЯМД и разработана методика выбора оптимального подмножества операторов ЯМД с учётом специфики БД.

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

6. Выполнено исследование БД, . разработанной согласно предложенной модели, в плане изучения её качественных характе-

- э -

рпстзк ¿обеспечение мобильности, способность к язрзздазяет Зунг-люнальных возмо.таостей, использование а качества угла распределенной БД и т.д.).

Иэтоды jjcследов?.^. Для ресения поставленной задачи использовались методы теории вероятностей, теории массового обслуживания/ теории информационных систем и баз данных, а такта методы моделирования сложных систем.

Для подтверждения достоверности результатов исследования использовало мзтемзтическсэ и юятациоянсе модедгровакиг процессов обработки данных на ГЕБЕ

Кз. sraptry пгзссатсз:

1. Математическая модель специализированной ООБД, ориентированная яз использование в информзциокно-ёмких динамических СОД (СОЭД, АСКИ, САПР, АСНГИ и др.) с простым идентифицированием oCseraas

2. Метод двухуровневого хеиировгния с использованием открытых Ст. е. размещаемых внутри хез-таЗлицы) ограниченных цепочек, используемый в предложенной модели ООБД на нижнем уровне доступа к данным.

3. ¿йтоды обеспечения мобильности данных и ПО для БД, разработанной в рамках предложенной модели.

-L ¡Методы обеспечения сетевой лоддерхки при реаллзация "распределённой БД в рамках предложенной модели с учетом специфики СОЭД.

Наущая шлизна получению рдзулататон:

1. Разработана математическая модель ООБД, ойеспечиваютя Солее з( {с-ктивнув реализацию доступа к данным по. сравнении с промышленными версиями СУБД (ForcBass, семейство dBase, Oracle и др.) в информационно-.эмхих динамических СОД с простым идентифицированием объекта без применения дополнительных указатель ньк структур при поиске в БД.

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

3. Разработан метод двухуровневого хеетроза^и с ксполь-

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

4. На базе предложенной СОЕД разработана модель сетевой СОЭД, ориентированная на использование простых механизмов передачи информации и малую ОП, которая позволяет реализовать сетевую СОЭД на ПЗШ а минимальной конфигурации в отличии от прокат пенных версий вышэукаэаных СУБД.

Практическая ашюаюсгь днесерх'ацжмгноЯ роСогаг

1. На основе предложенного двухуровневого хеширования с использованием открытых ограниченных цепочек могут Сыть реализованы эффективные механизмы доступа з больших ддаамических системах с простым идентифицированием обьекта и разработана математическая модель ООБД, предназначенная для работ*: в таких системах. Результаты исследований могут испо.тьгаться при разработке новых оСтэ кт но- орие нт кров анных СУБД.

2. На базе разработанной пат е мат кче с ко й модели ООБД реализованы СОЭД, предназначенные для сбора данных в информационно-емких динамических системах на аппаратуре с ограниченной оперативной к внешней пам.?гью, а также экспериментальная распределенная БД, ориентированная на работу в системах с многоточечным сбором данных при проведении эксперимента.

3. Создание программные средства поддержки и сопровождения специализированной ООБД могут быть использованы как инструментальное средство при разработке и тиражировании АСНИ в информационно-емких динамических системах.

Реализация результатов работы. Результаты приведённых исследований использовались при выполнении НИР "Создать исследовательскую САПР СБИС и устройств на их основе. Раздал 02.02.10. Разработать проектные решения по программному обеспечению для системы управления базами данных САПР. Разработка банка данных на современных СУБД (часть 2)", а также в рамках договора о научно-техническом содружестве с Госкомикту-ристом СССР "Разработка и сопровождение АСУ отделением Госко-минтуриста СССР в г. Брест (АСУ "Брест")".

— ^ -

Рэзра&гсзнаьз при рс2оте над диссертации .'эдэхи, агто-р;:г! : и програ.з.ккэ сргдстга каг^ги г.ри:.!э:-:ен;:з в Брестском Дэ-ЕЦ зтапсртно-импорхных пгрезогс:-?, а яг:«» гкедрзны з уч:-бкыД прайсе Брестского политехнического :п-:отиту7а.

Практическая цэкнссть работы, вююлнэнкой по т-здиосэр-т-,цгл!, пог?2ор:*дготса соота-зтстгукзгг-а актам! о гкодрении.

Лпроб^л работ Результаты диссертЕлиояной работы док-лэдгаались и обсу:«далпсь кз Ее-; с окопом нау^'о-техгппгском се-етггрэ "САП? 2 кзгинсстроенгй" 'г. У.-зянорс;-:, ISiG г.), I со-пвпажп.'-сег.сгкарз "Про:.:ызлгнньэ САП? 2 сб.:?.;г и элэктрокгзси и вычисдителансЯ техжкГ (г. Бр-ст, 1520 г.), II ссггианги-се-микарэ "фоуьплеиныэ С/Л? з области олэгегрсшки и вычислительной техники" (г. Брест, 1331 г.).

ПуСл^ги<;.z*. По теьэ диссертации опубппсоаако 8 печатных работ.

Струхгург и с<5г5н рсГоты. Диссертационная работа состси? из гвэдекпп, пяти глаз и зат-лсчения, изложенных на 102 страницах, сп;:ока литературы из 154 нз:о.;е нов гний к трэх приложений. Основной текст содер:«:т 7 рисунков, 12 тзблзд.

Я7ЛТКС2 СЩЕ?/:ЛШ& РЛШТУ

Во взэлюся обоснозьззэгся актуальность те;« диссертации, е^срмулнроягкы пель работы и -задачи исследования, пригэдаяу оснсань'э регу.-ьтзты положения, аыкоспмые ка оазгту, указано э 49м заключается научная нсзкона затронуть-: вопроооз л практическая ценность полученных рггультатоз.

Яер ал г лаг п. псс2~сгна обзору современного состояния зоп-рссз, зыбору и с'ссжэаннэ цели и залзч работы. Нл класс? задач, с^язаньих с oCvai:ткой Сольшх ~п:глсгч'?с:с!х БД с просту. ид?НТ5!ф-.1Р05:2Н5ЙМ СбгЗКГЗ, рЗССМОТр-гНЫ ОСССЭКЗОСТИ С'СребОТ!3! болшас юз информации, высокой гиаамдаа и целостности тага!* систем- Рассмотрены ООЕД и значимость ксаэльгсззнкз пр:пг-цппоз объектно-ориентированного подхода при проектировании кз рьгзукггзняом классе зедач. Гьлолкея обгор по кэтодзм зсеетро-взкия и ргсс;пт?игнетсл проблематика их использования 8 соврз-меннмх ОТД. Сфсрмудирсвгнн требования к БД о учетом спештфихи пп^ормаппоннс-ёмкн:: динаютеских систем к критерии для оценки их эффективности.

Показано, чю проблема большее сбгемзз данш.,: з настоящее

- в -

зр&мя з основном рееаегс-я гиювгаи методами г г счо т коингго-закия более могшой аппаратной подд&р*хи. Это прежде псего Солее быстрые инфорг-.ашижко-ёьлне запомкягпцке устройства пряьд-го доступа и маямкы баз данных (МЕЛ), Непосредственно с

этой проблзмой сгягано ре.г-укиз гздзчн кэ.Епггцпи г Е? в п.тзке обеспечения эффегаивнсгэ доступа к проблема ¿семенник затра? прл ресргаяизэщи и восстановлении БД. ¡Го о С о рассматривается вопрос о динамике таких систем. Изкаганэ, ито р~Бенлгм проблемы белек оСъемог динамических БД яаяя^тоя ксполгзогачие сг.е-цнальньк структур для храненга данных, которые- разрабатывается ссгласнс принципов объектно-ориентированного подхода и учитывает специфику таких систем. В кач^стъе средства для кавигацм1. е НД предлагается исаолмовммэ методов рандомизации.

^ учетом результатов анализе литературы сформулированы '.'рейогания к 2Д с учетом специфики работы ь ¡информационно-эмки;: динамических система.': и критерии эффективности Соль те: ди-наустчгскпх БД.

По второй главе сформуляреванн требования к методу хеширования, Еытекаисз:е иа специфики обработки бельезе хез-тгблиц с зыс-скся динаьсикс-й. Предлагается моде а дсстуг.а к данным, предназначенная для решения задач обработки данных б икформа-цпекго-емких динамических системах с простым идентифицирован..-т объекта к Оагируксзлея кз ксп-льгог-ак».:-! спетдталького метода г е основания {двухуровневое хеширование с использованием открытых ограниченных цепочек). Олпсьгается спешат-кзирсЕанкел ХЬД, называема?. в дальнейшем 0Г.Д2 ■ ^е-ктно-СриентирСЕакнен Зсгьзза Бага Данных Дингдичгская » ООБЬДД ОБ22;, разработанная еь основе предложенной модели доступа. Описана алгоритмы выполнения операторов ЕЦ2 к особенности, ьрегрегавей ре&дизгтзш

Для хранения данных предлагается кспс.иесе&тг спеииелишт параметрически описываемые кольцевые структуры При

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

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

- отсугстшге списковых структур с шпольаовгнкем сизгуя-

- о -

екг укгшая&яеЗ, позволяйте улучшить эффективность и целостность системы;

- з гаиястге указателя ка запись исгаяьауэтгл а?ггч?ккэ логического кягча, что позволяет достигать высокой мобильности данных и з$4ектив.чо реализовать механизм диз;амического изменения размеров структур хранения;

- хеэ-структура продполи аэт укпользагазкэ йлокоргактиро-взниаго доступа к нхеизшй паюти,

- параметрическое озгредэленко области поиска в сочетания с типизированной 4иаичесняЯ структурой хрсшезвет дмашх с яктв-каздим отсюда единым механизмом реализации ввода/выгода;

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

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

Предлагается модель доступа к данным, базирующаяся на использовании КС и методов рандомизации при-навигации в БД и удовлетворяются вышеуказанным .требованиям. Суть предяагзеноЯ модели ааклзсчается в обеспечении классических структур дазавк, а кменно, записи фиксированной длины, валнеи лерешнной длины, массива записей фиксированной длины, при зтепользоизнни за нхн-кем уровне модели згекотораго алемэта хранения дзниък с палым иреиенем доступа я которая учятьваот особенности кзйорг&щхаг-ко-5|«ок дкнгмнчестгкх СОЗД. Формальное описание модели приводится ниже. При именовании объекта модели используется следу»-¡цие соглзпэния: последнее поле в именовании объекта модели опционно и служит в качестве индекса, допускается сокрапркие слов при именовании, "аакааычизанке" с помецыэ о говорит о том, что речь идёт об объекте модели. <БД_глобальная> ::« -«ВД_0>,..., <БД_М» <БД> {<КС_осковнза>,<КС_1!йретолзюш1Я>> <ЙО { <Ьхк:_0>,<Елок_1>,...,<Блж_(>Ь1)>>

- :о -

<06ласте_храке1»кя_зажс>_ПС_1> <Ежх.£> ... <агак_.1-*з-1>

<£жж_1> хрвдвкиЕ..!.», <Влок. аалжей_Я»>

{ < Лриа}иак_шре1юлна ране ;мя _аатсей_КО,

<Елок_аапм1вЯ_К»> = <Залиеь_КС_0> ... <.Ззпись_КС_(п-1)> <Запись_КГ> :: = {<йлаги_гатаси_К>, <(^нгч:5ггалыйЛ_нсмар_гд<й_

сея2Мбзнкм>, <Кж.ч_аапиаи_КО, < Ду.ш,ие_ошо:сч} <влаги_а&пхс*_ЯО ::« <Прка1Ял_иусхой_зт1:шск> ! <Прканш;_аа-п»си_1шрешлййшв> | <Ири2:«ак_си<зша£оЯ_запи:и> | <Грнгз-нак_посведа»й_аал/к:м_при_сяяаш£ЦЛ1я> | <Прхзиак_блсшфон-<ш_аапиеи>

Область хранения конкретной записи КС определяется по клипу с поыощь^ некоторой функции хеширования, а именно. фугкцяи определенна облает* хрзлеши

Н : <Кл««и_за10й:ей_ХО -> 10, (N-1)3

< Даииье_о0т)вкта_ф}!кс> >

1х : <Ятл:_о5ъек'га_фгкс> -> <1ишч_запкск_К> <Дшшью. объекта« <Дгишые_сапися_КО

: <Клян_абъекта_перем> -> Ч<Клш_аапйсн_ЕО_С>,... ... ,<Клпч_аапкси_|£С_пэсдед(на>} <}^ннда_обтекта_пвреы> = <Даиныэ..затшси_КС_0> ... ... <йЕим«_гап»и;й_ПЕ;_последня»> <Иатс»ш_залксой..ф1псс11роБашюйлли«ы> ::= -(<Элауенг _ю.сс,

.... <Эж}мент.|^сиза_(ра21лерноэть_1г1сскБз)>> <<аяемэнт_шссква_л>> {<К;.ам_о£5ъс1аа_масг(са^>,

< Данйш_о&ьекта. ку:сив_3>

Р_аггау : <Клнн_обгокта_ыассю1_-> <Клич_азпкпи_ЕС_л> <дгшныв_оОъекта_иассив_Л> ■= <Датйк_аалиси_КС_}> фикции Г_Пх, Г„уаг\ г_аггау в совокупности определял: функцию атабраюэкид теней объектов на иноксстао клшей записей КС

Р : <Клячи_о&ыгктов> -> «Клети. аапкеей_К1>, определённой на множестве ключей объектов. Операции ЯЦД, определённые на КС:

- ЧЙГАТЬ_ЗАШСЬ_КС (<К5ич_гапкси..КО),

- и -

- ОБНОВИ АПИСЬ_лС КС>\

- У£ШТЬ_ЗАПИСЬ_?Х- < <£яоч_з&т:си_КС>),

- БС1А2ИТЬ_ЙА1Г'1СЬ_КО {<Кшч_э&ГП!-=и_КО;,

- 1ЕРВЗКАЧА^НАЯ_ЗАГРУУНА^ЗАГИ01У_К0 {<&мч„эаяиск_К»).

Здрсь М - коагмстго типов обрабатываемых объектов,

К - рагмер КС в блока?, записей КС,

п - размер блоча записей-КС в <-Запись_КС>,

1 - указатель на начало области храпения (относительный всмер

а КС блока записей), з - размер сбласгч хранения в блоках записей КС.

При этом <КО циклически упорядочена и номера расшреякых блоков записей КС 'Ел?¡о области хранения {1....;1+з-1> отзз-чгет относекия порядка, задгпноыу на КС.

Основным объектом хранения данных служг запись кольцевой структуры <Згпгяъ_КС>, которая однозначно определяется полем ключ записи кольцевой структуры <Ялгсч__знл;гя_ЙС>. Изсто нахождения конкретной <Запись_КС> в <КО ограниченно <0бл_хргя_зап_ КО, которая определяется с помощью некоторой фушзции хеширования (хе г:-функция) Н, задающей отобралэнш шюлэстза клзсчей записей кольцевой структуры <£ггчя_гзш!сей_&> нз множество адресуемых <Блок_залисей_КО. Пример "исевдсреальной" хеш-структуры изобрази на рис. 1. Б случае переполнения попользуется область переполнения <Обл_переполне:иш> (второй уровень хеширования), которая представляет из себя либо дополнительную <КС>, либо в качестве <С6л_переполнения>. слулит первоначально определенная <КО. Допускается взаимное пересечение <05л_храя_ зап_КС>, что позволяет увеличить количество точек первоначального псзииюнирования при навигации в БД. Алгоритмы операций поиска (чтения), замены (обновления), удаления, вставгл и первоначальной загрузки записи с ключом <Ктч_записи_КС> построены на использовании простого перебора <Запись_КС> в <0бл_хран_ зап_КС> с учётом Олаги_зап.иси. КС> и детально описаны а диссертационной работе.

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

«Среднее_№л:гоэг:тво_г.рос> - (2-з)*{ Ма/1-й'2-5)-5-?а)/Ча).

Здесь й - коэффициент загрузки >'С, которой характернее1.' гапо.чкяюю КС и определяется стедуосде- оорагац г - <?сличесгго_хргшичих_гзписбй>.'<Раймар..КС^„записях>, Прнслилеккое средне« количество просчсгргнных запипсй со время поиска пустой записи вычисляемся по формуле <Ср?дн50_количество_про'5_по.1ск_пустой_.зэписи> « (141/(1-а)}/2.

Ключи

записей

КС

н - з — > —

<

IСбл_храненяя|

нения _9; >-

00л_хрм:ения„2

< Нлок_0> < Блок. 1 > < Блок_2> < Влок_о> < Елок_4> <

3-

8>

*пусто

КЕ030

К1^79

-ХРА62

КАР21

*пусто

-КАШЗ

-Ю043

#+11

К2032

КЛУ22

К0231

КУУП2

/Г.-2

К4002

1Д7Б2

ке8к2

К2173

3--,

1(2083 КГЕ44 К5Г04 К567*

9-

><Блок 9>

-1

#'-0

лпусто

К7БЭЭ

*ПУСТ0

К7Н79

8 - расширенный блок записей КС <Елок>

# - системная информация области хранения (<+>,<-> - признак '.. переполнения, <аначэкие> - количество ззлисей переполнения)

* - пустая запись КС (< Клвч_з апис и. КО « "пусто'7)

- запись переполнения (в качестве области переполнения используется первоначально заданная <КС>, хеширование произ-" водится согласно значения поля < Клгч_запкси_КС> Г 43)

Рис. 1. Пример двухуровневого хеширования с использованием открытых ограниченных цепочек

При работе с блокориентированным устройством в качестве единицы измерения выступает количество операций с <Блок_за-писей_КО. 11а практике речь идэт о сканировании одного или двух < Елок_записей_КС>. Приближенная оценка объемов прссматри-

- :а -"

каеаых доннas хэд-структуры в <Базк.згл;яей_.0 зрюодекл а таба. i.

"Гьблвда 1

ОЬгёи ррсекатривавмнх данкьгс в <Бюк_заш1С0й_?!С> прь неплотном ааподноаяи (а < 0.3} м)

Операция ?Щ есть запись нет записи

читать СКП X РБ РОХ

удалги СКП X РБ их

обновить СКП X ИЗ | РОХ

вставить СКП % РБ j ГСХ + С'КПЛПЗ X 7Б

зат'рузка_пэрв0начальнал СКП_ПШ X РБ

*) РОХ - «Размер оСл_хра_м9»ия записи КО з <Блот;_эаписей_ЕО

РБ - <Рагкер блсгл_КС> в «Запись J»

СХП - < Среднее количество проО

СНЩ35 - < Среднее_колит-:есгно_проб_поиок_рустой_<?ашгси>

Z - обозначение операции целочисленного деления.

Описывается специализированная ООБД ОЕД2, аспользущая предложенную нызэ модель доступа к данным. Оеаозгшм объектом обработки системы ОБД2 является «Хъ?кт>, который однозначно определяется идентификатором объекта <Ид_сбг$кга> д характеризуется атрибутами объекта, размещаемым в полз данные фиксированной или переменной длины. < Ид. объекта> з качестве подполя содержи тип (или класс) объекта <Тип_об-ьен?а>, который определяет требуемую <КС>. <Ид_объекта> определяет доступ к <3а-писъ_КС> по ключу.

Систола СБД2 относится к сштешы с процодуриьи еьссеся гсггерфайскаго модуля БД. Предусматривается трёхуровневая поддержка интерфейса с пользователем, а именно:

- бааовьй урсжекь доступа (доступ к <Бапись._КО);

- дзтаческкй уровень доступа (доступ к типовым структурам БД: запись фиксированной длины, запись переданной длины, массив записей фиксированной длины);

- урсшша доступа пола закалила (доступ к специализированным структурам БД).

Интерфейс с БД обеспечивается посредством вызова базового интерфейсного модуля связи с ЕД <3ыаов_бааоео8о_уроеня_ЕД>. При обращении к <Вызов_баэового_урозня_£Д> пользователь пэре-

даёт плодущие параметры:

- блок оппсашк кольцевой структура

- код запроса на обработку данлых базового уровня;

- раамйр рабсчегс буфера;

- адрес рабочего буфора.

Запросы на обработку данных баэогого уровня доступа к Дй ыогуе бить слздукцего гида- ЧИТАТЬ <Запксь_КС>;

- '21ТАТЬ_С_ЭЛХНЛТ0У <£апись_КС>;

- ОВШВИТЬ < Запись_КС>;

- УДАЛЯТЬ <5злисг_КС>:

- БОТАШГЬ <2апксл_Кач;

- ЗАГРУЗИТЬ <5апксъ_нс>:

- БСТАКиЬ_ЗДОЕЬ_ПЕР2!£Щ1£>£„ДЛИНЫ с установкой <Г1риз-нак_свй8авкой. гапкси>;

- ЭАГРУЗИТЬ_ЗАШ:СЬ_]ге?ЕМЕШЮ1!;_ДЛИШ с установкой <Яриз-нак_сзя?анной_зааиси>.

функциональное назначение запросов базового уровня отражено названием запроса. При работе с записи) переменной длины шы с массивом записей происходит уоделпрозание этих структур с использованием <Зашюь._КО. По отработке запроса формируете л соответстзусщ^й <Код_зоэврата>. На уровне доступа пользователя используются нестандартные операции ЩЦ, обеспечогаые самим пользователем к которые поддерживают специализированные структуры БД.

Корреганость данных при множественном доступ? обеспечивается с помощью использования механизма блокировок. Блокировка объекта происходит по сыполненкп опэрацж ЧИТАТЬ_С„ЗАХВАТ0Ы.. Сброс состояние объекта "захвачен" происходит по выполникию операции ОБЮВИГЬ.

Прл хранвюш данпьк во втооной памяти <Блок_запиеей_К1> слуинт в качестве едаиицы обмана, меиду носктэлеы информации и буфером пользователя. В качестве медали памяти, кслодьзузшй 0БД2 для реализации структур шеетго хрвдеиия данкьи, мажет сдулить лпбая аппаратно прддершшаэцая модель матричного представления последовательного нзЛора докш в огораткнной или игоЕней памяти, а именно:

- стандартное дисковое устройство (доступ к блоку данных

фиксированной длины по фкаич5схс«7 адресу <<btamecwisijippsc> ••цилиндр, трак, сектор});

- стандартное дисковое устройство (дг;с;/п к блоку данных фиксированной длины по относительному ягчдару «лтка);

- рчегмяя дисковая память с использовании кластерной ор-га:-:иг алии;

- матриччэд саруктура в ОЛ;

- файловая структура, аналогичная используемой в системе

unix.

'■¿одель стандартного дискового устройства поддерллгьс-гся практически всеми ОС и позволяет реализовать ееод/еыеоц с 101-нимальным временем доступа и обеспечить вис с куп мобильность по данным. Использование кластерной организации позволяет использовать "скрытый11 в ОС обход обработки сбойных участков внешня памяти. Кспользовхнио файловой модели системы UNIX отличается простотой реализации, но является малоэффективным с точки зрения временных характеристик.

Обращение к данным на физическом уровне выделено в независимую подсистему (систему) управления физическим доступом ССУ2Л) к данным и реализовано посредством обеспечения следующих функций:

- инициализация ЕС;

- чтение физического блока по относительному номеру;

- запись физического блока по относительному номеру.

Интерфейс с СУЗД обеспечивается с поморю передачи следу-

щих параметров:

- <БОКО;

- относительный нсмэр <Елок_записей_КС>;

- адрес буфера ввода/вывода.

Для хранения данных используются КС и при работе с ними на физическом уровне происходит обращение к функцилм СУФД:

- ЧИГАТЬ_ЕЮЯ (OTK_EOLEP_EJDKA);

- обновиь_ел0к (0тн_ко1£ер_влока).

Название операции ОБНОВИТЬ_ЗЛОК подчёркивает тот факт, что операция выполняется на предварительно размеренной структуре и исключает многозначное толкование способа физической реализации.

Таким образом, ОБЩ содорго-гг только три систоиогшшсгаад Еызопа. с шяог^о которых оСоспзчиеозтся подцеркка ввода/зшада

и эффективность доступа определяется возможностью использования при этом средств БСВЗ СС

Алгоритмизация выполнения операций ЯМД идеолсгическл построена на использовании линейного просмотра матричной структуры и детально опис-зна я диссертационной работе.

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

Время обработки запроса в 0БД2 определяется количеством операций ввода/вывода при реализации запроса При работе с данными, "разбросанными" по устройству прямого доступа, з качестве главной оценочной характеристики операции ввода/вывода выступает время позиционирования головок.

с0бдае_время_обработки_запроса> =

< Время -установки_головок_Е_началс_области_хранекия> + <Ереыя_работы_на_области_хрзкения>

При этом

<Время_устаноБКИ_головок_р_начэло_области_хранения> « const * (< Размер_КС_в_ш!линдрях> / 3) где const определяется конкретным типом используемого ЗУЦЦ.

Оценка <Еремя_работы._на_области_хра.чения> определяется алгоритмизацией обработки данных при реализации запроса к БД. Количество операций ввода/вывода при поиске не более 2 * <Раз-мер_области_хранения_записи_КС_в_6локах>. При использовании кластерной модели доступа при линейном размещении кластеров (для приведения файла к такому виду применяет программы компрессирования) оценки совпадают. В случае сильного перемесиза-ния кластеров при сканировании <0бл_хран_зап_КС> увеличивается время доступа за счёт перемещение головок на <?аз-мер_ЗУПД_в_далиндрах>/3 при переходе к следующему кластеру.

Мобильность ОБД2 определяется следующем:

- использование параметрически задаваемой КС в качестве базовой структуры хранения данных;

- работа с блокориентированной моделью внешней памяти с минимальным набором операций (инициализация, читать по относительному номеру блока, писать по относительному номеру блока);

- КСП0ЛЬ302?ЙЯ8 При ЯЗВКГаЦИИ ЛОГИЧЕСКИ? КЗЯЧеЗ э физпчйсг.пх указателей, каторс-> позволяет залисимост;-; от типа устройства и физического места расположения дгтаых при ¡ссякрэукса реализации ЕД.

Одним кз способов обеспеччН!*л мобильности данных янляэтс* нс.сс.с^сссск;:? в рамках 0ЕД2 понятия "обсбцзнное" 32"1Д. "С<1 с-5-сенлсе" 2УПД состоит на <Дил> цилиндров, каждый из <Трк> треков (дсро/ак), кзудкй трах из <Секг> еехтороз длиной яо < Длина. сектора* блЛт. Доступ к данным обеспечен с псмскьп операций ЧйТА1Ь( ПИСАТЬ)_Б/лХ_СЕКТО?ОЯ 15с-дэ.к> такого устройства ясгго-ллот га счет разделения структур хранения с точностью до цилиндра использовать эффективные процедура сифроваккя данных к сбеслечпвгет мобильное??! системы при раз .умной аппаратной поддержке подсистем.' зкеиней памяти.

Использование з модели данных понятие "Слокироуьз записи" погиоляет реализовать разграничение ресурсов и обеспечить целостность при обработка удаленных данных с использованием сетевых адаптеров. Программы пользователя при работе с линией для разделения данных используй: буф-эр программного блекл <Сспр.~уе}п:е_с_линней>, который сбсспечивает Воттзлнение следухг фуккшй:

- ПКаАТЬ_3_ГЛНЯЮ_£.:СК„ДАННЫХ;

- чк: АТЬ_С_ЛИБЭ1_Б.10К^.ККСЪ

- ОТРЛБОТАТ Ь_ТАТ^^АУТ.

Г2>;: работе а системах передачи данных (СПД) в качестве цеятрального уз га ковдт использоваться высокопроизводительная Размер ЕД з этом случае практически неограничен в силу кспольесзания для хранения данных ЗУДД больной емкости.

О не ль к увеличения быстродействия системы везмоо-з гаг-руг кз небольших 'Е^объекта* в ОП при открытии ЕД. 3 этом случае обработчик гзпроса риестс обращения к модулям СУФД отрабатывает поиск данных непосредственно в ОП бег изменения логики работы :: прикладных программ.

В чатзйртсЛ глаьэ описывается архитектура 0ЕД2 и инструментальные средства поддержи системы.

Предлагаемая модель ЕД в осровном определила внутренне» архитектуру системы Ы5огсурокневы? подход при организации доступа к данным обусловил создание соответствующих влолекккх уровней со сеокют промежуточными интерфиксами. Архитектура

0ЕД2 приведена на рис. 2.

Программы пользователя

Рис. 2. Архитектура системы 0БД2

Инструментальные средства поддержи вклзчант процедуры '-татистического учёта распределения данных, копирования, пересылки, загрузки, выгрузки БД, 2 также процедуры обеспечения злостности.

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

. - IS -

обслуживанием бол;*лх динамических БД.

^следование эффективности доступа к данным проводилось с учётом специ£::к:т обслуживания таких БД. 3 качестве объекта исследования была вьйредз БД с переменным количеством записей (от £00 до 200000), содержащая записи вида •£<Клич>, < Поделанных» h При проведении эксперимента с помоги генератора случайных чисел формировались смеси операций на БД, катера обеспечивали раз личные уровни динамики. Эксперимент проводился на v.2z:?.io типа IEM FC/AT для 0БД2 (дескрстторкыг файлы), 0ЕД2 (кластерная модель), 0БД2 (траловая модель> и roxEase-t-, Fox3ase+ Сил выбран s связи с тем, что является наиболее типичным представителем реляционных СУБД, часто используется в промышленных разработках и обладает достаточно высоким быстродействием.

Исследование показало, что 0БД2 за счет унификации алгоритмов и структур хранения данных отльчаэтея от других систем минимальные затратами ОП Отметим, что в некоторых промьален-ных версиях СУБД за малыми затратами ОП скрывается "подкачка" оверлейных программ. ^Максимальный объем доступных структур внешнего хранения данных на ЗУПЦ практзг-гзеки неограничен г".я 0БД2. Это определяется тем, что для доступа к данным расположенным на одном ЗУПД используются методы доступа требукске открытия не более одного системного блока управления данными (БУД). Калримгр, з среде .VS-D03 на Е?БМ типа IEM FC з случае физического доступа БУД вообще не требуется, при использовании файловых структур достаточно одного открытого блока описания файловой структуры для данных, хранящихся на одном ЗУПД. Бтэ достигается за счёт того, что все 5УВД (или его часть) выделяется под хранение данных одной файловой структурой.

От im че ко, что в большинстве реляционных БД динамический релям работы вызывает рост поддерживаемых структур хранения данных за счет "пустого" пространства на месте ранее удалённых записей, при этом используемые процедуры "сбора мусора" и ре-индексации характеризуются сильной зависимостью от объёмов БД. 0БД2 выгодно отлгчается з этом плане отсутствием всяких зависимостей от временн работы динамической системы, прошедшего от первоначальной загрузки БД. Отсутствие поддерживаемых внутренних индексных и списковых структур имеет следствием меныне затраты внешней памяти, снижение временных затрат при обработ-

ке запроса к БД и Солее значительные гарантии по обеспечения целостности системы.

При сравнительном анализе разработка системы на базе сетевой ОС фирмы .NOYELL выявился ряд преимуществ 0БД2. Прозрачность интерфейса с системным ПО позволила обеспечить эффективную реализацию механизма разделения ресурсов. При анализе распределенной БД в сети 33U звездообразной конфигурации был выявлен ряд преимуществ vBffi обусловленных простотой пользовательского интерфейса к единой идеологией организацией доступа к данным. Это позволило аффективно реализовать сетевую поддержку в системе и обеспечило высокую мобильность данных.

Одним из примеров использования предлагаемых КС является экспериментальная разработка однородной распределённой БД на сети кольцеобразной конфигурации из 1ЭВУ типа IBM PC. Успех проекта был обусловлен палыми затратами OIL

(хжошшз результаты работу

1. Разработана математическая ■ модель СОЕД, в.оззодянцзя обеспечить:

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

- работу на малых Збъёмах ОП;

- поддержку распределённой БД при работе в сети.

В рамках - модели разработана концепция логического ключа в качестве замены физического указателя на запись и на её основе методы обеспечения мобильности данных и ГО в специализированной ООБД.

2. Разработан метод двухуровневого хеширования с использованием открытых ограниченных цепочек, который обеспечивает независимость времени поиска от динамики системы (отсутствие "скручивания" и необходимости "сбора мусора"), учитывает специфику блокориентированного доступа к данным и позволяет задавать максимальное количество операций с блоками записей хеш-таблицы при поиске.

3. Созданы программные средства поддержки и сопровождения специализированной ООБД, которая шкет быть использована как инструментальное средство для разработки СОД в информацион-

ко-ёмких динамических системах с простым идэнтиодированием объе кта. На базе разработанкой математической модели ООЕД реализованы специализированные СОД,

4 Разработана оде ль сетевой СОЗД, предназначенной для работы с большими объёмами обработки данных и ориентированная на использование простьпс иеханкэ'.йа передачи информации на ПЗЕЫ с ¡той ОП (иэнзе 253К). 3 рамках модели рэализована экспериментальная распределённая ООЕД,

5. Разработаны методы оценки эффективности доступа к данным и выбора оптимального подмножества операторов ЯЦЦ с учётом специфики БД. Еа Сазе разработанной математической ¡.ядэли проведены вычислительные эксперименты по исследовании эффективности доступа в больших динамических БД.

5. Выполнен сразнитэльный анализ СУБД для задач, связанных с использованием больших динамических БД с простым идентифицированием объекта. Сравнительной анализ показал актуальность разработки специализированных ООБД на этом классе задач.

Ос но гни? результаты диссертации опубликованы в следущк работах:

1. Уухоз С. К , Штхеков Л. П. Базы данных с рачдошши-рсвачным доступом на основе картотек с кольцо-вой структурой. -!£шск, 1939.- 18 с. (Препринт/ Ин-т техн. кибернетики АН БССР; N 14).

2. Мухов С. В., Ма-тсакоз Л. П. !йбильные Сазы данных с с рандомизированным доступом на ПЗЗД. - ¡¿инск, 1990. - 26 с. (Щзепринт/ Ин-т техн. кибернетики АН БССР; N 7).

3. Мухов С. а , Катхлксв Л. П. Модель взаимодействи-я пользователей САПР СБИС с базами данных // Проблемы построения САПР СБИС. - !&нск: Ин-т техн. кибернетики АН ЕССР, 1950. -С. 30-37.

4. Мухоз С. Е Двухуровневая модель доступа с рандомизацией к данным САПР СБИС // Тезиса докладов I сове!дзнил-сем'.яара "Промышленные САПР в области электроники и вычислительной техники" г. Брест. - 1!инск: Ин-т техя. кибернетики АН БССР, 1990. -С. 54-53.

5. Мухов С. а , Уатогкоз Л. П. Об кспсльзовачии параметрических кольцевых структур с рандомизацией в базах данных САПР // Тезисы докладов Всзсоезного научко-техничэск^о семинара

"САПР в машиностроении" Ыинэлектротехприбор СССР.- Ульяновск: НПК УЦМ. 1920. - С. 9.

6. Пухов С. R , Матюшков Л. П. Реализация методов доступа с рандомизацией на кольцевых структурах в сети IDEM. - 1!инск, 1291. - 1Б с. (Препринт/ Кн-т техн. кибернетики АН БССР; N 12).

7. Ыухов С. В., ife-iLJKOB JL П. Модель сбъектно-ориантиро-ванной базы данных САПР СБИС с использованием двухуровневой рандомизации на кольцевых структурах // Тезисы докладов II со-Еешэния-сешшара "Промыалэнные САПР в области электроьчгки и вычислительной техники" г. 1рест. - Минск: Ин-т техн. кибернетики АН ЕССР, 1991.- С. 26-37.

8. Цухов С. Е , Уатипков Л. П. О реалиаац!ш на ПЭВМ доступа к данны1.' по нескольким ключам с использованием методов рандомизации// Система автоматизированного проектирования САПР СЕКС (функционально-логический уровень). - Минск: Ин-т техн. кибернетики АН ECCF, 1991.- С. 76-83.