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

АКАДЕМИЯ НАУК АЗЕРБАЙДЖАНА ИНСТИТУТ КИБЕРНЕТИКИ

На правах рукописи РГ5 ОЛ УДК 681.5.015

2 4 АПР 1995

ШАХБАЗОВА ШАХНАЗ НАДИР кызы

ОПЕРАТИВНО-АССОЦИАТИВНАЯ ФИЗИЧЕСКАЯ МОДЕЛЬ ДАННЫХ БЕЗ АНОМАЛИЙ ОБРАБОТКИ, ОБЕСПЕЧИВАЮЩАЯ ДИНАМИЧЕСКУЮ НЕЗАВИСИМОСТЬ В БАЗАХ ДАННЫХ РЕЛЯЦИОННОГО ТИПА

Специальность: 05.13.14 — Системы сбработки информации

и управления

АВТОРЕФЕРАТ

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

БАКУ - 1995

Работа выполнена на кафедре «ЭВМ и системы» Азербайджанского Технического^ Университета.

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

—доктор технических наук,

профессор, академик Международной Академии Информатизации Аскеров Т. М., —кандидат технических наук, доцент Абидов Ч. Д.

Официальные оппоненты:

—доктор технических наук, профессор, —академик Международно)! Академии

Информатизации Соломатин Н. М., —кандидат физ.-мат. наук, доцент Махмуд-заде Р. А.

Ведущая организация—Институт Системного Программирования Российской Академии Наук.

Защита состоится „ У/ *• ^сСь^-_1995 г.

в // часов на заседании Специализированного совета Н 004.21.01 по присуждению ученой степени кандидата технических наук в Институте кибернетики Академии наук Азербайджана по адресу: 370141, г. Баку, ул. Ф. Агаева, 9.

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

Автореферат разослан « »

Ученый секретарь /

Специализированного совета, У

кандидат технических наук, с. и. с. НУСРАТОВ О. Г.

- 3 -

Общая характеристика работы Актуальность теми.

В связи с появлением и широким внедрение» построенных Л'Л базе современных микропроцессоров персональных компьютеров, длл большинства областей народного хозяйства, наряду с другими, основным орудием труда становится и информация. Широко внедряемые локальные и глобальные информащюшга-вычислитвльние сети и в их состава различнче объектно-ориентированный автоматизированные системы обработки информации ' и управления, так называете специализированные автоматизированные рабочие места (АРМ), вошли в нозузэ стадию своего развития. Они незаменимы для успешной, организации всзсбъешвкцеЯ системы автоматизации

оперативно-управленческих и отчетно-статистических конторских

работ (о?Пс& гиговагюп}.

Задачи, реваемие в таких специализированных АРМ-ах характеризуются: большм разнообразием информации (сотнями шллиснов байт данных, различных по форме и ведению документов); большим объеггам динамически изменяющихся .зо времени и по интенсивности наполнения операция обновления, включения и удаления данных; значительной ьзаимосвязанностью отнесений (ассоциативные шогослигксБне структуры) и болтам их количеством и разнообразием; переменней длиной и составом записей, содержащих разного типа поля; большой частотой использования и значительны-.' количеством храниим для псследувде« итоговой обработки дгнних и их организации.'

Как известно, реляционная база дзгекос (БД; является совокупностью взаимосвязанных и организованны;: в нид-з двумерных таблиц данных, которые можно обрабатывать различными программами, модифицировать и обновлять с помощью специальных средств управления базой данных (СУБД). Однако, реляционная СУБД з Сольгашство случаев для специализированного применения в системах, характеризующихся Быгзпзречисленнами особенностями, обладает рядом недостатков, которые снижают эффективность использования ресурсов вычислительной системы,:! ограничивает возможности слонно-логической оперативной обработки данных. Основными и-" достатками являются: в связи с нормализованным представлением отношений увеличивается избыточность при логическом представлении данных и ' требуется применять более эффективные модели физической организации, т.е.

алгоритмы теории нормализации да позволяют получить минимальную избыточность данных, подлежадо хранению и обработке е БД; при декомпозиции сложного универсального отношения с целью ее нормализации, увеличивается количество производите нормализованных отношений, что приводит к усложнению запросов, поскольку они 'должны поддерживать прохождение цепочки из соответствующего количества нормализованных отношений при поиске требуемых данных ( общая эффективность системы резко снижается при более интенсивном потоке запросов, что является- характерным для оперативно-информационных систем); возникают аномалии вставки, удаления и обновления, понимая под аномалией отклонения от нормы при выполнении указанных процедур (количество ае таких процедур в олоративно-ин1|ормационных системах значительно); ЕследстЕИИ вышеизложенного увеличивается' время отклика системы и возникает проблема болов ^активного обеспечения динамической н. зависимости и минимизации времени физической привязки данных; при • обработке сложных логических • услоеиП эффективность системы снижается, т.к. пр!£Ходося включать в процессе обработки значительное гчличество отношения; невозможно создавать ыногосписковые многслризнакозые ассоциативные структуры данных, характерных для оперативно-информационных систем, без значительного увеличения кoJичecтш отношений и установления сложных взаимосвязей мезду ними.

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

Работа выполнялась согласно комилексно-целэвой программе "Создание и внедрение микропроцессорной техники в народное хозяйство Азербайджанской республики" по теме "Микропроцессорио-лрограммные ерэдетш повышения эффективности использования ресурсов вычислительных комплексов, систем и сетей " (регистрационный «01860093138) на 1986-1990 г.Г. И 1991-1995 г.Г. '

Цель работы.

Основными задачами разработки и исследований являются:

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

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

- создание возможностей Формирования цегаясс, гнездовнх, узловых и комбинированных ассоциативных структур данных;

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

- разработка эффективного механизма отобранения логической модели данных в физическую и наоборот; .

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

- разработка система генерации тштегрированной БД.

Методы исследований.' • ; • '

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

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

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

- исследованы различные мзтоды орга!31 з ашпг многослискоеых многопризнаковнх ассоциативных, структур данных (последовательные, цошше, гнездовые,узловые и др.), разработаны оригинальные способы их формирования с прт-дпэкпем кощопщи логических скал позиционного кодирования (Л2Е0 и яоглгяпо, что при сильной взошюсчяззннссти ассоциативные элзнектов дашпх пр.здлоп:внны9

- б -

структуры обеспечивают наибольшую динашческуп независимость данных;

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

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

- физическая модель состоит из объектной части (последовательные сгис;;;; деканов) и поисковой структура, формируемой в виде булевых изтшц, фжсируызих ассоциативные связи, существуйте мекду отдэлъ:.кми элементами различных доменов (атрибутов).характеризуемые удсбосзимаехость» и обеспечивающие относитольнс простые алгоритш пополнения процедур ивстав2'л", "обновление", "удаление", а такге шиьмзльное время рвагадаи системы на запрос по отношению к соответствующим реляционным СУБД, в которых модели данных организованы в виде нескольких отношешй, представленных в нормальной (¿орм-э БоЯса -Кодца;

- разработаны оригинальные алгоритма совместной обработки объектной и структурной частей модэли ко схема записи-считывания данных в стековой памяти типа ЕЧГО и алгоритм гакэрации тисковой структуры с использованием счетчика "бегахедл одшеща" в процессе начального ввода отнокекий з БД;

- слоеннэ логические условия поиска з запросах фор:.зрргаел ПОСрёдСТВСМ Л0ГИЧ03121Х СВЯЗОК И, \'Ж\, КЗ, БНПаЛКЯеМЫЗ ТОЛЫ» над

соотЕегстБунцгаа векторами- столбцами покзковгз матрен;, а выдача трзбуеыой информации производится в соотгатствж с получзаша прокзЕадшгл вектором-столбцом и ключевым домоком.

Практкч-эскай ценность к вшдрзнн-з результатов рабегы.

Рсз1й5огак(ая сазгслшко-йсссцг'зтин^я Сжппэская модель

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

При этом удовлетворяются такие требования как большой объем памяти, сложность логических условий многоаспектного пои.стл, дружественность пнтерфойса и массовость использования со стороны неподготовленных пользователей. Повышается оперативность и более эффективно используются ресурсы вычислительной системы. Предложенная концепция модели данных и разработанные алгоритмы и программы (на языке СИ) внедрены в оперативно-справочной системе "Кадри высшего учебного заведения" для Факультета автоматики и вычислительной техники Азербайджанского Технического университета (на IBM PC/AT).Система рекомендована для тиражирования.

Аппробация работы. Основные результаты диссертационной работы

были изложены и обсуждены на республиканских научных конференциях аспирантов Азербайдаанской Республики (1983-1384 и 1988-1939 г.г.), на всесоюзной конференции по искусственному интеллекту (г.Москва, 19S8), на всесоюзной научно-практической конференции молодых ученых (г. Фрунзе, 198Sr. ), ¡fa научно-методических конференциях профессорско-преподавательского состава АзТУ (1990-1994 г.г.),а также на научном семинаре Института Кибернетики АН Азербайджанской республики.

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

Структура и объем работы. Работа состоит из введения, трех глав,

заключешя, литературы, включзщей 63 наименования и 2 приложений. Основное содерглние работы изложено на 213 страницах, включая 19 рисунков.

Основное содержание•работы.

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

таете краткое содержание работы.

В первой главе исследованы и проанализированы основные задачи обеспечения независимости данных в' ЕД. Раздельно рассмотрены задачи логической и физической независимости данных, и соответственно вопросы, связанные с их логическим и физическим описаниями.

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

Следовательно программное обеспечение (ПО) располагает средствам! отображения файлов структуры прикладного программиста в такую физическую структуру данных, которая запоминается на реальном носителе информации, и наоборот. Значит, глобальное логическое представление данных монет сильно отличаться от физической структуры (организации) данных и от их прэдетавлэний в конкретных прикладных программах,. т.е. от внешних- представления (организаций) данных.

Существуют системы с различными степеням! обеспеченности независимости данных. Однако, во многих ответственных и важных приложениях,например, в системах, призванных отвечать и на заранее незапланированные ' запросы, возможно обеспечение полной независимости данных имеет'первостепенное значение.

Процесс преобразования одного описания данных в другое называется привязкой. На рис.1 приводится схема выполнения логической и физической привязок.

Разработана модель процесса привязки (рис.2), которая отражает возможные. моменты его выполнения: во время компиляции прикладной программы (г5); во время установления связей объектной программы с предварительно ' откомпилированной таблицей ( или программными модг'лями ), содержащими описаше данных (); во время загрузки.прикладной программы И3); во время открытия файла Иг); во время выборки данных и,,). Как видно, если г.тивязка выполняется во время выборки данных ), то период зависимости данных в прикладной программа от их физической организации 'гзав=^ЧГ1'1* будет минимальным.

Рис.!. Схема выполнения процесса привязки.

--Выполнение программы

- Момент привязки

-Выборка данных

- Открытие файла

- Загрувка прикладной программы

- Установление связей обгзктной прогул

- Компиляция прикладной программ

Процессы

Условное вргш

Рис.2. Временная модель процесса привязки.

Если процесс логической привязки выполняется во время компиляции программы, то в период U5*tM) схема описания данных (S) не должка меняться, т.е. S = const. Если же физическую привязку осуществляют во время компиляции программы, то физическая организация данных S(ф) должна сохраняться неизменной в период (t5ftM). Следовательно, привязка, осуществляемая во время выборки данных обеспечивает максимальную гибкость и называется динамической привязкой (динамическая независимость данных).

Выполнение процесса привязки в i-ый момент периода (^-^у). где обеспечивает статическую независимость данных

(статическая привязка). Последняя стоит сравнительно дешевле. Однако, существуют ситуации, когда динамическая независимость данных является существенным. Напр., если пользователь не является программистом (ато наиболее распространенная ситуация) и хочет обращаться к структурам данных некоторым способом, который предварительно не был запланирован, проведение процесса динашчаской привязки неизбежно. Ьообще, когдз одни и те же типы данных, расположенные в разных участках памяти, могут иметь различные форматы и связи, то динамическая щгшязка необходима, чем длительнее существует (живет) БД и чем большее количество сис.'ем или грулл программистов объединяются для работы (сеть, объединяющая ЛРМ-н) на одних и тех же компьютерах, тем больше вероятность наличия в системе несовместимых файлов, что приводит к необходимости обеспечения динамической независимости данных. Точно так- же ,когда для повышения производительности системы необходимо обеспечить хранение разных версий записи одного и того ке типа с помощью различных физических организаций данных, динамическая независимость неизбежна.

Динамическая .независимость дэньдс отличается следующими особенностям»!: возможностью "сосуществования" различных форм представления однзк и тех же дашшх; ' для различных форм представления дашшх 'можно использовать различные схемы ивдексацил ш адресации, различные типы кодировашга и способы разкоггег-ыя элементов данных, различные клочк защиты и т.д.; перед вылолпонкем программ кэт надобности производить кх перекомпиляций; согласование г.ршслэдноЛ прог^акш с ¿ашшц осук>эсг;ил:«эгзл во гремя счшнЕакия дашых -иззави:»» от форж их пр^.детекадкия. Пчретислокш

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

Таким образом можно сформулировать следующие основные проблемы физической организации БД с динамической независимостью:

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

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

- организация древовидных и сетевых структур в' виде совокупности последовательных битов;.

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

- организация физического размещения данных с максимальной плотностью;

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

При этом должны быть получены:

"Тзав= «V V-*0111'

- эффективное нсгользовзние памяти;

п

- У V ■—т1л , где V - объем избыточных даных 1-го файла,

п - максимальное количество файлов в системе;

- эффективные с средства преобразования форматов представления данных;

- эффективные средства выполнения процедур вставки, обновления, и удаления;

- гибкие средства и методы адресации данных;

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

- эффективные метода и средства фиксации взаимосвязей, существующих между элементами данных;

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

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

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

вОО Б(р; „—„ Б(ф) _ (1)

Нас интересует Б(, необходимое системному программисту

или системному разработчику, которые занимаются1 вопросами эффективности работы системы, расположения данных на носителях, их индексирования или поиска, а также вопросами использования методов сжатия данных ,

При этом должны быть учтены основные требования, относящиеся к обеспечению динамической независимости данных (глава 1).

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

(к) (к) (к) (к) а1 = * хи • \г *"•* Х1ч > »

где 1=1,0 и 0 есть мощность конечного множества сущностей, прэдставяяемых в разрабатываемой БД на концептуальном уровне,

Г (1:) 1

ЛТРхЧЧ }•

где есть максимальное количество разнообразных атрибутов, описивзщих конкретную 1-ю сущность, т.е. аг .Тогда

и (АТР)1 = | ]■ ,

где ъ 1,4 и Ч есть общее количество разнообразных-атрибутов, применяемых ■ для описания всех <3 сущностей.

Ассоциации элементов дашшх представляются бинарными связями в основном двух типов: "один к одному" (одномерная ассоциация, означающая, что в каздый момент времени t, каздому значению элемента Л соответствует одно и только одно значение ассоциацировэнного с ним элемента В, т.е. А В);"один ко многим" (М ассоциация, означающая, что одному значению А в каждый момент времени 1; соответствует несколько значений ассоциацироЕЭННого с Л элемента В).Значит возможны четыре представления прямых и обратных связей (1:1, 1:М, И:1,М:М). Здесь ваяным являются временные ограничения I, в зависимости от которых могут .изменяться типы ассоциации и, при не учете Ъ, могут возникнуть ситуации, приводящие к противоречивости базы. Обозначим генеральное множество существующих взаимосвязей через Э , т.е.

где 1, 3 принимают значения 1,Q ШЗ) и учитываются таете все существующие гзеттрцбутные связи. Тогда на концептуальном уровне

Б(.С) Г | ОО J __ Л (2)

I L 1 ji=I,Q 1 ~ Js=1,4 J '

(Г) .

Йа уровне Б , как изеостно, наиболее часто применяются иерархическая, сетевая и -реляционная- - модели- дзнних,

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

' Физическое представление Б строится на базе компонент

(р)

(2), принятых моделей представления данных • на уровне Б и тлеющихся средств реализации БД.

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

Обозначим время, затрачиваемое на выполнение процессов, указанных в блока через Тогда на выполнение процессов, связанных с физической памятью (процессы взаимодействия) и пересылкой требуемых записей в рабочую область ПП потребуется время

ТФ= £ ь. .

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

тф < 'VV •

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

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

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

Опишем предложенный принцип организации требуемой поисковой структуры с применением концепции ЛШПК.

Предположим, что тлеется упорядоченная (или фиксированная; последовательность п элементов данных . Удобнее всего такую последовательность представить в виде кортежа '

(Я (Я (Л) С;)!

^ = < й1 ' <*2 • Й3 ' ■ % >>

<я

где З-идентификатор последовательности, с^ е 1-ый элемент

3-ой последовательности, 1=1 ,т. Последовательностей может быть

несколько (3=1,п).Предположим,что элементы З-ой последовательности могут характеризоваться максимум К^ признакаул (атрибутами). Эти признаки такие могут быть представлены в виде фиксированной последовательности- ■ '

<я <я ся ся

= <и1 ' и2 ' "З > '

(3)

где и е » ¡1 =1,К . Для всей БД могут быть определен»

Ч^. ^ 0 3

последовательные списки объект"® ( сущностей ) и атрибутов (соответственно их обозначим через ПСО и ПСА)

и Б = Б, и и = .н. 1 3 3

Операции объединения проводятся с раскрытием кортежей, которые могут содержать одинаковые элементы. Тогда

чг, а3, ... , ат> ,

с

н = «2> »3 , ...» «к >

являются основными параметрами реляционной БД , т.е. строками (записями, характеризующими . отдельные сущности) и столбцам! (атрибутами - характеристиками генерального мнсжества сущностей) универсального отношения . Для выделения -атрибутов из и,

характеризующих конкретную сущность с!^ предлагается сформировать ЛШПК

V < ая' «¿3- ' V элементы которой определяются следующим образом

а, =

Jя.

1 , если й^ характеризуется ■ признаком (атрибутом)

О , в противном случае .

Таким образом, получается структура Б, состоящая из конечного мновества ЛШПК (кортежей) 3= | или же из универсальной

булавой матрицы Э = <х , где З-Т/п и . Конкретные

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

"а = < Рч1» р<53' ' >

Э г (где могут фиксироваться различными способами:

единичкш значением компоненты соответствующей ЛШК (или двоичным номером позиции) для косвенной адресации; фактическим значением фактографического данного; автономной организацией структурной и соответствующей объектной частями. Теперь структура физической модели БД с динамической независимость» данных в терминах ЛШПК будеть иметь вид,приведенный на рис.З.

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

-Н г

Выдача данных в-буфер и рабочую область БП „

Ответы на запросы

{ а1

г

Логические операции над ЛШПК

Определение соот-Еетствуюднх ЛЩПК; Определение физического адреса (адресов) объекта (объектов); др.

Определение логичес-кп операций и последовательности их выполнения

Запросы

Рис.' 3. Структура физической ¡додели БД с динамической независимостью данных в тершшах ЖПК.

произведено их сравнение с ' классическим: метода^! иостроаши подобных структур .Сопостовителыгшй анализ показал,что применение

концепции ЛШПК при большинстве случаях является более эффективным.

Составлены программы машинного моделирования этих способов организации списковых структур, работающих в составе внедренной системы 'Кадрн-ВУЗ".

В этой главе разработана общая модель многосписковой многспркзнаковой ассоциативной структуры и механизмы адресации и аппарат логической обработки данных, интегрированных в этой структуре. Исследованы причины возникновения аномалий обработки в Г.Д реляционного типа, обоснованы возможные варианты их устранения путем формирования поисковой структуры с применением концепции лШЛК и разделения последней от объектной части системы. В общей модели объединены возможные типы имеющихся в системе слиское посредством единой многосписковой многопризнаковой ассоциативной структуры, объектные части которых в основном состоят из общих ;ithckob последовательного типа < наиболее простые списки).

Соответствующая математическая модель динамически независимой физической модели БД состоит из следующего.

• I. Множества доменов БД DCI]

= { (D I _

где 1=1, К и эти шояеетвэ могу г быть представлены в гиде упорядоченного по определенному признаку (например, если домен содержит символьные строки, представляющие собой нaзEaftия предметов, то его элементы могут быть'упорядочены по буквам алфавита) кортезш

11. Кортеж доменов БД

в; ■= < 31, иг, ... , ш >.

Каждый га этих кортежей идентифицирует определенное множество домен) элементов (например, множество целых ■ чисел, названия ¡.радметов и т.д.), которое так не представляется в виде -лсрядочекного .кортежа ИГ, где кет совпадающих элементов тличительная особениость-бозизбыточность доменов).

„,.» (I ) (I ) (I > С1 )

III. БГ » < , у2 , У3 , у1у >. -

Множество элементов фиксированного домена 1)1* представляет собой последовательней список , где члени списка упорядочены по эффективному, с точки-, зрения шпшшзащш избыточной 1Шформации (сжатие), ко!,шлексу признаков и который располагается в автономной области памяти со свои.! фиксатором.

Каздое фиксированное отношение ЯХ* . определяется последовательностью осей проещнроваиия ИХ*)

IV. 1(Х*) = < 1 ,1 ,...Л >, 1 < 1 1 ,

<Ц 1а ч2

V q1 е {1, 2, 3, ... , К }.

V. 'Атрибуты 0ТН01ПЭ1ШЯ ИХ*

пр . • Ш*= < В[1 ]=УЧ ВС1 3 = щг, ... 0С1 ] *

VI. Корневые поисковые структуры 3(У*)■отношения ЯХ*

* (О) „ (0) / (О) .

ЖПК [S0(X*)]= < st • (X*), з2 (X*),..., зк (X*) >,

{0) J 1, если DI* е RX* ', V = - 1 0, если DI* i RX* .

Vit. Обобщенная корневая поисковая структура S0

f.! (S ) -булевая матрица.

VIII. Поисковая структура oTnoneira RX*, т.е. S(X*):

D Ci ], L[i ], ... , DCi ] - домены; q1 q2 qz

Yq^Yn,, .... Yqs , - атрибуты;

RX* (Yq,,Yq2, ... , Yqj - отношение;

Yqi -» Yq2 ; Yql — Yq3 , ... , Yq, — Yq, ,

у у 1 е юс1 з , V у. 2 е ВС! ], ... ,

(О

ЛШПК (Yq1—» у1 2 ), ЖПК (—^ Уг 2 ),..., ЛШПК (У^, -для одного 1ч2 атрибута,

лшпк^ —► у;^ ) = < ъ

У,*2 ) ч2

у )

1

при 3 = ~огт , з = 1,2, ... , К и 2

1, если у.

Ч

0, в противном случав

IX. Обобщенная последовательность ассоциативных бинарных матриц для отношения ИХ* , Yq2 ,

ЬШШК -

ШППК —► Yqз )

МЛИПК (Yq1 —► Yqг )

*Чг )

Далее произведено исследование предложенной физической модели данных на аномалии, возникающие при выполнении 'процедур удаления (аномалия "удаление") и обновления (анызлия "обновление"),а так аё включения (аномалия "включение"). Показано, что в ' предложенной физической модели БД эти аномалии отсутствуют.

Разработаны общие алгоритмы выполнения указанных процедур.

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

Дчлее произведено исследование модели нэ•выполнение операций

и поиска данных со слолными условиями поиска. Показано, что при поиске одновременно выполняются и операции обработки данных, т.к. поиск ведется в соответствии с обработкой составляющих поисковой структуры (столбцов матриц) согласно условию поиска. Физические адреса искомых данных определяются соответствующей обработкой производного столбца-Евктора. Разработан общий, алгоритм выполнения операций поиска (с одновременной обработкой), состоящий в основном из типовых процедур выполнения логических операций и, ИЛИ, НЕ и кх различных комбинаций над столбцам!, строками и матрицами поисковой структуры. В работе пригодятся примеры выполнения различных вариантов поисгл.

Данная глава завершается разработкой некоторых предложений, связанных с вопросом возможной автономней аппаратно-программной реализацией данной физической модели БД с учетом возможностей современных БИС программируемых (или перепрограммируем*«) логических матриц и микропроцессорных средств.

Третья глава посвящена разработке алгоритмов генерации физической модели и процедур функционирования системы с динамической независимостью данных. ' Разработаны общий алгоритм генерации систем!, алгоритм формирования последовательных списков и Еекторов-столбцов матриц поисковой структур« динамичен« независимой физическом модели отноиеиия. При этом продлении оригинальный способ формирования ЛШПК с использованием считчика "бегающая единица"'и схемы записи-считывания в стековой памяти типа FIFO, в работе приведены фрагменты принщшиально-структурноп схемы физической модели данных. Здесь же разработаны машинк:;э алгоритм» процедур обработки простых и сложных (многоаспектных) запросов с использованием одного отношения, с использованием нескольких отношений, без'логической обработки векторов-столбцов и с логической обработкой соответствующих векторов-столбцов. При этом определены и наследованы некоторые временные характеристики машинных- процедур обработки. '

Основными типовыми процедурами (модулям!) алгоритма обработки простых и сложных запросов являются:

- анализ ЗАПРОС-а. и обращение к СПРАЮЧНИК-у для считывания ЛШПК отношения (или отношений) в буфер обработки (БуфОбр);

- определение ключевого атрибута, параметров обработки ЗАПРОС-а

в соответствии с объектной частью отношения ОВМ(t). и их перепись в БуфОбр и выходной буфер (ВыхБуф); .

- обработка содержимого областей БуфОбр в соответствии с ЗАПРОС-ом;

- обработка содержимого БуфОбр в соответствии с содержимым ВыхБуф (ЖПК ключевого. домена) и формирование в ЕыхБуф. требуемой

информации;

- обработка определенного домена в соответствии с МПК по. схема стековой памяти F2F0.

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

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

В приложениях 1 и 2 имеются акты внедрения основных разработок диссертационной . работы в составе оперативной информационно-справочной системы "Кадры- ВУЗ", краткое описание программ' общей системы "Деканат" в состав которой бходят подсистемы "Сессия", "Учебный план", "Стипендия".

- 23 -ВЫВОДЫ

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

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

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

4. Исследован:: и проанализированы различные метода организации ыногосписковых мкогопризнаковых ассоциаигашх структур данных (последовательше,цепные, гнездовые, узловые и т.д.) и разработаны ор;ппиальныэ способы форихрогания таких структур с применением логических . шкал позиционного кодирования (ЛШПК).

5. Разработана общая модель многосписксвоП многопризгшюеой ассоциативной структуры, гэханнзм адресации и аппарат лоппесксй обработки Дании с пргиэкением ЖПК.

6. Произведено исследование предложенной -дшиютюски незавксимоЗ физичесгл! шдзли даншпс на аномалии. Исследованы проблемы, связанные с вшюднэкгегл различных вариантов процедур обновления, удаления и вставки. Предложенная физическая модель данных отличается тем, что структура состоит из универсальны:; отнесений, но требуется вшгалгзнкз процедур нормализации и декомпозиции глздого универсального- отпевания т ряд норнализовашгеих отновеняп, в результате чего создается удобства потребителя в форг.лрованит1 слояпс: запросов и укзиьпз-этея общее врзмя поиска тробузиах дашшх ио этим запрсс-?-',

7. Разработанная физтпзехж ¡.год.зль ятях ксслздотана на эффэктатссть пгааливпия сиот.'аут псккса латешх со слогшмн лоютпекмян усдоЕгзями поиска.

8. Разработана физическая модель данных, которая состоит из двух частей: объектная часть, содержащая последовательные списки доменов,матрицы поисковой структуры,состоящих из векторов-столбцов ( логических икал позиционного кодирования.), фиксирующих ассоциативные взаимосвязи,существующие между отдельными элементами различных доменов (атрибутов). Формирование поисковой структуры в виде булевых матриц,связанных с одним ключевым доменом (или so с составным ключам, образованным при помощи операции "конкатенация" из ' нескольких доменов) позволяет использовать единственное универсальное отношение, лишенное проблем, вызываемых Еыполнешюм процедур "вставка", "обновление" и "удаление". Такая структура содержит мишшальную избыточность, характеризуется относительно простыми алгоритмами выполнения процедур "вставка", "обновление", "удаление" и минимальным временем реакции системы на ЗАПРОС по отношении к реляционным СУБД, представленным в " виде нескольких отношений, представленных в нормальной форме Бойса-Кодда.

9. Разработан оригинальный алгоритм совместной обработки объектной и структурной частей системы по схеме записи-считывания данных в стековой памяти типа FIFO.

10. Лрэдяоаан • эффективный алгоритм генерации поисковой структуры системы с использованием счетчика "бегающая единица" в процессе начального ввода универсального отношения в систему.

11. Процедуры "вставка","обновленке" и ' удаление" выполняются, з основном, в области поисковой структуры путам изменения состояния определенных разрядов логических шкал позиционного кодирования. Сложные логические условия поиска в ЗАДРОС-ах формируются при помощи логических связок И, ИЛИ, НЕ, которые выполняются над соответствующими векторами-столбцами поисковых матриц. Выдача требуемой информации производится - в соответствии с получаемым производным вектором-столбцом и ключевым доменом.

12. Предложенная концепция и разработанные модели и алгоритмы аппробированы в спроект1фованной и внедренной системе "Кадры высшего учебного заведения (Кадры-ВУЗ)"для факультета автоматики и вычислительной техники Азербайджанского Технического Университета на языке СИ для IBM PC/AT. Система оказалась эффективной с точки зрения обработки сложных и составных запросов. Она отличается достаточно дружественным интерфейсом и может тиражироваться.

Основные содержание диссертации изложены в следующих расютсх:

1. Ш.Н.Шахбазова. Исследование универсальных и специализированных баз данных и выявление общих процедур логического проектирования. Тезисы докладов vi республиканской конференции аспирантов ВУЗ-ов, АзГО1, Баку, 1983, с. 75-77.

2. И.Н.Шахбазова.Вопросы автоматизации логического проектирования специализированных баз данных. Тезисы докладов VI республиканской конференции аспирантов ВУЗ-ов, АзГШ, Баку, 1983, с.78-60.

3. Ш.Н.Шахбазова. Структура информационно-советующей системы для управленческого персонала. Сборник научных трудов АзГШ, Баку, 1938, с.21-23.

4. Ш.Н.Шахбазова. Генерация подбаз данных из нескольких объекто-орпентированных баз для дистанционного информационного обеспечения оперативного управления. Тезисы докладов VII республиканской конференции ВУЗ-ов, АзГШ, Баку, 1984, с. 8.

5. И.Н.йахбазова. Интеллектуальная информационно-советующая система для управления научно-исследовательскими работами. Тезисы доклздов республиканской научно-практической конференции молодых ученых, Фрунзе, 1989, с. 100-101.

6. Ш.Н.Шахбазова. Основные концепции построения инфоумацискно-советующей системы для управленческого персонала. Всесоюзная конференция по искусственному интеллекту. М.,1988, с.523-527.

7. Ш.Н.Шахбазова. Чнформационно-советующая система, построенная на базе ¿base iii Pius. Сборник научных трудов АзГШ. Баку, 1991, с.92-94.

8. Ш.Н.Шахбазова. Языковые средства генерации подбаз данных систем информационного обеспечения. Сссргаш научных трудов АзПИ, 1988, с .18-21.

9. Ш.Н.Шахбазова. 1Гнформащюш=о-спрарочная система "Деканата" в системе dBASE IV.Тезисы докладов всесоюзной научно-технической конференции. Фрунзе, 1989, с.21-23.

10. ШЛ!.Шахбазова.'Основные концепции построения информационно-советующей системы организационного типа. Материалы XI Республиканской конференции аспирантов ВУЗов Азербайджана,АПИ, Баку, 1988, с.206.

11. Ш.Н.Шахбазова. Языковые средства информационно-советующей ■ системы управления наукой и .техникой. Тезисы докладов республшсанской научной конференции молодых ученых.АзИСИ,1989,

с.18-21.

12. Аскеров Т.Н., Абидоь Ч.Д., Ш.Н.Шахбазова.Подсистемы "Сессия" и "Стипендия" в информацшшо-справочной системе "Деканат". Сборник научных трудов АзПИ,1992, с.14-17.

13. Ш.Н.Шахбазова. Автоматизация планирования . подсистемы "Учебный план" в информационно-советующей системы "Деканат". Ученые записки АзТУ, 1992 (в печати).

14. Ш.Н.Шахбазова.Подсистема "Учебный план" в автоматизированном рабочем маете "Деканат".Сборник научпих трудов АзГШ, 1991, с.9-12.

15. Т.Ы.Аскеров, Ч.Д.Абидов, Ш.Н.Шахбазова. Физическая модель бази данных, обеспечивающая динамическую независимость и эффективность выполнения процедур обработки данных в микроэвм. Известия АН Азер-на, серия технических и физ-мат наук, выпуск "Информатика", том ху М-2, 1995,стр.74-82.

16. ШахбазоЕа jJ.il., Аскеров А. Р., Алиев А. А; Искусственный интеллект ба1жа данных для управления наукой и техникой в республиканской автоматизированной системе управле-зш (РАСУ), Сборник научных трудов АзГШ, 1989, с.78-80.

X Y Л A G 9

ДпссзртЕсаЗа иил диалог рег^пллдэ жпексиз кстснзр одунан во Ест^Задвчилзрян t.iïpEic.sO мзнтиги arrapa пэртлзринз асаевн бэЗук bs«5ira ин®0Т2дасиЗа кютеьспггэз ?элвб одуная вэралэнлэрлэ тэ"гая одс2 рзл^сслЗа ташп дината: геЗри sctirs взрялзнлзр базасыяан estnaajsrara с!илз-есеосязтзз фазшш шдзлгикн тэдгига вэ сштбзшз мер слункупдур. !.'одол чохесгпктли Ессссиатпэ ахтар-цп толзблэрпнл (aznapss jsjmss в-тауэтларин гзргнлшуэ гкргазмэгли элагзлзряна езуцдз экс бтозрзн структурда 'Епаралдагнддаз)9дэ^эргк емэлп сгсгелиэрдэ шггзесез Ззр'нз зетаралза "jeн!îл^;та!p?.:з",т'J•эpлззд;^p^'з', вэ "хзнаряошдору.а" емолларзшш кчрасы s<sî3eh зщешЗЗзгсззллЗа Т0"К2Н ОДГШ. ЗЗЗИЗЗЭХЯЗрЗЕ 733-183 зергкласы тзчрубэдз

кеняя нсткфздз олунзн ролЗасиЗз гипли гзрилгглзр Сазаларцна кс олгн чзьотдпр вэ ояягрнн зрадаи галдзрнд??"са учун курзккзб, чол зкзк вз ЕЗСС2ТКН сэрфани тзлеб о два олаза прогрев згеитэдвршздзя Естк*здг олупур. Твгдам олунак кодэлдо псэ- бу, вэрллзнлзрпн Защада yjpya Ззрлездаршггса вэ кэвгэлк кодлазд^ла Еэбвкэдзрп консзпсазасындап цсигйдз Золу илэ арадад кетурулур.

SUM11AEY

This dissertation is dedicated to synthesis and application of dynamicaliy independent operationally associative physical aodel of database without anoirily operated in сjnversational mode uith intensive using of datas got as result of processing of complexly los»ca.l enquiries.

Database is contain froa great volume of information that is organized uith installation of coiaplicate-logical connections. Tao Kodol 13 realizing nultyaspect associative searchs executed uith high ratin (a search is executing uith aanipulation only uith atructura■that contain ohe-to-one rulations of attributtes) uith cultiply U3Sd of "update", "delete", "insert'' procedures. At that tias> ii supporting a database";* consistency.

Л riso of inconsistencies is typically to the widely used relational 'databases and to renove that are used required considérai-Is tine and difficulty complicate softuare.

In suggested aodel that detect is reiaove by the uay 01 corresponding organization - of nultiply attributes associative structuro uith usinb the conception of logical scales of positional coding. ■

Заказ ¡31. Тираж ¡00. Бесплатно. Тип. АГ'ПУ. им. II. Туси. Баку, ул. Уз. Гаджибекова, 34.

Бесплатно

Азэрба)чан Елмлэр Акаде.уц^асы Кибернетика Институту

Эл]азмасы Ьугугунда УОТ 681.5.015

ШАЬБАЗОВА ШЭЬНАЗ НАДИР гызы

РЕЛЛАСИЛА ТИПЛИ ВЕРИЛЭНЛЭР БАЗАСЫНДА ДИНАМИКИ ГЕЛРИ-АСЫЛ ЫЛЫРЫ ТЭ'МИН ЕДЭН АНОМАЛ Л АСЫЗ ЕМАЛЫН ЭМЭЛИ—АССОСИАТИВ ФИЗИКИ МОДЕЛИ

Ихтисас: 05.13.14 — Информаси]анын ишлэнмэси вэ идарэетмэ системлэри

Техника ел.млдри намиззди алил1лик дэрэчэси алмаг учун тэгдим едилмиш диссертаси)анын

АВТОРЕФЕРАТЫ

БАКЫ — 1995