Graph database systems store graph data as nodes and relationships, and utilize graph query languages (e.g., Cypher) for efficiently querying graph data. Proving the equivalence of graph queries is an important foundation for optimizing graph query performance, ensuring graph query reliability, etc. Although researchers have proposed many SQL query equivalence provers for relational database systems, these provers cannot be directly applied to prove the equivalence of graph queries. The difficulty lies in the fact that graph query languages (e.g., Cypher) adopt significantly different data models (property graph model vs. relational model) and query patterns (graph pattern matching vs. tabular tuple calculus) from SQL. In this paper, we propose GraphQE, an automated prover to determine whether two Cypher queries are semantically equivalent. We design a U-semiring based Cypher algebraic representation to model the semantics of Cypher queries. Our Cypher algebraic representation is built on the algebraic structure of unbounded semirings, and can sufficiently express nodes and relationships in property graphs and complex Cypher queries. Then, determining the equivalence of two Cypher queries is transformed into determining the equivalence of the corresponding Cypher algebraic representations, which can be verified by SMT solvers. To evaluate the effectiveness of GraphQE, we construct a dataset consisting of 148 pairs of equivalent Cypher queries. Among them, we have successfully proven 138 pairs of equivalent Cypher queries, demonstrating the effectiveness of GraphQE.

Database Management Systems (DBMSs) utilize transactions to guarantee data consistency and integrity. Incorrect implementations of transaction processing mechanisms can introduce critical transaction bugs, which can lead to incorrect database states after the involved transactions complete. However, we lack an effective test oracle to determine whether a DBMS produces a correct database state for a given concurrent transaction schedule. In this paper, we propose a general property for concurrent transaction schedules, write-specific serializability , in which a schedule of concurrent transactions should produce the same database state as a corresponding serial schedule of the same transactions. Through our empirical study on 35 critical transaction bugs collected from six widely-used DBMSs, we find that write-specific serializability can be an effective test oracle to expose critical transaction bugs in DBMSs. We further develop a simple and general transaction testing approach, WriteCheck, to automatically detect write-specific serializability violations by identifying inconsistencies in the final database states produced by the original transaction schedule and its corresponding serial schedule. We evaluate WriteCheck on the latest versions of six production-grade DBMSs, and have found 22 write-specific serializability violations, 11 of which have been confirmed as new critical transaction bugs.

Relational Database Management Systems (DBMSs) provide flexible DDL (Data Definition Language) statements that enable the creation, modification, and deletion of database schemas. In addition to database schemas, relational DBMSs typically manage various schema-related information internally, e.g., schema changes, tablespace allocation, and block-level data layout. However, incorrect implementations related to schema-related information maintenance and utilization can introduce schema-related logic bugs. These bugs can cause DQL (Data Query Language) statements to return incorrect query results and DML (Data Manipulation Language) statements to create incorrect database states. Existing approaches mainly focus on detecting logic bugs in DQL statements, but are ineffective in detecting schema-related logic bugs. In this paper, we propose a novel and general testing approach, DDLCheck, to effectively detect schema-related logic bugs in relational DBMSs. We first generate a complex DDL sequence seq gen that consists of various types of DDL statements, and then synthesize a rather simple DDL sequence seq syn , which utilizes CREATE statements to create the same database schema as seq gen . Executing the same SQL statements on the two databases created by seq gen and Seq syn should yield the same execution results. Any discrepancy between their execution results indicates a schema-related logic bug. To improve the testing efficiency of DDLCheck, we further design a DDL-sequence-oriented testing optimization strategy, which can help DDLCheck explore diverse schema-related information and detect schema-related logic bugs quickly. We implement and evaluate DDLCheck on six widely-used relational DBMSs. We have detected 34 bugs in these DBMSs, of which 29 bugs have been confirmed as previously unknown bugs and 9 bugs have been fixed.

Streaming graph computation has been widely applied in many fields, e.g., social network analysis and online product recommendation. However, existing streaming graph computation approaches still present limitations on accuracy and efficiency. To improve the accuracy, some distributed systems use the sequential graph update method based on an incremental computation model. However, these systems cannot handle the dynamic graph update concurrently. The speculation-based parallel updating model can parallelize the graph computation, however, it is restricted due to ignoring the original messages when updating a graph. Streaming graph computation usually requires high accuracy and low latency. As such, it is challenging to utilize incremental computation while simultaneously supplying concurrent processing guarantees.To overcome these challenges, in this paper, we first analyze a number of classical graph algorithms and summarize three principles that graph algorithms should satisfy in streaming scenarios. Based on these principles, we propose GraphFlow, a streaming graph computation model. GraphFlow achieves fast and accurate computation by utilizing incremental state update and propagation. To reduce the impact of concurrent update conflicts, GraphFlow provides a fine-grained lock based parallel update strategy. We implement GraphFlow framework and evaluate its performance and concurrent update conflict probability on real-world datasets. Meanwhile, we compare GraphFlow with two existing representative graph processing systems. Experimental results show GraphFlow achieves low latency and outperforms other graph processing systems given large datasets.

Transactions are used to guarantee data consistency and integrity in Database Management Systems (DBMSs), and have become an indispensable component in DBMSs. However, faulty designs and implementations of DBMSs' transaction processing mechanisms can introduce transaction bugs, and lead to severe consequences, e.g., incorrect database states and DBMS crashes. An in-depth understanding of real-world transaction bugs can significantly promote effective techniques in combating transaction bugs in DBMSs.

Graph database systems (GDBs) allow efficiently creating, modifying, and retrieving graph data in a graph database. To accelerate graph queries, GDBs usually adopt various and complex optimization strategies. However, incorrect optimizations in GDBs can introduce optimization bugs, which cause a graph query to compute an incorrect query result, e.g., omitting a vertex in a graph database. In this paper, we propose Differential Optimization Testing (DOT), an effective and automated approach to detect optimization bugs in GDBs that adopt Gremlin as their query language. The main idea of DOT is that, given a Gremlin query$Q$, we execute it on the target GDB with two different optimization configurations and then verify whether they can compute the same query results for query$Q$. Any inconsistency between their query results indicates an optimization bug in the target GDB. To improve the efficiency of differential testing in DOT, we further propose an optimization-guided approach, aiming to explore more optimization strategies and more graph database features. We evaluate DOT on six popular and widely-used GDBs, i.e., Neo4j, OrientDB, JanusGraph, HugeGraph, TinkerGraph, and ArcadeDB. In total, we have found 28 unique optimization bugs, 16 of which have been confirmed as previously-unknown bugs.

Graph Database Systems (GDBs) support efficiently storing and retrieving graph data, and have become a critical component in many important applications. Many widely-used GDBs utilize the Gremlin query language to create, modify, and retrieve data in graph databases, in which developers can assemble a sequence of Gremlin APIs to perform a complex query. However, incorrect implementations and optimizations of GDBs can introduce logic bugs, which can cause Gremlin queries to return incorrect query results, e.g., omitting vertices in a graph database. In this paper, we propose Query Di sassembling (QuDi), an effective testing technique to automatically detect logic bugs in Gremlin-based GDBs. Given a Gremlin query Q, QuDi disassembles Q into a sequence of atomic graph traversals TList, which shares the equivalent execution semantics with Q. If the execution results of Q and TList are different, a logic bug is revealed in the target GDB. We evaluate QuDi on six popular GDBs, and have found 25 logic bugs in these GDBs, 10 of which have been confirmed as previously-unknown bugs by GDB developers.

Database Management Systems (DBMSs) are widely used to efficiently store and retrieve data. DBMSs usually support various metadata, e.g., integrity constraints for ensuring data integrity and indexes for locating data. DBMSs can further utilize these metadata to optimize query evaluation. However, incorrect metadata-related optimizations can introduce metadata-related logic bugs, which can cause a DBMS to return an incorrect query result for a given query. In this paper, we propose a general and effective testing approach, Raw database construction (Radar), to detect metadata-related logic bugs in DBMSs. Given a database db containing some metadata, Radar first constructs a raw database rawDb , which wipes out the metadata in db and contains the same data as db. Since db and rawDb have the same data, they should return the same query result for a given query. Any inconsistency in their returned query results indicates a metadata-related logic bug. To effectively detect metadata-related logic bugs, we further propose a metadata-oriented testing optimization strategy to focus on testing previously unseen metadata, thus detecting more metadata-related logic bugs quickly. We implement and evaluate Radar on five widely-used DBMSs, and have detected 42 bugs, of which 38 have been confirmed as new bugs and 16 have been fixed by DBMS developers.

Graph database systems (GDBs) allow efficiently storing and retrieving graph data, and have become the critical component in many applications, e.g., knowledge graphs, social networks, and fraud detection. It is important to ensure that GDBs operate correctly. Logic bugs can occur and make GDBs return an incorrect result for a given query. These bugs are critical and can easily go unnoticed by developers when the graph and queries become complicated. Despite the importance of GDBs, logic bugs in GDBs have received less attention than those in relational database systems.

Graph algorithms are widely applied in social networks, computational biology, Internet security and a broad range of complexity science. Although there are many state-of-the-art graph frameworks, few frameworks support parallel graph mining in joint cloud computing environment. In this paper, we propose GraphLib, a parallel graph mining library, based on a BSP (Bulk Synchronous Parallel) service over joint cloud computing which was proposed in our prior work. We first summarize the features of commonly-used graph mining algorithms, and present our approaches for parallelizing typical graph mining algorithms. GraphLib includes 17 parallel graph mining algorithms that can be used in 3 scenarios. We evaluate the performance of 4 typical parallel graph algorithms in GraphLib on three real-world datasets. Our parallelized algorithms can achieve sub-linear scalability.

Stream processing system (SPS) faces the problem of node failure when running over a long period of time. In addition, "exactly once" precise semantic guarantee is more and more important for SPS in some scenarios. In general, the approaches to achieve precise semantic is by using global snapshot, which should store state and records to external reliable storage or rely on transactions. However, these approaches suffer from high recovery latency, because of large I/O disk overhead. In order to reduce excessive latency in failure recovery, we save the intermediate results which are produced during the stream processing, and propose an algorithm DCAS which asynchronously snapshots state to implements precise recovery. In addition, we use in-memory distributed cache to provide the storage of intermediate results and snapshots to reduce recovery latency. We evaluate our failure recovery approach in recovery latency and runtime overhead. The experimental results show that our approach is 2 to 6 times faster than other conventional failure recovery approaches, and induces a 6% runtime overhead.