Синтаксический анализ графов с использованием конъюнктивных грамматик

Графы используются в качестве структуры данных для представления больших объемов информации в компактной и удобной для анализа форме в различных областях - биоинформатике, графовых базах данных, статическом анализе кода и др. При этом оказывается необходимо вычислять запросы к большим графам с целью выявления зависимостей между их вершинами. Ответом на такие запросы обычно является множество всех троек (A, m , n ), для которых существует путь в графе от вершины m до вершины n такой, что метки на ребрах этого пути образуют строку, выводимою из нетерминала A в некоторой контекстно-свободной грамматике. Говорят, что такой тип запросов вычисляется с использованием реляционной семантики запросов. Кроме того, существуют конъюнктивные грамматики, образующие более широкий класс грамматик, чем традиционные контекстно-свободные грамматики. Использование конъюнктивных грамматик в задаче синтаксического анализа графов позволяет формулировать более сложные запросы к графу и решать более широкий круг задач. Известно, что задача вычисления запросов к графу с использованием реляционной семантики и конъюнктивных грамматик является неразрешимой. В данной работе предлагается алгоритм, вычисляющий приближенное решение этой задачи, а именно, аппроксимацию сверху. Предложенный алгоритм основан на матричных операциях, и проведенные эксперименты показывают, что его производительность может быть существенно повышена, благодаря использованию вычислений на графическом процессоре.

синтаксический анализ графов, конъюнктивные грамматики, транзитивное замыкание, матричные операции, вычисления на графическом процессоре

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.