Статьи

Слюни: оценки на основе стека PHREAK и обратная цепочка

Некоторое время назад я написал блог о нашем новом алгоритме: http://blog.athico.com/2013/11/rip-rete-time-to-get-phreaky.html

Кто-то спросил меня о новой системе на основе стека и о том, как работает обратное связывание. Я ответил на них по электронной почте, но я подумал, что другие могут найти это полезным, поэтому вставил его ниже. Это написано прямо из моего мозга на страницу, так что это немного сырые места .; но я надеюсь, что некоторые найдут это полезным, несмотря ни на что.

Когда правило оценивается, оно оценивается от корня до кончика.

Для каждого узла он оценивает все возможные соединения и создает набор кортежей. Этот набор дочерних кортежей затем передается дочернему узлу. Переданный набор кортежей называется srcTupleSet (для имени переменной), после чего все дочерние элементы помещаются в trgTupleSet. TrgTupleSet передается дочернему узлу, где он становится srcTupleSet.

Строка 245 показывает этот цикл: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java#L245

1
srcTuples = trgTuples; // previous target, is now the source

Когда узел вводится, он имеет ряд переменных, которые необходимы для оценки узла. Идентификатор узла, память узла, память сегмента, srcTupleSet trgTupleSet. Любой узел можно приостановить и возобновить (выполнить оценку позднее), создав StackEntry, который ссылается на эти значения. StackEntry помещается в стек. Вот класс StackEntry: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/StackEntry.java

Это необходимо по двум причинам: обратное связывание и подсети. Обратная цепочка выполняется через узел запроса.

Когда распространение достигает узла запроса, ему необходимо приостановить оценку текущего правила – поэтому он создает StackEntry и помещает его в стек.

строка 459: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java#L459

Запрос – это просто правило без RHS, без последствий. Он собирает все результаты, которые достигают терминального узла, и возвращает их вызывающей стороне. Узел запроса позволяет правилу вызывать запрос, передавая аргументы. Вызов запроса выполняется путем вставки объекта DroolsQuery, который соответствует корневому шаблону и запускает распространение:

см. строку 67: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/PhreakQueryNode.java

1
LeftInputAdapterNode.doInsertObject(handle, pCtx, lian, wm, lm, false, dquery.isOpen());

Как и пролог, аргументы могут быть связаны или не связаны. Связанный аргумент – это переменная, а несвязанный аргумент – это переменная. В случае реализации мы не применяем ограничения к несвязанным аргументам. Это позволяет выполнять классический тип запроса «транзитивное замыкание». И хотя правило может вызывать запрос, запрос также может вызывать запрос (у нас нет табуляции для обнаружения бесконечных циклов).

1
2
3
4
5
query isContainedIn( String x, String y )
  Location( x, y; )
  or
  ( Location( z, y; ) and isContainedIn( x, z; ) )
end

Примечание drools поддерживает позиционные и щелевые аргументы в шаблонах. Это делается путем сопоставления всех позиций в слоте.

Пошаговое руководство, показывающее вышеуказанный запрос в действии, для реактивных и нереактивных транзитивных замыканий, можно найти здесь: https://www.youtube.com/watch?v=fCjIRVSRFvA

Для оценочного запроса, когда trgTulupleSet достигает терминального узла, он выполняет итерацию и добавляет каждый кортеж в «сборщик».

см. строку 65: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/PhreakQueryTerminalNode.java#L65

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

см. строку 343: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/reteoo/QueryElementNode.java#L343

Как только запрос закончил оценку, он возвращается. Затем процесс перенастройки позволяет выполнению посетить стек, где он выталкивает StackEntry и возобновляет оценку – но теперь результаты запроса доступны.

см. строки 166 и 173: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java

Запрос может быть вызван реактивно и нереактивно. Неактивно означает, что не осталось левой памяти, а запрос не оставлен открытым. Реактивно означает, что осталась память, а запрос оставлен открытым. Реактивный запрос является полностью инкрементным и поддерживает обновления и удаления:

см. строки 143 и 169: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/PhreakQueryNode.java#L143

Структуры данных, которые мы используем для кортежей и «вложенных» (результат запроса), эффективны и «свободны от копирования» и «свободны от поиска» – все это списки с двойными связями. Это было необходимо для повышения эффективности дополнительных запросов.

Подсети используют аналогичную технику. В момент достижения подсети внешнее правило приостанавливается (помещается в стек) и создается оценка внутренней сети.

см. строки 593 и 604: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java

Как только подсеть закончена, внешнее правило возобновляет и помещает результаты в правый вход внешнего дочернего узла:

строка 662: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java#L662

Как уже упоминалось ранее, мы предоставляем ленивую оценку правил, но не добавочную оценку правил. Как только начинается оценка правила, создаются все кортежи. Однако, поскольку запись в стеке может быть приостановлена ​​и возобновлена ​​на любом узле, она также может быть использована для обеспечения инкрементальной оценки правил – хотя мы сейчас этого не делаем. По сути, вы «берете» X количество объектов на правом входе – это может быть 1, или 5, или 25, или 100. Это число позволяет вам настроить задержку по сравнению с пропускной способностью. После получения, если все еще не оценены правильные входные данные, вы создаете StackEntry, который вызывает переоценку этого узла после завершения текущего распространения.

Ссылка: Drools: оценки на основе стека PHREAK и обратная цепочка от нашего партнера JCG Джеффри Де Смета в блоге Drools & jBPM .