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 ... more >>>