Методика тестирования результатов вертикальной кластеризации отношений реляционных баз данных
Автор: Гранков Михаил Васильевич, Жуков Александр Игоревич
Журнал: Вестник Донского государственного технического университета @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.