01/01/1990 09:00 AM
Computer Science
We study here the language Datalog(not =), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(not =) as a fragment of an infinitary logic L^omega and show that L^omega can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog(not =). As a case study, we classify the expressibility of *fixed subgraph homeomorphism* queries on directed graphs. Fortune et al. classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P not = NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog(not =).
