{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T09:56:12Z","timestamp":1768730172708,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>In this paper, we study a declarative framework for specifying transformations of property graphs. In order to express such transformations, we leverage queries formulated in the Graph Pattern Calculus (GPC), which is an abstraction of the common core of recent standard graph query languages, GQL and SQL\/PGQ. In contrast to previous frameworks targeting graph topology only, we focus on the impact of data values on the transformations---which is crucial in addressing users' needs. In particular, we study the complexity of checking if the transformation rules do not specify conflicting values for properties, and we show this is closely related to the satisfiability problem for GPC. We prove that both problems are PSpace-complete.<\/jats:p><jats:p>We have implemented our framework in openCypher. We show the flexibility and usability of our framework by leveraging an existing data integration benchmark, adapting it to our needs. We also evaluate the incurred overhead of detecting potential inconsistencies at run-time, and the impact of several optimization tools in a Cypher-based graph database, by providing a comprehensive comparison of different implementation variants. The results of our experimental study show that our framework exhibits large practical benefits for transforming property graphs compared to ad-hoc transformation scripts.<\/jats:p>","DOI":"10.14778\/3681954.3681972","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"2906-2918","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Transforming Property Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Angela","family":"Bonifati","sequence":"first","affiliation":[{"name":"Lyon 1 Univ., Liris CNRS &amp; IUF"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Filip","family":"Murlak","sequence":"additional","affiliation":[{"name":"Univ. of Warsaw"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Ramusat","sequence":"additional","affiliation":[{"name":"Lyon 1 Univ., Liris CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290182"},{"key":"e_1_2_1_2_1","first-page":"17","article-title":"Transforming RDF-star to Property Graphs","volume":"2022","author":"Abuoda Ghadeer","year":"2022","unstructured":"Ghadeer Abuoda, Daniele Dell'Aglio, Arthur Keen, and Katja Hose. 2022. Transforming RDF-star to Property Graphs: A Preliminary Analysis of Transformation Approaches. In QuWeDa 2022. 17--32.","journal-title":"A Preliminary Analysis of Transformation Approaches. In QuWeDa"},{"key":"e_1_2_1_3_1","volume-title":"Relational and XML Data Exchange","author":"Arenas Marcelo","unstructured":"Marcelo Arenas, Pablo Barcelo, Leonid Libkin, and Filip Murlak. 2010. Relational and XML Data Exchange (1st ed.). Morgan and Claypool Publishers.","edition":"1"},{"key":"e_1_2_1_4_1","first-page":"108","article-title":"The IBench Integration Metadata Generator","volume":"9","author":"Arocena Patricia C.","year":"2015","unstructured":"Patricia C. Arocena, Boris Glavic, Radu Ciucanu, and Ren\u00e9e J. Miller. 2015. The IBench Integration Metadata Generator. VLDB 9, 3 (2015), 108--119.","journal-title":"VLDB"},{"key":"e_1_2_1_5_1","volume-title":"Miller","author":"Arocena Patricia C.","year":"2013","unstructured":"Patricia C. Arocena, Boris Glavic, and Renee J. Miller. 2013. Value Invention in Data Exchange. In SIGMOD. 157--168."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Pablo Barcel\u00f3 Jorge P\u00e9rez and Juan Reutter. 2013. Schema Mappings and Data Exchange for Graph Databases. In ICDT. 189--200.","DOI":"10.1145\/2448496.2448520"},{"key":"e_1_2_1_7_1","volume-title":"Reutter","author":"Barcel\u00f3 Pablo","year":"2012","unstructured":"Pablo Barcel\u00f3, Jorge P\u00e9rez, and Juan L. Reutter. 2012. Relative Expressiveness of Nested Regular Expressions. In AMW. 180--195."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Pablo Barcel\u00f3 Baeza. 2013. Querying Graph Databases. In PODS. 175--188.","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Z. Bellahsene A. Bonifati and E. Rahm. 2011. Schema Matching and Mapping.","DOI":"10.1007\/978-3-642-16518-4"},{"key":"e_1_2_1_10_1","volume-title":"Bernstein and Sergey Melnik","author":"Philip","year":"2007","unstructured":"Philip A. Bernstein and Sergey Melnik. 2007. Model Management 2.0: Manipulating Richer Mappings. In SIGMOD. 1--12."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Iovka Boneva Beno\u00eet Groz Jan Hidders Filip Murlak and Slawek Staworko. 2023. Static Analysis of Graph Database Transformations. In PODS. 251--261.","DOI":"10.1145\/3584372.3588654"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Angela Bonifati Ugo Comignani Emmanuel Coquery and Romuald Thion. 2017. Interactive Mapping Specification with Exemplar Tuples. In SIGMOD. 667--682.","DOI":"10.1145\/3035918.3064028"},{"key":"e_1_2_1_13_1","unstructured":"Angela Bonifati Filip Murlak and Yann Ramusat. 2024. Transforming Property Graphs. arXiv:2406.13062 [cs.DB] https:\/\/arxiv.org\/abs\/2406.13062"},{"key":"e_1_2_1_14_1","unstructured":"Laura Chiticariu and Wang-Chiew Tan. 2006. Debugging schema mappings with routes. In PVLDB. 79--90."},{"key":"e_1_2_1_15_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 Filip Murlak 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. 2246--2258.","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/262762.262763"},{"key":"e_1_2_1_19_1","volume-title":"Offshoreleaks Data Packages. Retrieved","author":"Fiandor Miguel","year":"2024","unstructured":"Miguel Fiandor and Michael Hunger. [n.d.]. Offshoreleaks Data Packages. Retrieved March 1, 2024 from https:\/\/github.com\/ICIJ\/offshoreleaks-data-packages"},{"key":"e_1_2_1_20_1","volume-title":"GPC: A Pattern Calculus for Property Graphs. In PODS. 241--250.","author":"Francis Nadime","year":"2023","unstructured":"Nadime Francis, Am\u00e9lie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2023. GPC: A Pattern Calculus for Property Graphs. In PODS. 241--250."},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"A Researcher's Digest of GQL","volume":"255","author":"Francis Nadime","year":"2023","unstructured":"Nadime Francis, Am\u00e9lie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgo\u010d. 2023. A Researcher's Digest of GQL. In ICDT, Vol. 255. 1--22.","journal-title":"ICDT"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_23_1","volume-title":"Schema Mappings for Data Graphs. In PODS'17","author":"Francis Nadime","year":"2017","unstructured":"Nadime Francis and Leonid Libkin. 2017. Schema Mappings for Data Graphs. In PODS'17. 389--401."},{"key":"e_1_2_1_24_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990","unstructured":"Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co."},{"key":"e_1_2_1_25_1","first-page":"2242","article-title":"Updating graph databases with Cypher","volume":"12","author":"Green Alastair","year":"2019","unstructured":"Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Martin Schuster, Petra Selmer, and Hannes Voigt. 2019. Updating graph databases with Cypher. VLDB 12, 12 (2019), 2242--2254.","journal-title":"VLDB"},{"key":"e_1_2_1_26_1","volume-title":"ILOG: Declarative Creation and Manipulation of Object Identifiers. In VLDB. 455--468.","author":"Hull Richard","year":"1990","unstructured":"Richard Hull and Masatoshi Yoshikawa. 1990. ILOG: Declarative Creation and Manipulation of Object Identifiers. In VLDB. 455--468."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Phokion G. Kolaitis. 2005. Schema Mappings Data Exchange and Metadata Management. In PODS. 61--75.","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_1_28_1","volume-title":"APOC user guide for Neo4j 5. Retrieved","year":"2023","unstructured":"Neo4j. 2023. APOC user guide for Neo4j 5. Retrieved November 9, 2023 from https:\/\/neo4j.com\/docs\/apoc\/current\/"},{"key":"e_1_2_1_29_1","volume-title":"Graph Data Modeling Fundamentals. Retrieved","year":"2023","unstructured":"Neo4j. 2023. Graph Data Modeling Fundamentals. Retrieved November 9, 2023 from https:\/\/graphacademy.neo4j.com\/courses\/modeling-fundamentals\/"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Larissa C. Shimomura George Fletcher and Nikolay Yakovets. 2020. GGDs: Graph Generating Dependencies. In CIKM. 2217--2220.","DOI":"10.1145\/3340531.3412149"},{"key":"e_1_2_1_31_1","unstructured":"Larissa C. Shimomura Nikolay Yakovets and George Fletcher. 2022. Reasoning on Property Graphs with Graph Generating Dependencies. arXiv:2211.00387 [cs.DB] https:\/\/arxiv.org\/abs\/2211.00387"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611506"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Moshe Y. Vardi. 2016. A Theory of Regular Queries. In PODS. 1--9.","DOI":"10.1145\/2902251.2902305"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412168"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681972","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T15:12:59Z","timestamp":1732720379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681972"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":35,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681972"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681972","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}