Testing Graph Databases with Synthesized Queries Article Swipe
Zhongbao Yin
,
Si Liu
,
David Basin
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1145/3749186
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1145/3749186
Graph databases (GDBs) are increasingly used in many applications. However, their advanced features make them prone to logic bugs. Despite advances in GDB testing, a common limitation of current approaches is the lack of ground truth for their test oracles. This results in both incorrectly identified bugs and overlooked bugs. We introduce GQS (Graph Query Synthesis), the first automated testing approach for detecting logic bugs in graph databases (GDBs) based on an established ground truth. GQS starts by randomly generating a graph and selecting a set of properties associated with its elements, whose key-value pairs form the expected result set serving as the ground truth. It then synthesizes a query that should retrieve these values from the graph. When the query is executed on the graph by the GDB under test, any discrepancy between the actual result set and the ground truth indicates a logic bug. To extensively test a GDB, we develop novel techniques that synthesize both syntactically and semantically complex queries. We implement GQS in a tool that incorporates the first Cypher query synthesizer specifically designed for testing GDBs. Our tool finds 36 previously unknown bugs across four production GDBs, of which 26 are logic bugs, with some remaining undetected for up to five years. Additionally, our tool demonstrates superior effectiveness in bug detection compared to the state-of-the-art testers.
Related Topics
Concepts
No concepts available.
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1145/3749186
- OA Status
- hybrid
- References
- 32
- OpenAlex ID
- https://openalex.org/W4414427881
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4414427881Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1145/3749186Digital Object Identifier
- Title
-
Testing Graph Databases with Synthesized QueriesWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-09-22Full publication date if available
- Authors
-
Zhongbao Yin, Si Liu, David BasinList of authors in order
- Landing page
-
https://doi.org/10.1145/3749186Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
hybridOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.1145/3749186Direct OA link when available
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
32Number of works referenced by this work
Full payload
| id | https://openalex.org/W4414427881 |
|---|---|
| doi | https://doi.org/10.1145/3749186 |
| ids.doi | https://doi.org/10.1145/3749186 |
| ids.openalex | https://openalex.org/W4414427881 |
| fwci | 0.0 |
| type | article |
| title | Testing Graph Databases with Synthesized Queries |
| biblio.issue | 4 |
| biblio.volume | 3 |
| biblio.last_page | 26 |
| biblio.first_page | 1 |
| topics[0].id | https://openalex.org/T12292 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1707 |
| topics[0].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[0].display_name | Graph Theory and Algorithms |
| topics[1].id | https://openalex.org/T10317 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9995999932289124 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Advanced Database Systems and Queries |
| topics[2].id | https://openalex.org/T11106 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9987999796867371 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1711 |
| topics[2].subfield.display_name | Signal Processing |
| topics[2].display_name | Data Management and Algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| language | en |
| locations[0].id | doi:10.1145/3749186 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4387289859 |
| locations[0].source.issn | 2836-6573 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 2836-6573 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Proceedings of the ACM on Management of Data |
| locations[0].source.host_organization | https://openalex.org/P4310319798 |
| locations[0].source.host_organization_name | Association for Computing Machinery |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310319798 |
| locations[0].source.host_organization_lineage_names | Association for Computing Machinery |
| locations[0].license | cc-by-nc-nd |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by-nc-nd |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Proceedings of the ACM on Management of Data |
| locations[0].landing_page_url | https://doi.org/10.1145/3749186 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5107930184 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Zhongbao Yin |
| authorships[0].countries | CH |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I35440088 |
| authorships[0].affiliations[0].raw_affiliation_string | ETH Zurich, Zurich, Switzerland |
| authorships[0].institutions[0].id | https://openalex.org/I35440088 |
| authorships[0].institutions[0].ror | https://ror.org/05a28rw58 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I2799323385, https://openalex.org/I35440088 |
| authorships[0].institutions[0].country_code | CH |
| authorships[0].institutions[0].display_name | ETH Zurich |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Zijing Yin |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | ETH Zurich, Zurich, Switzerland |
| authorships[1].author.id | https://openalex.org/A5100330142 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-3578-7432 |
| authorships[1].author.display_name | Si Liu |
| authorships[1].countries | CH |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I35440088 |
| authorships[1].affiliations[0].raw_affiliation_string | ETH Zurich, Zurich, Switzerland |
| authorships[1].institutions[0].id | https://openalex.org/I35440088 |
| authorships[1].institutions[0].ror | https://ror.org/05a28rw58 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I2799323385, https://openalex.org/I35440088 |
| authorships[1].institutions[0].country_code | CH |
| authorships[1].institutions[0].display_name | ETH Zurich |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Si Liu |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | ETH Zurich, Zurich, Switzerland |
| authorships[2].author.id | https://openalex.org/A5025344654 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-2952-939X |
| authorships[2].author.display_name | David Basin |
| authorships[2].countries | CH |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I35440088 |
| authorships[2].affiliations[0].raw_affiliation_string | ETH Zurich, Zurich, Switzerland |
| authorships[2].institutions[0].id | https://openalex.org/I35440088 |
| authorships[2].institutions[0].ror | https://ror.org/05a28rw58 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I2799323385, https://openalex.org/I35440088 |
| authorships[2].institutions[0].country_code | CH |
| authorships[2].institutions[0].display_name | ETH Zurich |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | David Basin |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | ETH Zurich, Zurich, Switzerland |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doi.org/10.1145/3749186 |
| open_access.oa_status | hybrid |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Testing Graph Databases with Synthesized Queries |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T12292 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1707 |
| primary_topic.subfield.display_name | Computer Vision and Pattern Recognition |
| primary_topic.display_name | Graph Theory and Algorithms |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1145/3749186 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4387289859 |
| best_oa_location.source.issn | 2836-6573 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | 2836-6573 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Proceedings of the ACM on Management of Data |
| best_oa_location.source.host_organization | https://openalex.org/P4310319798 |
| best_oa_location.source.host_organization_name | Association for Computing Machinery |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310319798 |
| best_oa_location.source.host_organization_lineage_names | Association for Computing Machinery |
| best_oa_location.license | cc-by-nc-nd |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by-nc-nd |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Proceedings of the ACM on Management of Data |
| best_oa_location.landing_page_url | https://doi.org/10.1145/3749186 |
| primary_location.id | doi:10.1145/3749186 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4387289859 |
| primary_location.source.issn | 2836-6573 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 2836-6573 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Proceedings of the ACM on Management of Data |
| primary_location.source.host_organization | https://openalex.org/P4310319798 |
| primary_location.source.host_organization_name | Association for Computing Machinery |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310319798 |
| primary_location.source.host_organization_lineage_names | Association for Computing Machinery |
| primary_location.license | cc-by-nc-nd |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by-nc-nd |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Proceedings of the ACM on Management of Data |
| primary_location.landing_page_url | https://doi.org/10.1145/3749186 |
| publication_date | 2025-09-22 |
| publication_year | 2025 |
| referenced_works | https://openalex.org/W4399156224, https://openalex.org/W1601925768, https://openalex.org/W2979942385, https://openalex.org/W4301500808, https://openalex.org/W2071952624, https://openalex.org/W4413755864, https://openalex.org/W4404181165, https://openalex.org/W4366660507, https://openalex.org/W4384155660, https://openalex.org/W4206512216, https://openalex.org/W4205625808, https://openalex.org/W4403223306, https://openalex.org/W4394745495, https://openalex.org/W3176686265, https://openalex.org/W3042605769, https://openalex.org/W3106731144, https://openalex.org/W1893177189, https://openalex.org/W4384305072, https://openalex.org/W4399208693, https://openalex.org/W2535818195, https://openalex.org/W3093296244, https://openalex.org/W4380433204, https://openalex.org/W3174531561, https://openalex.org/W2626990892, https://openalex.org/W2012380206, https://openalex.org/W4413349917, https://openalex.org/W2038123353, https://openalex.org/W4285490445, https://openalex.org/W3197227406, https://openalex.org/W109452506, https://openalex.org/W4392453941, https://openalex.org/W3099032206 |
| referenced_works_count | 32 |
| abstract_inverted_index.a | 24, 80, 84, 108, 143, 149, 167 |
| abstract_inverted_index.26 | 194 |
| abstract_inverted_index.36 | 184 |
| abstract_inverted_index.It | 105 |
| abstract_inverted_index.To | 146 |
| abstract_inverted_index.We | 50, 163 |
| abstract_inverted_index.an | 71 |
| abstract_inverted_index.as | 101 |
| abstract_inverted_index.by | 77, 126 |
| abstract_inverted_index.in | 6, 21, 42, 65, 166, 213 |
| abstract_inverted_index.is | 30, 121 |
| abstract_inverted_index.of | 27, 33, 86, 192 |
| abstract_inverted_index.on | 70, 123 |
| abstract_inverted_index.to | 16, 204, 217 |
| abstract_inverted_index.up | 203 |
| abstract_inverted_index.we | 151 |
| abstract_inverted_index.GDB | 22, 128 |
| abstract_inverted_index.GQS | 52, 75, 165 |
| abstract_inverted_index.Our | 181 |
| abstract_inverted_index.and | 47, 82, 138, 159 |
| abstract_inverted_index.any | 131 |
| abstract_inverted_index.are | 3, 195 |
| abstract_inverted_index.bug | 214 |
| abstract_inverted_index.for | 36, 61, 178, 202 |
| abstract_inverted_index.its | 90 |
| abstract_inverted_index.our | 208 |
| abstract_inverted_index.set | 85, 99, 137 |
| abstract_inverted_index.the | 31, 56, 96, 102, 116, 119, 124, 127, 134, 139, 171, 218 |
| abstract_inverted_index.GDB, | 150 |
| abstract_inverted_index.This | 40 |
| abstract_inverted_index.When | 118 |
| abstract_inverted_index.both | 43, 157 |
| abstract_inverted_index.bug. | 145 |
| abstract_inverted_index.bugs | 46, 64, 187 |
| abstract_inverted_index.five | 205 |
| abstract_inverted_index.form | 95 |
| abstract_inverted_index.four | 189 |
| abstract_inverted_index.from | 115 |
| abstract_inverted_index.lack | 32 |
| abstract_inverted_index.make | 13 |
| abstract_inverted_index.many | 7 |
| abstract_inverted_index.some | 199 |
| abstract_inverted_index.test | 38, 148 |
| abstract_inverted_index.that | 110, 155, 169 |
| abstract_inverted_index.them | 14 |
| abstract_inverted_index.then | 106 |
| abstract_inverted_index.tool | 168, 182, 209 |
| abstract_inverted_index.used | 5 |
| abstract_inverted_index.with | 89, 198 |
| abstract_inverted_index.GDBs, | 191 |
| abstract_inverted_index.GDBs. | 180 |
| abstract_inverted_index.Graph | 0 |
| abstract_inverted_index.Query | 54 |
| abstract_inverted_index.based | 69 |
| abstract_inverted_index.bugs, | 197 |
| abstract_inverted_index.bugs. | 18, 49 |
| abstract_inverted_index.finds | 183 |
| abstract_inverted_index.first | 57, 172 |
| abstract_inverted_index.graph | 66, 81, 125 |
| abstract_inverted_index.logic | 17, 63, 144, 196 |
| abstract_inverted_index.novel | 153 |
| abstract_inverted_index.pairs | 94 |
| abstract_inverted_index.prone | 15 |
| abstract_inverted_index.query | 109, 120, 174 |
| abstract_inverted_index.test, | 130 |
| abstract_inverted_index.their | 10, 37 |
| abstract_inverted_index.these | 113 |
| abstract_inverted_index.truth | 35, 141 |
| abstract_inverted_index.under | 129 |
| abstract_inverted_index.which | 193 |
| abstract_inverted_index.whose | 92 |
| abstract_inverted_index.(GDBs) | 2, 68 |
| abstract_inverted_index.(Graph | 53 |
| abstract_inverted_index.Cypher | 173 |
| abstract_inverted_index.across | 188 |
| abstract_inverted_index.actual | 135 |
| abstract_inverted_index.common | 25 |
| abstract_inverted_index.graph. | 117 |
| abstract_inverted_index.ground | 34, 73, 103, 140 |
| abstract_inverted_index.result | 98, 136 |
| abstract_inverted_index.should | 111 |
| abstract_inverted_index.starts | 76 |
| abstract_inverted_index.truth. | 74, 104 |
| abstract_inverted_index.values | 114 |
| abstract_inverted_index.years. | 206 |
| abstract_inverted_index.Despite | 19 |
| abstract_inverted_index.between | 133 |
| abstract_inverted_index.complex | 161 |
| abstract_inverted_index.current | 28 |
| abstract_inverted_index.develop | 152 |
| abstract_inverted_index.results | 41 |
| abstract_inverted_index.serving | 100 |
| abstract_inverted_index.testing | 59, 179 |
| abstract_inverted_index.unknown | 186 |
| abstract_inverted_index.However, | 9 |
| abstract_inverted_index.advanced | 11 |
| abstract_inverted_index.advances | 20 |
| abstract_inverted_index.approach | 60 |
| abstract_inverted_index.compared | 216 |
| abstract_inverted_index.designed | 177 |
| abstract_inverted_index.executed | 122 |
| abstract_inverted_index.expected | 97 |
| abstract_inverted_index.features | 12 |
| abstract_inverted_index.oracles. | 39 |
| abstract_inverted_index.queries. | 162 |
| abstract_inverted_index.randomly | 78 |
| abstract_inverted_index.retrieve | 112 |
| abstract_inverted_index.superior | 211 |
| abstract_inverted_index.testers. | 220 |
| abstract_inverted_index.testing, | 23 |
| abstract_inverted_index.automated | 58 |
| abstract_inverted_index.databases | 1, 67 |
| abstract_inverted_index.detecting | 62 |
| abstract_inverted_index.detection | 215 |
| abstract_inverted_index.elements, | 91 |
| abstract_inverted_index.implement | 164 |
| abstract_inverted_index.indicates | 142 |
| abstract_inverted_index.introduce | 51 |
| abstract_inverted_index.key-value | 93 |
| abstract_inverted_index.remaining | 200 |
| abstract_inverted_index.selecting | 83 |
| abstract_inverted_index.approaches | 29 |
| abstract_inverted_index.associated | 88 |
| abstract_inverted_index.generating | 79 |
| abstract_inverted_index.identified | 45 |
| abstract_inverted_index.limitation | 26 |
| abstract_inverted_index.overlooked | 48 |
| abstract_inverted_index.previously | 185 |
| abstract_inverted_index.production | 190 |
| abstract_inverted_index.properties | 87 |
| abstract_inverted_index.synthesize | 156 |
| abstract_inverted_index.techniques | 154 |
| abstract_inverted_index.undetected | 201 |
| abstract_inverted_index.Synthesis), | 55 |
| abstract_inverted_index.discrepancy | 132 |
| abstract_inverted_index.established | 72 |
| abstract_inverted_index.extensively | 147 |
| abstract_inverted_index.incorrectly | 44 |
| abstract_inverted_index.synthesizer | 175 |
| abstract_inverted_index.synthesizes | 107 |
| abstract_inverted_index.demonstrates | 210 |
| abstract_inverted_index.incorporates | 170 |
| abstract_inverted_index.increasingly | 4 |
| abstract_inverted_index.semantically | 160 |
| abstract_inverted_index.specifically | 176 |
| abstract_inverted_index.Additionally, | 207 |
| abstract_inverted_index.applications. | 8 |
| abstract_inverted_index.effectiveness | 212 |
| abstract_inverted_index.syntactically | 158 |
| abstract_inverted_index.state-of-the-art | 219 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.4624923 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |