Экзаменационные ответы одним файлом (1038657), страница 7

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

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

Вход: логический план выполнения запроса с таблицами R1..R3 (декартово соединение таблиц).

Выход: квазиоптимальный (потому что рассматриваем левосторонние деревья) план выполнения запроса.

@НАЧАЛО АЛГОРИТМА

ДЛЯ i=1,3

AccessPlan(Ri); // определение параметров подзапроса Qi=ΠAi(Σfi(Ri)).

КОНЕЦ ДЛЯ

// поиск оптимального плана

ДЛЯ i=2,3

ДЛЯ всех подмножеств P⊂Q1..Q3,

// для i=2

// P=(Q1,Q2), P=(Q2,Q3), P=(Q1,Q3)

// для i=3

// P=(Q1,Q2,Q3) и так же все варианты комбинаций

ДЛЯ всех таблиц Qj∈P

JoinPlan(P−Qj,Qj) // (P−Qj)⋈Qj

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

// вывод оптимального плана

OptPlanReturn(Q1..Qn)

@КОНЕЦ АЛГОРИТМА

Процедуры алгоритма работают с массивом структур.

W:

если мощность W>1, то W⊂Qi, W=X⋃Y;

если мощность W=1, то W - это имя таблицы {Q_i}}}.

X:

X⊂Qi, которые были использованы в качестве левого аргумента соединения.

Y:

имя таблицы Qi, которая была использована в качестве правого аргумента соединения. Если мощность W=1, то X и Y пустые.

Z:

если W>1, Z - текущая стоимость выполнения плана, включающая стоимость выполнения подзапросов и промежуточных соединений;

если W=1, Z - оценка времени выполнения(?) Qi.

ZIO:

составляющая Z, касающаяся ввода/вывода.

V: опции; включает в себя:

1) число записей:

• если мощность W>1, то T(W) - число прогнозируемых записей;

• если мощность W=1, то T(Qi) - оценка числа записей в подзапросе;

2) B(W) - прогнозируемое число блоков;

3) I(W,Ai) - мощности атрибутов, по которым было выполнено или выполняется соединение;

4) идентификатор:

• если мощность W>1, то k - идентификатор метода соединения таблиц;

• если мощность W=1, то k - идентификатор метода выбора записей из исходных таблиц.

AccessPlan()

Вход: Ri - имя исходной таблицы.

Выход: str[i] - заполненный экземпляр структуры (описанной выше).

@НАЧАЛО АЛГОРИТМА

// оценка стоимости выбора записей из Ri для различных методов

// j=1 - TableScan

// j=2 - IndexScan

ДЛЯ i=1,2

Cj=C_CPU+C_I/O // для разных j разные формулы

КОНЕЦ ДЛЯ

// определение оптимального метода выбора записей из Ri

С=min(C1,C2) // здесь C=Ck

// заполнение экземпляра str[i]

str[i]=

{

Qi, ∅, ∅ // W, X, Y

C, CI/Ok // Z, ZIO

T(Qi),B(Qi),min(T(Qi),I(Ri,Ai)),k // V

}

@КОНЕЦ АЛГОРИТМА

JoinPlan()

Вход: R=(P−Qj), S=Q.

Выход: str[n].

@НАЧАЛО АЛГОРИТМА

1)

// поиск в массиве структур str[] номеров экземпляров m1 и m2, для которых str[m1].W=R и str[m2].W=S

// оценка стоимости соединения для различных методов

// если i=1, то NLJ

// если i=2, то SMJ

// если i=3, то HJ

// k - выбор оптимального из этих трёх

2)

ДЛЯ i=1,3

Ci=C_CPUi+C_I/Oi // для разных i разные формулы из предыдущих лекций

КОНЕЦ ДЛЯ

C=min(C1,C2) // стоимость соединения R и S

C=str[m1].Z+str[m2].Z+C

3)

// поиск str[n].W=P

// а) если такого экземпляра не существует, то заполнить очередной пустой экземпляр n.

// б) если такой экземпляр найден, то сравнить стоимость выполнения плана. И если str[n].Z>C, то перезаписать экземпляр n.

str[n]=

{

P, R, S // W, X, Y

C, CI/Ok // Z, ZIO

T(P),B(P),I(P,Ai)i,k // V

}

@КОНЕЦ АЛГОРИТМА

OptPlanReturn()

Вход: список таблиц Qi=Q1..Qn

Выход: вывод оптимального плана.

@НАЧАЛО АЛГОРИТМА

1)

// поиск в массиме структур str[] экземпляра, который str[i].W=Q

печать(Q, " = ", str[i].X, " ⋈ ", str[y].Y, " метод ", str[i].V.k)

2)

// если поле str[i].X пусто, то выйти из алгоритма

// иначе рекурсивно вызываем сами себя, OptPlanReturn(str[i].X) // вывод оптимального плана для левого аргумента соединения

3)

OptPlanReturn(str[i].Y) // вывод метода выбора записей из правого аргумента соединения

@КОНЕЦ АЛГОРИТМА

1. Задача: будет ли правильно выполняться запрос к базе данных?

Исходные данные: 1) схема базы данных = (AB, CA, DC) = (R1, R2, R3) (подчёркнутые атрибуты – ключи схем отношений), 2) запрос: select * from R1, R2, R3 where R1.A=R2.A and R2.C=R3.C;

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

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