Path querying using conjunctive grammars
https://doi.org/10.15514/ISPRAS-2018-30(2)-8
Abstract
Graphs are used as a data structure to represent large volumes of information in a compact and convenient for analysis form in many areas: bioinformatics, graph databases, static code analysis, etc. In these areas, it is necessary to evaluate a queries for large graphs in order to determine the dependencies between the nodes. The answer to such queries is usually a set of all triples (A, m, n) for which there is a path in the graph from the vertex m to the vertex n, such that the labels on the edges of this path form a string derivable from the nonterminal A in some context-free grammar. This type of query is calculated using relational query semantics and context-free grammars but there are conjunctive grammars, which form a broader class of grammars than traditional context-free grammars. The use of conjunctive grammars in the path querying allows us to formulate more complex queries to the graph and solve a wider class of problems. It is known that the path querying using relational query semantics and conjunctive grammars is undecidable problem. In this paper, we propose a path querying algorithm which uses relational query semantics and conjunctive grammars, and approximates the exact solution. The proposed algorithm is based on matrix operations, and our evaluation shows that it is possible to significantly improve the performance of the algorithm by using a graphics processing unit.
About the Authors
R. Sh. Azimov
Saint Petersburg State University
Russian Federation
Russian Federation
S. V. Grigorev
Saint Petersburg State University
Russian Federation
Russian Federation
References
1. Anderson J. W. et al. Quantifying variances in comparative RNA secondary structure prediction. BMC bioinformatics, vol. 14, № 1, 2013.
2. Mendelzon A., Wood P. Finding Regular Simple Paths in Graph Databases. SIAM J. Computing, vol. 24, № 6, 1995, pp. 1235–1258.
3. Zhang Q., Su Z. Context-sensitive data-dependence analysis via linear conjunctive language reachability. Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, 2017, pp. 344–358.
4. Koznov D.V., Larchik E.V., Terekhov A.N. View to view transformations in domain specific modeling. Programming and Computer Software, vol. 41, № 4, 2015, pp. 208-214. DOI: 10.1134/S0361768815040039.
5. Hellings. J. Conjunctive context-free path queries. In: Proc. of ICDT’14, 2014, pp.119–130.
6. Okhotin A. Conjunctive grammars. Journal of Automata, Languages and Combinatorics, vol. 6, № 4, 2001, pp. 519–535.
7. Abiteboul S., Vianu V. Regular path queries with constraints. In Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1997 pp. 122–133.
8. Fan W., Li J., Ma S., Tang N, and Wu Y. 2011. Adding regular expressions to graph reachability and pattern queries. In 27th Data Engineering International Conference, 2011, pp. 39–50.
9. Nolé M. and Sartiani C. Regular path queries on massive graphs. In Proceedings of the 28th International Conference on Scientific and Statistical Database Management, 2016.
10. Reutter J., Romero M., and Vardi M. Regular queries on graph databases. Theory of Computing Systems, vol. 61, № 1, 2017, pp. 31–83
11. Azimov R. Sh., Grigorev S. V. Context-Free Path Querying by Matrix Multiplication. arXiv preprint, arXiv:1707.01007v2, 2017.
12. Sevon P., Eronen L. Subgraph queries by context-free grammars. Journal of Integrative Bioinformatics, vol. 5, № 2, 2008.
13. Zhang X. et al. Context-free path queries on RDF graphs. International Semantic Web Conference, 2016, pp. 632–648.
14. Abiteboul S., Hull R., Vianu V. Foundations of databases: the logical level. Addison-Wesley Longman Publishing Co., Inc., 1995.
15. Chomsky N. On certain formal properties of grammars. Information and control, vol. 2, № 2, 1959, pp. 137–167.
16. Kasami T. An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Report of University of Hawaii, Contract No. AF 19(628)-4379, No. 2, July, 1965.
17. Younger D.H. Recognition and parsing of context-free languages in time n3, Information and control, vol. 10, № 2, 1967, pp. 189–208.
18. Grune D., Jacobs C. J. H. Parsing Techniques (Monographs in Computer Science). Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2006.
19. Valiant L.G. General context-free recognition in less than cubic time. Journal of computer and system sciences, vol., № 2, pp. 308– 315.
20. Okhotin A. Conjunctive and Boolean grammars: the true general case of the context-free grammars. Computer Science Review, vol. 9, 2013. pp. 27–59.
21. Che S., Beckmann B.M., Reinhardt S.K. Programming GPGPU Graph Applications with Linear Algebra Building Blocks. International Journal of Parallel Programming, vol. 45, Issue 3, June 2017, pp 657–679.
22. Syme D., Granicz A., and Cisternino A. Expert F# 3.0. Springer, 2012.
23. The Math.Net Numerics WebSite. Доступно по ссылке: https://numerics.mathdotnet.com/, 20.03.2018.
24. The managedCuda library. Доступно по ссылке: https://kunzmi.github.io/managedCuda/, 20.03.2018.
25. Hellings J. Querying for Paths in Graphs using Context-Free Path Queries. arXiv preprint arXiv:1502.02242, 2015.
26. Okhotin A. 2004. Boolean grammars. Information and Computation, vol. 194, issue 1, 2004, pp. 19–48.
27. Okhotin A. Parsing by matrix multiplication generalized to Boolean grammars. Theoretical Computer Science, vol. 516, 2014, pp. 101–120.
Review
For citations:
Azimov R.Sh., Grigorev S.V. Path querying using conjunctive grammars. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(2):149-166. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(2)-8
Email this article 