5. Свойства ddb: независимость от оборудования, независимость от операционных систем, прозрачность сети, независимость от баз данных.

Независимость от оборудования.

Это свойство означает, что в качестве узлов распределенной системы могут выступать компьютеры любых моделей и производителей.

Независимость от ОС.

Подразумевает многообразие ОС, управляемых узлами распределенной системы.

Прозрачность сети.

Спектр поддерживаемых конкретной СУБД сетевых протоколов не должен быть ограничением системы с РБД. В распределенной системе должны быть возможны любые сетевые протоколы.

Независимость от БД.

В распределенной системе могут мирно сосуществовать СУБД различных производителей и возможны операции поиска и обновления в БД различных моделей и форматов.

6. Обработка и оптимизация запросов.

Обработка запросов – это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня.

Оптимизация запросов – это процедура выбора наилучшей стратегии для реализации запросов из множества альтернатив.

Для централизованного СУБД весь процесс состоит обычно из 2х шагов:

• Декомпозиция запроса;

• Оптимизация запроса.

Декомпозиция запроса – это трансляция его с языка SQL в выражения реляционной алгебры. В ходе декомпозиции запрос подвергается семантическому анализу, при этом некорректные запросы отвергаются, а корректные упрощаются. Упрощение заключается в частности – в исключении избыточных предикатов, которые могли бы привнесены за счет использования представлений, а также исходя из требований безопасности и семантической целостности.

Упрощенный запрос преобразуется в алгебраическую формулу, например:

… where position=”manager” and position=”assistant” - такой предикат противоречив.

… where (position=”manager” and position=”assistant”) or salary>2000 – может быть заменен на:

… where salary>2000

Для заданного SQL запроса существует более чем одно алгебраическое представление. Качество алгебраического выражения определяется исходя из объема затрат, необходимых для его вычисления.

Традиционная процедура состоит в том, чтобы сначала транслировать SQL запрос в какое-нибудь выражение, а затем, применяя правила эквивалентных алгебраических преобразований получать из него другие алгебраические выражения до тех пор, пока не будет найдено наилучшее.

При поиске наилучшего выражения используется функция стоимости в соответствии с которой вычисляется сумма затрат, необходимых для выполнения запросов.

Пример: нужно получить имена всех менеджеров, работающих в Лондонских отделениях компании:

Select * from staff s, branch b where s.no=b.no and (s.position=”manager” and b.city=”London”)

Исходя из правил эквивалентных выражений функциональной алгебры запрос может быть записан в 3х вариантах:

1) σ(position=”manager”)and(city=”London”)and(staff.no=branch.no)(staff x branch)

2) σ(position=”manager”)and(city=”London”)(staff  branch)

3) (σ(position=”manager”) staff )  (σ(city=”London”) branch)

Пусть staff – 1000 кортежей, branch – 50 кортежей. 5 из 50 менеджеров управляют отделом в Лондоне. Сортировки по ключам и индексам нет, результаты любой операции записываются на диск.

Рассмотрим 1 вариант:

(1000+50) записей читаются;

1000*50 – запись операции декартова произведения на диск, и столько же чтение для проверки соответствия требуемому предикату.

(1000+50)+2*(1000*50)=101050 операций.

Рассмотрим 2 вариант:

(1000+50) записей читаются;

1000 – запись результата операции соединения (каждый сотрудник приписан 1 отделению), и столько же чтение для проверки соответствия требуемому предикату.

(1000+50)+2*1000=3050 операций.

Рассмотрим 3 вариант:

1000 – чтение таблицы staff для проверки соответствия требуемому предикату;

(50+5) – чтение отношений для последующей операции соединения;

50 – запись результата операции ограничения;

50 – чтение таблицы branch для проверки соответствия требуемому предикату;

5 – запись результата 2 операции ограничения.

1000+50+50+5+50+5=1160 операций.

В распределенной СУБД между шагами декомпозиции и оптимизации запроса включаются еще 2 действия:

• Локализация данных;

• Глобальная оптимизация запросов.

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

Сущности данного шага заключаются в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. При этом выделяются фрагменты реально участвующие в запросе, а запрос преобразуется в форме, где операции применяются уже не глобальным отношениям, а к фрагментам.

Правила фрагментации выражаются посредствам реляционных операций:

• Селекция для горизонтальной фрагментации;

• Проекция для вертикальной фрагментации.

Распределенные отношения реконструируются путем применения инверсии правил фрагментации – это называется программой локализации.

Программа локализации для горизонтальной фрагментации запроса – есть объединение его фрагментов. Для вертикально-фрагментированного запроса – есть соединение его фрагментов.

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

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

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

Путем перестановок операций в рамках фрагментного запроса можно получить множество эквивалентных планов его выполнения, среди которых ищется наилучший.

Оптимизатор запросов обычно представляется в виде 3х компонентов:

1) Пространство поиска – это множество альтернативных планов выполнения исходного запроса. Эти планы эквивалентны в том смысле, что они дают один и тот же результат, но различаются порядком и способами выполнения отдельных операций.

2) Модель стоимости – это способ оценивания стоимости реализации заданного плана. Для того, чтобы оценка была близка к реальности, модель стоимости должна учитывать свойства среды параллельных вычислений.

3) Стратегия поиска – способ обхода пространства поиска и выбора наилучшего плана. Она определяет, какие планы, и в каком порядке следует выбирать и оценивать.

В распределенной среде функция стоимости определяется в единицах времени и оценивает затраты таких ресурсов, как дисковое пространство, число обмена с дисками, время процессора, коммуникации и т.д. Обычно это некоторая взвешенная сумма затрат этих параметров (ресурсов).

Иногда в РСУБД применяется упрощенный подход, когда в качестве наиболее значимых рассматриваются лишь коммуникационные затраты. Это справедливо для глобальных сетей, где из-за ограниченной пропускной способности линий связи пересылки данных обходятся значительно дороже, чем при локальной обработке.

Важнейший аспект оптимизации запросов, это порядок выполнения соединений, которые являются самыми дорогостоящими операциями, поскольку его изменение может привести к ускорению на несколько порядков. Базовая методика для оптимизации последовательностей соединений заключается в применении оператора полусоединений.

Операция полусоединения R S

Определяет отношение, которое содержит кортежи отношения R, входящие в соединение отношений R и S.

Например: нужно выполнить соединение R1 R2, где R1S1, R2S2,

тогда R1 R2 = (R1 R2) R2.

Теперь результат можно получить с меньшими затратами. Для этого:

- вычисляем R' в узле S2: R’ = Пх(R2) в S2;

- передаем R' в узел S1: R' -> S1;

- вычисляем R'' в узле S1: R'' = R1 R’ в S1;

- передаем R'' в узел S2: R'' -> S2;

- окончательно вычисляем: R'' R2 в S2;

- передаем только часть, удовлетворяющую условиям.