Оптимальное вторичное индексирование
Будем выделять в структуре файла первичный ключ н атрибуты, которые могут служить для построения вторичного индекса (вторичные ключи).
Если ключ является многоатрн- бутным, то по его отдельным атрибутам может существовать вторичный индекс.Нам известны типы запросов к файлу (определяемые ат- рнбутами-входами запроса) и допустимые для файла стратегии поиска (определяемые именами вторичных ключей). Особое положение среди стратегий поиска занимает последовательный доступ к файлу, который не использует никаких индексных путей.
Затраты времени на реализацию поиска и корректировки данных в файле будем выражать количеством прочитанных или записанных блоков информации, предполагая, что длина блока одинакова и в основном файле, н в файлах-индексах. Обозначим через 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-го типа обновления прн помощи і-й стратегии поиска. Если обновление не затрагивает соответствующий индекс, то c'(i,k) = 0. Когда c'(i,k) # 0, то c'(i,k) = 2(log n(i) + 1).Во всех указанных формулах округление производится после каждого действия в большую сторону. Для существующих типов запросов вводятся соответствующие вероятности 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?
Еще по теме Оптимальное вторичное индексирование:
- ВТОРИЧНЫЕ ПОТРЕБНОСТИ ЛИЧНОСТИ
- 4.Вторичная обобщающая информация
- ПОСТАВЩИКИ ВТОРИЧНЫХ ИССЛЕДОВАНИЙ
- «Кризис вторичности» интернет-СМИ
- ВТОРИЧНЫЙ АНАЛИЗ ДАННЫХ ОПРОСА
- Вторичные механизмы четкой формулировки и закрепления основ
- 6. ПЕРВИЧНЫЕ И ВТОРИЧНЫЕ КАЧЕСТВА. РЕАЛЬНЫЕ И НОМИНАЛЬНЫЕ СУЩНОСТИ
- 1. Рынок первичного и вторичного жилья, технология проведения сделок
- БАД на основе вторичного животного сырья и морепродуктов
- Принцип оптимальности
- VII. 2. ПСИХОЛОГО-ПЕДАГОГИЧЕСКИЕ МЕТОДЫ ПРОФИЛАКТИКИ И КОРРЕКЦИИ ВТОРИЧНЫХ ОТКЛОНЕНИ
- 4.2.Э.1. Процедура прямого хода в алгоритме формирования оптимального расписания
- 11.1. Задача об оптимальном рационе питания
- Раздел VII. MEТОДЫ ПРОФИЛАКТИКИ И КОРРЕКЦИИ ВТОРИЧНЫХ ОТКЛОНЕНИЙ В ПСИХИЧЕСКОМ РАЗВИТИИ ДЕТЕЙ СО СПЕЦИАЛЬНЫМИ ОБРАЗОВАТЕЛЬНЫМИ ПОТРЕБНОСТЯМИ
- Оптимальная манера общения
- воспитательный потенциал ХУДОЖЕСТВЕННОГО ОБРАЗОВАНИЯ: ПОИСК ОПТИМАЛЬНЫХ ПУТЕЙ РЕАЛИЗАЦИИ