Context-free path querying with all-path semantics using matrices with sets of intermediate vertices.

Azimov R.Sh., Grigorev S.V. Context-free path querying with all-path semantics using matrices with sets of intermediate vertices.

Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2021, vol. 21, no. 4, pp. 499–505 (in Russian). doi: 10.17586/2226-1494-2021-21-4-499-505

The study considers the problem of context-free path querying with all-path query semantics. This problem consists in finding all paths of the graph, the labels on the edges of which form words from the language generated by the input context-free grammar. There are two approaches to evaluate context-free path queries using linear algebra operations: matrix multiplication-based and the Kronecker product-based. But until now, there is no algorithm using the matrix multiplication capable of handling context-free path queries with the most complex all-path query semantics, in which the all paths that match the query must be provided. The paper proposes the algorithm for context-free path query evaluation using the matrix multiplication, which is capable of processing queries with the all-path query semantics. In the adjacency matrix of the input graph for each pair of vertices, we store additional information about the paths found between these vertices in the form of a set of possible intermediate vertices. At the first stage, a set of matrices is constructed that store such information about all paths that satisfy the input query. At the second stage, all queried paths are restored from the constructed set of matrices. The proposed algorithm was implemented in C++ and a comparison was made with other most efficient algorithms for evaluating context-free path queries, namely with the matrix-based algorithm that allows us to find only one such path, and with the Kronecker product-based algorithm that allows us to find all such paths in the graph. The results of the experimental study showed that the proposed algorithm is significantly more efficient in restoring the queried paths, but in some cases it consumes a significantly larger amount of memory than the algorithm based on the Kronecker product. The described algorithm can be applied in static code analysis, bioinformatics, network analysis, as well as in graph databases, when it is required to find all possible dependencies in the data presented in the form of a labeled graph.

1. Rehof J., Fähndrich M. Type-base flow analysis: from polymorphic subtyping to CFL-reachability. SIGPLAN Notices, 2001, vol. 36, no. 3, pp. 54–66. https://doi.org/10.1145/373243.360208

2. Zheng X., Rugina R. Demand-driven alias analysis for C. Proc. 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’08), 2008, pp. 197–208.  

3. Sevon P., Eronen L. Subgraph queries by context-free grammars. Journal of Integrative Bioinformatics, 2008, vol. 5, no. 2, pp. 157–172. https://doi.org/10.1515/jib-2008-100

4. Zhang X., Feng Z., Wang X., Rao G.Z., Wu W.R. Context-free path queries on RDF graphs. Lecture Notes in Computer Science, 2016, vol. 9981, pp. 632–648. https://doi.org/10.1007/978-3-319-46523-4_38

5. Medeiros C., Musicante M.A., Costa U.S. Efficient evaluation of context-free path queries for graph databases. Proc. 33rd Annual ACM Symposium on Applied Computing (SAC-2018), 2018, pp. 1230–1237. https://doi.org/10.1145/3167132.3167265

6. Santos F., Costa U.S., Musicante M.A. A bottom-up algorithm for answering context-free path queries in graph databases. Lecture Notes in Computer Science, 2018, vol. 10845, pp. 225–233. https://doi.org/10.1007/978-3-319-91662-0_17

7. Grigorev S., Ragozina A. Context-free path querying with structural representation of result. Proc. 13th Central & Eastern European Software Engineering Conference in Russia (CEE-SECR’17), 2017, pp. 3166104. https://doi.org/10.1145/3166094.3166104

8. Verbitskaia E., Grigorev S., Avdyukhin D. Relaxed parsing of regular approximations of string-embedded languages. Lecture Notes in Computer Science, 2016, vol. 9609, pp. 291–302. https://doi.org/10.1007/978-3-319-41579-6_22

9. Verbitskaia E., Kirillov I., Nozkin I., Grigorev S. Parser combinators for context-free path querying. Proc. 9th ACM SIGPLAN International Symposium on Scala (Scala 2018), 2018, pp. 13–23. https://doi.org/10.1145/3241653.3241655

10. Kuijpers J., Fletcher G., Yakovets N., Lindaaker T. An experimental study of context-free path query evaluation methods. Proc. 31st International Conference on Scientific and Statistical Database Management (SSDBM-2019), 2019, pp. 121–132. https://doi.org/10.1145/3335783.3335791

11. Azimov R., Grigorev S. Context-free path querying by matrix multiplication. Proc. 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics (GRADES-NDA 2018), 2018, pp. a5. https://doi.org/10.1145/3210259.3210264

12. Terekhov A., Khoroshev A., Azimov R., Grigorev S. Context-free path querying with single-path semantics by matrix multiplication. Proc. 3rd ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics (GRADES-NDA 2020), 2020, pp. 5. https://doi.org/10.1145/3398682.3399163

13. Orachev E., Epelbaum I., Azimov R., Grigorev S. Context-free path querying by kronecker product. Lecture Notes in Computer Science, 2020, vol. 12245, pp. 49–59. https://doi.org/10.1007/978-3-030-54832-2_6

14. Chomsky N. On certain formal properties of grammars. Information and Control, 1959, vol. 2, no. 2, pp. 137–167. https://doi.org/10.1016/S0019-9958(59)90362-6

15. Abiteboul S., Hull R., Vianu V. Foundations of Databases: The Logical Level. 1st ed. Addison-Wesley, 1995, 704 p.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License