Regular path queries (RPQs) are a fundamental part of recent graph query languages like SPARQL and PGQL. They allow the definition of recursive path structures through regular expressions in a declarative pattern matching environment. We study the use of the K2-tree graph compression technique to materialize RPQ results with low memory consumption for indexing. Compact index representations enable the efficient storage of multiple indexes for varying RPQs.

Regular Path Queries (RPQs) are at the core of many recent declarative graph pattern matching languages. They leverage the compactness and expressiveness of regular expressions for matching recursive path structures. Unfortunately, most prior works on RPQs only consider breadth-first search as traversal strategy, neglecting other possible graph traversals like depth-first search or a combination of both. Within this paper, we conduct an analysis of graph traversals for RPQs by introducing a generalized graph traversal frame-work subsuming breadth-first search and depth-first search as extreme cases and thus opening up a new design space for graph traversals algorithms. We outline the underlying principles as well as provide comprehensive experimental evaluation using implementations which yield beneficial results regarding evaluation time and peak memory consumption.

Classical regular path queries (RPQs) can be too restrictive for some applications and answering such queries under approximate semantics to relax the query is desirable. While for answering regular path queries over graph databases under approximate semantics algorithms are available, such algorithms are scarce for the ontology-mediated setting. In this paper we extend an approach for answering RPQs over graph databases that uses weighted transducers to approximate paths from the query in two ways. The first extension is to answering approximate conjunctive 2-way regular path queries (C2RPQs) over graph databases and the second is to answering C2RPQs over ELH and DL-LiteR ontologies. We provide results on the computational complexity of the underlying reasoning problems and devise approximate query answering algorithms.