Dangers of List Processing in Querying Property Graphs

Speaker(s)

Alexandra Rogova

Affiliation

MIMUW

Language of the talk

English

Date

Feb. 25, 2025, 10:15 a.m.

Room

room 4060

Title in Polish

Dangers of List Processing in Querying Property Graphs

Seminar

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

The focus of graph databases is graph-like data, i.e. data that represents heavily-linked information where the topology is an important aspect. The workhorse of graph query languages is pattern matching. The result of pattern matching is a collection of paths and mappings of variables to graph elements. To increase expressiveness of pattern matching results, graph languages introduce the possibility of creating lists of nodes and edges from matched paths, and provide users with standard list processing tools such as reduce. In this talk, I will show that on the one hand, this makes it possible to capture useful classes of queries that pattern matching alone cannot do. On the other hand, this opens a backdoor to very high and unexpected expressiveness. In particular one can very easily express several classical NP-hard problems by simple queries that use reduce. This level of expressiveness appears to be beyond what query optimizers can handle, and indeed this is confirmed by an experimental evaluation, showing that such queries time out already on very small graphs.

---