Задача поиска путей в ациклических графах с ограничениями в терминах булевых грамматик

Графовая модель данных активно используется в научных и прикладных областях, например, в графовых базах данных, биоинформатике, при анализе социальных сетей и в статическом анализе кода. Одной из основных задач, связанных с графовыми моделями, является поиск специфичных путей в графе. Естественным способом задать ограничения на пути являются формальные грамматики над метками рёбер графа, при этом запрос к графу может быть представлен в виде множества всех троек , для которых существует путь в графе от вершины  до вершины  такой, что метки на ребрах этого пути образуют строку, выводимую из нетерминала  в данной грамматике. Использование булевых грамматик позволяет формулировать более выразительные запросы по сравнению с традиционно используемыми регулярными и контекстно-свободными грамматиками. Известно, что задача выполнения запросов к графу с использованием булевых грамматик является неразрешимой. В данной работе предложен приближённый алгоритм поиска путей в ориентированных графах без циклов с ограничениями, заданными с помощью булевых грамматик. Благодаря ограничению на тип анализируемых графов, предложенный алгоритм является более асимптотически оптимальным, чем наивный итерационный алгоритм.

1. Barceló Baeza P. Querying graph databases. In Proc. of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems (PODS '13), 2013, pp. 175-188.

2. Mendelzon A., Wood P. Finding Regular Simple Paths in Graph Databases. SIAM Journal on Computing, vol. 24, № 6, 1995, pp. 1235-1258.

3. Anderson J. W. et al. Quantifying variances in comparative RNA secondary structure prediction. BMC bioinformatics, vol. 14, 2013.

4. Chaudhary A., Faisal A. Role of graph databases in social networks. 2016, available at: https://www.researchgate.net/publication/304462174_Role_of_graph_databases_in_social_networks, accessed 02.06.2019.

5. Warchał, Ł. Using Neo4j graph database in social network analysis. Studia Informatica, vol. 33, № 2A, 2012, pp. 271-279.

6. Reps T. Program analysis via graph reachability. In Proc. of the 1997 international symposium on Logic programming (ILPS '97), 1997, pp. 5-19.

7. Zhang Q., Su Z. Context-sensitive data-dependence analysis via linear conjunctive language reachability. In Proc. of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, 2017, pp. 344–358.

8. Yuan H., Eugster P. An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees. In Proc. of the 18th European Symposium on Programming Languages and Systems: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009 (ESOP '09), 2009, pp. 175-189.

9. Neo4j's Graph Query Language: An Introduction to Cypher. Available at: https://neo4j.com/developer/cypher-query-language/, accessed 02.06.2019.

10. Rodriguez M. A. The gremlin graph traversal machine and language (invited talk). In Proc. of the 15th Symposium on Database Programming Languages, 2015, pp. 1–10.

11. Eric Prud'hommeaux, Andy Seaborne (eds). SPARQL query language for RDF. W3C Recommendation 15 January 2008. Available at: https://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/, accessed 02.06.2019.

12. Okhotin A. Conjunctive grammars. Journal of Automata, Languages and Combinatorics, vol. 6, № 4, 2001, pp. 519–535.

13. Okhotin A. Boolean grammars. Information and Computation, vol. 194, issue 1, 2004, pp. 19–48.

14. Hellings J. Querying for Paths in Graphs using Context-Free Path Queries. CoRR abs/1502.02242, 2015.

15. Hellings. J. Conjunctive context-free path queries. In Proc. of the International Conference on Database Theory (ICDT’14), 2014, pp.119–130.

16. Sevon P., Eronen L. Subgraph queries by context-free grammars. Journal of Integrative Bioinformatics, vol. 5, № 2, 2008.

17. Zhang X. et al. Context-free path queries on RDF graphs. In Proc. of the International Semantic Web Conference, 2016, pp. 632–648.

18. Grigorev S., Ragozina A. Context-free path querying with structural representation of result. In Proc. of the 13th Central & Eastern European Software Engineering Conference in Russia (CEE-SECR '17), article 10.

19. Azimov R.Sh., Grigorev S.V. Context-Free Path Querying by Matrix Multiplication. CoRR, vol. abs/1707.01007, 2017.

20. Азимов Р.Ш., Григорьев С.В. Синтаксический анализ графов с использованием конъюнктивных грамматик. Труды ИСП РАН, том 30, вып. 2, 2018 г., стр. 149-166 / Azimov R.Sh., Grigorev S.V. Path querying using conjunctive grammars. Trudy ISP RAN/Proc. ISP RAS, vol. 30, issue. 2, 2018, pp. 149-166 (in Russian). DOI: 10.15514/ISPRAS-2018-30(2)-8.

21. Valiant L.G. General context-free recognition in less than cubic time. Journal of computer and system sciences, vol. 10, № 2, 1975, pp. 308– 315.

22. Okhotin A. Parsing by matrix multiplication generalized to Boolean grammars. Theoretical Computer Science, vol. 516, 2014, pp. 101–120.

23. Арлазаров В.Л., Диниц Е.А., Кронрод М.А., Фараджев И.А. Об экономном построении транзитивного замыкания ориентированного графа. Доклады АН СССР, том 194, № 3, 1970, pp. 487–488 / Arlazarov V.L., Dinitz Y.A., Kronrod M.A., Faradzhev I.A. On economical construction of the transitive closure of an oriented graph. Doklady Akademii Nauk SSSR, vol. 194, № 3, 1970, pp. 487–488 (in Russian).

24. Vassilevska Williams V. Multiplying matrices faster than Coppersmith-Winograd. In Proc. of the 44th Symposium on Theory of Computing, (STOC2012), 2012, pp. 887–898.

25. Tarjan R.E. Depth-first search and linear graph algorithms. In Proc. of the 12th Annual Symposium on Switching and Automata Theory (SWAT 1971), 1971, pp. 114-121.

26. Koschmieder André, Leser Ulf. Regular Path Queries on Large Graphs. In Proc. of the 24th International Conference on Scientific and Statistical Database Management (SSDBM’12), 2012, pp. 177–194.

27. Reutter Juan L., Romero Miguel, Vardi Moshe Y. Regular Queries on Graph Databases. Theory of Computing Systems, vol. 61, № 1, 2017, pp. 31–83.

28. Lu C., Yu J. X., Li R., Wei H. Exploring Hierarchies in Online Social Networks. IEEE Transactions on Knowledge and Data Engineering, vol. 28, № 8, 2016, pp. 2086-2100.

29. Sridharan, M., Gopan, D., Shan, L., Bod ́ık, R. Demand-driven points-to analysis for Java. In Proc. of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA2005), 2005, pp. 59–76.

30. Терехов А.Н., Эрлих Л.А., Терехов А.А. История и архитектура проекта RescueWare. В сб. «Автоматизированный реинжиниринг программ», Издательство Санкт-Петербургского государственного университета, 2000 г., стр. 7-19 / Terekhov A.N., Erlikh L.A., Terekhov A.A. History and architecture of a project RescueWare. In «Automated software reengineering», Publishing House of St. Petersburg State University, 2000, pp. 7-19 (in Russian).

31. Medeiros Ciro M., Musicante Martin A., Costa Umberto S. Efficient evaluation of context-free path queries for graph databases. In Proc. of the 33rd Annual ACM Symposium on Applied Computing (SAC '18), 2018, pp. 1230-1237.

32. Rosenkrantz D.J., Stearns R.E. Properties of deterministic top-down grammars. Information and Control, vol. 17, № 3, 1970, pp. 226-256.