Home
Scholarly Works
Explaining results of path queries on graphs:...
Conference

Explaining results of path queries on graphs: Single-path results for context-free path queries

Abstract

Many graph query languages use, at their core, path queries that yield node pairs that are connected by a path of interest. For the end-user, such node pairs only give limited insight as to why this query result is obtained, as the pair does not directly identify the underlying path of interest. To address this limitation of path queries, we propose the single-path semantics, which evaluates path queries to, for each node pair (m, n), a single path from m to n satisfying the conditions of the query. To put our proposal in practice, we provide an efficient algorithm for evaluating context-free path queries, a particular powerful type of path queries, using the single-path semantics. Additionally, we perform a short evaluation of our techniques that shows that the single-path semantics is practically feasible, even when query results grow large.

Authors

Hellings J

Volume

1281

Pagination

pp. 84-98

Publication Date

January 1, 2020

DOI

10.1007/978-3-030-61133-0_7

Conference proceedings

Communications in Computer and Information Science

ISSN

1865-0929
View published work (Non-McMaster Users)

Contact the Experts team