{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:45:19Z","timestamp":1774982719158,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,12,18]]},"abstract":"<jats:p>The recent ISO SQL:2023 standard adopts SQL\/PGQ (Property Graph Queries), facilitating graph-like querying within relational databases. This advancement, however, underscores a significant gap in how to effectively optimize SQL\/PGQ queries within relational database systems. To address this gap, we extend the foundational SPJ (Select-Project-Join) queries to SPJM queries, which include an additional matching operator for representing graph pattern matching in SQL\/PGQ. Although SPJM queries can be converted to SPJ queries and optimized using existing relational query optimizers, our analysis shows that such a graph-agnostic method fails to benefit from graph-specific optimization techniques found in the literature. To address this issue, we develop a converged relational-graph optimization framework called RelGo for optimizing SPJM queries, leveraging joint efforts from both relational and graph query optimizations. Using DuckDB as the underlying relational execution engine, our experiments show that RelGo can generate efficient execution plans for SPJM queries. On well-established benchmarks, these plans exhibit an average speedup of 21.90x compared to those produced by the graph-agnostic optimizer.<\/jats:p>","DOI":"10.1145\/3698828","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-27","source":"Crossref","is-referenced-by-count":4,"title":["Towards a Converged Relational-Graph Optimization Framework"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9427-3012","authenticated-orcid":false,"given":"Yunkai","family":"Lou","sequence":"first","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4735-3835","authenticated-orcid":false,"given":"Longbin","family":"Lai","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6795-9262","authenticated-orcid":false,"given":"Bingqing","family":"Lyu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9397-9458","authenticated-orcid":false,"given":"Yufan","family":"Yang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1687-4621","authenticated-orcid":false,"given":"XiaoLi","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-5641-2452","authenticated-orcid":false,"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2674-1638","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4220-2634","authenticated-orcid":false,"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2024. Apache Age. https:\/\/age.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"2024. DuckDB. https:\/\/duckdb.org\/."},{"key":"e_1_2_1_3_1","unstructured":"2024. openCypher. https:\/\/opencypher.org\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3184470.3184473"},{"key":"e_1_2_1_6_1","volume-title":"Article 68 (sep","author":"Angles Renzo","year":"2017","unstructured":"Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Aidan Hogan, Juan Reutter, and Domagoj Vrgoc. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5, Article 68 (sep 2017), 40 pages."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--21595--7_16"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 1974 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control","author":"Donald","unstructured":"Donald D. Chamberlin and Raymond F. Boyce. 1974. SEQUEL: A structured English query language. In Proceedings of the 1974 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control (Ann Arbor, Michigan) (SIGFIDET '74). Association for Computing Machinery, New York, NY, USA, 249--264."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '02)","author":"Chatterji S.","unstructured":"S. Chatterji, S. S. K. Evani, S. Ganguly, and M. D. Yemmanuru. 2002. On the complexity of approximate query optimization. In Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '02). Association for Computing Machinery, New York, NY, USA, 282--292."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320249"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539303"},{"key":"e_1_2_1_14_1","first-page":"2","article-title":"English sentence structure and entity-relationship diagrams","volume":"29","author":"Pin-Shan Chen Peter","year":"1983","unstructured":"Peter Pin-Shan Chen. 1983. English sentence structure and entity-relationship diagrams. Information Sciences 29, 2--3 (1983), 127--149.","journal-title":"Information Sciences"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375706"},{"key":"e_1_2_1_17_1","first-page":"19","article-title":"The Cascades Framework for Query Optimization","volume":"18","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe. 1995. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18, 3 (1995), 19--29. http:\/\/sites.computer.org\/debull\/95SEP-CD.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588927"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/EDBT.2018.04"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1270.1498"},{"key":"e_1_2_1_22_1","volume-title":"K\u00d9ZU Graph Database Management System. In 13th Conference on Innovative Data Systems Research, CIDR 2023","author":"Jin Guodong","year":"2023","unstructured":"Guodong Jin, Xiyang Feng, Ziyi Chen, Chang Liu, and Semih Salihoglu. 2023. K\u00d9ZU Graph Database Management System. In 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8--11, 2023. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2023\/papers\/p48-jin.pdf"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510400"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/EDBT.2017.26"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00676--3"},{"key":"e_1_2_1_26_1","volume-title":"VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25--28","author":"Krishnamurthy Ravi","year":"1986","unstructured":"Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo. 1986. Optimization of Nonrecursive Queries. In VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25--28, 1986, Kyoto, Japan, Proceedings, Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi (Eds.). Morgan Kaufmann, 128--137. http:\/\/www.vldb.org\/conf\/1986\/P128.PDF"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_1_29_1","volume-title":"GLogS: Interactive Graph Pattern Matching Query At Large Scale. In 2023 USENIX Annual Technical Conference, USENIX ATC 2023","author":"Lai Longbin","year":"2023","unstructured":"Longbin Lai, Yufan Yang, Zhibin Wang, Yuxuan Liu, Haotian Ma, Sijie Shen, Bingqing Lyu, Xiaoli Zhou, Wenyuan Yu, Zhengping Qian, Chen Tian, Sheng Zhong, Yeh-Ching Chung, and Jingren Zhou. 2023. GLogS: Interactive Graph Pattern Matching Query At Large Scale. In 2023 USENIX Annual Technical Conference, USENIX ATC 2023, Boston, MA, USA, July 10--12, 2023, Julia Lawall and Dan Williams (Eds.). USENIX Association, 53--69. https:\/\/www.usenix.org\/conference\/atc23\/presentation\/lai"},{"key":"e_1_2_1_30_1","volume-title":"https:\/\/ldbcouncil.org\/benchmarks\/snb\/. [Online","author":"Social Network Benchmark LDBC","year":"2022","unstructured":"LDBC Social Network Benchmark. 2022. https:\/\/ldbcouncil.org\/benchmarks\/snb\/. [Online; accessed 20-October-2022]."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021941"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Yunkai Lou Longbin Lai Bingqing Lyu Yufan Yang XiaoLi Zhou Wenyuan Yu Ying Zhang and Jingren Zhou. 2024. Towards a Converged Relational-Graph Optimization Framework (Artifact). https:\/\/anonymous.4open.science\/r\/relgo-artifact2-C4F0","DOI":"10.1145\/3698828"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Yunkai Lou Longbin Lai Bingqing Lyu Yufan Yang XiaoLi Zhou Wenyuan Yu Ying Zhang and Jingren Zhou. 2024. Towards a Converged Relational-Graph Optimization Framework (Full Version). https:\/\/anonymous.4open.science\/r\/relgo-artifact2-C4F0\/paper\/paper.pdf","DOI":"10.1145\/3698828"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_37_1","volume-title":"Freitag","author":"Neumann Thomas","year":"2020","unstructured":"Thomas Neumann and Michael J. Freitag. 2020. 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. http:\/\/cidrdb.org\/cidr2020\/papers\/p29-neumann-cidr20.pdf"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_40_1","volume-title":"Property Graph Queries (SQL\/PGQ)","year":"2023","unstructured":"Oracle. 2023. Property Graph Queries (SQL\/PGQ). International Organization for Standardization. Retrieved June, 2023 from https:\/\/www.iso.org\/standard\/79473.html"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_1_42_1","unstructured":"Protocol Buffers. 2024. https:\/\/protobuf.dev\/overview\/."},{"key":"e_1_2_1_43_1","volume-title":"Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries. In SIGMOD '21: International Conference on Management of Data","author":"Qiu Yuan","year":"2021","unstructured":"Yuan Qiu, Yilei Wang, Ke Yi, Feifei Li, Bin Wu, and Chaoqun Zhan. 2021. Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries. In SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20--25, 2021, Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 1465--1477."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_45_1","volume-title":"2023 USENIX Annual Technical Conference (USENIX ATC 23)","author":"Shen Sijie","year":"2023","unstructured":"Sijie Shen, Zihang Yao, Lin Shi, Lei Wang, Longbin Lai, Qian Tao, Li Su, Rong Chen, Wenyuan Yu, Haibo Chen, Binyu Zang, and Jingren Zhou. 2023. Bridging the Gap between Relational OLTP and Graph-based OLAP. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). USENIX Association, Boston, MA, 181--196. https:\/\/www.usenix.org\/conference\/atc23\/presentation\/shen"},{"key":"e_1_2_1_46_1","first-page":"427","article-title":"A comparative analysis of entity-relationship diagrams","volume":"3","author":"Song Il-Yeol","year":"1995","unstructured":"Il-Yeol Song, Mary Evans, and Eun K Park. 1995. A comparative analysis of entity-relationship diagrams. Journal of Computer and Software Engineering 3, 4 (1995), 427--459.","journal-title":"Journal of Computer and Software Engineering"},{"key":"e_1_2_1_47_1","volume-title":"13th Conference on Innovative Data Systems Research, CIDR 2023","author":"Wolde Daniel","year":"2023","unstructured":"Daniel ten Wolde, Tavneet Singh, G\u00e1bor Sz\u00e1rnyas, and Peter A. Boncz. 2023. 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. https:\/\/www.cidrdb.org\/cidr2023\/papers\/p66-wolde.pdf"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611614"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589295"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698828","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698828","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:46:20Z","timestamp":1774979180000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698828"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698828"],"URL":"https:\/\/doi.org\/10.1145\/3698828","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}