Complexity of Conjunctive Regular Path Query Homomorphisms

Laurent Beaudou (1) , Florent Foucaud (1) , Florent Madelaine (2) , Lhouari Nourine (1) , Gaétan Richard (3)

1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
2 LACL - Laboratoire d'Algorithmique Complexité et Logique
3 Equipe AMACC - Laboratoire GREYC - UMR6072

A graph database is a digraph whose arcs are labelled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labelled with regular expressions over the alphabet. RGPs model navigational queries for graph databases, more precisely, conjunctive regular path queries. A match of a navigational RGP query in the database is witnessed by a special navigational homomorphism of the RGP to the database. We study the complexity of deciding the existence of a homomorphism between two RGPs. Such homomorphisms model a strong type of containment between two navigational RGP queries. We show that this problem can be solved by an EXPTIME algorithm (while general query containment in this context is EXPSPACE-complete). We also study the problem for restricted RGPs over a unary alphabet, that arise from some applications like XPath, and prove that certain interesting cases are polynomial-time solvable.

Domains: Logic in Computer Science [cs.LO]; Databases [cs.DB]

Laurent Beaudou, Florent Foucaud, Florent Madelaine, Lhouari Nourine, Gaétan Richard. Complexity of Conjunctive Regular Path Query Homomorphisms. Conference on Computability in Europe (CiE 2019), Jul 2019, Durham, United Kingdom. pp.108-119, ⟨10.1007/978-3-030-22996-2_10⟩. ⟨hal-02288666⟩