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

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

ΠA(σ_F(R₁×...×R_n)), где

от R₁ до R_n - это декартово произведение отношений, указанных за ключевым словом FROM;

σ_F - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом WHERE;

Π_A - это проекция селекции на множество атрибутов A, указанных за ключевым словом SELECT

1. выполняется оптимизация этой формулы.

Пусть условие F=f1∧...∧fn

Правила:

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

2. переместить каждую проекцию внутрь декартова произведения;

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

После выполнения этих трёх правил выражение Π_A(σ_F(R₁×...×R_n)) преобразуется к виду: ΠA(σF(Π_A1(σ_f1(R₁))×...×Π_An(σ_fn(R_n)))), здесь Π_Ai(σ_fi(R_i)) - подзапросы.

Полученную формулу можно представить в графическом виде - это и будет логический план выполнения запроса.

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

Построение физического плана

1. Последовательно строится множество физических планов на основе логического плана. Эти физические планы отличаются следующим:

• методом выбора записей из исходных таблиц (TableScan – чтение всех записей, IndexScan – чтение записей по индексу);

• порядком соединения промежуточных таблиц Qi (комбинация вариантов соединения таблиц);

• методом соединения таблиц (NLJ – метод вложенных циклов, SMJ – метод сортировки слияния, (Hash Join));

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

1. Задача: Проверить, является ли G покрытием F.

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

БИЛЕТ 17 (НЕ ПРОВЕРЯЛОСЬ)

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

Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3:

SELECT остаток

FROM R2

WHERE остаток > 1500 AND

номер_счёта IN(

SELECT номер_счёта

FROM R1

WHERE код_пользователя = 3

);

Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры:

Πостаток(σR2.о>1500∧R1.к−п=3∧R1.н−c=R2.н−с(R1×R2)) =

Πостаток(σR1.н−c=R2.н−с(σR2.о>1500∧R1.к−п=3(R1×R2))) =

Πостаток(σR1.н−c=R2.н−с(σR1.к−п=3 (R1)×σR2.о>1500(R2))) =

Πостаток(σR1.н−c=R2.н−с(Πостаток,R1.н−с,R2.н−с(σR1.к−п=3(R1) × σR2.о>1500(R2)) =

Πостаток(σR1.н−c=R2.н−с(ΠR1.н−с(σR1.к−п=3(R1)) × ΠR2.н−с,остаток(σR2.о>1500(R2)))).

Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.

Каждый из подзапросов - это промежуточные таблицы Q1 и Q2.

1) Q1:

Q2:

2) соединение Q1 и Q2 (естественное соединение):

декартово произведение:

соединение:

проекция:

Вот этот результат и передаётся от СУБД на рабочую станцию.

А теперь предположим, что таблицы R1 и R2 находятся на разных серверах. В этом случае, подзапросы Q1 и Q2 после оптимизации на сервере-оптимизаторе преобразуются в SELECT.

Q1:

SELECT R1.ном.сч

FROM R1

WHERE R1.код.польз = 3;

Q2:

SELECT R2.ном.сч, R2.ост

FROM R2

WHERE R2.ост > 1500;

Эти подзапросы направляются на сервера, где хранятся соответствующие таблицы, там они параллельно выполняются, результаты возвращаются серверу-оптимизатору, а от него - пользователю.

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

Исходные данные: схема базы данных =(EG, EKL)= (R1, R2) и множество функциональных зависимостей F=(EG, EKL).

БИЛЕТ 18

1. Методы выбора записей из исходных таблиц при построении оптимального физического плана выполнения запроса к базе данных. Формулы оценки стоимости выбора записей с использованием этих методов.

Чтение всех записей и фильтрация (TableScan + Filter)

Ф ормула стоимости:

CostΣ=C_CPU+C_IO

C_CPU=T(R)⋅C_filter

C_IO=B(R)⋅C_B

здесь:

T(R) - общее количество записей в таблице R;

C_filter - среднее время фильтрации одной записи;

B(R) - число физических блоков в таблице R;

C_B - время чтения/записи одного блока на диск.

Чтение записей из индекса и фильтрация (IndexScan + Filter)

Формула стоимости:

CostΣ=C_CPU+C_IO

C_CPU=T(R)I(R,a)⋅C_filter

Два варианта:

• д ля кластеризованного:

C_IO=B(Index(R,a))I(R,a)⋅C_B+B(R)⋅kI(R,a)⋅C_B. В кластеризованном индексе последовательность значений в индексе и в таблице совпадает;

• для индекса без кластеризации C_IO=B(Index(R,a))I(R,a)⋅C_B+T(R)⋅kI(R,a)⋅C_B. Последовательность в индексе и таблице не совпадает. Число в этом случае читаемых записей равно числу блоков. Или наоборот.

здесь:

T(R) - общее количество записей в таблице R;

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

C_filter - среднее время фильтрации одной записи;

B(Index(R,a)) - число блоков на листовом уровне индекса по атрибуту a;

C_B - время чтения/записи одного блока на диск;

B(R) - число физических блоков в таблице R;

k - мощность атрибута a в запросе (число разных значений, указанных в подзапросе y).

Определение k:

k=1, если y: a=const;

k=n, если y: a IN (C1...Cn), Ci=const;

k= диапазон значений, если y: a>=C1 AND a<=C2;

k= число атрибутов, удовлетворяющих образцу, если y: a LIKE 'чтонить'.

1. Задача: определить, обладает ли схема базы данных свойством соединения без потерь.

Исходные данные: схема базы данных =(AB, AC, BD) (подчёркнутые атрибуты – ключи схем отношений).

БИЛЕТ 19

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

Q=Π_A(σ_f(R))

Число кортежей в промежуточной таблице Q вычисляется по формуле:

T(Q)=T(R)⋅p, где:

Q - промежуточная таблица;

T(Q) - число кортежей в промежуточной таблице;

T(R) - число записей в исходной таблице R;

p - вероятность того, запись из таблицы R удовлетворяет условию F.

Расчёт p:

1. если f=F1⋂F2, то p=p1⋅p2;

2. если f=F1⋃F2, то p=p1+p2−p1⋅p2;

3. если f=¯F1, то p=1−p1.

Для i-ой вероятности: pi=k/I(R,a), здесь:

k - мощность атрибута a в запросе;

I(R,a) - мощность атрибута a в таблице R.

Пример

Допустим, T(R)=1000, I(R,a)=5, I(R,b)=10, I(R,c)=2, где a,b,c - положительные натуральные числа. И f=(a<3 OR b≥5) AND c=2. Найти T(Q).

Обозначим:

• a<3 как F1;

• b≥5 как F2;

• f=(a<3 OR b≥5) как F3;

• c=2 как F4.

1) F1⋃F2=F3: p3=p1+p2−p1⋅p2=2/5+6/10−2/5⋅6/10=0.76

2) f=F3⋂F4: p=p3⋅p4=0.76⋅1/2=0.38 – это вероятность того, что запись из R удовлетворяет условию f.

3) T(Q)=1000⋅0.38=380

1. Задача: удалить из F лишние функциональные зависимости, в оставшихся зависимостях редуцировать лишние атрибуты слева, для получившегося множества функциональных зависимостей построить условно неизбыточное покрытие (УНП).

Исходные данные: множество функциональных зависимостей F=(BD, DB, ABD, ADB, BCA, BCD, CDA, CDB, ABCD, ACDB, BCDA).

БИЛЕТ 20

1. Виды деревьев (порядок) соединения таблиц. Преимущества и недостатки. Канал обработки.

Левостороннее

Предположим, соединяются таблицы R,S,T,U:

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

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

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

• достаточно просто организивать каналы обработки - возможность передачи результата выполнения одной операции на вход другой через оперативную память (без сохранения на диск);

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

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

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