Лабораторная работа 2
Пролог-программы как простейшие базы данных и знаний

Цель работы:
1. Знакомство с организацией баз данных как совокупности фактов.
2. Получение навыков организации явных и неявных баз данных.
3. Изучение способов построения универсальных запросов к базам.
4. Знакомство с представлением знаний в виде правил и процедур.

1. Введение

       Система понятий для представления знаний несколько отличается от понятий для представления данных. Вместе с тем база знаний (БЗ) способна хранить данные и как простую разновидность знаний в виде базы данных (БД). Запросы, которые формирует пользователь к базе, реализуются одним из двух возможных способов:
- сообщения, являющиеся ответом на запрос, хранятся в явном виде в БД, и процесс получения ответа представляет собой выделение подмножества значений из БД, удовлетворяющих запросу;
- ответ не существует в явном виде в БД и формируется в процессе логического вывода на основании имеющихся данных.

       Последний случай принципиально отличается от технологий использования БД и рассматривается в рамках представления знаний, то есть информации, необходимой в процессе вывода новых фактов. В Пролог-программах вывод новых фактов возможен на основании набора правил, включаемых в программу и представляющих собой упрощенный вариант БЗ. Представление знаний в виде набора правил имеет следующие преимущества:
- простота создания и понимания отдельных правил;
- простота механизма логического вывода.

       К недостаткам этого способа организации БЗ относится его отличие от человеческой структуры знаний.

2. Запросы к базе данных

       Простейшая Пролог-программа представляет собой множество фактов, которое неформально называют базой данных.

       Рассмотрим пример. Пусть для хранения информации о служащих и местах их работы необходимо создать БД со структурой отношения РАБОТАЕТ (ИМЯ, ОТДЕЛ). При этом атрибут ИМЯ описывает домен данных типа строки символов, а атрибут ОТДЕЛ - домен целочисленных данных.
/* Программа 4 */
domains
name = string
office = integer
predicates
work( name , office )
clauses
work( "Петров" , 101 )
work( "Павлов" , 211 )
work( "Сидоров" , 101)
Для решения поставленной задачи в Пролог-программе:
- исходное отношение описывается предикатом аналогичной структуры;
- в секции domains задаются области изменения каждого аргумента предиката;
- каждый кортеж данного отношения представляется в секции clauses в виде факта.

       Одним из примеров программы, реализующих данную задачу, может быть приведенная здесь программа 4.

       После того, как данная программа введена в систему Турбо-Пролога с помощью текстового редактора или загружена с диска, а затем запушена на выполнение командой Вып главного меню системы, активизируется окно диалога (появляется сообщение Goal:) и система готова к приему запросов. Синонимом слова запрос является слово цель. В переводе с английского goal обозначает цель.

2.1. Простые запросы

       Простой запрос состоит из имени предиката, за которым располагается список аргументов.

       Если в запрос входят только константы (т.е. атомы и числа), то такой запрос называется запросом с константами и на него система выдает только один из двух ответов - True или False. Ответ True свидетельствует о том, что система доказала истинность запроса в соответствии с множеством фактов, загруженных в нее в данный момент. Ответ False - это невозможность системы доказать истинность запроса. Приведенные в окне диалога запросы соответствуют вопросам:
- "Работает ли Павлов в 211 отделе?". Ответ на него можно трактовать так: "Да, работает Павлов в 211 отделе"
- "Работает ли Павлов в 101 отделе?". Ответ на который: "Нет, не работает Павлов в 101 отделе".

       Однако применение запросов с константами весьма ограничено, поэтому наиболее часто применяются запросы, которые используют переменные - запросы с переменными.

       Переменная - это вид терма, начинающийся с заглавной буквы. В запросе, содержащем переменную, неявно спрашивается о том, существует ли хотя бы одно значение переменной, при котором запрос будет истинным.

       Т.е. переменные в запросах квантифицированы экзистенциально. Если это иметь в виду, то приведенный в окне диалога запрос можно прочесть так: "Существует ли хотя бы один человек, который работает в 101-м отделе?". Запрос будет истинным, если такое лицо будет найдено в текущей базе.

       Система пытается унифицировать (т.е. согласовать) аргументы запроса с аргументами фактов, входящих в базу данных "work". Запрос окажется успешным при его сопоставлении с первым же фактом, поскольку атом "101" в запросе унифицируется с атомом "101" первого факта, а переменная "Who" унифицируется с атомом "Петров", входящим в этот факт. В результате данного процесса переменная "Who" примет значение атома "Петров", сообщение о чем и выводится в окне диалога.

       Далее происходит сопоставление запроса с другими фактами БД и о всех успешных унификациях и их количестве выдается сообщение в окне диалога. Говорят, что переменная конкретизируется, когда при выполнении запроса она унифицируется с некоторым значением.

2.2. Составные запросы

       Составные запросы образуются из простых, соединенных между собой запятыми. Каждый простой запрос называется подцелью. Для того, чтобы составной запрос оказался истинным, необходимо, чтобы каждая из его подцелей была бы истинной. Введем составной запрос, который будет соответствовать вопросу: "Есть ли такой отдел, где вместе работают Петров и Сидоров?"
Goal: work("Петров",X),work("Сидоров",X)
Х=101
1
Goal:
       Переменная Х входит в обе подцели, т.е. для истинности всего запроса требуется, чтобы вторые аргументы в каждой из подцелей принимали одни и те же значения.

       Использование констант в аргументах запроса эквивалентно заданию входных параметров программы. Использование переменных - эквивалентно требованию получить от программы выходные данные.

2.3. Запросы с анонимными переменными

       Символ подчеркивания (_) выступает в качестве анонимной переменной, которая предписывает системе проигнорировать значение аргумента. Эта переменная унифицируется с чем угодно, но не обеспечивает выдачу на экран данных. Каждая анонимная переменная, входящая в запрос, отличается от других переменных этого запроса.

       Посмотрим, что будет, если ввести запрос work(Worker,_). При выполнении этого запроса будут выданы все возможные значения первого аргумента предиката work(...), вне зависимости от того, какие значения будет принимать второй аргумент. Таким образом данный запрос соответствует вопросу:

"Существует ли хотя бы один служащий, который работает в каком-либо из отделов?"
Сформированный к программе запрос аналогичен желанию получить данные о всех служащих, работающих во всех отделах фирмы.
Goal: work(Worker,_)
Worker="Петров"
Worker="Павлов"
Worker="Сидоров"
3
Goal:

3. Статические и динамические базы данных

       Как уже отмечалось, множество фактов Пролог-программы можно рассматривать как базы данных, к которой могут формулироваться любые произвольные запросы. Однако, данные такой БД жестко связаны с самой Пролог-программой. Любое манипулирование с БД требует изменения или добавления того или иного факта в текст программы. В связи с этим такие базы данных называют статическими БД.

       Так, для ввода информации о поступлении на службу в 101 отдел Иванова, нам потребуется войти в режим редактирования программы и добавить новый факт.
/* Программа 4 */
. . . .
clauses
. . . .
work( "Петров" , 101 ).



Goal: work(Worker,_)
Worker="Петров"
Worker="Павлов"
Worker="Сидоров"
Worker="Иванов"
4
Goal:
       Если затем в режиме выполнения мы зададим запрос о сотрудниках всех отделов, то получим информацию уже о четырех служащих. Причем обратите внимание, что в ответе на запрос данные об Иванове будут выводиться в той, по номеру, строке, каким по счету в программе является факт о работе Иванова в 101 отделе.

       Попробуйте, войдя в режим редактирования, переставить факты местами. Затем, войдя в режим выполнения, сформулировать запрос к базе. Заметьте, что система находит ответы в БД в том порядке, как они введены в программе. 5h'o еще одна особенность работы со статическими БД.

       Динамические базы данных - это БД, в которых факты могут модифицироваться во время выполнения программы или выбираться из файла. Для работы с такими БД в тексте программы в секции database должны быть декларированы предикаты для описания структуры динамической БД. Работа с такими БД будет описана ниже.

4. Явные и неявные базы данных. Правила логического вывода

       Рассмотренная выше база данных о местах работы служащих является явной БД, так как она составлена из фактов, аргументы которых константы. Работая даже с такой простой БД, у человека хватает интеллекта установить между имеющимися данными, и совсем иные отношения, кроме работы служащего в конкретном отделе.

       Так человеку хватает знаний на то, чтобы назвать двух служащих коллегами, если они работают в одном и том же отделе. Вместе с тем, работая с БД work(...) , для определения коллег Петрова пользователю системы необходимо:
· определить номер отдела (N), в котором работает Петров:
· найти всех сотрудников, работающих в отделе с номером N;
· исключить из полученного списка самого Петрова;
· сформировать все сочетания Петрова с лицами из полученного списка.

       Таким образом у пользователя появляется возможность свои представления о понятии коллега сформировать в виде составного запроса к явной БД и получить ответ на интересующий его вопрос. И такая ситуация будет повторяться при каждом использовании понятия коллега при формировании запросов, таких как "Являются ли Петров и Павлов коллегами?", "Кто коллега Петрова и Сидорова?" и т.д. Ясно, что такая процедура длительна, требует от пользователя системы должной квалификации по составлению составных запросов.

       Вместе с тем зги несложные познания по преобразованию отношений и своп представления о понятии коллега пользователь может передать" Пролог-программе, описав свои знания набором декларативных правил.

       Для этого можно ввести новое отношение КОЛЛЕГА (СЛУЖАЩИЙ1 , СЛУЖАЩИЙ2), определив его как пару разных служащих, работающих в одном и том же отделе. Новое отношение следует описать в секции predicates двуместным предикатом со структурой, аналогичной отношению КОЛЛЕГА(...).

       Аргументы предиката должны принимать значения из области символьных данных. А сам предикат в секции clauses определяется на основании логического правила вывода:

Любые два служащих Служащий1 и Служащий2 являются коллегами
ЕСЛИ
существует такой отдел N_отд , что работает Служащий1 в отделе N_omд
И
работает Служащий2 в отделе N_omд
И
служащие Служащий1 и Служащий2 различны.

Выполнив все необходимые действия по модификации исходной программы, мы получим программу, которая содержит не только факты, но и знания, в виде правил манипулирования этими фактами. Это позволяет к правилам применять все возможные типы запросов, что и к фактам.

Если нас интересуют все коллеги служащего Петрова, то запрос надо задать в виде:
Goal: colleague ("Петров", Who),
а если интересуют общие коллеги и Петрова и Иванова, то запрос будет иметь вид:
Goal: colleague ("Петров",Х), colleague ("Иванов",Х)
и система найдет только один ответ о служащем по фамилии Сидоров, так как именно он работает в одном отделе с Петровым и Ивановым.
/* Программа 5 */
domains
name = string
office = integer
predicates
work( name , office )
clauses
colleague(Manl,Man2) :- work(Man1,X)
work(Man2,X),
Маn1<>Маn2.
work( "Петров" , 101 ).
work( "Павлов" , 211 ).
work( "Сидоров" , 101 ).
work( "Иванов" , 101 ).
       Из изложенного следует, что если БД work(...) - это явная база данных, так как составлена из фактов, аргументы которых константы, то база colleague(...) - это неявная база данных, поскольку правило для ее формирования определено с использованием переменных, значения которых зависят от подцелей этого правила. С точки зрения пользователя, формирующего запрос, не имеет значения, является база явной или неявной.

5. Использование структур в качестве доменов отношений

       Турбо-Пролог позволяет создавать объекты, компонентами которых являются другие объекты. Причем сложные объекты рассматриваются и обрабатываются так же, как и простые. Это сильно упрощает составление программ и организацию баз данных.

       В предыдущем разделе мы сформировали неясную базу данных о коллегах па основе наших представлений о понятии коллега. При этом, формулируя правила для представления этого понятия, мы ограничились только представлением о коллегах, как о людях, которых объединяет совместный труд, т.е. как о сослуживцах.

       Более точно определить понятие коллеги можно, как пару лиц, объединенных единой целью, интересом, предметом деятельности и т.д. При такой формулировке понятия коллеги мы можем для его реализации сформировать отношение
ОБЬЕДИНЯЕТ ( ЛИЦ01 , ЛИЦ02 , ПРЕДМЕТ )
или в синтаксисе языка Турбо-Пролога
unite( name , name, object)
       И тогда мы могли бы, например, называть людей коллегами, если:
- объединяет Тома и Билла работа
- объединяет Сидорова и Петрова общее хобби, которым является спорт
- объединяет Петрова и Тома проект по новым системам для IBM
- объединяет Козлова и Сидорова совместная трудовая деятельность
       У нас не возникнет никаких сложностей при представлении первого предложения в виде факта на Прологе, который будет иметь вид
unite( tom , bill, labour )
Но если второе предложение записать в аналогичной форме, т.е.
unite( '"Сидоров" , "Петров", sport ) ,
то оно не будет соответствовать действительности, так как из него совсем не следует, что спорт является общим увлечением двух лиц, т.е. является их хобби. Более того оно ложно, так как из него можно заключить, что Петров и Сидоров профессиональные спортсмены, объединенные общими спортивными делами. Не верным будет и наше решение в качестве третьего аргумента указать
unite( ''Сидоров" , "Петров", "hobby sport" ) ,
так как hobby является некоторым свойством объекта совместной деятельности, а sport является конкретным значением этого свойства. Т.е. hobby - это атрибут объекта object, а sport - конкретный экземпляр этого атрибута. При таком подходе единственный вариант записи второго предложения будет
unite( "Сидоров" , "Петров", hobby(sport) ) ,
где hobby(sport) - это составной терм или структура Турбо-Пролога. Тогда по аналогии можно записать пролог-факты для второго и третьего предложений
unite( "Петров", tom , project("New system",ibm) ) ,
unite( "Козлов","Сидоров" , labour ) ,
       Таким образом можно сделать вывод о том, что во введенном для определения понятия коллеги отношении unite первые два домена являются простыми объектами, а третий - это сложный объект, атрибуты которого сами являются объектами.

       Описание данного отношения на Прологе в виде предиката и определение областей изменения его аргументов будет иметь вид:
domains
name.firm = symbol
object = labour ; hobby(name) ; project(name,firm)
predicates
unite( name , name, object )
где символ ";" (точка с запятой) эквивалентен логической операции "ИЛИ" и в данном описании использован для того, чтобы показать, что домен object может иметь одну из возможных структур, описанных для него в области domains.

       Задание 1.
  1. Откорректируйте программу 5, включив в нее описание предиката unite и определив его для четырех фраз, приведенных в данном разделе.
  2. Сформируйте запросы, соответствующие вопросам:
         - "Кого объединяет совместный труд ?",
         - "Есть ли пара любителей шахмат ?",
         - "Кто является коллегой Тома ?"
         - "Для кого и с кем Петров выполняет проект ?"
         - "Кто является коллегами Тома ?" ( если есть сложности, то вспомните о логической операции дизъюнкции и ее использовании в Прологе).
  3. Сформулируйте самостоятельно еще три составных запроса к базе и введите в программу.
  4. Все вопросы, соответствующие им запросы и результаты вывода представить в отчете по лабораторной работе.

6. Процедуры как элемент представления знаний

       Смысл предложений Пролог-программ может быть понят либо с позиций декларативного подхода, либо с позиций процедурного подхода. Декларативный смысл подчеркивает статическое существование отношений. Порядок следования подцелей в правиле не влияет на декларативный смысл этого правила.

       При процедурной трактовке программы подчеркивается последовательность шагов, которые выполняются при обработке запроса. В этом случае, приобретает значение порядок следования подцелей в правиле.

       Множество предложений, имеющих одно и то же имя предиката с одинаковым количеством аргументов, называют процедурой. Когда обрабатывается запрос к процедуре, то он анализирует фразы, образующие процедуру, в том порядке, как они в ней представлены. Считается, что между правилами процедуры неявно присутствует соединитель '"или".

       В предыдущих разделах мы сформировали два подхода к представлению наших знаний о понятии коллега. С одной стороны коллегами являются сослуживцы, т.е. любая пара лиц, которые работают вместе, с другой - любая пара лиц, которая объединена объектом общей деятельности. Мы подошли к тому, чтобы два наши знания о понятии коллега объединить в одно.

       Представьте себе, что одну из формулировок какого-либо понятия (в нашем случае это коллега) мы получили от одного эксперта, имеющего свои знания этой проблемы, а вторую - от эксперта, имеющего иные знания этой же проблемы. Объединяя в Пролог-программе два знания одной и той же проблемы, мы получим систему, которая задает больше каждого отдельного эксперта.

       Понятие коллеги, удовлетворяющее обеим точкам зрения, может быть описано отношением вида:
ПОЛНЫЙ_КОЛЛЕГА (ЛИЦ01 , ЛИЦ02 , ПРЕДМЕТ ОБЩЕЙ_ДЕЯTEJIЬHOCTИ),

которое на Прологе будет описано предикатом all_colleague, структура которого будет полностью аналогична структуре предиката unite, а определить его можно в виде процедуры, содержащей три декларации предиката all_colleague.
predicates
all_colleague( name , name, object ) clauses
all_colleague(X,Y,Z) :- colleague(X,Y), Z=labour.
all_colleague(X,Y,Z) :- unite(X,Y,Z).
all_colleague(X,Y.Z) :- unite(Y,X,Z).
С декларативной точки зрения это описание процедуры полный_коллега можно прочитать так.

Для любых двух лиц X и Y и любой общей деятельности Z

X и Y являются коллегами по общей деятельности Z
ЕСЛИ
X и Y являются сослуживцами
И
общая их деятельность Z - это труд
ИЛИ
X объединяет с Y общая деятельность Z
ИЛИ
Y объединяет с X общая деятельность Z

Последнее правило устраняет асимметрию отношения unite no отношению к лицам, объединенным общей деятельностью. Действительно, если Козлов является коллегой Сидорова по работе, то, очевидно, что и Сидоров является кометой Козлова по работе.

       Задание 2.
  1. Измените программу, добавив в нее описание предиката all_colleague и процедуру для его определения.
  2. Определите состав явных и неявных баз, используемых в данной программе и опишите их структуру.
  3. Введите запрос "Кто является коллегой Тома?". Третье правило процедуры заключите в /*...*/ и повторите запрос. Объясните, почему разные ответы.
  4. В чем заключается разница в выполнении запросов unite("Петров",Who,X) и all_colleague("Петров",Who,Х). Введите еще ряд произвольных запросов.
  5. Определите, кто является коллегой Козлова и кто - коллега Сидорова.
  6. Все вопросы, запросы и результаты вывода привести в отчете по работе.

7. Целостность и непротиворечивость баз данных и знаний

       С этими двумя сложными понятиями, одними из основных при построении баз данных и знаний, мы постоянно будем оперировать дальше. Здесь же остановимся лишь на одном небольшом примере, иллюстрирующем их важность.

       При выполнении п.5 задания 2 мы определили, что у Козлова только один коллега - Сидоров, связанный с ним совместным трудом. Вместе с тем у Сидорова кроме Козлова есть еще два коллеги, которые связаны с ним совместным трудом.

       Но из этих двух посылок и наших представлений о понятии коллеги любому человек ясно, что Козлов работает в том же отделе, что и Сидоров. А если это так, то и имеет он более одного коллеги, в отличие от ответа системы. Т.е. у нашей системы не хватает интеллекта на такой вывод.

       А на запрос work("Козлов",office) система вообще даст отрицательный ответ. Налицо противоречивость данных. Частично исправить ситуацию можно, если доопределить предикат work в виде
work(Man1,N) :- unite(Man1,Man2,labour), work(Man2,N).
Тогда на запрос о номере отдела у Козлова и его коллегах система будет давать более точные ответы. Но ведь в базе work() отсутствуют данные о Козлове в виде фактов, т.е. в явном виде. Стало быть после нашего доопределения эта база стала не совсем явной, так как часть данных хранится в явном виде, а часть выводима из других на основе правил. В первом приближении - это уже прообраз базы знаний. Текст программы 5 со всеми добавлениями, введенными по ходу работы, имеет вид:
/* программа 6 */
domains
name,firm = symbol
office = integer
object = labour;hobby(name);project(name,firm)
predicates
work( name , office )
colleague( name , name )
unite( name , name ,object )
all_colleague( name , name , object )
clauses
colleague(Man1,Man2) :- work(Man1,X), work( Man2,Y), Man1<>Man2.
all_colleague(X,Y,Z):- colleague(X,Y), Z=labour.
all_colleague(X,Y,Z) :- unit(X,Y,Z).
all_colleague(X,Y,Z) :- unit(Y,X,Z).

unite(tom,bill,labour).
unite("Сидоров","Петров",hobby(sport)).
unite("Петров",tom, project("New system",ibm)
unite("Козлов","Сидоров",labour)

work( "Петров" , 101 ).
work( "Павлов" , 211 ).
work( "Сидоров" , 101 ).
work( "Иванов" , 101 ).
work(Man1,N) :- unite(Man1,Man2,labour),
work( Man2,N).

8. Содержание отчета по лабораторной работе

       Отчет по лабораторной работе должен содержать:
  1. Текст программы с набором фактов, который применяется при запросах.
  2. Запросы, сформированные самостоятельно при изучении п.2 и п.3 данной лабораторной работы, а также результаты их выполнения.
  3. Результаты выполнения задания 1 и 2 данной лабораторной работы.
  4. Результаты выполнения индивидуального задания, выданного преподавателем.