On the expressive power of datalog
Phokion G. Kolaitis, Moshe Y. Vardi · 1990
We study here the language Datalog(≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(≠) as a fragment of an infinitary logic Lω and show that Lω can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog(≠). As a case study, we classify the expressibility of fixed subgraph homeomorphism queries on directed graphs. Fortune et al. [FHW80] classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P ≠ NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog(≠).