Методика тестирования результатов вертикальной кластеризации отношений реляционных баз данных

Автор: Гранков Михаил Васильевич, Жуков Александр Игоревич

Журнал: Вестник Донского государственного технического университета @vestnik-donstu

Рубрика: Физико-математические науки

Статья в выпуске: 8-2 (59) т.11, 2011 года.

Бесплатный доступ

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

Методы структурной оптимизации, вертикальная кластеризация, декомпозиция отношений

Короткий адрес: https://sciup.org/14249685

IDR: 14249685

Текст научной статьи Методика тестирования результатов вертикальной кластеризации отношений реляционных баз данных

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

Одним из методов структурной оптимизации является метод вертикальной кластеризации ( секционирования ) отношений РБД. На базе этого метода в ДГТУ аспирантом кафедры «ПОВТ и АС» Нго Т.Х. был разработан эвристический алгоритм вертикальной кластеризации HBVP [1], который заключается в получении декомпозиции исходного отношения, приводящего к повышению вероятности кэш-попадания при заданном распределении запросов к БД в независимости от эффективности используемого алгоритма кэширования. При обосновании данного метода была выдвинута гипотеза о том, что при практических и теоретических исследованиях методов структурной оптимизации необходимо использовать поток запросов с равномерным распределением объектов ИС [1]. Целью настоящей статьи является теоретическое доказательство данной гипотезы. Постановка задачи. Рассмотрим модель информационной системы для проведения исследований методов структурной оптимизации. Пусть данная ИС реализует в своем составе некоторый алгоритм замещения объектов в кэш-памяти, определим ее основные понятия:

  •    объект информационной системы (объект трассы, объект системы кэширования) – минимальная единица информации, сохраняемая в кэше (в нашем случае, кортеж). Допустим также, что каждый объект имеет идентификатор, уникальным образом определяющий его на множестве всех объектов ИС;

  •    трасса – это последовательность обращений к объектам информационной системы, соответствующая некоторому потоку запросов к БД. Трасса формируется на основании пользовательских запросов, каждый из которых может подразумевать запрос в источнике данных (база

данных или файловое хранилище) некоторого числа объектов. Таким образом, трасса может быть представлена как последовательность идентификаторов объектов ИС;

  •    дистанция – участок трассы для объекта a , который начинается и заканчивается обращением к объекту а и внутри себя не содержит обращений к этому объекту.

Необходимо доказать, что использование трасс с равномерным распределением объектов позволяет нивелировать влияние кэш-системы на эффективность информационной системы в целом, таким образом, объективно оценить эффективность проведения структурной оптимизации. Доказательство. Величина временного интервала между двумя соседними вызовами объектов в исследованиях методов структурной оптимизации не играет роли и обычно принимается равной 1 [2,3]. Таким образом, позиция объекта в трассе может быть интерпретирована как момент времени, в который данный объект был запрошен пользователем ИС (рис.1).

Рис.1. Схема трассы потока объектов кэш-системы

Будем считать, что понятию «объект ИС» в реляционных системах соответствует понятие «кортеж» . Рассмотрим отношение, состоящее из N кортежей и только те отношения, в которых N >>1.

Пусть вероятность появления объекта в трассе в некоторый момент времени i не зависит ни от объекта, ни от позиции в трассе и равна:

p = 1 N                                    (1)

Вероятность того, что объект не появится в любой позиции трассы в момент времени i , выражается соотношением:

q = 1 - p = 1 - 1 N = ( N - 1)/ N                             (2)

Обозначим ^ - дискретную случайную величину, равную дистанции для некоторого объекта и изменяющуюся в диапазоне (1, ∞). Пусть в момент времени i в трассе появляется объект a . Тогда с вероятностью ( N - 1)/ N2 он может появиться в ( i+ 1 )-ой позиции, с вероятностью 1 N ( ( N - 1 )/ N ) 2 - в ( i +2 )-ой позиции и в ( i + к -1 )-ой позиции с вероятностью:

Р+к-1 = 1N((N -1)/N)k"’ ,(3)

где i = 1,2,...

Введем в рассмотрение E K : k

Ek = Z1 N ((N -1)/N) • I(4)

= 1

Выполнив преобразования в соответствии с (2), получаем:

k

Ek = 1N Z q1 -1 • l(5)

I = 1

Тогда математическое ожидание случайной величины ^ :

E (6)=limEk(6)

к ^го

k

Введем дополнительное обозначение для суммы: S k = £ q - 1 l и рассчитаем несколько i = 1

первых значений для определения закономерности: S 1 = 1, S 2 = 2 q , S 3 = 3 q 2 . Тогда, очевидно:

S k = S 1 + S 2 + S 3 + ... + Sm , при m=k. Представим полученные значения в виде квадратной матрицы,

в которой на каждой J -ой строке расположим составные части J -ого значения для S j , J = 1, m .

При этом, S – сумма элементов в -ом столбце:

S 1

( 1

0

0

0

0

0 )

S 2

q

q

0

0

0

0

S 3

q q

q 2

q 2

0

0

0

S 4

q 3

q 3

q 3

q 3

0

0

...

...

...

...

...

0

S m

a m 1 k q

qm 1

qm 1

qm 1

...

a m 1

q J

S 1

S 2

S 3

S 4

...

S m

.

m

m

Очевидно, что Sk = £ S j = £ S j , кроме того, S 2 = S 1 1 , S 3 = S 2 q , S 4 = S 3 q 2 , из чего = 1            = 1

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

m

S = £ q 1

t = 1

j

£ q t 1

t = 1

Для нахождения S из (8) воспользуемся формулой геометрической прогрессии:

m

m

S k = £ Sj = £

f 1 qm   1 qJ '

j = 1

J = 1 k

1 q 1 q J 1 q

m ( 1 qm ) m + £ qJ k                             j = 1

'—1

J

1 q

k

m

mq m + — q- 1 q

.

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

k

E ( 5 ) = lim Ek ( 5 ) = -lim £ q1 1 l k ^m        N k ^m 7=1

Учитывая выражение, полученное для Sk , а также подставив значения для q , предельное значение для математического ожидания появления каждого объекта из рассматриваемого множества мощности N ( N >> 1) на дистанции неограниченной длины, равно:

E ( 5 ) = — lim Sk = — lim

N m ^m     N m ^m

( 1

k i q k

1 qm

mq m + —— 1 q

k

J

---- • -----------г N ( 1 — q ) 2

(

lim 1 qm

m ^m

k

mqm

1 q

-

N ( 1 q ) 2

lim 1 m ^m

qm qm + 1 + mq m V 1     1

k

i q

----------г

N ( 1 q ) 2

•lim 1

m ^m

k

qm i— q

qm + 1 +

1 q

mqm

1 q

Так как q <1, а также в связи с тем, что показательная функция растет на бесконечности быстрее любой полиномиальной, получаем:

E © = —

N

Подставим значение для q :

E © =  

= N

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

Теорема А0 Ахо доказывает [4], что оптимальной стратегией вытеснения объектов из кэшпамяти является утилизация объектов с наибольшим математическим ожиданием дистанции появления в трассе. Также доказано, что этот алгоритм уступает по эффективности только оптимальному алгоритму Биледи, для которого будущая трасса должна быть известна, что практически нереализуемо [2]. Однако, очевидно, что при равенстве математического ожидания дистанции для всех объектов трассы, оптимальный алгоритм A0 неэффективен, а значит, любой другой алгоритм кэширования, кроме алгоритма Биледи, имеет эффективность меньше эффективности алгоритма A0.

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

Список литературы Методика тестирования результатов вертикальной кластеризации отношений реляционных баз данных

  • Нго Тхань Хунг. Метод вертикальной кластеризации отношений реляционных баз данных/Тхань Хунг Нго//Вестн. Донск. гос. техн. ун-та. -2008. -№4.
  • Аль-Згуль Мосаб Басам. Гибридные алгоритмы в системах кэширования объектов/Мосаб Басам Аль-Згуль//Вестн. Донск. гос. техн. ун-та. -2008. -№4.
  • Жуков А.И. Математическая модель метода бигибридизации алгоритмов кэширования/А.И. Жуков, Мосаб Басам Аль-Згуль//«В мире научных открытий». -№4(10). -Ч.13. -Красноярск, 2010.
  • Aho A.V., Denning P.J., Ulman J.D., Principles of optimal page replacement, J. ACM, vol. 18, no. 1, 1971.
Статья научная