Магия сохраняет силу


Преобразования методом магических множеств для нерекурсивных программ - часть 2


Поэтому данную программу можно переписать без рекурсии.

Можно избежать введения рекурсии в магической программе, если не распознавать общих подвыражений. Если относиться к двум использованиям q в программе P как к двум разным таблицам q1 и q2, то преобразование методом магических множеств не приведет к появлению рекурсии, в чем можно убедиться, произведя преобразование методом магических множеств для программы P’, которая получается из P с использованием q1 и q2, определяемых в соответствии с P2.

Уточним интуитивные размышления, на которых основан приведенный пример.

Утверждение 4.1 Пусть M является запросом, полученным путем магического преобразования заданного запроса P в соответствии с набором полных SIPS. Тогда: (A) Если P является запросом с древовидной структурой, и (B) если P является направленным ациклическим графом (DAG), то в M будет иметься ограниченная рекурсия, которую можно избежать, не образуя общих подвыражений.




Начало  Назад  Вперед



Книжный магазин