Datalog プログラムを最適化するための古典的なトリックは、対称性の破れです。対称性の破れにより、データベースで計算する必要がある事実の数を半分にすることができedge(0, 1)ますedge(1, 0)。
nxm 座標グリッドを考えてみましょう。このグリッド上で無向辺を記述する関係を書きたい場合、対称性を破る簡単な方法は、辺が小さい座標から大きい座標へと進む (たとえば(2, 3)へ(3, 3)、その逆ではない) ということです。以下は、正確にこの方法で 2x2 グリッドをモデル化する簡単な clingo プログラムです。
row(0..1).
col(0..1).
node(n(I, J)) :- row(I), col(J).
delta(0,1).
delta(1,0).
edge(e(N1, N2)) :-
node(N1), node(N2),
N1 = n(I1, J1),
N2 = n(I2, J2),
delta(I2-I1, J2-J1).
#show edge/1.
これにより、対称性が破られていない場合の 8 つではなく、エッジに関する 4 つの事実が生成されることがわかります。
edge(e(n(0,0),n(0,1)))
edge(e(n(1,0),n(1,1)))
edge(e(n(0,0),n(1,0)))
edge(e(n(0,1),n(1,1)))
この座標グリッドによって誘導される折れ線グラフを考えてみましょう。この折れ線グラフも無向なので、同様に対称を破りたいと思います。このグラフの対称性を破るコンパクトな方法は何ですか?
参考までに、対称性を破らない折れ線グラフのエッジの短い定義を次に示します。
ledge(l(E1, E2)) :-
edge(E1), edge(E2),
E1 = e(N1, N2),
E2 = e(N1, N3; N3, N1; N3, N2; N2, N3),
N3 != N1, N2 != N1.
#show ledge/1.
次の 2 つの事実が生成されるため、対称性が崩れていないことがわかります。
ledge(l(e(n(0,0),n(1,0)),e(n(1,0),n(1,1))))
ledge(l(e(n(1,0),n(1,1)),e(n(0,0),n(1,0))))