Методология общесистемного проектирования

Размещено на http://www.allbest.ru/

14

Размещено на http://www.allbest.ru/

Курсовая работа

по курсу

Методология общесистемного проектирования

Задача 1

Постановка задачи.

Пусть задана универсальная схема отношений R:

R = A - курс, дисциплина,

B - преподаватель,

C - час начала занятия,

D - аудитория,

E - студент,

T - оценка

Пусть также задано множество функциональных зависимостей:

F= (

CDB	- в аудитории одновременно может быть только один преподаватель;
ACD	- каждый курс одновременно может читаться только в одной аудитории;
CEA	- каждый студент одновременно может слушать только один курс;
AB	- каждый курс ведет только один преподаватель;
CDA	- в аудитории в один и тот же момент времени может читаться только один курс;
CBD	- преподаватель в один и тот же момент времени может находиться только в одной аудитории;
AET	- по каждому курсу каждый студент имеет только одну оценку;
CED	- студент в один и тот же момент времени может находиться только в одной аудитории

Задача:

Построить с - хорошую схему БД.

1.1. Решение задачи.

1. Положим =0, где - множество схем отношений, которые образуют схему БД.

2. Определим минимальное покрытие G для F:

1) G = (CDB, ACD, CEA, AB, CDA, CBD, AET, CED)

2) A. Проверяем принадлежность XA замыканию (G - XA)⁺, где XA G:

a) CDB:

G - CDB = (ACD, CEA, AB, CDA, CBD, AET, CED)

(CD)⁺=CDAB => B (CD)⁺ => CD>B (G - CD>B) ⁺

Т.о. данная зависимость принадлежит замыканию (G - CDB)+, т.е.

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

G= (ACD, CEA, AB, CDA, CBD, AET, CED)

b) ACD:

G - ACD = (CEA, AB, CDA, CBD, AET, CED)

(AC)⁺=ACBD => D (AC)⁺ => ACD (G - ACD) ⁺

Т.о. данная зависимость принадлежит замыканию (G - ACD)+, т.е.

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

G= (CEA, AB, CDA, CBD, AET, CED)

c) CEA:

G - CEA = (AB, CDA, CBD, AET, CED)

(CE)⁺=CEDATB => A (CE)⁺ => CEA (G - CEA) ⁺

Т.о. данная зависимость принадлежит замыканию (G - CEA)+, т.е.

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

G= (AB, CDA, CBD, AET, CED)

d) AB:

G - AB = (CDA, CBD, AET, CED)

(A)⁺=A => B (A)⁺ => AB (G - AB)

Т.о. данная зависимость не принадлежит замыканию (G- AB)+, т.е. данная зависимость остается в G:

G= (AB, CDA, CBD, AET, CED)

e) CDA:

G - CDA = (AB, CBD, AET, CED)

(CD)⁺=CD => A (CD)⁺ => CDA (G - CDA) ⁺

Т.о. данная зависимость не принадлежит замыканию (G- CDA)+, т.е. данная зависимость остается в G:

G= (AB, CDA, CBD, AET, CED)

f) CBD:

G - CBD = (AB, CDA, AET, CED)

(CB)⁺=CB => D (CB)⁺ => CBD (G - CBD) ⁺

Т.о. данная зависимость не принадлежит замыканию (G- CBD)+, т.е. данная зависимость остается в G:

G= (AB, CDA, CBD, AET, CED)

g) AET:

G - AET = (AB, CDA, CBD, CED)

(AE)⁺=AEB => T (AE)⁺ => AET (G - AET) ⁺

Т.о. данная зависимость не принадлежит замыканию (G - AET)+, т.е. данная зависимость остается в G:

G= (AB, CDA, CBD, AET, CED)

h) CED:

G - CED = (AB, CDA, CBD, AET)

(CE)⁺= CE => D (CE)⁺ => CED (G - CED) ⁺

Т.о. данная зависимость не принадлежит замыканию (G - CED)+, т.е. данная зависимость остается в G:

G= (AB, CDA, CBD, AET, CED)

В дальнейшем замыкание атрибутов рассматривается для полученного G.

Б. Проверяем принадлежность ZA замыканию G, где Z X:

a) AB:

Данную функциональную зависимость рассматривать не будем, так как у неё в обеих частях только по одному атрибуту.

b) CDA:

Рассмотрим следующие две зависимости:

CA:

(C)⁺= C => A (C)⁺ => CA (G) ⁺. Следовательно, зависимость не заменяется

DA:

(D)⁺= D => A (D)⁺ => DA (G) ⁺. Следовательно, зависимость не заменяется

c) CBD:

Рассмотрим следующие две зависимости:

CD:

(C)⁺= C => D (C)⁺ => CD (G) ⁺. Следовательно, зависимость не заменяется

BD:

(B)⁺= B => D (B)⁺ => BD (G) ⁺. Следовательно, зависимость не заменяется

d) AET:

Рассмотрим следующие две зависимости:

AT:

(A)⁺= AB => T (A)⁺ => AT (G) ⁺. Следовательно, зависимость не заменяется

ET:

(E)⁺= E => T (E)⁺ => ET (G) ⁺. Следовательно, зависимость не заменяется

e) CED:

Рассмотрим следующие две зависимости:

CD:

(C)⁺= C => D (C)⁺ => CD (G) ⁺. Следовательно, зависимость не заменяется

ED:

(E)⁺= E => D (E)⁺ => ED (G) ⁺. Следовательно, зависимость не заменяется

Таким образом, G остается без изменений:

G= (AB, CDA, CBD, AET, CED)

3) Данный шаг не выполняется, так как в G нет зависимостей с одинаковой левой частью.

Итак, минимальное покрытие G для F:

G= (AB, CDA, CBD, AET, CED)

3. Получим множество схем отношений Q, заменив каждую зависимость VW из G на VW:

Q=(AB, CDA, CBD, AET, CED)

4. Так как ABCDET Q, оставляем без изменений и продолжаем выполнение алгоритма.

5. В Q вошли все атрибуты, следовательно остается без изменений.

6. Добавляем в все схемы отношений из Q:

=(AB,CDA,CBD,AET,CED).

7. Определяем ключ для R:

1) i:=0, x₀=ABCDET;

2) (BCDET)⁺=BCDETA=R => x₁= BCDET, i:=1;

3) i возросло;

4) (CDET)⁺=CDETAB=R => x₂= CDET, i:=2;

5) i возросло;

6) (DET)⁺=DETR;

(CET)⁺=CETDAB=R => x₃= CDE, i:=3;

7) i возросло;

8) (ET)⁺=ETR;

(CT)⁺=CTR;

(CE)⁺=CEDATBR => x₄= CE, i:=4;

9) i возросло;

10) (C)⁺=CR;

(E)⁺=ER;

11) i не возросло. Следовательно, x₄= CE - ключ схемы отношений R.

Так как ключ найден, то в качестве новой схемы отношений добавлять в какой-либо ключ для R не требуется.

Итак, получаем, что =(AB,CDA,CBD,AET,CED) - «хорошая» схема БД.

Подставляя исходные данные, получим пять таблиц искомой БД:

1. {читаемый курс, преподаватель}

2. {час начала занятия, аудитория, читаемый курс}

3. {час начала занятия, преподаватель, аудитория}

4. {читаемый курс, студент, оценка по курсу}

5. {час начала занятия, студент, аудитория}

Ответ:

=(AB,CDA,CBD,AET,CED) - «хорошая» схема БД.

Задача 2

Постановка задачи

Пусть задана грамматика арифметического выражения:

<Z>::=<E>

<E>::=<T>|<T>+<E>|T>-<E>

<T>::=<F>|<F>*<T>|<F>/<T>

<F>::=(<E>) | i

Здесь: +,-,*,/,(,) - операторы,

i- константа или идентификатор,

<Z>,<E>,<T>,<F>- нетерминальные символы.

Задача:

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

Решение задачи

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

r\s	+	-	*	/	(	)	\0
+	?>	?>	?<	?<	?<	?>	?>
-	?>	?>	?<	?<	?<	?>	?>
*	?>	?>	?>	?>	?<	?>	?>
/	?>	?>	?>	?>	?<	?>	?>
(	?<	?<	?<	?<	?<	?=	ошибка
)	?>	?>	?>	?>	ошибка	?>	?>

На основании таблицы отношений между операторами можно ввести следующие функции предшествования:

функция	+	-	*	/	(	)	\0
f	10	10	12	12	8	12	0
g	9	9	11	11	13	8	0

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

Спецификация программы

@Вход-строка арифметического выражения

@Выход-результат вычисления арифметического выражения

@Спецификация программы восходящего распознавателя для грамматики арифметического выражения

Создать стек stack1, stack2;

Создать символ S1, S2;

Создать число N1, N2, T;

1: считать символ строки и записать в S2;

ЕСЛИ S2?'+' И S2?'-' И S2?'*' И S2?'/' И S2?'(' И S2?')' И S2?'\0' ТО

поместить S2 в stack2;

перейти к метке 1;

КОНЕЦ ЕСЛИ

2: ЕСЛИ S2='+' ИЛИ S2='-' ИЛИ S2='*' ИЛИ S2='/' ИЛИ S2='(' ИЛИ S2=')' ИЛИ S2='\0'

считать последний из stack1 в S1;

ЕСЛИ f(S1) < g(S2) ТО

Поместить S2 в stack1;

Перейти к метке 1;

КОНЕЦ ЕСЛИ

ЕСЛИ f(S1) > g(S2) ТО

вызвать программу обработки S1;

считать последний из stack2 в N1;

считать последний из stack2 в N2;

ЕСЛИ S1 =`+' ТО

T = N1 + N2;

КОНЕЦ ЕСЛИ

ЕСЛИ S1 =`-' ТО

T = N1 - N2;

КОНЕЦ ЕСЛИ

ЕСЛИ S1 = `*' ТО з

T = N1 * N2;

КОНЕЦ ЕСЛИ

ЕСЛИ S1 = `/' ТО

T = N1 / N2;

КОНЕЦ ЕСЛИ

удалить S1 из stack1;

удалить N1 из stack2;

удалить N2 из stack2;

поместить T в stack2;

ЕСЛИ S1 = `\0' и stack1 пуст ТО

перейти к метке 3;

КОНЕЦ ЕСЛИ

Перейти к метке 2;

КОНЕЦ ЕСЛИ

ЕСЛИ f(S1) = g(S2) ТО

удалить S1 из stack 1;

перейти к метке 1;

КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

3: считать stack2 в T;

выйти с результатом T;

@Конец спецификации

Задача 3

Постановка задачи

Пусть задана схема БД с = (S, P, J, SPJ)

В схеме содержатся следующие таблицы, имеющие указанные поля:

S - Поставщик;

S = (номер_поставщика, имя, состояние, город)

P - Деталь;

P = (номер_детали, название, цвет, вес, город)

J - Изделие;

J = (номер_изделия, название, город)

SPJ - Сборка;

SPJ = (номер_поставщика, номер_детали, номер_изделия, количество деталей)

Задача:

Написать следующие запросы SQL:

1. Выдать номера изделий и названия городов, где они изготавливаются, такие, что второй буквой названия города является буква `е'.

2. Выдать номера деталей, поставляемых для какого-либо изделия поставщиком, проживающим в том же городе, где изготавливается это изделие.

3. Выдать номера поставщиков, поставляющих детали с номером `P1' для какого-либо изделия в количестве большим, чем средний объем поставок детали с номером `P1' для этого изделия.

4. Выдать номера изделий, для которых детали поставляет только поставщик с номером `S1'.

Решение задачи

SELECT номер_изделия, город

FROM J

WHERE город LIKE `_е%';

SELECT DISTINCT SPJ.деталь

FROM J, S, SPJ

WHERE S.номер=SPJ.поставщик AND J.номер=SPJ.изделие AND S.город=J.[город изготовления];

SELECT DISTINCT номер_поставщика

FROM SPJ SX

WHERE номер_детали = `P1' AND

количество>(SELECT AVG(количество)

FROM SPJ

WHERE номер_изделия = SX.номер_изделия AND

номер_детали = `P1');

SELECT DISTINCT номер_изделия

FROM SPJ SX

WHERE NOT EXISTS

(SELECT *

FROM SPJ

WHERE номер_изделия = SX.номер_изделия AND

номер_поставщика != `S1' );

Задача 4

Постановка задачи

Пусть заданы следующие отношения:

S - поставщик детали; S = (номер_поставщика, фамилия, состояние, город)

P - деталь; P = (номер_детали, название, цвет, вес, город)

J - изделие; J = (номер_изделия, название, город)

SPJ - поставщик, который поставляет детали для изделия в определенном количестве;

SPJ = (номер_поставщика, номер_детали, номер_изделия, количество)

Пусть на сервер базы данных поступает оператор SELECT, соответствующий следующему запросу: «Выдать имена поставщиков из Лондона, которые поставляют для изделия с номером `J1', по крайне мере, одну красную деталь».

1. Написать соответствующий оператор SELECT и построить логический план выполнения этого оператора.

2. Определить оптимальный физический план выполнения оператора при следующих исходных данных:

1) Количество записей в таблицах: T(S) = 10000, T(P) = 100000, T(SPJ) = 1000000;

2) Количество записей в одном блоке таблицы: L_J = 500, L_P = 500, L_Join = 2000, L_SPJ =1000;

3) Индексы по атрибутам и число записей таблицы в одном блоке индекса (L):

Таблица S - 1) индекс по атрибуту "номер поставщика", L=200

Таблица Р - 1) индекс по атрибуту "номер детали", L=200

Таблица SPJ - 1) индекс по атрибуту "номер поставщика", L=200

2) индекс по атрибуту "номер детали", L=200

3) индекс по атрибуту "номер изделия", L=200

Примечания:

- записи таблиц могут читаться в отсортированном виде по своим индексированным атрибутам;

- записи во всех таблицах не сгруппированы(нет кластеризации).

4) Мощности атрибутов:

I(S, город)=50, I(S, номер поставщика)=10000,

I(Р, цвет)=20, I(Р, номер детали)=100000,

I(SPJ, номер поставщика)=5000, I(SPJ, номер детали)=100000,

I(SPJ, номер изделия)= 10000

5) Число блоков b = 10, C_сomp = С_move = C_filter = 0.01 мс, С_в = 10 мс;

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

Примечание:

Метод хешированного соединения не рассматривать.

Решение задачи

Оператор SELECT, соответствующий исходному запросу:

SELECT имя

FROM S, P, SPJ

WHERE S.город = 'Лондон' AND

P.цвет = 'красный' AND

SPJ.номер_изделия = 'J1' AND

S.номер_поставщика = SPJ.номер_поставщика AND

P.номер_детали = SPJ.номер_детали ;

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

р _S.имя (у _{S.город='Лондон' AND} (S?P?SPJ)) .

_{P. цвет = 'красный' AND}

_{SPJ.номер_изделия = 'J1' AND}

_{S.номер_поставщика = SPJ.номер_поставщика AND}

_{P.номер_детали = SPJ.номер_детали}

программа запрос реляционный алгебра

Введем следующие обозначения для условий:

FS::= (S.город = 'Лондон')

FP::= (P.цвет = 'красный')

FSPJ::= (SPJ.номер_изделия = 'J1')

JFS::= (S.номер_поставщика = SPJ.номер_поставщика)

JFP::= (P.номер_детали = SPJ.номер_детали)

Оптимизируем приведенную выше формулу, используя законы реляционной алгебры:

р _S.имя (у _{FS AND FP AND FSPJ AND JFS AND JFP} (S?P?SPJ)) = р _S.имя (у _{JFS AND JFP} (у _{FS AND FP AND FSPJ} (S?P?SPJ)) = р _S.имя (у _{JFS AND JFP} (у _FS(S) ? у _FP(P) ? у _FSPJ(SPJ))) =

= р _S.имя (у _{JFS AND JFP} (р _S.имя, (у _FS(S) ? у _FP(P) ? у _FSPJ(SPJ)))) =

_{S.номер_поставщика,}

_{P. номер_детали,}

_{SPJ.номер_поставщика,}

_{SPJ.номер_детали}

= р _S.имя (у _{JFS AND JFP} (р _S.имя, (у _FS(S)) ? р _{P. номер_детали}(у _FP(P)) ? р _{SPJ.номер_поставщика,}(у _FSPJ(SPJ)))) .

_{S.номер_поставщикаSPJ.номер_детали}

Заменяя введенные выше обозначения FS, FP, FSPJ, JFS и JFP соответствующими им условиями, получим следующий логический план выполнения запроса.

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

1) Таблица S.

j = 1 - чтение всей таблицы:

С₁ = С_CPU1+ С_I/O1= T(S)·C_filter + B(S)·C_B .

Учитывая, что B(S) = T(S) / L_S, и подставляя значения исходных данных, получим:

(мс).

j = 2 - чтение по индексу - не рассматривается, так как нет индекса по атрибуту "Город".

С = С₁ = 300 мс - стоимость выбора записей из таблицы S; метод выбора k=1.

С_I/O = С_I/O1 = 200 мс - составляющая ввода-вывода.

Определим характеристики таблицы Q₁, являющейся результатом выполнения подзапроса.

- число записей в таблице Q₁.

- число блоков в таблице Q₁.

I(Q₁, номер_поставщика) = min {T(Q₁), I(S, номер_поставщика)} = min {200, 10000} = 200 - мощность атрибута "Номер_поставщика" в таблице Q₁ (этот атрибут потребуется при соединении таблиц).

Заполним экземпляр структуры str[1]:

str[1]= { {Q₁}, O, O, // W, X, Y

300, 200,// Z, ZIO

{ 200, 1, {200}, 1}// V: T(Q₁), B(Q₁), {I(Q₁, номер_поставщика)}, k

}.

2) Таблица P.

j = 1 - чтение всей таблицы:

.

С₁ = 3000 мс

j = 2 - чтение по индексу - не рассматривается, так как нет индекса по атрибуту "Цвет".

С = С₁ = 3000 мс ; k=1.

С_I/O = С_I/O1 = 200 мс .

.

.

I(Q₂, номер_детали) = min {T(Q₂), I(P, номер_детали)} = min {5000, 100000} = 5000 .

Экземпляр структуры str[2]:

str[2]= { {Q₂}, O, O, // W, X, Y

3000, 2000,// Z, ZIO

{ 5000, 1, {5000}, 1}// V: T(Q₂), B(Q₂), {I(Q₂, номер_детали)}, k

}.

3) Таблица SPJ.

j = 1 - чтение всей таблицы:

j = 2 - чтение по индексу; используется индекс по атрибуту "Номер_изделия":

Здесь K=1 - мощность атрибута "Номер_изделия" в запросе, B(Index(номер_изделия)) - число блоков листьевого уровня индекса по атрибуту "Номер_изделия". Записи таблицы SPJ не сгруппированы по атрибуту "Номер_изделия", поэтому в последнее слагаемое входит T(SPJ).

С = min {С₁, C₂} = C₂ =1006 мс ; k=2.

С_I/O = С_I/O2 = 1005 мс .

.

.

I(Q₃, номер_поставщика) = min {T(Q₃), I(SPJ, номер_поставщика)} = min {100, 5000} = 100.

I(Q₃, номер_детали) = min {T(Q₃), I(SPJ, номер_детали)} = min {100, 100000} = 100 .

Экземпляр структуры str[3]:

str[3]= { {Q₃}, O, O, // W, X, Y

1006, 1005,// Z, ZIO

{ 100, 1, {100, 100}, 2}// V: T(Q₃), B(Q₃), { I(Q₃, номер_поставщика),

// I(Q₃, номер_детали)}, k

}.

Определение методов соединения

1) i = 2. Рассматриваем такие подмножества P множества таблиц {Q₁, Q₂, Q₃}, мощность которых равна 2. Подмножество {Q₁, Q₂} не рассматриваем, поскольку у таблиц Q₁ и Q₂ нет общих атрибутов и поэтому выполнять их соединение нецелесообразно.

2) Рассматриваем подмножество P={Q₁, Q₃}.

Q_j = Q₁.

R = P - Q_j = Q₃, S=Q₁ - аргументы соединения.

m₁=3, m₂=1 - номера экземпляров структуры str, соответствующих аргументам соединения.

а) Метод NLJ, i1=1.

б) Метод SMJ, i1=2.

Поскольку таблицы Q₃ и Q₁ уже отсортированы по атрибуту "Номер_поставщика" (имеются соответствующие индексы) и I(Q₃, номер_поставщика) < I(Q₁, номер_поставщика) (эти мощности равны 100 и 200 соответственно), получим:

Значение С_I/O^JOIN(Q₃, Q₁) равно 0, поскольку B(Q₁) < I(Q₁, номер_поставщика) (1 < 200).

С = min {С₁, C₂} = C₂ =4 мс ; k=2.

С_I/O = С_I/O2 = 0 .

Полученные значения C и C_I/O учитывают только соединение таблиц. Добавляя к ним стоимости получения аргументов соединения, получим:

C = str[3].Z + str[1].Z + C = 1006 + 300 + 4 = 1310 (мс);

С_I/O = str[3].ZIO + str[1].ZIO + С_I/O = 1005 + 200 + 0 =1205 (мс).

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

Число записей:

Число блоков:

.

Мощность атрибута соединения:

Мощность атрибута "Номер_детали", который потребуется для соединения данной таблицы с таблицей Q₂:

Экземпляр структуры str[4]:

str[4]= { {Q₁, Q₃}, {Q₃}, {Q₁}, // W, X, Y

1310, 1205,// Z, ZIO

{ 100, 1, {100, 100}, 2}// V: T(Q₃><Q₁), B(Q₃><Q₁),

// { I(Q₃><Q₁, номер_поставщика),

// I(Q₃><Q₁, номер_детали)}, k

}.

3) Q_j = Q₃.

R = P - Q_j = Q₁, S=Q₃ .

m₁=1, m₂=3 .

а) Метод NLJ, i1=1.

б) Метод SMJ, i1=2.

Таблицы Q₁ и Q₃ уже отсортированы по атрибуту "Номер_поставщика"; кроме того, I(Q₃, номер_поставщика) < I(Q₁, номер_поставщика), поэтому

Значение С_I/O^JOIN(Q₁, Q₃) равно 0, поскольку B(Q₃) < I(Q₃, номер_поставщика) (1 < 100).

С = min {С₁, C₂} = C₂ =4 мс ; k=2.

С_I/O = С_I/O2 = 0 .

C = str[3].Z + str[1].Z + C = 1006 + 300 + 4 = 1310 (мс).

Это значение С совпадает с рассчитанным выше значением str[4].Z, поэтому экземпляр структуры str[4] не изменяется.

2) Рассматриваем подмножество P={Q₂, Q₃}.

Q_j = Q₃.

R = P - Q_j = Q₂, S=Q₃ .

m₁=2, m₂=3 .

а) Метод NLJ, i1=1.

б) Метод SMJ, i1=2.

Поскольку таблицы Q₂ и Q₃ уже отсортированы по атрибуту "Номер_детали" (имеются соответствующие индексы) и I(Q₃, номер_детали) < I(Q₂, номер_детали) (эти мощности равны 100 и 5000 соответственно), получим:

Значение С_I/O^JOIN(Q₂, Q₃) равно 0,

поскольку B(Q₃) < I(Q₃, номер_детали) (1 < 100).

С = min {С₁, C₂} = C₂ = 52 мс ; k=2.

С_I/O = С_I/O2 = 0 .

C = str[2].Z + str[3].Z + C = 3000 + 1006 + 52 = 4058 (мс);

С_I/O = str[2].ZIO + str[3].ZIO + С_I/O = 2000 + 1005 + 0 =3005 (мс).

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

.

Мощность атрибута соединения:

Мощность атрибута "Номер_поставщика", который потребуется для соединения данной таблицы с таблицей Q₁:

Экземпляр структуры str[5]:

str[5]= { {Q₂, Q₃}, {Q₂}, {Q₃}, // W, X, Y

4058, 3005,// Z, ZIO

{ 100, 1, {100, 100}, 2}// V: T(Q₂><Q₃), B(Q₂><Q₃),

// { I(Q₂><Q₃, номер_поставщика),

// I(Q₂><Q₃, номер_детали)}, k

}.

Q_j = Q₂.

R = P - Q_j = Q₃, S=Q₂ .

m₁=3, m₂=2 .

а) Метод NLJ, i1=1.

б) Метод SMJ, i1=2.

Таблицы Q₂ и Q₃ уже отсортированы по атрибуту "Номер_поставщика"; кроме того, I(Q₃, номер_ детали) < I(Q₂, номер_детали), поэтому

Значение С_I/O^JOIN(Q₃, Q₂) равно 0, поскольку B(Q₂) < I(Q₂, номер_детали) (1 < 5000).

С = min {С₁, C₂} = C₂ = 52 мс ; k=2.

С_I/O = С_I/O2 = 0 .

C = str[3].Z + str[2].Z + C = 3000 + 1006 + 52 = 4058 (мс).

Это значение С совпадает с рассчитанным выше значением str[5].Z, поэтому экземпляр структуры str[5] не изменяется.

1) i = 3. Рассматриваем подмножества P множества таблиц {Q₁, Q₂, Q₃}, мощность которых равна 3. Такое подмножество одно - это само множество {Q₁, Q₂, Q₃}.

P={Q₁, Q₂, Q₃}.

Q_j = Q₁.

R = P - Q_j ={Q₂, Q₃}, S=Q₁ .

m₁=5, m₂=1 .

а) Метод NLJ, i1=1.

б) Метод SMJ, i1=2.

Таблица Q₁ уже отсортирована по атрибуту "Номер_поставщика"; результат соединения таблиц Q₂ и Q₃ нужно отсортировать.

Соотношение мощностей атрибутов:

I(Q₂><Q₃, номер_поставщика) < I(Q₁, номер_ поставщика) (100 < 200 соответственно).

Исходя из этого, рассчитываем стоимость соединения следующим образом:



Значение С_I/O^JOIN(Q₂><Q₃, Q₁) равно 0, поскольку B(Q₁) < I(Q₁, номер_поставщика) (1 < 200).

Подставляя числовые значения величин, получим:

Слагаемое, содержащее множитель (log _bB(Q₂><Q₃) - 1), не учитываем, поскольку B(Q₂><Q₃) = 1.

С = min {С₁, C₂} = C₂ = 17 мс ; k=2.

С_I/O = С_I/O2 = 0 .

C = str[5].Z + str[1].Z + C = 4058 + 300 + 17 = 4375 (мс);

С_I/O = str[5].ZIO + str[1].ZIO + С_I/O = 3005 + 200 + 0 =3205 (мс).

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

.

Мощность атрибута соединения:

Экземпляр структуры str[6]:

str[6]= { { Q₁, Q₂, Q₃}, { Q₂, Q₃}, {Q₁}, // W, X, Y

4375, 3205,// Z, ZIO

{ 100, 1, {100}, 2}// V: T(Q₂><Q₃><Q₁), B(Q₂><Q₃><Q₁),

// { I(Q₂><Q₃><Q₁, номер_поставщика)}, k

}.

Q_j = Q₂.

R = P - Q_j ={Q₁, Q₃}, S=Q₂ .

m₁=4, m₂=2 .

а) Метод NLJ, i1=1.

б) Метод SMJ, i1=2.

Таблица Q₂ уже отсортирована по атрибуту "Номер_детали"; результат соединения таблиц Q₁ и Q₃ нужно отсортировать.

Соотношение мощностей атрибутов:

I(Q₁><Q₃, номер_детали) < I(Q₂, номер_детали) (100 < 5000).

Исходя из этого, рассчитываем стоимость соединения следующим образом:



Слагаемое, содержащее множитель (log _bB(Q₁><Q₃) - 1), не учитываем, поскольку B(Q₁><Q₃) = 1.

Значение С_I/O^JOIN(Q₁><Q₃, Q₂) равно 0, поскольку B(Q₂) < I(Q₂, номер_детали) (1 < 5000).

С = min {С₁, C₂} = C₂ = 65 мс ; k=2.

С_I/O = С_I/O2 = 0 .

C = str[4].Z + str[2].Z + C = 1310 + 3000 + 65 = 4375 (мс).

Это значение С совпадает с рассчитанным выше значением str[6].Z, поэтому экземпляр структуры str[6] не изменяется.

Оптимальный план найден.

Выводы

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

(Q₁, Q₂, Q₃) = (Q₂, Q₃) >< Q₁, метод SMJ

(Q₂, Q₃) = Q₂ >< Q₃, метод SMJ

Q₂ = метод TableScan(P) + Filter(P.цвет = 'красный', р_{P.номер_детали})

Q₃ = метод IndexScan(SPJ, номер_изделия = 'J1') + Filter(р_{SPJ.номер_поставщика, SPJ.номер_детали})

Q₁ = метод TableScan(S) + Filter(S.город = 'Лондон', р_{S.имя, S.номер_поставщика})

Размещено на Allbest.ru