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

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Перейти к навигации Перейти к поиску
Версия для печати больше не поддерживается и может содержать ошибки обработки. Обновите закладки браузера и используйте вместо этого функцию печати браузера по умолчанию.

...начало

Продолжение решения ДЗ №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) Предполагается, что используются левосторонние деревья для поиска оптимального плана и применяются каналы.
Примечание: метод хешированного соединения не рассматривать.

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