{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:45Z","timestamp":1779174825638,"version":"3.51.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>Graph database systems (GDBs) have supported many important real-world applications such as social networks, logistics, and path planning. Meanwhile, logic bugs are also prevalent in GDBs, leading to incorrect results and severe consequences. However, the logic bugs largely cannot be revealed by prior solutions which are unaware of the graph native structures of the graph data. In this paper, we propose Gamera (Graph-aware metamorphic relations), a novel metamorphic testing approach to uncover unknown logic bugs in GDBs. We design three classes of novel graph-aware Metamorphic Relations (MRs) based on the graph native structures. Gamera would generate a set of queries according to the graph-aware MRs to test diverse and complex GDB operations, and check whether the GDB query results conform to the chosen MRs.<\/jats:p>\n          <jats:p>We thoroughly evaluated the effectiveness of Gamera on seven widely-used GDBs such as Neo4j and OrientDB. Gamera was highly effective in detecting logic bugs in GDBs. In total, it detected 39 logic bugs, of which 15 bugs have been confirmed, and three bugs have been fixed. Our experiments also demonstrated that Gamera significantly outperformed prior solutions including Grand, GD-smith and GDBMeter. Gamera has been well-recognized by GDB developers and we open-source our prototype implementation to contribute to the community.<\/jats:p>","DOI":"10.14778\/3636218.3636236","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:07Z","timestamp":1709658247000},"page":"836-848","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Testing Graph Database Systems via Graph-Aware Metamorphic Relations"],"prefix":"10.14778","volume":"17","author":[{"given":"Zeyang","family":"Zhuang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Penghui","family":"Li","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pingchuan","family":"Ma","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Meng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuai","family":"Wang","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2015. Count Lines of Code. https:\/\/github.com\/AlDanial\/cloc."},{"key":"e_1_2_1_2_1","unstructured":"2023. AQL (ArangoDB Query Language). https:\/\/www.arangodb.com\/docs\/stable\/aql\/."},{"key":"e_1_2_1_3_1","unstructured":"2023. ArangoDB. https:\/\/www.arangodb.com\/."},{"key":"e_1_2_1_4_1","unstructured":"2023. Cypher Manual. https:\/\/neo4j.com\/docs\/cypher-manual\/current\/introduction\/."},{"key":"e_1_2_1_5_1","unstructured":"2023. DB-Engines Ranking of Graph DBMS. https:\/\/db-engines.com\/en\/ranking\/graph+dbms."},{"key":"e_1_2_1_6_1","unstructured":"2023. GDBMeter artifact. https:\/\/github.com\/gdbmeter\/gdbmeter."},{"key":"e_1_2_1_7_1","unstructured":"2023. GDsmith artifact. https:\/\/github.com\/ddaa2000\/GDsmith."},{"key":"e_1_2_1_8_1","unstructured":"2023. Grand artifact. https:\/\/github.com\/tcse-iscas\/Grand."},{"key":"e_1_2_1_9_1","unstructured":"2023. Graph Algorithms. https:\/\/neo4j.com\/docs\/graph-data-science\/current\/algorithms\/."},{"key":"e_1_2_1_10_1","unstructured":"2023. Gremlin Manual. https:\/\/tinkerpop.apache.org\/docs\/3.6.2\/reference\/."},{"key":"e_1_2_1_11_1","unstructured":"2023. HugeGraph. https:\/\/hugegraph.apache.org\/."},{"key":"e_1_2_1_12_1","unstructured":"2023. JanusGraph. https:\/\/janusgraph.org\/."},{"key":"e_1_2_1_13_1","unstructured":"2023. Neo4j. https:\/\/neo4j.com\/."},{"key":"e_1_2_1_14_1","unstructured":"2023. The Next Generation Multi-Model Database Supporting Graphs Key\/Value Documents and Time-Series. https:\/\/arcadedb.com\/."},{"key":"e_1_2_1_15_1","unstructured":"2023. OrientDB. https:\/\/orientdb.org\/."},{"key":"e_1_2_1_16_1","unstructured":"2023. Path Finding. https:\/\/neo4j.com\/docs\/graph-data-science\/current\/algorithms\/pathfinding\/."},{"key":"e_1_2_1_17_1","unstructured":"2023. RedisGraph. https:\/\/redis.io\/docs\/stack\/graph\/."},{"key":"e_1_2_1_18_1","unstructured":"2023. SQLancer. https:\/\/github.com\/sqlancer\/sqlancer."},{"key":"e_1_2_1_19_1","unstructured":"2023. TingerGraph. https:\/\/www.tigergraph.com\/."},{"key":"e_1_2_1_20_1","unstructured":"2023. TinkerGraph. https:\/\/github.com\/tinkerpop\/blueprints\/wiki\/tinkergraph."},{"key":"e_1_2_1_21_1","unstructured":"2023. TinkerPop. https:\/\/tinkerpop.apache.org\/."},{"key":"e_1_2_1_22_1","unstructured":"2023. Traversal Recipes. https:\/\/tinkerpop.apache.org\/docs\/current\/recipes\/#_traversal_recipes."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457545"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362715"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551813"},{"key":"e_1_2_1_27_1","unstructured":"Forrester Consulting. 2021. The Total Economic Impact\u2122 of the Neo4j Graph Data Platform. https:\/\/neo4j.com\/whitepapers\/forrester-total-economic-impact\/."},{"key":"e_1_2_1_28_1","unstructured":"Alin Deutsch. 2018. Querying Graph Databases with the GSQL Query Language.. In SBBD. 313."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3395032.3395327"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597926.3598046"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357382"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597926.3598044"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00303"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494139"},{"key":"e_1_2_1_38_1","first-page":"100","article-title":"Differential testing for software","volume":"10","author":"McKeeman William M","year":"1998","unstructured":"William M McKeeman. 1998. Differential testing for software. Digital Technical Journal 10, 1 (1998), 100--107.","journal-title":"Digital Technical Journal"},{"key":"e_1_2_1_39_1","unstructured":"Neo4j. 2015. Introducing the new Cypher Query Optimizer. https:\/\/neo4j.com\/blog\/introducing-new-cypher-query-optimizer\/."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00197"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409710"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428279"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815072.2815073"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365109.3368782"},{"key":"e_1_2_1_45_1","volume-title":"VLDB","volume":"98","author":"Slutz Donald R","year":"1998","unstructured":"Donald R Slutz. 1998. Massive stochastic testing of SQL. In VLDB, Vol. 98. Citeseer, 618--622."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209950.3209958"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533767.3534409"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384351"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3636218.3636236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:06:20Z","timestamp":1709658380000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3636218.3636236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.14778\/3636218.3636236"],"URL":"https:\/\/doi.org\/10.14778\/3636218.3636236","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}