удовлетворяют все наборы значений переменных образца, которые удовлетворяют по крайней мере одному из (запроса) ... (запросап).

Кроме того, составные запросы можно порождать при помощи not. Например,

(and (начальник ?x (Битобор Бен))

(not (должность ?x (компьютеры программист))))

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

(not (запрос 1))

удовлетворяют все присваивания переменным образца, которые не удовлетворяют (запросу!).63

Последняя комбинирующая форма называется lisp-value. Когда она стоит в начале образца, она указывает, что следующий элемент является предикатом Лиспа, который требуется применить к остальным (конкретизированным) элементам как к аргументам. В общем случае, образец

(lisp-value (предикат) (ара ... (арап))

удовлетворяется теми присваиваниями переменным образца, для которых применение (предиката) к конкретизированным (арв]) ... (аргп) дает истину. Например, чтобы найти всех сотрудников с зарплатой выше 30000 долларов, мож-

64

но написать64

(and (зарплата ?person ?amount)

(lisp-value > ?amount 30000))

Упражнение 4.56.

Сформулируйте составные запросы для получения следующей информации:

a.имена всех сотрудников, у которых начальником Бен Битобор, и их адреса;

b.все сотрудники, чья зарплата ниже, чем у Бена Битобора, вместе с их зарплатой и зарплатой Бена;

c.все сотрудники, у которых начальник не относится к компьютерному отделу, вместе с именем и должностью их начальника.

Правила

В дополнение к элементарным и составным запросам, наш язык обладает средством абстракции запросов. Это правила (rules). Правило

(rule (живет-около ?person-1 ?person-2)

(and (адрес ?person-1 (?town . ?rest-1)) (адрес ?person-1 (?town . ?rest-2)) (not (same ?person-1 ?person-2))))

63Это описание not верно только для простых случаев. На самом деле поведение этой конструкции более сложное. Мы исследуем тонкости not в разделах 4.4.2 и 4.4.3.

64Lisp-value имеет смысл использовать только для тех операций, которых нет в языке запросов. В частности, с его помощью не следует проверять равенство (так как для этого предназначено сопоставление в языке запросов) и неравенство (так как это можно сделать посредством правила same, приведенного ниже).

говорит, что двое людей живут рядом друг с другом, если они живут в одном городе. Выражение not в конце необходимо для того, чтобы правило не говорило про всех людей, что они живут сами около себя. Отношение same (тот же самый) определяется очень простым правилом:65

(rule (same ?x ?x))

Следующее правило объявляет, что сотрудник является «шишкой», если он начальствует над кем-нибудь, кто сам является начальником:

(rule (шишка ?person)

(and (начальник ?middle-manager ?person) (начальник ?x ?middle-manager)))

В общем случае правило выглядит как

(rule (заключение) (тело))

где (заключение) - это образец, а (тело) - произвольный запрос.66 Можно считать, что правило представляет собой большое (даже бесконечное) множество утверждений, а именно, все конкретизации заключения при помощи присваиваний переменным, удовлетворяющих телу правила. Когда мы описывали простые запросы (образцы), мы сказали, что присваивание переменным удовлетворяет образцу в том случае, когда конкретизированный образец имеется в базе данных. Однако образец не обязательно должен явно присутствовать в базе данных как утверждение. Это может быть неявное утверждение, следующее из правила. Например, запрос

(живет-около ?x (Битобор Бен))

выдает

(живет-около (Дум Хьюго) (Битобор Бен)) (живет-около (Фиден Кон) (Битобор Бен))

Чтобы найти всех программистов, живущих около Бена Битобора, можно спросить

(and (должность ?x (компьютеры программист)) (живет-около ?x (Битобор Бен)))

Как и в случае с составными процедурами, правила можно использовать внутри других правил (как мы видели в живет-около), и они даже могут быть рекурсивными. Например, правило

65Заметим, что правило same не нужно для того, чтобы сделать два объекта одинаковыми: достаточно просто использовать одну и ту же переменную образца - тогда у нас с самого начала будет иметься только один объект, а не два. Например, обратите внимание на ?town в правиле живет-около или ?middle-manager в правиле шишка ниже. Same оказывается полезным, когда нам хочется, чтобы два объекта различались, как ?person-1 и ?person-2 в правиле живет-около. При том, что использование одной переменной в двух местах в запросе требует, чтобы в обоих местах присутствовало одно значение, использование разных переменных не означает, что значения различаются. (Значения, присваиваемые различным переменным образца, могут быть как разными, так и одинаковыми.)

66Кроме того, мы разрешаем иметь правила без тела, вроде same, и будем полагать, что такое правило означает, что заключение удовлетворяется любыми значениями переменных.

(rule (одчиняется ?staff-person ?boss)

(or (начальник ?staff-prerson ?boss)

(and (начальник ?staff-person ?middle-manager) (подчиняется ?middle-manager ?boss))))

говорит, что служащий подчиняется руководителю, если руководитель командует им непосредственно или (рекурсивно) непосредственный начальник служащего подчиняется руководителю.

Упражнение 4.57.

Определите правило, которое говорит, что служащий 1 может заменить служащего 2, если либо служащий 1 имеет ту же должность, что и служащий 2, либо человек с должностью служащего 1 может выполнять работу служащего 2, и при этом служащие 1 и 2 - разные люди. Используя это правило, составьте запросы, которые находят следующую информацию:

a.все служащие, которые могут заменить П.Э. Фекта.

b.все служащие, которые могут заменить кого-то, кто получает больше их самих, с указанием двух зарплат.

Упражнение 4.58.

Определите правило, которое говорит, что человек «независим» в своем отделе, если он работает в этом отделе, но у него нет начальника, который работает в том же отделе.

Упражнение 4.59.

Бен Битобор пропускает слишком много совещаний. Опасаясь потерять из-за этой глупой привычки работу, он решает, что с ней надо что-то делать. Он добавляет данные обо всех еженедельных совещаниях в базу данных «Микрошафт» в виде следующих утверждений:

(совещание бухгалтерия (понедельник 9)) (совещание администрация (понедельник 10)) (совещание компьютеры (среда 15)) (совещание администрация (пятница 13))

Все эти утверждения сообщают о совещаниях отделов. Кроме того, Бен вводит утверждение о совещании всей компании, которое относится ко всем отделам. Все сотрудники компании должны ходить на это совещание.

(совещание вся-компания (среда 16))

a.В пятницу утром Бен хочет спросить у базы данных, какие совещания происходят в этот день. Как ему надо составить запрос?

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

(rule (время-совещания ?person ?day-and-time) (тело))

c.Лиза приходит на работу в среду и хочет узнать, на какие совещания ей нужно идти в этот день. Если имеется правило время-совещания, то какой запрос ей надо подать?