Монография американского специалиста, содержащая систематическое изложение теоретических результатов по математическому моделированию баз данных. В ней отражены современные направления исследований по реляционным базам данных: базы данных с частичной информацией, их семантика, зависимость данных. Имеется много специально подобранных примеров и упражнений. Для математиков-прикладников, специалистов по информатике, разработчиков баз данных, преподавателей, аспирантов и студентов вузов. ОГЛАВЛЕНИЕ Предисловие редактора перевода 5 Предисловие 7 Глава 1. Отношения и схемы отношений 9 1.2. Суть проблемы 9 1.2. Формализация отношений 10 1.3. Ключи 13 1.4. Обновление отношений 14 1.5. Упражнения 18 1.6. Библиография и комментарии 19 Глава 2. Реляционные операторы 20 2.1. Булевы операции 20 2.2. Оператор выбора 22 2.3. Оператор проекции 24 2.4. Оператор соединения 25 2.5. Свойства соединения 27 2.6. Упражнения 31 2.7. Библиография и комментарии 32 Глава 3. Другие операции на отношениях 33 3.1. Оператор деления 33 3.2. Постоянные отношения 34 3.3. Переименование атрибутов 35 3.4. Оператор эквисоединения 37 3.5. Расширения для других сравнений на доменах 39 3.5.1. Расширение выбора 40 3.5.2. Оператор 6-соединения 41 3.6. Реляционная алгебра 42 3.6.1. Алгебраические выражения как отображения .... 44 3.6.2. Ограничение множества операторов 45 3.7. Оператор расщепления 46 3.8. Оператор фактор 46 3.9. Упражнения 48 3.10. Библиография и комментарии 49 Глава 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. Проверка принадлежности к F4" 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. Третья нормальная форма 110 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 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 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 12.7. Библиография и комментарии 426 Глава 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. Теорема эквивалентности для ациклических схем . . 449 13.3.4. Заключительные замечания 471 13.4. Упражнения 471 13.5. Библиография и комментарии 475 Глава 14. Дополнительные вопросы 477 14.1. Логика и зависимости между данными 477 14.1.1. Мир двустрочных отношений 478 14.1.2. Эквивалентность импликаций для формул и функциональных зависимостей 480 14.1.3. Добавление многозначных зависимостей 480 14.1.4. Невозможность обобщения результатов 484 14.2. Другие зависимости между данными 485 14.2.1. Табличные зависимости 487 14.2.2. Примеры и контрпримеры табличных зависимостей 490 14.2.3. Графическое представление табличных зависимостей 492 14.2.4. Проверка логической выводимости табличных зависимостей 497 14.2.5. Обобщенные функциональные зависимости 505 14.2.6. Замкнутость классов выполнимости относительно проекции 512 14.3. Некоторые границы реляционной алгебры 14.4. Вычисляемые отношения 521 14.4.1. Пример 521 14.4.2. Проверка выражений, содержащих вычисляемые отношения 524 14.5. Упражнения 531 14.6. Библиография и комментарии 535 Глава 15. Реляционные языки запросов 537 15.1. ISBL 539 15.2. QUEL 543 15.3. SQL 548 15.4. QBE 554 15.5. PIQUE 570 15.6. Библиография и комментарии 578 Литература 579 Предметный указатель 598