ВУЗ:
Составители:
Рубрика:
5
Слайд 3
Функциональные зависимости
Определение:
r(R), Х
⊆
R и Y
⊆
R, отношение r удовлетворяет
функциональной зависимости Х
→
Y, если π
Y
(σ
X=x
(r))
имеет не более чем один кортеж для каждого Х-
значения х.
То есть для любых двух кортежей t
1
и t
2
в r верно,
если t
1
(X) = t
2
(X), то t
1
(Y) = t
2
(Y).
В F-зависимости Х
→
Y подмножество Х называется левой
частью, a Y — правой частью.
F-зависимость X
→
∅ удовлетворяется любым отношением.
F-зависимость ∅→Y удовлетворяется теми отношениями, в
которых Y-значения всех кортежей совпадают.
Слайд 4
Проверка наличия F-зависимости
Алгоритм SATISFIES
Вход: Отношение r и F-зависимость Х
→
Y.
Выход: истина, если r удовлетворяет X
→
Y,
ложь — в противном случае.
SATISFIES (r, Х
→
Y)
1. Пересортируем отношение r по X-столбцам так,
чтобы собрать кортежи с равными X-значениями
вместе.
2. Если каждая совокупность кортежей с равными X-
значениями имеет также равные Y-значения, то на
выходе получаем истину, в противном случае — ложь.
6
Слайд 5
Алгоритм SATISFIES. Пример 1
SATISFIES(график, РЕЙС
→
ВРЕМЯ-ВЫЛЕТА).
график (ПИЛОТ РЕЙС ДАТА ВРЕМЯ-ВЫЛЕТА)
Кушинг
83 9 авг. 10:15
Кларк 83 11 авг. 10:15
Чин 83 13 авг. 10:15
Кушинг
116 10 авг. 13:25
Чин 116 12 авг. 13:25
Кларк 281 8 авг. 5:50
Коупли 281 9 авг. 5:50
Коупли 281 13 авг. 5:50
Кларк 301 12 авг. 18:35
Коупли 412 15 авг. 13:25
Слайд 6
Алгоритм SATISFIES. Пример 2
SATISFIES(график, ВРЕМЯ-ВЫЛЕТА
→
РЕЙС)
график
(ПИЛОТ РЕЙС ДАТА ВРЕМЯ-ВЫЛЕТА)
Кларк 281 8 авг. 5:50
Коупли 281 9 авг. 5:50
Коупли 281 13 авг. 5:50
Кушинг 83 9 авг. 10:15
Кларк 83 11 авг. 10:15
Чин 83 13 авг. 10:15
Кушинг 116 10 авг. 13:25
Чин 116 12 авг. 13:25
Коупли 412 15 авг. 13:25
Кларк 301 12 авг. 18:35
