Базы данных: конспект лекций
Добавить в закладки К обложке
- Лекция № 1. Введение - Страница 1
- 2. Реляционные базы данных - Страница 2
- Лекция № 2. Отсутствующие данные - Страница 4
- 1. Пустые значения (Empty-значения) - Страница 5
- 2. Неопределенные значения (Null-значения) - Страница 6
- 3. Null-значения и общее правило вычисления выражений - Страница 7
- 4. Null-значения и логические операции - Страница 8
- 5. Null-значения и проверка условий - Страница 9
- Лекция № 3. Реляционные объекты данных - Страница 10
- 2. Домены и атрибуты - Страница 11
- 3. Схемы отношений. Именованные значения кортежей - Страница 12
- 4. Кортежи. Типы кортежей - Страница 13
- 5. Отношения. Типы отношений - Страница 14
- Лекция № 4. Реляционная алгебра. Унарные операции - Страница 15
- 1. Унарная операция выборки - Страница 16
- 2. Унарная операция проекции - Страница 17
- 3. Унарная операция переименования - Страница 18
- 4. Свойства унарных операций - Страница 19
- Лекция № 5. Реляционная алгебра. Бинарные операции - Страница 20
- 2. Операции декартового произведения и естественного соединения - Страница 22
- 3. Свойства бинарных операций - Страница 24
- 4. Варианты операций соединения - Страница 26
- 5. Производные операции - Страница 31
- 6. Выражения реляционной алгебры - Страница 33
- Лекция № 6. Язык SQL - Страница 35
- 1. Оператор Select – базовый оператор языка структурированных запросов - Страница 36
- 2. Унарные операции на языке структурированных запросов - Страница 37
- 1. Операция выборки. - Страница 38
- 2. Операция проекции. - Страница 39
- 3. Операция переименования. - Страница 40
- 3. Бинарные операции на языке структурированных запросов - Страница 41
- 1. Операция объединения. - Страница 42
- 2. Операция пересечения. - Страница 43
- 3. Операция разности. - Страница 44
- 4. Операция декартова произведения. - Страница 45
- 5. Операции внутреннего соединения. - Страница 46
- 6. Операция естественного соединения. - Страница 47
- 7. Операция левого внешнего соединения. - Страница 48
- 8. Операция правого внешнего соединения. - Страница 49
- 9. Операция полного внешнего соединения. - Страница 50
- 4. Использование подзапросов - Страница 51
- Лекция № 7. Базовые отношения - Страница 53
- 1. Базовые типы данных - Страница 54
- 2. Пользовательский тип данных - Страница 56
- 3. Значения по умолчанию - Страница 57
- 4. Виртуальные атрибуты - Страница 58
- 5. Понятие ключей - Страница 59
- Лекция № 8. Создание базовых отношений - Страница 61
- 1. Металингвистические символы - Страница 62
- 2. Пример создания базового отношения в записи на псевдокоде - Страница 63
- 3. Ограничение целостности по состоянию - Страница 66
- 4. Ограничения ссылочной целостности - Страница 67
- 5. Понятие индексов - Страница 70
- 6. Модификация базовых отношений - Страница 71
- Лекция № 9. Функциональные зависимости - Страница 72
- 2. Правила вывода Армстронга - Страница 74
- 3. Производные правила вывода - Страница 76
- 4. Полнота системы правил Армстронга - Страница 78
- Лекция № 10. Нормальные формы - Страница 80
- 2. Первая нормальная форма (1NF) - Страница 82
- 3. Вторая нормальная форма (2NF) - Страница 84
- 4. Третья нормальная форма (3NF) - Страница 86
- 5. Нормальная форма Бойса – Кодда (NFBC) - Страница 87
- 6. Вложенность нормальных форм - Страница 88
- Лекция № 11. Проектирование схем баз данных - Страница 89
- 1. Различные типы и кратности связей - Страница 91
- 2. Диаграммы. Виды диаграмм - Страница 92
- 3. Связи и миграция ключей - Страница 93
- Лекция № 12. Связи классов сущностей - Страница 95
- 1. Иерархическая рекурсивная связь - Страница 96
- 2. Сетевая рекурсивная связь - Страница 97
- 3. Ассоциация - Страница 98
- 4. Обобщения - Страница 100
- 5. Композиция - Страница 102
- 6. Агрегация - Страница 104
- 7. Унификация атрибутов - Страница 105
- Лекция № 13. Экспертные системы и продукционная модель знаний - Страница 106
- 2. Структура экспертных систем - Страница 109
- 3. Участники разработки экспертных систем - Страница 110
- 4. Режимы работы экспертных систем - Страница 111
- 5. Продукционная модель знаний - Страница 112
4. Полнота системы правил Армстронга
Пусть F(S) — заданное множество функциональных зависимостей, заданных над схемой отношения S.
Обозначим через inv <F(S)> ограничение, накладываемое этим множеством функциональных зависимостей. Распишем его:
Inv <F(S)> r(S) = ∀X → Y ∈F(S) [inv <X → Y> r(S)].
Итак, это множество ограничений, накладываемое функциональными зависимостями, расшифровывается следующим образом: для любого правила из системы функциональных зависимостей X → Y, принадлежащего множеству функциональных зависимостей F(S), действует ограничение функциональных зависимостей inv <X → Y> r(S), определенных над множеством отношения r(S).
Пусть какое-то отношение r(S) удовлетворяет этому ограничению.
Применяя правила вывода Армстронга к функциональным зависимостям, определенным для множества F(S), можно получить новые функциональные зависимости, как уже было сказано и доказано нами ранее. И, что показательно, ограничениям этих функциональных зависимостей отношение F(S) будет автоматически удовлетворять, что видно из расширенной формы записи правил вывода Армстронга. Напомним общий вид этих расширенных правил вывода:
Правило вывода 1.inv < X → X > r(S);
Правило вывода 2.inv <X → Y> r(S) ⇒inv <X ∪ Z → Y> r(S);
Правило вывода 3.inv <X → Y> r(S) & inv <Y ∪ W → Z> r(S) ⇒inv <X ∪ W → Z>;
Возвращаясь к нашим рассуждениям, пополним множество F(S) новыми, выведенными из него же с помощью правил Армстронга зависимостями. Будем применять эту процедуру пополнения до тех пор, пока у нас не перестанут получаться новые функциональные зависимости. В результате этого построения мы получим новое множество функциональных зависимостей, называемое замыканием множества F(S) и обозначаемое F+(S).
Действительно, такое название вполне логично, ведь мы собственноручно путем длительного построения «замкнули» множество имеющихся функциональных зависимостей само на себе, прибавив (отсюда «+») все новые функциональные зависимости, получившиеся из имеющихся.
Необходимо заметить, что этот процесс построения замыкания конечен, ведь конечна сама схема отношения, на которой и проводятся все эти построения.
Само собой разумеется, что замыкание является надмножеством замыкаемого множества (действительно, ведь оно больше!) и ни сколько не изменяется при своем повторном замыкании.
Если записать только что сказанное в формулярном виде, то получим:
F(S) ⊆ F+(S), [F+(S)]+= F+(S);
Далее из доказанной истинности (т. е. законности, правомерности) правил вывода Армстронга и определения замыкания следует, что любое отношение, удовлетворяющее ограничениям заданного множества функциональных зависимостей, будет удовлетворять ограничению зависимости, принадлежащей замыканию.
X → Y ∈ F+(S) ⇒ ∀r(S) [inv <F(S)> r(S) ⇒inv <X → Y> r(S)];
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113