Стратегия распределения данных
Отношение может быть физически разделено горизонтально (множество кортежей разделяется на подмножества в соответствии с паттерном локальных обращений), вертикально (множество атрибутов разделяется в соответсвии с особенностями различных приложений в разных местах) или на произвольные фрагменты с наличием перекрытия между ними или без перекрытия [Mahmoud et al. 1979].
В [Gavish and Segev 1983] описывается алгоритм оптимизации набора операций в горизонтально разделенной реляционной базе данных. Доказана вычислительная трудность проблемы и разработаны эвртистики для ее решения. В [Ullman 1982] описывается использование "сторожевых условий" ("guard conditions") для упрощения запросов в горизонтально разделенных базах данных путем определения значимых фрагментов. Работа с неразъединенными фрагментами только что началась [Maier and Ullman 1983].
Основное внимание в существующей литературе уделяется вертикально распределенным базам данным. В этом случае ограничение и проецирование могут выполняться локально; исследования концентрируются на оптимальной реализации и планирования соединений и других операций над несколькими отношениями. Основным средством, используемым в этом контексте, является операция полусоединения, описанная в разд. 4.3. Как обсуждалось, древовидные запросы можно полностью решить с использованием полусоединений. Для частного случая цепочных запросов существует эффективный алгоритм, вычисляющий оптимальное расписание полусоединений при известном коэффициенте сокращения каждого полусоединения [Chiu et al. 1981]. Аналогичные алгоритмы для общих древовидных запросов приводятся в [Chiu and Ho 1980 и Gouda and Dayal 1981]. Однако по причине вычислительной сложности точных методов обычно предпочитают использовать эвристические процедуры Bernstein et al. 1981; Chang 1982; Cheung 1982a; Yu and Chang 1983].
В некоторых ранних алгоритмах полусоединения не использовались. В [Wong 1977] использовалась процедура поиска экстремума для инкрементального совершенствования начального решения, обрабатывающего весь запрос в одном узле.
В [ Epstein et al. 1978] представлена модель для раздельной минимизации времени обработки или сетевого трафика для каждой операции в запросе. Не гарантируется глобальная оптимальность. Оптимизационный алгоритм в R* (распределенный вариант System R [Williams et al. 1982]) производит исчерпывающий поиск комбинаций из нескольких альтернативных стратегий соединения для запросов с несколькими соединениями. В пределах просранства поиска и ограничений оценок данных находится оптимальное решение [Daniels 1982; Daniels et al. 1982; Ng 1982; Selinger and Adiba 1970].
Как и в централизованном случае, многие алгоритмы распределенного выполнения запросов подвергаются критике либо за предположение о практичности использования слишком больших объемов статистической информации, либо за использование нереалистичных упрощений. В [Muthuswamy and Kerschberg 1983] описывается процедура получения детальной статистики база данных путем наблюдения за использованием базы данных. Вычислительная сложность проблемы оптимизации распределенных запросов приводит к тем же явлениям, которые мы наблюдали для централизованных запросов. Одна группа ислледователей занимается поиском оптимальных решений в частных случаях, в то время как другая использует общие эвристики, чтобы иметь возможность отвечать на все запросы. При наличии планов реализации распределенной СУБД проблема состоит в объединении обоих подходов однородным образом. В [Yu and Chang 1983] приводится хороший пример такой исчерпывающей стратегии, которая включает эффективную работу с фрагментами, репликацию данных и динамические планы доступа (при этом избегаются упомянутые выше ошибки статистических оценок).
