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.

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.

Boolean expression matching plays an important role in many applications. However, existing solutions still show efficiency and scalability limitations. For example, existing solutions often exhibit degraded performance when applied to high-dimensional and diverse workloads, and existing algorithms rarely consider supporting concurrent matching and index updating under multicore environments. To overcome these limitations, in this article, we first design the PS-Tree data structure to efficiently index Boolean expressions in one dimension. By dividing predicates into disjoint predicate spaces, PS-Tree achieves high matching performance and good expressiveness. Based on the PS-Tree , we propose a Boolean expression matching algorithm called PSTDynamic . By dynamically adjusting the index and efficiently filtering out a large proportion of unmatching expressions, PSTDynamic achieves high matching performance under high-dimensional and diverse workloads. For multicore environment, we further extend the PSTDynamic algorithm to PSTParallel to achieve scalability with lower matching latency and higher matching throughput. We run experiments on both synthetic and real-world datasets. The experiments verify that our proposed algorithms show high efficiency and parallelism. Moreover, they also achieve fast index construction and a small memory footprint. Comprehensive experiments show that our solutions drastically outperform state-of-the-art methods.

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.

Popular big data frameworks, ranging from Hadoop MapReduce to Spark, rely on garbage-collected languages, such as Java and Scala. Big data applications are especially sensitive to the effectiveness of garbage collection (i.e., GC), because they usually process a large volume of data objects that lead to heavy GC overhead. Lacking in-depth understanding of GC performance has impeded performance improvement in big data applications. In this paper, we conduct the first comprehensive evaluation on three popular garbage collectors, i.e., Parallel, CMS, and G1, using four representative Spark applications. By thoroughly investigating the correlation between these big data applications' memory usage patterns and the collectors' GC patterns, we obtain many findings about GC inefficiencies. We further propose empirical guidelines for application developers, and insightful optimization strategies for designing big-data-friendly garbage collectors.

As one database offloading strategy, elastic key-value stores are often introduced to speed up the application performance with dynamic scalability. Since the workload is varied, efficient data migration with minimal impact in service is critical for the issue of elasticity and scalability. However, due to the new virtualization technology, real-time and low-latency requirements, data migration within cloud-based key-value stores has to face new challenges: effects of VM interference, and the need to trade off between the two ingredients of migration cost, namely migration time and performance impact. To fulfill these challenges, in this paper we explore a new approach to optimize the data migration. Explicitly, we build two interference-aware models to predict the migration time and performance impact for each migration action using statistical machine learning, and then create a cost model to strike a balance between the two ingredients. Using the load rebalancing scenario as a case study, we have designed one cost-aware migration algorithm that utilizes the cost model to guide the choice of possible migration actions. Finally, we demonstrate the effectiveness of the approach using Yahoo! Cloud Serving Benchmark (YCSB).