Лекция 12. Использование и функционирование РБД
Особенности использования РБД связаны со спецификой запросов. Функционирование РБД характеризуется особенностями обеспечения одновременного доступа, защиты, восстановления данных, определяемых используемой СУБД.
Перейдем к детальному изучению специфики названных процессов.
Запросы
Если структура запросов заранее известна (стандартна), эффективность процесса запроса определяется на описанных ранее этапах фрагментации и локализации [11].
Если же структура запросов неизвестна, возникает необходимость оптимизации процесса запросов. Это особенно актуально при наличии параллельной обработки данных.
Целями (целевыми функциями) оптимизации могут быть:
• минимум времени передачи данных;
• минимум времени обработки данных в узлах;
• увеличение параллельности при обработке и передачах данных;
• улучшение трафика и загрузки процессоров в сети;
• минимум стоимости (задержки) только передачи данных (если имеются низкоскоростные каналы связи);
• минимум стоимости локальной обработки (если скорость передачи данных соизмерима с быстродействием процессора);
• выравнивание нагрузки компьютеров.
Для характеристики затрат на запросы введем два параметра: стоимость обработки и задержку данных.
Стоимость ТС обработки данных объема х, пересылаемых в узел i из узлов j, связанной с эксплуатацией физических каналов связи, составляет
где– определяемые системой матрицы стоимости установления связи и передачи единицы информации (
).
Задержка TD(x) – время между началом и окончанием обработки запроса:
где– матрицы времени установления связи и передачи единицы информации.
Примем такие предположения:
1) каналы связей однородны ();
2) стоимость передачи высока, и затратами на локальную обработку можно пренебречь (учитываются параметры только передачи данных).
Оптимизацию запроса можно разделить на два этапа:
1) глобальную оптимизацию, которую далее будем называть просто оптимизацией;
2) локальную оптимизацию, проводимую методами, описанными в гл. 4 и здесь не рассматриваемыми.
Для описания сути оптимизации используется аппарат реляционной алгебры (РА) с ее эквивалентными преобразованиями, позволяющими в результате сократить время ответа на запрос. Переменными оптимизации могут служить выбор физических копий и назначение узлов при выполнении операций РА.
Снова используем дерево запросов, в котором каждому из листов соответствует отношение, каждой вершине – операция РА. Конечной вершине соответствует узел РБД (локальная БД), а ответу на вопрос – корневая вершина.
Операции реляционной алгебры (селекция S или о, проекция Р или π, соединение J, объединение UN, разность DF, декартово произведение СР) и связывающие их законы описаны в гл. 4 данной работы. Полусоединение SJ рассмотрено в этой главе.
Возможно строгое решение задачи оптимизации, чаще всего сводящееся к задаче целочисленного программирования. Однако при ее решении встречаются серьезные затруднения (большой объем данных задачи и потребность значительного свободного ресурса, дефицит времени решения) и выигрыш по сравнению с эвристическими алгоритмами, как правило, невелик. К тому же на решение влияют такие трудно учитываемые факторы, как топология сети, протоколы передачи данных, модели и схема размещения данных.
Поэтому воспользуемся эвристическим подходом к оптимизации.
Стоимость и время пересылки данных можно сокращать за счет снижения объема передаваемой информации. В этой связи возможны следующие рекомендации.
1. Унарные операции необходимо выполнить как можно ранее (в узлах), как это показано на рис. 12.1, где S и J – унарные операции.
2. Многократно встречающиеся выражения лучше выполнить один раз. Для этого в дереве запроса проводится слияние листьев- отношений, затем – слияние одинаковых промежуточных операций (рис. 12.2). Здесь используется очевидное выражение
3. Использовать полусоединения. Идея полусоединения показана на рис. 12.3. При традиционной схеме либо R надо пересылать в узел 2, либо S – в узел 1. Можно пересылать лишь один раз S, сокращенную в помощью проекции, в узел I и затем осуществлять полусоединение. Покажем сказанное на примере.
Рис. 12.1. Использование унарного оператора в конце (а) и в начале (б) преобразования
Рис. 12.2. Выделение общих подвыражений: а – исходный запрос; б – промежуточный запрос; в – преобразованный запрос
Пусть даны следующие отношения:
Имеются следующие возможности:
а) переслать S из узла 2 в узел 1 (24 значения);
б) вычислить r' = Рв(r) в узле 1 и переслать его в узел 2, где вычислить s' = J(r', s) и отправить в узел 1. Там найти J(r, s) как J(r, s'), т. е. получить полусоединение. Передается уже 9 + 6 =15 значений.
Рис. 12.3. Использование полусоединения
Напомним, что полусоединение r и s или SJ(r, s) есть PR(J(r, s)), R Î r. Если отношения r и s находятся в разных узлах, то вычисление полусоединения уменьшает объем передаваемых данных. Заметим, что для полусоединения справедливо J(SJ(r, s), s).
Иногда полусоединение может полностью заменить соединение.
Отметим, что полусоединение чаще применяется при вертикальной фрагментации.
4. Стратегия использования копий (доступа). Она осуществляется на физическом уровне. Определить лучший вариант при их значительном количестве возможно только с помощью моделирования. Пусть учитываются только затраты передачи данных и имеются матрицы стоимости или времени передач. Значения матрицы могут быть определены точно, а размеры отношений – приближенно. Здесь, следовательно, необходимо использовать приближенные методы.
Вводят понятие "профиль", который включает:
• мощность (количество полей) отношения R;
• "ширину" (число байт) любого атрибута;
• число различных значений атрибута в отношении R.
Используют метод оценки размеров промежуточных отношений для каждой операции реляционной алгебры.
Для решения вопроса о выборе копий и назначении узлов выполнения удобно строить граф оптимизации, который не содержит унарных операций, выполняемых в узлах. Операции декартова произведения и разности встречаются редко, чаше имеют место операции объединения и соединения.
Таким образом, задача оптимизации запроса отличается неоднозначностью решения.
Следует заметить, что задача оптимизации должна решаться регулярно и оперативно. Это требует от разработчика построения специальных программ и потому делается далеко не всегда.
Чаще отработанный алгоритм оптимизации закладывается при проектировании разработчиками СУРБД непосредственно в системе управления, при создании специальных программных продуктов в виде приложений или утилит.