Мейер Д.
15 Теория реляционных баз данных: Пер. с англ.—М.: Мир, 1987. — 608 с., ил.
Монография американского специалиста, содержащая систематическое изложение теоретических результатов по математическому моделированию баз данных. В ней отражены современные направления исследований по реляционным базам данных: базы данных с частичной информацией, их семантика, зависимость данных. Имеется много специально подобранных примеров и упражнений.
Для математиков-прикладников, специалистов по информатике, разработчиков баз данных, преподавателей, аспирантов и студентов вузов.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
С начала семидесятых годов слова «реляционная модель данных», «реляционная база данных», «реляционная алгебра» и «реляционное исчисление» стали общепринятыми терминами, употребляемыми в теории, методологии проектирования и использования автоматизированных банков данных. Самый общий термин — реляционный подход — обозначает определенную идеологию создания баз данных и баз знаний, идеологию, которая была объявлена основной в японском проекте ЭВМ пятого поколения (1980 г.). Создатель реляционной модели данных Э. Ф. Кодд в 1981 г. получил за ее разработку премию Тьюринга Американской ассоциации по вычислительной технике.
Быстрому распространению идей реляционного подхода способствовали в основном два фактора. Во-первых, база данных представляется на внешнем, не зависящем от структуры ЭВМ уровне как совокупность повседневно встречающихся в человеческой практике двумерных таблиц, поиск и обработка информации в которых не зависят от организации хранения данных в памяти ЭВМ. Это представление значительно упрощает взаимодействие пользователя с банком данных и значительно повышает производительность его труда.
Во-вторых, реляционная база данных с математической точки зрения — это конечный набор конечных отношений различной арности между заранее определенными множествами элементарных данных. Другими словами, реляционная база данных (точнее, любое ее состояние) — это конечная модель в смысле математической логики. Над отношениями модели можно осуществлять различные алгебраические операции. Тем самым теория реляционных баз данных становится областью приложений математической логики и современной алгебры и опирается на точный математический формализм.
Следует подчеркнуть, что математическая логика и современная алгебра в настоящее время стимулируют развитие теорети-'
ОГЛАВЛЕНИЕ
Предисловие редактора перевода................. 5
Предисловие.......................... • 7
Глава 1. Отношения и схемы отношений.............. 9
.2. Суть проблемы ..................... 9
.2. Формализация отношений................. 10
.3. Ключи.......................... }3
.4. Обновление отношений.................. '4
.5. Упражнения....................... |°
.6. Библиография и комментарии............... 19
Глава 2. Реляционные операторы................. 20
2.1. Булевы операции .................... 20
2.2. Оператор выбора .................... ~
2.3. Оператор проекции .'....-............... ?*
2.4. Оператор соединения................... **.
2.5. Свойства соединения................... i1
2.6. Упражнения....................... ;?'
2.7. Библиография и комментарии............... •"
00
Глава 3. Другие операции на отношениях..............
33
3.1. Оператор деления .................... Х^
3.2. Постоянные отношения.................. ос
3.3. Переименование атрибутов . .'.............. yj
3.4. Оператор эквисоединения ................ «о
3.5. Расширения для других сравнений на доменах....... 4Q
3.5.1. Расширение выбора................ 4j
3.5.2. Оператор 9-соединения............... ^2
3.6. Реляционная алгебра .................. ^4
3.6.1. Алгебраические выражения как отображения . . . • ^
3.6.2. Ограничение множества операторов......... ^
3.7. Оператор расщепления.................. ^6
3.8. Оператор фактор.................. . • • ^g
3.9. Упражнения....................... 49
3.10. Библиография и комментарии...............
Оглавление
605
Глава 4. Функциональные зависимости............... 50
4.1. Определение....................... 50
4.2. Аксиомы вывода..................... 53
4.3. Применение аксиом вывода................ 56
4.4. Полнота системы аксиом вывода............. 57
4.5. Выводы и направленные ациклические графы вывода .... 59
4.5.1. RAP-последовательности вывода........... 61
4.5.2. Ориентированные ациклические графы вывода .... 64
4.5.3. Еще о DDA-графах................ 69
4.6. Проверка принадлежности к F*.............. 71
4.7. Упражнения....................... 78
4.8. Библиография и комментарии.............. 79
Глава 5. Покрытия функциональных зависимостей.......... 80
5.1. Покрытия и эквивалентность............... 80
5.2. Неизбыточные покрытия ................. 82
5.3. Посторонние атрибуты.................. 83
5.4. Канонические покрытия ................. 86
5.5. Структура неизбыточных покрытий............ 87
5.6. Минимальные покрытия ................. 88
5.6.1. Явная определяемость ............... 89
5.6.2. Вычисление минимальных покрытий......... 94
5.7. Оптимальные покрытия ................. 96
5.8. Кольцевые покрытия и составные функциональные зависимости 96
5.9. Упражнения....................... 100
5.10. Библиография и комментарии............... 102
Глава 6. Базы данных и нормальные формы............. 103
6.1. Базы данных и схемы баз данных............. 104
6.2. Нормальные формы для баз данных............ 106
6.2.1. Первая нормальная форма............. 106
• 6.2.2. Аномалии и избыточность данных.......... 108
6.2.3. Вторая нормальная форма............. 109
6.2.4. Третья нормальная форма............. ПО
6.3. Нормализация через декомпозицию............ 112
6.4. Недостатки нормализации посредством декомпозиции. ... 115
6.5. Нормализация посредством синтеза............ 117
6.5.1. Предварительные результаты для алгоритма синтеза 119
6.5.2. Построение алгоритма синтеза........... 119
6.5.3. Корректность и другие свойства алгоритма синтеза 121
6.5.4. Улучшения алгоритма синтеза........... 124
6.6. Устранимые атрибуты .................. 126
6.7. Нормальная форма Бойса—Кодца (НФБК)........ 128
6.7.1. Проблемы НФБК ................. 130
6.8. Упражнения....................... 130
6.9. Библиография и комментарии.............. 132
Глава 7. Многозначные зависимости, зависимости соединения и нормальные формы ..................... 133
7.1. Многозначные зависимости................ 134
7.2. Свойства многозначных зависимостей........... 136
7.3. Многозначные и функциональные зависимости....... 138
7.4. Аксиомы вывода для многозначных зависимостей...... 139
7.4.1. Одни многозначные зависимости........... 139
7.4.2. Функциональные и многозначные зависимости..... 142
7.4.3. Полнота системы аксиом и связанные с ними задачи 143
606
Оглавление
7.5. Четвертая нормальная форма............... 145
7.6. Четвертая нормальная форма и реализация зависимостей ... 147
7.7. Зависимости соединения................. 148
7.8. Нормальная форма вида «проекция-соединение»....... 150
7.9. Встроенные зависимости соединения............ 152
7.10. Упражнения....................... 153
7.11. Библиография и комментарии .............. 154
Глава 8. Отображения «проекция-соединение», табло и прогонка. 156
8.1. Отображения «проекция-соединение»............ 156
8.2. Табло.......................... 158
8.2.1. Табло как отображения.............. 159
8.2.2. Представление PJ-отображения в виде табло..... 160
8.3. Эквивалентность табло и эквивалентность схем....... 161
8.4. Отображения вложения................... 165
8.5. Эквивалентность при наличии ограничений........ 168
8.5.1. F-правила..................... 170
8.5.2. J-правила..................... 171
8.6. Алгоритм прогонки (chase) ............... 172
8.6.1. Свойство конечности Чёрча—Россера........ 175
8.6.2. Эквивалентность табло при ограничениях....... 181
8.6.3. Проверка выводимости зависимостей соединения .... 182
8.6.4. Проверка выводимости функциональных зависимостей 183
8.6.5. Вычисление базиса зависимостей........... 186
8.7. Табло как шаблон.................... 188
8.8. Сложность вычислений по методу прогонки......... 192
8.9. Упражнения....................... 195
8.10. Библиография и комментарии............... 198
Глава 9. Теория представлений .................. 199
9.1. Понятие адекватного представления............ 199
9.2. Эквивалентность по данным схем баз данных........ 211
9.3. Проверка на адекватность представления и на эквивалентность
при наличии ограничений................. 214
9.3.1. Случай, когда Р определяется только функциональными зависимостями................... 215
9.3.2. .Случай, когда Р определяется функциональными и многозначными зависимостями ............. 219
9.3.3. Проверка эквивалентности по данным........ 222
9.4. Упражнения....................... 226
9.5. Библиография и комментарии............... 228
Глава 10. Системы запросов .................... 229-
10.1. Эквивалентность и полнота................ 230
10.2. Реляционное исчисление кортежей ............ 232
10.2.1. Формулы исчисления кортежей.......... 234
10.2.2. Типы; свободное и связанное вхождения....... 236.
10.2.3. Выражения и исчисления кортежей......... 240
10.3. Сведение реляционной алгебры с дополнением к реляционному исчислению кортежей................. 246
10.4. Ограниченная интерпретация формул исчисления кортежей 248
10.4.1. Сведение реляционной алгебры к исчислению кортежей
при ограниченной интерпретации ......... 251'
10.4.2. «Безопасные» выражения исчисления кортежей . . . 251
10.5. Реляционное исчисление доменов............. 254
10.6. Сведение исчисления кортежей к исчислению доменов .... 259
Оглавление 607
10.7. Сведение исчисления доменов к реляционной алгебре..... 261
10.8. Табло запросов . .................... 265
10.8.1. Табло запросов для одного отношения....... 266
10.8.2. Табло запросов для ограниченных алгебраических выражений ..................... 272
10.8.3. Табло запросов, которые получаются из алгебраических выражений ................. 276
10.8.4. Табло запросов к базам данных, состоящих из нескольких отношений .................. 278
10.8.5. Наборы табло запросов.............. 279
10.9. Конъюнктивные запросы ................. 281
10.10. Упражнения....................... 282
10.11. Библиография и комментарии .............. 287
Глава 11. Модификация запросов ................. 288
11.1. Уровни информированности при модификации запросов . . . . 293
11.2. Упрощения и повторяющиеся подвыражения в алгебраических выражениях....................... 295
11.3. Оптимизация алгебраических выражений......... 299
11.4. Декомпозиция запросов ................. 305
11.4.1. Первичная обработка................ 308
11.4.2. Итерация..................... 310
11.4.3. Алгоритм декомпозиции запроса.......... 311
11.5. Оптимизация табло запросов............... 319
11.5.1. Эквивалентность табло запросов.......... 319
11.5.2. Простые табло запросов.............. 323
11.5.3. Эквивалентность при наличии ограничений..... 331
11.5.4. Обобщение на базы данных из нескольких отношений . . 334
11.5.5. Эквивалентность наборов табло запросов...... 341
11.6. Оптимизация конъюнктивных запросов .......... 343
11.7. Модификация запросов в распределенных базах данных . . . 346
11.7.1. Полусоединение.................. 347
11.7.2. Фрагменты отношений .............. 351
11.8. Упражнения....................... 353
11.9. Библиография и комментарии .............. 358
Глава 12. Неопределенные значения, неоднородная информация и семантика баз данных..................... 360
12.1. Неопределенные значения................ 362
12.2. Функциональные зависимости и неопределенные значения . . . 367
12.3. Ограничения на неопределенные значения......... 376
12.4. Реляционная алгебра и частичные отношения........ 377
12.4.1. Функции возможных расширений.......... 377
12.4.2. Обобщение реляционных операторов........ 380
12.4.3. Примеры функций возможных расширений .... 384
12.5. Неоднородная информация и семантика баз данных..... 395
12.5.1. Предположения об универсальном отношении. . . . 396
12.5.2. Пустышки и отношения на подсхемах........ 398
12.5.3. Семантика баз данных и W-функции........ 400
12.5.4. W-функция, основанная на соединениях....... 404
12.5.5. Слабоуниверсальные отношения.......... 406
12.5.6. Независимость .................. 412
12.5.7. Другие условия на W-функции........... 417
12.6. Упражнения....................... 422
608
Оглавление
Глава 13. Ациклические схемы баз данных.............. 428
13.1. Некоторые свойства схем баз данных............ 428
13.1.1. Существование программы полной редукции..... 428
13.1.2. Эквивалентность зависимости соединения множеству многозначных зависимостей ........... 431
13.1.3. Единственность декомпозиции в 4НФ........ 432
13.1.4. Попарная согласованность влечет за собой согласованность в целом................... 433
13.1.5. Малые промежуточные соединения......... 434
13.2. Синтаксические условия на схемы баз данных....... 437
13.2.1. Ациклические гиперграфы ......_...... 437
13.2.2. Деревья соединений .........'...... 442
13.2.3. Свойство квазистягиваемости пересечений...... 445
13.3. Эквивалентность условий ................ 445
13.3.1. Редуктивный алгоритм Грэхема .......... 445
13.3.2. Отыскание деревьев соединений.......... 447
13.3.3. Теорема эквивалентности для ациклических схем . .
Цена: 300руб.
