ТОРА (9) - Семинар №7 - Синтез хорошей БД: различия между версиями
Перейти к навигации
Перейти к поиску
ILobster (обсуждение | вклад) мНет описания правки |
ILobster (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
{{Backward|l=ТОРА (9) - Семинар №6 - Синтез хорошей БД}} | {{Backward|l=ТОРА (9) - Семинар №6 - Синтез хорошей БД}} | ||
__TOC__ | |||
== Продолжение решения ДЗ №2 == | |||
Продолжаем решать [[ТОРА (9) - Семинар №5 - Синтез хорошей БД#Вторая задача | вторую задачу второго ДЗ]]. Начало решения - в предыдущем семинаре. | Продолжаем решать [[ТОРА (9) - Семинар №5 - Синтез хорошей БД#Вторая задача | вторую задачу второго ДЗ]]. Начало решения - в предыдущем семинаре. | ||
Строка 106: | Строка 109: | ||
[[Файл:9sTORAs7pic4.png|500px|center]] | [[Файл:9sTORAs7pic4.png|500px|center]] | ||
== ДЗ №3 == | |||
Пусть на сервер базы данных поступает оператор <code>SELECT</code>, соответствующий следующему запросу: "''Выдать имена поставщиков из Лондона, которые поставляют для изделия с номером {{Формула|f=J1}}, по крайней мере, одну красную деталь''". | |||
Схема базы данных (таблицы {{Формула|f=S}}, {{Формула|f=P}}, {{Формула|f=J}}, {{Формула|f=SPJ}}) в виде ER-диаграммы: | |||
[[Файл:9sTORAs7pic5.png|center|500px]] | |||
Схема базы данных: {{Формула|f=\rho = (S, P, J, SPJ)}}. | |||
здесь: | |||
:{{Формула|f=S}} - таблица "Поставщик", описывающая поставщиков деталей. Имеет следующие поля: | |||
:* <u>номер поставщика</u> - идентификационный номер поставщика (ключевое поле); | |||
:* имя - фамилия, имя и отчество поставщика; | |||
:* состояние - состояние поставщика (состояние счета); | |||
:* город - город, в котором проживает поставщик и в котором находится его центральный офис. | |||
:{{Формула|f=P}} - таблица "Деталь". Описывает поставляемые детали и включает следующие поля: | |||
:* <u>номер детали</u> - идентификационный номер детали (ключевое поле); | |||
:* название - название детали; | |||
:* цвет - цвет детали; | |||
:* вес - все детали в фунтах; | |||
:* город - город, в котором изготавливается деталь. | |||
:{{Формула|f=J}} - таблица "Изделие". Описывает изготавливаемые изделия и включает следующие поля | |||
:* <u>номер изделия</u> - идентификационный номер изделия (ключевое поле); | |||
:* название - название изделия; | |||
:* город - город, где изготавливается изделие. | |||
:{{Формула|f=SPJ}} - таблица "Сборка". Имеет следующие поля: | |||
:* <u>номер поставщика</u> — идентификационный номер поставщика, поставляющего деталь (ключевое поле); | |||
:* <u>номер детали</u> - идентификационный номер детали, поставляемой поставщиком (ключевое поле); | |||
:* <u>номер изделия</u> - идентификационный номер изделия, в которое входит деталь, поставляемая поставщиком (ключевое поле); | |||
:* количество - количество деталей, поставляемых поставщиком для данного изделия (количество деталей в поставке). | |||
<u>Задание</u>: | |||
# Написать соответствующий оператор <code>SELECT</code> и построить логический план выполнения этого оператора. | |||
# Определить оптимальный физический план выполнения оператора <code>SELECT</code> при следующих исходных данных: | |||
::1) Количество записей в таблицах: | |||
:::{{Формула|f=T(S)=10000}}, {{Формула|f=T(P)=100000}}, {{Формула|f=T(SPJ)=1000000}}. | |||
::2) Количество записей в одном блоке таблицы: | |||
:::{{Формула|f=L_s=500}}, {{Формула|f=L_p=500}}, {{Формула|f=L_{SPJ}=1000}}, {{Формула|f=L_{JOIN}=2000}}. | |||
::3) Индексы по атрибутам и число записей таблицы в одном блоке индекса ({{Формула|f=L}}): | |||
::таблица {{Формула|f=S}}: | |||
:::* индекс по атрибуту "номер поставщика", {{Формула|f=L=200}}; | |||
::таблица {{Формула|f=Р}}: | |||
:::* индекс по атрибуту "номер детали", {{Формула|f=L=200}}; | |||
:: таблица {{Формула|f=SPJ}}: | |||
:::* индекс по атрибуту "номер поставщика", {{Формула|f=L=200}}; | |||
:::* индекс по атрибуту "номер детали", {{Формула|f=L=200}}; | |||
:::* индекс по атрибуту "номер изделия", {{Формула|f=L=200}}. | |||
::<span style="color:blue">''Примечания:'' | |||
:::* ''записи таблиц могут читаться в отсортированном виде по своим индексированным атрибутам''; | |||
:::* ''записи во всех таблицах не сгруппированы (нет кластеризации).''</span> | |||
::4) Мощности атрибутов: | |||
::* {{Формула|f=I(S, город) = 50}}, {{Формула|f=I(S, номер\_ поставщика) = 10000}}; | |||
::* {{Формула|f=I(Р, цвет) = 20}}, {{Формула|f=I(Р, номер\_ детали) = 100000}}; | |||
::* {{Формула|f=I(SPJ, номер\_ поставщика) = 5000}}, {{Формула|f=I(SPJ, номер\_ детали) = 100000}}, {{Формула|f=I(SPJ, номер\_ изделия) = 10000}}. | |||
::5) Число блоков {{Формула|f=b=10}}, значения {{Формула|f=C_{comp} = C_{move} = C_{filter} = 0.01}} мс, {{Формула|f=C_B = 10}} мс. | |||
::6) Предполагается, что используются левосторонние деревья для поиска оптимального плана и применяются каналы. | |||
::<span style="color:blue">''Примечание: метод хешированного соединения не рассматривать.''</span> | |||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]] | [[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]] | ||
[[Категория:Конспекты лекций и семинаров]] | [[Категория:Конспекты лекций и семинаров]] |
Версия от 17:43, 8 декабря 2012
...начало
Продолжение решения ДЗ №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 KKDELTVXBPRS$$ |
$$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$$ - таблица "Сборка". Имеет следующие поля:
- номер поставщика — идентификационный номер поставщика, поставляющего деталь (ключевое поле);
- номер детали - идентификационный номер детали, поставляемой поставщиком (ключевое поле);
- номер изделия - идентификационный номер изделия, в которое входит деталь, поставляемая поставщиком (ключевое поле);
- количество - количество деталей, поставляемых поставщиком для данного изделия (количество деталей в поставке).
Задание:
- Написать соответствующий оператор
SELECT
и построить логический план выполнения этого оператора. - Определить оптимальный физический план выполнения оператора
SELECT
при следующих исходных данных:
- 1) Количество записей в таблицах:
- $$T(S)=10000$$, $$T(P)=100000$$, $$T(SPJ)=1000000$$.
- 1) Количество записей в таблицах:
- 2) Количество записей в одном блоке таблицы:
- $$L_s=500$$, $$L_p=500$$, $$L_{SPJ}=1000$$, $$L_{JOIN}=2000$$.
- 2) Количество записей в одном блоке таблицы:
- 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$$.
- 4) Мощности атрибутов:
- 5) Число блоков $$b=10$$, значения $$C_{comp} = C_{move} = C_{filter} = 0.01$$ мс, $$C_B = 10$$ мс.
- 6) Предполагается, что используются левосторонние деревья для поиска оптимального плана и применяются каналы.
- Примечание: метод хешированного соединения не рассматривать.