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

- ^ ч

Го

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

БЕЛОУСОВ Алексей Л&онидозич

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

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

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

Пенза 1999

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

Научный руководитель: д.т.н., профессор Линьков В.М-Официальные оппоненты:

доктор технических наук, профессор Левин В.И.? кандидат технических наук, доцент Мякишев Д.Б.

Ведущая организация: Пензенский научно-исследовательс электротехнический институт.

Защита состоится «» ЗМ^ЫУ-ЬЛ^ 1999 г., в часов,

заседании диссертационного совета Д 063.18.02 в Пенэенс

государственном университете по адресу: 440017, г. Пенза, Красная, 40, ПГУ.

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

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

1998 г.

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

диссертационного совета / Шашков Б.Д.

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

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

Актуальность работы. В последние годы значительное внимание еляется решению вопросов, связанных с проектированием систем раьления данными, которые работают с большим объемок хранимой формации. В связи с этим важной задачей является поддержание ожной структуры системы эффективной обработки различных запросов, этому при проектировании систем управления данными необходимо тать вопросы поддержания целостности информации, устранения быточности данных, повышения общей производительности системы. шение этих задач позволит сократить объемы используемой памяти, высить скорость обработки запросов, обеспечить высокий уровень |СТоверности информации, защиту от несанкционированного доступа. При ■ом для улучшения этих характеристик системы применяется несколько |Дходов, для которых, разрабатываются оптимизаторы запросов. |фективность системы в целом во многом определяется качеством [стемы оптимизации запросов. Во всех существующих направлениях, ¡язанных с оптимизацией, остаются нерешенные проблемы. Большинство i них имеет переборный характер и требует развития эвристических ¡шаний.

Другая специфическая проблема оптимизации запросов и структур >анекия и стратегий доступа относится к системам управления базами 1ННЫХ в оперативной памяти. Такие системы становятся все более стуальными в связи с постоянным увеличением объемов доступной в ЭВМ 1еративной памяти и ве удешевлением.

Проблемы, связанные с эффективной обработкой запросов и систзмах травления данными, рассматриваются в работах отечественных и ФУбежных специалистов в области проектирования баз данных {Д. гйер, К. Дейт, Д. Ульман, С. Кузнецов к др.). ' Линьковым З.М. осматривалось применение нумерационных методов для решения задач ЬФективного хранения и управления данными. Использование монотонных гображений в нумерации дает возможное. производить интервальные ¿числения над числовыми номерами для эффективной обработки данных..

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

семантику при работе с данными, решить вопросы организа) эффективных методов хранения и доступа к данным.

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

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

Задачи исследования. Для достижения поставленной цели решаю-следующие задачи: , ■

1. Разработка формальной модели базы данных на основе домеш ориентированной структуры системы с использованием нумерациош методов.

2.Разработка методов преобразования запроса в интервалы уравнения.

3.Разработка механизмов применения нечетких интервалов 1 оптимизации процесса обработки запроса.

4.Разработка эффективных методов решения интервальных уравнен»

5.Разработка архитектуры системы управления данными на осн< интервальных вычислений и методов проектирования СУБД.

6.Разработка алгоритмов реализации функций обработки запросе* системе управления данными.

Научная нови&на.

1.Обосновано применение нумерационных методов для повыше! эффективности обработки запросов в системах управления данными.

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

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

4.Для повышения эффективности в использовании ресурсов ЭВМ I обработке запросов предложены методы, основанные на работе нечеткими интервалами.

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

Основные результаты я положения, выиосимыа на защиту:

1.Внутренняя модель данных в виде совокупности бинарных ношений.

2.Метод преобразования реляционной модели во внутреннюю модель иных.---------------- ------------------------------------ - ----------------------------------

3.Методы преобразования запросов, представленных в виде гдиката, в систему интервальных уравнений.

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

5.Метод применения показателя нечеткости для оптимизации пользования имеющихся ресурсов.

6.Архитектура системы управления данными и алгоритмы поиска вета на запрос, позволяющие эффективно использовать предлсжонкук дель ,данных.

Практическая ценность заключается в следующем:

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

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

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

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

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

-на II международной конференции "Новые информационные хнологии и системк" {г. Пенза, 1996);

-на Международной методической конференции "Университетское разевание в условиях формирования рыночных отношений (г. Пенза,

97г.);

-на научно-практическом семянаре "Применение баз данных" (г. нза, 1997);

-на всероссийской научно-технической конференции "Непрерывная и яжные логики в информатике, экономике и социологии" (Пенза, 1997).

Реализация работы. Основные результаты, изложенные р ссертационной работе, использованы в НИР, проводимой в рамках анта «Доменно-ориентированная нумерационная система управления

Сазами данных» программы «Конверсия и высокие технологии. 1997-2( гг.». Кроме того, результаты работы использованы в Щ!Р, выполнен! для КПФ "Пензснаб" (г. Пенза) и РКК "Энергия" (г. Москва) и внедреь -в автоматизированную информационную систему "Пензснаб", > подтверждено соответствующим актом;

-в автоматизированную обучающую систему для кафедры спортив] игр ПГПУ, что подтверждается соответствующим актом.

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

Copyicvypa и объем работ. Диссертация состоит из введения, ti глав, заключения, списка литературы из 83 наименований и д: приложений. . Работа содержит 142 страницы текста, 7 рисунков, таблиц, 7 страниц библиографии, 8 страниц приложений.

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

Во введении • отражены: актуальность темы, цели и зад диссертации, новизна И практическая ценность полученных результат структура диссертации и положения, выносимые на защиту.

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

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

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

leKCHbte файлы, в системе ADABAS - инвертированные файлы. В ADABAS 1иси хранятся сжатыми, в виде строк .байтов переменной длины.

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

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

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

Вопросы оптимизации запросов актуальны в распределенных ляционных системах, а также . в системах с использованием огопроцессорной архитектуры (Informix, 0ra.cle7). В этих системах обкодимо решать комбинаторно сложные проблемы обеспечения свтабируемости .и уменьшения числа элементов, участвующих в запросе.

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

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

Пусть имеется реляционное от!'о<аеиие г со схемой Atri,...,Atr„) . .Каждому имени атрибута Atrt ставится б соответствие южество D1( называемое доменом атрибута Atri, i<n. Домен атрибута

Atri будем также обозначать как doa(Atri) (dam: {Atri}->{Di}) . Доме являются произвольными непустыми конечными или счетными -множествами

Дпя построения внутренней модели предлагается выполни уникальную идентификацию кортежей отношений в БД. С этой цел рассмотрим множество отношений В в реляционной БД и постро уножество кортежей Е путем объединения кортежей отношений г БД:

E = \Jr

гшВ

Для множества кортежей вводится нумерация V:

v: Н0 -> Е, где No - номерное множество.

Таким образом, каждый кортеж в БД,' получает уникальный номе Генерация уникальных номеров для включаемых кортежей являет функцией системы управления данными. Номер кортежа следу рассматривать как внутрисистемный ключ кортежа отношения.

Значение любого атрибута в кортеже зависит от ключевых значен кортежа, то есть от его внутрисистемного номера (ВСН). Таким образо имеет место ряд функциональных зависимостей для каждого атрибута:

А±: Н0 Di Aj: Ко -» D],

Исходя из этого, каждому атрибуту можно сопоставить бинарн отношение. Тогда БД Судет представлять собой совокупность бинарн отношений:

В {Ах,А2,._, Atol»

где n-число атрибутов в базе данных.

Наряду с нумерацией кортежей предлагается выполнить кодирован значений кортежа путем замены значения его номером.

Пусть D = |D¿, D2,...,Ba). Зададим для каждого множества нумерацию вида:

Vi.: Щ -*■ Di, где B¿ - номерное множество.

Нумерация Vi определяется так, чтобы задать монотонн отображение ¿тожества Hi в Di , т.е.

n* i щ о Vi(nx) <, Vilny), пж, Пу е Ni.

Таким образом, пронумерованные домены можно рассматривать как сношения Ко!, которые представляются как множества кортежей: {<пх, <1> 1 ¿ей!, пх е М1, V! (пх) = с!).

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

Тогда модель внутренней организации связей будет иметь вид: н =■ <3, , v, уо, £>,

где У0 - {V! | ,

Э - множество бинарных отношений 3={31.|1еХ}, Э!» 1<в£, П1>1(УМ{П1) е 01) и (у(в!) е Е)}, £ - набор теоретико-множественных операций.

Рассмотрим отображения 5 и 8"1, позволяющие соответственно из гношений.Г! сконструировать {в^и наоборот:

5: В ->Т(3) , 8 "1: Т(3) В,

Т(3)- система подмножеств множества бинарных отношений Э.

Номер кортежа з однозначно определяет значение каждого атрибута энного кортежа. Поэтому имеет место функциональная зависимость

£: в пь,

где Уп (пн) * йк, <1* е О* и атрибут с номером имеет область начений О*.

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

Суть операции 5"1 состоит а том, что для каждого атриСута ортежа с номером а в отношении находятся кортеж!! {э, п), затем

для каждого атрибута с о&пастыэ значений Di по номеру п, испол! нумерацию v^. ; восстанавливаем его значение d.

С использованием 'нумераций Vm. мы можем получить еще функциональных Зависимостей:

Vi * В±,

которые каждому номеру кортежа ставят а соответствии ВСН атриб; причем операция hi" является композицией операций

Рассмотрим пример преобразования стандартной реляционной moj в предложенную бинарную модель.

Пусть имеется отношение: «Студент» (таблица Г), Таблица 1. Отношение '.«Студена»

» ФИО ст-та Год рохц. Пол Группа

1 Иванов 1974 М 91Ф2

2 Петров 1973 м 90ФЗ

3 Сидоров 1962 и 84Е1

4 Кривошеее 1968 и 84Е1

'5 Андриянова 1967 ж 84Е1

6 Сидоренко 1968 X 84Е1

7 ' Ревунов 1971 м • 90ФЭ

8 Матросов 1973 м 90ФЗ

Первая колонка - номер кортежа - в традиционных реляцио) отношениях не используется и введена для удобства нумерации связе{ Введем домены для данного отноше!

Йемен «Фио» (Ох)

ВСН | МО

101 Алексеева

102 Андриянова

103 Борисов

301 Иванов

302 Кривошееа

303 Куроедов

304 Матросов

305 Петров .

;..

500 Ревунов

501 Сидоренко

502 Сидоров

Домен «Название группы» (D4)

ВСН На паяя*

грушш •

...

500 84Е1

...

600 90П1

...

1001 90ФЗ

...

1500 91Ф2

...

ген пол

0 ж

С использованием нумераций составляются таблицы сзязей:

Сви^ь Студент-ФИО

Связь Студент - Год рожд.

!!> Кортежа ВСН ФИО

1 301

- 305

~> 502

4 302

5 102

6 501

7 500

8 304

язь Студент - Пол

№ Кортежа Пол

1 1

2 X

3 1

4 1

5 ' 0

6 0

7 1

8 1

№ Кортежа Год рожд.

1 1974 !

2 1Э73

3 1962

4 1063 '

5 1 1567

о 1968 |

7 1971

о ( 1573

язь Студент - Группа

№ Кортежа Группа

1 1500

2 1001

3 500

4 500

5 500

6 50С

^ 1001

8 1001

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

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

Введем определенный набор символов операций О, принятый в рассматриваемой информационной системе.

Множество П включает в себя

а ш { + , - , * , / , * , > ( < г >, <, V. з,

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

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

-определение интерзалов возможных значений I(Dj.) переменных, входящих в запрос;

-преобразование системы интервалов I(Di) в систему числовыг интервалов I{Ni), используя нумерации vBi;

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

-решение интервальных уравнений относительно систем интервале! * (Hi) и получение нового множества интервалов I'(Кх);

-определение множеств кортежей I для интервалов I' (Ni('

каждого атрибута, которые удовлетворяют соответствующему условию j предикате;

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

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

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

Будем рассматривать множество возможных значений R как частичн упорядоченное множество, на котором задан линейный порядок < Элементы множества R будем обозначать строчными буквами а...г. Определим на множестве R понятие замкнутого интервала I - [а,Ь] = { хеК I .

Множество всех замкнутых интервалов в R обозначим через I <й) Всякое вещественное число х из R может считаться особым элементом к X (R), имеющим вид [s.s:] .

Два интервала А и В называются равными (записывается А=3), ест они равны в теоретико-множественном смысле. Для замкнутых интервале и B=[bi,b2] из определения равенства следует: А=В <=> а1=Ы, а2=Ь2.

Наряду с замкнутыми интервалами существуют открытые полуоткрытые интервалы:

Ii в {а,Ь] = | а < х S Ь, а,Ь, <= D ) , •12 " [а,Ь) = {х | а i х < Ь, а,Ь е D ) ,

13 я (а,Ь) » {х | а < х < Ь , а,Ь е D ) .

ДЛЯ- открытого (полуоткрытого) интервала всегда можно указать ¡амкнутый интервал, содержащий все его элементы.

Одним из этапов реализации запроса является вычисление области ¡начений-переменных, входящих в запрос. Эта задача может быть сведена : задаче представления запроса в виде интервальных уравнений. -Решение этой задачи состоит в вычислении по исходному предикату P(xlf х2, ■ . . , ::„) соответствующей системы интервалов.

Рассмотрим переменные а и Ь, которые имеют одну и ту же область возможны:: значений D. Область значений этих переменных сарактеризуштся некоторыми интервалами I, и 1ь из D. Предикат ¡?(а,Ь) вкладывает дополнительные ограничения на области значений ■¡временных. Обозначим интервалы, при которых предикат истинен, I'. и с'ь, I'» Sl« , I'bS Наряду с операцией вхождения е определим

отношение < на множестве интервалов:

I, < 1ь « (inf{I.) < inf (Zb))S(sup(I.) < sup<Ib)),

где I« , 1ь в I (D) .

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

- для предиката а < t,t-KOHCiaHTa:

I', = I. П (in£(D) ,t] :

- для предиката а i Ь:

(1,,еслл1, <1„ или1, £ib, 2' а * <1, П1(..если1( <!,.

|iinДТ,).sup(I„)],еслиiь с 1г,

(1Ь,если I, <1Ь или Ibsl„

I'b в |l.nit ,есяи1ь <1,.

[[infflJ.suptfJl.eciml,

. Для интервалов I'. и 1'ь в последнем случае в системе происходит сужение области значений переменных, удовлетворяющих запросу. Но полученные интервала не означают, что для каждой пасы

<а,Ь>, такой, что ае Г, и Ье 1'ь , предикат a i Ь будет истине: Для нахождения номеров кортежей, удовлетворяющих запросу, необходи! для каждого кортежа, в котором значение а принадлежит интервалу I'

проверить истинность условия (Ье 1'ь) и (а£Ь).

Рассмотрим, как вычисляются области значений переменных предикатах, содержащих операции конъюнкции и дизъюнкции: Pi (a) S Р2 (а).

Пусть Ji и Jj - области значений переменной а в предикатах Pi Р2 • Тогда интервал l'a вычисляется следующим образом: ajain * max{in£(Ji) ,lnf (J2) l, ащах ш ain{sup(Ji) ,sup(J2) } ,

* |0, a > a ,

' mm ma*'

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

Рассмотренные выше преобразования ориентированы на переменные одной областью значений. Однако реальные информационные систе! характеризуются несколькими областями значений предметных переменны;

Для более эффективной реализации запроса следует (где э' возможно) привести запрос к запросу с разделенными переменными: Г[Х1,Х2,.:.,ХВ) - Pi(xx) в Р2(*а)в...вРв(хп),

где вместо символа в можно подставить операцию конъюнкции(ву и. дизъюнкции(v).

Приведем примеры- запросов, приводящиеся к запросам разделенными переменными:

-Pi(xi)S(Pa(Xi)vP3(x2)) .

Если выполняется условие Pi(xi) 6P2(xi) »FaJ.ee, то исходный 3anpi можно преобразовать в эквивалентный запрос с разделенными переменны Pl (Xi) « Рэ <Х2) .

-PitxiWtPnxOHMxj)).

Если Pi (xi) vP2 (xi) ^Тзп20, то исходный запрос эквивалентен запро с разделенными переменными Pi(xi)v Р3(х2).

Как было сказано ранее, при использовании интервалы® вычислений задача поиска на заключительных этапах состоит

нахождении пересечения и объединения интервалов Однако в некоторых случаях из-за ограниченности- имеющихся ресурсов или с целью оптимизации процесса обработки запроса спя-дует использовать покрывающее множество интервалов, которое содзржит- меньше элементов. Возникает задача: перейти от - множеств« интервалов {I), удовлетворяют-.« запросу, к покрывающему множессау tr9}'-,, такому, что {1} £{1®}. Во множестве {I®} будут находиться значения, которые не удовлетворяют запросу. Будем называть систему интервалов правильной, если все значения в этой система удовлетворяют запросу. В противном случае система интервалов называется неправильной. Для неправильной системы интервалов, на.заключительном этапе необходимо для каждого ее элемента осуществить проверку, удовлетворяет ли он- исходному запросу. Для эффективной обработки запросов для каждого, интервала вводится числовой параметр р, показывающий, какая часть элементов интервала удовлетворяет запросу. Этот параметр равен единице, если все элементы интервала удовлевворяят запросу, и нулю, если не один элемент не удовлетворяет запросу.

Пусть имеются, два правильных интервала а2] и B=[bi, Ь2] с

параметрами р* и ра, равными единице (это означает, что все элементы этих интервалов удовлетворяю* запросу), причем

ajS biS Ь2.

Составим покрытие этих интервалов одним интервалом С таким, что {А, В)сС, С= 1аг, Ъг1.

Если nj^bi, то не асе. элементы интервала С удовлетворяют исходному запросу. Поэтому введем характеристику рс для интервала С, применяя геометрическое определение вероятности (отношение длины отрезков, который принадлежат элементы, удовлетворяющие запросу / (Ь2-»i>~ (bx - *j)/, к общей длине интервала С /(b2-ai)/):

Pc«l-{bi г. «г)/(Ьг-ai)

Вероятность рс показывает, что наудачу выбранный элемент интервала 6' удовлетворяет запросу.

Рассмотрим, как вычисляются вероятностные характеристики для операций множества Q над интервалами A®*»(A=[ai, а2] ,рА} и Е®я{В=[Ъ1(Ь23 ,Рв) :

" ' -пересечение: A®r> Be"JAr®, р*пв), Ра^г=Р**Рв-

-дополнение: данная операция с нечеткими множествами може привести к тому, что в конечной системе интервалов буду отсутствовать элементы, удовлетворяющие запросу. Поэтому необходим при реализации операций над интервалами перейти к эквивалентном выражению, в котором не требуется проводить операцию дополнения; -арифметические операции: р*.*рв>" -предикаты вида, а 5 1:, ^константа - р',»р,; -предикаты вида а 2 Ь , р' «=р'« и р'ь= Р'ъ-

Использование числа как меры появления элемента удовлетьоряющего запросу, дает возможность изменения стратегии поиск в процессе изменения вероятностных характеристик интервалов. Тале уменьшение вероятностной характеристики интервала до определенно!» предела может привести к решению о пересмотре этого интервала уточнения его вероятностных характеристик. Это позволит ускорит поиск путем уменьшений области перебора.

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

Рисунок 1 Структура системы обработки запросов

В данной системе связи между атрибутами хранятся отдельно от амих значений атрибутов.

Процесс обработки запросов в предложенной системе организуется ледующим образом. SQL-запрос поступает в систему обработки запросов.

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

На второй стадии производится преобразование условия запроса в • истему интервальных уравнений. При этом осуществляется обращение к истеме управления доменами с целью определения области возможных начений переменных, входящих в запрос. На третьем этапе роизводится решение интервального уравнения с целью суженая области оиска элементов, удовлетворяющих исходному условию. На четвертой тадии производится выборка интервалов номеров кортежей для каждого лементарного условия. При этом возможно создание покрывающих ножеств с целью повышения эффективности обработки. На пятом этапе роизводится пересечение/объединение множеств номеров кортежей, олученных на четвертой стадии. В результате находится покрывающее ножество для множества, удовлетворяющего общему условию. На аключительном (пятом) этапе производится Еыборка ■"правильных" лементов покрывающего множества и восстановление исходных значений трибутов путем обращения к системе управления доменами.

Интервальные вычисления могут применяться не только в редложениях запроса SELECT языка SQL, но и в других его командах, ак, в операции удаления элементов отношений DELETE и модификации :уществуюяг.1Х элементов UPDATE , как и в предложение SELECT, входит :лючевое слоео WHERE, определяющее условие выполнения соответствующей 'Перации. "

Б результате экспериментов была построена заянсимость времени >егкции системы на запрос от количества обрабатываемых атрибутов. Она меет линейный характер для Доменно-ориентированной системы, 'азработанной автором, и Относительно постоянный для !аписеориентированных систем. Сравнение разработанной системы с [меющимися СУБД показало преимущества .разработанных методов пси 1вализации запросоз определенных классов. Испольййвание в SQL-запросе

до пяти атрибутов обеспечивает более высокую скорость по сравнению с записеориентированной СУБД FoxPro.

В Приложении А приводятся основные функции, используемые при реализации системы управления данными на «основе интервальных вычислений.

В Приложении В представлены документы, подтверждающие внедрение результатов диссертационной работы.

ОБЩИЕ ВЫВОДЫ ПО РАБОТЕ

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

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

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

4.Для оптимизации использования имеющихся ресурсов ЭВМ предложен метод оптимизации, основанный на использовании нечетких' интервалов. Использование числовых параметров нечеткости множества позволяет гибко менять . стратегию поиска в зависимости от изменения эти* параметров.

• 5.Для применения предложенной модели разработана архитектура и выполнена реализация системы управления данными с использованием доменно-ориентированного подхода. Реализованы методы решения интервальных уравнений.

6.Использование независимых ' методов хранения и обработки шформации позволяет эффективно, применять интервальные вычисления для

Реализации запросов по выборке элементов БД.

7. Для оптимизации запросов предложены и реализованы на основе

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

элементов, участвующих в запросе, и, следовательно, область поиска. Сравнение разработанной системы с имеющимися СУБД показало ■феимущество разработанных методов при реализации запросов определенных классов. Использование в SQL-запросе до пяти атрибутов обеспечивает более высокую скорость по сравнению с записеориентированной СУБД FoxPro.

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

1.Белоусов А.Л. Применение электронных таблиц для преподавания и изучения экономико-математических моделей и методов//Тезисы доклада. Материалы международной выставки-конференции "Новые компьютерные технологии в учебном процесса и научных исследованиях". - М.: КАДИ, 1995г. ■

2.Белоусов А.Л., Линьков В.М. Применение электронных таблиц при решении статистических задач//Тезисы доклада. Материалы международней выстазки-конференции "Новые компьютерные технологии в учебном процессе и научных исследованиях". - М.:. МАДИ, 1995г.

3.Белоусов А.Л., Линьков В.М. Применение электронных таблиц при преподавании математических дисциплин. //Материалы IV Международной конференции-выставки «Информационные технологии в образовании». - М.: 1995г.

4.Линьков В.М., Белоусов А.Л. Применение электронной таблицы TELEC для преподавания и изучения .математических дисциплин//Тезисы доклада. Материалы VII Международной конференций «Применение новых технологий в образовании», 29 июня-2 июля 1996г., Троицк.- Фонд новых технологий в образовании «Байтик», 1996.

5.Белоусов А.Л. Применение интервальных вычислений для реализации запросов языка SQL // Новые информационные технологии и системы: Материалы II международной конференции - 4.1. Пенза, ПГТУ, 1996.- С.39-40. ;

6.Линьков В.М., Белоусов А.Л. Применение электронных таблиц для

решений математических задач. // Университетское образование условиях формирования рыночных отношений: Материалы Международн методической конференции - 4.II, Пенза, ПГТУ, 1997г.- С.136-138.

7.V.M.Linkov, V.N.Nedoshivin, V.V.Drozhdin, E.V.Ogurechniko A.L.Belousov, D.V.Majorov. The Intellectuel System of Automat Design of Schemes of Measuring Systems (SAPR SI). EAST-WE International Conférence INFORMATION TECHNOLOGY IN DESIGN EWITD'9 PROCEEDINGS, Moscow, Russia, 1996. n.66-68.

8.Линьков В.M., Белоусов A.Jî., Майоров Д.В., Огуречников Е.В Дружаев А.А. Применение доменно-ориентированного подхода п] разработке систем автоматизированного проектирования среде измерения с поддержкой временной семантики // Применение баз данны: Материалы научно-практического семинара. - Пенза, 1997. - С. 5-6.

9.Линьков В.М., Дрождин В.В., Майоров Д.В., Белоусов А.Л Огуречников Е.В., Недошивин В.Н. Принципы реализации домен» ориентированной методологии построения баз данных //Непрерывная смежные логики в информатике, экономике и социологии: Материа. всероссийской научно-технической конференции. - Пенза, 1997. - С.39.

10.Белоусов А.Л., Огуречников Е.В. Применение нумерационш методов для реализации запросов к информационной системе.с доменн< ориентированной организацией данных // Математика и информатик. Межвузовский сборник. - Пенза: ПГПУ им. В.Г Белинского, 1996.,с. 61 80.

11.Белоусов А.Л., Мокшанина М.А. Использование компьютера курсе высшей математики //Математика и информатика: Межвузовски сборник. - Пенза: ПГПУ им. В.Г. Белинского, 1996., с.113-116.

12.Белоусов А.Л., Долгарев А.И., Линьков В.М., Самуйлова С.1 "Решение ■статистических задач с использованием элёктронных таблиц' Учебное пособие/ Пенз. Гос. пед. ун-т им. В.Г.Белинского.- Пенз; 1996.- 44с.

13.Велоусов А.Л., Дружаев А.А., Иванцов М.А. «Применен! временных баз данных при многоэтапном проектировании сложш систем»//Сучасн1 проблеми математики: Матер1али м1жнародно1 науковс KOH$epe.4uii. Частина 4.- 4epHieui: Рута, 1998., С. 9-11.

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

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

БЕЛОУСОВ АЛЕКСЕЙ ЛЕОНИДОВИЧ

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

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

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

Научный руководитель: д.т.н., профессор Линьков В.М.

Пенза - 1999

СОДЕРЖАНИЕ

ВВЕДЕНИЕ........................................................ 4

1. СПОСОБЫ ОПТИМИЗАЦИИ ЗАПРОСОВ В СИСТЕМАХ УПРАВЛЕНИЯ

ДАННЫМИ „ ........................................................................9

1.1. Стадии оптимизации запросов. Логическая оптимизация................................................9

1.1.1. Алгебраическая оптимизация запросов................ 10

1.1.2. Семантическая оптимизация запросов................. 16

1.1.3. Выбор процедурных планов выполнения запроса........ 17

1.2. Физическая организация данных и оптимизация запросов........................................................24

1.3. Проблемы оптимизации запросов в архитектуре

клиент/сервер.............................................35

1.4. Использование параллельных архитектур для

повышения эффективности систем управления данными ........ 40

1.5. Применение систем управления данными при

работе с хранилищами данных (DataWaгehouse) ..............4 9

ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ......................................... 55

2. НУМЕРАЦИИ И ИНТЕРВАЛЬНЫЕ ВЫЧИСЛЕНИЯ В РЕАЛИЗАЦИИ ЗАПРОСОВ.....................................................56

Вводные замечания.........................................56

2.1.Применение доменно-ориентированной методологии

в реализации реляционных моделей данных..................57

2.2. Интервальные вычисления.............................67

2.3. Преобразование логических выражений в

интервальные уравнения....................................75

2.4. Нечеткие интервалы и операции над ними..............85

2.5. Преобразование логических выражений и

нечеткие интервалы........................................91

ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ......................................... 95

3. ОРГАНИЗАЦИЯ НУМЕРАЦИОННЫХ ДОМЕННО-ОРИЕНТИРОВАННЫХ СУБД...... 97

3.1. Организация системы управления данными на

основе интервальных вычислений...........................97

3.2. Организация хранения и обработки данных .............99

3.3. Алгоритмы реализации отдельных функций

обработки запросов выбора элементов БД..................105

3.3.1. Лексический и синтаксический анализ............... 106

3.3.2.Преобразование предиката в систему интервальных уравнений........................................ 109

3.3.3.Решение интервальных уравнений..................... 115

3.3.4. Выборка кортежей отношений........................ 119

3.4. Применение интервальных вычислений для

реализации других запросов языка SQL....................12 7

3.5. Анализ эффективности разработанной системы.........12 8

ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ....................................... 132

ЗАКЛЮЧЕНИЕ.................................................... 133

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ. ...............................................135

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ................................ 136

ПРИЛОЖЕНИЕ А. МЕТОДЫ, ИСПОЛЬЗУМЫЕ ПРИ РЕАЛИЗАЦИИ СИСТЕМЫ

УПРАВЛЕНИЯ ДОМЕНАМИ........................................... 143

ПРИЛОЖЕНИЕ Б. ДОКУМЕНТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЯ. ................................................. 148

ВВЕДЕНИЕ

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

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

становятся все более актуальными в связи с постоянным увеличением объемов доступной в ЭВМ оперативной памяти и ее удешевлением.

Проблемы, связанные с эффективной обработкой запросов в системах управления данными, рассматриваются в работах отечественных и зарубежных специалистов в области проектирования баз данных (Д. Мейер, К. Дейт, Д. Ульман, С. Кузнецов и др.). Линьковым В.М. рассматривалось применение нумерационных методов для решения задач эффективного хранения и управления данными. Использование монотонных отображений в нумерации дает возможность производить интервальные вычисления над числовыми номерами для эффективной обработки данных.

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

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

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

Задачи исследования. Для достижения поставленной цели решаются следующие задачи:

1.Разработка формальной модели базы данных на основе доменно-ориентированной структуры системы с использованием нумерационных методов.

2.Разработка методов преобразования запроса в интервальные уравнения.

3.Исследование возможностей применения нечетких интервалов для оптимизации процесса обработки запроса о

4.Разработка эффективных методов решения интервальных уравнений.

5.Разработка архитектуры системы управления данными на основе интервальных вычислений и методов проектирования СУБД.

6.Разработка алгоритмов реализации функций обработки запросов к системе управления данными.

Научная новизна.

1.Обосновано применение нумерационных методов для повышения эффективности обработки запросов в системах управления данными.

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

3.Предложены методы преобразования запросов в интервальные уравнения^ позволяющие эффективно решать задачу оптимизации запросов.

4. Для повышения эффективности в использовании ресурсов ЭВМ при обработке запросов предложены методы, основанные на работе с нечеткими интервалами.

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

Основные результаты и положения, выносимые на защиту:

1.Внутренняя модель данных в виде совокупности бинарных отношений.

2.Метод преобразования реляционной модели во внутреннюю модель данных.

3.Методы преобразования запросов, представленных в виде предиката, в систему интервальных уравнений.

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

5.Метод применения показателя нечеткости для оптимизации использования имеющихся ресурсов.

6.Архитектура системы управления данными и алгоритмы поиска ответа на запрос, позволяющие эффективно использовать предложенную модель данных.

Практическая ценность заключается в следующем:

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

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

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

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

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

-на II международной конференции "Новые информационные технологии и системы" (г. Пенза, 1996);

-на Международной методической конференции "Университетское образование в условиях формирования рыночных отношений (г. Пенза, 1997г.);

-на научно-практическом семинаре "Применение баз данных" (г. Пенза, 1997);

-на всероссийской научно-технической конференции "Непрерывная и смежные логики в информатике, экономике и социологии" (Пенза, 1997).

Реализация работы» Основные результаты, изложенные в диссертационной работе, использованы в НИР, проводимой в рамках гранта «Доменно-ориентированная нумерационная система управления базами данных» программы «Конверсия и высокие технологии. 1997-2000 гг.». Кроме того, результаты работы использованы в НИР, выполненных для КПФ "Пензснаб" (г. Пенза) и РКК "Энергия" (г. Москва) и внедрены:

-в автоматизированную информационную систему "Пензснаб", что подтверждено соответствующим актом;

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

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 83 наименований и двух приложений. Работа содержит 142 страницы текста, 7 рисунков, 25 таблиц, 7 страниц библиографии, 8 страниц приложений.

1. СПОСОБЫ ОПТИМИЗАЦИИ ЗАПРОСОВ В СИСТЕМАХ УПРАВЛЕНИЯ

ДАННЫМИ

1.1. Стадии оптимизации запросов. Логическая оптимизация

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

Обработка поступившего в систему запроса состоит из нескольких фаз [2]. На первой фазе запрос, заданный на языке запросов, подвергается лексическому и синтаксическому анализу. При этом вырабатывается его внутреннее представление, отражающее структуру запроса и содержащее информацию, которая характеризует упомянутые в запросе объекты базы данных, (отношения, поля и константы). Информация о хранимых в базе данных объектах выбирается из каталогов базы данных. Внутреннее представление запроса используется и преобразуется на последующих стадиях обработки запроса. Форма внутреннего представления должна быть достаточно удобной для проведения последующих оптимизационных преобразований.

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

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

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

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

1.1.1. Алгебраическая оптимизация запросов

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

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

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

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

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

Так, в [3] применяется следующий метод оптимизации при обработке квазиконъюнктивных запросов. Запрос вначале представляется в нормальной форме, а затем определяется запрос с минимальным числом термов. Тем самым можно минимизировать число соединений и декартовых произведений, необходимых при его обработке.

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

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

Если язык запросов основан на исчислении доменов или кортежей, то обычно производится перевод его на язык реляционно