Intégration de la recherche de connexion dans les requêtes de graphique
| Autor: | Anadiotis, Angelos Christos, Manolescu, Ioana, Mohanty, Madhulika |
|---|---|
| Přispěvatelé: | Mohanty, Madhulika, Oracle Labs Switzerland, École polytechnique (X), Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020), Inria Saclay - Île de France |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Artificial Intelligence (cs.AI) [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Computer Science - Databases [INFO.INFO-WB] Computer Science [cs]/Web Computer Science - Artificial Intelligence [INFO.INFO-WB]Computer Science [cs]/Web Keyword Search on Graphs [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB] Databases (cs.DB) [INFO]Computer Science [cs] Graph Queries Graph Data Management |
| Zdroj: | BDA 2022-38ème Conférence sur la Gestion de Données-Principes, Technologies et Applications BDA 2022-38ème Conférence sur la Gestion de Données-Principes, Technologies et Applications, Oct 2022, Clermont-Ferrand, France Inria Saclay-Île de France. 2023 ICDE 2023-39th IEEE International Conference on Data Engineering ICDE 2023-39th IEEE International Conference on Data Engineering, Apr 2023, Anaheim (CA), United States |
| Popis: | National audience; Graph data management and querying has many practical applications. When graphs are very heterogeneous and/or users are unfamiliar with their structure, they may need to find how two or more groups of nodes are connected in a graph, even when users are not able to describe the connections. This is only partially supported by existing query languages, which allow searching for paths, but not for trees connecting three or more node groups. The latter is related to the NP-hard Group Steiner Tree problem, and has been previously considered for keyword search in databases. In this work, we formally show how to integrate connecting tree patterns (CTPs, in short) within a graph query language such as SPARQL or Cypher, leading to an Extended Query Language (or EQL, in short). We then study a set of algorithms for evaluating CTPs; we generalize prior keyword search work, most importantly by (i) considering bidirectional edge traversal and (ii) allowing users to select any score function for ranking CTP results. To cope with very large search spaces, we propose an efficient pruning technique and formally establish a large set of cases where our algorithm, MOLESP, is complete even with pruning. Our experiments validate the performance of our CTP and EQL evaluation algorithms on a large set of synthetic and real-world workloads. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|