# Integrating connection search in graph queries

arXiv: https://arxiv.org/abs/2208.04802 · HTML: https://mlsanity.com/paper/2208.04802/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 82 references that are in the map.
- First posted on arXiv 9 Aug 2022.

## Builds on (most cited first, 9 of 9)

- [G-CORE: A Core for Future Graph Query Languages](https://mlsanity.com/paper/1712.01550/) (2017)
- [Graph Pattern Matching in GQL and SQL/PGQ](https://mlsanity.com/paper/2112.06217/) (2021)
- [Graph integration of structured, semistructured and unstructured data for data journalism](https://mlsanity.com/paper/2007.12488/) (2020)
- [The Future is Big Graphs! A Community View on Graph Processing Systems](https://mlsanity.com/paper/2012.06171/) (2020)
- [Beyond Equi-joins: Ranking, Enumeration and Factorization](https://mlsanity.com/paper/2101.12158/) (2021)
- [Empowering Investigative Journalism with Graph-based Heterogeneous Data Management](https://mlsanity.com/paper/2102.04141/) (2021)
- [Regular Path Query Evaluation Sharing a Reduced Transitive Closure Based on Graph Reduction](https://mlsanity.com/paper/2111.06918/) (2021)
- [A Reachability Index for Recursive Label-Concatenated Graph Queries](https://mlsanity.com/paper/2203.08606/) (2022)
- [Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version)](https://mlsanity.com/paper/2207.06887/) (2022)

## Abstract (arXiv)

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.