91 Логика, алгебра и базы данных / Пер. с англ. X. И. Килова, Г. Е. Минца; Под ред. Г. В. Орловского, А. О. Слисенко. - М.: Машиностроение, 1989. - 368 с.: ил. ISBN 5-217-00178-Х
Изложены основные понятия математической логики и алгебры, которые лежат в основе таких приложений этих дисциплин, как базы данных, экспертные системы. системы логического программирования и др. Эти же понятия становятся методологической основой описания, анализа и моделирования автоматизированных интегрированных производств. Описаны концепция Кодасил, функциональные языки запросов, модели баз данных.
Для программистов, работающих в промышленности, преподавателей и студентов вузов в области вычислительной техники и информатики .
ОГЛАВЛЕНИЕ
Предисловие редакторов перевода.......................... 10
Глава 1. Исчисление высказываний........................... 13
1.1. Введение........................................ 13
1.2. Истинность и ложность предложений - двузначная
логика.......................................... 14
1.3. Составные предложения.................•......... . 15
1.4. Таблицы истинности для основных операций........ 15
1.5. Теоремы из булевой алгебры...................... 17
1.6. Законы де Моргана............................... 19
1.7. Дистрибутивный закон - предложения в нормальной
форме........................................... 20
1.8. Оператор ВЛЕЧЕТ.................................21
1.9. Правила вывода: цепное заключение и модус поненс 23
1. 10. Выводы.......................................... 24
1.11. Тавтологии и подстановка........................ 26
1. 12. Логическая эквивалентность и подстановка........ 27
1.13. Доказательство с введением допущения............ 28
1.14. Приведение к противоречию....................... 29
1.15. Доказательство методом резолюции................ 30
1.16. Преимущества метода резолюции................... 34
Глава 2. Исчисление предикатов............................. 35
2.1. Введение. Параметризованные предложения......... 35
2.2. Квантор общности V.............................. 36
2.3. Квантор существования 3......................... 37
2.4. Запись утверждения в языке исчисления предикатов 38
2.5. Комбинации кванторов............................ 39
2.6. Формальный синтаксис............................ 42
2.7. Семантические ограничения исчисления предикатов. 43
2.8. Теоретике-множественная модель.................. 43
2.9. Отрицание кванторов............................. 45
2. 10. Примеры кванторных утверждений.................. 46
2.11. Кванторные утверждения о данных................. 47
2. 12. Эквивалентность различных формул................ 48
2. 13. Приведение к системе дизъюнктов................. 49
2.14. Принцип резолюции............................... 51
2.15. Применение метода резолюций для ответов на вопросы ............................................ 52
2. 16. Эвристики для поиска доказательства............. 55
5
2.17. Подстановка и унификация........................ 56
2.18. Выводы.......................................... 57
Глава 3. Ламбда-выраження и обработка списков.............58
3.1. Введение....................................... 58
3.2. Функции как отображения множеств................ 59
3.3. Композиция функций: составной оператор.......... 65
3.4. Ограничение и объединение функций: условный опе-
ратор if........................................ 67
3.5. Формы аппликатнвного синтаксиса: ламбда-обозначения ............................................. 69
3.6. Запись рекурсивных определений в ламбда-обозначениях............................................ 71
3.7. Рекурсивная обработка списков................... 73
3.8. Типы рекурсивных функций........................ 77
3.9. Запись некоторых функций обработки множеств и
списков в ламбда-обозначениях................... 81
3. 10. Выводы.......................................... 84
Глава 4. Представление программ дизъюнктами: язык Пролог.. .85
4.1. История логического программирования............ 85
4.2. Элементы Пролога................................ 86
4.3. Вычисление как поиск от цели в глубину.......... 89
4.4. Примеры запросов к базе данных на Прологе....... 92
4.5. Аксиоматизация операций обработки списков....... 94
4.6. Механизм порождения новых ответов............... 95
4.7. Функции как конструкторы записей................ 98
4.8. Соотношение метода резолюции и поиска в глубину 102
4.9. Специальные предикаты в Прологе............>. . . 104
4. 10. Перевод ламбда-обозначений на Пролог........... 107
4.11. Некоторые основные процедуры обработки множеств
и списков...................................... 109
4. 12. Операции над базами данных и множествами в Прологе........................................... 1Ю
4.13. Выводы......................................... ИЗ
Глава 5. Представление программ в функциональных обозначениях............................................115
5.1. Функциональное программирование................ 115
5.2. Функциональный синтаксис языка KRC............. 116
5.3. Функции, управляющие итерацией: maplist, lit... 118
5.4. Функции, порождающие функции................... 120
5.5. Комбинаторы Карри н Тернера.................... 122
5.6. Функции, порождающие множества................. 124
5.7. Отложенные вычисления.......................... 126
5.8. Функции, оперирующие на потоках: примеры из языка
FQL............................................ 128
5.9. Выводы: основные операции FQL.................. 130
5.10. Обобщенные типы функций: примеры из языка НОРЕ. 132
5.11. Выводы......................................... 135
Глава 6. Реляционная модель............................... 137
6. 1. Введение....................................... 137
6.2. Общие свойства отношений в реляционной базе данных............................................ 138
6.3. Бинарная реляционная модель.................... 143
6.4. Объектно-связная модель........................ 145
6.5. Нормализация................................... 148
6.6. Обобщенные теоретике-множественные операции над
двумя отношениями.............................. 150
6.7. Различия между отношениями и файлами в Паскале н Коболе.......................................... 154
6.8. Подтипы и иерархии типов........................ 160
6.9. Выводы.......................................... 163
Глава 7. Языки, основанные на реляционном исчислении......165
7.1. Введение........................................ 165
7.2. Язык QUEL системы INGRES как исчисление, ориентированное на кортежи......................... 165
7.3. Синтаксис языка QUEL............................ 167
7.4. SQL н другие языки.............................. 171
7.5. Язык QBE: Query-by-Example...................... 177
7.6. Примеры из QBE и их сравнение с примерами из SQL 179
7.7. Использование выходных отношений, 'снимков" и представлений................................... 181
7.8. Операция GROUP.BY на SQL н QBE.................. 183
7.9. Выводы.......................................... 187
Глава 8. Реляционная алгебра: аппликативный язык...........188
8.1. Введение........................................ 188
8.2. Четыре основные алгебраические операции......... 189
8.3. Соответствие операциям обработки данных на последовательных файлах......................... 193
8.4. Композиция основных операций.................... 196
8.5. Сравнение алгебры и исчисления.................. 197
8.6. Язык Астрнд. Синтаксис обобщенной алгебры....... 198
8.7. Использование соединения с переименованием...... 200
8.8. Примеры запросов на Астриде в сравнении с запросами
на QBE..........................................203
8.9. Оператор расширения и вычисляемые поля.......... 205
8. 10. Операция группировки как расширенная проекция. . . 207
8.11. Операция обобщенной разности и квантор общности. 211
8.12. Формулирование сложных многострочных запросов... 212
8.13. Выводы.......................................... 213
Глава 9. Преобразование запросов в реляционной алгебре и
реляционном исчислении...........................2Н
9.1. Введение....................................... 214
9.2. Преобразование из реляционной алгебры в исчисление........................................... 216
9.3. Оптимизация алгебраических выражений - переупорядочение операций................................ 219
9.4. Оптимизация объединения и разности.............. 224
9.5. Преобразование выражений, содержащих группировку 226
9.6. Оператор деления и эквивалентные ему операторы. . 229
9.7. Другие полезные эквивалентности из теории множеств........................................... 232
9.И. Алгоритм оптимизации, применяемый в системе PRTY 232
9.9. Трансляция из QBE в реляционную алгебру......... 233
9.10. Алгоритм Кодда для преобразования реляционного исчисления в реляционную алгебру........... 238
9.11. Улучшенный вариант алгоритма Кодда, использующий группировку................................. 240
9.12.
Глава
Глава
10. Функциональная модель данных ............. , . . . 243 ...245
10.1 . Основные понятия : объекты и функции .......... . . . 246
10.2 . Композиция функций в функциональной модели ...... 254
10.3 . Сравнение разновидностей синтаксиса манипулиро-
вания данными ................................... 255
10.4 . Представление функциональной схемы с помощью от-
ношений ........................................ . 258
10.5 . Представление отношений схемой на Даплексе ...... 260
10.6 . Связь с абстрактными типами данных .............. 261
10.7 . Выводы: основные положения ...................... 262
11. База данных Кодасил DBTG ................... . . . 265
11.1 . Введение ....................................... . 265
11.2. Представление наборов с помощью цепочек и указа -
телей........................................... 267
11.3. Кодасиловская схема и ее диаграмма Бахмана...... 271
11.4. Дополнительные подробности описания набора...... 276
11.5. Предложения ANSI/SPARC: внешние представления
и структуры хранения............................ 280
11.6. Кодасиловские операции языка манипулирования
данными......................................... 282
11.7. Форматы команды FIND............................ 285
11.8. Другие команды языка манипулирования данными.... 289
11.9. Выводы.......................................... 291
Глава 12. Функциональные языки запросов для баз данных типа Кодасил.................................... 292
12.1. Реализация языка FQL для базы данных типа Кода-
сил............................................ 293
12.2. Реализация Даплекс-функций над Кодасилом....... 296
12.3. Представление Даплекс-схемы кодасиловскими наборами ......................................... 298
12.4. Формирование реляционного представления основ -
ной схемы Кодасил ............................. 300
12.5. Реализация операций реляционной алгебры над
Кодасилом...................................... 308
12.6. Модификация программ в системе Астрнд.......... 310
12.7. Проблемы модификаций и их отображение в базах
данных......................................... 316
12.8. Ограничения целостности........................ 320
12.9. Дальнейшее развитие............................ 324
12.10. Заключение..................................... 326
Приложение 1. Отношения базы данных "Кубок мира"..........328
Приложение 2. Синтаксис реляционной алгебры Астрид........ 334
Приложение 3. Диаграмма Бахмана и схема описания данных в
IDS-П для базы данных "Кубок мира".........337
Приложение 4. Синтаксис языка SQL........................ 341
Приложение 5. Синтаксис языка Даплекс..................... 343
Список литературы ......................................... 348
Список дополнительной литературы........................... 359
Предисловие редакторов перевода
Одним из важнейших путей резкого повышения технико-экономического уровня и качества машин, оборудования, приборов является электронизация и комплексная автоматизация производства, слияние островков" автоматизации в целостные интегрированные производственные комплексы - АСУ/АСНИ/САПР/АСТПП/ГПС/АСКИОГ Этим вопросам уделяется большое внимание и у нас в стране и за рубежом. В результате становится все более ясным, что сквозная автоматизация проектирования и производства упирается в необходимость создания единой стратегии управления данными -создание баз данных отдельных автоматизированных систем (САПР АСГПП и др.) и налаживание потоков данных между ними без потери информации. Это фундаментальная проблема, требующая активной работы не только специалистов-теоретиков, но и специалистов в области автоматизации производства.
АСУ - автоматизированная система управления; АСНИ - автоматизированная система научных исследований: САПР - система автоматизированного проектирования; АСТПП - автоматизированная система технологическое подготовки производства; ГПС - гибкая производственная система; АСКИО - автоматизированная система контроля и испытания объектов.
10
Каждая автоматизированная система (АС) требует описания входных данных. Чем больше таких систем, тем больше работа по подготовке данных. Без научного подхода к этой проблеме, без хорошей теории может создаться такое положение, когда АС будут простаивать (а порой уже и сейчас простаивают) из-за информационного голода. Необходима научная политика в создании баз данных в стране, обеспечивающая широкую кооперацию усилий отдельных предприятий, необходимо информационное обеспечение комплексной автоматизации промышленных предприятий, включающее разработку и стандартизацию СУБД, языков описания данных и т.д.
Хорошим введением в это новое направление может служить предлагаемая читателю книга П. Грэя. В отличие от ряда работ, появившихся за последние годы в отечественной и переводной литературе, в ней доступно и наглядно изложен материал. При сравнительно небольшом объеме в ней рассмотрены не только все популярные модели баз данных (реляционная, кодасиловская, функциональная), но и связи между ними, что составляет большое достоинство книги.
В книге изучаются приложения логического и аппликативного программирования к базам данных, рассматриваются современные языки запросов, в частности, такой популярный, как QBE: Query-by-Example (запрос по примеру). В нем широко используется распространенный язык логического программирования Пролог, мировую известность которому принесла идея его применения в компьютерах пятого поколения. Демонстрируются также возможности реляционной алгебры Астрид (ASTRID), являющейся расширением известной системы Кодда.
Основой книги послужил рассчитанный на широкую аудиторию курс лекций П. Грэя,читавшийся в Абердинском университете (Шотландия).
От читателя не требуется почти никаких предварительных знаний. Автор начинает с рассмотрения основ логического и аппликативного программирования и развития последнего по направлению к функциональному программированию. Эти подходы сопоставляются с методами, используемыми в таких классических языках баз данных, как Кобол. Описываются две классические модели баз данных -реляционная и кодасиловская, а также современная функциональная. Рассматриваются хорошо известные реляционные и более новые функциональные языки запросов. Показывается, как запросы можно переводить из логической в функциональную форму, и наоборот.
Подробное рассмотрение взаимосвязи между логическим и аппли-кативным программированием применительно к теории баз данных, проведенное в весьма популярной форме, как это сделано в книге
11
Цена: 150руб.
