Динамическая база данных – это база данных, в которую время от времени требуется вносить изменения, отражающие изменения структуры описываемой системы. Один из методов реализации динамической базы данных заключается в деструктивном редактировании базы данных при необходимости внесения в нее изменений. К сожалению, при деструктивном редактировании исчезает возможность возврата к состоянию базы данных, существовавшему ранее. Это затрудняет анализ изменений базы данных.
Аксиома фреймов является альтернативной концепцией реализацией динамической базы данных. Если необходимо внести изменение, то исходная база данных остается неизменной, а записывается собственно изменение. Текущая форма базы данных получается при использовании ее исходной формы с учетом сделанных изменений. Ниже формулируется аксиома фреймов, в которой U обозначает любое отношение, а состояние S+1 является результатом выполнения действия А в состоянии S.
Аксиома фреймов. Отношение U будет соблюдаться в состоянии S + 1, являющемся результатом выполнения действия А в состоянии S, если U соблюдается в состоянии S, а А не влияет на U.
Иными словами, состояние базы данных унаследует каждую фразу предыдущего состояния, если только эти фразы не были явно изменены при переходе в данное состояние.
В соответствии с аксиомой фреймов для представления динамической базы данных можно воспользоваться механизмом наследования. Начальное состояние базы данных соответствует самому верхнему узлу дерева состояний. Каждое новое состояние базы данных вводится как состояние-потомок предыдущего состояния.
После введения нового состояния базы данных, как потомка существующего состояния, каждая фраза, связанная с существующим состоянием, либо будет унаследована состоянием-потомком (т.е. не изменится), либо будет перекрыта новым значением (т.е. изменится), либо будет опровергнута (т.е. удалена). Помимо этого, в новое состояние могут быть введены новые фразы.
Мир кубиков. Мир кубиков - это пример, часто используемый для того, чтобы проиллюстрировать аксиому фреймов. Для точного описания мира кубиков требуется динамическая база данных, в которой задаются положения кубиков на крышке стола. Метод, употребляемый для представления мира кубиков, можно с успехом применить и в других задачах, где требуется динамическая база данных.
Описываемая версия мира кубиков основывается на базе данных, состоящей из фактов "на/3", при помощи которых задается положение кубиков. Факт «на(5, А, В)» означает, что в состоянии S кубик А находится на верхней части кубика В. Процедура "поместить" позволяет пользователю перемещать кубики, входящие в мир, на другие места, что соответствует переходам к новым состояниям базы данных "на". Начальное состояние базы данных "на" носит название "1", следующее состояние - "2" и т.д.
Характеристики отношения "на". Отношение "на" - это отношение либо между двумя кубиками в некотором состоянии, либо между кубиком и столом. Согласно определению данное отношение несимметрично, нерефлексивно и нетранзитивно. Все кубики имеют одинаковый размер, отношение "на" между двумя кубиками регулируется ограничением вида один-к-одному, обеспечивающим целостность. Иными словами, если кубик А уже находится на кубике В, то на кубике В не может быть никаких других кубиков. На столе может поместиться более одного кубика.
Главной функцией процедуры "поместить" является сбор данных - она собирает у пользователя сведения о необходимых изменениях базы данных. Для защиты базы данных "на" от некорректных изменений в процедуре "поместить" применяются ограничения, обеспечивающие целостность базы данных. К примеру, если кубик А уже находится на кубике В, а пользователь попытается поставить на В кубик С, то процедура "поместить" откажется выполнить предписываемое перемещение и выдаст пользователю предупреждающее сообщение. Тем самым процедура "поместить" следит за тем, чтобы в точке, где пользователь пытается вносить изменения в базу данных, отношение "на" между двумя кубиками имело вид один-к-одному. Процедура "поместить" накладывает и другие ограничения, обеспечивающие целостность, такие как недопущение употребления кубика, отсутствующего в текущем состоянии.
Первоначально база данных, описывающая мир кубиков, состоит из следующих фактов:
на(1, а, стол).
на (1, б, стол).
на(1, в, а).
на(1, г,в).
текущее_состояние (1).
Факт "текущее_состояние" содержит наименование самого последнего состояния базы данных.
Картина состояния. Экранно-ориентированная процедура "отобразить_состояние" строит на экране дисплея изображение кубиков для заданного состояния базы данных. Начальное состояние выглядит так:
?- отобразить_состояние (1).
Г
В
А Б
С Т О Л
Внесение изменений в базу данных при помощи процедуры "поместить". Процедура "поместить" вносит изменение в базу данных, генерируя состояние-потомок текущего состояния. Она добавляет новые данные в состояние-потомок, а затем деструктивно изменяет значение факта "текущее-состояние", превращая его в обозначение потомка. Первым аргументом процедуры "поместить" является обозначение кубика, который нужно передвинуть, а вторым аргументом служит место, куда нужно поставить этот кубик.
Например, если текущее состояние - это "1", то запрос
?- поместить (г, стол). % запрос (1)
вызовет добавление в программу следующих фраз:
текущее-состояние (2).
на (2, г, стол).
опровергнуть (2, на (_,г,в)).
Кроме того, из программы будет удалена фраза «текущее_состояние (1)».
Выяснение того, где находятся кубики. Нижеследующий запрос покажет, где находятся кубики в состоянии "2" базы данных:
?- послать (2, на (_X, Y)).
Х=г
У=стол; %по состоянию «2»
Х=а
У=стол; %по состоянию «1»
Х=б
У=стол; %по состоянию «1»
Х=в
У=стол; %по состоянию «1»
нет
Эта информация будет лучше восприниматься, если ее представить в графическом виде:
?- отобразить_состояние (2).
В
Г А Б
С Т О Л
Посмотрим, как будет выглядеть база данных после внесения еще нескольких изменений.
?- поместить (а, б). % запрос (2)
да
?-поместить (в, г). % запрос (3)
да
? - текущее_состояние (X).
Х=4
? – отобразить_состояние (4).
В А
Г Б
С Т О Л
Реализация процедуры "поместить".
% запретить использование неизвестного кубика:
поместить (Кубик. Куда_поставить) : -
% проверить, отсутствуют ли
% Кубик и Куда_поставить:
( not (на(...; Кубик, _))
;
Куда_поставить \== стол,
not (на(...; Куда_поставить, _))
),
write(‘неверное обращение к кубику’), nl, !.
% запретить изменение, если переменная Куда_поставить обозначает
% кубик, на котором уже стоит другой кубик:
поместить (Кубик. Куда_поставить) : -
Куда_поставить \== стол,
Текущее_состояние(Состояние),
послать(Состояние, на(Занят, Куда_поставить)),
write(Занят),
write(‘ уже находится на ’)
write(Куда_поставить), nl,!.
% здесь база данных изменяется:
поместить (Кубик, Куда_поставить) :-
текущее_состояние (Состояние), %1
НовоеСостояние is Состояние + 1, %2
assert (порождение (НовоеСостояние, Состояние)), %3
%
послать (Состояние, на (Кубик, Под_кубиком)), %4
assert (опровергнуть (НовоеСостояние,
на(_, Кубик, Под_кубиком))), %5
assert (на (НовоеСостояние, Кубик, Куда_поставить)), %6
retract (текущее_состояние (Состояние)), %7
assert (текущее_состояние (НовоеСостояние)), !. %8
Ограничения, обеспечивающие целостность, которые накладываются во время сбора данных. Первое правило "поместить" отвергает кубики, которые отсутствуют в мире. Второе правило не разрешает пользователю ставить кубик на другой кубик, место над которым уже занято. Если два первых правила потерпят неудачу, то это будет означать, что ограничения, обеспечивающие целостность базы данных, не будут нарушены при предлагаемом ее изменении. Собственно изменение осуществляется третьим правилом "поместить" Подцели (2) и (3) этого правила устанавливают новое состояние базы данных "порождение". Подцель (4) выясняет текущее местоположение кубика "Кубик", а подцель (5) опровергает это местоположение. Подцель (6) добавляет к новому состоянию новое местоположение кубика "Кубик". В заключение подцели (7) и (8) деструктивно изменяют значение факта "текущее_состояние".
Перемещение колонки кубиков. В рассматриваемой версии программы "поместить" разрешается передвигать за один раз целую колонку кубиков. Иными словами, не запрещается перемещать кубик, если на нем стоит еще один кубик. Это именно то что будет сделано в ответ на приведенный выше запрос (2): «поместить (а, б)». Все кубики, стоящие над перемещаемым, наследуют новое положение этого кубика. Можно было бы добавить еще одно правило, которое реализовывало бы ограничение, обеспечивающее целостность, гарантируя то. что за один раз будет перемещаться только один кубик.
Оценка механизма наследования. Механизм наследования - это практическое воплощение концепции наследования. Он пригоден для представления таких ситуаций, в которых имеется множество состояний знаний, иерархически взаимосвязанных друг с другом. Тем самым механизм наследования создает основу для перевода на Пролог знаний, выраженных при помощи формализма фреймов или объектно-ориентированного формализма. Уже существующую фразу Пролог-программы легко можно адаптировать к этому механизму, просто добавив в заголовок этой фразы дополнительный аргумент, содержащий имя состояния знаний. Примеры данного раздела показывают, что применение механизма наследования позволяет реализовать удобную дня восприятия аксиоматизацию системы, свободную от побочных эффектов управления.
Недостатком механизма наследования является то, что он работает неэффективно, если запросу к процедуре "послать" приходится анализировать длинные цепи состояний. В приведенной форме, механизм наследования позволяет порожденному состоянию иметь более одного родителя. В объектно-ориентированном формализме это называется множественным наследованием. Неэффективность процедуры "послать" возрастает, если состояние, к которому обращен запрос, имеет более одного родителя. |
Главная
Каталог файлов
