Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Недостатки:

• путём перебора порядков соединения можно выбрать квазиоптимальный план (потому что на самом деле вариантов перебора больше, чем n!, потому что правый аргумент - всегда таблица).

Кустовое

Тут таблицы могут соединяться в любом порядке.

Т ак что перебираются все возможные варианты соединения.

Преимущества:

• всегда выбирается оптимальный план.

Недостатки:

• если количество соединяемых таблиц велико, то перебор всех деревьев может занять много времени;

• могут возникнуть сложности в организации канала обработки, так как возрастают требования к объёму оперативной памяти. Чтобы реализовать соединение за один проход, в памяти должно храниться слишком много таблиц.

Правостороннее

П ри таком порядке левым аргументом каждого соединения является исходная таблица.

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

1. Задача: построить схему базы данных , используя алгоритм синтеза «хорошей» схемы базы данных; проверить, находятся ли схемы отношений базы данных  в нормальной форме Бойса-Кодда.

Исходные данные: универсальная схема отношений U=(A,B,C), множество функциональных зависимостей F=(AB, BC, CA).

БИЛЕТ 21

1. Метод вложенных циклов соединения таблиц (NLJ). Формулы оценки стоимости соединения с использованием метода NLJ.

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

Зависит от:

• используемого дерева соединения;

• назначения буферов ввода/вывода.

Если на 3 операции блоков будет больше b, то лишние сохраняются на диск.

Формулы оценки стоимости соединения NLJ

C_JOIN=C_CPU+C_I/O

C_CPU=T(Q2)⋅C_comp

C_I/O=C_I/O(Q2)⋅⌊B(Q1)b⌋

здесь:

T(Q1), T(Q2) оценка числа записей в таблицах подзапросов Q1 и Q2;

B(Q1) - число блоков ввода/вывода для получения таблицы Q1;

C_I/O(Q2) - время ввода/вывода для получения таблицы Q2;

b - число блоков в буферах 1 и 3 (из рисунка выше);

C_comp - время сравнения двух кортежей из Q1 и Q2 в оперативной памяти.

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

1. Задача: Проверить, обладает ли схема отношений R следующими аномалиями: избыточностью, потенциальной противоречивостью, аномалией включения записей и аномалией удаления записей. Почему? Если да, то выполнить нормализацию схемы отношений.

Исходные данные: схема отношений R= (индекс факультета, наименование факультета, код выпуска, количество выпущенных студентов)=(A, B, C, D), множество функциональных зависимостей F=(AB, BA, ACD).

БИЛЕТ 22

1. Метод сортировки-слияния соединения таблиц (SMJ). Алгоритм сортировки больших таблиц.

Соединение двух таблиц этим методом выполняется по следующим шагам:

1. соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через a;

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

Рассмотрим пример реализации второго шага.

Выполняется сравнение записей в таблицах Q1 и Q2, на которые указывают указатели. Перемещение указателей выполняется следующим образом:

• если выполняется условие <, то указатель перемещается в таблицу Q1;

• если выполняется условие >, то указатель перемещается в таблицу Q2;

• если выполняется условие =, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы Q2.

Результат соединения Q1 и Q2 получается уже отсортированным.

Механизм сортировки таблиц Q1 и Q2:

1. блоки таблицы R читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;

2. в буфер читаются ещё блоки.

Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Далее из 1-го файла уровня 1 записи читаются в 1-й блок буфера, из 2-го файла уровня 1 записи читаются во 2-й блок и т.д., и из b-го файла уровня 1 записи читаются в b-й блок. В каждом блоке записи уже отсортированы на предыдущем этапе. Поэтому сравниваются первые записи этих блоков по атрибуту сортировки (b сравнений). Запись с минимальным значением атрибута перемещается в файл (одно перемещение). Остальные записи соответствующего блока сдвигаются вверх (блок работает как стек). Затем снова сравниваются первые записи b блоков по атрибуту сортировки и т.д. Если записи в каком-либо блоке исчерпаны, то в этот блок подгружаются записи из связанного с ним файла. После обработки таким способом b файлов уровня 1 будет сформирован файл уровня 2, записи в котором отсортированы. Далее в блоки буфера подгружаются записи следующих b файлов уровня 1 и т.д. По аналогичной схеме объединяются файлы уровня 2 и т.д. В конце концов, будет сформирован один отсортированный результирующий файл.

1. Задача: проверить, находится ли схема отношений в третьей нормальной форме (3НФ), используя определение 3НФ. Если нет, то нормализовать эту схему, используя практические приёмы нормализации.

Исходные данные: схема отношений R(сотрудник) = (номер, ФИО, должность, оклад) = (A, B, C, D); функциональные зависимости F = (ABCD, CD).

БИЛЕТ 23

1. Метод хешированного соединения (HJ). Варианты реализации хешированного соединения. Асинхронное соединение таблиц в методе HJ.

Осуществляется по следующим шагам:

1. Выполняется хэш-функция, где a - атрибут соединяемых таблиц;

2. Записи соединяемых таблицы хэшируются, то есть создаются разделы (Ri и Si);

3. Выполняется соединение соответствующих разделов (Ri⋈Si) по алгоритму NLJ или SMJ.

Предположим, заданы две таблицы (после выполнения подзапросов).

По шагам:

1) в качестве хэш-функции выберем остаток от деления на 10: h(a)=a mod 10

2) Ri - подмножество номеров счетов из таблицы R, у которых значение хэш-функции равно i=0..9

Si - подмножество номеров счетов из таблицы S, у которых значение хэш-функции равно i=0..9

Представим эти разделы в виде таблицы. Будет 9 разделов.

Разделы соединяются по диагонали. Потому что если остатки от деления разные, то и номера счетов разные. Остальные смотреть не смысла, потому что разные остатки.

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

Реализация метода может быть различной.

Однопроходной вариант реализации

Разделы опорной таблицы R хранятся в оперативной памяти.

1. читаются блоки таблицы S из внешней записи;

2. для каждой записи из S выполняется хэширование атрибута соединения (i);

3. значение атрибута a сравниваются со значениями атрибута соединения в разделе Ri.

Двухпроходной вариант реализации

Оперативной памяти может не хватать. Число размеров (точнее, хэш-функция) подбирается так, чтобы максимальный раздел таблицы R помещался в оперативной памяти. При таком подходе после хэширования таблиц R и S все разделы сохраняются на диске.

1. подбирается хэш-функция;

2. хэширование таблицы;

3. раздел R0 целиком читается в оперативную память;

4. в оперативную память поблочно читается раздел S0;

5. для каждой записи раздела S0 значение атрибута a сравнивается со значением атрибута соединения в разделе R0;

6. считываются следующие разделы (R1, R2 и так далее).

Метод хэшированного соединения имеет важную особенность. В методах NLJ или SMJ соединяемые таблицы должны уже храниться на сервере перед выполнением соединения. А в этом методе соединение таблиц может выполняться асинхронно, по мере поступления записей с других серверов.

На серверах 1 и 2 выполняются подзапросы, а на сервере 0 выполняется соединение. Предположим, с сервера 2 на сервер 0 поступила очередная запись из таблицы S. При этом СУБД на сервере 0 выполняет следующие действия:

1. вычисляется хэш-функция для атрибута соединения;

2. значение атрибута соединения сравнивается со значениями атрибутов соединения из раздела R1. Если есть совпадения, то выводятся результаты соединения;

3. запись сохраняется в разделе Si.

4. и так далее.

1. Задача: построить схему базы данных, используя алгоритм синтеза «хорошей» схемы базы данных; проверить, обладает ли эта схема базы данных свойством соединения без потерь и свойством сохранения функциональных зависимостей, построить диаграмму сущность-связь.

Исходные данные: универсальная схема отношений U=(A,B,C), множество функциональных зависимостей F=(AB).

БИЛЕТ 24 (уж слишком нагороженно)

1. Алгоритм динамического программирования поиска физического плана с минимальной стоимостью для левостороннего дерева соединений. Пояснить алгоритм на примере соединения трёх таблиц.

Алгоритм:

Характеристики

Список файлов ответов (шпаргалок)