,
где 
‑ длина сегмента для фрагмента 
Доказательство. В соответствии с формулой имеем
Отсюда получаем
.
Так как 
, 
и поддеревья 
и 
являются смежными, то минимальное поддерево 
, содержащее диски 
и 
будет иметь уровень 
. Тогда в соответствии с получаем 
. Подставив это значение в, будем иметь
.
Подставив вместо 
значение из, получим
Теорема доказана.
Оценка суммарного размера всех реплик фрагмента может быть получена с помощью следующей теоремы.
Теорема 2. Пусть T ‑ симметричное DM‑дерево высоты 
. Пусть фрагмент располагается на диске 
. Обозначим степень уровня l дерева T как 
. Обозначим 
‑ суммарное количество кортежей во всех репликах фрагмента . Тогда
.
Доказательство. Доказательство проведем индукцией по высоте H дерева T.
Пусть 
. Тогда число дисков в дереве T равно 
. В соответствии с теоремой 1 каждая реплика будет иметь размер 
. Следовательно, суммарное количество кортежей во всех репликах фрагмента имеет следующую оценку
,
что согласуется с формулой при .
Пусть 
. Тогда дерево T содержит поддеревьев высоты 
:
.
Обозначим через 
суммарное количество кортежей во всех репликах фрагмента , расположенных на всех дисках поддерева 
. Мы имеем
.
Без ограничения общности мы можем считать, что 
. Тогда в силу симметричности дерева T из получаем
.
В соответствии с теоремой 1[Л. Б.10] любая реплика 
, располагающаяся в поддереве 
имеет следующий размер
.
В силу симметричности дерева T, суммарное количество дисков в поддереве равно 
. Учитывая этот факт, из получаем
.
С другой стороны, по предположению индукции имеем
.
Подставляя в значения правых частей из и, имеем
Теорема доказана.
4.3. Выбор функции репликации
При выборе функции репликации 
целесообразно учитывать коэффициенты трудоемкости узлов DM‑дерева. Очевидно, что в симметричном DM‑дереве все вершины уровня l имеют одинаковую трудоемкость 
, которую мы будем называть трудоемкостью уровня l.
Назовем симметричное DM‑дерево T регулярным, если для любых двух уровней 
и 
дерева T справедливо
,
то есть, чем выше уровень в иерархии, тем больше его трудоемкость.
Следующая теорема позволяет получить оценку трудоемкости покортежного формирования реплики в регулярном DM‑дереве.
Теорема 3. Пусть T ‑ регулярное DM‑дерево высоты 
. Пусть фрагмент располагается на диске . Пусть M поддерево дерева T такое, что 
и . Пусть ‑ произвольное смежное с M поддерево дерева T; ‑ реплика фрагмента , размещенная на диске . Обозначим 
‑ трудоемкость покортежного формирования реплики при отсутствии помех. Тогда
,
где 
‑ коэффициент трудоемкости корня дерева T.
Доказательство. Организуем конвейерную передачу кортежей с диска на диск в соответствии с моделью операционной среды из [7]. Скорость работы конвейера определяется самым медленным узлом. Так как M и являются смежными поддеревьями, их корневые узлы имеют общего родителя уровня 
, который в соответствии с и будет самым медленным звеном конвейера. Следовательно, трудоемкость передачи одного кортежа при полностью запущенном конвейере равна 
. Отсюда
.
Здесь 
обозначает верхнюю границу для времени, необходимого для полного «разгона» конвейера в предположении, что высота дерева T является константой.
Так как T регулярно, то 
. На основании этого из получаем
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
