ТОРА (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) Предполагается, что используются левосторонние деревья для поиска оптимального плана и применяются каналы.

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

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