AarXiv2022Cited 1×

Representing Paths in Graph Database Pattern Matching

Wim Martens, Matthias Niewerth, Tina Popp, Stijn Vansummeren, Domagoj Vrgoč

Abstract

'Domagoj Vrgoč'] Modern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that paths that match regular path queries can be returned to the user. This brings a number of challenges in terms of efficiency, caused by the fact that graphs can have a huge amount of paths between a given node pair.

A figure from Representing Paths in Graph Database Pattern Matching — fig. from the paper

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

Path multiset representations (PMRs) provide an exponentially succinct way to represent multisets of paths, enabling significant time and space savings for regular path query execution.

What’s new

i.Introduce path multiset representations (PMRs) for compactly encoding path multisets
ii.Analyze fundamental problems such as minimization and equivalence testing of PMRs
iii.Demonstrate that using PMRs yields significant time and space savings in query execution
iv.Show suitability of PMRs for extensions like counting, random sampling, unions, and joins

How they did it

We formally define PMRs and develop algorithms for their minimization and equivalence testing. Then we incorporate PMRs into query planning to assess their impact on execution efficiency.

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Representing Paths in Graph Database Pattern Matching

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

The paper, in five minutes

Similar papers in all four archives