Введение в системы БД (542480), страница 243
Текст из файла (страница 243)
На самом деле можно переопределить это правило таким образом, чтобы рекурсия не была линейной. СОМЕ ( рх, ру ) «= РЯ ( рх, ру ) СОМР ( рх, ру ) ~ СОМР ( рх, рг ) йМО СОМР ( рг, ру ) Однако с практической точки зрения линейная рекурсия представляет гораздо больший интерес, потому что чаще встречается на практике и для ее применения разработано несколько известных и эффективных методов [23,16).
Поэтому далее речь пойдет исключительно о линейной рекурсии. Замечание. Для полноты изложения следует подчеркнуть, что понятие "рекурсивное правило" необходимо обобщить для решения более сложных случаев следующего типа. Р ( х, у ) «= О ( х, г ) ЕМО Е ( г, у ) О(х,у)«=Р(х,г!йМОЯ(яру) Для краткости изложения эти особенности будут опушены. Более подробную информацию о них можно найти в (23.16).
924 Часть )г. дополнительные аспекты Так же, как при обработке классических 1нерекурсивных) запросов, в целом, проблема реализации заданного рекурсивного запроса может быть разбита на две отдельные части, а именно: преобразование исходного запроса в эквивалентную, но более эффективную форму и собственно выполнение преобразованного таким образом запроса. В литературе содержатся описания различных подходов к решению этих проблем. Ниже кратко описаны некоторые простейшие из предложенных технологий. Они будут проиллюстрированы на примере запроса "Найти все компоненты детали с номером 'Р1'" с использованием приведенного ниже набора значений в переменной-отношении РЯ.
Унификация и резолюция Одним из возможных подходов, конечно, является использование стандартных для языка Рго(ой методов унификации н резолюции, описанных в разделе 23.4. В данном примере этот подход будет реализован следующим образом. Прежде всего следует указать первичные предпосылки, которые являются дедуктивными аксиомами и в коньюнктивной нормальной форме выглядят так, как показано ниже.
1. КОТ РЯ ( рх, ру ) ОИ СОМР ( рх, ру ) 2. МОТ РЯ ( рх, рг ) Ой МОТ СОМР ( рг, ру ) ОК СОМР ( рх, ру ) ЕШе одна предпосылка создана на основе искомого заключения. 3. НОТ СОМР ( 'Р1', ру ) ОК КЕЯШ,Т ( ру ) Основные аксиомы образуют оставшиеся предпосылки. Ниже приведен пример одной из таких аксиом. 4.
РЯ ( 'Р1', 'Р2' ) Подставив 'Р1' вместо рх и 'Р2' вместо ру в строке из п. 1 и совместив строки из пп. 1 и 4, получим следующий результат. 5. СОМР ( 'Р1', 'Р2' ) Теперь, подставив значение 'Р2' вместо ру в строке из п. 3 и совместив строки из пп. 3 и 5, получим окончательный результат. б. КЕЯШТ ( 'Р2' ) Таким образом, деталь с номером 'Р2' является компонентом детали с номером 'Р!'. Аналогично можно показать, что деталь с номером 'Р3' также является компонентом детали с номером 'Р1'.
Теперь, обладая дополнительными аксиомами СОМР('Р1', 'Р2') и СОМР('Р1', 'Р3'), можно рекурсивно выполнить поиск всех остальных компонентов. Эта задача предлагается читателю в качестве упражнения. 925 Глава 23. Логические системы управления базами данных Однако на практике применение унификации и резолюции может в значительной степени снизить производительность системы. Поэтому желательно найти и использовать более эффективную стратегию. Несколько таких стратегий описано ниже. Наивное оценивание Наивное оценивание (23.25), судя по названию, является, вероятно, простейшим подходом.
Его можно продемонстрировать (на основе рассматриваемого примера запроса) с помощью приведенного ниже псевдокода. СОМР := РБ бо ппГ11 СОМР геасйен а "11хро1пп" ) /* Вмполнять, пока СОМР не достигнет "точки неизменности" */ СОКР := СОМР ОМ1ОН ( СОМР и РЯ ) ) епб ; 01БРЬАХ := СОМР ГНЕВЕ РХ = Р)) ('Р1') Каждая из переменных-отношений СОМР и 01БРЬАУ (подобно переменной-отношению РБ) имеет по два атрибута: РХ и РУ. Попросту говоря, выполнение этого алгоритма с получением промежуточного результата, состоящего из объединения соединения отношения РБ и предыдущего промежуточного результата, повторяется до тех пор, пока промежуточный результат не достигнет точки неизменности, т.е. пока не прекратится рост (изменение) промежуточного результата.
Замечание. Выражение СОМР м РБ является сокращенной формой записи выражения "соединить СОМР и РБ по атрибутам СОМР.РУ и РБ.РХ с выводом результатов по атрибутам СОМР.РХ и РБ.РУ". Для краткости здесь игнорируются операции переименования атрибута, соответствующие рассматриваемому диалекту данной алгебры (подробности приводятся в главе 6). Теперь попробуем применить этот алгоритм к рассматриваемому набору данных. Ниже показаны результаты выполнения первой итерации цикла: слева приведены значения выражения СОМР и РБ, а справа — значения величины СОМР (кортежи, добавленные в ходе этой итерации, отмечены звездочкой).
СОМР и РБ СОМР Далее привелены результаты, полученные после второй итерации. 926 Часть Р'. Дополнительные аспекты СОМР СОМР и РЯ Внимательно их просмотрев, можно заметить, что на второй итерации повторяется вычисление кортежей СОМР к РЯ, полученных во время первой итерации, а также вычисляется несколько дополнительных кортежей (в данном случае — два кортежа: ('Р1', 'Рб') и ('Р2', 'Рб')). Это делает методику наивного оценивания не очень привлекательной. После третьей итерации и повторения всех необходимых вычислений извлекаемые значения выражения СОМР к РЯ остаются теми же, что и в предыдущей итерации, Таким образом, точка неизменности для СОМР достигается и выполнение цикла завершается. Выполнив выборку СОМР по всем РХ, равным 'Р1', получим окончательный результат.
СОМР Неэффективность этого алгоритма проявляется еще и в том, что он выполняет огромную работу по поиску компонентов каждой детали, фактически вычисляя транзитивное замыкание отношения РЯ (ниже это описано более подробно), и оставляет в виде конечного результата лишь небольшую часть вычисленных кортежей. Иначе говоря, при этом выполняется большой объем ненужной работы. В заключение следует отметить, что наивное оценивание можно рассматривать как применение метода прямого формирования цепочки.
В самом деле, оно начинается с использования экстенсиональной базы данных (т.е. с действительных значений данных), а затем продолжается в виде повторного использования предпосылок определения (т.е. основы правила) вплоть до получения желаемого результата. Фактически этот алгоритм позволяет вьщнсл ать минимаэьную модазь для программы на языке (заш!оЯ (см. разделы 235 и 23 6). Полунаивное оценивание Первым очевидным усовершенствованием алгоритма наивного оценивания является возможность избежать повторных вычислений результатов, полученных во время предыдущей итерации.
Такой усовершенствованный алгоритм называется полунаивным 927 Глава 23. Логические системы управления базами данных оцениванием (23.28). Иначе говоря, на каждом шаге итерации вычисляются только новые кортежи, которые добавляются к полученным ранее результатам. Эта идея вновь будет проиллюстрирована на примере запроса "Найти все компоненты детали с номером 'Р1'". Ниже показана реализация соответствующей процедуры на псевдокоде. НЕИ :® РЯ СОМР := ИЕИ ; бо цпШ ИЕИ Ев ешрсу ; /* Виполнять, пока отношение ИЕИ не окажется пустим */ ИЕИ := ( ИЕИ ш РЯ ) М1ИОЯ СОМР СОМР := СОМР ОИ1ОИ КЕИ ; епб ; О1ЯРЬАХ := СОМР ИНЕССЕ РХ = Р() ('Р1') Теперь стоит просмотреть, как выполняется этот алгоритм на примере использованных ранее данных.
Перед выполнением цикла переменные-отношения ИЕН и СОМР идентичны переменной-отношению РЯ. 1ч Е%г СОМР После выполнения первой итерации эти переменные-отношения будут выглядеть следующим образом. В(Е(чГ СОМР Данные в переменной-отношении СОМР такие же, как при использовании алгоритма наивного оценивания, а данные в переменной-отношении ИЕИ содержат только те кортежи, которые были добавлены в СОМР на этой итерации.
Обратите внимание, что данные в переменной-отношении ИЕИ не содержат кортеж ('Р1', 'Р3') (сравните с данными, полученными при наивном оценивании). 928 Часть К Дополнительные аспекты Ниже приведены результаты, которые будут получены после выполнения следующей итерации. СОМР А)ЕЪУ На следующей итерации для переменной-отношения МЕМ никаких данных получено не будет и цикл завершится. Статическое фильтрование Статическое фильтрование базируется на основной идее классической теории оптимизации — налагать ограничения на самых ранних этапах вычислений.
Его можно рассматривать как приложение метода прямого формирования цепочки, поскольку в нем информация запроса (заключения) фактически используется для модификации правил (предпосылок). Иногда этот способ называется сокращениеи набора необходимых фактов, так как в нем информация запроса используется (вновь) для исключения ненужных кортежей из экстенсиональной базы данных непосредственно на выходе (23.29).
Эффективность этого способа мы продемонстрируем с помощью следующей процедуры на псевдокоде. МЕМ := РБ МНЕКЕ РХ = Р() ( 'Р1' ) СОМР := НЕМ ; бо цлШ МЕМ Ев вырву ; /Я Выполнять, пока отношение МЕМ не окажется пустын Я/ МЕЩ 1= (МЕН к РБ) М1МОБ СОМР СОМР := СОМР ОМ1ОМ МЕН елб ; 01БРЬАУ := СОМР Далее приводится последовательное описание этого алгоритма. Перед началом выполнения цикла переменные-отношения МЕН и СОМР выглядят так, как показано ниже. тч"ЕЪЧ СОМР 929 Глава 23. Логические системы управления базами данньп После первой итерации эти переменные-отношения примут следующий вид. 1чЕ 1яг СОМР В конце следующей итерации будет получен окончательный результат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
