{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T09:56:08Z","timestamp":1779011768153,"version":"3.51.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>Graph databases are enjoying enormous popularity, through both their RDF and Property Graphs (PG) incarnations, in a variety of applications. To query graphs, query languages provide structured, as well as unstructured primitives. While structured queries allow expressing precise information needs, they are unsuited for exploring unfamiliar datasets, as they require prior knowledge of the schema and structure of the dataset. Prior research on keyword search in graph databases do not suffer from this limitation. However, keyword queries do not allow expressing precise search criteria when users do know some.<\/jats:p>\n          <jats:p>\n            This tutorial (1.5 hours) builds a continuum between structured graph querying through languages such as SPARQL and GPML, a recently proposed standard for PG querying, on one hand, and graph keyword search, on the other hand. In this space between querying and information retrieval, we analyze the features of modern query languages that go toward unstructured search, discuss their strength, limitations, and compare their computational complexity. In particular, we focus on (\n            <jats:italic toggle=\"yes\">i<\/jats:italic>\n            ) lessons learned from the rich literature of graph keyword search, in particular with respect to result scoring; (\n            <jats:italic toggle=\"yes\">ii<\/jats:italic>\n            ) language mechanisms for integrating\n            <jats:italic toggle=\"yes\">both<\/jats:italic>\n            complex structured querying and powerful methods to search for connections users do not know in advance. We conclude by discussing the open challenges and future work directions.\n          <\/jats:p>","DOI":"10.14778\/3611540.3611577","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T11:32:37Z","timestamp":1694777557000},"page":"3886-3889","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Full-Power Graph Querying: State of the Art and Challenges"],"prefix":"10.14778","volume":"16","author":[{"given":"Ioana","family":"Manolescu","sequence":"first","affiliation":[{"name":"Inria and IPP, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhulika","family":"Mohanty","sequence":"additional","affiliation":[{"name":"Inria and IPP, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"BANKS: Browsing and Keyword Searching in Relational Databases. In VLDB.","author":"Aditya B.","year":"2002","unstructured":"B. Aditya, Gaurav Bhalotia, Soumen Chakrabarti, Arvind Hulgeri, Charuta Nakhe, Parag, and S. Sudarshan. 2002. BANKS: Browsing and Keyword Searching in Relational Databases. In VLDB."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Christian Aebeloe Gabriela Montoya Vinay Setty and Katja Hose. 2018. Discovering Diversified Paths in Knowledge Bases. In VLDB.","DOI":"10.14778\/3229863.3236245"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Sanjay Agrawal Surajit Chaudhuri and Gautam Das. 2002. DBXplorer: A System for Keyword-Based Search over Relational Databases. In ICDE.","DOI":"10.1145\/564780.564782"},{"key":"e_1_2_1_4_1","volume-title":"St\u00e9phane Horel, Ioana Manolescu, and Youssr Youssef.","author":"Anadiotis Angelos-Christos","year":"2021","unstructured":"Angelos-Christos Anadiotis, Oana Balalau, Th\u00e9o Bouganim, Francesco Chimienti, Helena Galhardas, Mhd Yamen Haddad, St\u00e9phane Horel, Ioana Manolescu, and Youssr Youssef. 2021. Empowering Investigative Journalism with Graph-based Heterogeneous Data Management. In Bulletin of the Technical Committee on Data Engineering. IEEE Computer Society."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Angelos Christos Anadiotis Ioana Manolescu and Madhulika Mohanty. 2023. Integrating Connection Search in Graph Queries. In ICDE.","DOI":"10.1109\/ICDE55515.2023.00200"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Angelos Christos Anadiotis Ioana Manolescu and Madhulika Mohanty. 2023. Integrating Connection Search in Graph Queries. Technical Report.","DOI":"10.1109\/ICDE55515.2023.00200"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Angelos Christos Anadiotis Ioana Manolescu and Madhulika Mohanty. 2023. More power to SPARQL: From paths to trees. In ESWC.","DOI":"10.1007\/978-3-031-43458-7_6"},{"key":"e_1_2_1_8_1","volume-title":"Stephane Horel, Ioana Manolescu, and Youssr Youssef.","author":"Anadiotis Angelos-Christos G.","year":"2021","unstructured":"Angelos-Christos G. Anadiotis, Oana Balalau, Theo Bouganim, Francesco Chimienti, Helena Galhardas, Mhd Yamen Haddad, Stephane Horel, Ioana Manolescu, and Youssr Youssef. 2021. Discovering Conflicts of Interest across Heterogeneous Data Sources with ConnectionLens. In CIKM."},{"key":"e_1_2_1_9_1","volume-title":"Ioana Manolescu, Tayeb Merabti, and Jingmao You.","author":"Anadiotis Angelos-Christos G.","year":"2022","unstructured":"Angelos-Christos G. Anadiotis, Oana Balalau, Catarina Concei\u00e7\u00e3o, Helena Galhardas, Mhd Yamen Haddad, Ioana Manolescu, Tayeb Merabti, and Jingmao You. 2022. Graph integration of structured, semistructured and unstructured data for data journalism. In Inf. Syst."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Peter A. Boncz George H. L. Fletcher Claudio Gutierrez Tobias Lindaaker Marcus Paradies Stefan Plantikow Juan F. Sequeda Oskar van Rest and Hannes Voigt. 2018. G-CORE: A Core for Future Graph Query Languages. In SIGMOD. ACM.","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_11_1","volume-title":"Sequeda","author":"Arenas Marcelo","year":"2021","unstructured":"Marcelo Arenas, Claudio Gutierrez, and Juan F. Sequeda. 2021. Querying in the Age of Graph Databases and Knowledge Graphs. In SIGMOD."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Andrey Balmin Vagelis Hristidis and Yannis Papakonstantinou. 2004. ObjectRank: Authority-Based Keyword Search in Databases. In VLDB.","DOI":"10.1016\/B978-012088469-8.50051-6"},{"key":"e_1_2_1_13_1","unstructured":"Gaurav Bhalotia Arvind Hulgeri Charuta Nakhe Soumen Chakrabarti and S. Sudarshan. 2002. Keyword Searching and Browsing in Databases using BANKS. In ICDE."},{"key":"e_1_2_1_14_1","volume-title":"Minh-Huong Le Nguyen, and Ioana Manolescu","author":"Chanial Camille","year":"2018","unstructured":"Camille Chanial, R\u00e9douane Dziri, Helena Galhardas, Julien Leblay, Minh-Huong Le Nguyen, and Ioana Manolescu. 2018. ConnectionLens: Finding Connections Across Heterogeneous Data Sources (demonstration). In PVLDB."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.228"},{"key":"e_1_2_1_16_1","volume-title":"Edleno Silva de Moura, and Rosiane Rodrigues","author":"de Oliveira Pericles","year":"2018","unstructured":"Pericles de Oliveira, Altigran S. da Silva, Edleno Silva de Moura, and Rosiane Rodrigues. 2018. Match-Based Candidate Network Generation for Keyword Queries over Relational Databases. In ICDE."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Alin Deutsch Nadime Francis Alastair Green Keith Hare Bei Li Leonid Libkin Tobias Lindaaker Victor Marsault Wim Martens Jan Michels Stefan Plantikow Petra Selmer Oskar van Rest Hannes Voigt Domagoj Vrgoc Mingxi Wu and Fred Zemke. 2022. Graph Pattern Matching in GQL and SQL\/PGQ. In SIGMOD.","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_2_1_18_1","volume-title":"Shan Wang, Lu Qin, Xiao Zhang, and Xuemin Lin.","author":"Ding Bolin","year":"2007","unstructured":"Bolin Ding, Jeffrey Xu Yu, Shan Wang, Lu Qin, Xiao Zhang, and Xuemin Lin. 2007. Finding Top-k Min-Cost Connected Trees in Databases. In ICDE. IEEE Computer Society."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872762"},{"key":"e_1_2_1_20_1","volume-title":"Yu","author":"He Hao","year":"2007","unstructured":"Hao He, Haixun Wang, Jun Yang, and Philip S. Yu. 2007. BLINKS: ranked keyword searches on graphs. In SIGMOD."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Vagelis Hristidis Luis Gravano and Yannis Papakonstantinou. 2003. Efficient IR-Style Keyword Search over Relational Databases. In VLDB.","DOI":"10.1016\/B978-012722442-8\/50080-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287427"},{"key":"e_1_2_1_23_1","unstructured":"Vagelis Hristidis Yannis Papakonstantinou and Andrey Balmin. 2003. Keyword Proximity Search on XML Graphs. In ICDE."},{"key":"e_1_2_1_24_1","unstructured":"Varun Kacholia Shashank Pandit Soumen Chakrabarti S. Sudarshan Rushi Desai and Hrishikesh Karambelkar. 2005. Bidirectional Expansion For Keyword Search on Graph Databases. In VLDB."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Mehdi Kargar and Aijun An. 2011. Keyword Search in Graphs: Finding r-cliques. In VLDB.","DOI":"10.14778\/2021017.2021025"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2985376"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_28_1","volume-title":"STAR: Steiner-Tree Approximation in Relationship Graphs. In ICDE.","author":"Kasneci Gjergji","year":"2009","unstructured":"Gjergji Kasneci, Maya Ramanath, Mauro Sozio, Fabian M. Suchanek, and Gerhard Weikum. 2009. STAR: Steiner-Tree Approximation in Relationship Graphs. In ICDE."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2302294"},{"key":"e_1_2_1_30_1","volume-title":"Jianhua Feng, Jianyong Wang, and Lizhu Zhou.","author":"Li Guoliang","year":"2008","unstructured":"Guoliang Li, Beng Chin Ooi, Jianhua Feng, Jianyong Wang, and Lizhu Zhou. 2008. EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. In SIGMOD."},{"key":"e_1_2_1_31_1","volume-title":"Jeffrey Xu Yu, and Rui Mao","author":"Li Rong-Hua","year":"2016","unstructured":"Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao. 2016. Efficient and Progressive Group Steiner Tree Search. In SIGMOD."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Yi Luo Xuemin Lin Wei Wang and Xiaofang Zhou. 2007. Spark: top-k keyword query in relational databases. In SIGMOD.","DOI":"10.1145\/1247480.1247495"},{"key":"e_1_2_1_33_1","article-title":"SPARK2: Top-k Keyword Query in Relational Databases. In IEEE","author":"Luo Yi","year":"2011","unstructured":"Yi Luo, Wei Wang, Xuemin Lin, Xiaofang Zhou, Jianmin Wang, and Keqiu Li. 2011. SPARK2: Top-k Keyword Query in Relational Databases. In IEEE Trans. Knowl. Data Eng.","journal-title":"Trans. Knowl. Data Eng."},{"key":"e_1_2_1_34_1","volume-title":"System Implementations, and Open Challenges. VLDB","author":"Mhedhbi Amine","year":"2022","unstructured":"Amine Mhedhbi and Semih Salihoglu. 2022. Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges. VLDB (2022)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Madhulika Mohanty and Maya Ramanath. 2018. Klustree: clustering answer trees from keyword search on graphs. In COMAD\/CODS.","DOI":"10.1145\/3152494.3152509"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Madhulika Mohanty and Maya Ramanath. 2019. Insta-Search: Towards Effective Exploration of Knowledge Graphs. In CIKM.","DOI":"10.1145\/3357384.3357858"},{"key":"e_1_2_1_37_1","unstructured":"Madhulika Mohanty Maya Ramanath Mohamed Yahya and Gerhard Weikum. 2019. Spec-QP: Speculative Query Planning for Joins over Knowledge Graphs. In EDBT."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Davide Mottin Matteo Lissandrini Yannis Velegrakis and Themis Palpanas. 2019. Exploring the Data Wilderness through Examples. In SIGMOD.","DOI":"10.1145\/3299869.3314031"},{"key":"e_1_2_1_39_1","unstructured":"Neo4j. 2022. Cypher Query Language. https:\/\/neo4j.com\/developer\/cypher\/"},{"key":"e_1_2_1_40_1","volume-title":"Stefania Dumbrava, Olaf Hartig","author":"Sakr Sherif","year":"2021","unstructured":"Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid G. Aref, Marcelo Arenas, Maciej Besta, Peter A. Boncz, Khuzaima Daudjee, Emanuele Della Valle, Stefania Dumbrava, Olaf Hartig, Bernhard Haslhofer, Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer \u00d6zsu, Eric Peukert, Stefan Plantikow, Mohamed Ragab, Matei Ripeanu, Semih Salihoglu, Christian Schulz, Petra Selmer, Juan F. Sequeda, Joshua Shinavier, G\u00e1bor Sz\u00e1rnyas, Riccardo Tommasini, Antonino Tumeo, Alexandru Uta, Ana Lucia Varbanescu, Hsiang-Yun Wu, Nikolay Yakovets, Da Yan, and Eiko Yoneki. 2021. The future is big graphs: a community view on graph processing systems. In Commun. ACM."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Thanh Tran Haofen Wang Sebastian Rudolph and Philipp Cimiano. 2009. Top-k Exploration of Query Candidates for Efficient Keyword Search on Graph-Shaped (RDF) Data. In ICDE.","DOI":"10.1109\/ICDE.2009.119"},{"key":"e_1_2_1_42_1","unstructured":"W3C. 2013. SPARQL 1.1. https:\/\/www.w3.org\/TR\/sparql11-overview\/"},{"key":"e_1_2_1_43_1","volume-title":"Aggarwal","author":"Wang Haixun","year":"2010","unstructured":"Haixun Wang and Charu C. Aggarwal. 2010. A Survey of Algorithms for Keyword Search on Graph Data. In Managing and Mining Graph Data. Springer."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Jianye Yang Wu Yao and Wenjie Zhang. 2021. Keyword Search on Large Graphs: A Survey. In Data Sci. Eng.","DOI":"10.1007\/s41019-021-00154-4"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Yueji Yang Divyakant Agrawal H. V. Jagadish Anthony K. H. Tung and Shuang Wu. 2019. An Efficient Parallel Keyword Search Engine on Knowledge Graphs. In ICDE.","DOI":"10.1109\/ICDE.2019.00038"},{"key":"e_1_2_1_46_1","volume-title":"Guoren Wang, Ye Yuan, and Lisi Chen.","author":"Zhang Zhiwei","year":"2022","unstructured":"Zhiwei Zhang, Jeffrey Xu Yu, Guoren Wang, Ye Yuan, and Lisi Chen. 2022. Keycore: cohesive keyword subgraph exploration in large graphs. In World Wide Web."},{"key":"e_1_2_1_47_1","article-title":"Cohesive Subgraph Search Using Keywords in Large Networks. In IEEE","author":"Zhu Yuanyuan","year":"2022","unstructured":"Yuanyuan Zhu, Qian Zhang, Lu Qin, Lijun Chang, and Jeffrey Xu Yu. 2022. Cohesive Subgraph Search Using Keywords in Large Networks. In IEEE Trans. Knowl. Data Eng.","journal-title":"Trans. Knowl. Data Eng."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611540.3611577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:34:52Z","timestamp":1757543692000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611540.3611577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":47,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.14778\/3611540.3611577"],"URL":"https:\/\/doi.org\/10.14778\/3611540.3611577","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,8]]},"assertion":[{"value":"2023-08-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}