Integrating Connection Search in Graph Queries

When graph database users explore unfamiliar graphs, potentially with heterogeneous structure, users 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, whic...

Full description

Saved in:
Bibliographic Details
Main Authors: Anadiotis, Angelos Christos, Manolescu, Ioana, Mohanty, Madhulika
Format: Conference Proceeding
Language:English
Subjects:
Ciphers
Costs
Data engineering
Graph Data Management
Graph Queries
Key-word Search on Graphs
Keyword search
Measurement
Shape
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:When graph database users explore unfamiliar graphs, potentially with heterogeneous structure, users 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.In this work, we formally show how to integrate connecting tree patterns (CTPs, in short) with a graph query language such as GPML [1], SPARQL or Cypher, leading to Extended Queries (or EQs, in short). We then study a set of algorithms for evaluating CTPs; we generalize prior keyword search work to be complete, most importantly by (i) considering bidirectional edge traversal, (ii) allowing users to select any score function for ranking CTP results and (iii) returning all results. To cope with very large search spaces, we propose efficient pruning techniques and formally establish a large set of cases where our best algorithm, MOLESP, is complete even with pruning. Our experiments validate the performance of our algorithms on many synthetic and real-world workloads.
ISSN:2375-026X
DOI:10.1109/ICDE55515.2023.00200