arXiv:2305.07271 · v2
Complexity of conjunctive regular path query homomorphisms
摘要
A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose arcs are labeled with regular expressions over the alphabet. RGPs model navigational queries for graph databases called \emph{conjunctive regular path queries} (CRPQs). A match of a CRPQ in the database is witnessed by a special navigational homomorphism of the corresponding RGP to the database, where vertices of the RGP are mapped by a function $f$ to the vertices of the database, and for each arc $uv$ of the RGP, we require the existence of a walk in the database from $f(u)$ to $f(v)$, such that the word corresponding to the sequence of labels of that walk belongs to the regular language labeling the arc $uv$. We extend this definition to one of navigational homomorphisms between two RGPs, modeling a homomorphism-based form of CRPQ containment. We study the complexity of deciding the existence of such a homomorphism between RGPs. We show that this problem, in the case where general walks are considered, can still be solved by an EXPSPACE algorithm (just like general CRPQ Containment, which is known to be EXPSPACE-complete). In the case of simple paths or trails, in fact the navigational homomorphism problem considered here becomes much more tractable, as it is PSPACE-complete. We also study the problem for restricted RGPs over a unary alphabet, that arise from some applications like XPath or SPARQL. For this case, homomorphism-based CRPQ containment is in NP. We prove that certain interesting cases are in fact polynomial-time solvable.
作者备注：24 pages, 7 figures. A short version appeared in the proceedings of the 15th Conference on Computability in Europe (CIE 2019). This improved version corrects mistakes from earlier versions, contains new results, and has one additional author