ББК 22.12 П39 УДК 510+519.7 Плоткин Б. И. Универсальная алгебра, алгебраическая логика и ба- зы данных.—М.: Наука. Гл. ред. физ.-мат. лит., 1991.—448 с.— ISBN 5-02-014635-8. Излагается одна из возможных точно математически обоснованных ма- тематических моделей «баз данных»— важнейшего понятия программиро- вания. Развиваются алгебраические, в частности, категорные основы тео- рии, различные подходы, направленные на алгебраизапию узкого ис- числения предикатов, алгебраические модели базы данных. Дается обзор проблем теории баз данных и сопоставлены различные подходы исследова- ний в этой области. Для специалистов в области алгебры и математической логики, а так- же в теоретическом и практическом программировании. Рецензент профессор С. И. Адян 1602040000—096 19-91 053(02)-91 ISBN 5-02-014635-8 © «Наука». Физматлит, 1991 ОГЛАВЛЕНИЕ Предисловие ВВЕДЕНИЕ ОБЩИЙ ВЗГЛЯД НА ЗАДАЧИ И СОДЕРЖАНИЕ КНИГИ § 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). ЧАСТЬ 1 УНИВЕРСАЛЬНАЯ АЛГЕБРА Глава 1. Множества, алгебры, модели . . ...... § 1. Множества . . . ........... 1.1. Множества, подмножества и отображения (35). 1.2. Умно- жения отображении (36). 1.3. Декартово произведение мно- жеств (36). 1.4. Свободное объединение множеств (37). 1.5. Характеристические функции подмножеств (38). 1.6. Би- нарные отношения (39). 1.7. Эквивалентность (40). 1.8. Фак- тормножество (40). 1.9. Основная теорема об отображениях (40). 1.10. Мощность множества (41). 1.11. Нечеткие множест- ва (42). § 2. Алгебры и модели ............ '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. Многосортные системы ........... 3.1. Комплекты множеств (50). 3.2. Многосортные операции и отношения (51). 3.3. Многосортные алгебры и модели (51). 3.4. Алгебра многосортных термов (53). I* Глава 2. Основные структуры . . . ....... § 1. Определения и примеры . . ........ 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. Гомоморфизмы. Свободные алгебры ....... 2.1. Определение свободной алгебры (63). 2.2. Полугруппы (63). 2.3. Группы (64). 2.4. Кольца (65). 2.5. Линейные про- странства и модули (66). 2.6. Линейные алгебры (66). § 3. Некоторые многосортные структуры ....... 3.1. Представления групп и полугрупп (67). 3.2. Линейные представления (67). 3.3. Автоматы (68). 3.4. Аффинные про- странства и аффинные автоматы (69). Глава 3. Категории .............. § 1. Общие сведения и примеры .......... 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. Некоторые рабочие понятия . . ....... 2.1. Универсальные объекты (80). 2.2. Прямые и свободные произведения—произведения и копропзведения (81). 2.3. Другие примеры универсальных объектов (83). 2.4. Тензор- ные произведения модулей (84). 2.5. Сопряженные функторы (86). 2.6. Конусы, уравнители, пределы (90). Глава 4. Категория множеств. Топосы. Нечеткие множества § 1. Дальнейшие общие понятия .......... 1.1. Замечания о категории множеств (92). 1.2. Амальгамы и коамальгамы. Декартов квадрат (93). 1.3. Полнота и копол- нота (97). 1.4. Экспоненпирование (97). 1.5. Декартово замк- нутые категории (99). § 2. Топосы . . . ............ 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. Нечеткие множества. Разное ......... 3.1. Нечеткие множества и нечеткие фактормножества (115). 3.2. Категория нечетких множеств (118). 3.3. Топос нечетких множеств (119). 3.4. Замечания об основаниях. История (121) Глава 5. Многообразия алгебр. Аксиоматизируемые классы § 1. Многообразия . . . . ......... 1.1. Замкнутые классы и свободные алгебры (122). 1.2. Клас- сы и тождества (125). 1.3. Теорема Биркгофа (127). 1.4. Вер- бальные функции (128). § 2. Некоторые конструкции . . . ....... 2.1. Свободные произведения в многообразиях (130). 2.2. Амальгамы (131). 2.3. Эпиморфизмы и мономорфизмы в многообразиях (132). оглАилляша § 3. Аксиоматизируемые классы алгебр . ...... 1 3.1. Общие замечания (133). 3.2. Фильтрованные произве- дения (134). 3.3. Квазимногообразия и псевдомногообразия (136). Глава 6. Категорная алгебра и алгебраические теории . . . 1 § 1. Клоны и клоны операций .......... 1 1.1. Клоны операций (137). 1.2. Абстрактные клоны (138). 1.3. Клоны и свободные алгебры (139). 1.4. Представления клонов и многообразия алгебр (141). § 2. Алгебраические теории ........... 1 2.1. Клоны и категории (147). 2.2. Алгебры как функторы (148). 2.3. Алгебраические теории и многообразия алгебр (151). 2.4. Дополнительные замечания (155). ЧАСТЬ 2 АЛГЕБРАИЧЕСКАЯ ЛОГИКА Глава 7. Булевы алгебры и исчисление высказываний . . . . ' § 1. Булевы алгебры ............. 1.1. Булевы алгебры, булевы кольца и булевы решетки (161). 1.2. Гомоморфизмы, идеалы и фильтры (165). 1.3. Свободные булевы алгебры (169). 1.4. Конечные булевы алгебры (172). § 2. Исчисление высказываний и булевы алгебры .... 2.1. Исчисление высказываний (173). 2.2. Алгебра Ливден- баума — Тарского исчисления высказываний (175). 2.3. Непро- тиворечивость, совместность и модели (176). Глава 8. Алгебры Халмоша и исчисление предикатов .... § 1. Алгебры Халмоша . . .......... 1.1. Кванторы, кванторные алгебры (179). 1.2. Алгебры Хал- моша (183). 1.3. Носители элементов (186). § 2. Алгебры Халмоша исчисления предикатов ..... 2.1. Исчисление предикатов (188). 2.2. Алгебра Халмоша ис- числения предикатов (191). § 3. Алгебры Халмоша с равенством. Цилиндрические алгебры 3.1. Равенство в алгебрах Халмоша (196). 3.2. Цилиндриче- ские алгебры (200). § 4. Гомоморфизмы и строение алгебр Халмоша. Дополнительные замечания .............. 4.1. Гомоморфизмы, идеалы и фильтры (201). 4.2. Простые алгебры. Теорема о полупростоте (203). 4.3. Константы, тер- мы и предикаты (205). 4.4. Другие замечания (206). Глава 9. Специализированные алгебры Халмоша ..... § 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). Глава 10. Связи с теорией моделей ......... § 1. Существование модели ........... 1.1. Вспомогательные замечания (238). 1.2. Основная теорема (241). 1.3. Дополнительные замечания (243). § 2. Разное ................ 2.1. Непротиворечивость, совместность и полнота (247). 2.2. Некоторые применения теоремы существования модели (250). 2.3. Классы и фильтры. База знаний модели (251). Глава 11. Категорный подход в алгебраической логике § 1. Реляционные алгебры ........... 1.1. Замечания о кванторах (256). 1.2. Определение реляци- онных алгебр (259). 1.3. Другой подход (264). § 2. Реляционные алгебры, связанные с алгебрами Халмоша . 2.1. Основная конструкция (268). 2.2. Алгебры отношении (276). 2.3. Дополнительные замечания (279). § 3. Обобщения .............. 3.1. Обобщение реляционных алгебр (280). 3.2. Интуицио- нистская логика и модели в топосах (281). ЧАСТЬ 3 БАЗЫ ДАННЫХ. АЛГЕБРАИЧЕСКИЕ АСПЕКТЫ Глава 12. Алгебраическая модель базы данных ...... § 1. Универсальная база данных ......... 1.1. Определение (285). 1.2. Функторное свойство (287). 1.3. Дополнительные замечания (289). § 2. Модель базы данных ........... 2.1. Определение (292). 2.2. Гомоморфизмы и категория баз данных (296). § 3. Динамическая база данных . . ....... 3.1. Предварительные замечания (303). 3.2. Динамическая алгебра Халмоша (305). 3.3. Динамическая база данных (307). § 4. Обобщения . . . ........... 4.1. Недетерминированное действие (310). 4.2. Базы данных, основанные на цилиндрических и реляционных алгебрах (310). 4.3. Базы данных с нечеткой информацией (312). Глава 13. Эквивалентность и перестройка баз данных. Другие во- просы . . . . . ......"... § 1. Еще о гомоморфизмах ........... 1.1. Замена схемы (313). 1.2. Каноническое разложение го- моморфизма (317). 1.3. Дополнительные замечания (318). § 2. Эквивалентность и перестройка ........ 2.1. Базисная информация (319). 2.2. Эквивалентность баз данных (320). 2.3. Перестройка базы (321). 2.4. Изменение ак- сиом (323). 2.5. Перестройка схемы (324). § 3. Функциональные свойства отношений . ..... 3.1. Структура функциональных зависимостей (327). 3.2. Из- менение множества атрибутов (329). 3.3. Аксиомы и функ- циональные зависимости (330). § 4. Изменение состояний. Накопление и чистка ..... 4.1. Предварительные замечания (331). 4.2. Отношения и частичные мультиотображения (332). 4.3. Накопление (333). 4.4. Чистка (334). 4.5. Взап-модействие чистки и накопления (335). Глава 14. Симметрии отношений и теория Галуа баз данных § 1. Теория Галуа алгебры отношений. Предварительные заме- чания .,.........••••• 1.1. Автоморфизмы алгебры отношений (337). 1.2. Соответ- ствие Галуа (342). 1.3. Основные результаты (343). § 2. Доказательства в случае чистых алгебр Халмоша 2.1. Доказательство первой теоремы (344). 2.2. Доказательст- во второй теоремы (348). § 3. Общий случай. Некоторые следствия . . .... 3.1. Предварительные замечания (352). 3.2. Доказательства теорем (355). 3.3. Некоторые следствия (357). § 4. Теория Галуа баз данных ......... 4.1. Симметрии состояний (363). 4.2. Теория Галуа баз дан- ных (366). 4.3. Группа автоморфизмов базы данных (368). 4.4. Аксиомы и симметрии отношений (372). Глава 15. Конструкции в теории баз данных ...... § 1. Конструкции без изменения схемы . . ..... 1.1. Общие замечания (375). 1.2. Произведение алгебр отно- шений (376). 1.3. Произведение баз данных (379). 1.4. Объ- единение баз данных (382). § 2. Конструкции с изменением схемы . . ..... 2.1. Произведение и объединение (383). 2.2. Сплетения мо- делей (387). 2.3. Каскадные соединения и сплетения баз дан- ных (389). 2.4. Другие конструкции (391). 2.5. Декомпозиция (394). § 3. Добавление . . ............ 3.1. Замечания об объектах в базах данных (397). 3.2. Сети баз данных (398). Глава 16. Обсуждение и заключение ......... § 1. Итоги и задачи ............. 1.1. Некоторые итоги (400). 1.2. Задачи (402). § 2. Вопросы реализации ............ 2.1. Предварительные замечания (412). 2.2. Конструктивные алгебры (413). 2.3. О конструктивных базах данных (417). 2.4. Дополнения (423). § 3. История и источники. Обсуждение ....... 3.1. Универсальная алгебра (424). 3.2. Алгебраическая логика (426). 3.3. Базы данных (427). СПИСОК ЛИТЕРАТУРЫ 1. Агафонов В. Н. Абстрактные типы данных // Данные в языках программирования.—М.: Мир, 1982. 2. Алгебраическая теория автоматов, языков и полугрупп/Под ред. М. Ар- биба.— М.: Статистика, 1975. 3. А н д р е к а X., Г е р г е и Т., Н е м е т и И. Многосортные языки и их связь с языками га-го порядка // Кибернетика (Киев).—1975.—№ 4.— С. 86—92. 4. Б а с а р а б И. А., Р е д ь к о В. Н. Базы данных с логико-функцио- нальной точки зрения // Программирование.— 1984.— № 2.— С. 53—67. 5. Вениаминов Е. М. Алгебраический подход к моделям баз данных реляционного типа // Семиотика и информатика.— 1979.— Вып. 14.— С. 44—80. 6. Вениаминов Е.М. Алгебраическая структура реляционных моде- лей баз данных // НТИ, сер. 2.— 1980.— № 9.— С. 23—25. 7. Вениаминов Е.М. Теория Галуа полных реляционных подалгебр алгебр отношений, логические структуры, симметрия // НТИ, сер. 2.— 1980. 8. Вениаминов Е. М. О роли симметрии в реляционных моделях баз данных и логических структурах // НТИ, сер. 2.—1984.— №. 5.— С. 17—25. 9. Б е н и а м и н о в Е.М. Основания категорного подхода к представле- нию знаний If Изв. АН СССР, Техн. кибернетика.—1988.— № 2.— С. 21-33. 10. Б и р к г о ф Г. Теория решеток.— М.: Наука, 1984. И.Биркгоф Г., Барти Т. Современная прикладная алгебра.—М.: Мир, 1976. 12. Б о р щ е в В. Б. Логический подход к описанию реляционных баз дан- ных II Семиотика и информатика.—1980.—Вып. 16.—С. 78—122. 13. Б о р щ е в В. Ю. ПРОЛОГ — основные идеи и конструкции // Приклад- ная информатика.— 1986.— Вып. 2.— С. 49—76. 14. Б о р щ е в В. В., Х о м я к о в М. В. Об информационной эквивалент- ности баз данных // НТИ, сер. 2.— 1979.— № 7.— С. 14—21. 15. Б о и к о С. Н. Теория Галуа баз данных Ц СУБД и пакета окруже- ния. Проблемы разработки и применения.— Рига, 1985.— С. 43—45. 16. Б р у д н о В. А., Скворцов Д. П., Финн В. К., Ц а л е н к о М. Ш. База данных с неполной информацией // Семиотика и информатика.— 1985.— Вып. 25.— С. 5—46. 17. Бургин М. С. Кванторы в теории свойств Ц Нестандартная семан- тическая неклассическая логика.— М., 1986.— С. 99—107. 18. Б у р г и н М. С. Операции над именованными множествами // Упо- рядоченные множества и решетки.— Вып. 9.— Саратов, 1986.— С. 3— 12. 19. Б у р г и н М. С. Функторная семантика в категориях именованных множеств II Рациональность рассуждения, коммуникация.— Киев, 1987.— С. 183—198. 20. Б у к у р И., Деляну А. Введение в теорию категорий и функто- ров.— М.: Мир, 1972. 21.Вандер Варден. Б. Алгебра.—М.: Наука, 1979. 28* СПИСОК ЛИТЕРАТУРЫ .Ван Хао, Макнотон. Аксиоматические системы теорип мно- жеств.— М.: ИЛ, 19G3. .Волков Н. Д. Алгебры Халмоша и реляционные алгебры // Латв. мат. ежегодник.—1986.—Вып. 30.—С. 110—123. Г в арами я А. А. Квазимпогообразия автоматов. Связи с квазигруп- пами II Сиб. мат. журнал.— 1985.—Т. 26, № 3.—С. 11—30. Г в а р а м и я А. А. Квазимногообразия многосортных алгебр // Тези- сы кратких сообщении международного математического конгресса. Варшава, 1983. Секция 2, Алгебра. Г в а р а м и я А. А. Аксиоматизируемые классы квазигрупп, инвари- антные при изотонии.— Деп. ВИНИТИ. № 6704—84. .Гильберт Д., А к к е р м а н В. Основы теоретической логики.— М.: ИЛ, 1947. . Г л ушко в В. М. Синтез цифровых автоматов.—М.: Физматгиз, 1962. .Глушков В. М. Основы безбумажной инсЬорматикп.— М.: Наука, 1982. Глушков В. М., Летичевский А. А. Теория автоматов и про- граммирование // Первая всесоюзная конференция по программирова- нию.— Киев, 1968.— С. 3—19. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Язы- ки. Программирование.— Киев: Наукова думка, 1978. Голдблатт Р. Топосы. Категорный анализ логики.—М.: Мир, 1983. Голосов А. О., Ц а л е н к о М. Ш. Схемы реляционных баз данных. Теория нормализации и построения нормальных форм // Прикладная информатика.—Вып. 2.—М.: Финансы и статистика, 1983.—С. 92—119. Гончаров С. С. Конструктивизируемость суператомных булевых ал- гебр // Алгебра и логика.— 1973.— Т. 12, J\» 1.— С. 31—40. Гончаров С. С. Некоторые свойства конструктивизаций булевых алгебр II Сиб. мат. журнал.— 1975.— Т. 16, № 2.— С. 264—278. Дейт К. Введение в системы баз данных.— М.: Наука, 1980. Джонстон П. Т. Теория топосов.— М.: Наука, 1986. Д р и б а с В. М. Реляционные модели баз данных.— Минск: Изд. БГУ, 1982. 3 а м у л и н А. В. Типы данных в языках программирования и базах данных.— Новосибирск: Наука, 1987. Ершов А. П. Проблемы баз данных и информационных систем на конгрессе ИФИП-80.—УСНМ.—1981.-^ 4.—С. 140—143. Ершов А. П. Вычислимость в произвольных областях и базисах // Семиотика и информатика.— 1982.— Вып. 19.— С. 3—58. Ершов Ю. Л. Теория нумераций.—М.: Наука, 1977. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели.— М.: Наука, 1980. Ершов Ю. Л. Динамическая логика над допустимыми множества- ми II ДАН СССР.— 1985.— Т. 273, № 5.— С. 1045—1048. Ершов Ю. Л., Палютин Е. А. Математическая логика.—М.: На- ука, 1987. К а л м а н Р., Ф а л б П., А р б и б М. Очерки по математической теории систем.— М.: Мир, 1971. Калужпин Л. А. Введение в общую алгебру.—М.: Наука. 1973. К а ц о в Е. Б. Многосортная логика в алгебре // Вестн. МГУ: мат. мех.— 1984.— № 5.— С. 96—97. К а ц о в Е. Б. Аксиоматизируемость классов плоских и проективных функторов II VII Всесоюзная конференция по математической логи- ке (5—7 сентября 1984 г.): Тезисы докладов.—Новосибирск, 1984.— С. 74. К а ц о в Е. Б. Аксиоматизируемость классов инъектпвных и свобод- ных функторов II XVIII Всесоюзная алгебраическая конференция (16—18 сентября 1985 г.): Тезисы сообщений, ч. 1.—Кишинев, 1985. Кейслер Г., Чен Ч. Теория моделей.—М.: Мир, 1977. СПИСОК ЛИТЕРАТУРЫ 437 Клиффорд А., Престон Г. Алгебраическая теория полугрупп.— Т. 1, 2.—М.: Мир, 1972. К л о к с и и У., М е л л и ш К. Программирование на языке ПРОЛОГ.— М.: Мир, 1987. Колмогоров А. Н., Д р а г а л и н А. Г. Введение в математиче- скую логику.—М.: Пзд-во МГУ, 1982. . Кок А., Р е и е с Г. Доктрины в категорией логике Ц Справочная кни- га по математической логике.—Ч. I: Теория моделей.—М.: Наука, 1982. Кон П. Универсальная алгебра.— М.: Мир, 1968. Кострикин А. И. Введение в алгебру.—М.: Наука, 1977. Кофман А. Введение в теорию нечетких множеств.—М.: Радио и связь, 1982. , К у р о ш А. Г. Теория групп.— М.: Наука, 1967. . Курош А. Г. Общая алгебра.—М.: Наука, 1974. . Курош А. Г. Лекции по общей алгебре.—М.: Наука, 1975. . Лен г С. Алгебра.—М.: Мир, 1968. . Л и в ч а к А. Б. Реляционные модели баз данных и полиномиальная вычислимость II НТИ, сер. 2.— 1981.— № 6.— С. 28—29. . Л и в ч а к А. Б. О семантической силе языка запросов // НТИ, сер. 2.— 1984.—№ 2.—С. 30-31. .Ливчак А. Б., Овсянников А. Я. О вычислимых запоосах к ре- ляционным базам данных // ПТИ, сер. 2.— 1983.— № 8.— С. ^29—31. . Логическое программирование: Сборник статей.— М.: Мир, 1988. . Ляпин Е. С. Полугруппы.—М.: Физматгиз, 1960. . Макленн С. Гомология.—М.: Мир, 1966. .Мальцев А. И. Модельные соответствия // Изв. АН СССР, сер. мат.— 1959.— Т. 23, № 3.— С. 313—336. .Мальцев А. И. Конструктивные алгебры // Успе:;и мат. наук.— 1961.— Т. 16, № 3.— С. 3—60. Мальцев А. И. Алгоритмы и рекурсивные функции.—М.: Наука, 1986. ..Мальцев А. Н. Алгебраические системы.—М.: Наука, 1970. . Мании Ю. И. Доказуемое и недоказуемое.—М.: Радио и связь, 1979. . Манин Ю. И. Вычислимое и невычислимое,—М.: Радио и связь, 1980. . Мартин Дж. Организация баз данных в вычислительных систе- мах.— М.: Мир, 1980. ,. М а ф ц и р Е. С. Соответствие Галуа в базах данных // Латв. мат. ежегодник.— Рига, 1989.— Вып. 33. '. М а ф ц и р Е. С., П л о т к и н Б. И. Группа автоморфизмов базы дан- ных II Укр. мат. журнал.— 1988.— Т. 40, № 3.— С. 335—345. !. М а ф ц и р Е. С., П л о т к и н Б. И. Группы автоморфизмов в теории баз данных // Латв. мат. ежегодник.-- Рига, 1990.— Вып. 34. I. Мейер Д. Теория реляционных баз данных.—М.: Мир, 1987. •.Мендельсон Э. Введение в математическую логику.— М.: Наука, 1988. [.Месарович Н., Такахара Я. Общая теория систем. Математи- ческие основы.— М.: Мир, 1978. '.Михалев А. В. Ортогонально полные многосортные алгебраические системы II ДАН СССР.— 1986.— Т. 289, № 6.— С. 1304—1308. i. М о в с и с я н Ю. М. Введение в теорию алгебр со сверхтождествами.— Ереван: Изд. ЕрГУ. 1986. t. Морозов А. С. Вычислимые группы автоморфизмов // Алгебра и ло- гика, 1986.— Т. 25, № 4.— С. 415—424. 5. М о с т о в с к и и А. Конструктивные множества и их приложения.— М.: Мир, 1973. 3. П п к у с А. Г. Конгруэнц-модулярные многообразия алгебр.— Иркутск: Изд. Иркутск, ун-та, 1986. 7. П л о т к и н Б. И. Бпавтоматы // Тр. Тбил. ун-та, сер. мат., мех., аст- СПИСОК ЛИТЕРАТУРЫ 3. П л о т к и н Б. И. Модели и базы данных // Тр. ВЦ АН ГрССР.— 1982.— Т. 21, вып. 2.— С. 50—78. ). П л о т к и н Б. И. Алгебраическая модель базы данных — автома- та II Латв. мат. ежегодник.—Рига, 1983.—Вып. 27.—С. 216—232. ). П л о т к и н Б. И. Группы автоморфизмов алгебраических систем.— М.: Наука, 1966. 1. П л о т к и н Б. И., П е р а н и д з е И. Н., Ш т е и н б у к В. В. Авто- маты, представления и полугруппы // Латв. мат. ежегодник.— Рига, 1981.— Вып. 25.— С. 222—236. i. П л о т к и п а Т. Л. Схемы накопления и чистки информации в базах данных II Латв. мат. ежегодник.—Рига, 1984.—Вып. 28.—С. 194—207. !. II л о т к и н а Т. Л. Эквивалентность и преобразования реляционных баз данных // Латв. мат. ежегодник.— Рига, 1985.— Вып. 29.— С 137— 150. i. Pa сев а Е., Сикорский Р. Математика метаматематики.—М.: На- ука, 1972. i. Роджерс X. Теория рекурсивных функций и эффективная вычис- лимость.— М.: Мир, 1972. [.Розенберг С. М. О многообразиях алгебр Халмоша // Латв. мат. ежегодник.—Рига, 1988.—Вып. 32.—С. 85—89. '.Розенберг С.М. Специализированные реляционные алгебры и ал- гебры Халмоша // Латв. мат. ежегодник.— Рига, 1990. Вып. 34. 1. Сикорский Р. Булевы алгебры.—М.: Мир, 1969. '.Скворцов Д. П., Финн В. К. Замечания об одном расширении языка многосортной логики предикатов // НТИ, сер. 2.—1981.—«Ns 8.— С. 25—26. '.Скорняков Л. А. Элементы общей алгебры.—М.: Наука, 1983. . С тол л Р. Множества. Логика. Аксиоматические теории.—М.: Просве- щение, 1968. .. Суставова В. Е. Функциональные зависимости и аксиомы баз дан- ных Н Латв. мат. ежегодник.— 1986.— Вып. 30.— С. 162—167. . Ульман Дж. Основы систем баз данных.—М.: Финансы и статис- тика, 1983. .Успенский В. А., Семенов А. П. Теория алгоритмов: основные открытия и приложения.— М.: Наука, 1987. .Финн В. К. К формальному определению понятия информационно- поисковой системы II НТИ, сер. 2.— 1981.— № 5.— С. 5—22. .Френкель А., Бар-Хиллел И. Основания теории множеств.— М.: Мир, 1966. .Цаленко М.Ш. Реляционные модели баз данных.— I Ц Алгоритмы и организация решения экономических задач.— М., 1977.— Вып. 9.— С. 18—36.— II II Алгоритмы и организация решения экономических задач.— М., 1977.— Вып. 10.— С. 16—29. .Цаленко М. Ш. Основные задачи теории баз данных // НТИ, сер. 2.— 1983.— № 3.— С. 1—7. .Цаленко М. Ш. Семантические и математические модели баз дан- ных.—М.: ВИНИТИ, сер. информатика. 1985. (Итоги науки и техники). Цаленко М. Ш., Шульгейфер Е.Г. Основы теории категории — М.: Наука, 1974. .Цирулис Я. П. Модель базы данных с недетерминированными пе- реходами II Теория алгоритмов и программ.— Рига, 1986.— С. 87—95. Цирулис Я. П. Цилиндрические и реляционные алгебры — равно- сильность двух понятий алгебры отношений.— Деп. РФАН Латв. ССР, 21.10.86, инф. № ИТ0008. Цирулис Я. П. Абстрактное описание типов данных и многообра- зии алгебр данных ,/Алгебра и дискретная математика: Теоретические основы математического обеспечения ЭВМ.— Рига, 1986.— С. 131—144. . Эсакиа Л. Л. Алгебры Рейтинга, I: Теория двойственности.—Тби- лиси: Мецниереба, 1985. 439 СПИСОК ЛИТЕРАТУРЫ 115. An are I? a H., Nemety I. A simple purely algebraic proof of the completeness of some first order logics // Alg. L'niv.—1975.—V. 5.— P. 8—15. 116. Andreka H., Nemety I. On universal algebraic construction of lo- gic If Studia Logica.— 1977.—V. 36.—P. 9—47. 117. Andreka H., Nemety I. Applications of universal algebra, model theory, and categories in computer science (survey and bibliography) // Сотр. Ling. and Сотр. Lang.— 1979.— V. 13.— P. 251—282. 118. Andreka H., Nemety I. Importance of universal algebra for com- puter science // Universal Algebra and Links Logic Algebra, Combinato- rics and Computer ScL— Berlin, 1984.— P. 204—215. 119. Andreka H., Nemety I. Dynamic algebras and their representation theory, an introduction for mathematicians.— Preprint Math. Inst. Hun- gar. Acad. Sci. Budapest. 120. Armstrong W. \V. Dependency structures for database relationships // Information processing-74.—Amsterdam: North-Holland, 1974.—P. 580— 583. 121. В ancil 1 on F. On the completeness of query language for relational databases // Lect. Notes in Comput. Sci.—1978.—V. 64.—P. 112— 123. 122. В а г г М. Fuzzy set theory and topos theory // Canad. Math. Bull.— 1986.—V. 29(4).—P. 501—508. 123 Bhattacharrya P. Fuzzy subgroups: some characterizations // J. Math. Anal. Appl.— 1987.— V. 128, N 1.— Р. 241—252. 124. BirkhoffG.,Lipson J. Heterogeneous algebras // J. Comb. Theo- ry.—1970.—V. 8, N l.—P. 115—133. 125. Category Theory and Computer Programming // Lect. Notes in Comput. Sci.— 1986.— N 240. 126. Cirulis J. Generalizing the notion of poliadic algebras // Bull. Sect. Log.— 1986.— V. 15, N 1.— Р. 2—9. 127. С о d d E. F. A relational model of data for large shared data banks // Communications of ACM.— 1970.— V. 13, N 6.— Р. 377—387. 128. С о d d E. F. Extending the database relational model to capture more- meaning II ACM trans. of database systems.—1979.—V. 3, N 4.—Р. 397— 434. 129. С о d d E. F. Relational Database: A Practical Foundation for Productivi- ty II Comm. of ACM.— 1982.—V. 25, N 1.— Р. 109—117. 130. D a i g n e u 11 A. On automorphisms of polyadic algebras // Trans. Amer. Math. SOC.—1964.—V. 112.—P. 84—130. 131. DallenD.,Van de Vries E.F. Intuitionistic free abelian groups/ Z. math. Logik Grundl. Math.— 1988.— V. 34, N 1.— Р. 3—12. 132. Eilenberg S. Automata, langugages and mashines.— N. Y.; San Fran- cisco; London; Acad, Press., 1974. 133. Feferman S. Application of many-sorted interpolation theorems // Proceedings of the Tarski Simpozium, Providence, R. I.: Amer. Math. Sci., 1974.— P. 205—224. 134. G a lie г В. Cilindric and polyadic algebras.—1977. 135. Georgescu J.A categorical approach to knowledge-based systems // Computers and Artificial Intelegence.-1984.-N 2.—P. 105—113. 136. G е г 1 a G. Code theory and fuzzy subsemigroups // J. Math Anal. Appl.— 1987.— V. 128, N 2.— Р. 362—369 137. Goguen J. А., Т hatcher J. W., Wagner E. G., W right J. B. Introduction to categories, algebraic theories and algebras.— IBM Re- search Report. RC 5369, 1975. 138. Goguen J.A. A junction between computer science and category theo- ry, I—II.— IBM Thomas J. Watson Res. Center, Report RC 6908, 1976. 139. Goguen J. A. Concept representation in natural and artificial langua- ges II Axioms, extensions and applications for fuzzy sets.— Int. Man-Ma- shine Studies.-1974.-V. 6.—P. 513—561. О СПИСОК ЛИТЕРАТУРЫ О Gray J. Categorical aspect of data type constructors // Theor. Comput. Sci—1987.—V. 50, N 2.—P. 103—135. 1. Halmos P. R. Algebraic logic.—N. Y., 1962. 2 Н о h 1 е V. Fuzzy sets and subobjects // Fuzzy Sets Theory and Appl.— Dordrecht: Proc. NATO Adv. Study Inst., 1986.—P. 69—76. 3. H e n k i n L., M о n k I. D., Т а г s k у A. Cylindric algebras, Part 1.— Amsterdam; London, 1971. 4. H e n k i n L., Monk I. D., Т a r s k у A. Cylindric algebras. Part 2.— N. Y.; Amsterdam; Oxford: North-Holland, 1985. 5. H e n k i n L., Monk I. D., Т а г s k у A., A n d r e k a H., Neme- ty I. Cylindric set algebras.—Berlin; Heidelberg; N. Y.: Springer, 1981. S H i g g i n s P. J. Algebras with a scheme of operators // Malh. Nachrich- ten.-1963.-V. 27, N 1—2—P. 115—132. 7 H i g g s D. Integrity in the topos of complete Heytiag algebra valued sets If Canad. J. Math.-1984.-V. 36, N 3.—P. 550—568. 3. H i g g s D. A category approach to Boolean valued modeles.— Preprint University of Waterloo, 1973. 4. J о h n s tо n e P. T. Collapsed toposes and cartesian closed varieties.— University of Cambridge, preprint, 1988. 0. J о h n s t о n e P. T. When is a variety a topos? // Algebra Univerea- lis.-1985.-V. 21.-P. 198-212. LJonsson B. Varieties of relation algebras f/ Universalis.—1982.— V. 15.— P. 273—298. !. K a t s о v E. В. Many-sorted logic and exiomatizibility of homological classes of functors // East European Category Seminar'Summaries, ^Bul- garia, Prevala, 1987. i. К о z e n D. A representation theorem for models of *-free PDL.—N. Y.: IBM Research, 1979. :. K r a s n e r M. I. Une generalization de la notion de corps // J. Math pu- re appl.—1938—V. 17.—P. 367—385. i. K r a s n e r M. I. Generalization et analogues de la theorie de Galois // Congress de la Victorie de L'Ass. France Avancem. Sci.— 1945.— P. 54— 58. 5. Lawvere F. W. An elementary theory of the category of sets // Proc. Nat. Acad. Sci. USA.—1964—V. 52.—P. 1506—1510. .Lawvere F. W. Adjointness and foundations.— Dialectica.— 1969 — V. 23.- P. 281— 296. 1. Lawvere F. W. Some algebraic problems in the context of functorial semantics of algebraic theories // Rep. Midwest Category Seminar II.— V. 61.— Berlin: Springer-Verlag, 1968.— P. 41—61. ).Leblanc L. Nonhomogeneous polyadic algebras // Proc. Amer. Math. Soc.— 1962.— V. 13, N 1.— Р. 59—65. . L i n t о n F. Some aspects of equational categories // Proc. La Jolla Conf. on Categorial Algebra.— Berlin: Springer-Verlag, 1966.— P. 84—94. . McKenzie B. Finite equational bases congruence modular varieties // Algebra Universalis, 1987.— V. 24, N 3.— Р. 224—250. . M с К i n s 1 е у J. С. С. The decision problem for some classes of senten- ces without quantifiers // J. Svinbol. Log.—1943.— V 8, N 3.— P. 61— 76. M а с L a n e S. Categories for the working mathematician.— Berlin; Hei- delberg; N. Y.: Springer-Verlag, 1971.—P. 262. M а с L a n e S. Diagrams, equations and theories in categories // Univer- sal Algebra and Links Logic, Algebra, Combinatorics and Computer Sci.— Berlin, 1984.— P. 143—149. Manca V., Salibra A. First-order theories as many-sorted algeb- ras II Notre Dame J. Formal Logic.— 1984.—P. 86—94. M a 11 h i e s s e n G. A heterogeneous algebraic approach to some prob- lems in automata theory, many-valued logic and other topics // Contr. to General Algebra Proc. Klagentfurt Conf.— 1978.— P. 193—211. 441 СПИСОК ЛИТЕРАТУРЫ 167. Monk D. Mathematical Logic.— Berlin; Heidelberg; N. Y.: Springer' Verlag, 1976. 168. Nemety I. Some universal algebraic and model theoretic results of computer science // Proc. 3-d Hung. Сотр. Sci. Conf.— 1981.— P. 125—143. 169. Nemety I. Dynamic algebras of programs/Fundamentals of computa- tion theory.— Berlin: Springer, 1981. Lect. Notes in Сотр. Sci. V. 117.— P. 281—290. 170. Nemety I. Some constructions of cylindric algebras theory applied to dynamic algebras of programs // Сотр. Linguist. Сотр. Lang.— 1980.— V. 14.— P. 43—65. 171. Plotkin B. I. Galois theory of databases /f Algebra, some current trends.— Berlin: Springer-Verlag, 1988.— P. 147—162. 172. P о i n t e r С. A simpler set of axioms for poiyadic algebras // Fundaraen" ta Math.— 1973.— P. 223—232. 173. P о s с h е 1 R., K a 1 u z n i n L. A. Funktionen und relationen algebren.— Berlin, 1979. 174. P rat t V. Dynamic algebras: examples, constructions, applications.— Report MIT/LCS/TM—138, 1979. 175. Pratt V. Models of program logics // Proc. IEEE Conf. of found, cf сотр. science.— San Juan, 1979. 176. Quellet R. A categorial approach to polyadic algebras f/ Studia Logi- ca.-1982.-V. 41, N 4.—P. 317—327. 177. R о топ о D. Rings and fields, a constructive view // Z. math,. Logik Grundl. Math.— 1988.— V. 34, N 1.— Р. 25—40. 178. Sangalli A. On the structure and representation of clones // Algebra Universalis.—1988.—V. 25, N 1.—Р. 101—106. 179. Ton k ova V., ReitermanJ. Dynamic algebras with test // J. Com- put. Syst. Sci.— 1987.— V. 35, N 2.— Р. 229—242. 180. Universal algebra and its links with logics.— Berlin; Heldermann, 1984. 181. Van H а о. Logic of Many-Sorted Theories // J. Symbol. Log.— 1972.— V. 17, N 2. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА 182. Гончаров С. С. Счетные булевы алгебры.— Новосибирск: Наука, 1988. 183. П и н у с А. Г. Конгруэнп-дистрибутивные многообразия алгебр // Ито- ги науки и техники, сер. алгебра, топология, геометрия.— Т. 26. M.: ВИНИТИ, 1988.— С. 45—83. 184. Цаленко M. Ш. Моделирование семантики в базах данных.—M.: Наука,1989. 185. A n d r ё k a H., S a i n I. Connections between algebraic logic and ini- tial algebra semantifcs of CF languages // Mathematical Logic in Compu- ter Science. Colloq. Math. Soc. J. Bolyai.— 1978.— V. 26.— P. 25—83. 186. Biro В., S h e e a h S. Isoinorphic but not lower base-isomorphic cvlin- dric set, aigpbras // J. Symbol. Log.-1988.-V. 53, N 3.—P. 846—853. 187. Biro В., S e r e n у G. An explicit characterisation of some non-repre- sentableic cylindric algebras // Mathematical institute of the Hungarian academy of sciences. Preprint № 9/1989, Budapest. 188. D i a g n e a u 11 A., Monk D. Representation theory for polyadic al- gebras II Fundam. Math.-1963.-V. 53.—P. 151—176. 189. Georgescu G. Modal polyadic algebras // Bull. Math. Society Science. Math. Romania.-1979.-V. 23(71), N l.-P. 49-64. СП11ДОК ЛИТЕРАТУРЫ 442 G-corgescu р. A representation theorem for polyadic Heyting algeb- ras II Algebra universales.— 1982.— V. 14, N 2a.— Р. 197—209. 191. Imielinski Т., Lipski W. The relational model of data and cy- lindric algebras // J. Compnt. Syst. Sci.—1984.—V. 28—P. 80—102. 192. К e isle г Н. J. A complete first-order logic with infinitary predicates // Fundam. Math.-1963.-V. 52.—P. 117—203. 193. Lambek J., Scott B. Introduction to higher order categorical logic.— Cambridge (Mass.): Cambridge Univ. Press, 1980. 194. Makkai M., Re yes G. First Order Categorical Logic.—Berlin: Spnn- ger-Verlag, 1977. 195. Manes E. G. Algebraic Theories.—N. Y.: Springer-Verlag, 1976. 196. Salibra A. A general theory of algebras with quantifiers // Univ. of Pisa. Dip. Informatica Corso Italia.— 1989.— V. 40.— P. 1—25. 197. Грэй П. Логика, алгебра и базы данных.—M.: Машиностроение, 1989.— С. 359. 198. Nemeti I. Algebraizations of quantifier logics, an introductory over- view.— Preprint, 1990. 190. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Абелева группа 55 Абстрактная база данных 313 — теория 259 Абстрактный класс 135 — клон 138 Автомат 31, 68 «-автомат 32, 69, 293 Аксиоматизируемый класс 133, 134 Аксиомы в базах данных 295 Алгебра 29, 43 — Рейтинга 113, 280 — Линдёнбаума интуиционистского исчисления высказываний 282 — Линдёнбаума — Тарского 175 — многосортных термов 53 — счетного ранга 127 — термов 47 — Халмоша 30, 183 Алгебраическая система 44 — теория 137, 151 Алгебраически замкнутое поле 59 Амальгама 99, 131 Ассоциативная алгебра над К 61 Атом .булевой алгебры 172 Аффинное отображение 70 — пространство 69 Аффинный автомат 71 га-арная операция 42 я-арное отношение 43 Вербальная конгруэнция 126 — функция 128 Вербальный функтор (вербал) 89 Вполне характеристическая конгру- энция 126 Выводимость формулы 174 Выводимый элемент 167 Вычислимая операция 414 Главный идеал булевой алгебры 166 — — кольца 65 — фильтр булевой алгебры 166 Гомоморфизм алгебр 44 — — Халмоша с переменной схемой 330 — баз данных 296, 300 — булевых алгебр 162 — моделей 45 — — с переменными отношениями 390 — первого и второго рода 314 Гомотопия 57 Градуированное отображение 387 График отношения 43 Группа 55 — автоморфизмов объекта 72 — симметрии отношения 342 Групповая алгебра 62 Группоид 57 База данных 11, 33, 292, 295 —, основанная на реляционных ал- гебрах 311 —с нечеткой информацией 312 — знаний модели 251 Базисная информация 319 Базисное отношение 19 Базисный набор 320 Биективное отображение (биекция) 36 Бинарное отношение 39 Булеан множества 35 Булев топос 114 Булева алгебра 161 — решетка 165 Булево кольцо 163 Двузначный топос 108 Декартов квадрат 94 Декартово замкнутая категория 99 — произведение алгебр 47 — — множеств 36 — — моделей 47 Диагональ 200 Динамическая алгебра Халмоша 306 — база данных 309 Динамический *-автомат 308 Дискретное прямое произведение групп 82 Дистрибутивная решетка 165 Домены 17, 189 Дуальная (двойственная) категория 75 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 444 Единичная операция 138 Единичное отображение 36 Естественное отображение множест- ва на фактормножество 40 Задание алгебры образующими и оп- ределяющими соотношениями 48 Замена схемы 314 Замкнутый класс 123 Замыкание Галуа 125 Идеал алгебры Халыоша 202, 212 — булевой алгебры 165 — в полугруппе 63 — кольца 65 Изменение состояний 303 Изоморфизм алгебр 45 — баз данных 300 — моделей 45 — функторов 78 Изотония 57 Имя стрелки 101 Инициальный сорт 221 Интерпретация формул 189 Интуиционистское исчисление вы- сказываний 282 — — предикатов 284 Инъективное отображение (инъек- ция) 35 Иорданова алгебра 63 Исчисление высказываний 173 Канторовская нумерующая функция 415 Каскадное соединение баз 392 — — моделей 392 Категория 72 — нечетких множеств (0-множеетв) .118 Квазигруппа 56 Квазимногообразие 134 Квазитождество 134 Квантор всеобщности 181 — существования 180, 181, 182 Кванторная алгебра 183 Классификатор подобъектов 104 Классический топос 108 Клон операций 137 Ковариантный функтор 76 Коконус 90 Кольцо 57 — с единицей 57 Коммутативное кольцо 57 Комплект, Г-комплект 50 Конгруэнция 46 —^ Риса 63 Конечно полная категория 97 Конечное отображение 332 — состояние 332 Конкретная база данных 313 Константа в алгебре Халмоша 205 Конструктивная алгебра 417 — база данных 417, 428 Контравариантный функтор 76 Конус 90 Копольная категория 97 Копредел диаграммы 91 Копроизведение (свободное произве- дение) 82 Коуравнитель 91 Критерий Сикорского 172 Левый идеал в полугруппе 63 Лиева алгебра 62 Линеаризация полугруппы 83 Линейное представление 67 — пространство над полем 59 Линейный автомат 68 Локально конечная алгебра Халмо- ша 187 Лупа 57 Максимальный идеал 168, 204 Малая категория 73 Многообразие 125 — алгебр 21, 49 — клонов 139 Многосортные алгебры 51 — модели 51 Множество образующих алгебры 48 Модель 44 — базы данных 31 — набора 177 — (применительно к топосу) 283 Модуль 60 Моноид 54 Мономорфизм 45, 74 Морфизм функторов 78 Мощность множества 41 Мультиотображенпе 39 Набор символов отношений 189 Негативный элемент 254 Ненулевой объект 109 Непротиворечивое подмножество 249 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 445 Непротиворечивость 248 Непротиворечивый набор 177,178 Непустой объект 109 Нечеткие отношения 42 —отображения 118 — — четких множеств 42 Нечеткое множество 42, 116 — равенство 116 Нижняя грань 164 — точная грань 164 Нормализатор 371 Нормальный делитель (инвариант- ная подгруппа) 64 Носитель формулы 192, 222 — функции 170 —элемента 139, 210, 218 — элемента алгебры Халмоша 187, 188 Нулевая характеристика 59 Нульарная операция 43 Нульарный оператор 138 Нумерация 413 Нумерованная алгебра 414 Нумерованное множество 413 Нумерованный комплект 416 Образ конгруэнции при гомоморфиз- ме 128 Обратное отображение 36 Обратный образ (коамальгама) 93 — элемент в полугруппе 54 Объединение баз данных 382, 394 Объект-степень 106 Ограничения целостности 29 Однотипные алгебры 44 Одноэлементная алгебра 131 Оператор замыкания 122, 181 Основное соотношение 102 Относительное псевдодополнение 113 Отношение порядка 40 Перечислимое множество 416 Подалгебра 46 — Я-алгебры 52 Подбаза 375 Подкатегория 73 Подмодель 47 Подмодуль 66 Подобъект 101 Подстановка множества 54 Подфунктор 80 Позитивный элемент 254 Поле 58 Полная категория 97 •— подкатегория 73 Полное Й-множестпо 120 Полнота 248 Полный автомат 366 Полуавтомат 69 Полугомоморфизм базы данных 320 Полугруппа 54 — накоплений 333 — с единицей 54 — сдвигов 335 — эндоморфизмов объекта 72 Полугрупповая алгебра 62 Полугрупповой автомат 68. 319 Полупростая алгебра 168, 294 Правильная подстановка 338 Правый идеал в полугруппе 63 Предел диаграммы 91 Предикат в алгебре .Халмоша 205 Представление групп 67 — клона 141 — полугрупп 67 Представляющий функтор 77 Принцип экзистенциальное™ для стрелок 108 Произведение автоматов 381 — баз данных 382 — гомоморфизмов 317 Прообраз конгруэнции при гомомор- физме 129 Простая алгебра 168, 203 — — Халмоша 204 Прямое произведение 81 Псевдодополнение 113 Псевдомногообразие 134 Псевдотождество 134 Равенство в алгебре Халмоша 196, 217, 227 Равномощные множества 41 Радикал 89 Радикальный класс 89 Разрешимая нумерация 414, 416 Реализация 241 Регулярное действие 333 Рекурсивное подмножество 415 Реляционная алгебра 259 — база данных 21 — модель 27 Решетка 164 — с псевдодополнениями 113 га-развертка 415 Свободное объединение множеств 37 — произведение алгебр 130 — — с объединенной подалгеброй 132 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 446 Сетевая база данных 26 Сети баз данных 398 Сжатие отображения 335 — состояния 335 Симметричная функция 197 Синглетон 120 Синтаксис теории 153 Синтаксическое определение алгеб- ры Халмоша 249 Система аксиом баз данных 28 Слоение множества 50 Смежный класс по эквивалентности 40 Собственный идеал 166 — фильтр 166 Совместность 247, 249 Совместный набор 176, 179 Соответствие Галуа 125 Сопряженные отображения 258 — функторы 87 Состояние базы данных 286 Специализированная алгебра Халмо- ша 209 Специальная алгебра Халмоша 203 Сплетение баз данных 396 Структура функциональных зависи- мостей 328 Сюръективное отображение (сюръек- ция) 35 ге-свертка 415 Тавтология 174, 248, 382 Тело 58 Тензорное произведение модулей 85 Теорема единственности равенства 199 — компактности 179 — Стоуна 168 Терминальный сорт 221 Термы 47 Тип операции 51 — отношения 51 Тождество ассоциативности 164 — идемпотентности 164 — коммутативности 164 — поглощения 164 Тождество алгебры 125 — класса 125 Топос 105, 280 — G-полигонов 110 Точечный топос 108 Точная база 320 — верхняя грань 164 Транзитивная функция 197 Трансформационная алгебра 186 Ультрапроизведение 135, 245 Ультрафильтр 134 3 -ультрафильтр 239 Умножение бинарных отношений 39 — отображений 36 Универсальная аксиоматизируемость 134 — алгебра 29 — база данных 287 Универсальное каскадное соедине- ние 388 Универсальный отталкивающий (инициальный) объект 80 — притягивающий (терминальный) объект 80 Уравнитель 91 Факторалгебра 45 Факторкомплект 52 Фактормножество по эквивалентно- сти 40 Факторфунктор 80 Фильтр i34 — алгебры Халмоша 202, 213 — булевой алгебры 166 — над множеством 249 Фильтрованные произведения 135, 245 Формулы языка УЗКОГО исчисления предикатов 189 Функтор 76 Характеристика поля 59 Характеристическая стрелка моно- морфизма 105 — функция подмножества 38 Центрированная система 240 Цилиндрическая алгебра 200 Частичное мультиотображение 26, 39, 332 Четкие отображения нечетких мно- жеств 42 Чистка 334 Эквациональные теории 155 Эквивалентность баз данных 321 — на множестве 40 — наборов элементов 326, 357 — схем баз данных 321 Эквивалентные категории 79 — формулы 16 Экспонента (экпоненциал) 98 Экспоненцирование 98 Элементарная формула 18, 125 Элементарно аксиоматизируемый класс 255 Ядро отображения 40 Научное издание Плоткин Борис Исакович УНИВЕРСАЛЬНАЯ АЛГЕБРА, АЛГЕБРАИЧЕСКАЯ ЛОГИКА И БАЗЫ ДАННЫХ Заведующий редакцией А. П. Баева "--•:' Редакторы В. В. Донченко, И. Е. Морозова Художественный редактор Г. М. Коровина Технический редактор С. Я. Шкляр Корректор И. Я. Кришталъ ИБ № 41277 Сдано в набор 14.08.90. Подписано к печати 10.09,91. Формат 60Х90/16. Бумага тип. № 1. Гарнитура обыкновенная. Печать высокая. Усл. печ. л. 28. Усл. кр.-отт. 28. Уч.-изд. л. 28,84. Тираж 3960 экз. Заказ .Ne 348. Цена 5 р. 80 к. Издательско-производственное и книготорговое объединение «Наука» Главная редакция физико-математической литературы 117071 Москва В-71, Ленинский проспект, 15 Четвертая типография издательства «Наука» 630077 Новосибирск, 77, Станиславского, 25