We introduce symmetric Datalog, a syntactic restriction of linear
Datalog and show that its expressive power is exactly that of
restricted symmetric monotone Krom SNP. The deep result of
Reingold on the complexity of undirected
connectivity suffices to show that symmetric Datalog queries can be
evaluated in logarithmic space. We show that for a number of
constraint languages \Gamma, the complement of the constraint
satisfaction problem CSP(\Gamma) can be expressed in symmetric
Datalog. In particular, we show that if CSP(\Gamma) is
first-order definable and \Lambda is a finite subset of the
relational clone generated by \Gamma then \neg \CSP(\Lambda) is
definable in symmetric Datalog. Over the two-element domain and
under a standard complexity-theoretic assumption, expressibility of
\neg CSP(\Gamma) in symmetric Datalog corresponds exactly to the
class of CSPs solvable in logarithmic space. Finally, we describe a
fairly general subclass of implicational (or 0/1/all) constraints
for which the complement of the corresponding CSP is also definable
in symmetric Datalog. Our results provide preliminary evidence that
symmetric Datalog may be a unifying explanation for families of CSPs
lying in L.