Testing Graph Database Systems via Equivalent Query Rewriting
Read the paper · doi:10.1145/3597503.3639200
What this paper does with SQLancer
The paper works from Ternary Logic Partitioning throughout, but at one remove: its comparison target is GDBMeter, which carries TLP to graph databases, and the paper is precise that GDBMeter is based on Query Partitioning and reuses a test oracle designed for relational systems. That reuse is its critique -- it reports that none of the graph-related bugs were detected by GDBMeter for exactly that reason, that TLP applies only to filter clauses, and that partitioning yields four distinct query plans against GRev's many. It states outright that GRev cannot be compared with relational tools such as SQLancer, so SQLancer itself is not a baseline; TLP is, through GDBMeter.
GRev tests graph database systems by rewriting a Cypher query into a form that must return the same result, then comparing the two. Its argument against the existing metamorphic approach is that partitioning a query into sub-queries yields only a handful of distinct query plans and cannot express graph-specific constructs, so graph-related bugs go undetected. GRev found bugs in Neo4j, RedisGraph and MemGraph that the existing tools had not.
How it was classified
uses infrastructure — no
GRev is compared with GDBMeter rather than built on it, and M13 states that GRev cannot be compared with relational tools such as SQLancer at all.
extends technique — no
GRev rewrites a query into an equivalent one rather than partitioning it, which the paper presents as an alternative to TLP rather than a generalisation. Its treatment of TLP is a critique of carrying a relational oracle to graphs.
compares with — yes
M6 and M11 name GDBMeter among the tools GRev is evaluated against, and M18 and M20 report the outcome and attribute it to GDBMeter's reuse of TLP. The comparison reaches TLP through GDBMeter, which M12 and M14 identify as a Query Partitioning tool; M13 states SQLancer itself was not compared against.
Ternary Logic Partitioning (TLP)
, GDsmith [ 13], Grand [ 44], and GDBMeter [ 15]).
, GDsmith [ 13], Grand [ 44], and GDBMeter [ 15], that can detect bugs other than crashes.
For example, as shown in Listing 5, the TLP approach fails to generate bug-triggering test cases for the graphrelated bugs shown in Listing 2.
However, none of the graph-related bugs have been detected by it due to reusing TLP[ 32], a metamorphic relation for RDBMS.
describes as state of the art — yes
M19 calls GDBMeter the SOTA tool for detecting logic bugs in graph database systems. The recognition attaches to the TLP-based tool rather than to SQLancer directly.
Based on metamorphic testing, GDBMeter [ 15] is the SOTA tool for detecting logic bugs in GDBMS.
SQLancer publications it cites (4)
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 |
|---|---|---|
| 2 | Jinsheng Ba and Manuel Rigger. 2023. Testing Database Engines via Query Plan Guidance. In (ICSE). 2060โ2071. https://doi.org/10.1109/ICSE48619.2023.00174 | sqlancer publication · QPG |
| 15 | Matteo Kamm, Manuel Rigger, Chengyu Zhanga, and Zhendong Su. 2023. Testing Graph Database Engines via Query Partitioning. In Proceedings of the 32nd ACMSIGSOFT International Symposium on Software Testing and Analysis. | project authored |
| 32 | 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. https://doi.org/10.1145/3428279 | sqlancer publication · TLP |
| 33 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis.. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), Vol. 20. 667โ682. | sqlancer publication · PQS |
Every place it refers to SQLancer (20)
20 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 | Second, it is non-trivial to adapt RDBMS testing approaches [ 2, 32,33,36] to GDBMS because it incurs re-implementation under different database models and query languages. |
citation marker |
1 INTRODUCTION page 2 |
| M2 | For example, GDBMeter [ 15], the only existing metamorphic testing approach for GDBMS, utilizes an RDBMS testing approach Ternery Logic Partitioning (TLP) [32], which partitions a query ๐into sub-queries ๐๐,๐ยฌ๐,๐nullbased on three possible outcomes of the predicate ๐:true, false, and null. |
technique |
1 INTRODUCTION page 2 |
| M3 | The metamorphic testing approach, GDBMeter [ 15], is based on the relationship between the original query and three sub-queries, which do not exhibit clear performance relationships. |
citation marker project authored |
1 INTRODUCTION page 2 |
| M4 | 2 Graph Generation Unlike some testing techniques [ 13,15] that are specific to particular data, our EQR approach can be generally applied to any graph. |
citation marker project authored |
4.2 Graph Generation page 5 |
| M5 | Similarly, GDBMeter [ 15], a tool based on Query Partitioning [ 32], requires different validation rules for different queries and may struggle to handle some widely-used clauses such as DISTINCT. |
technique |
4.3 Base Query Generator page 5 |
| M6 | , GDsmith [ 13], Grand [ 44], and GDBMeter [ 15]). |
citation marker project authored |
5.1 Experimental Setting page 6 |
| M7 | Notably, these bugs were rarely detected by the existing techniques, especially for GDBMeter [ 15], which reused the test oracles designed for RDBMS (i. |
citation marker project authored |
5.2 Detecting Previously Unknown Bugs page 7 |
| M8 | , TLP [32]). |
technique |
5.2 Detecting Previously Unknown Bugs page 7 |
| M9 | In contrast, existing techniques based on certain query transformations, such as GDBMeter [ 15], can only trigger 1 (from the base query) + 3 (from three sub-queries) = 4 distinct query plans. |
citation marker project authored |
5.3 Test Cases Analysis page 8 |
| M10 | Consequently, when executing differential testing on Testing Graph Database Systems via Equivalent Query Rewriting ICSE 2024, April 2024, Lisbon, Portugal Table 3: Comparing GRev with Existing Techniques T ool Approach Supp orted LanguagesAble to detect shared bugsAble to test unique featuresInsensitive to base quer... |
technique |
5.3 Test Cases Analysis page 8 |
| M11 | , GDsmith [ 13], Grand [ 44], and GDBMeter [ 15], that can detect bugs other than crashes. |
citation marker project authored |
5.4 Analytical Comparison with Existing page 9 |
| M12 | Specifically, GDsmith and Grand are based on Differential Testing [38] while GDBMeter is based on Query Partitioning [32] (i. |
technique |
5.4 Analytical Comparison with Existing page 9 |
| M13 | Notably, we can not compare GRev with RDBMS testing tools, such as SQLancer [ 33]. |
name |
5.4 Analytical Comparison with Existing page 9 |
| M14 | Based on Query Partitioning, GDBMeter [ 15] leverages the test oracle called Ternary Logic Partitioning (TLP) to detect bugs in GDBMS. |
technique |
5.4 Analytical Comparison with Existing page 9 |
| M15 | TLP [ 32] was initially introduced in testing RDBMS. |
technique |
5.4 Analytical Comparison with Existing page 9 |
| M16 | (TLP :๐๐)MATCH (n0:L3)( n2:L2) WITH *MATCH (n0) ( n2)WITH * WHERE (ID(n2) > ID(n0))RETURN * --{n0: 19244, n1: 19230, n2: 19328, r0: 85207} (TLP :๐ยฌ๐)MATCH (n0:L3)( n2:L2) WITH *MATCH (n0) ( n2)WITH * WHERE NOT (ID(n2) > ID(n0))RETURN *--{} (TLP :๐null)MATCH (n0:L3)( n2:L2) WITH *MATCH (n0) ( n2)WITH * WHERE (ID(n2) ... |
technique |
5.4 Analytical Comparison with Existing page 9 |
| M17 | In addition, TLP can only be applied to filter clauses (e. |
technique |
5.4 Analytical Comparison with Existing page 9 |
| M18 | For example, as shown in Listing 5, the TLP approach fails to generate bug-triggering test cases for the graphrelated bugs shown in Listing 2. |
technique |
5.4 Analytical Comparison with Existing page 9 |
| M19 | Based on metamorphic testing, GDBMeter [ 15] is the SOTA tool for detecting logic bugs in GDBMS. |
citation marker project authored |
7 RELATED WORK page 11 |
| M20 | However, none of the graph-related bugs have been detected by it due to reusing TLP[ 32], a metamorphic relation for RDBMS. |
technique |
7 RELATED WORK page 11 |