Рекурсия (RECURSION)
Оператор рекурсии - оператор, создающий свойство, которое последовательно выполняет две операции:
- Рекурсивно строит промежуточное свойство (result) с дополнительным первым параметром (номером операции) следующим образом:
result(0, o1, o2, ..., oN) = initial(o1, ..., oN)
, гдеinitial
- начальное свойство.result(i+1, o1, o2, ..., oN) = step(o1, ..., oN, $o1, $o2, ..., $oN) IF result(i, $o1, $o2, ..., $oN)
, гдеstep
- свойство шага.
- Для всех значений полученного свойства вычисляет заданную агрегирующую функцию в разрезе всех его параметров, за исключением номера операции.
На данный момент для оператора рекурсии поддерживаются только два вида агрегирующих функций - SUM
и OR
. Последний используется в случае, когда начальное значение и шаг класса BOOLEAN
. SUM
используется во всех остальных случаях.
Отметим, что на некоторой итерации наборы объектов могут начать повторяться. В этом случае будем говорить что образуется цикл. Существует три политики работы с циклами:
CYCLES YES
- циклы допускаются. В этом случае при обнаружении цикла значение свойства будет равно максимально допустимому значению для класса значений этого свойства. Такая политика не поддерживается, когда начальное значение и шаг классаBOOLEAN
.CYCLES NO
(по умолчанию) - циклы не допускаются. Работает аналогично предыдущей политике, но дополнительно создается ограничение, что значение полученного свойства не должно быть равно максимальному значению (которое как раз и обозначает, что для данного набора объектов образовался цикл).CYCLES IMPOSSIBLE
- циклы невозможны. Как правило, используется, если среди объектов есть некоторый счетчик, который на каждой итерации увеличивается и, как следствие, повториться не может.
При использовании оператора рекурсии важно удостовериться в том, что рекурсивное построение коллекции будет конечно, то есть значение шага рано или поздно станет NULL
(как правило, речь идет о политике CYCLES IMPOSSIBLE
, так как в противном случае рекурсия остановится при первом найденном цикле). Если это условие не выполнено, операция будет принудительно остановлена в зависимости от настроек SQL сервера.
Язык
Для объявления свойства, реализующего рекурсию, используется оператор RECURSION
.
Примеры
CLASS Node;
edge = DATA BOOLEAN (Node, Node);
// итерация по integer от from к to (это свойство по умолчанию входит в модуль System)
iterate(i, from, to) = RECURSION i==from AND from IS INTEGER AND to IS INTEGER STEP i==$i+1 AND i<=to CYCLES IMPOSSIBLE;
// считает количество различных путей от a до b в графе
pathes 'Кол-во путей' (a, b) = RECURSION 1 AND a IS Node AND b==a STEP 1 IF edge(b, $b);
// определяет на каком уровне находится child от parent, и null если не является потомком (тем самым это свойство можно использовать для определения всех child'ов)
parent = DATA Group (Group);
level 'Уровень' (Group child, Group parent) = RECURSION 1 IF child IS Group AND parent == child
STEP 1 IF parent == parent($parent);
// числа Фибоначчи, свойство высчитывает все числа Фибоначи до значения to, (после будет возвращать null)
fib(i, to) = RECURSION 1 IF (i==0 OR i==1) AND to IS INTEGER STEP 1 IF (i==$i+1 OR i==$i+2) AND i<to CYCLES IMPOSSIBLE;