Testing Graph Databases with Synthesized Queries

Summary: GQS automates GDB testing by generating a ground truth graph with results, then synthesizing retrieval queries. It introduces syntactic and semantic query synthesis, including a Cypher tester, and finds 36 previously unknown bugs (26 logic) across four GDBs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7533
Venue: SIGMOD
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,331 | 29.13%
DOI: 10.1145/3749186

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Zijing Yin (ETH Zurich)
2. Si Liu (ETH Zurich)
3. David Basin (ETH Zurich)

BibTeX Citation

@inproceedings{yin_sigmod26,
        title = {{Testing Graph Databases with Synthesized Queries}},
        author = {Yin, Zijing and Liu, Si and Basin, David},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3749186},
        url = {https://dl.acm.org/doi/10.1145/3749186},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,597	Fast Verification of Strong Database Isolation	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,080	Elle: Inferring Isolation Anomalies from Experimental Observations	2021	VLDB	0.00012257972
1,187	Highly Available Transactions: Virtues and Limitations	2014	VLDB	0.00011760199
2,044	Detecting Logic Bugs of Join Optimizations in DBMS	2023	SIGMOD	9.2663577e-05
3,903	Keep It Simple: Testing Databases via Differential Query Plans	2024	SIGMOD	7.0304586e-05
4,129	Testing Graph Database Systems via Graph-Aware Metamorphic Relations	2024	VLDB	6.8840169e-05
5,429	Detecting Metadata-Related Logic Bugs in Database Systems via Raw Database Construction	2024	VLDB	6.222006e-05
5,438	PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns	2021	VLDB	6.2195845e-05
8,715	Efficient Black-box Checking of Snapshot Isolation in Databases	2023	VLDB	5.3777365e-05
9,857	NOC-NOC: Towards Performance-optimal Distributed Transactions	2024	SIGMOD	5.2079113e-05
10,820	VerIso: Verifiable Isolation Guarantees for Database Transactions	2025	VLDB	5.093636e-05
11,311	IsoVista: Black-box Checking Database Isolation Guarantees	2024	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,227	Detecting Schema-Related Logic Bugs in Relational DBMSs via Equivalent Database Construction	2025	VLDB
2	10,402	SRS: Detecting Logic Bugs of Join Implementation in DBMSs via Set Relation Synthesis	2026	SIGMOD
3	5,429	Detecting Metadata-Related Logic Bugs in Database Systems via Raw Database Construction	2024	VLDB
4	8,482	A Demonstration of DLBD: Database Logic Bug Detection System	2023	VLDB
5	7,427	Constant Optimization Driven Database System Testing	2025	SIGMOD
6	10,199	Automated Discovery of Test Oracles for Database Management Systems Using LLMs	2026	SIGMOD
7	3,903	Keep It Simple: Testing Databases via Differential Query Plans	2024	SIGMOD
8	10,522	Dinkel: State-Aware and Granular Framework for Validating Graph Databases	2026	VLDB
9	2,044	Detecting Logic Bugs of Join Optimizations in DBMS	2023	SIGMOD
10	4,129	Testing Graph Database Systems via Graph-Aware Metamorphic Relations	2024	VLDB