The homomorphism problem for regular graph patterns

Abstract

The evaluation of conjunctive regular path queries– which form the navigational core of the query languagesfor graph databases – raises challenges in the context of thehomomorphism problem that are not fully addressed by existingtechniques. We start a systematic investigation of such challengesusing a notion of homomorphism for regular graph patterns(RGPs). We observe that the RGP homomorphism problemcannot be reduced to known instances of the homomorphismproblem, and new techniques need to be developed for its study.We first show that the non-uniform version of the problemis computationally harder than for the usual homomorphismproblem. By establishing a connection between both problems,in turn, we postulate a dichotomy conjecture, analogous tothe algebraic dichotomy conjecture held in CSP. We also lookat which structural restrictions on left-hand side instances ofthe RGP homomorphism problem ensure efficiency. We studyrestrictions based on the notion of bounded treewidth moduloequivalence, which characterizes tractability for the usual ho-momorphism notion. We propose two such notions, based ondifferent interpretations of RGP equivalence, and show that theyboth ensure the efficiency of the RGP homomorphism problem.