Complexity of conjunctive regular path query homomorphisms

Autor: Florent R. Madelaine, Florent Foucaud, Lhouari Nourine, Gaétan Richard, Laurent Beaudou
Přispěvatelé: Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Laboratoire d'Algorithmique Complexité et Logique (LACL), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12), Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), IFCAM project 'Applications of graph homomorphisms' (MA/IFCAM/18/39)., ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017), ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2023
Předmět:
FOS: Computer and information sciences
Computer Science - Logic in Computer Science
Discrete Mathematics (cs.DM)
computer.internet_protocol
Computer science
Formal Languages and Automata Theory (cs.FL)
EXPTIME
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
computer.software_genre
01 natural sciences
Combinatorics
Computer Science - Databases
Regular expression
0101 mathematics
Computer Science::Databases
ComputingMilieux_MISCELLANEOUS
XPath
Graph database
[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB]
010102 general mathematics
InformationSystems_DATABASEMANAGEMENT
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Digraph
Databases (cs.DB)
Logic in Computer Science (cs.LO)
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics
Path (graph theory)
Regular graph
Homomorphism
computer
Computer Science::Formal Languages and Automata Theory
Computer Science - Discrete Mathematics
Zdroj: Conference on Computability in Europe (CiE 2019)
Conference on Computability in Europe (CiE 2019), Jul 2019, Durham, United Kingdom. pp.108-119, ⟨10.1007/978-3-030-22996-2_10⟩
Computing with Foresight and Industry ISBN: 9783030229955
CiE
Popis: 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 edges are labeled with regular expressions over the alphabet. RGPs model navigational queries for graph databases called 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. We study the complexity of deciding the existence of a homomorphism between two RGPs. Such homomorphisms model a strong type of containment between the two corresponding CRPQs. We show that this problem can be solved by an EXPTIME algorithm (while general query containmement 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 or SPARQL. For this case, homomorphism-based CRPQ containment is in NP. We prove that certain interesting cases are in fact polynomial-time solvable.
15 pages. Short version appeared in the proceedings of the 15th Conference on Computability in Europe (CIE 2019)
Databáze: OpenAIRE
Externí odkaz: