Efficient evaluation of context-free path queries for graph databases
Ciro M. Medeiros, Martin Alejandro Musicante, Umberto Souza da Costa · 2018
We present a context-free path query evaluation algorithm inspired by top-down parsing techniques. Given a graph and a query defined over a context-free grammar, our algorithm identifies paths on the graph which form words of the language generated by the grammar. We show that our algorithm is correct. We conduct performance evaluation experiments with some popular ontologies and synthetic databases to endorse the efficiency of our approach. The algorithm presents a cubic worst-case runtime complexity in terms of the number of nodes in the graph, which is an improvement over previous work.