{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T09:55:28Z","timestamp":1779011728548,"version":"3.51.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study the optimization of navigational graph queries in the form of the Regular Queries, i.e., queries which combine recursive and pattern-matching fragments. Current approaches to their evaluation are not effective in practice. Towards addressing this, we present a number of novel powerful optimization techniques which aim to constrain the intermediate results during query evaluation. We show how these techniques can be planned effectively and executed efficiently towards the first practical evaluation solution for complex navigational queries on real-world workloads. Indeed, our experimental results show several orders of magnitude improvement in query evaluation performance over state-of-the-art techniques on a wide range of queries on diverse datasets.<\/jats:p>","DOI":"10.1007\/s00778-024-00892-7","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T03:21:24Z","timestamp":1737429684000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimizing navigational graph queries"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-5847-5941","authenticated-orcid":false,"given":"Thomas","family":"Mulder","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2111-6769","authenticated-orcid":false,"given":"George","family":"Fletcher","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1488-1414","authenticated-orcid":false,"given":"Nikolay","family":"Yakovets","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,21]]},"reference":[{"key":"892_CR1","doi-asserted-by":"publisher","unstructured":"Aimonier-Davat, J., Skaf-Molli, H., Molli, P., Dang, M.H., N\u00e9delec, B.: Join ordering of sparql property path queries. In: The Semantic Web: 20th International Conference, ESWC 2023, Hersonissos, Crete, Greece, May 28\u2013June 1, 2023, Proceedings, p. 38\u201354. Springer-Verlag, Berlin, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-33455-9_3","DOI":"10.1007\/978-3-031-33455-9_3"},{"key":"892_CR2","doi-asserted-by":"publisher","unstructured":"Angles, R., Aranda, C.B., Hogan, A., Rojas, C., Vrgo\u010d, D.: Wdbench: A wikidata graph query benchmark. In: The Semantic Web \u2013 ISWC 2022: 21st International Semantic Web Conference, Virtual Event, October 23\u201327, 2022, Proceedings, p. 714\u2013731. Springer-Verlag, Berlin, Heidelberg (2022).https:\/\/doi.org\/10.1007\/978-3-031-19433-7_41","DOI":"10.1007\/978-3-031-19433-7_41"},{"key":"892_CR3","doi-asserted-by":"publisher","unstructured":"Arch, S., Hu, X., Zhao, D., Suboti\u0107, P., Scholz, B.: Building a join optimizer for souffl\u00e9. In: Logic-Based Program Synthesis and Transformation: 32nd International Symposium, LOPSTR 2022, Tbilisi, Georgia, September 21\u201323, 2022, Proceedings, p. 83\u2013102. Springer-Verlag, Berlin, Heidelberg (2022).https:\/\/doi.org\/10.1007\/978-3-031-16767-6_5","DOI":"10.1007\/978-3-031-16767-6_5"},{"key":"892_CR4","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., G\u00f3mez-Brand\u00f3n, A., Hogan, A., Navarro, G., Rojas-Ledesma, J.: Optimizing rpqs over a compact graph representation. The VLDB Journal pp. 1\u201326 (2023)","DOI":"10.1007\/s00778-023-00811-2"},{"key":"892_CR5","doi-asserted-by":"publisher","unstructured":"Arroyuelo, D., Hogan, A., Navarro, G., Rojas-Ledesma, J.: Time- and space-efficient regular path queries. In: 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022, pp. 3091\u20133105. IEEE (2022).https:\/\/doi.org\/10.1109\/ICDE53745.2022.00277","DOI":"10.1109\/ICDE53745.2022.00277"},{"key":"892_CR6","unstructured":"Barcel\u00f3, P., P\u00e9rez, J., Reutter, J.L.: Relative expressiveness of nested regular expressions. In: J.\u00a0Freire, D.\u00a0Suciu (eds.) Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27-30, 2012, CEUR Workshop Proceedings, vol. 866, pp. 180\u2013195. CEUR-WS.org (2012). https:\/\/ceur-ws.org\/Vol-866\/paper13.pdf"},{"key":"892_CR7","doi-asserted-by":"publisher","unstructured":"Bonifati, A., Fletcher, G., Voigt, H., Yakovets, N.: Querying Graphs. Synthesis Lectures on Data Management. Morgan & Claypool Publishers (2018). https:\/\/doi.org\/10.2200\/S00873ED1V01Y201808DTM051","DOI":"10.2200\/S00873ED1V01Y201808DTM051"},{"issue":"2\u20133","key":"892_CR8","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s00778-019-00558-9","volume":"29","author":"A Bonifati","year":"2020","unstructured":"Bonifati, A., Martens, W., Timm, T.: An analytical study of large SPARQL query logs. VLDB J. 29(2\u20133), 655\u2013679 (2020). https:\/\/doi.org\/10.1007\/s00778-019-00558-9","journal-title":"VLDB J."},{"key":"892_CR9","unstructured":"Calvanese, D., Giacomo, G.D., Lenzerini, M., Vardi, M.Y.: Containment of conjunctive regular path queries with inverse. In: Cohn, A.G., Giunchiglia, F., Selman, B.: (eds.) KR 2000, Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference, Breckenridge, Colorado, USA, April 11-15, 2000, pp. 176\u2013185. Morgan Kaufmann (2000)"},{"issue":"1","key":"892_CR10","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1109\/69.43410","volume":"1","author":"S Ceri","year":"1989","unstructured":"Ceri, S., Gottlob, G., Tanca, L.: What you always wanted to know about datalog (and never dared to ask). IEEE Trans. Knowl. Data Eng. 1(1), 146\u2013166 (1989). https:\/\/doi.org\/10.1109\/69.43410","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"6","key":"892_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"EF Codd","year":"1970","unstructured":"Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377\u2013387 (1970). https:\/\/doi.org\/10.1145\/362384.362685","journal-title":"Commun. ACM"},{"key":"892_CR12","unstructured":"CONSORTIUM, S.: String database \u2013 statistics (2023). https:\/\/string-db.org\/cgi\/about?footer_active_subpage=statistics. Accessed: 13 Oct 2023 16:00"},{"issue":"1","key":"892_CR13","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/321556.321562","volume":"17","author":"DG Corneil","year":"1970","unstructured":"Corneil, D.G., Gotlieb, C.C.: An efficient algorithm for graph isomorphism. J. ACM 17(1), 51\u201364 (1970). https:\/\/doi.org\/10.1145\/321556.321562","journal-title":"J. ACM"},{"key":"892_CR14","doi-asserted-by":"publisher","unstructured":"Cruz, I.F., Mendelzon, A.O., Wood, P.T.: A graphical query language supporting recursion. In: Dayal, U., Traiger, I.L.: (eds.) Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, CA, USA, May 27-29, 1987, pp. 323\u2013330. ACM Press (1987). https:\/\/doi.org\/10.1145\/38713.38749","DOI":"10.1145\/38713.38749"},{"key":"892_CR15","doi-asserted-by":"publisher","unstructured":"DeHaan, D., Tompa, F.W.: Optimal top-down join enumeration. In: C.Y. Chan, B.C. Ooi, A.\u00a0Zhou (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007, pp. 785\u2013796. ACM (2007). https:\/\/doi.org\/10.1145\/1247480.1247567","DOI":"10.1145\/1247480.1247567"},{"key":"892_CR16","doi-asserted-by":"publisher","unstructured":"Deutsch, A., Francis, N., Green, A., Hare, K., Li, B., Libkin, L., Lindaaker, T., Marsault, V., Martens, W., Michels, J., Murlak, F., Plantikow, S., Selmer, P., van Rest, O., Voigt, H., Vrgoc, D., Wu, M., Zemke, F.: Graph pattern matching in GQL and SQL\/PGQ. In: Ives, Z.G., Bonifati, A., Abbadi, A.E.: (eds.) SIGMOD \u201922: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pp. 2246\u20132258. ACM (2022). https:\/\/doi.org\/10.1145\/3514221.3526057","DOI":"10.1145\/3514221.3526057"},{"key":"892_CR17","unstructured":"Deutsch, A., Xu, Y., Wu, M., Lee, V.E.: Tigergraph: A native MPP graph database. CoRR abs\/1901.08248 (2019). http:\/\/arxiv.org\/abs\/1901.08248"},{"key":"892_CR18","doi-asserted-by":"publisher","unstructured":"Fender, P., Moerkotte, G.: A new, highly efficient, and easy to implement top-down join enumeration algorithm. In: Abiteboul, S., B\u00f6hm, K., Koch, C., Tan, K.: (eds.) Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany, pp. 864\u2013875. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/ICDE.2011.5767901","DOI":"10.1109\/ICDE.2011.5767901"},{"issue":"10","key":"892_CR19","doi-asserted-by":"publisher","first-page":"1803","DOI":"10.1109\/TKDE.2011.235","volume":"24","author":"P Fender","year":"2012","unstructured":"Fender, P., Moerkotte, G.: Reassessing top-down join enumeration. IEEE Trans. Knowl. Data Eng. 24(10), 1803\u20131818 (2012). https:\/\/doi.org\/10.1109\/TKDE.2011.235","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"892_CR20","doi-asserted-by":"publisher","unstructured":"Fender, P., Moerkotte, G.: Counter strike: Generic top-down join enumeration for hypergraphs. Proc. VLDB Endow. 6(14), 1822\u20131833 (2013). https:\/\/doi.org\/10.14778\/2556549.2556565. (http:\/\/www.vldb.org\/pvldb\/vol6\/p1822-fender.pdf)","DOI":"10.14778\/2556549.2556565"},{"key":"892_CR21","unstructured":"Feng, X., Jin, G., Chen, Z., Liu, C., Saliho\u011flu, S.: K\u00f9zu Database Management System Source Code. https:\/\/github.com\/kuzudb\/kuzu (2022)"},{"key":"892_CR22","unstructured":"Feng, X., Jin, G., Chen, Z., Liu, C., Saliho\u011flu, S.: K\u00fazu graph database management system. In: CIDR (2023)"},{"key":"892_CR23","unstructured":"Francis, N., Gheerbrant, A., Guagliardo, P., Libkin, L., Marsault, V., Martens, W., Murlak, F., Peterfreund, L., Rogova, A., Vrgoc, D.: A researcher\u2019s digest of GQL (invited talk). In: Geerts, F., Vandevoort, B.: (eds.) 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece, LIPIcs, vol. 255, pp. 1:1\u20131:22 (2023)"},{"issue":"2","key":"892_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1561\/1900000017","volume":"5","author":"TJ Green","year":"2013","unstructured":"Green, T.J., Huang, S.S., Loo, B.T., Zhou, W.: Datalog and recursive query processing. Found. Trends Databases 5(2), 105\u2013195 (2013). https:\/\/doi.org\/10.1561\/1900000017","journal-title":"Found. Trends Databases"},{"key":"892_CR25","doi-asserted-by":"publisher","unstructured":"Gubichev, A., Bedathur, S.J., Seufert, S.: Sparqling kleene: fast property paths in RDF-3X. In: Boncz, P.A., Neumann, T.: (eds.) First International Workshop on Graph Data Management Experiences and Systems, GRADES 2013, co-located with SIGMOD\/PODS 2013, New York, NY, USA, June 24, 2013, p.\u00a014. CWI\/ACM (2013). https:\/\/doi.org\/10.1145\/2484425.2484443. http:\/\/event.cwi.nl\/grades2013\/14-gubichev.pdf","DOI":"10.1145\/2484425.2484443"},{"key":"892_CR26","doi-asserted-by":"publisher","unstructured":"Gubichev, A., Neumann, T.: Exploiting the query structure for efficient join ordering in SPARQL queries. In: Amer-Yahia, S., Christophides, V., Kementsietsidis, A., Garofalakis, M.N., Idreos, S., Leroy, V.: (eds.) Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece, March 24-28, 2014, pp. 439\u2013450. OpenProceedings.org (2014). https:\/\/doi.org\/10.5441\/002\/EDBT.2014.40","DOI":"10.5441\/002\/EDBT.2014.40"},{"key":"892_CR27","doi-asserted-by":"publisher","unstructured":"Han, Y., Wu, Z., Wu, P., Zhu, R., Yang, J., Tan, L.W., Zeng, K., Cong, G., Qin, Y., Pfadler, A., Qian, Z., Zhou, J., Li, J., Cui, B.: Cardinality estimation in dbms: a comprehensive benchmark evaluation. Proc. VLDB Endow. 15(4), 752\u2013765 (2021). https:\/\/doi.org\/10.14778\/3503585.3503586","DOI":"10.14778\/3503585.3503586"},{"key":"892_CR28","doi-asserted-by":"publisher","unstructured":"Hofer, M., Hellmann, S., Dojchinovski, M., Frey, J.: The new dbpedia release cycle: Increasing agility and efficiency in knowledge extraction workflows. In: Blomqvist, E., Groth, P., de\u00a0Boer, V., Pellegrini, T., Alam, M., K\u00e4fer, T., Kieseberg, P., Kirrane, S., Mero\u00f1o-Pe\u00f1uela, A., Pandit, H.J.: (eds.) Semantic Systems. In the Era of Knowledge Graphs - 16th International Conference on Semantic Systems, SEMANTiCS 2020, Amsterdam, The Netherlands, September 7-10, 2020, Proceedings, Lecture Notes in Computer Science, 12378,1\u201318. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-59833-4_1","DOI":"10.1007\/978-3-030-59833-4_1"},{"key":"892_CR29","doi-asserted-by":"publisher","unstructured":"Hogan, A., Riveros, C., Rojas, C., Soto, A.: A worst-case optimal join algorithm for SPARQL. In: Ghidini, C., Hartig, O., Maleshkova, M., Sv\u00e1tek, V., Cruz, I.F., Hogan, A., Song, J., Lefran\u00e7ois, M., Gandon, F.: (eds.) The Semantic Web - ISWC 2019 - 18th International Semantic Web Conference, Auckland, New Zealand, October 26-30, 2019, Proceedings, Part I, Lecture Notes in Computer Science, vol. 11778, pp. 258\u2013275. Springer (2019).https:\/\/doi.org\/10.1007\/978-3-030-30793-6_15","DOI":"10.1007\/978-3-030-30793-6_15"},{"key":"892_CR30","doi-asserted-by":"publisher","unstructured":"Jachiet, L., Genev\u00e9s, P., Gesbert, N., Laya\u00efda, N.: On the optimization of recursive relational queries: Application to graph queries. In: Maier, D., Pottinger, R., Doan, A., Tan, W., Alawini, A., Ngo, H.Q.: (eds.) Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pp. 681\u2013697. ACM (2020).https:\/\/doi.org\/10.1145\/3318464.3380567","DOI":"10.1145\/3318464.3380567"},{"issue":"6","key":"892_CR31","doi-asserted-by":"publisher","first-page":"5485","DOI":"10.1109\/TKDE.2022.3161328","volume":"35","author":"W van Leeuwen","year":"2023","unstructured":"van Leeuwen, W., Fletcher, G., Yakovets, N.: A general cardinality estimation framework for subgraph matching in property graphs. IEEE Trans. Knowl. Data Eng. 35(6), 5485\u20135505 (2023). https:\/\/doi.org\/10.1109\/TKDE.2022.3161328","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"892_CR32","doi-asserted-by":"publisher","first-page":"167","DOI":"10.3233\/SW-140134","volume":"6","author":"J Lehmann","year":"2015","unstructured":"Lehmann, J., Isele, R., Jakob, M., Jentzsch, A., Kontokostas, D., Mendes, P.N., Hellmann, S., Morsey, M., van Kleef, P., Auer, S., Bizer, C.: Dbpedia - A large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web 6(2), 167\u2013195 (2015). https:\/\/doi.org\/10.3233\/SW-140134","journal-title":"Semantic Web"},{"issue":"5","key":"892_CR33","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/S00778-017-0480-7","volume":"27","author":"V Leis","year":"2018","unstructured":"Leis, V., Radke, B., Gubichev, A., Mirchev, A., Boncz, P.A., Kemper, A., Neumann, T.: Query optimization through the looking glass, and what we found running the join order benchmark. VLDB J. 27(5), 643\u2013668 (2018). https:\/\/doi.org\/10.1007\/S00778-017-0480-7","journal-title":"VLDB J."},{"key":"892_CR34","doi-asserted-by":"publisher","unstructured":"Meimaris, M., Papastefanatos, G., Mamoulis, N., Anagnostopoulos, I.: Extended characteristic sets: Graph indexing for SPARQL query optimization. In: 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA, USA, April 19-22, 2017, pp. 497\u2013508. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/ICDE.2017.106","DOI":"10.1109\/ICDE.2017.106"},{"key":"892_CR35","doi-asserted-by":"publisher","unstructured":"Moerkotte, G., Neumann, T.: Dynamic programming strikes back. In: J.T. Wang (ed.) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pp. 539\u2013552. ACM (2008). https:\/\/doi.org\/10.1145\/1376616.1376672","DOI":"10.1145\/1376616.1376672"},{"key":"892_CR36","doi-asserted-by":"publisher","unstructured":"Na, I., Moon, Y., Yi, I., Whang, K., Hyun, S.J.: Regular path query evaluation sharing a reduced transitive closure based on graph reduction. In: 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022, pp. 1675\u20131686. IEEE (2022). https:\/\/doi.org\/10.1109\/ICDE53745.2022.00171","DOI":"10.1109\/ICDE53745.2022.00171"},{"key":"892_CR37","unstructured":"Neumann, T.: Efficient generation and execution of dag-structured query graphs. Ph.D. thesis, University of Mannheim, Germany (2005). http:\/\/bibserv7.bib.uni-mannheim.de\/madoc\/volltexte\/2005\/1089\/index.html"},{"key":"892_CR38","unstructured":"Neumann, T., Freitag, M.J.: Umbra: A disk-based system with in-memory performance. In: 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. www.cidrdb.org (2020). http:\/\/cidrdb.org\/cidr2020\/papers\/p29-neumann-cidr20.pdf"},{"key":"892_CR39","doi-asserted-by":"publisher","unstructured":"Neumann, T., Moerkotte, G.: Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins. In: Abiteboul, S., B\u00f6hm, K., Koch, C., Tan, K.: (eds.) Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany, pp. 984\u2013994. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/ICDE.2011.5767868","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"892_CR40","doi-asserted-by":"publisher","unstructured":"Nguyen, D., Aref, M., Bravenboer, M., Kollias, G., Ngo, H.Q., R\u00e9, C., Rudra, A.: Join processing for graph patterns: An old dog with new tricks. In: Proceedings of the GRADES\u201915, GRADES\u201915. Association for Computing Machinery, New York, NY, USA (2015). https:\/\/doi.org\/10.1145\/2764947.2764948","DOI":"10.1145\/2764947.2764948"},{"key":"892_CR41","unstructured":"Ono, K., Lohman, G.M.: Measuring the complexity of join enumeration in query optimization. In: Proceedings of the Sixteenth International Conference on Very Large Databases, p. 314 \u2013325. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1990)"},{"key":"892_CR42","doi-asserted-by":"publisher","unstructured":"Patel, J.M., Deshmukh, H., Zhu, J., Potti, N., Zhang, Z., Spehlmann, M., Memisoglu, H., Saurabh, S.: Quickstep: A data platform based on the scaling-up approach. Proc. VLDB Endow. 11(6), 663\u2013676 (2018). https:\/\/doi.org\/10.14778\/3184470.3184471. (http:\/\/www.vldb.org\/pvldb\/vol11\/p663-patel.pdf)","DOI":"10.14778\/3184470.3184471"},{"key":"892_CR43","unstructured":"Raasveldt, M., Muehleisen, H.: DuckDB (2023). https:\/\/github.com\/duckdb\/duckdb"},{"issue":"1","key":"892_CR44","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00224-016-9676-2","volume":"61","author":"JL Reutter","year":"2017","unstructured":"Reutter, J.L., Romero, M., Vardi, M.Y.: Regular queries on graph databases. Theory Comput. Syst. 61(1), 31\u201383 (2017). https:\/\/doi.org\/10.1007\/s00224-016-9676-2","journal-title":"Theory Comput. Syst."},{"key":"892_CR45","doi-asserted-by":"publisher","unstructured":"Rodriguez, M.A.: The gremlin graph traversal machine and language (invited talk). In: Cheney, J., Neumann, T.: (eds.) Proceedings of the 15th Symposium on Database Programming Languages, Pittsburgh, PA, USA, October 25-30, 2015, pp. 1\u201310. ACM (2015). https:\/\/doi.org\/10.1145\/2815072.2815073","DOI":"10.1145\/2815072.2815073"},{"key":"892_CR46","doi-asserted-by":"publisher","unstructured":"Szklarczyk, D., Kirsch, R., Koutrouli, M., Nastou, K., Mehryary, F., Hachilif, R., Gable, A.L., Fang, T., Doncheva, N., Pyysalo, S., Bork, P., Jensen, L., vonMering, C.: The STRING database in 2023: protein-protein association networks and functional enrichment analyses for any sequenced genome of interest. Nucleic Acids Research 51(D1), D638\u2013D646 (2022). https:\/\/doi.org\/10.1093\/nar\/gkac1000","DOI":"10.1093\/nar\/gkac1000"},{"issue":"5\u20136","key":"892_CR47","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1017\/S1471068416000405","volume":"16","author":"KT Tekle","year":"2016","unstructured":"Tekle, K.T., Liu, Y.A.: Precise complexity guarantees for pointer analysis via datalog with extensions. Theory Pract. Log. Program. 16(5\u20136), 916\u2013932 (2016). https:\/\/doi.org\/10.1017\/S1471068416000405","journal-title":"Theory Pract. Log. Program."},{"key":"892_CR48","doi-asserted-by":"publisher","unstructured":"Tetzel, F., Voigt, H., Paradies, M., Lehner, W.: An analysis of the feasibility of graph compression techniques for indexing regular path queries. In: Boncz, P.A., Larriba-Pey, J.L.: (eds.) Proceedings of the Fifth International Workshop on Graph Data-management Experiences & Systems, GRADES@SIGMOD\/PODS 2017, Chicago, IL, USA, May 14 - 19, 2017, pp. 11:1\u201311:6. ACM (2017). https:\/\/doi.org\/10.1145\/3078447.3078458","DOI":"10.1145\/3078447.3078458"},{"key":"892_CR49","doi-asserted-by":"publisher","unstructured":"Willsey, M., Nandi, C., Wang, Y.R., Flatt, O., Tatlock, Z., Panchekha, P.: Egg: Fast and extensible equality saturation. Proc. ACM Program. Lang. 5(POPL) (2021). https:\/\/doi.org\/10.1145\/3434304","DOI":"10.1145\/3434304"},{"key":"892_CR50","unstructured":"ten Wolde, D., Singh, T., Sz\u00e1rnyas, G., Boncz, P.A.: Duckpgq: Efficient property graph queries in an analytical RDBMS. In: 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8-11, 2023. www.cidrdb.org (2023). https:\/\/www.cidrdb.org\/cidr2023\/papers\/p66-wolde.pdf"},{"key":"892_CR51","doi-asserted-by":"publisher","unstructured":"Yakovets, N., Godfrey, P., Gryz, J.: Query planning for evaluating SPARQL property paths. In: \u00d6zcan, F., Koutrika, G., Madden, S.: (eds.) Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pp. 1875\u20131889. ACM (2016). https:\/\/doi.org\/10.1145\/2882903.2882944","DOI":"10.1145\/2882903.2882944"},{"key":"892_CR52","unstructured":"Ymous, A.: Optimizing Navigational Queries Online Appendix (2023). https:\/\/github.com\/ymous5380\/ongq"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00892-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-024-00892-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00892-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T07:31:56Z","timestamp":1744270316000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-024-00892-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,21]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["892"],"URL":"https:\/\/doi.org\/10.1007\/s00778-024-00892-7","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,21]]},"assertion":[{"value":"22 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"16"}}