The queries are something like
Return all vertices such that (reachable from (A and (B or C))) and (not reachable from (D and E)).
The query can be formed with any kind of boolean constraints on reachability.
Are there efficient methods to do this query fast? Other than actually find the set of all item reachable vertex of concern, then do unions, intersections and set minus on those sets?
I think the only way to make the search faster than the default you suggest (calculate the sets reachable from each of the vertices in the predicate, then do set arithmetic), is to so the boolean math during the search, and use it to abort branches.
For example, suppose we're trying to calculate the set reachable from ((A or B) but not C). When searching the nodes, if we're on a node marked (B), and two of the "next" node are already marked (A) and (C) respectively. On these three nodes, the predicate reduces to:
(B): P = NOT(C)
(A): P = NOT(C)
(C): P = FALSE
So there's no reason to continue the search to either of these nodes.
(Naturally, if we're going to calculate more than one set on the same DAG, it behooves us to retain these marks.)