Оптимальное вторичное индексирование

Будем выделять в структуре файла первичный ключ н атрибуты, которые могут служить для построения вторичного индекса (вторичные ключи). Если ключ является многоатрн- бутным, то по его отдельным атрибутам может существовать вторичный индекс.

Нам известны типы запросов к файлу (определяемые ат- рнбутами-входами запроса) и допустимые для файла стратегии поиска (определяемые именами вторичных ключей).

Затраты времени на реализацию поиска и корректировки данных в файле будем выражать количеством прочитанных или записанных блоков информации, предполагая, что длина блока одинакова и в основном файле, н в файлах-индексах. Обозначим через c(ij) количество прочитанных блоков для удовлетворения j-ro типа запроса прн помощи і-й стратегии поиска. Очевидно, что стратегия не способна удовлетворить запрос, еслн атрибуты-входы запроса и вторичные ключи не содержат общих имен.

В этом случае c(i j) равно количеству блоков информации в основном файле. Формулы для расчета числа блоков обычно приводятся в технической документации на СУБД н чаще всего имеют внд

ML/B,

где M,L - число записей в основном массиве и длина записи в байтах, В - размер блока в байтах. ~

Когда атрибуты-входы запроса н вторичные ключи содержат общие имена, формулы для c(i j) сильно зависят от состава общих имен. Пусть общим является атрибут А(х) с количеством различных значений т(х) н длиной значения 1(х). Количество блоков в файле-нндексе, построенном по атрибуту А(х), обозначим через п(х).

Формулы для расчета п(х) сильно различаются у разных СУБД из-за многообразия способов реализации индекса. Здесь будет использоваться формула

n(x) = (m(x)l(x) + МЧ)/В, где і - длина адресной ссылки на запись основного файла.

Величина c(i j) определяется количеством чтений индекса (log п(х) или (п(х) + 1)/2 в зависимости от способа доступа) и количеством чтений из основного файла. Пренебрегая возможностью нахождения нескольких записей-целей в одном блоке, получаем выражение для числа считываемых блоков в виде r(j,x)*M/m(x). Если в условии j-запроса указано точное значение атрибута искомых записей, то r(j,x) = 1, если задается диапазон значений, то r(j,x) равно количеству значений в этом диапазоне. Итак,

c(ij) = log n(x) + r(j,x)*M/m(x).

Корректировка данных в файле разделяется на включение/исключение запнсн и замену значення атрибута в записи. Количество обрабатываемых блоков прн включении c'(i) = log п(і) + 1, прн исключении с"(і) = с'(і).

При рассмотрении корректировок в файле с индексами надо различать внесение изменений в запись с известным значением первичного ключа (собственно корректировка) н по известному значению вторичного ключа (доступ через индекс). В первом случае необходимо ввести дополнительный параметр с'(і,к). Он представляет собой количество обрабатываемых блоков для k-го типа обновления прн помощи і-й стратегии поиска.

Во всех указанных формулах округление производится после каждого действия в большую сторону. Для существующих типов запросов вводятся соответствующие вероятности q(j), аналогичные вероятности u(k) к = l...s описывают варианты обновлений. Вероятность включення записи обозначается через I, вероятность исключения - через D.

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

min F(i) = Iq(j)c(ij) + I u(k)c'(i,k) + Ic'(i) + Dc"(i).

Время внесения изменений в основной файл предполагается постоянным н поэтому в F(i) не входит.

Дополнительно должно соблюдаться соотношение

q(i) + u(k) +1 + D = 1.

Переменная і описывает возможные стратегии поиска. Максимальное число стратегий составляет 2AN-1, где N - число атрибутов, которые могут быть использованы прн вторичном индексировании.

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

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

ВОПРОСЫ И ЗАДАНИЯ 1.

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

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

Во многих задачах, где взаимосвязь данных соответствует понятию сети, числовые значения приписываются не вершинам сети, а ее дугам. Как представить УТИ данные в воде таблицы? Можно ли значения дуг передать вершинам и какие неудобства это вызовет?

.4. Какова вероятность того, что массив из М записей случайно окажется упорядоченным? 5.

Изобразите однонаправленные и двунаправленные представления в памяти ЭВМ следующих списков:

а) ((a,b),(c,a),d)

б)((a,(b,c)),(d)) 6.

Для последовательного массива и упорядоченного бинарного дерева известен алгоритм поиска по совпадению. Как использовать этот алгоритм для поиска по условию p(i)>q?