Complexity of conjunctive regular path query homomorphisms
| العنوان: | Complexity of conjunctive regular path query homomorphisms |
|---|---|
| المؤلفون: | Florent R. Madelaine, Florent Foucaud, Lhouari Nourine, Gaétan Richard, Laurent Beaudou |
| المساهمون: | 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) |
| المصدر: | 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 |
| سنة النشر: | 2023 |
| مصطلحات موضوعية: | 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 |
| الوصف: | 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) |
| اللغة: | English |
| ردمك: | 978-3-030-22995-5 |
| الوصول الحر: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e6d640753a0051d19cbca2db0a68839eTest http://arxiv.org/abs/2305.07271Test |
| حقوق: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....e6d640753a0051d19cbca2db0a68839e |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783030229955 |
|---|