ТОРА (9) - Семинар №7 - Синтез хорошей БД

...начало

Продолжение решения ДЗ №2

Продолжаем решать вторую задачу второго ДЗ. Начало решения - в предыдущем семинаре.

4) разбиваем на классы эквивалентности:

$$A\rightarrow CNO$$	-	$$K_1 = ACNO$$
$$B\rightarrow PRS$$	-	$$K_2 = BPRS$$
$$AD\rightarrow CNOXVTBPRSE$$	-	$$K_3 = ACDNOXVTPRSE$$
$$K\rightarrow DELTVXBPRS$$	-	$$K_4\rightarrow KDELTVXBPRS$$
$$L\rightarrow T$$	-	$$K_5 = LT$$
$$X\rightarrow VT$$	-	$$K_6 = XVT$$
$$ET\rightarrow V$$	-	$$K_7 = EVT$$
$$D\rightarrow XEBPRSVT$$	-	$$K_8 = DXEBPRSVT$$
$$ABCDEKLNOPRSTVX\rightarrow\varnothing$$	-	$$K_9 = ABCDEKLNOPRSTVX$$

5) граф классов эквивалентности:

6) редуцируем:

7)

смотри граф.

8)

$$AD\rightarrow\varnothing$$

9)

$$\rho = (ACNO, XVT, BPRS, ETV, LT, DXBE, KDL, AK) = (R_1, R_2, R_3, R_4, R_5, R_6, R_7, R_8$$

10)

• проверяем свойство сохранения без потерь:

	$$A$$	$$B$$	$$C$$	$$D$$	$$E$$	$$K$$	$$L$$	$$N$$	$$O$$	$$P$$	$$R$$	$$S$$	$$T$$	$$V$$	$$X$$
$$ACNO$$	$$a$$		$$a$$					$$a$$	$$a$$
$$XVT$$													$$a$$	$$a$$	$$a$$
$$BPRS$$		$$a$$								$$a$$	$$a$$	$$a$$
$$ETV$$					$$a$$								$$a$$	$$a$$
$$LT$$							$$a$$						$$a$$
$$DXBE$$		$$a$$		$$a$$	$$a$$					$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$
$$KDL$$		$$a$$		$$a$$	$$a$$	$$a$$	$$a$$			$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$
$$AK$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$	$$a$$

получили строку, сплошь состоящую из $$a$$. Значит, схема обладает свойством соединения без потерь.

• проверяем свойство сохранения функциональных зависимостей:

$$УНП = (A\rightarrow CNO, B\rightarrow PRS, AD\rightarrow XCNOVTBPRSE, K\rightarrow DELTVXBPRS,$$

$$L\rightarrow T, X\rightarrow VT, ET\rightarrow V, D\rightarrow XBEVTPRS)$$

1-4)

$$H\neq\varnothing$$

5)

$$УНП - H = (A\rightarrow CNO, B\rightarrow PRS, K\rightarrow DL, L\rightarrow T, X\rightarrow VT, ET\rightarrow V, D\rightarrow XBE)$$

$$H = (AD\rightarrow CNOVTPRSXBE, K\rightarrow EXBTVPRS, D\rightarrow PPRSVT)$$

6)

$$AD\rightarrow^? CNOVTPRSXBE$$ да

$$(AD)^+ = ADCNOXBEPRSVT$$

$$K\rightarrow^? XBTEVPRS$$ да

$$(AD)^+ = KDLXBEVTPRS$$

$$D\rightarrow^? PRSVT$$ да

$$(AD)^+ = DXBEPRSVT$$

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

А теперь строим схему в нотации ERwin:

переделываем в схему с синтетическими ключами:

ДЗ №3

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

Схема базы данных (таблицы $$S$$, $$P$$, $$J$$, $$SPJ$$) в виде ER-диаграммы:

Схема базы данных: $$\rho = (S, P, J, SPJ)$$.

здесь:

$$S$$ - таблица "Поставщик", описывающая поставщиков деталей. Имеет следующие поля:

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

$$P$$ - таблица "Деталь". Описывает поставляемые детали и включает следующие поля:

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

$$J$$ - таблица "Изделие". Описывает изготавливаемые изделия и включает следующие поля

• номер изделия - идентификационный номер изделия (ключевое поле);
• название - название изделия;
• город - город, где изготавливается изделие.

$$SPJ$$ - таблица "Сборка". Имеет следующие поля:

• номер поставщика — идентификационный номер поставщика, поставляющего деталь (ключевое поле);
• номер детали - идентификационный номер детали, поставляемой поставщиком (ключевое поле);
• номер изделия - идентификационный номер изделия, в которое входит деталь, поставляемая поставщиком (ключевое поле);
• количество - количество деталей, поставляемых поставщиком для данного изделия (количество деталей в поставке).

Задание:

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

1) Количество записей в таблицах:

$$T(S)=10000$$, $$T(P)=100000$$, $$T(SPJ)=1000000$$.

2) Количество записей в одном блоке таблицы:

$$L_s=500$$, $$L_p=500$$, $$L_{SPJ}=1000$$, $$L_{JOIN}=2000$$.

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

таблица $$S$$:

• индекс по атрибуту "номер поставщика", $$L=200$$;

таблица $$Р$$:

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

таблица $$SPJ$$:

• индекс по атрибуту "номер поставщика", $$L=200$$;
• индекс по атрибуту "номер детали", $$L=200$$;
• индекс по атрибуту "номер изделия", $$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_{comp} = C_{move} = C_{filter} = 0.01$$ мс, $$C_B = 10$$ мс.

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

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

Пример решения можно посмотреть в последнем семинаре.