{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T16:37:24Z","timestamp":1773160644595,"version":"3.50.1"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,3,20]],"date-time":"2016-03-20T00:00:00Z","timestamp":1458432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["MA 4938\/2-1"],"award-info":[{"award-number":["MA 4938\/2-1"]}]},{"name":"Millennium Nucleus Center for Semantic Web Research","award":["NC120004"],"award-info":[{"award-number":["NC120004"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["G049165, J015377 and M025268"],"award-info":[{"award-number":["G049165, J015377 and M025268"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,5,4]]},"abstract":"<jats:p>Graph databases have received much attention as of late due to numerous applications in which data is naturally viewed as a graph; these include social networks, RDF and the Semantic Web, biological databases, and many others. There are many proposals for query languages for graph databases that mainly fall into two categories. One views graphs as a particular kind of relational data and uses traditional relational mechanisms for querying. The other concentrates on querying the topology of the graph. These approaches, however, lack the ability to<jats:italic>combine<\/jats:italic>data and topology, which would allow queries asking how data changes along paths and patterns enveloping it.<\/jats:p><jats:p>In this article, we present a comprehensive study of languages that enable such combination of data and topology querying. These languages come in two flavors. The first follows the standard approach of path queries, which specify how labels of edges change along a path, but now we extend them with ways of specifying how both labels and data change. From the complexity point of view, the right type of formalisms are subclasses of register automata. These, however, are not well suited for querying. To overcome this, we develop several types of extended regular expressions to specify paths with data and study their querying power and complexity. The second approach adopts the popular XML language XPath and extends it from XML documents to graphs. Depending on the exact set of allowed features, we have a family of languages, and our study shows that it includes efficient and highly expressive formalisms for querying both the structure of the data and the data itself.<\/jats:p>","DOI":"10.1145\/2850413","type":"journal-article","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T18:56:20Z","timestamp":1458586580000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":75,"title":["Querying Graphs with Data"],"prefix":"10.1145","volume":"63","author":[{"given":"Leonid","family":"Libkin","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bayreuth, Bayreuth, Germany"}]},{"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[{"name":"PUC Chile and Center for Semantic Web Research, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2016,3,20]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley. S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132869"},{"key":"e_1_2_2_3_1","first-page":"58","article-title":"1999. Regular path queries with constraints","volume":"3","author":"Abiteboul S.","year":"1999","unstructured":"S. Abiteboul and V. Vianu . 1999. Regular path queries with constraints . J. Comput. Syst. Sci. 3 , 58 ( 1999 ), 428--452. S. Abiteboul and V. Vianu. 1999. Regular path queries with constraints. J. Comput. Syst. Sci. 3, 58 (1999), 428--452.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"A. V. Aho. 1990. Handbook of Theoretical Computer Science. 255--300 pages. A. V. Aho. 1990. Handbook of Theoretical Computer Science. 255--300 pages.","DOI":"10.1016\/B978-0-444-88071-0.50010-2"},{"key":"e_1_2_2_5_1","volume-title":"A modal perspective on path constraints. J. Log. Comput. 13, 6","author":"Alechina N.","year":"2003","unstructured":"N. Alechina , S. Demri , and M. de Rijke . 2003. A modal perspective on path constraints. J. Log. Comput. 13, 6 ( 2003 ), 939--956. N. Alechina, S. Demri, and M. de Rijke. 2003. A modal perspective on path constraints. J. Log. Comput. 13, 6 (2003), 939--956."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.3.325"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"H. Andr\u00e9ka I. N\u00e9meti and I. Sain. 2001. Algebraic logic. In Handbook of Philosophical Logic (2nd ed.). Vol. 2. Springer. H. Andr\u00e9ka I. N\u00e9meti and I. Sain. 2001. Algebraic logic. In Handbook of Philosophical Logic (2nd ed.). Vol. 2. Springer.","DOI":"10.1007\/978-94-017-0452-6_3"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_2_2_9_1","volume-title":"32th ACM Symposium on Principles of Database Systems (PODS\u201913)","author":"Barcel\u00f3 P.","year":"2013","unstructured":"P. Barcel\u00f3 . 2013 . Querying graph databases . In 32th ACM Symposium on Principles of Database Systems (PODS\u201913) . P. Barcel\u00f3. 2013. Querying graph databases. In 32th ACM Symposium on Principles of Database Systems (PODS\u201913)."},{"key":"e_1_2_2_10_1","volume-title":"27th Annual IEEE Symposium on Logic in Computer Science (LICS\u201912)","author":"Barcel\u00f3 P.","unstructured":"P. Barcel\u00f3 , D. Figueira , and L. Libkin . 2012a. Graph logics with rational relations and the generalized intersection problem . In 27th Annual IEEE Symposium on Logic in Computer Science (LICS\u201912) . P. Barcel\u00f3, D. Figueira, and L. Libkin. 2012a. Graph logics with rational relations and the generalized intersection problem. In 27th Annual IEEE Symposium on Logic in Computer Science (LICS\u201912)."},{"key":"e_1_2_2_11_1","first-page":"4","article-title":"2012b. Expressive languages for path queries over graph-structured data","volume":"38","author":"Barcel\u00f3 P.","year":"2012","unstructured":"P. Barcel\u00f3 , L. Libkin , A. W. Lin , and P. T. Wood . 2012b. Expressive languages for path queries over graph-structured data . ACM TODS 38 , 4 ( 2012 ), 31:1--31:46. P. Barcel\u00f3, L. Libkin, A. W. Lin, and P. T. Wood. 2012b. Expressive languages for path queries over graph-structured data. ACM TODS 38, 4 (2012), 31:1--31:46.","journal-title":"ACM TODS"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870103.1870107"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559905"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW). 180--195","author":"Barcel\u00f3 P.","unstructured":"P. Barcel\u00f3 , J. P\u00e9rez , and J. L. Reutter . 2012c. Relative expressiveness of nested regular expressions . In Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW). 180--195 . P. Barcel\u00f3, J. P\u00e9rez, and J. L. Reutter. 2012c. Relative expressiveness of nested regular expressions. In Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW). 180--195."},{"key":"e_1_2_2_15_1","volume-title":"ACM Symposium on Principles of Database Systems (PODS\u201915)","author":"Barcel\u00f3 P.","unstructured":"P. Barcel\u00f3 , R. Pichler , and S. Skritek . 2015. Efficient evaluation and approximation of well-designed pattern trees . In ACM Symposium on Principles of Database Systems (PODS\u201915) . 131--144. P. Barcel\u00f3, R. Pichler, and S. Skritek. 2015. Efficient evaluation and approximation of well-designed pattern trees. In ACM Symposium on Principles of Database Systems (PODS\u201915). 131--144."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.25.1"},{"key":"e_1_2_2_18_1","first-page":"4","article-title":"2011. Two-variable logic on words with data","volume":"12","author":"Bojanczyk M.","year":"2011","unstructured":"M. Bojanczyk , C. David , A. Muscholl , T. Schwentick , and L. Segoufin . 2011. Two-variable logic on words with data . ACM TOCL 12 , 4 ( 2011 ), 27:1--27:26. M. Bojanczyk, C. David, A. Muscholl, T. Schwentick, and L. Segoufin. 2011. Two-variable logic on words with data. ACM TOCL 12, 4 (2011), 27:1--27:26.","journal-title":"ACM TOCL"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516515"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989731"},{"key":"e_1_2_2_21_1","volume-title":"International Conference on Concurrency Theory (CONCUR). 248--261","author":"Bouyer P.","unstructured":"P. Bouyer , A. Petit , and D. Th\u00e9rien . 2001. An algebraic characterization of data and timed languages . In International Conference on Concurrency Theory (CONCUR). 248--261 . P. Bouyer, A. Petit, and D. Th\u00e9rien. 2001. An algebraic characterization of data and timed languages. In International Conference on Concurrency Theory (CONCUR). 248--261."},{"key":"e_1_2_2_22_1","volume-title":"7th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201900)","author":"Calvanese D.","unstructured":"D. Calvanese , G. De Giacomo , M. Lenzerini , and M. Y. Vardi . 2000. Containment of conjunctive regular path queries with inverse . In 7th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201900) . 176--185. D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. 2000. Containment of conjunctive regular path queries with inverse. In 7th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201900). 176--185."},{"key":"e_1_2_2_23_1","volume-title":"12th International Symposium on Database Programming Languages (DBLP). 18--35","author":"Calvanese D.","unstructured":"D. Calvanese , G. De Giacomo , M. Lenzerini , and M. Y. Vardi . 2009. An automata-theoretic approach to regular XPath . In 12th International Symposium on Database Programming Languages (DBLP). 18--35 . D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. 2009. An automata-theoretic approach to regular XPath. In 12th International Symposium on Database Programming Languages (DBLP). 18--35."},{"key":"e_1_2_2_24_1","unstructured":"S. Cassidy. 2003. Generalizing XPath for directed graphs. In Extreme Markup Languages. S. Cassidy. 2003. Generalizing XPath for directed graphs. In Extreme Markup Languages."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01383878"},{"key":"e_1_2_2_26_1","volume-title":"9th ACM Symposium on Principles of Database Systems (PODS\u201990)","author":"Consens M.","unstructured":"M. Consens and A. O. Mendelzon . 1990. GraphLog: A visual formalism for real life recursion . In 9th ACM Symposium on Principles of Database Systems (PODS\u201990) . 404--416. M. Consens and A. O. Mendelzon. 1990. GraphLog: A visual formalism for real life recursion. In 9th ACM Symposium on Principles of Database Systems (PODS\u201990). 404--416."},{"key":"e_1_2_2_27_1","volume-title":"ACM Special Interest Group on Management of Data 1987 Annual Conference (SIGMOD\u201987)","author":"Cruz I.","unstructured":"I. Cruz , A. O. Mendelzon , and P. Wood . 1987. A graphical query language supporting recursion . In ACM Special Interest Group on Management of Data 1987 Annual Conference (SIGMOD\u201987) . 323--330. I. Cruz, A. O. Mendelzon, and P. Wood. 1987. A graphical query language supporting recursion. In ACM Special Interest Group on Management of Data 1987 Annual Conference (SIGMOD\u201987). 323--330."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.08.003"},{"key":"e_1_2_2_30_1","volume-title":"8th International Workshop on Database Programming Languages (DBPL\u201901)","author":"Deutsch A.","unstructured":"A. Deutsch and V. Tannen . 2001. Optimization properties for classes of conjunctive regular path queries . In 8th International Workshop on Database Programming Languages (DBPL\u201901) . 21--39. A. Deutsch and V. Tannen. 2001. Optimization properties for classes of conjunctive regular path queries. In 8th International Workshop on Database Programming Languages (DBPL\u201901). 21--39."},{"key":"e_1_2_2_31_1","unstructured":"Dex. 2013. DEX query language Sparsity Technologies. Retrieved from http:\/\/www.sparsity-technologies.com\/dex.php. Dex. 2013. DEX query language Sparsity Technologies. Retrieved from http:\/\/www.sparsity-technologies.com\/dex.php."},{"key":"e_1_2_2_32_1","unstructured":"Facebook. 2014. Graph Search. Retrieved from https:\/\/www.facebook.com\/about\/graphsearch. Facebook. 2014. Graph Search. Retrieved from https:\/\/www.facebook.com\/about\/graphsearch."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274578"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559827"},{"key":"e_1_2_2_36_1","volume-title":"14th International Conference on Database Theory (ICDT). 197--207","author":"Fletcher G. H. L.","unstructured":"G. H. L. Fletcher , M. Gyssens , D. Leinders , J. Van den Bussche, D. Van Gucht, S. Vansummeren, and Y. Wu. 2011. Relative expressive power of navigational querying on graphs . In 14th International Conference on Database Theory (ICDT). 197--207 . G. H. L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, and Y. Wu. 2011. Relative expressive power of navigational querying on graphs. In 14th International Conference on Database Theory (ICDT). 197--207."},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). 139--148","author":"Florescu D.","unstructured":"D. Florescu , A. Y. Levy , and D. Suciu . 1998. Query containment for conjunctive queries with regular expressions . In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). 139--148 . D. Florescu, A. Y. Levy, and D. Suciu. 1998. Query containment for conjunctive queries with regular expressions. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). 139--148."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"key":"e_1_2_2_40_1","unstructured":"Gremlin 2013. Gremlin Language. Retrieved from https:\/\/github.com\/tinkerpop\/gremlin\/wiki. Gremlin 2013. Gremlin Language. Retrieved from https:\/\/github.com\/tinkerpop\/gremlin\/wiki."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.009"},{"key":"e_1_2_2_42_1","unstructured":"S. Harris and A. Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. http:\/\/www.w3.org\/ TR\/sparql11-query\/. (March 2013). S. Harris and A. Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. http:\/\/www.w3.org\/ TR\/sparql11-query\/. (March 2013)."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.3233\/FUN-2006-69304","article-title":"2006. Regular expressions for languages over infinite alphabets","volume":"69","author":"Kaminski M.","year":"2006","unstructured":"M. Kaminski and T. Tan . 2006. Regular expressions for languages over infinite alphabets . Fundamenta Informaticae 69 , 3 ( 2006 ), 301--318. M. Kaminski and T. Tan. 2006. Regular expressions for languages over infinite alphabets. Fundamenta Informaticae 69, 3 (2006), 301--318.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"M. Kaminski and T. Tan. 2008. Tree automata over infinite alphabets. In Pillars of Computer Science. 386--423. M. Kaminski and T. Tan. 2008. Tree automata over infinite alphabets. In Pillars of Computer Science. 386--423.","DOI":"10.1007\/978-3-540-78127-1_21"},{"key":"e_1_2_2_46_1","unstructured":"M. Kay. 2004. XPath 2.0 Programmer\u2019s Reference. Wrox. M. Kay. 2004. XPath 2.0 Programmer\u2019s Reference. Wrox."},{"key":"e_1_2_2_47_1","volume-title":"Proceedings, Part I (ISWC\u201915)","author":"Kostylev E. V.","unstructured":"E. V. Kostylev , J. L. Reutter , M. Romero , and D. Vrgo\u010d . 2015b. SPARQL with property paths. In The Semantic Web - 14th International Semantic Web Conference , Proceedings, Part I (ISWC\u201915) . 3--18. E. V. Kostylev, J. L. Reutter, M. Romero, and D. Vrgo\u010d. 2015b. SPARQL with property paths. In The Semantic Web - 14th International Semantic Web Conference, Proceedings, Part I (ISWC\u201915). 3--18."},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI). 1525--1531","author":"Kostylev E. V.","unstructured":"E. V. Kostylev , J. L. Reutter , and D. Vrgo\u010d . 2015a. XPath for DL ontologies . In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI). 1525--1531 . E. V. Kostylev, J. L. Reutter, and D. Vrgo\u010d. 2015a. XPath for DL ontologies. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI). 1525--1531."},{"key":"e_1_2_2_49_1","doi-asserted-by":"crossref","unstructured":"G. M. Kuper L. Libkin and J. Paredaens (Eds.). 2000. Constraint Databases. Springer. G. M. Kuper L. Libkin and J. Paredaens (Eds.). 2000. Constraint Databases. Springer.","DOI":"10.1007\/978-3-662-04031-7"},{"key":"e_1_2_2_50_1","volume-title":"Model checking propositional dynamic logic with all extras. J. Appl. Logic 4, 1","author":"Lange M.","year":"2006","unstructured":"M. Lange . 2006. Model checking propositional dynamic logic with all extras. J. Appl. Logic 4, 1 ( 2006 ), 39--49. M. Lange. 2006. Model checking propositional dynamic logic with all extras. J. Appl. Logic 4, 1 (2006), 39--49."},{"key":"e_1_2_2_51_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer . L. Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_2_52_1","unstructured":"L. Libkin. 2014. Certain answers as objects and knowledge. In Principles of Knowledge Representation and Reasoning (KR\u201914). 328--337. L. Libkin. 2014. Certain answers as objects and knowledge. In Principles of Knowledge Representation and Reasoning (KR\u201914). 328--337."},{"key":"e_1_2_2_53_1","volume-title":"Joint 2013 EDBT\/ICDT Conferences (ICDT'13)","author":"Libkin L.","unstructured":"L. Libkin , W. Martens , and D. Vrgo\u010d . 2013a. Querying graph databases with XPath . In Joint 2013 EDBT\/ICDT Conferences (ICDT'13) . L. Libkin, W. Martens, and D. Vrgo\u010d. 2013a. Querying graph databases with XPath. In Joint 2013 EDBT\/ICDT Conferences (ICDT'13)."},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS).","author":"Libkin L.","unstructured":"L. Libkin , J. L. Reutter , and D. Vrgo\u010d . 2013b. TriAL for RDF: Adapting graph query languages for RDF data . In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). L. Libkin, J. L. Reutter, and D. Vrgo\u010d. 2013b. TriAL for RDF: Adapting graph query languages for RDF data. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)."},{"key":"e_1_2_2_55_1","doi-asserted-by":"crossref","unstructured":"L. Libkin and D. Vrgo\u010d. 2012a. Regular expressions for data words. In Logic for Programming Artificial Intelligence and Reasoning (LPAR). 274--288. L. Libkin and D. Vrgo\u010d. 2012a. Regular expressions for data words. In Logic for Programming Artificial Intelligence and Reasoning (LPAR). 274--288.","DOI":"10.1007\/978-3-642-28717-6_22"},{"key":"e_1_2_2_56_1","volume-title":"15th International Conference on Database Theory (ICDT). 74--85","author":"Libkin L.","unstructured":"L. Libkin and D. Vrgo\u010d . 2012b. Regular path queries on graphs with data . In 15th International Conference on Database Theory (ICDT). 74--85 . L. Libkin and D. Vrgo\u010d. 2012b. Regular path queries on graphs with data. In 15th International Conference on Database Theory (ICDT). 74--85."},{"key":"e_1_2_2_57_1","volume-title":"Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 101--112","author":"Losemann K.","unstructured":"K. Losemann and W. Martens . 2012. The complexity of evaluating path expressions in SPARQL . In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 101--112 . K. Losemann and W. Martens. 2012. The complexity of evaluating path expressions in SPARQL. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 101--112."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45206-5_13"},{"key":"e_1_2_2_59_1","volume-title":"929--959","author":"Marx M.","year":"2005","unstructured":"M. Marx . 2005. Conditional X Path . ACM Trans . Database Syst . 30, 4 ( 2005 ), 929--959 . M. Marx. 2005. Conditional XPath. ACM Trans. Database Syst. 30, 4 (2005), 929--959."},{"key":"e_1_2_2_60_1","unstructured":"Neo4j 2013. Neo4j The Graph Database. Retrieved from http:\/\/www.neo4j.org\/. Neo4j 2013. Neo4j The Graph Database. Retrieved from http:\/\/www.neo4j.org\/."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013560.1013562"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2010.01.002"},{"key":"e_1_2_2_64_1","unstructured":"J. L. Reutter. 2013a. Containment of Nested Regular Expressions. CoRR abs\/1304.2637. (2013). J. L. Reutter. 2013a. Containment of Nested Regular Expressions. CoRR abs\/1304.2637. (2013)."},{"key":"e_1_2_2_66_1","volume-title":"Proceedings, Part I (ISWC\u201915)","author":"Reutter J. L.","unstructured":"J. L. Reutter , A. Soto , and D. Vrgo\u010d . 2015. Recursion in SPARQL. In The Semantic Web - 14th International Semantic Web Conference , Proceedings, Part I (ISWC\u201915) . 19--35. J. L. Reutter, A. Soto, and D. Vrgo\u010d. 2015. Recursion in SPARQL. In The Semantic Web - 14th International Semantic Web Conference, Proceedings, Part I (ISWC\u201915). 19--35."},{"key":"e_1_2_2_67_1","volume-title":"25th International Conference on Data Engineering (ICDE\u201909)","author":"Ronen R.","unstructured":"R. Ronen and O. Shmueli . 2009. SoQL: A language for querying and creating data in social networks . In 25th International Conference on Data Engineering (ICDE\u201909) . 1595--1602. R. Ronen and O. Shmueli. 2009. SoQL: A language for querying and creating data in social networks. In 25th International Conference on Data Engineering (ICDE\u201909). 1595--1602."},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00105-X"},{"key":"e_1_2_2_69_1","volume-title":"6th European Semantic Web Conference (ESWC\u201909)","author":"San Mart\u00edn M.","unstructured":"M. San Mart\u00edn and C. Gutierrez . 2009. Representing, querying and transforming social networks with RDF\/SPARQL . In 6th European Semantic Web Conference (ESWC\u201909) . 293--307. M. San Mart\u00edn and C. Gutierrez. 2009. Representing, querying and transforming social networks with RDF\/SPARQL. In 6th European Semantic Web Conference (ESWC\u201909). 293--307."},{"key":"e_1_2_2_70_1","doi-asserted-by":"crossref","unstructured":"L. Segoufin. 2006. Automata and logics for words and trees over an infinite alphabet. In Computer Science Logic (CSL). 41--57. L. Segoufin. 2006. Automata and logics for words and trees over an infinite alphabet. In Computer Science Logic (CSL). 41--57.","DOI":"10.1007\/11874683_3"},{"key":"e_1_2_2_71_1","volume-title":"Static analysis of XML processing with data values. SIGMOD Record 36, 1","author":"Segoufin L.","year":"2007","unstructured":"L. Segoufin . 2007. Static analysis of XML processing with data values. SIGMOD Record 36, 1 ( 2007 ), 31--38. L. Segoufin. 2007. Static analysis of XML processing with data values. SIGMOD Record 36, 1 (2007), 31--38."},{"key":"e_1_2_2_72_1","doi-asserted-by":"crossref","unstructured":"A. Tarski and S. Givant. 1987. A Formalization of Set Theory Without Variables. AMS. A. Tarski and S. Givant. 1987. A Formalization of Set Theory Without Variables. AMS.","DOI":"10.1090\/coll\/041"},{"key":"e_1_2_2_73_1","volume-title":"25th ACM Symposium on Principles of Database Systems (PODS\u201906)","author":"Cate B.","year":"2006","unstructured":"B. ten Cate . 2006 . The expressivity of XPath with transitive closure . In 25th ACM Symposium on Principles of Database Systems (PODS\u201906) . 328--337. B. ten Cate. 2006. The expressivity of XPath with transitive closure. In 25th ACM Symposium on Principles of Database Systems (PODS\u201906). 328--337."},{"key":"e_1_2_2_74_1","first-page":"2","article-title":"ten Cate and M. Marx. 2007. Navigational XPath: Calculus and algebra","volume":"36","author":"B","year":"2007","unstructured":"B . ten Cate and M. Marx. 2007. Navigational XPath: Calculus and algebra . Sigmod Record 36 , 2 ( 2007 ), 19--26. B. ten Cate and M. Marx. 2007. Navigational XPath: Calculus and algebra. Sigmod Record 36, 2 (2007), 19--26.","journal-title":"Sigmod Record"},{"key":"e_1_2_2_76_1","volume-title":"Query languages for graph databases. Sigmod Record 41, 1","author":"Wood P. T.","year":"2012","unstructured":"P. T. Wood . 2012. Query languages for graph databases. Sigmod Record 41, 1 ( 2012 ), 50--60. P. T. Wood. 2012. Query languages for graph databases. Sigmod Record 41, 1 (2012), 50--60."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2850413","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2850413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:27Z","timestamp":1750225407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2850413"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,20]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,4]]}},"alternative-id":["10.1145\/2850413"],"URL":"https:\/\/doi.org\/10.1145\/2850413","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,20]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}