Show simple item record

Authordc.contributor.authorRomero, Miguel 
Authordc.contributor.authorBarceló Baeza, Pablo 
Authordc.contributor.authorVardi, Moshe Y. 
Cita de ítemdc.identifier.citation2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Abstractdc.description.abstractThe 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.
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.uri
Sourcedc.sourceAnnual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Keywordsdc.subjectMathematics (all)
Títulodc.titleThe homomorphism problem for regular graph patterns
Document typedc.typeArtículo de revista
Indexationuchile.indexArtículo de publicación SCOPUS

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile