TY - GEN

T1 - The homomorphism problem for regular graph patterns

AU - Romero, Miguel

AU - Barceló, Pablo

AU - Vardi, Moshe Y.

N1 - Funding Information:
ACKNOWLEDGMENT This work was done in part while Romero was visiting the Simons Institute for the Theory of Computing. Barceló is funded by the Millennium Nucleus Center for Semantic Web Research under Grant NC120004.
Publisher Copyright:
© 2017 IEEE.

PY - 2017/8/8

Y1 - 2017/8/8

N2 - The evaluation of conjunctive regular path queries - which form the navigational core of the query languages for graph databases - raises challenges in the context of the homomorphism problem that are not fully addressed by existing techniques. We start a systematic investigation of such challenges using a notion of homomorphism for regular graph patterns (RGPs). We observe that the RGP homomorphism problem cannot be reduced to known instances of the homomorphism problem, and new techniques need to be developed for its study. We first show that the non-uniform version of the problem is computationally harder than for the usual homomorphism problem. By establishing a connection between both problems, in turn, we postulate a dichotomy conjecture, analogous to the algebraic dichotomy conjecture held in CSP. We also look at which structural restrictions on left-hand side instances of the RGP homomorphism problem ensure efficiency. We study restrictions based on the notion of bounded treewidth modulo equivalence, which characterizes tractability for the usual homomorphism notion. We propose two such notions, based on different interpretations of RGP equivalence, and show that they both ensure the efficiency of the RGP homomorphism problem.

AB - The evaluation of conjunctive regular path queries - which form the navigational core of the query languages for graph databases - raises challenges in the context of the homomorphism problem that are not fully addressed by existing techniques. We start a systematic investigation of such challenges using a notion of homomorphism for regular graph patterns (RGPs). We observe that the RGP homomorphism problem cannot be reduced to known instances of the homomorphism problem, and new techniques need to be developed for its study. We first show that the non-uniform version of the problem is computationally harder than for the usual homomorphism problem. By establishing a connection between both problems, in turn, we postulate a dichotomy conjecture, analogous to the algebraic dichotomy conjecture held in CSP. We also look at which structural restrictions on left-hand side instances of the RGP homomorphism problem ensure efficiency. We study restrictions based on the notion of bounded treewidth modulo equivalence, which characterizes tractability for the usual homomorphism notion. We propose two such notions, based on different interpretations of RGP equivalence, and show that they both ensure the efficiency of the RGP homomorphism problem.

UR - http://www.scopus.com/inward/record.url?scp=85034099821&partnerID=8YFLogxK

U2 - 10.1109/LICS.2017.8005106

DO - 10.1109/LICS.2017.8005106

M3 - Conference contribution

AN - SCOPUS:85034099821

T3 - Proceedings - Symposium on Logic in Computer Science

BT - 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017

Y2 - 20 June 2017 through 23 June 2017

ER -