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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ ИНСТИТУТ АВТОМАТИКИ И ПРОЦЕССОВ УПРАВЛЕНИЯ

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

Денисов Сергея Борисович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА СЙЗИЧЕСКОГО УРОВНЯ ДЛЯ ДЕДУКТИВНЫХ РЕЛЯЦИОННЫХ СУБД

05.13.11 - математическое и программное обеспечение вычислительных машин,- комплексов, систем и сетей

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

ВЛАДИВОСТОК-1992

Работа Еалолнзна в Института авзоматики и процессов управления Дальневосточного отделения РАН,

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

А. XI Гвильдис.

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

А. Л Синявский,

кандидат физико-математических наук Т. JL Гаврилова.

Еодудее предприятие: Институт прикладной математики

ДВО РАН (Етадавостох)

Згл-жа состоится " мл-fjr*. 1QS2 года в fü часов на ьаседании Специализированного совета К OOS. 30.01 в Институте автоматики и процессов управления .Дальневосточного отделения РАН по адресу:

690032, г.Владивосток, ул.Радио, 5.

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

Автореферат разослан "2/ ■■ ^¿¿Л/^сы-Я 1992 г.

Ученый секретарь совета к. т. н.

в. И. Коган

«41^(11 и '1

|

" 3 -

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

ЦИСС6р7«4КЙ

ДКтуп-дьнссть псоблрмы. Один из подходов к рвапкзздаи интеллектуальной обработки датегог яакттвгся п растрптш рялягаюякьсг СУБД включением дэдугост о :сг запросов. Тгмой подход позно-

дяет сочетать использование алторетиоа быстрого пошел данных, эффективную Файлоаул организация, что сус^етЕЭнгсо для научных БД. еп»ших бользой объем, с прнмэкеш^м г-еляц,''0ншг< языков для представления знаний.

В реляционных СУБД производительность зависит от реализации физического уровня, то есть о!" той части СУБД, которая отображает лсгичесга:е структуры представлэнгл ргдяц'икк:« дгюшх в физичесткз стругаури, храним.гэ в 5ВЫ. Известие, что ви соЕреыгншлг релэдган-

СУБД , ни их физические уровни т дл-'онстрируит высокой скорости при обработке Оольснх объемов инфор:.<«эдки, пезтеуу является актуальной задача создания выгокозф$?!СП1Е!гого физического уровня сбработ.'си реляционных двкннх, способного поддергивать дедукцию.

При ресепии этой гад ачл есзшс^-э? прсблз^л с? работ ют итерационных запросов. в которых результат пшожекнл реляционной операции является операндом для еяедук^й сазрсцин, т. к. с точки зрения физического уровня СУБД дедукция-гто итерационное запроси с высокой степенью вложенности. 05'."ж^ ежмзой а-зпрос к БД такхз может породить длинна цепочку итерационных запросов, что приводит к резкому увеличению гребни доступа ¡4 базе данных.

Рассмотрим состояние прсдле!.гл обработки итерационных запросов. Алгоритмы обработки основных р<?дяц>'.оиных операций мокко разделить на следующие группы (см. рте. 1):

- не использующие сортироеку и выполнят« запроси за время

2

С1 • N , где N - число строк в отггегешш;

- осковываюаиеея «а сорти^ги внполнякцие запросы за срекя 02+СЗ"^ 1ойМ;

- основквзкцнеся на цепочной алгебре.

В цепочкой модели данных объекты реляционной базы данных (мгновения и индексы) представляются на основе единой структуры данных, называемой цепью, а реляционные операции представляются в виде композиции цэпей (цепе-:!,о,'! формулой)• Эта модель позволяет быстрее строить индексы отнесения-результата по индексам отнопе-ний-ог.ерандсв, чем Бри традиционном' подходе, использующем для построения индексов сортировку. Эго особенно ваяно при итерацион-

число отрок Ь отнозониях Рис.1. Обработка отношений в оперативной памяти

число фрагментов Рис.2. Обработка отновзний ео внешней памяти

• - {i -

них запросах, где отноклэште-результат одного запроса может оказаться операндом в другом запросе и наличие индексов у поисковых атрибутов отношений-операндов существенно ускоряет выполнение з'ш-роса. Использование цепочкой модели данных в несколько раа умень-П19Т процессорное время обработки итерационных запросов по сравнению с другими реляционными. системам, и итерационные запросы выполняются в ней за время С4+С5*М, как это изображено ка рис. 1.

Все сказанное справедливо только для обработки реляционных данных в оперативной памяти (СП). Если яэ отношения не помешается в ОП, то главным фактором становится время доступа к внесшей памяти, на фоне которого выигрьпз по процессорному времени становится малозаметным. Традиционные организация данных и методы выполнения реляционных запросов требуют КЗ-F+K4-F*logF обращений к внешней памяти, где F - число Фрагментов отнесения, каждый из. которых может быть полностью обработан в OIL Цепочная модель позволяет прогнозировать использование Фрагментов отиосония при выполнении запроса, что , в свою очередь, позволяет предложить другу?) организации внескей памяти с характеристикой K1-F+K2-F2 обращений, которая хотя и ассимптотически хутгл традиционного подхода, но в некоторой начальной облзсти требует значительно ионьпяго количества обращений к внеагей памяти (см. рис. 2).

Для того, чтобы цепочно;! модель значительно превосходила традиционные физические уровни по быстродействии, ее реализация долина иметь такие параметры К1 и К2, при которых интервал (1,F0) покрывает реальный диапазон объема данных (для научных БД до десятков миллионов строк). Значение этих коэффициентов зависит от выбора структур хранения данных и методов доступа к ним. Поэтому актуальной является задача создания и исследования таких структур хранения данных и методов доступа к ним, которые обеспечивают быстродействие, достаточное для создания дедуктивной реляционной СУБД.

Цель» диссертационной работы является разработка, реализация и исследование высокопроизводительного физического уровня дедуктивной реляционной СУБД, ориентированной на обработку нзучяых данных.

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

критерии оценки быстродействия реляционной СУЩ

Основные аагзчц, реаэннда ааторси и кродставленныо в работе, следующие:

- исслодовшю влияние штодоё доступа на быстродействие реляционной СУБД при выполнении запросов, характерных для задач автоматизации научных исследований (АНИ);

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

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

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

традиционных методов.

Научная новизна диссертационной работы гаклачается в разработ-№ структуры представления реляционных дшшых посредством формальной внутренней модели, основанной на аятебро цэпей, и определении области применимости такой структуры для хранения больших обгэюв научной информации и и oiwoirnmnorc итеративного доступа к ней. Также разработаны и реализованы нэтоды выполнения запросов к ролл-ционной БД, обеспечивающие выеокуа производительность физического уроьня, достаточна для поддержи дедукции. Кроме того,показано, что возыогша такая реализация реляционных еапросов штодачм формальной внутренней модели, которая повышает быстродействие реляционной СУБД в несколько раз за счет умэныаэнкя количества оСра^ний к внешней памяти по сравнению с традиционными методами выполнения реляционных операций

Практической вначимостыо работы является соадание ь среде СШ ЕС ЭВМ базового программного средства построения реляционных систем - физического уровня, . обладающего большей скоростью выполнения операций алгебры отношений, чем е распространенных коммерческих реляционных СУБД (SQL/DS, INGRES и т. п). В качестве такого базового средства разработан и реализован реляционный метод доступа (РМД1, поддерживающий интерфейс в Еиде операций манипулирования данными и алгебры отношений. РЦД является основой реализации реляционной СУБД -ЮРД/ВМ, которая поддерживает язык запросов SQL и обладает дедуктивными возможностями. Реляционная дедуктивная ОУЕД /¡ОРД/ВЦ -является основой системного программного обеспечения Pent-

опального 0;:са1;0грсфичэс!Х!Г0 банка даккых по Тихому и Индийскому океанам, котор;$ входит в с;;сто;гу ухрозых центров дэнкых и фушсци-онирует на Екчпелителыгом центре ¡<ЛПУ ДБО РАН с 1985 года. Такл? систэт ЛОРД/ВД внедрена в рчдэ сычкцяггельиш: центсоз.

Апробация работ». Осиовиио результат» диссертационной рпботи докладывались на Бсессгапсж паушо-тэхннчэском семинаре "иоСп:.ы;ое программное обеспечеки9"(Калин1'.ч, 1989), на Созецаннк рабочеП группы Fr25 по проблемам и ииетрумонтг&::а :я.тогрэдии инфориацисн-ш систем Ксшгссии по каучиын вопросам БТ диадам:«! наук соцотран (Киев, 1989), на VII Всс-сокзпом совега<гкн "Азто^тпзапия управле-пив твхнячесгас.« сродсгсг-гс гтсследовпкш Шрового ' огаэаиа" (Калининград, 1989), на Eaeco^isofi 'ъхе^глтлссксй ппсле (На/сдка, 19£9), па Научкэ-техннческоЛ кколе "Iíqeu? информационные техноло-пш'ЧОдссеа, lQSü)', на Кокаународной кзн£>рэнцки "Обработка изоб-раго?н:й и л'^та-ш-юнн.1^ кссдвдопагпет (0:í.ra-Q0)" (Глгссибирск, 1990), на Всесоюзном соч^наро "Црогра»лшоо

обеспечение косых информационных хыпазопЯГ (?гзрь, 1991), на научных сеганарах в Г0;2!з, ВН'1И0Ч, '!ЛПУ.

ПуЗяггдиии. По !лтрр:злау пргг.?денно'Л работы опубаагапачо я печатных трудоЕ.

Структура и объем гугссостапии, Диссертация состоя? из введения, четырех глав, зшсяй'йшш, cri:c::а .тагер^тура, сод?рэт.т?гго 120 наикенозанг.Гс. Объем работы i:;5 страниц t/acr-oiiv-CHoro тс-ксга, в том числе 3 рисунка. б графиков и 1 тгблнца.

СОДЕРЖАНИЕ РАБОТУ

Во введении рассматривается рааз;;тне систем обработки информации и определяется место дедуктивной реляционной СУБД при разработке систем обработка информации для автоматизации научных исследования. Определяется роль Физичсского уровня при реализации хе-дустивной реляционной СУБД. 'Тор^лируются основная цель и задачи, поставлен»!;? в диссертации. Кратко излагается содержание диссертации по глазам.

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

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

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

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

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

- редкая модификация перЕичноЯ инфориацил, порученной- б результате измерений.

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

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

- иь.еет в качестве интерфейса язык запросов высокого уровня;

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

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

- обеспечивает быстрый доступ к члслоеой информации.

•е.. Провести теоретическое и экспериментальное исследование быстродействия физического уровня дедуктивной реляционной СУБД.-

Наличие программной систег<и, названной реляционны?.: методом доступа и удовлетворяющей перечисленным вьсе требованиям, позволяет разработчикам реляционных • СУБД основное внимание уделять созданию удобного интерфейса с пртсладньм: пользователями. РУД берет на себя все проблемы по поддерике БД и обеспечении быстрого выполнения итерационных запросов н эффективного доступа к реляционным данным.

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

Проанализированы основные методы доступа к данным, применяемых в реляционных СУБД, основанные па сканировании отноиений, кластеризации, .хешировании, индексации и сортировке. По^чьано, что pea-

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

В глчестзе математической и алгоритмической основ реализации физического уровня дедуктивной СУБД в:3рана цепочная модель данных. Использозалне цепочной модели данных а кеегалько раз уменьиа-ет процессорное врекя обработки гггерациояних запросов по (¡равнению с другими реляш:-ннь^и систо'.зши. Для представления реляционных данных посредстпом цэпошгоЯ модели били разработали эффективнее структуры хранения цепочных дашшх и метод доступа к ¡иг.', использующие прогнозирующие свойства цепочной модели.

РКЦ хранит цзпсчпыЛ аналог отпосоя'-гя по атрибутам (в одной . странице внешней пз.'яти - • элементы цепи, соответствующие элементам столбца отношения). Поатрибутное хранение вызнано тем., что в формулу цепочной алгебры входят цепи, одни из которых соответствуют атрибутам отношения, другие - индексам этих атрибутов. При выполнении цепочной формулы, соответствующей реляционному запросу, .желательно, чтобы в СП извлекались только те цепи, которые необходимы в данпил момент или в следующий непосредственно за ним.

Применение индексных ¡¿этодоз для пов>т!ен;:я быстродействия ограничено тем, что использование индекса для болыглх отношений при выполнении реляционных операций ведет к значительному увеличению числа обменов с Енешней памятью. Цепочные аналоги отношений и их индексов оказывается возможным разбить на Фрагменты так, что при выполнении цепочной формулы в • оперативную память будет считана только или почти только та информация, которая необходима. Тогда реляционная операция над отношениями отображается в множество опе--раций над фрагментами, размер и структура которых определяется размерами ОП и структурой БД. При выполнении операции над фрагментом обращение к каддой его странице происходит не более одного раза.

В третьей главе описывается программная реализация реляционного метода доступа Р1(Ц обеспечивает хранение и обработку объектов реляционной базы данных - отношений, индексов и подсхем. РУЛ поддерживает операции четырех типов: манипулирование объектами БД, манипулирование данными, операции реляционной алгебры и получение справочной информации.

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

основе рад реализован язык запросов SQL в СУБД ЛОРД/ВU. РОД поддерживает дедуктивное построение подсхем и берет на себя проблемы, связанные с выполнением запросов к реляционным данным.

Отношения и индексы в РОД хранятся е виде множеств корте л» й цепей (фрагментов). Каждый фрагмент является частью отношения или индексами этой части. Кортеж цепей представляет собой совокупность цепей с одинаковым числом элементов, причем каждая цепь соответствует либо части атрибута отношения, если кортеж цепей - фрагмент отношения, либо индексу атрибута огнопония, если кортеж цепей - фрагмент индексов. Над цепями определены операции цепочной алгебры (норма, транспонирование, инвертирование и умножение), поддерживаемые в РВД. Результатом цепочной операции является цепь.

Реляционный запрос, получаемый РМД, сначала анализируется с целый выбора метода, которым он будет выполняться. Основным в РЦЦ является метод цепочных формул. Однако в случае, если отноаения малы и запрос модно выполнить быстрее другим методом, например, построчным просмотром отношения, то применяется зтот альтернативный метод. Если реляционная операция'выполняется методом цепочных формул, tq сначала строится цепь, которая определяет операцию. Затем умножение этой цепи на кортеж целей исходного отношения дает корт о;.-; целой отношения-результата, а умножение кортежа цепей индекса исходного отношения на обращение этой цепи дает индекс отношения-результата. В ряде случаев получение индекса отнсеэнил результата быстрее произвести посредством сортировки. При выполнении реляционной опеоации посредством последовательного просмотра строк отношения строится отношение-результат и затем, если необходимо, индексы - отношения-результата посредством сортировки. - Возможность на разных стадиях выполнения реляционного запроса выбирать наилучший из разных методов его реализации позволяет РМД выполнять этот запрос быстрее.

Программное обеспечение РВД подразделяется на четыре уровня:

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

- программы, реализующие цепочные формулы (уровень цепочных формул);

- программы, реализующие цепочные операции (уровень цепочных операций);

- программы, обеспечивающие файловую поддержу цепочных опера-

. - и -

щгЛ и операция Ш1Шяу.£нроза:п{я ;;сл::!.1п - цэпочпуЗ ¡¿етод доступа.

Уровень цепочных операций сСеепочивгот' эффективное кяголи^ние транспонирования, инвертирования, яopiy, а та;сз ргалпяует насколько типов операция y?i;or:?:nrr? цепей. ПЬстяьку старость выполнения операций алгебры цепей является од.ч;2! га основных факторов, влкяг^м па процессорное .-зреет г'лголнег.тл запроса, то при реализации цепочных операций использован« быстрые регистровые операции.

Программы, составляла уровень цепочных формул, поддеркивсвт алгебраические операции над отношениями, а тсгсз упорядочение строк отношений. В результате выполнения лхйсй га программ создается отноптоние, являющееся, соответственно, либо результатом алгебраической операции, дгбо отсортированный исходным откоеэниэм. Каждая операция реализуется,' гсая правило, necKoibicinsi катода».®, причем не обязательно по цепочной формуле, ШЗор сотодз производится на основании предварительных оцешс. Метод язгяетса применимым, если есть псе данисе для его реализации (напртэр, для организации понсгл по индексу необходимо отот индекс кмзть). Пели применимы лесгалько »-отодоб, то предпочтение отдается тсь?. которого предварительная оценка является наилучшей. Предварительные оценки представляют собой арпф^от.т.'эские выражения я не требуя? существенных затрат врзгяни при выполнении операций.

Реляционная операция PROJECT реализуется в РМД двух париастах, которые принят1; и в друг::х рэлзачсиных СУБД. Отличие этих вариантов в том, что в пермм случае равные строки относенпя-результата (если они есть) на удаляется, а во втором - удаляется. 1Ьлнч"а двух таких случаев объясняется тем, что на практик очень чгсто удаление разных строк го является необходим.!, а определение разных строк з таблице и удаление их запишет в реализации много времени и ухудказт Еффекхивкасть СУБД. Первый вариант операции проецирования (без удаления равных строк) реализуется переписыванием в результат цепей, зздазае;шх нмзнак! атрибутов в операции PROJECT. Второй вариант реализуется программой сортировки-слияния, для которой в качестве элементов сортируемых записей учитывается тользео атрибуты, которые являются операндами операции PROJECT. Следует отметить, что операция проецирования в РВД шлет выполняться одновременно с любой другой реляционной операцией.

Операция SELECT реализопана вРЦД двуья методами. Первый метод аналогичен поиску в последовательном файле, то есть производится построчное сканирование отнокения с выборкой тех строк, которые

удовлетворяют условию,• заданному ц запросе. Этот метод используется, когда . условие выборки требует обязательного построчного просмотра таблицы, например, когда в условии необходимо сравнивать поля одной и той же строки, или когда отсутствуют индексы для поисковых атрибутов. Второй метод за:сличается в построен™ выбира»-е?эЛ цепи и затем, на ее основе, в получении результата цепочной формулой. Так как отношение представляется множеством кортелай цепей, то выборка производится отдельно для каждого из них.

Соединение отношений (JOIN) является наиболее трудоемкой реляционной операцией. РЫД под.цор;.-:вает два метода соединения: или по гартежам цепей или с использованием предварительной сортировки. Выбор метода соединения производится по критерия, оценивающему время выполнения операции каждым методом.

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

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

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

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

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

РПЗЛКЧКЫМИ мэтодаул.

Показало, что построение иадокса по цзпочясЛ произво-

дится быстрее, чем ссртг'розкой, !согдз Но < О, 2- ¡¿р«( 1с~11р-1), гдч !)о - число строк исходного отг.сгения, Ир - число строг, результата.

Проведено сравнение мэтодсв интервальной выборки дан:«':: по индексу и показано, что при традиционней организации кпд-жса потребуется просмотреть !•(Яр/Ко) страниц "зденеа, где I - ебцэе чголо страниц индекса. В Г?.Щ гэ д.тл этого потребуется просмотреть 1»п»1 п(}1р,!!о-1!р)/(2«Но) етуаг/лц, т.е. а ср«д«9»« в 4 раза иень^о.

Проявлен срзатаелышЛ ападкз :*з«~.7 сскоаиь?*ч методами соединения отношений, об'"":э кглохъзуздалс: в £ганческях урсз>>ях реляционных СУБД (па примере ¿тэкчесгаго уротня сс:*зйства СУБД фгр-Л! 1Ъй ^ЭТЕМ К, ЗОЬ/С", 012), утз-су соединения по цепочный формулам, регдюэпаяноч в КГ1, Пзрич Ь"?70дс«"с0&д1э:ен?ы стко-згпэт\, используемом в фяасргссюи ¿розпэ СУГД С'Ф5-^ 1ГМ, является последозатель-лый просмотр отногзнпЛ-глэрхдаз (иди гетод ваогагпк '^кдов), которыЛ захтдчастел в г.огзрг.С'1 срззпеп-ш всзх строк ссо-деи-.ш;.:.; ЕТср^ч ^л'С.гои ячляэтсд соодше!:!*.* ¡то ла-

дскеам. Сп заключатся з сраячэтт юкияптоп тдопсов соединяв? атрибутов. Если аздеэпти !Г!декса удовлзг-оггта ус-опта соединения, то 133л9(с?игся СООТВОТСТВУЗПЗ» стрс'я «сходных отнсгх-лнй для получения строки от!!сгс-гаш-рэзультт:а. Трзп'З метол основал к.а сортировке отношений по ссэ;;;шре>г:! гщкйугг.ч и аналогичен истоду, реализованному в РШ1 "зтодом в'т.одпен:-. I соединения отметаний, срав-иивгсыим с тремя аг-зиэнш"?: "¿толам:!, является создптэюгз по цепочным формулам. В рзооте сг ¿.".чва.чось количество ссэрзцпЛ чтенмя и записи страниц, требуем: длл кл1о;и:зппп ссеглтпеша каждом из этих .:;тодоз. Пг эдпол&галось, что соединяемые атрибуты имеют индекса. При пропедег.'.ш сравнения не учитывалась запись результата "о вн^иаплэ пглгть, так кэличгство Езп".еызае>глх при этом страниц является адд-лглвяой "снстзнтой для всех методов соэкгпоиия.

Пусть сбгем оазрагнБкоЯ памяти - Ь байт, размер стракгюи гнойной памяти - К байт, разиер элзмс-нта - Е Сайт. И пусть соединятся отношения и К.'. Отношение И п:.'еет Н1 атрибутов и !!1 строк, К2 - !.« атрибутов и N2 строк.. Результатом этого соединения пусть оу-дет отнои'ение РЗ, в котором ИЗ атрибутов. Одна строга отношения имеет длину (М>2)- Е, где 2»Е-размер заголовка записи, М-число ат-

рибутоз ь отьояакш. Тогда число обрадрниЛ к внешней памяти при соединении относаний R1 и R2 последовательным просмотром (Qn), по икде(х:ал{ (Q¡0, предварительной сортировкой (Qc) и методом цепочно формул (Од) будет соответственно: Qn=( (Ш+2) • Е/К) ■N1+C(Ш+2) • (КЕ+2) • Е) /(К- L)) • N1« N2 ; Qc-( Е/К) • (Ш+2) • N1 • (1+1ое Г( (Ш+2) E/L) • ЫЯ) + (Е/К) • (К2+2) • f¡"2• (1+log Г( (Ь2+2) E/L) • N21) ; Q¿*>( (4-E) /К) • N1+((Ш +2) E/K) • Kl, (1 - (L/( (Ш +2) • 2 • É • til)) • N1) +

((4- E)/i!)• íi£+ir¿x(((Ш+2)E/K) • «2,(i-(L/( (í.2+2)• 2-E«H2)) • K2) ; Qa»(2'Vi+fJ3/2)-i;2-(E/Kb( i?. E fU/LJ+(2 E/Lb mocl( N1, fL/(2<E)U) +

(2 • V2+K3/2) • til • (E/K) • ( [2 E ÍI2/LJ +(ÍT E/L). mod( N2, fL/( 2 • EЛ)) ;

Чтобы сравнить получзнныэ формулы, построим график зависимости числа обрадапий к страикщам внешней памяти от числа строк соединяемое отношений при слидуизпс значениях параметров: Ktl«6, 12-4, l»=4, К-4К6, Ь-4.6, L«llp, Nl«fI2. Выбор зпачеккй параметров основан па спыге использования СУБД ЛОРД/íü в океанографическом банка дан-иих. ¡ü гргфкеа видно, что метод цепочных формул в этом случае предпочтительней других до нескольких миллионов строк. Заметим, что график построен в логарифмическом касотабе, и небольшой "зазор" между KpKEür.ci соответствует большой разнице во времени. Таким образом, в результате диссертационной работы удалось предложить реализацию физического уровня реляционной дедуютвной СУБД, превосходящую по быстродействия сусэствуодие системы для диапазона объема данных до нескольких миллионов строк.

Доведено практическое сравнение быстродействия СУБД ЛОРД/Ш и СУБД SQL/DS и показано, что система ЛЭРД/М выполняет запросы, связанные с обработкой больших сбъамоз данных более чем на порядок быстрее, чем SQL/DS.

Основные результаты, полученные в диссертации:

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

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

- разработана и реализована программная система - РМД, являю-сдяся физическим, уровпэм дэдугсгивной реляционной СУБД;

- проведен сравнительный анализ старости выполнения реляцион-

10СЗ

10ЕС

10Е5

гтлти)

' ЮЕЗ

N2

а - МЕТОД ПРЕДВАРИТЕЛЬНОЙ СОРТИРОВКИ.* - ИНДЕКСНЫЙ МЫОД.

МЕТОД ВПОЖЕННЫХ ЦИКЛОВ, о - МЕТОД ЦЕПОЧНЫХ ФОРМУЛ. N1 = N2, М1=6. М2-Ч, МЗ=Ч. Е-Ч5. К = иК5. /.= 1М6.

ЗАВИСИМОСТЬ КОЛИЧЕСТВА ОБМЕНОВ ОТ ЧИСЛА СТРОК ПРИ СОЕДИНЕНИИ ОТНОШЕНИИ РАЗНЫМИ МЕТОДАМИ

пых операций посредством предложенных в работе методов и скорости традиционных методов;

- па опыте работы реляционной дедуктивной СУБД ЛОРД/EU в составе регионального океанографического банка по Тихому и Индийскому oiteauau показано, что применение реляционного метода доступа позволяет на порядок повысить скорость выполнения вапросов и скорость дедуктивных выводов в реляционных системах.

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

1. Гвильдис А. Ю., Денисов С. Б. и др. Исследование алгоритмов реализации цепочной алгебры как внутренней модели реляционных данных. - Владивосток, 1986. - 43с. - Препринт/ИАПУ ДБНЦ АН СССР.

2. Гвильдис д. kl , Денисов С. Б. Реляционный ыетод доступа в СУБД ЛОРД//Систекшое програшое обеспечение автоматизации научных исследований: Сб. - Владивосток: ДВНЦ АН СССР, 1986. - С. 169-162.

3. Денисов С. Б. Реализация реляционной СУБД на основе формальной внутренней модели данных// Всес. научно-техн. семин. "Мобильное программное обеспечение": Тез. докл. - Калинин, 1988. - С. 137-139.

4. Гвильдис А.Ю., Денисов С. Б. и др. Система..ГОРД как средство создания океанографических баш сов данных// VII Всес. совещ. "Автоматизация управления техническими средствами исследования Мирового океана": Тез. докл. - Калининград, 1989. - С. 31-32.

5. Гвильдис А. И., Денисове. Б. л др. Многоаспектное представление океанографической информации средствами СУБД ЛОРД// VII Всес. совет, "Автоматизация управления техническими средствами исследования Шрового океана": Tea. докл. - Калининград, 1989. - С. 33-34.

6. Денисов С. Б. Вопросы реализации физического уровня реляционной СУБД ЛОРД// Системное программирование и автоматизация научных исследований: СО. - Владивосток: ДВО АН СССР, 1989. -.0.46-51.

7. Асманов Е В., Вяткин С. К . Денисов С. Б. и др. Экспертная система реального времени для 8адач распознавания// Научно-техн. ек. "Новые информационные технологии": Теэ. докл. - Одесса, 1990. - С. 12.

8. Асманов В. В., Вяткин С. К., Денисов С. Б. и др. Экспертная система для задач распознавания//. Мзад. конф. "Обработка изображний и дистанционные исследования (0ИДИ-90)": Тез. докл. - Новосибирск, 1990. - С. 56-57.

9. Денисов С. Б. Реализация физического уровня дедуктивной реляционной СУБД на основе формальной модели данных// Всес. научно-техн. семин. "Программное обеспечение новых информационных технологий": Тез. докл. - Тверь,1931. - С. 112-115.