Testing Graph Databases with Synthesized Queries
Read the paper · doi:10.1145/3749186
What this paper does with SQLancer
TLP reaches this paper through GDBMeter, which the authors describe as adopting the metamorphic oracles from TLP, originally designed for SQL, and partitioning queries using three-valued logic. That inheritance is the limitation they identify: a three-valued oracle applies only to filter clauses such as WHERE, and they show a case where all three of GDBMeter's partitioned queries return empty results and so reveal nothing. GDBMeter is one of four metamorphic detectors compared against. PQS is discussed as the closest relational analogue -- it also synthesises queries -- but is distinguished on the grounds that it relies on a subset relationship rather than establishing ground truth.
This work tests graph databases by synthesising queries whose correct result is known by construction, so the oracle does not depend on comparing two queries. That distinguishes it from the metamorphic graph testers, which detect only discrepancies between an original and a rewritten query and are therefore bounded by what their rewrite rules can express. It reports bugs in Neo4j, RedisGraph and Memgraph that the existing detectors do not find.
How it was classified
uses infrastructure — no
The comparison tools are graph testers run as baselines; nothing describes reuse of the SQLancer codebase.
extends technique — no
The oracle is ground truth established by construction, which M15 contrasts with the subset relationships PQS relies on. It is an alternative to those oracles rather than a development of one.
compares with — yes
M9 lists GDBMeter among the metamorphic bug detectors compared against, and M10 works through what GDBMeter's ternary logic partitioning produces on a test query. M13 identifies GDBMeter's oracle as TLP's, carried over from SQL.
Ternary Logic Partitioning (TLP)
•The metamorphic bug detectors, GDBMeter [ 22], Gamera [ 62], GQT [ 19], and GRev [ 33], each applying specifically designed query rewrite rules to identify discrepancies between the result of the original query and that of the rewritten query.
Upon applying GDBMeter’s ternary logic partitioning [ 22] to the test query, all three partitioned queries (lines 5–13) also produce empty results.
describes as state of the art — no
The section is headed as a comparison with state-of-the-art tools, but no sentence attributes that standing to TLP, PQS or SQLancer specifically.
SQLancer publications it cites (7)
Bibliography entries that resolved to a SQLancer publication, or to a paper by one of the project's authors. A sentence citing one of these numbers is a reference to SQLancer even when it never writes the name.
| # | Entry | Matched as |
|---|---|---|
| 3 | Jinsheng Ba and Manuel Rigger. 2024. Keep It Simple: Testing Databases via Differential Query Plans. | sqlancer publication · DQP |
| 19 | Yuancheng Jiang, Jiahao Liu, Jinsheng Ba, Roland H. C. Yap, Zhenkai Liang, and Manuel Rigger. 2024. Detecting Logic Bugs in Graph Database Management Systems via Injective and Surjective Graph Query Transformation. In... | project authored |
| 20 | Zu-Ming Jiang, Si Liu, Manuel Rigger, and Zhendong Su. 2023. Detecting Transactional Bugs in Database Engines via Graph-Based Oracle Construction. InOSDI ’23. 397–417. | project authored |
| 22 | Matteo Kamm, Manuel Rigger, Chengyu Zhang, and Zhendong Su. 2023. Testing Graph Database Engines via Query Partitioning. InISSTA ’23. ACM, 140–149. | project authored |
| 45 | Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. InESEC/FSE ’20. ACM, 1140–1152. | sqlancer publication · NOREC |
| 46 | Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning.Proc. ACM Program. Lang.4, OOPSLA, Article 211 (nov 2020), 30 pages. | sqlancer publication · TLP |
| 47 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. InOSDI ’20. USENIX Association, 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (16)
16 sentences, each stored verbatim from the extracted text with where it was found and how. “Citation marker” means the sentence names no tool at all and was reached through a reference number that resolved to a SQLancer publication.
| Id | Sentence | Found by | Where |
|---|---|---|---|
| M1 | Such logic bugs are widely recognized as being more challenging to detect than database crashes or exceptions [19, 47, 54, 62]. |
citation marker |
1 Introduction page 1 |
| M2 | Recent research has produced excellent testers [ 16,19,22,33,61,62] that attempt to address this challenge. |
citation marker project authored |
1 Introduction page 2 |
| M3 | In line with the growing trend of using randomized testing to effectively uncover system-level bugs in general [ 23,31] and relational databases in particular [ 20,47,54], these tools all generate random graph data and queries to exercise the GDB under test. |
citation marker |
1 Introduction page 2 |
| M4 | For instance, the Grand tool [ 61] was recently found to report a large number of false alarms [22, 62]. |
citation marker project authored |
1 Introduction page 2 |
| M5 | Metamorphic testers [ 19,22,33,62] avoid false positives by design. |
citation marker project authored |
1 Introduction page 2 |
| M6 | , whether one result set is equivalent to another [ 33], is a subset of another [ 19], or is a union of multiple other result sets [ 22,62]. |
citation marker project authored |
1 Introduction page 2 |
| M7 | For instance, GDBMeter [ 22] bases its test oracle on a three-valued logic, which can be used only to filter clauses like WHERE (in Cypher language [ 11]). |
citation marker project authored |
1 Introduction page 2 |
| M8 | Previous work [ 16,47] provides a good basis for generating complex expressions in general, likechar_length(‘abc’)+sqrt(round(1. |
citation marker |
3.5 Generating Complex Expressions page 12 |
| M9 | •The metamorphic bug detectors, GDBMeter [ 22], Gamera [ 62], GQT [ 19], and GRev [ 33], each applying specifically designed query rewrite rules to identify discrepancies between the result of the original query and that of the rewritten query. |
citation marker project authored |
5.4 Comparison with State-of-the-Art page 18 |
| M10 | Upon applying GDBMeter’s ternary logic partitioning [ 22] to the test query, all three partitioned queries (lines 5–13) also produce empty results. |
citation marker project authored |
5.4 Comparison with State-of-the-Art page 20 |
| M11 | 1UNWIND [1,2,3] AS a0 2MATCH (n2 :L12)-[r1]-(n3) WHERE (((r1. |
citation marker |
5.4 Comparison with State-of-the-Art page 21 |
| M12 | In recent years, a wide range of logic bug detectors have been developed for RDBs [ 3,15,20,21,46,47,49,50,54]. |
citation marker |
6 Related Work page 22 |
| M13 | GDBMeter illustrates this by adopting the metamorphic oracles from TLP [ 46], originally designed for SQL, which partitions queries using three-valued logic. |
technique |
6 Related Work page 22 |
| M14 | Similar to our approach, PQS [ 47], Pinolo [ 15], and TQS [ 54] test RDBs by synthesizing SQL queries. |
technique |
6 Related Work page 22 |
| M15 | However, PQS and Pinolo cannot establish the ground truth and, instead, rely on subset relationships as test oracles—an approach that doesnotguarantee the correctness of individual queries. |
technique |
6 Related Work page 22 |
| M16 | 268:24 Zijing Yin, Si Liu, & David Basin of ground truth on the expected execution time, where the cardinality estimation approach [ 45] designed for RDBs may provide a direction for future research. |
citation marker |
7 Discussion and Concluding Remark page 23 |