Поиск DAG с логическими ограничениями на достижимость

Question

Запросы похожи на

Вернуть все вершины так, чтобы (доступно из (A и (B или C))) и (недоступно из (D и E)).

Запрос может быть сформирован с любыми логическими ограничениями на достижимость.

Существуют ли эффективные методы для быстрого выполнения этого запроса? Кроме того, чтобы на самом деле найти множество всех достижимых вершин предмета, представляющих интерес, тогда объединения, пересечения и установить минус на этих множествах?

Answer 1

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

Например, предположим, что мы пытаемся вычислить набор, достижимый из ((A или B), но не C). При поиске узлов, если мы находимся на узле, отмеченном (B), и два «следующих» узла уже отмечены (A) и (C) соответственно. На этих трех узлах предикат уменьшается до:

(B): P = NOT(C)
(A): P = NOT(C)
(C): P = FALSE

Так что нет причин продолжать поиск на любом из этих узлов.

(Естественно, если мы собираемся рассчитать более одного набора на одном и том же DAG, мы должны сохранить эти метки.)