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

Нго Тхань

Хунг

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

МЕТОД ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ДЛЯ РЕЛЯЦИОННЫХ СИСТЕМ ХРАНЕНИЯ И ОБРАБОТКИ ИНФОРМАЦИИ

Специальность 05.13.01 ~ Системный анализ, управление и обработка информации

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

1 2 ДЕК 200В

Ростов-на-Дону 2008 г.

003457760

Работа выполнена на кафедре «Программное обеспечение вычислительной техники и автоматизированных систем» факультета «Информатика и вычислительная техника» Донского государственного технического университета.

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

М.В. Гранков

Официальные оппоненты: д.т.н., профессор

В.А. Иванов

к.т.н., доцент В.В. Хашковский

Ведущая организация: Научно-исследовательский институт механики и прикладной математики Южного федерального университета

Защита состоится «1$ » декабря 2008 г. в «/ 2, » часов на заседании диссертационного совета Д-212.058.04 Донского государственного технического университета по адресу:

344000, г. Ростов-на-Дону, пл. Гагарина 1, ДГТУ, ауд. № 2S~2~-

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

Автореферат разослан «)?>» ноября 2008 года. Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим направлять в адрес совета.

Ученый секретарь диссертационного совета к. т. н., доцент Н.С. Могилевская

J/á*«^

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

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

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

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

Существуют три основных метода решения этой задачи: денормали-зация, горизонтальная кластеризация и вертикальная кластеризация. Вертикальная кластеризация является задачей ЫР-сложности и представляет наибольший интерес для научного исследования. По сути, этот метод является развитием классической теории нормализации, который также реализуется через декомпозицию отношений, но с учетом распределения частот требования атрибутов приложениями. Цель этой декомпозиции -повышение общей производительности приложений и производительности системы в целом. Эта проблема достаточно хорошо исследована в зарубежной литературе. К сожалению, на русском языке редко встречаются даже переводы зарубежных работ по данной тематике. Следует отметить, что в существующих в настоящий момент зарубежных работах рассматривается проектирование только систем распределенных БД. Но очевидно, что доля централизованных систем реляционных БД значительно больше, чем распределенных.

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

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

Для достижения данной цели необходимо решить следующие основные задачи:

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

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

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

4) разработать программные средства для экспериментального исследования предложенного метода вертикальной кластеризации и эффективности алгоритмов его реализации.

Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и систем БД, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, методы математического программирования и эвристические методы оптимизации.

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

1. Критерий оценки частоты кэш-попаданий для метода вертикальной кластеризации отношений при заданном потоке запросов и условии равной вероятности обращений к кортежам отношения, экспериментальная проверка которого установила, что оценка относительного отклонения от теоретического значения не превышает 2% с математическим ожиданием 0,1% и средним квад-ратическим отклонением 0,23%.

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

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

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

оценка математического ожидания отклонения от точного решения составляет 5%, а среднее квадратическое отклонение 1%.

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

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

2. Зарегистрированный в Отраслевом фонде алгоритмов и программ (ОФАП) "Программный стенд для исследования алгоритмов кэширования" позволяет исследовать частоты кэш-попаданий при кэшировании различных схем декомпозиции отношения. Зарегистрированная в ОФАП "Программа для вертикального бинарного разбиения отношений РБД" позволяет исследовать эффективность приближенного решения задачи декомпозиции отношения в сравнении с алгоритмом полного перебора.

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

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

• на XX Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-20), ЯГТУ, Ярославль, 2007;

• на XXI Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-21), СПУ, Саратов, 2008;

• V Spring young researchers' colloquium on database and information systems (SYRCoDIS V), Saint-Petersburg, 2008;

• на I международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2006);

• на II международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2007);

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского госу-. дарственного технического университета.

Публикации. Всего по теме диссертации опубликовано 16 печатных работ (одна в издании, включенном в перечень ВАК), в которых отражены основные результаты диссертации.

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

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

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

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

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

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

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

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

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

2. Выбор следующего ребра для рассмотрения. В случае, если при выборе следующего ребра для включения в линейный остов существует несколько ребер с максимальным весом, то приоритет отдается тому ребру, у которого есть новая вершина. Если суще-

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

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

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

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

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

Рассмотрим отношение Я с множеством атрибутов А, которые используются различными незчвисимыми приложениями. Для выполнения приложений кэш-системе необходимо обращаться к физической таблице соответствующего отношения и извлекать нужные им атрибуты требуемых кортежей. Таким образом, поток запросов приложений к кэш-системе можно рассматривать как последовательность троек(/?, Л,//)), где Я -

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

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

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

Предположим, что было отведено £л (байт) памяти для кэширования

отношения Л, которое декомпозируется на две проекции Л, и /?2 с множествами атрибутов А] и А,, соответственно. Общий объем кэш-памяти также рационально разделится на две части £,(1 и £/(2, каждая из которых служит для кэширования одной из проекций. Метод вертикальной кластеризации должен разбить отношения на две проекции и разделить общий объем памяти для их кэширования так, чтобы оценка доли кэш-попаданий была максимальна при заданном потоке запросов. Обозначим Л^, и МК2 максимальное число объектов отношений /?, и Л2, которые

могут быть помещены в кэш-памяти размером £Л1 и 1п соответственно.

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

Пусть К - первичный ключ исходного отношения. В этом случае имеем следующие утверждения:

• Л,иЛ2 = А, А1пА1 = К ; (1)

• не уменьшая обобщенности, можно считать, что А\ К ^ 0 и ". А,\К*0-, (2)

• исходный запрос (/?, А, Ю) будет полностью заменен по одному из трех следующих вариантов:

a) одним запросом (К,, Л п Л,, //)), если Л с Л,;

b) одним запросом (М2, /1 п Л,, /О), если Дс(/(2\А');

c) запросом (/?,, Лр Ю) и запросом (/?2, Л п ,/£>) ^ одновременно в остальных случаях (т.е. если

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

• отношение Я с мощностью N и множеством атрибутов А — ..,аи ], К - множество атрибутов первичного ключа отношения К, I =(/,,/,,... ,/д/) - вектор длин атрибутов отношения Я , где М - число атрибутов и А\ К ^ 0.

• множество независимых приложений Тг — с частотами их вызова {р^рг,...р0} и множествами требуемых ими атрибутов Д1,Д2,...,Ду, где р, + р2 + ... + р1, = 1, А, а А, V» = 1 -б ;

• Ь1( - размер кэш-памяти, отведенной для кэширования исходного

отношения 7?. Найти:

1) схему декомпозиции отношения Я на две проекции и К2 с множеством атрибутов А1 и А2 соответственно, где А,иА2=А, АхглАг=К, А{\ К Ф0;

2) максимальные количества кортежей ЫК1 и М1(2 отношений Л, и /?2, которые могут находиться в кэш-памяти, где

Кт-1т+К1П-11П<Ьк, 0<Ыт,Ы1П<М, и -

целые числа; 1К1, 1К2 - размеры кортежей отношений Л,, Я2. При этом найденные А{, Аг, 7Уу(| и должны обеспечить максимум частоты кэш-попаданий.

Рассмотрим получение оценки вероятности кэш-попаданий при кэшировании исходного отношения. Обозначим размер кортежей отношений /? через /,( и максимальное количество кортежей отношения Я , которое

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

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

N.

Г„ ==

где

Ык = пин

N

= 1111П

У/| О^А

(4)

(5)

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

г{в) = ^(г(в/с,)р(с\)). (6)

Для V = 1 исходный запрос (/?, Л, /£>) заменяется запросом

(/?,, Л, Ю) и А с /!,. В этом случае поиск кортежа (Л, Л, /О) завершится

успешно, если кортеж отношения Я{ с номером Ю присутствует в кэшпамяти. Таким образом:

р{В/С1)-

N

/л

N

где

/ \

111 ¡11 К,

[Л.

\ /

: 1)1111

и,

I

(7)

(8)

Из условия замены исходного запроса очевидно следующее выраже-

ние:

р{с,)= Е д.

Л, с .1,

Для 2, аналогично предыдущему, получим:

/

р{В1Сг) = -

где

/V,,, = нмп

А',

= ш т

I Р,-

V/] Л(с-.12

(10)

(И)

(12)

В случае / = 3 исходный запрос (Л, /), Ю) заменяется двумя запросами (Л,, ЛпА, ю) и (/?,, /1п(/13 \ А"), /О). Поиск кортежа (II А, /О) завершится успешно тогда и только тогда, когда кортеж отношения ^ с

номером Ю и кортеж отношения У?2 с номером Ю одновременно находятся в кэш-памяти. Таким образом, верно следующее:

р(в/с1)^р(в1сх\р{в1сг)^ ^

(13)

N ' N А/2 Из свойства полной группы событий вероятность наступления события Су вычисляется как

р(С^1-р(С\)-р(Сг). (14)

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

Р(в)=)+■^.р(с,)+.КС,). (15)

Если обозначить:

/'(с,)= 1

N Р(Сг)

N

I д;

V/| r.Jj

с =

N N2

— Е л;

(16)

_1_

iV2

1- S л- I л

Ч л,с/), V,| дл.л2

то формулу (15) можно переписать следующим образом:

(17)

'т '* яг •

Сформулируем следующую математическую модель задачи бинарной вертикальной кластеризации отношений:

1- I Pi

Ч V-Л,

f P{Al,A2,Nl(],NK2) = a-N Ь' Мнг +c ■ Nm ■ N K2 max, где,

^ r

a = ~~ pt; b=— ^ pt; c~—-

N Vij Л^Л, N V)| A(c. a2 N

с ограничениями:

А,<оАг=А, A,nA2=K, |Л,|>|К|; NKl "Ir\ + N1<2 ■lK2 < LK, 0 <Nm<N, 0 < NK2 < N ;

Nm ■> NK1 - целые.

(18) ' Z P<

Ч A, <4

(19)

(20) (21)

(22)

Задача (18-22) принадлежит к классу дискретного нелинейного программирования с четырьмя переменными А,, А2, Ит и Миг, в которых

А, и Аг являются ограниченными дискретными множествами, N 1<х и N - неотрицательными целыми числами.

В четвертой главе приводится оценка числа итераций при решении задачи (*) методом полного перебора. При этом решение реализуется в два этапа. Первый этап - это перебор вариантов бинарного разбиения отношения /?. А второй - перебор вариантов распределения объема кэшпамяти (МК1, Л/Д2) для каждого варианта разбиения. На втором этапе состав множеств А] и Л, известен и фиксирован. Задача второго этапа принадлежит к классу задач целочисленного нелинейного программирования и имеет следующий вид:

(**)J

<

p (N«.' ) = «,,„„ ■ N«, + Л....., • Л//(2 + с......■ Nm • NK} -> max (23)

где at„m(, c„m, - константы, вычисленные по (16) при фиксированных значениях переменных Ах и Аг, с ограничениями:

llirNRI+llt2.NK2<LR-, (24)

0<yV/;,</V, 0<iV,(2<jV; (25)

Nm, iV/(2 - целые. (26)

Для решения задачи (**) предлагается решить ее ослабленную задачу, получаемую отбрасыванием требования целочисленности (26). Ослабленная задача имеет вид: г

Р {Х,п , ) = асоп, ■ + Коп, ■ Х,п + ...... • • Х,п > max (27)

с ограничениями:

,Х R\ + ha 'Х R2 — >

0<Xin<N,0<X,a<N Решение ослабленной задачи (***) имеет вид:

(28) (29)

Хк. = 0,Хнг =min

/ L ^

I

V '/<2

, если X' <0;

X[<t = min

Y* Л/ -Л h

,Х.п = min

/ f -I у ^

Цзо)

\

,если X' >0

«2 ))

где А'* =

а -Ь с L"

"смш IMISI' , Г1-,«т/

/«2

2.с

А2 У

Если решение ослабленной задачи (***) является целочисленным, то оно является и оптимальным решением задачи-истока (**). Иначе можно установить нижнюю границу Ртш. для оптимального решения задачи-

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

[та\(0,п"п(д|, V,)),ппп(Л',шах(V,,л, ),£„//„,)], (31)

где л-, и х2 являются корнями уравнения второго порядка:

а ,.х + Ь ,,

(.чпи 1-11>1\!

/ , \ ^К '/<!•*

( I I N

V 'й 2 )

= Л

(32)

и значение переменной оптимального решения задачи-истока Nю

можно получить по формуле

Кг = «"¡п(л',[(/,; -/„Х, )/'«]) ■ (33)

Графическая иллюстрация построения интервала (31) представлена на рис.1.

Рис. 1. Графическая иллюстрация решения целочисленного нелинейного программирования При решении задачи (*) для устранения полного перебора вариантов разбиения, множества А на два подмножества А1 и Аг, удовлетворяющие условию (19), предлагается метод построения потенциального множества, являющегося подмножеством множества всех возможных схем декомпозиции. Метод основан на принципе "жадного выбора" эвристического подхода. Под потенциальностью построенного множества разбиения понимается высокая эвристическая оценка того, что схема декомпозиции, соответствующая оптимальному решению задачи (*), принадлежит этому множеству. Алгоритм построения потенциального множества схем декомпозиции заключается в последовательном переносе атрибутов, которые используются реже и занимают большее пространство в кэш-памяти, из множества А] во множество А,. Назовем выражение

/эвристической оценкой атрибута а;. На каждом

(„/ЕЛ()л(Л,с.1,) /

шаге алгоритм исключает атрибут с наименьшим значением эвристической оценки из множества /),. Множество схем декомпозиции, которое

состоит из начальной схемы (Л, = Л, Лг = К), соответствующей исходному отношению и схем, полученных при каждом переносе, является потенциальным множеством. Блок-схема этого алгоритма представлена на рис.2.

; Ш'ЫЧо

Ввод входных п.чммефи! чтчсниПН М О I-множл тел Л К А, векторы р,. I, где (1=1 (.1=1 М)

III 1111(11.141|Ч,|ЦШ Л' := :

.1, :=.!;. 1,:=/:

л, > 1 -

г.,'

Н<|йш|' I дс ; = 1 и и а, л К

| »РуЛ, 1*^01,) ] |

Вывод 8 как искомое множество «Л'ем

( К'онец

удотаются мкже те<)грпС>>1Ы ч, .(, (</,■; Л") дчя которых

»1 .«,«1 ,л(1,с4)

Г ^ЧМ-М] 1

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

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

При экспериментальной проверке предложенного критерия на стенде автоматически сгенерированно 50 задач, для каждой задачи - 50 схем декомпозиции, для каждой схемы - 100 потоков запросов длиной 5000 обращений к кэш-системе. Результат экспериментов, проведенных имитационным методом, показал, что относительное отклонение между теоретической и экспериментальной частотой кэш-попаданий составляет, в худшем случае, менее чем 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%.

Для испытания эффективности эвристического алгоритма на стенде было сгенерированно 150 задач, которые подвергнуты декомпозиции точным и эвристическим методами. Результаты испытаний показали, что величина относительного отклонения оценки вероятности кэш-попаданий эвристического метода от точного метода распределяется по нормальному закону с математическим ожиданием 5% и средним квадратическим отклонением 1%.

Заключение

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

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

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

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

Таким образом, поставленная в диссертации цель достигнута.

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

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Нго Тхань Хунг. Метод вертикальной кластеризации отношений реляционных баз данных / Тхань Хунг Нго // Вестник ДГТУ, 2008, №4.

Публикации в других изданиях

2. Гранков М.В. Система управления образовательным контентом Учебно-методического Управления ДГТУ / М.В. Гранков, Д.В. Грачев, Тхань Хунг Нго Ц Современные проблемы многоуровневого образования: сб. трудов I меж. научно-методического симпозиума, ММТГ XIX. - Россов н/Д: Издательский центр ДГТУ, 2006.

3. Гранков М.В. Методы разработки тестов на быстродействие информационных систем с использованием цепей Маркова / М.В. Гранков, Тхань Хунг Нго, Басам Мосаб Алзгуль // Инновационные образовательные технологии в технических университетах, сб. науч. статей по проблемам высшей школы / ЮРГТУ. - Новочеркасск, 2006. С. 394-396.

4. Нго Тхань Хунг. Разработка тестов быстродействия информационных систем с использованием цепей Маркова / Тхань Хунг Нго // Математические методы в технике и технологиях: сб. тр. XX меж. науч. кон. - Ярославль, 2007. С. 213-214.

5. Гранков М.В. Система, автоматизации администрирования прав доступа к образовательным ресурсам ВУЗа / М.В. Гранков, В.И. Мостовой, Тхань Хунг Нго // Современные проблемы многоуровневого образования; сб. трудов И меж. научно-методического симпозиума, ММТТ XX. - Россов н/Д: Издательский центр ДГТУ, 2006.

6. Нго Тхань Хунг. Повышение вероятности удачного обращения к кэш-памяти вертикальной кластеризацией / Тхань Хунг Нго, М.В. Гранков // Системный анализ, управление и обработка информации: 1-й межвуз. сборник науч. статьей молодых ученных / ДГТУ. - Ростов н/Д, 2008. С. 368-375.

7. Нго Т. X. Алгоритм рационального разбиения отношения на проекции при использовании ограниченной кэш-памяти / Т. X. Нго // Математические методы в технике и технологиях: сб. тр. XXI меж. науч. кон. - Саратов, 2008. С/ 288-289.

8. Нго Т. X. Программный стенд для исследования эффективности алгоритмов кэширования / Т. X. Нго, Б. М. Аль-Згуль // Математические методы в технике и технологиях: сб. тр. XXI меж. науч. кон. - Саратов, 2008. С. 260-266.

9. Ngo Thanh Hung. New objective function for vertical partitioning in database system / Thanh Hung Ngo // Proceedings of the Spring young researchers' colloquium on database and information systems -SYRCoDIS 5, volume B. - Saint-Petersburg, 2008. P. 6-9.

10. Grankov Michael V. The framework for study of caching algorithm efficiency / Michael V. Grankov, Thanh Hung Ngo, M. B. Al Zgool // Proceedings of the Spring young researchers' colloquium on database and information systems - SYRCoDIS 5, volume A. - Saint-Petersburg, 2008. P. 65-69.

11. Hro T.X. Разработка методов вертикальной кластеризации отношений в реляционных базах данных / Т.Х. Нго // Осенняя школа молодых ученных: сб. тр. / ТГТУ. - Тамбов, 2008.

12. Нго Т.Х. Графический алгоритм вертикальной фрагментации отношений и его дополнение/ Т.Х. Нго // Осенняя школа молодых ученных: сб. тр. / ТГТУ. - Тамбов, 2008.

13. А.с. № 11449. Программа для вертикального бинарного разбиения отношений реляционных баз данных / Т.Х. Нго // № государственной регистрации 50200801939; дата регистрации 29.08.2008

- 1с.

14. Нго Т.Х. Программа для вертикального бинарного разбиения отношений реляционных баз данных / Т.Х. Нго // Инновации в науке и образовании (Телеграф отраслевого фонда алгоритмов и программ). - № 9(44). - 2008. - С. 32. - Режим доступа: http://ofap.ru/portal/newspaper/2008/9_44.pdf. - Загл. с экрана.

15. А.с. № 11450. Программный стенд для исследования алгоритмов кэширования / М.Б. Альзгуль, Т.Х. Нго // № государственной регистрации 50200801940; дата регистрации 29.08.2008 - 1 с.

16. Альзгуль М.Б. Программный стенд для исследования алгоритмов кэширования / М.Б. Альзгуль, Т.Х. Нго // Инновации в науке и образовании (Телеграф отраслевого фонда алгоритмов и программ).

- № 9(44). - 2008. - С. 32-33. - Режим доступа: http://ofap.ru/portal/newspaper/2008/9_44.pdf. - Загл. с экрана.

В печать 18.11.2008.

Объем 1,1 усл.п.л., 1,0 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ № 542. Тираж 100 экз.

Издательский центр ДГТУ

Адрес университета и полиграфического предприятия: 344000, г. Ростов-на-Дону, пл. Гагарина, 1.

ВВЕДЕНИЕ.

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

1.1. ОСНОВНЫЕ ПОНЯТИЯ.

1.1.1. Трехуровневая архитектура абстракций базы данных.

1.1.2. Разработка внешних представлений баз данных.

1.1.3. Логическое проектирование базы данных.

1.1.3. Физическое проектирование систем реляционных баз данных.

1.2. ПОДГОТОВКА ИСХОДНОЙ ИНФОРМАЦИИ ДЛЯ ФИЗИЧЕСКОГО ПРОЕКТИРОВАНИЯ.

1.3. МЕТОДЫ ДЛЯ ФИЗИЧЕСКОГО ПРОЕКТИРОВАНИЯ.

1.3.1. Проектирование с использованием триггеров.

1.3.2. Применение уникальных индексов.

1.3.3. Использование снимков.

1.3.4. Применение денормализации.

1.3.5. Горизонтальная и вертикальная кластеризация отношений.

1.3.5.1. Горизонтальная кластеризация.

1.3.5.2. Вертикальная кластеризация.

1.3.5.3. Смешанная кластеризация.

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

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

2.1. ПОКАЗАТЕЛИ ЭФФЕКТИВНОСТИ СИСТЕМ БАЗ ДАННЫХ.

2.2. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ УЛУЧШЕНИЯ ПОКАЗАТЕЛЕЙ СИСТЕМ БАЗ ДАННЫХ С ПОМОЩЬЮ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ.

2.3. РОЛЬ МАТРИЦЫ ОБРАЩЕНИЙ К АТРИБУТАМ ОТНОШЕНИЯ.

2.4. ИСПОЛЬЗОВАНИЕ МАТРИЦЫ РОДСТВЕННОСТИ АТРИБУТОВ ОТНОШЕНИЯ.

2.5. АЛГОРИТМ "СОРТИРОВКИ" МАТРИЦЫ РОДСТВЕННОСТИ АТРИБУТОВ ВЕА.

2.6. АЛГОРИТМ БИНАРНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ В VP.

2.6.1. Процедура разбиения и критерий оценки качества схемы разбиения.

2.6.2. Пример выполнения процедуры разбиения.

2.6.3. Процедура смещения.

2.6.4. Выводы по алгоритму BVP.

2.7. ГРАФИЧЕСКИЙ АЛГОРИТМ НАВАТХЕ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ.

2.7.1. Основные понятия и обозначения.

2.7.2. Процедура построения остова и кластеров.

2.7.3. Пример применения графического алгоритма Наватхе.

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

2.7.5. Уточнение графического алгоритма Наватхе.

2.7.6. Выводы по графическому алгоритму Наватхе.

2.8. ЭВРИСТИЧЕСКИЙ АЛГОРИТМ МА ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ДЛЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ БАЗ ДАННЫХ.

2.8.1. Специфика распределенных систем баз данных.

2.8.2. Критерий размещения атрибутов на серверах.

2.8.3. Постановка задачи применения вертикальной кластеризации для уменьшения суммарной стоимости доступов к атрибутам.

2.8.4. Алгоритм решения задачи вертикальной кластеризации в распределенных системах баз данных.

2.8.5. Выводы по эвристическому алгоритму Ма.

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

ГЛАВА 3. МЕТОД ПРИМЕНЕНИЯ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЙ ДЛЯ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ЦЕНТРАЛИЗОВАННЫХ СИСТЕМ БАЗ ДАННЫХ.

3.1. ОБОСНОВАНИЕ ВЫБОРА ПОКАЗАТЕЛЯ ПРОИЗВОДИТЕЛЬНОСТИ ДЛЯ ОЦЕНКИ КАЧЕСТВА СХЕМ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ.

3.2. МОДЕЛЬ КЭШ-СИСТЕМЫ В ЦЕНТР АЛИЗОВАННЫХ СИСТЕМАХ БАЗ ДАННЫХ.

3.2.1. Метод физической реализации вертикальных кластеров в централизованных системе баз данных.

3.3. ОПИСАНИЕ И ОБОЗНАЧЕНИЕ ПЕРЕМЕННЫХ.

3.4. ВЫВОД ФОРМУЛЫ ОЦЕНКИ ВЕРОЯТНОСТИ КЭШ-ПОПАДАНИЯ ПРИ КЭШИРОВАНИИ БИНАРНЫХ ВЕРТИКАЛЬНЫХ КЛАСТЕРОВ.

3.4.1. Вероятность кэш-попаданий для кэширования исходного отношения.

3.4.2. Вероятность кэш-попаданий для кэширования проекций.

3.5. ПОСТАНОВКА ЗАДАЧИ ПРИМЕНЕНИЯ БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ В ЦЕНТРАЛИЗОВАННЫХ СИСТЕМ БАЗ ДАННЫХ.

3.6. АНАЛИЗ ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ ИЗВЕСТНЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ (II).

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

ГЛАВА 4. РАЗРАБОТКА МЕТОДА БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ.

4.1. РЕШЕНИЯ ЗАДАЧИ (3.5.15 - 3.5.19) АЛГОРИТМОМ ПОЛНОГО ПЕРЕБОРА.

4.2. ФОРМУЛИРОВКА ЗАДАЧИ-ИСТОКА И ЕЕ ОСЛАБЛЕННОЙ ЗАДАЧИ.

4.3. МЕТОД РЕШЕНИЯ ЗАДАЧИ-ИСТОКА ПРИ С * 0.

4.3.1. Лемма 1: о нахождении оптимального решения ослабленной задачи на краевой линии (4.2.6).$

4.3.2. Решение ослабленной задачи.

4.3.3. Лемма 2: о свойстве оптимального решения задачи-истока.

4.3.4. Лемма 3: о допустимости решения задачи-истока, полученного целочисленным округлением некоторого допустимого решения ослабленной задачи.

4.3.5. Лемма 4.

4.3.6. Теорема об области, содержащей оптимальное решение задачи-истока.

4.3.7. Пример реализации метода сужения интервала поиска в среде Maple.

4.4. ЭВРИСТИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ ПОТЕНЦИАЛЬНОГО МНОЖЕСТВА СХЕМ ВЕРТИАКЛЬНОЙ КЛАСТЕРИЗАЦИИ.

4.5. ПРЕДЛОЖЕННЫЙ ЭВРИСТИЧЕСКИЙ АЛГОРИТМ БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ.

4.6. СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИИ АЛГОРИТМОВ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ.

4.6.1. Реализация алгоритма BVP.

4.6.2. Реализация графического алгоритма Наватхе.

4.6.3. Реализация эвристического алгоритма Ма.

4.6.4. Реализация предложенного алгоритма HBVP.

4.7. СРАНИТЕЛЬНЫЕ ПРИМЕРЫ РЕАЛИЗАЦИИ ГРАФИЧЕСКОГО АЛГОРИТМА НАВАТХЕ С ПРЕДЛОЖЕННЫМ ЭВРИСТИЧЕСКИМ АЛГОРИТМОМ.

4.7.1. Первый пример.

4.7.2. Второй пример.

4.7.3. Третий пример.

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

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.

5.1. ОПИСАНИЕ ИМИТАЦИОННОЙ МОДЕЛИ КЭШ-СИСТЕМЫ.

5.2. МОДЕЛИ ПОТОКОВ ЗАПРОСОВ К КЭШ-СИСТЕМЕ.

5.2.1. Специальные случая реализации предложенной модели.

5.3. ОПИСАНИЕ И РЕЗУЛЬТАТ ЭКСПЕРИМЕНТАЛЬНОЙ ПРОВЕРКИ ДОСТОВЕРНОСТИ ФОРМУЛЫ ОЦЕНКИ ВЕРОЯТНОСТИ КЭШ-ПОПАДАНИЙ.

5.4. ОПИСАНИЕ И РЕЗУЛЬТАТ ИССЛЕДОВАНИЙ ЭФФЕКТИВНОСТИ ПРЕДЛОЖЕННОГО ЭВРИСТИЧЕСКОГО АЛГОРИТМА БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ.

5.5. ПРИМЕР ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ ПРЕДЛОЖЕННОГО МЕТОДА ПРИМЕНЕНИЯ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ.

5.5.1. Исходное отношение в момент создания БД.

5.5.2. Улучшение системной производительности при проведении бинарной вертикальной кластеризации.

5.5.3. Вертикальная кластеризация в системах с нестабильным распределением частот вызовов запросов.

5.6. ВЫВОДЫ ПО ПЯТОЙ ГЛАВЕ.

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

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

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

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

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

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

Для достижения данной цели необходимо решить следующие основные задачи:

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

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

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

4. разработать программные средства для экспериментального исследования предложенного метода вертикальной кластеризации и эффективности алгоритмов его реализации.

Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и систем БД, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, методы математического программирования и эвристические методы оптимизации.

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

1. Критерий оценки частоты кэш-попаданий для метода вертикальной кластеризации отношений при заданном потоке запросов и условии равной вероятности обращений к кортежам отношения, экспериментальная проверка которого установила, что оценка относительного отклонения от теоретического значения не превышает 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%.

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

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

4. Алгоритм приближенного решения задачи декомпозиции отношений с критерием оценки частоты кэш-попаданий при заданном потоке запросов и при условии равной вероятности обращений к кортежам отношения, для которого на репрезентативной выборке оценка математического ожидания отклонения от точного решения составляет 5%, а среднее квадратическое отклонение 1%.

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

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

2. Зарегистрированный в Отраслевом фонде алгоритмов и программ (ОФАП) "Программный стенд для исследования алгоритмов кэширования" позволяет исследовать частоты кэш-попаданий при кэшировании различных схем декомпозиции отношения. Зарегистрированная в ОФАП "Программа для вертикального бинарного разбиения отношений РБД" позволяет исследовать эффективность приближенного решения задачи декомпозиции отношения в сравнении с алгоритмом полного перебора.

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

Апробация диссертационной работы. Основные результаты диссертационной работы получили апробацию на следующих международных конференциях: на XX Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-20), ЯГТУ, Ярославль, 2007; на XXI Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-21), СГТУ, Саратов, 2008;

V Spring young researchers' colloquium on database and information systems (SYRCoDIS V), Saint-Petersburg, 2008; на I международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2006); на II международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2007); Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета.

Публикации. Всего по теме диссертации опубликовано 16 печатных работ (одна в издании, включенном в перечень ВАК), в которых отражены основные результаты диссертации.

Структура и объём работы. Диссертация состоит из введения, 5 глав, заключения, списка литературы и 5 приложений. Основная часть работы изложена на 158 страницах машинописного текста, 34 рисунках, 38 таблицах.

5.6. ВЫВОДЫ ПО ПЯТОЙ ГЛАВЕ

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

• Результаты экспериментов, проведенных имитационным методом, показали, что относительное отклонение между теоретической и экспериментальной частотой кэш-попаданий составляет, в худшем случае, менее чем 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%, что доказывает высокую достоверность разработанной математической модели и разработанного критерия оценки вероятности кэш-попаданий.

• Результаты испытаний алгоритма HBVP показали, что по точности решения задачи алгоритм HBVP дает совпадающее решение с полным перебором в более 95% случаях, что является высоким показателем для класса эвристических алгоритмов. Это показывает высокую эффективность разработанного алгоритма HBVP.

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

ЗАКЛЮЧЕНИЕ

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

2. В работе показано, что в централизованных системах баз данных повышение эффективности использования кэш-памяти непосредственно приведет к повышению производительности системы в целом. Полученный критерий оценки частоты кэш-попаданий при заданной схеме декомпозиции, заданном потоке запросов приложений и условии равной вероятности обращений к кортежам отношения позволяет реализовать метод рациональной вертикальной кластеризации отношений для повышения эффективности использования кэш-памяти в централизованных системах баз данных. Разработана математическая модель задачи бинарной вертикальной кластеризации с использованием критерия оценки частоты кэш-попаданий в централизованных системах при заданном потоке запросов приложений и условии равной вероятности обращений к кортежам отношения. Полученная задача принадлежит к классу задач дискретного нелинейного программирования с четырьмя параметрами (AvA2,NRl,NR2), в которых А, и А2 являются ограниченными дискретными множествами, a NKl и NR2 - целыми ограниченными числами.

3. Предложенный метод (HBVP) решения поставленной задачи дискретного программирования, состоящий из двух этапов, позволяет выполнять рациональную декомпозицию отношений с целью повышения эффективности использования кэш-памяти в системах обработки и хранения информации. При этом для первого этапа разработан алгоритм построения потенциального множества схем декомпозиции (АпА2), который сокращает количество рассматриваемых схем декомпозиции. Алгоритм построен на принципе "жадного выбора" эвристического подхода применительно к специфике данной математической модели. Эффективность алгоритма, т.е. доля полного совпадения полученной этим алгоритмом схемы по сравнению со схемой, полученной полным перебором, составляет более 95% . Для второго этапа разработан метод сужения области поиска значения параметров (Л^,,/^), соответствующего оптимальному решению задачи нелинейного целочисленного программирования при известном значении параметров А, и А2. Предложенный метод, реализуя фактически идею метода ветвей и границ, за каждую итерацию позволяет сузить на порядок интервал неопределенности. Метод сужения области поиска параметров (NRl,NR2) и алгоритм построения потенциального множества схем декомпозиции могут быть использоваться как в совокупности между собой, так и в сочетании с другими подходящими существующими методами, что делает их использование более гибким.

4. Для экспериментального исследования предложенных математических моделей и разработанного метода вертикальной кластеризации отношений реализованы два программных комплекса, зарегистрированных в отраслевом фонде алгоритмов и программ. С их помощью были проведены проверка достоверности разработанного критерия оценки вероятности кэш-попаданий и испытание эффективности разработанного эвристического алгоритма HBVP. Результаты экспериментов, проведенных имитационным методом, показали, что относительное отклонение между теоретической и экспериментальной частотами кэш-попаданий составляет, в худшем случае, менее 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%, что доказывает высокую достоверность разработанной математической модели и критерия оценки вероятности кэш-попаданий. Экспериментально доказана высокая эффективность разработанного метода вертикальной кластеризации. Таким образом, основные задачи диссертационной работы решены полностью и достигнута ее цель.

1. Adrian Sergiu Darabant. A new approach in fragmentation of distributed object oriented databases using clustering techniques. // Studia Univ. Babes-Bolyai, Informatica, Volume L, Number 2, 2005.

2. Baiao F. A strategy for the Distributed Design of Object Oriented Databases. // Thesis, COPPE/UFRJ, Rio de Janeiro, Brazil, 1997. Bail.

3. Baiao F., Mattoso M. A Mixed Fragmentation Strategy for Distributed OO Databases. // Proceedings of The second Workshop on CSCW in Design, pp. 42-48, Bangkok, Thailand, 1997. Bai2.

4. Bellatreche L. et.al. Vertical Fragmentation in Distributed Object Database Systems with Complex Attribute and Methods. // Proceedings of the 7th International Workshop on Database and Expert Systems Applications, 1996. Belli.

5. Ceri S., Navathe S.B. A Comprehensive Approach to Fragmentation and Allocation of data in a Distributed Databases. // Proceedings of the IEEE COMPCON Conference, 1983. Nav4.

6. Ceri S., Navathe S.B., and Wiederhold G. Distributed design of Logical database schemas. // IEEE Transaction on Software Engineering, 9 (4), 1983. Nav5.

7. Ceri S., Negri M., and Pelagatti G. Horizontal data partitioning in database design. // Proceedings if the ACM SIGMOD International Conference on Management of Data. SIGPLAN Notices, 1982. Ceril.

8. Chakravarthy S., Jeyakumar Muthuraj, Varadarajan R., and Navathe S.B. A formal approach to the vertical partitioning problem in Distributed Database

9. Design. // Proceedings of Second International Conference on Parallel and Distributed Information. Chakl.

10. Chu P.C. A transaction-oriented approach to attribute partitioning. // Information Systems, vol. 17, no. 4, pp. 329-342, 1992. Chu2.

11. Chu W.W., Ieong I.T. A transaction-based approach to vertical partitioning to vertical partitioning for relational databases. //Tech. rep. UCLA, 1991. Chul.

12. Cornell D.W., Yu P.S. A vertical partitioning algorithm for relational databases. // Proceedings of International Conference on Data Engineering, IEEE, pp. 30-35, 1987. Cornl.

13. Ezeife C.I., Ken Barker. Vertical Class Fragmentation in a Distributed Object Based System". // Technical Report 94-03, Dept. of Computer Science, Univ. of Manitoba, 1994. Ezeifel.

14. Ezeife C.I., Ken Barker. A Comprehensive Approach to Horizontal Class Fragmentation in a Distributed Object Based System.// Distributed and Parallel Databases, 3(3), pp. 247-272, 1995. Ezeife2.

15. Ezeife C.I. and Ken Barker. A Distributed Object Based Design Technique. // Natural Science and Engineering Research Council, Canada, 1995. Ezeife3.

16. Fernanda Baiao, Marta Mattoso. A Mixed Fragmentation Algorithm for Distributed Object Oriented Databases. // Proceedings of the Ninth International Conference on Computing Information, Winnipeg, Canada, 1998. Bai3.

17. Fleming C. and Von Halle B. Handbook of Relational Database Design. // Addison-Wesley, 1989. Fleml.

18. Hoffer J.A. An integer programming formulation of computer database design problems. // Inf. Sci., 11 (July 1976), 29-48. Hoff2.

19. Hoffer J.A. and Severance D.G. The use of cluster analysis in physical database design. //Proceedings of the 1st International Conference on Very large Databases, Vol. l,No. 1, 1975. Hoffl.

20. Hui Ma, Klaus-Dieter Schewe and Markus Kirchberg. A Heuristic Approach to Vertical Fragmentation Incorporating Query. // Massey University,1.formation Science Research Centre & Department of Information Systems. — USA, 2006.

21. Ismail Hababeh, Muthu Ramachandran and Nicholas Bowring. A Mathematical Approach for Modeling Data Allocation in Distributed Database Systems. // The Seventh Annual U.A.E. University Research Conference, April, 2006. Nicl.

22. Jain A.K., Murty M.N., Flynn P.J. Data Clustering: A Review // ACM

23. Computing Surveys, Vol. 31, No. 3, September 1999. Jainl.

24. Jelenkovic P. R., Radovanovic A. Optimizing the LRU algorithm for Web caching. // 18th. International Teletraffic Congress, Berlin, Germany, 2003.

25. Jeyakumar Muthuraj. A formal approach to the vertical partitioning problem in Distributed Database Design. // Master of Science Thesis, Dept.of Computer Science, Univ. of Florida. Muthl.

26. Kennedy R. The Use of Access Frequencies in Database Organization. // Ph.D Dissertation, The Wharton School, Univ. of Pennsylvania, 155 pp, May 1973. Kenl.

27. Lawrence R. Rabiner. A tutorial on Hidden Markov Models and selected applications in speech recognition. // Proceedings of the IEEE, VOL. 77, NO. 2, Feb 1989. http://www.cs.ubc.ca/~muphyk/Bayers/rabiner.pdf. Rabl.

28. Lin X., Orlowska M., and Zhang Y. A graph based cluster approach for vertical partitioning in database design. // Data and Knowledge Engineering, vol. 11, pp. 151-169, 1993. Zhang 1.

29. Lorinda Visnick. Clustering Techniques A Technical Whitepaper. // www.objectstore.net Visnickl.

30. Malinowski E. Fragmentation Techniques for Distributed Object-Oriented Databases. // Thesis, Univ. of Florida, USA, 1996. Mall.

31. Matthias Jarke, Jurgen Koch. Query Optimization in Database Systems. // Computing Surveys, Vol. 16, No. 2, June 1984. Jarl.

32. McCormick W.T., Schweitzer P.J., and White T.W. Problem decomposition and data reorganization by a clustering technique. // Operation Research, vol.20, p.993-1009, 1972. Corml.

33. Michael J. Franklin, Michael J. Carey, Miron Livny. Local disk caching for client-server database systems. // Proceedings of the 19th VLDB Confidence, Dublin, Irelang, 1993. Frankl.

34. Narasimhaiah Gorla. A Methodology for Vertically Partitioning in a Multi-Relation Database Environment. // JCS&T Vol. 7 No. 3, 2007. Gorlal.

35. Natallia Kokash. An introduction to heuristic algorithms. 2005// http://dit.unitn.it/~kokash/documents/Heuristic algorithms.pdf fNatl.

36. Navathe S.B., Ceri S., Wiederhold G., Dou J. Vertical Partitioning Algorithms for Database Design. // ACM Transactions on Database Systems, vol. 9, no. 4, pp. 680-710, 1984. Navl.

37. Navathe S.B., Kamalakar Karlapalem, and Minyoung Ra. A Mixed Fragmentation Methodology For Initial Distributed Database Design. // Database Systems R&D Center, University of Florida, USA, 1995. Nav3.

38. Navathe S.B., Ra M. Vertical partitioning for database design: A graphical algorithm. // Proceedings of ACM SIGMOD International Conference on Management of Data, 1989. Nav2.

39. Nemhauser G. Integer and Combinational Optimization. / G. Nemhauser, L. Wolsey. New York: Wiley, 1988.

40. Ngo Thanh Hung, Grankov Michael Vasilevich. New Objective Function for Vertical Partitioning in Database System. // SYRCoDIS, 2008.

41. Ngo Thanh Hung, Grankov Michael Vasilevich, A1 Zgool M.B. The Framework for Study of Caching Algorithm Efficiency. // SYRCoDIS, 2008.41.0zsu M.T. and Valduriez P. Principles of Distributed Database Systems. // Prentice Hall, 1991. Ozsul.

42. Parker G. Discrete Optimization / G. Parker, R. Rardin. Orlando FL: Academic Press, 1988.

43. Pernul G., Karalapalem K., and Navathe S.B. "Relational database organization based on views and fragments." // Proceedings of the second International Conference on Data and Expert System Applications, Berlin, 1991. Nav6.

44. Rex Blankinship, Alan R. Hevner, S. Bing Yao. An iterative Method for Distributed Design. // Proceedings of the 17th International Conference on Very Large Data Bases, 1991. Yaol.

45. Rogers U. Denormalization: Why, what and how? // Database Programming and Design, 2(12), 1989, 46-53. Rogl.

46. Sanjay Agrawal, Vivek Narasayya, and Beverly Yang. Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design. // The 2004 ACM SIGMOD International Conference on Management of Data. June 2004.

47. Savonnet, M. et. al. Using Structural Schema Information as Heuristics for Horizontal Fragmentation of Object Classes in Distributed OODB. // Proceedings IX International Conference on Parallel and Distributed OODB, pp. 732-737. France, 1996.

48. Sharma Chakravarthy, Jaykumar Muthuraj, Ravi Varadarajan, Navathe Shamkant В. An Objective Function for Vertically Partitioning Relations in Distributed Databases and its Analysis // Distributed and Parallel Databases 2(2): 183-207(1994).

49. Shin D. and Irani K.B. Fragmenting relation horizontally using a knowledge-based approach. // IEEE Transactions on Software Engineering, 17 (9), 1991.

50. Starobinski D., Tse D. Probabilistic methods for Web caching. // Performance evaluation, 46(2-3):125-137, 2001.

51. Steve Rozen, Dennis Shasha. Automating Physical Database Design A Universal Approach and Its Evaluation. // 1993.

52. Steve Rozen. Automating Physical Database Design An Extensible Approach. // PhD thesis/New York University. - New York, 1993.

53. Suk-Kyu Song and Narasimhaiah Gorla. A Genetic Algorithm for Vertical Fragmentation and Access Path Selection. // The Computer Journal, Vol.43, No.1,2000.

54. Sylvain Guinepain and Le Gruenwald. Research Issues in Automatic Database Clustering. // SIGMOD Record, Vol.34, No.l, March, 2005.

55. Wai Gen Yee, Michael J. Donahoo, Shamkant B. Navathe. A framework for server data fragment grouping to improve scalability in intermittently synchronized databases. // In Proc. ACM Conf. on Information and Knowledge Management, 2000.

56. Алексеев В.Ю. Комплексное применение методов дискретной оптимизации / В.Ю. Алексеев. М.: Наука, 1987.

57. Андерсон Дж. Дискретная математика и комбинаторика / Дж Андерсон. — М.: Вильяме, 2003.

58. Барсегян А.А. Методы и модели анализа данных: OLAP и Data Mining /

59. A.А. Барсегян, М.С. Куприянов, В.В. Степаненко. Санкт-Петербург: изд-во BHV, 2004. - 336с.

60. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем / В.В. Бойко, В.М. Савинков. Москва, 1989.

61. Гладков JI.A. Генетические алгоритмы / JI.A. Гладков, В.В. Курейчик,

62. B.М. Курейчик. Москва: ФИЗМАТЛИТ, 2006. - 320с.

63. Голицына О.Л. Основы алгоритмизации и программирования / О.Л. Голицына, И.И. Попов. Москва: изд-во "Высшая школа", 2005. - 320с.

64. Гранков М.В., Нго Тхань Хунг, «Повышение вероятности удачного обращения к кэш-памяти вертикальной кластеризацией», Сборник аспиранта ДГТУ, 2008.

65. Нго Т. X. Алгоритм рационального разбиения отношения на проекции при использовании ограниченной кэш-памяти / Т. X. Нго // Математические методы в технике и технологиях: сб. тр. XXI меж. науч. кон. Саратов, 2008.

66. Дегтярев Ю.И. Методы оптимизации / Ю.И Дегтярев. — Москва: изд-во "Советское радио", 1980. 272с.

67. Дейт К. Дж. Введение в системы баз данных. 7-ое издание / К. Дж Дейт. -М.: Вильяме, 2001. 1072с.

68. Иванова В.М. Математическая статистика / В.М. Иванова, В.Н. Калинина, JT.A. Нешумова, И.О. Решетникова. Москва: изд-во "Высшая школа", 1981.-371с.

69. Карпова И.П. Введение в базы данных Учебное пособие / И.П.Карпова // Московский государственный институт электроники и математики. -Москва, 2004.

70. Кириллов В.В. Основы проектирования реляционных баз данных/ В.В. Кириллов // Лекции/Санкт-Петербургский Государственный институт точной механики и оптики. Санкт-Петербург, 1995.

71. Кнут Д. Искусство программирования. Том 3. Сортировка и поиск / Д. Кнут. Москва: изд-во "Финансы и статистика", 2002.

72. Ковалев М.М. Дискретная оптимизация целочисленное программирование/ М.М. Ковалев. - М.: УРСС, 2003.

73. Коннолли Т.М., Бегг К.Э., Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и Практика / Т.М. Коннолли, К.Э. Бегг, А. Страчан // Пер. от англ. М.: Вильяме, 1998.

74. Крамер Г. Математические методы статистики / Г. Крамер. М.: Регулярная и хаотическая динамика, 2003. - 648с.

75. Кремер Н.Ш. Теория вероятностей и математическая статистика / Н.Ш. Кремер. -М.: изд-во "Юнити", 2007. 551с.

76. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кристофидес. Москва: изд-во "Мир", 1978.

77. Кузнецов С.Д. Введение в реляционные базы данных Лекция. // Центр Информационных Технологий, Москва, 2003. Кузн2.

78. Кузнецов С.Д. Информационно-аналитические материалы: Основы современных баз данных. // Центр Информационных Технологий -http://www.citmgu.ru. Кузн1.

79. Кузнецов С.Д. Тенденции в мире систем управления базами данных. // Материалы конференции "Корпоративные базы данных '96м, 1996. КузнЗ.

80. Кузнецов Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. Москва: изд-во "Высшая школа", 1976. 352с.

81. Курейчик В.М. Дискретная математика. Ч.З. Оптимизационные задачи на графах. Таганрог: Изд-во "ТРТУ", 1998.

82. Лонлон Дж., Лондон К. Управление информационными системам, 7-е издание // Питер, 2005, 912с.

83. Лукашин Ю.П. Адаптивные методы краткосрочного прогнозирования временных рядов: Учеб. Пособие. М.: изд-во "Финансы и статистика", 203, -416с.

84. Лю Б. Теория и практика неопределенного программирования. // Москва, БИНОМ, Лаборатория знаний, 2005.

85. Майкл Блаха. Ссылочная целостность является важной для баз данных. // Пер. Сергеем Кузнецовом, www.citforum.ru, 2005. Майкл1.

86. Моисеев Н.Н. Методы оптимизации / Н.Н. Моисеев, Ю.П. Иванилов, Е.М. Столярова. Москва: изд-во "Наука", 1978. 352с.

87. Нго Т.Х. Разработка методов вертикальной кластеризации отно-шений в реляционных базах данных / Т.Х. Нго // Осенняя школа молодых ученных: сб. тр. / ТГТУ. Тамбов, 2008.

88. Нго Тхань Хунг. Разработка тестов быстродействия информаци-онных систем с использованием цепей Маркова / Тхань Хунг Нго // Математические методы в технике и технологиях: сб. тр. XX меж. науч. кон. Ярославль, 2007.

89. Нго Т. X. Программный стенд для исследования эффективности алгоритмов кэширования / Т. X. Нго, Б. М. Аль-Згуль // Математи-ческие методы в технике и технологиях: сб. тр. XXI меж. науч. кон. Саратов, 2008.

90. Овчаров JI.A. Теория вероятностей и ее инженерные приложения / JLA. Овчаров, Е.С. Вентцель. Москва: изд-во "Высшая школа", 2007. 491с.

91. Пейдж В. И др. Использование Oracle8/8i.: пер. с англ.. М.: Вильяме, 2000.- 1024 с. [Вил1]

92. Петер Пин-Шен Чен. Модель "сущность-связь" шаг к единому представлению о данных. // Пер. ACM Transactions on Database Systems, v.l, №1, 1976.

93. Пупков K.A. Оценка и планирование эксперимента / К.А. Пупков, Г.А. Костюк. Москва: изд-во "Машиностроение", 1977. 118с.

94. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, А. Део. Москва: изд-во "Мир", 1980.

95. Реклейтис Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Москва: изд-во "Мир", 1986. 320с.

96. Соболь И.М. Метод Монте-Карло / И.М. Соболь. Москва, 1978.

97. Степнов М.Н. Статистические методы обработки результатов механических испытаний / М.Н. Степнов. — Москва: изд-во "Машиностроение", 1985. -232с.

98. Таненбаум Э. Современные операционные системы. Питер, 2004.

99. Тиори Т., Фрай Дж. Проектирование структур баз данных. Москва, 1985.

100. Хэмди А.Т. Введение в исследование операций / А.Т. Хэмди. М: изд-во "Вильяме", 2001. - 912с.

101. Цветков Э.И. Основы теории статистических измерений / Э.И. Цветков. -Ленинград: ЭнергоАтомИздт, 1986. -256с.