Излагается одна из возможных точно математически обоснованных математических моделей «баз данных»— важнейшего понятия программирования. Развиваются алгебраические, в частности, категорные основы теории, различные подходы, направленные на алгебраизацию узкого исчисления предикатов, алгебраические модели базы данных. Дается обзор проблем теории баз данных и сопоставлены различные подходы исследований в этой области.
Для специалистов в области алгебры и математической логики, а также в теоретическом и практическом программировании.
Рецензент профессор С. И. Адян
ОГЛАВЛЕНИЕ
Предисловие.................
ВВЕДЕНИЕ ОБЩИЙ ВЗГЛЯД НА ЗАДАЧИ И СОДЕРЖАНИЕ КНИГИ
§ 1. Предварительные сведения о базах данных. Примеры
1.1. Примеры и наводящие соображения (11). 1.2. Постановка основных задач. Реляционный подход. Применения алгебры (16).
§ 2. Еще примеры. Сетевая модель.........
2.1. Другие примеры реляционных баз (22). 2.2. Сетевые базы данных (24). 2.3. Аксиомы состояний (28).
§ 3. Обзор содержания книги...........
3.1. Замечания о первой части (29). 3.2. Содержание второй части (30). 3.3. Третья часть. Модель базы данных (31).
11
22 29
ЧАСТЬ 1 УНИВЕРСАЛЬНАЯ АЛГЕБРА
Глава 1. Множества, алгебры, модели........
§ 1. Множества..............35
1.1. Множества, подмножества и отображения (35). 1.2. Умножения отображений (36). 1.3. Декартово произведение мно-1-зк\ /i д Свободное объединение множеств (37).
--- 'ча\ 1 R Ки-
женпп чшиг„___
жеств (36). 1.4. Свободное объединение ш»,»--- „ ,
1.5. Характеристические функции подмножеств (38). 1.6. Бинарные отношения (39). 1.7. Эквивалентность (40). 1.8. Фактормножество (40). 1.9. Основная теорема об отображениях (40). 1.10. Мощность множества (41). 1.11. Нечеткие множества (42).
§ 2. Алгебры и модели............42
2.1. Алгебраические операции и отношения (42). 2.2. Алгебры (43). 2.3. Модели и алгебраические системы (44). 2.4. Гомоморфизмы алгебр и моделей (44). 2.5. Факторалгебры и фактормодели (45). 2.6. -Теорема о гомоморфизмах (46). 2.7. Подалгебры и подмодели (46). 2.8. Декартовы произведения (47). 2.9. Теорема Ремака (47). 2.10. Алгебра термов (48). 2.11. Образующие и соотношения (48). 2.12. Классы и аксиомы алгебр и моделей (49).
§ 3. Многосортные системы...........50
3.1. Комплекты множеств (50). 3.2. Многосортные операции и отношения (51). 3.3. Многосортные алгебры и модели (51). 3.4. Алгебра многосортных термов (53).
4 ОГЛАВЛЕНИЕ
. *
Глава 2. Основные структуры..........54
§ 1. Определения и примеры..........54
1.1. Полугруппы (54). 1.2. Группы (55). 1.3. Истоки групп и полугрупп (56). 1.4. Квазигруппы и лупы (56). 1.5. Кольца (57). 1.6. Поля и тела (58). 1.7. Еще примеры колец и полей. Источники (58). 1.8. Линейные пространства и модули (59). 1.9. Ассоциативные линейные алгебры (61). 1.10. Групповые и полугрупповые алгебры (62). 1.11. Другие структуры (62).
§ 2. Гомоморфизмы. Свободные алгебры.......63
2.1. Определение свободной алгебры (63). 2.2. Полугруппы (63). 2.3. Группы (64). 2.4. Кольца (65). 2.5. Линейные пространства и модули (66). 2.6. Линейные алгебры (66).
§ 3. Некоторые многосортные структуры.......67
3.1. Представления групп и полугрупп (67). 3.2. Линейные представления (67). 3.3. Автоматы (68). 3.4. Аффинные пространства и аффинные автоматы (69).
Глава 3. Категории..............71
§ 1. Общие сведения и примеры..........71
1.1. Определение категории (71). 1.2. Примеры (72). 1.3. Подкатегории (73). 1.4. Мономорфизмы, эпиморфизмы и изоморфизмы (74). 1.5. Двойственность (75). 1.6. Функторы (76). 1.7. Естественные преобразования функторов. Категория функторов (77). 1.8. Эквивалентность категорий (79).
§ 2. Некоторые рабочие понятия.........80
2.1. Универсальные объекты (80). 2.2. Прямые и свободные произведения — произведения и копроизведения (81). 2.3. Другие примеры универсальных объектов (83). 2.4. Тензорные произведения модулей (84). 2.5. Сопряженные функторы (86). 2.6. Конусы, уравнители, пределы (90).
Глава 4. Категория множеств. Топосы. Нечеткие множества . . 92
§ 1. Дальнейшие общие понятия..........92
1.1. Замечания о категории множеств (92). 1.2. Амальгамы и коамальгамы. Декартов квадрат (93). 1.3. Полнота и копол-нота (97). 1.4. Экспоненцирование (97). 1.5. Декартово замкнутые категории (99).
§ 2. Топосы...............100
2.1. Подобъекты (100). 2.2. Элементы. Имена стрелок (101). 2.3. Классификатор подобъектов (103). 2.4. Определение то-поса (105). 2.5. Объект-степень (106). 2.6. Общие замечания о топосах.Точечные топосы (107). 2.7.Примеры топосов (109).
2.8. Действия с подобъектами. Алгебры Гейтинга (113).
2.9. Алгебры Гейтинга подобъектов. Булевы топосы (114).
§ 3. Нечеткие множества. Разное.........115
3.1. Нечеткие множества и нечеткие фактормножества (115).
3.2. Категория нечетких множеств (118). 3.3. Топос нечетких множеств (119). 3.4. Замечания об основаниях. История (121)
Глава 5. Многообразия алгебр. Аксиоматизируемые классы . . 122
§ 1. Многообразия.............122
1.1. Замкнутые классы и свободные алгебры (122). 1.2. Классы и тождества (125). 1.3. Теорема Биркгофа (127). 1.4. Вербальные функции (128). § 2. Некоторые конструкции..........130
2.1. Свободные произведения в многообразиях (130).
2.2. Амальгамы (131). 2.3. Эпиморфизмы и мономорфизмы в многообразиях (132).
ОГЛАВЛЕНИЕ
133
§ 3. Аксиоматизируемые классы алгебр.......
3.1. Общие замечания (133). 3.2. Фильтрованные произведения (134). 3.3. Квазимногообразия и псевдомногообразия (136). Глава 6. Категорная алгебра и алгебраические теории ... 137
§ 1. Клоны и клоны операций..........137
1.1. Клоны операций (137). 1.2. Абстрактные клоны (138). 1.3. Клоны и свободные алгебры (139). 1.4. Представления • клонов и многообразия алгебр (141). '
§ 2. Алгебраические теории...........147
2.1. Клоны и категории (147). 2.2. Алгебры как функторы (148). 2.3. Алгебраические теории и многообразия алгебр (151). 2.4. Дополнительные замечания (155).
ЧАСТЬ 2 АЛГЕБРАИЧЕСКАЯ ЛОГИК А
Глава 7. Булевы алгебры и исчисление высказываний .... 161
§ 1. Булевы алгебры.............161
1.1. Булевы алгебры, булевы кольца и булевы решетки (161).
1.2. Гомоморфизмы, идеалы и фильтры (165). 1.3. Свободные булевы алгебры (169). 1.4. Конечные булевы алгебры (172).
§ 2. Исчисление высказываний и булевы алгебры . . . . ПЗ 2.1. Исчисление высказываний (173). 2.2. Алгебра Линден-баума — Тарского исчисления высказываний (175). 2.3. Непротиворечивость, совместность и модели (176). Глава 8. Алгебры Халмоша и исчисление предикатов .... 179
§ 1. Алгебры Халмоша............179
1.1. Кванторы, кванторные алгебры (179). 1.2. Алгебры Халмоша (183), 1.3. Носители элементов (186). § 2. Алгебры Халмоша исчисления предикатов . . ... . 188
2.1. Исчисление предикатов (188). 2.2. Алгебра Халмоша исчисления предикатов (191).
§ 3. Алгебры Халмоша с равенством. Цилиндрические алгебры 196 3.1. Равенство в алгебрах Халмоша (196). 3.2. Цилиндрические алгебры (200). | 4. Гомоморфизмы и строение алгебр Халмоша. Дополнительные
замечания..............201
4.1. Гомоморфизмы, идеалы и фильтры (201). 4.2. Простые алгебры. Теорема о полупростоте (203). 4.3. Константы, термы и предикаты (205). 4.4. Другие замечания (206).
Глава 9. Специализированные алгебры Халмоша.....208
§ 1. Алгебры Халмоша в многообразии универсальных алгебр 1.1. Аксиоматика, примеры (209). 1.2. Некоторые общие сведения (212). 1.3. Равенство в специализированных алгебрах
(217).
§ 2. Алгебра Халмоша над свободной алгеброй многообразия . 2.1. Носители элементов свободной алгебры (218). 2.2. Специализированная алгебра формул (221). 2.3. Алгебра Халмоша над свободной алгеброй многообразия (224).
§ 3. Изменение схемы............
3.1. Изменение многообразия (228). 3.2. Ядро перехода к подмногообразию (234). 3.3. Дополнительные замечания (238).
209 2J8 228
Глава 10. Связи с теорией моделей.........238
§ 1. Существование модели...........238
1.1. Вспомогательные замечания (238). 1.2. Основная теорема (241). 1.3. Дополнительные замечания (243).
§ 2. Разное................247
2.1. Непротиворечивость, совместность и полнота (247).
2.2. Некоторые применения теоремы существования модели (250). 2.3. Классы и фильтры. База знаний модели (251).
Глава 11. Категорный подход в алгебраической логике . . . 256
§ 1. Реляционные алгебры...........256
1.1. Замечания о кванторах (256). 1.2. Определение реляционных алгебр (259). 1.3. Другой подход (264).
§ 2. Реляционные алгебры, связанные с алгебрами Халмоша . . 268 2.1. Основная конструкция (268). 2.2. Алгебры отношений (276). 2.3. Дополнительные замечания (279).
§ 3. Обобщения..............280
3.1. Обобщение реляционных алгебр (280). 3.2. Интуиционистская логика и модели в топосах (281).
ЧАСТЬ 3
БАЗЫ ДАННЫХ. АЛГЕБРАИЧЕСКИЕ АСПЕКТЫ Глава 12. Алгебраическая модель базы данных......285
§ 1. Универсальная база данных.........285
1.1. Определение (285). 1.2. Функторное свойство (287). 1.3. Дополнительные замечания (289).
§ 2. Модель базы данных...........292
2.1. Определение (292). 2.2. Гомоморфизмы и категория баз данных (296).
§ 3. Динамическая база данных.........303
3.1. Предварительные замечания (303). 3.2. Динамическая алгебра Халмоша (305). 3.3. Динамическая база данных (307).
§ 4. Обобщения..............310
4.1. Недетерминированное действие (310). 4.2. Базы данных, основанные на цилиндрических и реляционных алгебрах (310). 4.3. Базы данных с нечеткой информацией.(312).
Глава 13. Эквивалентность и перестройка баз данных. Другие вопросы ..............313
§ 1. Еще о гомоморфизмах...........313
1.1. Замена схемы (313). 1.2. Каноническое разложение гомоморфизма (317). 1.3. Дополнительные замечания (318).
§ 2. Эквивалентность и перестройка........319
2.1. Базисная информация (319). 2.2. Эквивалентность баз данных (320). 2.3. Перестройка базы (321). 2.4. Изменение аксиом (323). 2.5. Перестройка схемы (324).
§ 3. Функциональные свойства отношений......327
3.1. Структура функциональных зависимостей (327). 3.2. Изменение множества атрибутов (329). 3.3. Аксиомы и функциональные зависимости (330).
§ 4. Изменение состояний. Накопление и чистка.....331
4.1. Предварительные замечания (331). 4.2. Отношения и частичные мультиотображения (332). 4.3. Накопление (333). 4.4. Чистка (334). 4.5. Взаимодействие чистки и накопления (335).
ОГЛАВЛЕНИЕ 7
Глава 14. Симметрии отношений и теория Галуа баз данных . . 336
§ 1. Теория Галуа алгебры отношений. Предварительные замечания ................337
1.1. Автоморфизмы алгебры отношений (337). 1.2. Соответствие Галуа (342). 1.3. Основные результаты (343).
§ 2. Доказательства в случае чистых алгебр Халмоша . . . 344 2.1. Доказательство первой теоремы (344). 2.2. Доказательство второй теоремы (348).
§ 3. Общий случай. Некоторые следствия......352
3.1. Предварительные замечания (352). 3.2. Доказательства теорем (355). 3.3. Некоторые следствия (357).
§ 4. Теория Галуа баз данных.......... 363
4.1. Симметрии состояний (363). 4.2. Теория Галуа баз данных (366). 4.3. Группа автоморфизмов базы данных (368). 4.4. Аксиомы и симметрии отношений (372).
Глава 15. Конструкции в теории баз данных.......374
§ 1. Конструкции без изменения схемы.......375
1.1. Общие замечания (375). 1.2. Произведение алгебр отношений (376). 1.3. Произведение баз данных (379). 1.4. Объединение баз данных (382).
§ 2. Конструкции с изменением схемы.......383
2.1. Произведение и объединение (383). 2.2. Сплетения моделей (387). 2.3. Каскадные соединения и сплетения баз данных (389). 2.4. Другие конструкции (391). 2.5. Декомпозиция (394).
§ 3. Добавление..............397
3.1. Замечания об объектах в базах данных (397). 3.2. Сети баз данных (398).
Глава 16. Обсуждение и заключение.........400
§ 1. Итоги и задачи.............400
1.1. Некоторые итоги (400). 1.2. Задачи (402). § 2. Вопросы реализации............412
2.1. Предварительные замечания (412). 2.2. Конструктивные
алгебры (413). 2.3. О конструктивных базах данных (417).
2.4. Дополнения (423). § 3. История и источники. Обсуждение.......424
3.1. Универсальная алгебра (424). 3.2. Алгебраическая логика
(426). 3.3. Базы данных (427).
Добавление при корректуре............432
Список литературы..............435
Предметный указатель..............443
Цена: 300руб.
