10.6. Ситуационное исчисление в дедуктивной базе данных

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

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

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

10.6.1. Категории

Студенческая среда для нашего примера содержит три категории:

Переменная, принимающая значение из категории студентов, обозначается студент. Переменная, принимающая значение из категории курсов, обозначается курс, а из категории оценок — оценка.

10.6.2. Отношения

Отношения в студенческой среде задаются следующими предикатами:

записан (студент, курс, предикат истинен, если студент студент записан на курс курс, когда база находится в ситуации

экзаменован (студент, курс, оценка, предикат истинен, если студент студент экзаменован по курсу курс с оценкой оценка, когда база находится в ситуации

прослушан (студент, курсх, курс): предикат истинен, если прослушивание курса является обязательным для записи на курс курс студента студент. Заметим, что значение этого предиката не зависит от ситуации, в которой находится база данных.

10.6.3. Действия

Действия, которые могут осуществляться в студенческой среде, являются следующими:

Записать (студент, курс), записать студента студент на курс курс.

Поставить (студент, курс, оценка), поставить студенту студент оценку оценка за сдачу курса курс.

Отчислить (студент, курс): отчислить студента студент с курса курс.

10.6.4. Аксиомы начальной ситуации

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

(см. скан)

10.6.5. Аксиомы допустимых действий

Студент может быть записан на курс курс только в том случае, если он получил оценку не ниже 3 по курсу обязательному для записи на курс

(см. скан)

Студенту может быть поставлена новая оценка, если она отличается от старой:

Студент может быть отчислен с курса, если он перед этим был на него записан:

10.6.6. Аксиомы перехода в следующие ситуации

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

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

10.6.7. Запросы к ситуационной Дейталог-программе

Обратим внимание, что аксиомы начальной ситуации, представленные в языке ситуационного исчисления и, вообще, любого исчисления, не изменяются средствами того исчисления, которое используется. Их изменение осуществляется извне. Кем и с помощью каких средств это делается в настоящей книге, мы даже не интересуемся. Использование же действий необходимо нам только для того, чтобы можно было запрашивать у дедуктивной базы данных ответы на гипотетические вопросы типа: “Может ли случиться некоторая ситуация, в которой истинны определенные предикаты при определенных значениях их аргументов, если такие-то и такие-то действия и в такой-то последовательности были бы выполнены?” Примером запроса этого типа для нашего примера мог бы быть следующий: Если была выполнена последовательность действий Отчислить (Иванов, Математика),

Записать (Маринина, Математика), то в результате ее выполнения студент Иванов записан на какой-либо курс?” Для положительного ответа на этот гипотетический вопрос необходимо установить истинность формулы

хотя бы для одного значения переменной курс.

10.6.8. Ограничения целостности дедуктивной базы данных

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

Ограничением целостности ситуационной Дейталог-программы называются такие ее инвариантные свойства, которые должны всегда выполняться, в какой бы ситуации база не находилась или даже какие бы изменения экстенсионала не произошли. Ограничения целостности задаются в виде аксиом и проверяются всякий раз после изменения экстенсионала. Так, например, для рассмотренной студенческой базы данных могло бы быть введено следующее ограничение целостности: ни один студент не может иметь сразу две оценки по одному и тому же предмету. Если предположить, что ситуационная Дейталог-программа содержит информацию о стипендиях, получаемых студентами в течение срока обучения, с использованием предикатов типа стипендия (студент, размер стипендии, s), то ограничением целостности могло бы быть следующее: стипендия каждого студента не может уменьшаться в течение всего срока его учебы.

Если ввести действие Назначить (студент, размер стипендии), то ограничение целостности можно задать формулой

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

Потребуется также следующая аксиома единственности имен:

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