[Toss-devel] Heuristics: expansion with Manhattan-distance-like properties

[Lukasz S. <luk...@gm...>]

Since I cannot fall asleep, I'll let the word out: as expected, we
will have a more robust, "smarter" expansion. And now we know how.

The expansion algorithm climbs a "spanning tree" where each path is a
"conjunctive query", and it returns a disjunction of longest paths
that are already expansions of the given relation. Why return a
disjunction of formulas that are already equal in the model? To have a
richer description, remember that disjunction will enter into the
final heuristic as a sum of these components. But the currently
implemented algorithm does a very poor job of finding a rich
description when there are lots (exponentially many) valid paths. It
searches in a depth-first manner, with a cut-off on the number of
stored current-best paths. That means for many problems it will return
similar paths, with long common prefixes.

Solution: after finding (using depth-first search almost as usual) a
valid path, instead of continuing the depth-first search, return to
the root and start search again with a different fixed permutation of
choices at each node. For example: after finding a conjunction ("a
valid path") by descending to relation "R" nodes before relation "C"
nodes (finding, say, an N shape), return to the root and search again
this time descending "C" first (finding, say, a Z shape).

Devil's in the details, though :-)