Запросы примерно такие
Вернуть все вершины такие, что (достижимы из (A и (B или C))) и (не достижимы из (D и E)).
Запрос может быть сформирован с любыми булевыми ограничениями на достижимость.
Существуют ли эффективные методы для быстрого выполнения этого запроса? Помимо того, что на самом деле найти набор всех достижимых вершин интересующего элемента, нужно ли объединять, пересекать и устанавливать минус в этих наборах?
Я думаю, что единственный способ сделать поиск быстрее, чем по умолчанию, которое вы предлагаете (вычислить наборы, достижимые из каждой из вершин в предикате, а затем выполнить арифметику набора), - это использовать логическую математику во время поиска и использовать его для прерывания ветви.
Например, предположим, что мы пытаемся вычислить множество, достижимое из ((A или B), но не из C). При поиске узлов, если мы находимся на узле, отмеченном (B), и два из «следующих» узлов уже отмечены (A) и (C) соответственно. На этих трех узлах предикат сводится к:
(B): P = NOT(C)
(A): P = NOT(C)
(C): P = FALSE
Так что нет причин продолжать поиск любого из этих узлов.
(Естественно, если мы собираемся рассчитать более одного набора для одного и того же DAG, нам следует сохранить эти метки.)
