The query optimizer is a fundamental component of database management systems that determines the most efficient execution strategy for a given query by evaluating alternative query plans. Among its tasks, join optimization plays a central role, as the order of joins in multi-table queries can significantly affect execution performance. However, due to the inherent complexity of join optimization, logical bugs are inevitable and often difficult to detect. While existing fuzzing tools have shown notable success in uncovering crash- and performance-related errors, effectively identifying logical bugs -- cases in which the system produces incorrect query results -- remains largely unresolved. In this paper, we propose a metamorphic testing approach to detect DBMS bugs related to INNER JOIN optimization through the lens of set theory. For each testing case, equivalent queries are generated based on a basic set operation -- intersection -- and three semantics-preserving transformation rules, i.e., symmetric join transformation, asymmetric difference transformation, and symmetric difference transformation, are introduced. These rules rewrite a simple NATURAL/INNER JOIN query into a more complex, yet semantically equivalent, form. We implement this design in JoinEquiv, which serves as a testing oracle to systematically uncover logical inconsistencies in DBMS query processing by comparing the results of original and transformed queries. Using JoinEquiv, we uncovered 29 previously unknown issues in mainstream DBMSs (MySQL, TiDB, DuckDB, and Percona), and 27 of them were officially confirmed. JoinEquiv reveals deep logical flaws in DBMS optimizers and executors, underscoring its value in enhancing DBMS robustness.

This paper investigates the feasibility of achieving zero-knowledge verifiability for graph databases, enabling database owners to cryptographically prove the query execution correctness without disclosing the underlying data. Although similar capabilities have been explored for relational databases, their implementation for graph databases presents unique challenges. This is mainly attributed to the relatively large complexity of queries in graph databases. When translating graph queries into arithmetic circuits, the circuit scale can be too large to be practically evaluated. To address this issue, we propose to break down graph queries into more fine-grained, primitive operators, enabling a step-by-step evaluation through smaller-scale circuits. Accordingly, the verification with ZKP circuits of complex graph queries can be decomposed into a series of composable cryptographic primitives, each designed to verify a fundamental structural property such as path ordering or edge directionality. Especially, having noticed that the graph expansion (i.e., traversing from nodes to their neighbors along edges) operation serves as the backbone of graph query evaluation, we design the expansion centric operator decomposition. In addition to constructing circuits for the expansion primitives, we also design specialized ZKP circuits for the various attributes that augment this traversal. The circuits are meticulously designed to take advantage of PLONKish arithmetization. By integrating these optimized circuits, we implement ZKGraph, a system that provides verifiable query processing while preserving data privacy. Performance evaluation indicates that ZKGraph significantly outperforms naive in circuit implementations of graph operators, achieving substantial improvements in both runtime and memory consumption.

Various real-world graphs, such as social and transaction networks, are typically distributed across users, each of whom holds a local view of the graph (i.e., their own relationships with others). Densest Subgraph Discovery (DSD) on such decentralized graphs is a fundamental task that can uncover valuable insights for downstream applications, including fraud detection, community identification, and user behavior mining. Additionally, in many scenarios, due to privacy concerns, sensitive original local views cannot be collected for DSD. Although there have been extensive studies on DSD, most existing algorithms either do not take user privacy into account or are specific to the centralized privacy setting that requires a (trusted) curator to collect all local views from users and then analyze the entire graph privately.

Inverted index is a basic tool in many data-intensive applications. Though numerous efforts have been made on efficient inverted index-based query processing, existing schemes do not achieve the expected performance for modern data centers, in which servers are equipped with powerful CPUs and relatively large memory. Through comprehensive measurement studies, we identify the root course is that the data formats for index representation make it unfeasible to design efficient query execution approaches on top of it, which results in poor parallel query support and waste CPU computation. Driven by the findings, we propose to reconcile the in-memory index as columnar structures. To enable this idea, we construct the compact columnar format (i.e., Cocoa) that achieves both desirable space efficiency and maintains the capability for efficient searching support. With Cocoa, we design an efficient query executing scheme that utilizes vectorized batch processing to avoid frequent branch prediction, as well as clause enumeration with pruning to save the overhead of intermediate batch materialization. We build an open-source system VeloSearch to embody our design; experimental results show that VeloSearch achieves ~30× better performance compared with state-of-the-art search libraries such as Lucene and Tantivy.

Abstract Distributed in-memory databases are widely adopted to achieve low latency and high bandwidth for data-intensive applications. They support scale-out by sharding and distributing data across multiple nodes. To efficiently adapt to various workloads, distributed in-memory databases must be capable of migrating shards across nodes. In this paper, we demonstrate that state-of-the-art approaches experience significant performance degradation during migration due to service downtime and redundant data transfer. Furthermore, our findings indicate that the presence of service downtime constrains the scalability of migration strategies, while the transfer of redundant data during the snapshot transfer phase limits their adaptability to dynamic workloads. To this end, this paper proposes Aion, a live migration strategy designed for distributed in-memory databases. Aion eliminates any potential service downtime by immediately switching transaction routing to the destination node. To ensure data consistency between the source and destination nodes, as well as serializable execution during migration, Aion proposes the mutual validation phase. Moreover, Aion introduces an analysis phase before the snapshot transfer phase to identify dynamically changing hotspots in workloads. The analysis phase identifies and transfers tuples and versions accessed less frequently to the destination node, reducing the amount of data transferred. Aion is implemented on a distributed in-memory database and evaluated using various OLTP workloads. The results demonstrate that Aion can fundamentally eliminate service downtime, adapt effectively to various workloads and exhibit robust scalability. Compared to state-of-the-art approaches, Aion achieves up to 2.25x–6.57x higher throughput during migration and shortens the migration duration by 53.7–68.2%.

Payment channel networks (PCNs) are generally regarded as one of the most effective and promising scalability solutions for blockchain-based cryptocurrency systems, but suffer the issues of low success ratio and long confirmation latency in processing transactions. In this paper, we demonstrate the feasibility of tremendously increasing the success ratio of transactions and improving their execution efficiency by enhancing network nodes' connectivity and enforcing a balanced network channel capacity. To implement such ideas, multiple designs have been made. First, to extent nodes connectivity, we transform the nearly-linear ordered nodes into a star payment structured typology, and design an incentive financing mechanism to restructure a new landmark routing typology design. Especially, for the marginalized or dissociative nodes, we utilize specific financial loan strategies to encourage them to (re)join the system. Besides, we propose the Power Atomic Multi-Path Payments (Power AMP) traffic distribution method, which hierarchically allocates the bottleneck's currently-available capacity (to replace the random or equal division used in traditional AMP), and thus archives a balanced traffic usage. With such efforts, we improve the transaction success ratio and efficiency of transaction exertion by order of magnitude—compared with traditional PCN using the benchmark of landmark route, our method improves the success ratio by 11.06%.

Machine unlearning is the process through which a deployed machine learning model is enforced to forget about some of its training data items. It normally generates two machine learning models, the original model and the unlearned model, indicating training results before and after data items are deleted. However, recent studies find that machine unlearning is vulnerable to membership inference attacks—as the directivity of training and nontraining data (i.e., data items in the training set have high posterior probabilities), the attackers can utilize this property to infer whether an item has been used for original model training. Nevertheless, such attacks are incapable in label-only settings, in which the attackers are infeasible to get the posteriors. In this paper, we propose a new label-only membership inference attack scheme targeted at machine unlearning to eliminate the dependence on posteriors. Our heuristic is that injected turbulence on candidate samples will present different behaviors for training and nontraining data. Thus, in our scheme, the attacker iteratively query on the original/unlearned models and inject turbulence to change their predicting labels; it determines whether an item is having-been-delated by observing the disturbance amplitude. Extensive experiments (i.e., on MNIST, CIFAR10, CIFAR100, and STL10 data sets) show that our method achieves high inference accuracy (measured by AUC) in label-only settings, for example, AUC = 0.96 for MNIST data set. Besides, we analyze the existing countermeasures in mitigating inference attacks and find that our scheme can bypass most of them.