To evaluate path queries, one typically resorts to the relational semantics in which node pairs (m, n) are returned that are connected by a path of interest. A popular way to specify paths of interest is by the labeling of the edges of the path, e.g., by specifying languages of allowed labeling. Unfortunately, this relational semantics provides little insight in how node pairs (m, n) are obtained. To improve on this, we propose the single-path semantics, in which path queries are answered by minimal-length paths between such node-pairs.
Our original implementation of query evaluation using the single-path semantics allows one to evaluate context-free path queries. Furthermore, the underlying algorithms can also be used to efficiently determine the shortest strings in a context-free grammar. Our implementation is in C++14 and is tested using two modern C++ compiler, namely the Microsoft Visual C++ compiler and the GNU g++ compiler. We have one external dependency, namely the Fibonacci Heap implementation of the Boost library Version 1.73.0. The implementation is available for public use under the BSD-license (license details included in the source files).
Our revised implementation of query evaluation using the single-path semantics allows one to evaluate context-free path queries. Furthermore, the underlying algorithms can also be used to efficiently determine the shortest strings in a context-free grammar. Our implementation is in C++20 and is tested using three modern C++ compiler, namely the Microsoft Visual C++ compiler, the Clang compiler, and the GNU g++ compiler. We have one external dependency, namely the Fibonacci Heap implementation of the Boost library Version 1.81.1.0. The implementation is available for public use under the BSD-license (license details included in the source files).
Explaining results of path queries on graphs. . (2020). In: Software Foundations for Data Interoperability and Large Scale Graph Data Analytics, 84-98, Springer. DOI: 10.1007/978-3-030-61133-0_7. author copy, technical report, slides.
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.
Conjunctive context-free path queries. . (2014). In: Proceedings of the 17th International Conference on Database Theory (ICDT), 119-130, OpenProceedings.org. DOI: 10.5441/002/icdt.2014.15. author copy, slides.
In graph query languages, regular expressions are commonly used to specify the labeling of paths. A natural step in increasing the expressive power of these query languages is replacing regular expressions by context-free grammars. With the Conjunctive Context-Free Path Queries (CCFPQ) we introduce such a language based on the well-known Conjunctive Regular Path Queries (CRPQ).
First, we show that query evaluation of CCFPQ has polynomial time data complexity. Secondly, we look at the generalization of regular expressions, as used in CRPQ, to regular relations and show how similar generalizations can be applied to context-free grammars, as used in CCFPQ. Thirdly, we investigate the relations between the expressive power of CRPQ, CCFPQ, and their generalizations. In several cases we show that replacing regular expressions by context-free grammars does increase expressive power. Finally, we look at including context-free grammars in more powerful logics than conjunctive queries. We do so by adding negation and provide expressivity relations between the obtained languages.