447 Логическое программирование и базы данных: Пер. с англ. - М.: Мир, 1992. - 352 с, ил.
ISBN 5-03-002472-7
в книге известных итальянских и австрийских специалистов систематически изложены подходы к построению дедуктивных баз данных, которые были разработаны с их участием в рамках европейских проектов по созданию новых поколений вычислительных систем. Особенность книт - удачное сочетание теоретических основ и технологии построения основных компонентов дедуктивных баз данных.
Для специалистов в области баз данных и логического программирования, искусственного интеллекта, а также для аспирантов и студентов соответствующих специальностей вузов.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Методы построения дедуктивных баз данных, требующих соединения независимо разрабатывавшихся методов управления базами данных и методов логического программирования, были разработаны за очень короткий срок (в течение 5-6 последних лет) в рамках проектов, связанных с созданием новых информационных технологий и вычислительных систем пятого поколения (стратегические программы США и Японии, стратегическая программа стран Европейского сообщества).
В предлагаемой книге изложены новые методы, которые уже зарекомендовали себя и находят практическое применение.
Эта книга в очередной раз свидетельствует о том, что эйфория от языка Пролог уже давно сменилась поисками новых языков, которые отражали бы последние достижения в области вычислительной алгебры, теории объектно-ориентированных структурированных типов данных, представления знаний, а также новых методов вычисления логических программ. Основное внимание в ней уделено языку Дейталог - логическому языку запросов к базам данных, разработка и интенсивное изучение которого осуществлялись в течение последних шести лет.
Дейталог возник как альтернатива языку Пролог в контексте дедуктивных баз данных, поскольку Пролог в качестве языка баз данных имеет ряд недостатков. Среди них назовем следующие:
• покортежная обработка (Пролог в качестве ответа на запрос возвращает отдельные кортежи, а не множество кортежей);
• процедурность и чувствительность к порядку записи правил или фактов в базе данных и к порядку предикатов в теле правила (такие языки, как SQL или реляционная алгебра, являются непроцедурными: выполнение запросов к базе данных не зависит от порядка поисковых предикатов или кортежей базы данных);
• потеря декларативности языка из-за специальных предикатов (используемых, например, для ввода-вывода, отладки или для воздействия на бэктрекинг).
Дейталог сконструирован для использования в качестве языка баз данных. Он является непроцедурным, множественным, нечувствительным к порядку языком и не имеет специальных предикатов.
Если прологовские программы имеют операционную семантику, программы на Дейталоге - чисто декларативные. При интерпретации программ на Прологе используется нисходящая схема, основанная на резолюци-онной стратегии, поиске сначала вглубь и бэктрекинге для конструирования деревьев доказательства. Базовая схема интерпретации ДейтаЛога - восходящая. В ее
основе лежат методы вычисления неподвижной точки программы и реляционная алгебра.
Пролог вместе с системами баз данных позволяет создавать слабо или сильно связанные системы, в которых средства поддержки логических программ и баз данных рассматриваются изолированно, и требуется выделять предикаты экстенсиональной базы данных для интерпретации доступа (статической при слабом связыван«и и динамической при сильном) к системе баз данных из логической программы. Дейталог же ориентирован на создание интегрированных дедуктивных систем. Идеи языка Дейталог и связанных с ним методов вычислений находят важное развитие в новых йзыках логического программирования и в языках дедуктивных объектно-ориентированных баз данных.
В книге рассмотрены синтаксис и логическая семантика Дейталога, эрбрановская теоретико-модельная интерпретация Дейталога, ориентированная на Дейталог теория логического вывода, подход к вычислению неподвижной точки программы Дейталога, идея трансляции программ на Дейталоге в систему уравнений на языке реляционной алгебры, вопросы полноты программ на Дейталоге. Важное место занимают методы оптимизации, предназначенные для достижения высокой эффективности запросов на Дейталоге. Рассмотрены различные расширения Дейталога, определяются дальнейшие усовершенствования, необходимые для применения Дейталога в реальных задачах.
В книге, достигнуто оптимальное соотношение между строгим изложением теоретических основ и техникой построения основных компонентов систем управления дедуктивными базами данных. Простота изложения, глубина и полнота рассмотрения вопросов делают книгу интересной не только для специалистов, работающих в области создания баз данных и экспертных систем, но и для преподавателей, аспирантов и студентов вузов соответствующих специальностей.
Следует отметить, что терминология в отечественной литературе в области дедуктивных баз данных еще не установилась. Поэтому при переводе приходилось предлагать свой вариант перевода терминов. В примерах баз данных, программ и запросов принято решение сохранить оригинальные обозначения переменных и предикатов, перевод которых дан в тексте.
Перевод книги выполнен Н.Н.Белоусовым (гл. 2, 6, 10), Д.Ю.Буланже (гл. 3, 12), В.И.Задорожным (гл. 4, 5, 8, 11), Л.А.Калиниченко (гл. 1, 7, 9).
Л.А.Калиниченко
ПРЕДИСЛОВИЕ
В последние годы в литературе появилось огромное число работ, посвященных проблемам логического программирования и баз данных. Этому способствовало несколько обстоятельств: выбор японским проектом ЭВМ пятого поколения Пролога и реляционной модели данных как основы создания новых архитектур ЭВМ; смещение интереса в теории баз данных в область рекурсивной обработки логических запросов; практическая разработка экспертных систем баз данных и систем баз знаний.
Настоящая книга представляет собой систематический обзор нового, быстро развивающегося направления исследований, лежащего на границе логического программирования и баз данных. Принятый в книге стиль изложения, сопровождение описания алгоритмов примерами и упражнениями позволяют сравнительно просто ввести в это новое направление студентов, аспирантов и специалистов, ранее работавших в одной из указанных областей. Мы стремились сбалансировать представление в книге теоретических и технических вопросов. Так, книга содержит подробное введение в новый язык Дейталог наряду с описанием подходов к созданию интерфейсов с большими базами данных на основе логического программирования.
Книга подразделяется на три части, которым предшествуют две вводные главы. Глава 1 содержит общий обзор рассматриваемой области. Глава 2 посвящена терминологии, нотации и основным понятиям реляционной модели и Пролога, необходимым для понимания основного материала книги.
Часть I посвящена соединению Пролога с реляционными базами данных. Глава 3 представляет Пролог как язык запросов на примере двух классических задач - проверки соблюдения антитрестовского закона и задачи о комплектующих. В главе 4 рассмотрены альтернативные архитектуры и методы соединения прологовских систем с реляционными базами данных, а в главе 5 дан обзор соответствующих конкретных проектов.
Часть II содержит описание языка Дейталог. В главе 6 определены формально синтаксис и семантика Дейталога. При определении семантики языка использован непроцедурный, теоретико-модельный подход. В главе 7 представлена теория доказательства применительно к Дейталогу, приведен алгоритм вычисления целей Дейталога и проанализированы его правильность и полнота по отношению к теоретико-модельной семантике. В ней представлены также две другие парадигмы вычисления программ Дейталога: теория неподвижной точки и
обратный вывод. В частности, в контексте Дейталога определены резолюция и SLD-резолюция.
Часть III посвящена описанию методов оптимизации запросов на Дейталоге. В главе 8 дана общая классификация методов оптимизации; при этом различаются методы переписывания, преобразующие входные программы Дейталога в оптимизированные выходные программы Дейталога, и методы вычисления, которые воспринимают на входе программу Дейталога и продуцируют ее результат. Далее приводится пример трансляции программ Дейталога в системы алгебраических уравнений. Такая трансляция позволяет определить класс алгебраических методов оптимизации запросов. Эти вопросы обсуждаются в главах 9 и 10. В главе 9 рассматриваются восходящие и нисходящие методы вычисления (включая непосредственный и полунепосредственный методы, а также метод запрос-подзапрос). Глава 10 посвящена методам переписывания, в ней рассматриваются логические (метод магических множеств, метод подсчета и метод статической фильтрации) и алгебраические методы переписывания.
В главе 11 рассматриваются расширения чистого Дейталога путем введения в него множеств и отрицания. Эта глава не претендует на полное рассмотрение проблемы, скорее она является лишь введением в предмет. Наконец, в главе 12 дан обзор основных проектов интеграции логического программирования и баз данных, включая Nail, LDL и проект ЭВМ пятого поколения.
Книга не охватывает всей проблематики дедуктивных баз данных. Например, здесь не рассматривается неполнота баз данных или проблема проверки ограничений целостности. При отборе материала книги мы ограничились проблемами, от решения которых зависит эффективность доступа к большим базам данных при использовании логического программирования в качестве языка запросов.
Книга является результатом исследований авторов совместно с другими специалистами. Мы приносим благодарность Джио Видерхольду за его вклад в подход CGW, разработанный в рамках проекта СУБЗ в Станфордском университете; Стефано Креспи-Регицци, Джанфранко Коцци, Фабриццио Коцци, Луиджи Лавацца и Роберте Зикари за их вклад в разработку алгебраического подхода к логическим запросам в рамках проекта АЛЬГРЕС; Сильвии Коцци, Фабриццио Гоцци, Марко Лульи и Гвидо Сангвинетти, разработавшим систему ПРИМО при выполнении дипломной работы в университете Модены; а также Роберте Кантарони, Стефании Феррари и Франке
Гарзотто, обращавшимся к нам с задача'ми, относящимися к логическим базам данных.
Многие из наших коллег и студентов дали полезные замечания в процессе доработки, рецензирования и редактирования рукописи. Мы хотелх бы поблагодарить Мауриса Хьютсма, который тщательно прочитал рукопись и дал ряд улучшающих книгу замечаний; Херва Галлера, Жан-Мари Николаса, Джоанн Кристоф Фрайтага и Франсуа Бри, предоставивших полезную информацию для рукописи в целом и конкретно по проектам, разрабатывавшимся в ECRC; Шамина Накви, который дал конкретные замечания по проекту LDL, разработанному в МСС; Вольфганга Нейдля, снабдившего нас материалами относительно метода запрос-подзапрос, и его модификаций. Вернер Шиманович и Алекс Ляйтш воодушевили нас интересными обсуждениями.
Особые благодарности мы приносим Гюнтеру Шлягетеру и его аспирантам, а также Ренате Питрик, Вильгельму Россак и Роберту Трашнег, чьи тщательное прочтение и критические замечания привели к улучшению качества книги. За ошибки и упущения, оставшиеся в книге, конечно же несут ответственность авторы.
Мы хотели бы поблагодарить институты, в которых работаем, за поддержку и предоставленное оборудование для редактирования рукописи: Университет Модены, Политехнический институт Милана, Технический университет Вены и Станфордский университет. При подготовке рукописи Летиция Танка использовала грант от Q.I.L.E.A. Окончательная подготовка всей рукописи была проведена под руководством д-ра Ганса Вьезнера, Ингеборга Майера и редактора Джиллиан Хайес из Издательства Шпрингер. По проекту "Progetto Finalizza-to Informatica e Calcolo Parallelo" Национального совета исследований Италии, над которым начали работать в 1989 г. , мы получили ресурсы для исследований и реализации многих идей, рассмотренных в этой книге.
Октябрь 1989
Стефано Чери. Георг Готтпоб, Летиция Тайка
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ................... 5
Предисловие ...................................... 7
Глава 1. Краткий обзор понятий логического
программирования и баз данных .................... 10
1. 1. Логическое программирование как язык
запросов ...................................... 12
1. 2. Пролог и Дейталог........................ 20
1. 3. Альтернативные архитектуры............... 23
1.4. Применения............................... 26
1. 5. Литература.............................. 27
Глава 2. Введение в реляционные базы данных и
язык Пролог..................................... 28
2. 1. Обзор реляционных баз данных............ 28
2.2. Пролог: язык программирования в логике ... 36
2.3. Литература к главе....................... 40
Часть I. Связывание Пролога с реляционными
базами данных ................................... 41
Глава 3. Пролог как язык запросов................ 41
3. 1. Антитрестовская задача................... 42
3. 2. Задача о комплектующих................... 47
3.3. Заключение............................... 52
3. S. Упражнения............................... 52
Глава 4. ' Связывание Пролог-систем и реляционных
баз данных....................................... 54
4. 1. Архитектуры для связывания Пролога и
реляционных систем ............................ 54
4. 2. Базовые конъюнкции....................... 62
4. 3. Оптимизация интерфейса Пролог/База данных. 77
4. 4. Заключение............................... 83
4. 5. Литература к главе....................... 84
4. 6. Упражнения............................... 84
Глава 5. обзор систем для связывания Пролога и реляционных баз данных ........................... 87
5. 1. PRO-SQL.................................. 87
5. 2. EDUCE.................................... 89
5. 3. ESTEAM................................... 90
5. 4. BERMUDA.................................. 91
5. 5. CGW И PRIMO.............................. 93
5. 6. QUINTUS-PROLOG........................... 95
5. 7. Литература к главе....................... 98
Часть 2. Основы языка Дейталог................... 99
Глава 6. Синтаксис и семантика языка Дейталог .... 99
6. 1. Основные определения и предположения.....100
6.2. Теория моделей Дейталога ................. ill
6. 3. Заключение...............................119
6. 4. Упражнения...............................120
Глава 7. Теория доказательства и вычислительные парадигмы Дейталога .............................. 121
7. 1. Теория доказательства для Дейталога......122
7.2. Итерация наименьшей неподвижной точки .... 130
7.3. Обратный вывод и резолюция ............... 138
7. 4. Заключение...............................156
7. 5. Литература к главе....................... 156
7. 6. Упражнения...............................157
Часть III. Методы оптимизации для Дейталога ...... 159
Глава 8. Классификация методов оптимизации для Дейталога........................................159
8.1. Критерии классификации методов оптимизации ................................... 160
8.2. Классификация методов оптимизации ........ 163
8. 3. Трансляция Дейталога в реляционную
алгебру .......................................... 166
8.4. Классификация правил Дейталога ........... 175
8.5. Выразительная мощность Дейталога ......... 182
8. 6. Литература к главе.......................183
8. 7. Упражнения........'.......................185
Глава 9. Методы вычисления .......................186
9.1. Восходящие методы вычисления ............. 186
9.2. Нисходящие методы вычисления ............. 198
9. 3. Литература к главе...................• •• • 205
9. 4. Упражнения............................... 205
Глава 10. Методы переписывания ................... 207
10.1. Логические методы переписывания ......... 207
10.2. Переписывание алгебраических систем ..... 235
10.3. Общий подход к оптимизации .............. 255
10.4. Литература к главе ...................... 260
10. 5. Упражнения..............................262
Глава 11. Расширения чистого Дейталога ........... 284
11.1. Использование встроенных предикатов в Дейталоге ..................................... 266
11.2. Введение отрицания в Дейталог ........... 269
11.3. Представление сложных объектов и манипулирование ими ........................... 292
11. 4. Заключение..............................310
11.5. Литература к главе......................310
11. 6. Упражнения..............................314
Глава 12. Обзор исследовательских проектов интеграции реляционных баз данных и систем логического программирования ..................... 316
12. 1. Система LDL.............................317
12. 2. Проект NAIL! ............................323
12. 3. Проект POSTGRES.........................327
12.4. Проект вычислительных систем пятого поколения ........................................ 330
12. 5. Проект KIWI.............................333
12.6. Проект ALGRES...........................335
12. 7. Проект PRISMA...........................337
12. 8. Литература к главе......................339
БИБЛИОГРАФИЯ ....... .............................. 341
Цена: 150руб.
