ACM TRANSACTIONS ON DATABASE SYSTEMS (TODS) 广泛用于学术和企业研发环境，是从事数据抽象、数据建模和设计数据管理系统的计算机科学家的重要出版物。主题包括存储和检索、事务管理、分布式和联合数据库、数据语义、智能数据库以及与这些领域相关的操作和算法。在这个瞬息万变的领域，TODS 提供了对数据库研发领域最优秀人才思想的洞察。

ACM Transactions on Database Systems (TODS) is an important publication widely used in academic and corporate research and development environments, aimed at computer scientists engaged in data abstraction, data modeling, and the design of data management systems. The topics covered include storage and retrieval, transaction management, distributed and federated databases, data semantics, intelligent databases, and operations and algorithms related to these areas. In this rapidly evolving field, TODS provides insights into the thoughts of the best minds in database research and development.

《ACM Transactions on Database Systems (TODS)》是学术界和企业研发环境中广泛使用的重要期刊，主要面向从事数据抽象、数据建模和数据管理系统设计的计算机科学家。期刊涵盖的主题包括存储与检索、事务管理、分布式和联合数据库、数据语义、智能数据库，以及与这些领域相关的操作和算法。在这个快速发展的领域中，《TODS》为数据库研发领域的优秀人才提供了深刻的见解。

ACM Transactions on Database Systems

Many popular database management systems implement a multiversion concurrency control algorithm called snapshot isolation rather than providing full serializability based on locking. There are well-known anomalies permitted by snapshot isolation that can lead to violations of data consistency by interleaving transactions that would maintain consistency if run serially. Until now, the only way to prevent these anomalies was to modify the applications by introducing explicit locking or artificial update conflicts, following careful analysis of conflicts between all pairs of transactions. This article describes a modification to the concurrency control algorithm of a database management system that automatically detects and prevents snapshot isolation anomalies at runtime for arbitrary applications, thus providing serializable isolation. The new algorithm preserves the properties that make snapshot isolation attractive, including that readers do not block writers and vice versa. An implementation of the algorithm in a relational DBMS is described, along with a benchmark and performance study, showing that the throughput approaches that of snapshot isolation in most cases.

Michael J. Cahill

Uwe Röhm

Alan D. Fekete

Serializable isolation for snapshot databases

快照数据库的可序列化隔离

This paper develops \(\mathsf {Hercules} \) , a system for entity resolution (ER), conflict resolution (CR), timeliness deduction (TD) and missing value/link imputation (MI) in graphs. It proposes \(\mathsf {GCR^{+}\!s} \) , a class of graph cleaning rules that support not only predicates for ER and CR, but also temporal orders to deduce timeliness and data extraction to impute missing data. As opposed to previous graph rules, \(\mathsf {GCR^{+}\!s} \) are defined with a dual graph pattern to accommodate irregular structures of schemaless graphs, and adopt patterns of a star form to reduce the complexity. We show that while the implication and satisfiability problems are intractable for \(\mathsf {GCR^{+}\!s} \) , it is in PTIME to detect and correct errors with \(\mathsf {GCR^{+}\!s} \) . Underlying \(\mathsf {Hercules} \) , we train a ranking model to predict the temporal orders on attributes, and embed it as a predicate of \(\mathsf {GCR^{+}\!s} \) . We provide an algorithm for discovering \(\mathsf {GCR^{+}\!s} \) by combining the generations of patterns and predicates. We also develop a method for conducting ER, CR, TD and MI in the same process to improve the overall quality of graphs, by leveraging their interactions and chasing with \(\mathsf {GCR^{+}\!s} \) ; we show that the method has the Church-Rosser property under certain conditions. Using real-life and synthetic graphs, we empirically verify that \(\mathsf {Hercules} \) is 53% more accurate than the state-of-the-art graph cleaning systems, and performs comparably in efficiency and scalability.

Wenfei Fan

Kehan Pang

Ping Lu

Chao Tian

Making It Tractable to Detect and Correct Errors in Graphs

使检测和纠正图中的错误变得易于处理

Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the last decade, the task of extracting data from nested documents over streams has become especially relevant. We focus on the streaming evaluation of queries with outputs of varied sizes over nested documents. We model queries of this kind as Visibly Pushdown Annotators (VPAnn), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as MSO over nested documents. Since processing a document through a VPAnn can generate a massive number of results, we are interested in reading the input in a streaming fashion and enumerating the outputs one after another as efficiently as possible, namely, with constant delay. This paper presents an algorithm that enumerates these elements with constant delay after processing the document stream in a single pass. Furthermore, we show that this algorithm is worst-case optimal in terms of update-time per symbol and memory usage.

Martín Muñoz

Cristian Riveros

Streaming enumeration on nested documents

嵌套文档的流式枚举

SkinnerDB uses reinforcement learning for reliable join ordering, exploiting an adaptive processing engine with specialized join algorithms and data structures. It maintains no data statistics and uses no cost or cardinality models. Also, it uses no training workloads nor does it try to link the current query to seemingly similar queries in the past. Instead, it uses reinforcement learning to learn optimal join orders from scratch during the execution of the current query. To that purpose, it divides the execution of a query into many small time slices. Different join orders are tried in different time slices. SkinnerDB merges result tuples generated according to different join orders until a complete query result is obtained. By measuring execution progress per time slice, it identifies promising join orders as execution proceeds. Along with SkinnerDB, we introduce a new quality criterion for query execution strategies. We upper-bound expected execution cost regret, i.e., the expected amount of execution cost wasted due to sub-optimal join order choices. SkinnerDB features multiple execution strategies that are optimized for that criterion. Some of them can be executed on top of existing database systems. For maximal performance, we introduce a customized execution engine, facilitating fast join order switching via specialized multi-way join algorithms and tuple representations. We experimentally compare SkinnerDB’s performance against various baselines, including MonetDB, Postgres, and adaptive processing methods. We consider various benchmarks, including the join order benchmark, TPC-H, and JCC-H, as well as benchmark variants with user-defined functions. Overall, the overheads of reliable join ordering are negligible compared to the performance impact of the occasional, catastrophic join order choice.

Immanuel Trummer

Junxiong Wang

Ziyun Wei

Deepak Maram

Samuel Moseley

Saehan Jo

Joseph Antonakakis

Ankush Rayabhari

SkinnerDB: Regret-bounded Query Evaluation via Reinforcement Learning

SkinnerDB：基于强化学习的遗憾有界查询评估

The query containment problem is a fundamental algorithmic problem in data management. While this problem is well understood under set semantics, it is by far less understood under bag semantics. In particular, it is a long-standing open question whether or not the conjunctive query containment problem under bag semantics is decidable. We unveil tight connections between information theory and the conjunctive query containment under bag semantics. These connections are established using information inequalities, which are considered to be the laws of information theory. Our first main result asserts that deciding the validity of a generalization of information inequalities is many-one equivalent to the restricted case of conjunctive query containment in which the containing query is acyclic; thus, either both these problems are decidable or both are undecidable. Our second main result identifies a new decidable case of the conjunctive query containment problem under bag semantics. Specifically, we give an exponential-time algorithm for conjunctive query containment under bag semantics, provided the containing query is chordal and admits a simple junction tree.

Mahmoud Abo Khamis

Phokion G. Kolaitis

Hung Q. Ngo

Dan Suciu

Bag Query Containment and Information Theory

袋查询包含与信息论

Answering SPJA queries under differential privacy (DP), including graph pattern counting under node-DP as an important special case, has received considerable attention in recent years. The dual challenge of foreign-key constraints combined with self-joins is particularly tricky to deal with, and no existing DP mechanisms can correctly handle both. For the special case of graph pattern counting under node-DP, the existing mechanisms are correct (i.e., satisfy DP), but they do not offer nontrivial utility guarantees or are very complicated and costly. In this paper, we propose two mechanisms for solving this problem with both efficiency and strong utility guarantees. The first mechanism, called R2T, is simple and efficient, while achieving down-neighborhood optimality with a logarithmic optimality ratio. Down-neighborhood optimality is a new notion of optimality that we introduce for measuring the utilities of DP mechanisms, which can be considered as a natural relaxation of instance optimality, and it is especially suitable for functions with a large or unbounded sensitivity. Our second mechanism further reduces the optimality ratio to a double logarithm, which is also known to be optimal, thus we call this mechanism OPT 2 . While OPT 2 also runs in polynomial time, it does have a higher computational cost than R2T in practice. Both R2T and OPT 2 are simple enough that they can be easily implemented on top of any RDBMS and an LP solver. Experimental results show that they offer order-of-magnitude improvements in terms of utility over existing techniques, even those specifically designed for graph pattern counting.

Wei Dong

Juanru Fang

Ke Yi

Yuchao Tao

Ashwin Machanavajjhala

Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys

外键条件下差分隐私查询评估的实例最优截断方法

Guarded tuple-generating dependencies (GTGDs) are a natural extension of description logics and referential constraints. It has long been known that queries over GTGDs can be answered by a variant of the chase —a quintessential technique for reasoning with dependencies. However, there has been little work on concrete algorithms and even less on implementation. To address this gap, we revisit Datalog rewriting approaches to query answering, where a set of GTGDs is transformed to a Datalog program that entails the same base facts on each base instance. We show that a rewriting consists of “shortcut” rules that circumvent certain chase steps, we present several algorithms that compute a rewriting by deriving such “shortcuts” efficiently, and we discuss important implementation issues. Finally, we show empirically that our techniques can process complex GTGDs derived from synthetic and real benchmarks and are thus suitable for practical use.

Michael Benedikt

Maxime Buron

Stefano Germano

Kevin Kappelmann

Boris Motik

Rewriting the Infinite Chase for Guarded TGDs

重写受保护TGD的无穷追逐

Accurately estimating the cardinality (i.e., the number of answers) of complex queries plays a central role in database systems. This problem is particularly difficult in graph databases, where queries often involve a large number of joins and self-joins. Recently, Park et al. [55] surveyed seven state-of-the-art cardinality estimation approaches for graph queries. The results of their extensive empirical evaluation show that a sampling method based on the WanderJoin online aggregation algorithm [47] consistently offers superior accuracy. We extended the framework by Park et al. [55] with three additional datasets and repeated their experiments. Our results showed that WanderJoin is indeed very accurate, but it can often take a large number of samples and thus be very slow. Moreover, when queries are complex and data distributions are skewed, it often fails to find valid samples and estimates the cardinality as zero. Finally, complex graph queries often go beyond simple graph matching and involve arbitrary nesting of relational operators such as disjunction, difference, and duplicate elimination. Neither of the methods considered by Park et al. [55] is applicable to such queries. In this paper we present a novel approach for estimating the cardinality of complex graph queries. Our approach is inspired by WanderJoin, but, unlike all approaches known to us, it can process complex queries with arbitrary operator nesting. Our estimator is strongly consistent, meaning that the average of repeated estimates converges with probability one to the actual cardinality. We present optimisations of the basic algorithm that aim to reduce the chance of producing zero estimates and improve accuracy. We show empirically that our approach is both accurate and quick on complex queries and large datasets. Finally, we discuss how to integrate our approach into a simple dynamic programming query planner, and we confirm empirically that our planner produces high-quality plans that can significantly reduce end-to-end query evaluation times.

Pan Hu

Accurate Sampling-Based Cardinality Estimation for Complex Graph Queries

基于采样的复杂图查询基数估计的精确方法

短名	ACM Trans. Database Syst.
Journal Impact	2.12
国际分区	COMPUTER SCIENCE, SOFTWARE ENGINEERING(Q2)
期刊索引	SCI Q3中科院 2 区

ISSN	0362-5915, 1557-4644
h-index	88
国内分区	计算机科学(2区)计算机科学计算机信息系统(2区)计算机科学计算机软件工程(2区)

涉及主题	计算机科学程序设计语言数据库数学数据挖掘情报检索操作系统理论计算机科学人工智能算法工程类哲学万维网关系数据库组合数学离散数学生物统计认识论
出版信息	出版商: Association for Computing Machinery (ACM)，出版周期: Quarterly，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 1976，原创研究文献占比: 100.00%，自引率:0.00%， Gold OA占比: 2.33%
平均审稿周期	网友分享经验：>12周，或约稿
平均录用比例	网友分享经验：容易

ACM Transactions on Database Systems

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

Serializable isolation for snapshot databases

Making It Tractable to Detect and Correct Errors in Graphs

Streaming enumeration on nested documents

SkinnerDB: Regret-bounded Query Evaluation via Reinforcement Learning

Bag Query Containment and Information Theory

Making It Tractable to Detect and Correct Errors in Graphs

Streaming enumeration on nested documents

Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys

Rewriting the Infinite Chase for Guarded TGDs

Accurate Sampling-Based Cardinality Estimation for Complex Graph Queries