В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 61
Текст из файла (страница 61)
задаче из рассматриваемой области (например, указанием конкретного человека)
служит аргументом для универсального алгоритма, выдающего решение этой
конкретной задачи (например, список племянников указанного человека).
Основное достижение в том, что переход к новой задаче (который при
традиционном подходе потребовал бы создания новой программы), например, к
задаче о списке всех родных теток заданного человека, не потребует никакого
программирования! Достаточно правильно сформулировать задачу в (т.е.
правильно представить в реляционном стиле знания о ее исходных данных и
ожидаемых результатах).
Конечно, чтобы она оказалась практичной, нужно выполнить целый ряд
требований. К ним мы еще вернемся, а сейчас пора рассмотреть пример
программирования в реляционном стиле.
16.3. Пример
Представим реляционные знания о родственных отношениях. Другими
словами, опишем "мир" родственных отношений. Содержательно это будет,
конечно, очень упрощенная модель реального мира человеческих отношений.
16.3.1. База данных
ф1) (мужчина, Иван) -- Иван - мужчина
ф2) (мужчина, Степан)
ф3) (мужчина, Николай)
ф4) (мужчина, Кузьма)
ф5) (женщина, Марья) -- Дарья - женщина
ф6) (женщина, Дарья)
ф7) (родитель, Степан, Николай) -- Степан - родитель Николая
ф8) (родитель, Дарья, Кузьма) -- Дарья - родитель Кузьмы
ф9) (родитель, Иван, Дарья)
ф10) (родитель, Иван, Степан)
Итак, мы пользуемся простейшим языком представления реляционных знаний.
Представлено три конечных отношения - "мужчина", "женщина" и "родитель". Два
первых - одноместные (унарные), третье - двухместное (бинарное). Отношение
представлено конечным множеством кортежей, каждый из которых предсталяет
элемент отношения - элементарный факт, касающийся некоторых имен-атомов. При
этом имя отношения всегда занимает первую позицию в кортеже. Позиция атома в
кортеже, конечно, существенна.
Например, (родитель, Дарья, Кузьма) и (родитель, Кузьма, Дарья)
представляют разные факты.
Совокупность отношений называется реляционной базой данных (БД).
16.3.2. База знаний
Вместе с тем содержательный смысл отношений пока никак нами не
представлен. Его можно проявить только за счет указания связей между
отношениями. Представим некоторые из таких связей так называемыми
предложениями. Содержательно предложения служат правилами вывода,
позволяющими строить одни отношения из других.
Определим правила вывода отношений "брат", "сестра", "общий_родитель",
"дядя" и "тетя".
п1) (брат, X, Y) (мужчина, X) (общие_родители, X, Y)
п2) (сестра, X, Y) (женщина, X) (общие_родители, X, Y)
п3) (общий_родитель,X,Y) (родитель,Z,X) (родитель,Z,Y)
п4) (дядя, X, Y) (мужчина, X) (родитель, Z,Y) (брат, X, Z)
п5) (тетя, X, Y) (женщина, X) (родитель, Z,Y) (сестра, X, Z)
Формально предложение - это кортеж кортежей, в которых допускаются не
только атомы, но и переменные. Переменные будем обозначать большими
латинскими буквами. Совокупность предложений называется базой знаний (БЗ)
(иногда этим термином называется совокупность предложений вместе с БД; во
всяком случае именно наличие правил вывода отличает базу знаний от базы
данных).
Нетрудно догадаться, что предложения позволяют выводить новые факты
новых отношений из фактов, уже содержащихся в БД. Например, можно вывести
факты
(общие_родители, Степан, Дарья)
(общие_родители, Дарья, Степан)
(брат, Степан, Дарья)
16.3.3. Пополнение базы данных (вывод фактов)
Точный смысл правил вывода (семантику реляционного языка) можно
об'яснять по-разному. Начнем с метода, никак не учитывающего конкретную
задачу, которую предполагается решать. Назовем его "разверткой" БД.
Сформулируем сначала суть развертки, а потом продемонстрируем ее на примере
нашей БЗ.
Суть развертки. Первый кортеж каждого правила интерпретируется как
"следствие" из "условий", представенных остальными кортежами этого правила.
Наглядно это можно выразить формулой
T <== B1&...Bn
где T - первый кортеж (следствие, теорема), а Bi - условия (посылки,
аксиомы, факты).
Цель развертки: постороить БД, содержащую все факты, выводимые из
фактов исходного состояния БД посредством правил вывода из БЗ.
Полная развертка состоит из последовательности циклов, в каждом из
которых каждое предложение поочередно применяется к текущему состоянию БД.
Вначале текущим состоянием считается исходное состояние БД.
Очередное применение предложения состоит из последовательности всех
разверток, выполнямых этим предложением при определенной подстановке атомов
вместо переменных (поскольку число переменных и атомов конечно, то и число
таких разверток конечно; вместо каждой переменной подсталяется один и тот же
атом).
Развертка состоит в том, что если все кортежи-условия содержатся в
соответствующих отношениях текущего состояния БД, то кортеж-следствие (после
замены в нем переменных атомами) пополняет соответствующее отношение (если
его еще там нет).
Развертка завершается, когда очередной цикл не добавляет ни одного
нового кортежа ни в одно отношение.
Заметим, что развертка завершается при любой исходной БД. (Почему?)
Рассмотрим пример.
Первая развертка правил (п1) и (п2) пуста (так как отношение "общие
родители" пусто). Первая развертка правила (п3) при Z = Иван пополняет
отношение "общие_родители" кортежами
(общие_родители, Степан, Дарья) и
(общие_родители, Дарья, Степан).
Первая развертка правил (п4) и (п5) также пуста (так как отношение
"брат" и "сестра" пока по-прежнему пусты).
Во втором цикле "общие_родители" уже не пусто и развертка правила (п1)
добавляет кортеж
(брат, Степан, Дарья),
а правило (п2) добавляет кортеж
(сестра, Дарья, Степан).
В этом же цикле развертка правил (п4) и (п5) добавляет кортежи
(дядя, Степан, Кузьма)
(тетя, Дарья, Николай).
Так как третий цикл ничего нового не добавляет, развертка завершается.
Теперь все готово для решения кокретных задач из предметной области,
знание о которой представлено.
16.3.4. Решение задач
Конкретная задача формулируется в виде кортежа (обычно с переменными),
выделяемым знаком вопроса. Например
?(дядя, Q, Кузьма).
Вопрос рассматривается в качестве образца, для которого требуется
подобрать кортежи из отношений БД, получаемые из образца подходящей заменой
переменных. Решением задачи считается перечень всех таких кортежей.
Например, решение нашей задачи имеет вид
(дядя, Степан, Кузьма).
Содержательный смысл решения очевиден (спрашивается, кто дядя Кузьмы;
ответ: Степан). Понятно, что несложно выдавать ответ и в виде, например
Q = Степан.
Нетрудно понять, что таким образом можно решить любую задачу из "мира
родственных отношений" Ивана, Степана, Николая, Кузьмы, Марьи и Дарьи.
Например:
?(тетя, R, Николай) R = Дарья
?(Q, Степан, Дарья) Q = общие_родители Q = брат
Итак, показано, как можно представить реляционные знания для целого
класса задач таким образом, что решение конкретной задачи не требует
никакого программирования. Человек описывает мир на языке представления
знаний, затем человек ставит задачу на языке запросов, а компьютер дает
решение задачи, пользуясь универсальным решающим алгоритмом (в нашем случае
это алгоритм развертки). Отличие от обычной реляционной БД - в языке
представления знаний.
16.3.5. Управление посредством целей
Если основное назначение предыдущих параграфов - объяснить семантику
реляционного языка, то теперь пришло время подумать о его эффективности.
Бросается в глаза, что развертка слишком расточительна с точки зрения
потребностей конкретных задач. Для ответа на запрос о дяде Кузьмы совершенно
не требуются отношения "сестра" и "тетя", которые тем не менее и -
вычмсляются, и хранятся в БД. Другими словами, развертка готовит ответы
сразу на все случаи жмзни, чего нельзя себе позволить в реальных условиях.
Суть управления посредством целей. Поищем иной принцип мспользования
исходной БЗ с тем, чтобы по возможности делать лишь ту работу, которая
необходима для решения конкретных задач.
Ясно, что лишняя работа делается из-за того, что развертка никак не
использует постановку задачи (и даже ничего не "знает" о ней). Ключевая идея
нового принципа использования БЗ в том и состоит, чтобы при попытке ответить
на запрос анализировать те и только те правила из БЗ, которые могут
оказаться полезными именно для этого запроса. Это "новый" принцип нам в
сущности уже хорошо знаком - это принцип пошаговой детализации "сверху-вниз"
- от исходной задачи к подзадачам (от исходной цели к подцелям). Главное при
управлении посредством целей - суметь выбирать такие подцели, которые
действительно способствуют достижению цели верхнего уровня и вовремя
прекращать заниматься подцелями, которые оказались бесперспективными (с
точки зрения цели верхнего уровня).
Уточнения и примеры. Постановка задачи считается первой текущей целью-
запросом. Затем БД и БЗ совместно используются для ответа на запрос. При
этом последовательно анализируются следствия (первые кортежи) предложений БЗ
и факты БД - тривиальные следствия. Следствие считается сопоставимым с
запросом-целью, если существует такая согласующая подстановка (значений
вместо переменных запроса и следствия), в результате которой запрос
совпадает со следствием.
Например, следствие (дядя, X, Y) сопоставимо с запросом (дядя, Q,
Кузьма), так как они совпадают после согласующей подстановки
X -> Q, Y -> Кузьма.
Дерево целей. Если найденное сопоставимое следствие оказывается фактом
(т.е. не содержит переменных), то цель считается достигнутой. Если же
сопоставимое следствие начинает некоторое предложение, то условия из этого
предложения становятся подцелями. Говоря точнее, подцелями становятся не
сами условия, а результат применения к ним согласующей подстановки.
Например, из цели (дядя, Q, Кузьма) образуются связанные подцели
(мужчина, Q) (родитель, Z, Кузьма) (брат, Q, Z)
Обратите внимание на замену переменных в подцелях по справнению с
исходными условиями. Связанность этих подцелей проявляется в том, что цель
верхнего уровня может быть достигнутой только при условии, что ее
непосредственные подцели достигаются совместно, при одной и той же
согласующей подстановке.
Например, для цели (мужчина, Q) сопоставимым следствием оказывается
факт (мужчина, Иван) при согласующей подстановке
Q -> Иван.
А для цели (родитель, Z, Кузьма) сопоставимым следствием факт (родитель,
Дарья, Кузьма) при согласующей подстановке
Z -> Дарья.
Тогда для достижения исходной цели и третья подцель должна быть
достижима при подстановке
Q -> Иван, Z -> Дарья.
Однако нетрудно убедиться, что подцель (брат, Иван, Дарья) не может быть
достигнута. Действительно, из (п1) возникает новая совокупность подцелей
(мужчина, Иван) (общие_родители, Иван, Дарья),
а затем из (п3)
(родитель, Z, Иван) (родитель, Z, Дарья).
Однако ни для какого Z в БД нет факта, сопоставимого с первой из этих
подцелей.
Итак, принципиально важный момент - что делать, когда для некоторой
подцели найти согласующую подстановку не удается. Назовем такую ситуацию
тупиком.
Тупики и перебор с возвратом. Конечно, такую подцель следует признать
недостижимой, так как для нее проанализированы все потенциально сопоставимые
следствия. Однако не исключено, что цель верхнего уровня все-таки достижима.
Ведь недостижимость конкретной ее подцели могла быть вызвана либо неудачным
выбором подстановок в связанных подцелях или неудачным выбором подстановки
при переходе от цели верхнего уровня к подцелям.
Например, для цели (мужчина, Q) другие сопоставимые следствия-факты -
(мужчина, Степан), (мужчина, Николай) и (мужчина, Кузьма). Причем каждому из
них соответствует своя согласующая подстановка.
Проблема тупиков в дереве подцелей решается классическим методом - так
называемым перебором с возвратом (backtracking) потенциальных сопоставимых
следствий и согласующих подстановок. Для его реализации нужно организовать
так называемый стек возвратов, где и запоминать место сопоставимого
следствия вместе с соответствующей согласующей подстановкой с тем, чтобы
иметь возможность продолжить помск согласующей подстановки, когда возникает
тупик.
Например, в нашем случае придется вернуться к подцели (мужчина, Q) и
выбрать другое следствие-факт (мужчина, Степан) при новой согласующей
подстановке
Q -> Степан.
Тогда при той же подстановке
Z -> Дарья
в качестве третьей подцели получим
(брат, Степан, Дарья),
что выводимо посредством (п1) с учетом (ф2), (п3), (ф9) и (ф10).
Итак, исходная цель будет достигнута при Q = Степан и тем самым
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
