Однако на практике применение унификации и резолюции может в значительной степени снизить производительность системы. Поэтому желательно найти и использовать более эффективную стратегию. Несколько таких стратегий описано ниже.

Наивное оценивание

Наивное оценивание [23.25], судя по названию, является, вероятно, простейшим подходом. Его можно продемонстрировать (на основе рассматриваемого примера запроса) с помощью приведенного ниже псевдокода.

точки неизменности */

СОМР := PS ;

do until СОМР reaches а fixpoint ; /* Выполнять, пока СОМР не достигнет СОМР := СОМР UNION ( СОМР PS ) ; end ;

DISPLAY := СОМР WHERE РХ = Р# (Р1) ;

Каждая из переменных-отношений СОМР и DISPLAY (подобно переменной-отношению PS) имеет по два атрибута: РХ и PY. Попросту говоря, выполнение этого алгоритма с получением промежуточного результата, состоящего из объединения соединения отношения PS и предыдущего промежуточного результата, повторяется до тех пор, пока промежуточный результат не достигнет точки неизменности, т.е. пока не прекратится рост (изменение) промежуточного результата.

Замечание. Выражение СОМР PS является сокращенной формой записи выражения соединить СОМР и PS по атрибутам COMP.PY и PS.PX с выводом результатов по атрибутам СОМР.РХ и PS.PY . Для краткости здесь игнорируются операции переименования атрибута, соответствующие рассматриваемому диалекту данной алгебры (подробности приводятся в главе 6).

Теперь попробуем применить этот алгоритм к рассматриваемому набору данных. Ниже показаны результаты выполнения первой итерации цикла: слева приведены значения выражения СОМР й PS, а справа - значения величины СОМР (кортежи, добавленные в ходе этой итерации, отмечены звездочкой).

СОМР PS

Далее приведены результаты, полученные после второй итерации.

СОМР PS

Внимательно их просмотрев, можно заметить, что на второй итерации повторяется вычисление кортежей СОМР й PS, полученных во время первой итерации, а также вычисляется несколько дополнительных кортежей (в данном случае- два кортежа: (Р1, Р6) и(Р2, Р6)). Это делает методику наивного оценивания не очень привлекательной.

После третьей итерации и повторения всех необходимых вычислений извлекаемые значения выражения СОМР й PS остаются теми же, что и в предыдущей итерации. Таким образом, точка неизменности для СОМР достигается и выполнение цикла заверщается. Выполнив выборку СОМР по всем РХ, равным Р1, получим окончательный результат.

СОМР

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

В заключение следует отметить, что наивное оценивание можно рассматривать как применение метода прямого формирования цепочки. В самом деле, оно начинается с использования экстенсиональной базы данных (т.е. с действительных значений данных), а затем продолжается в виде повторного использования предпосылок определения (т.е. основы правила) вплоть до получения желаемого результата. Фактически этот алгоритм позволяет вычислить минимальную модель для профаммы на языке Datalog (см. разделы 23.5 и 23.6).

Полунаивное оценивание

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

оцениванием [23.28]. Иначе говоря, на каждом шаге итерации вычисляются только новые кортежи, которые добавляются к полученным ранее результатам. Эта идея вновь будет проиллюстрирована на примере запроса Найти все компоненты детали с номером Р1 . Ниже показана реализация соответствующей процедуры на псевдокоде.

NEW := PS ;

СОМР := NEW ;

do until NEW is empty ;

/* Выполнять, пока отношение NEW не окажется пустым */

NEW := ( NEW й PS ) MINUS СОМР ;

СОМР := СОМР UNION NEW ; end ;

DISPLAY := СОМР WHERE PX = P# (Pi) ;

Теперь стоит просмотреть, как выполняется этот алгоритм на примере использованных ранее данных. Перед выполнением цикла переменные-отношения NEW и СОМР идентичны переменной-отношению PS.

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

Данные в переменной-отношении СОМР такие же, как при использовании алгоритма наивного оценивания, а данные в переменной-отношении NEW содержат только те кортежи, которые были добавлены в СОМР на этой итерации. Обратите внимание, что данные в переменной-отношении NEW не содержат кортеж (Р1, РЗ) (сравните с данными, полученными при наивном оценивании).