Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

A+=AB, C+=C, B+=BA

Покажем, что в этом случае R находится в 3НФ:

1) не первичный атрибут H, H=D

2) Y→H, H∉Y, Y=AC

3) X=BC, X=AC

Нельзя подобрать нужную тройку, потому R находится в 3НФ. Однако, отношение всё равно обладает аномалиями:

• избыточности;

• противоречивости;

• включения;

• удаления.

Для устранения этого вводится усиленная 3НФ - Бойса-Кодда.

ФЗ X→Y является неприводимой, если для любого подмножества Z⊂X выполняется Z↛Y (или Z→Y∉F+).

Пусть есть отношение R и F включает в себя нетривиальные неприводимые ФЗ. Тогда отношение R находится в нормальной форме Бойса-Кодда, если для любого X→Y∈F => X - ключ.

1. Задача: нормализовать схему отношений, используя практические приёмы нормализации.

Исходные данные: схема отношений R(сотрудник) = (номер_сотрудника, ФИО, должность, оклад, номер_заказа) = (A, B, C, D, E); функциональные зависимости F = (AEBCD, ABCD, CD).

БИЛЕТ 12

1. Алгоритм синтеза «хорошей» схемы базы данных. Преимущества и недостатки алгоритма.

Пусть U - универсальная схема отношения (множество всех атрибутов предметной области) и F - множество ФЗ.

1. построить УНП для F;

2. если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из U, то добавить в УНП тривиальную ФЗ U→∅. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД;

3. привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ);

4. разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости Xi→Yi и Xj→Yj будем называть эквивалентными, если XiYi=XjYj. Далее введём обозначение Kr=XiYi - множество атрибутов в левой и правой частях ФЗ r-того класса эквивалентности;

5. построить граф иерархии полученных на предыдущем шаге классов эквивалентности. Правило построения: j-ый узел соединяем снизу с i-ым узлом, если Kj⊂Ki. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности;

6. из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора:

   1. удалить из класса эквивалентности лишние ФЗ;

   2. если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части;

   3. если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) большее число атрибутов справа у ФЗ, расположенных выше в графе иерархии;

   4. если в результате не удалось выбрать ни одной, то выбрать произвольную;

7. редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути:

   1. пусть X→Y - это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше;

   2. для тривиальной ФЗ U→∅ атрибуты вычёркиваются слева;

8. исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ U→∅). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся;

9. каждую оставшуюся в графе иерархий ФЗ V→W заменить на множество VW. Получившееся множество схем отношений обозначить как ρ;

10. для полученной на предыдущем шаге схемы БД проверить:

    1. обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы U в эту схему;

    2. обладает ли ρ свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию X→Y∉ΠRi(F), для построения новых схем отношений, то есть добавить в ρ XY.

После выполнения всех шагов полученная схема ρ:

• обладает свойством соединения без потерь;

• обладает свойством сохранения ФЗ;

• находится в 3НФ или НФБК;

• содержит минимальное число схем отношений.

«+» :

• определяет стандартную (математическую) процедуру построения схемы БД.

«-» :

• очень трудно определить всё множество ФЗ, а алгоритм критичен к набору этих ФЗ;

• при увеличении числа ФЗ возможно увеличение сложности вычисления алгоритма.

1. Задача: найти все ключи схемы отношений R, используя алгоритм построения ключа.

Исходные данные: схема отношений R=(A, B, C, D), множество функциональных зависимостей F=(ABDC, BCAD).

БИЛЕТ 13 (НЕ ПРОВЕРЯЛОСЬ)

1. Практические приёмы приведения схемы отношения к 1-ой, 2-ой и 3-ей нормальным формам.

Отношение находится в первой нормальной форме (сокращённо 1НФ), если все его атрибуты атомарны, то есть если ни один из его атрибутов нельзя разделить на более простые атрибуты, которые соответствуют каким-то другим свойствам описываемой сущности.

Схема отношений находится в 2НФ, если не существует ключа X, подмножества атрибутов Y⊂X и непервичного атрибута H, для которых выполняются условия:

• X→Y;

• Y→H;

• Y↛X.

A1→Ai...Aj

X=A1A2, Y=A1⊂X, H∈(Ai...Aj):

1) X→Y, так как A1A2→A1

2) Y→H, так как A1→Ai...Aj

3) Y↛X, так как A+1=A1Ai...Aj, X⊈Y+

Схема отношений находится в 3НФ, если не существует ключа X, Y⊆R и непервичного атрибута H∉Y, для которых выполнялись бы условия:

• X→Y∈F+;

• Y→H∈F+;

• Y→X∉F+,

A2→Ai...Aj

X=A1, Y=A2, H∈(Ai...Aj):

1) X→Y, так как A1→A2

2) Y→H, так как A2→Ai...Aj

3) Y↛X, так как A+2=A2Ai...Aj, X=A1∉Y+

1. Задача: построить схему базы данных , используя алгоритм синтеза «хорошей» схемы базы данных; проверить, 1) обладает ли эта схема базы данных свойством соединения без потерь и свойством сохранения функциональных зависимостей, 2) находятся ли схемы отношений базы данных  в нормальной форме Бойса-Кодда.

Исходные данные: универсальная схема отношений U=(A,B,C,D,E,G), множество функциональных зависимостей F=(AB, CD, EG).

БИЛЕТ 14 (НЕ ПРОВЕРЯЛОСЬ)

1. Пример использования практических приёмов нормализации схем отношений.

R - схема отношения "Сотрудники".

ФЗ:

A1A5→A2A3A4

A1→A2A3A4

A3→A4

Покажем, что эта схема не находится в 2НФ:

Можно найти ключ X=A1A5, Y=A1⊂X, H∉Y, H∈(A2,A3,A4):

1) X→Y

2) Y→H

3) Y↛X

R1 тоже не находится во 2НФ, потому что X=A1, Y=A3, H=A4:

1) X→Y

2) Y→H

3) Y↛X

Предположим, вдруг оказалось, что сотрудник может занимать несколько должностей, и ещё теперь в таблице надо хранить сведения о заказе. В этом случае схема преобразуется к следующему виду:

Но анализ показывает, что в этом случае таблицы R1 и R2 не находятся в 2НФ:

R1:

A1→A2, X=A1A3, Y=A2⊂X, H=A2

1) X→Y, так как A1A3→A1

2) Y→H, так как A1→A2

3) Y↛X, так как Y+=A1A2, X⊈Y+

R2:

A5→A6, X=A1A3A5, Y=A5⊂X, H=A6

1) X→Y, так как A1A3A5→A5

2) Y→H, так как A5→A6

3) Y↛X, так как Y+=A5A6, X=A1A3A5⊈Y+

Поэтому вновь перестроим схему:

Указанная схема имеет два недостатка:

1. в ключи R3, R1 и R4 входят атрибуты предметной области. При изменении формата табельного номера придётся обновить его R_1 и через CASCADE в R3 и R4. Поэтому всегда желательно иметь синтетические ключи - не связанные с предметной областью (ID);

2. в сущностях R2 и R5 ключи составные. Это увеличивает размер индекса и время поиска по этому индексу.

В силу этого, схему БД предлагается реорганизовать следующим образом (ввести синтетические ключи):

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

Исходные данные: схема базы данных =(DE, DG), множество функциональных зависимостей F=(DE, EG).

БИЛЕТ 15

1. Законы реляционной алгебры.

1. Закон коммутативности декартова произведения отношений

R₁×R₂=R₂×R₁, здесь и далее R₁ и R₂ - экземпляры отношений.

1. Закон ассоциативности декартова произведения

(R₁×R₂)×R₃=R₁×(R₂×R₃)

1. Закон каскада проекций

Допустим, (a₁...a_n)⊆(b₁...b_n), a_i, b_i - это атрибуты отношения R, тогда Π_a1...an(Π_b1...bn(R))=Π_a1...an(R)

1. Закон каскада селекций

Допустим, F=f₁∧f₂, тогда σ_F(R)=σ_f1(σ_f2(R))

1. Закон перестановки проекции и селекции

   1. Допустим, в условия поиска F входят атрибуты только из множества a₁...a_n, тогда Π_a1...an(σ_F(R))=σ_F(Π_a1...an(R))

   2. Допустим, в условия поиска F входят атрибуты не только из множества a₁...a_n, но и из b₁...b_n, тогда Π_a1...an(σ_F(R))=Π_a1...an(σ_F(Π_{a1...an,b1...bn}(R)))

2. Селекция декартова произведения

Отношение f₁ содержит атрибуты только из отношения R₁, тогда σ_f1(R₁×R₂)=σ_f1(R₁)×R₂

Пусть F=f₁∧f₂ и в f₁ входят атрибуты R₁, а в f₂ входят из R₂, тогда σ_F(R₁×R₂)=σ_f1(R₁)×σ_f2(R₂)

1. Закон перестановки селекции и объединения

σ_F(R₁⋃R₂)=σ_f1(R₁)⋃σ_f2(R₂)

1. Закон перестановки селекции и разности отношений

σ_F(R₁−R₂)=σ_f1(R₁)−σ_f2(R₂)

1. Закон перестановки проекции и декартова произведения

b₁...b_n - это атрибуты отношения R₁

c₁...c_k - это атрибуты отношения R₂

Π_{b1...bn,c1...ck}(R₁×R₂) = Π_b1...bn(R₁)×Π_c1...ck(R₂)

1. Закон перестановки проекции и объединения

Π_a1...an(R₁⋃R₂)=Π_a1...an(R₁)⋃Π_a1...an(R₂)

1. Задача: построить схему базы данных , используя алгоритм синтеза «хорошей» схемы базы данных; проверить, 1) обладает ли эта схема базы данных свойством соединения без потерь и свойством сохранения функциональных зависимостей, 2) находятся ли схемы отношений базы данных  в нормальной форме Бойса-Кодда.

Исходные данные: универсальная схема отношений U=(E,G,H,K), множество функциональных зависимостей F=(GK, KG, GHKE).

БИЛЕТ 16

1. Правила построения логического плана выполнения запроса к базе данных. Суть логической оптимизации. Шаги построения физического плана выполнения запроса к базе данных.

Построение логического плана

1. запрос преобразуется в формулу реляционной алгебры:

Оператор SELECT (без агрегирования, группирования и удаления дубликатов) может быть представлен так:

Характеристики

Список файлов ответов (шпаргалок)