database engineers

Abstract: Given a 1D array over a total order and a query position in the array, a next larger value query returns the nearest position to the right whose value is larger than the value at the query position. Next smaller value queries and previous larger/smaller value queries are defined analogously. These queries are closely related to the $k$-th range minimum/maximum problem, which asks for the position of the $k$-th leftmost minimum/maximum value when the query range contains multiple minimum/maximum values. In this paper, we consider the encoding problem for answering any arbitrary subfamily of these four queries, where the queries must be answered without accessing the input array. We give a unified approach for obtaining space lower bounds for such encodings. We also obtain data structures for the query subfamilies that match the lower bounds up to lower-order additive terms, while supporting the queries in constant time. Our results generalize and improve several previous results on this problem [Gawrychowski and Nicholson, ICALP-2015; Jo and Satti, TCS-2016; Tsur, IPL-2019; Jo and Kim, Algorithmica-2025]. In addition, these results give tight bounds on the encoding complexity of all subfamilies of these queries for (1) permutations, (2) arrays without consecutive equal elements, and (3) general arrays.

Abstract: We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC). OLC replaces the multi-cache-line RW lock with a compact, single-cache-line lock: readers validate a version number without writing to shared memory, avoiding cache invalidations and retrying only on a detected conflict. Although OLC was thought poorly suited to skiplists, where a single per-element lock may span structurally unrelated levels, the B-skiplist's blocked layout places each level (and associated lock) in its own node. We exploit the B-skiplist's upfront knowledge of promotion height with a hybrid top-down scheme that traverses upper levels optimistically and locks only from the promotion level down, so most inserts never dirty a cache line. On 128 threads, the proposed optimistic B-skiplist achieves $1.2-10\times$ higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves $0.8-4.3\times$ the throughput compared to high-performance optimistic B+-tree implementations based on RW locks and OLC. Finally, the optimistic B-skiplist achieves up to $13\times$ lower latency than concurrent skiplists and tree-based indices, and is within $1.6\times$ of the latency of the OLC-based B+-tree.

Abstract: Large language models make it possible to pose semantic questions over diverse, multi-modal data. Recent systems give such workloads the declarative feel of a database through semantic operators: relational operators whose conditions a model judges. Most of them now run on a relational engine, yet almost none keeps what the model says past the query: every judgment is discarded on completion and paid for again the next time a query needs it. We present the tag model and tag operators, the right unit for semantic processing, and OCTOPUS, a prototype built as a middleware over DBMS. Two mechanisms are central. First, the tag: each semantic answer a model produces is written back to the relation as data, which the database engine filters, indexes, and stores as it would any other. Second, the tag operator: the unit into which common semantic operators are translated, which fixes the granularity of reuse. A model judges a tuple once, and later queries reuse that judgment as data: through relationships between predicates, a stored judgment can accept a tuple for a later predicate, eliminate one that cannot satisfy it, simplify its test, or order the search of a query that stops early. On the movie scenario of SemBench, our prototype sends the model 10 to 108x fewer rows than iPDB, ThalamusDB, Palimpzest, and LOTUS at broadly competitive quality, and three of its eight queries issue no model call at all. More broadly, a database that keeps its judgments lets its schema grow from the questions its users ask, so that each semantic answer is paid for once, stays consistent across queries, and can be audited through its provenance.

Abstract: We give a deterministic data structure for range weighted longest increasing subsequence (LIS) queries on $n$ values with positive weights. Preprocessing takes $O(n\log^2 n)$ time and space. Value queries take $O(\log n)$ time, and an optimal subsequence of $k$ elements can be reported in $O(k + \log n)$ time. This resolves an open question on truly subquadratic preprocessing with polylogarithmic query time. The key is a single-crossing property of envelopes for value-separated endpoint sets, enabling $O(\log n)$-time persistent merges. The bounds assume constant-time exact addition and comparison of weights.

Abstract: In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.

Abstract: Relational deep learning has emerged as a powerful paradigm for learning end-to-end predictive models over relational databases by representing them as temporal heterogeneous graphs. Recent advances based on graph neural networks and Transformers have achieved strong performance across diverse domains. However, the effectiveness of simpler relational baselines remains underexplored, making it difficult to assess how much architectural complexity is needed to achieve strong predictive performance. Motivated by the observation that predictive signals arise from target attributes, relational attributes, and historical labels, we revisit how effectively these signals can be exploited using simple propagation methods. We adapt fixed low-pass feature propagation to relational entity graphs and train an MLP for prediction. The resulting predictions are further refined using Correct-and-Smooth, a graph-based label propagation algorithm that incorporates historical labels over task-specific meta-graphs connecting target entities. Across classification and regression tasks on RelBench, an MLP trained on neighborhood-filtered features outperforms one using only target-entity features on most tasks and recovers a substantial portion of the performance of heterogeneous GNNs. Correct-and-Smooth provides further gains from historical labels, although applying it requires a separately constructed meta-graph because connections among target entities are not directly specified by the relational entity graph. Together, our studies revisit the effectiveness of established propagation methods as simple RDL baselines while identifying canonical meta-graph construction as a key challenge for effective label propagation.

Abstract: We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed $t\ge5$, a logarithm-free existence bound of $O_t(m^{1/c}n^{1-1/c})$, where $c=\lfloor(t-1)/2\rfloor$. For odd $t$, this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].

Abstract: CMinHash promises a new direction for designing MinHash algorithms with reduced variance and storage space via circulant permutations. However, the original variance analysis is difficult to extend to other MinHash estimators. We present a new approach that gives explicit and easily comparable approximate variance expressions, and use it to analyze the Minner estimator. Numerical experiments show that our variance expression matches the empirical mean square error (MSE) of estimates. Our work thereby demonstrates how to apply circulant permutation to other MinHash estimators and compute their approximate variance.

Abstract: We present PHastR, a minimal perfect hash function of the PHast family. Like PHast+, the fast-to-build variant of PHast, PHastR finds feasible seeds with bit-parallel operations: its seeds move keys along rings of slots, and to evaluate the seeds of a bucket it cyclically shifts, for each key, a word recording which slots of its ring are used. Unlike PHast+, however, it avoids self-collisions, which make two keys of a bucket collide for (almost) all its seeds: more than a third of the buckets bumped by PHast+ with wrapping and multiplier 3 contain one. With 8-bit seeds, PHastR uses $1.94$ bits per key, the same space as the best variant of PHast+ with wrapping, but it is built in $37\%$ of the time, and its queries are $28\%$ faster on $10^9$ keys, as it bumps $0.5\%$ of the keys instead of $3.9\%$; they are faster also than those of PHast, which takes eleven times as long to build, and about as fast as those of PtrHash, which uses more than one bit per key more. With a larger expected bucket size PHastR comes within $0.02$ bits per key of the space of PHast, using $1.90$ bits per key, and still has faster queries. Its construction also scales better with the number of threads: with all the threads of a 48-core machine it is almost three times faster than that of PHast+. Finally, we argue that when each key can be placed only within a range of $W$ slots, every placement of $n$ random keys on $n$ slots, however found, must bump on large key sets a constant fraction of the keys: we derive a lower bound of about $0.1/W$ on this fraction, and we estimate that the best placement bumps about $1/2W$ of the keys, which is about on tenth of the keys bumped by PHastR.

Abstract: We exhibit a fixed $4\times 4$ binary matrix with no polynomial induced ordered removal bound. At depth $h\geq 1$, let $m=2^h$. Our explicit host has order $(14h+2)m$, exactly $2m^6+\frac{1}{2}(m-2)m^5$ induced copies, and exact editing distance $m^2$ cells. Its normalized editing distance is $Θ(h^{-2})$, while its induced-copy density is $Θ(4^{-h}h^{-8})$. The lower bound holds against arbitrary cell edits through an injective family of $m^2$ protected selections. An exhaustive arithmetic classification identifies every induced copy and proves that a matching canonical repair creates none. The original-copy transversal number is exactly $m$, yielding an unbounded gap between hitting existing copies and eliminating all copies. The identities and the obstruction at every depth are formalized in Lean, with verification sources included as ancillary files.

Abstract: Join ordering is classic problem in data management. We highlight the connection between structure-specific dynamic programming algorithms and the mathematical enumeration of the possible merge trees from a join graph. We present two case studies, on double-star and helix shaped join graphs, that we believe carry useful techniques for a toolbox of building structure-specific join optimizers. For the double-star case, we show how the enumeration leads directly to a significantly improved search algorithm, whereas for the helix case we show that a algorithm derived from the mathematical enumeration is not necessarily better than structure-agnostic algorithms.

Abstract: Storage stalls remain a significant source of application latency even on fast storage devices. Prefetching can hide part of this latency by fetching data before it is demanded, but general-purpose operating-system mechanisms typically infer future accesses from recent file offsets. This approach is ineffective when accesses are determined by workload structure, such as recurring sparse accesses during application launch, logical traversal in database scans, or model-layout metadata in LLM runtimes. Existing workload-aware prefetchers usually embed prediction logic inside individual applications and couple execution to application-level I/O paths, making policies difficult to reuse across workloads and systems. We present PredictIO, a programmable interface that separates workload prediction from prefetch execution. PredictIO delivers kernel-observed accesses and application hints to user-space policies, which express predictions as uniform page-range requests. A kernel-space executor validates, bounds, and filters these requests against cached and in-flight pages before issuing asynchronous prefetch I/O. We implement PredictIO for application launch, SQLite range scans, and LLM model loading. Across these workloads, PredictIO reduces latency by 5.3-26.3%, achieves up to 2.99x speedup for SQLite scans, and reduces LLM loading latency by 8.8-47.9%. We further show that a common prediction policy can be reused across SQLite and LMDB through lightweight adapters, that an application-integrated RocksDB readahead policy can be migrated while preserving its workload selectivity, and that the execution backend determines how much benefit migration provides for different access patterns and storage devices.

Abstract: Scalable logic-based analytics are frequently dominated by cyclic multi-way joins over large relational datasets. State-of-the-art systems evaluate these joins through chains of binary joins, incurring substantial overhead from large intermediate relations that must be materialized and redistributed across the network. Worst-Case Optimal Joins (WCOJ) offer a provably superior alternative by evaluating joins one variable at a time, eliminating intermediate blowup. However, existing WCOJ implementations target either shared-memory machines or one-shot, non-recursive queries on dataflow and big-data platforms, leaving WCOJ-based recursive evaluation on distributed-memory HPC systems an open problem. We present, to our knowledge, the first distributed-memory Datalog engine that uses WCOJ for recursive fixpoint evaluation. Our design builds on HyperCube partitioning, which hash-partitions relations along variable-aligned grid dimensions and replicates them along missing dimensions, and extends it from a single shuffle to iterative execution: in every semi-naive iteration, only newly derived tuples are repartitioned and re-replicated, using MPI all-to-all collectives and per-dimension all-gathers over subcube communicators, while the same layout is reused across iterations so that all WCOJ intersections remain rank-local. We evaluate our system on the Aurora and Polaris leadership-class supercomputers at Argonne National Laboratory using graph mining and program analysis benchmarks, demonstrating strong scalability, outperforming state-of-the-art Datalog engines on most benchmarks, and characterizing how partition dimensionality trades runtime against memory feasibility.

Abstract: We prove an $Ω((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetildeΩ(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the strongest lower bound known for any dynamic problem. The same bound holds for incremental undirected shortest paths and subgraph connectivity. To prove it, we bring the recent framework of Ko [FOCS 2026], which gave this bound for Pătraşcu's multiphase problem with Inner Product, to the multiphase problem with Disjointness. Our main technical contribution is to show that verification in Ko's 2.5-round multiphase communication game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.

Abstract: We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.

Abstract: In-database predictive query processing increasingly applies Transformer-based models within relational pipelines. However, existing in-database inference typically exposes only tuple-level model inputs to the inference runtime, leaving relational predicates and metadata statistics invisible to neural execution planning. In this paper, we propose QCATS, a query context-aware transformer slicing framework that enables efficient sparse inference inside database systems. QCATS executes at query granularity: instead of routing individual tokens or tuples during inference, it uses query predicates and metadata statistics to pre-select context-aligned FFN slices before model execution. The framework comprises offline expert construction and lightweight query-level routing that dynamically selects experts during execution. QCATS further introduces system optimizations, including asynchronous CPU-GPU pipelines and routing-aware batching. Experiments on four predictive-query workloads with BERT-base and Qwen-0.6B show that QCATS achieves up to 4.42x latency reduction while preserving prediction accuracy comparable to dense baselines.

Abstract: Schema matching increasingly uses generative language models to rerank retrieved column candidates, although the underlying task is a bounded correspondence decision. We present JevNexus, which combines typed pairwise decisions with schema/instance evidence and invokes listwise refinement only when the evidence disagrees and the fused margin is small. The evaluation covers 561 cases from six benchmark families. JevNexus obtains dataset-macro MRR and Hits@1 of 0.930 and 0.909, compared with 0.926 and 0.903 for Magneto, while reducing mean latency from 123.452 to 15.929 seconds (7.750). Paired analysis finds no statistically significant difference in either MRR or Hits@1. The gate invokes listwise refinement for only 5.665% of source columns and avoids the degradation caused by unconditional refinement. Code and experimental artifacts are available at https://github.com/RazeenLI/JevNexus.

Abstract: CXL memory expands single-node memory capacity for in-memory databases but has higher latency and lower bandwidth than local DDR. Hybrid DDR--CXL databases require joint indexing and data distribution design. Indexing designs differ in access and migration paths and constrain the placement of indexes and tuples, creating trade-offs in runtime performance, DDR memory efficiency, and system integration complexity. Their performance impact is thus difficult to determine. Indexes and tuples may differ in access characteristics: placing them in the same tier may reduce DDR efficiency, while separate management adds tracking and decision overhead. We propose five indexing designs based on two approaches: treating the two tiers as a unified data space or managing them separately. We analyze their trade-offs and underlying causes and develop adaptive data distribution optimization for single-index designs in which the database explicitly manages distribution. The method manages index objects and tuples separately, reduces metadata overhead through hierarchical hotness tracking and an index object residency policy, and extends benefit-aware admission and randomized eviction to determine and adjust their placement according to each type's expected benefits and memory footprints. We implemented the designs in a hybrid DDR--CXL database prototype and evaluated them using YCSB. The single-index design with direct addressing achieves the best performance under most workloads and system configurations. The dual-index design performs better mainly when DDR capacity is limited or accesses are highly concentrated, and has relatively low integration complexity. Adaptive distribution optimization improves DDR memory efficiency and system performance, enabling single-index designs to achieve up to $1.59\times$ the throughput of their counterparts with non-separated management.

Abstract: Generative Information Retrieval (GIR) has emerged as a transformative paradigm, shifting document retrieval from a traditional "retrieve-and-rank" workflow to sequence-to-sequence generation, where a model directly predicts document identifiers (DocIDs). While the semantic design of these DocIDs is known to be critical for performance, a fundamental question remains under-explored: what makes a good DocID? Current approaches rely heavily on computationally expensive downstream evaluations, hindering systematic analysis and rapid iteration. In this work, we address this challenge by presenting a comprehensive study on the properties, metrics, and trade-offs that define effective numerical DocIDs. Specifically, our contributions are threefold: First, we propose a unified framework that unifies Product Quantization (PQ) and Residual Quantization (RQ), and their hybrid variants within a single design space. This enables us to systematically study key DocID properties, such as hierarchy versus parallelism, as well as the impact of hyperparameters like DocID length and codebook size. Second, we define a suite of training-free, intrinsic metrics, to quantify DocID quality and evaluate structural fidelity without the overhead of full model training. Through extensive experiments on MS MARCO 300K and NQ320K, we analyze how these structural properties influence retrieval effectiveness.

Abstract: In semantic query engines, predicates are evaluated by machine-learned models, and the choice of a query plan affects not only the cost of a query but also its result. Existing systems either apply a fixed threshold to each semantic operator or tune accuracy per operator, without accounting for how errors propagate through joins. We give a formal problem definition for cost-accuracy optimization of such queries. Our starting point is the calibrated confidence that decision models such as Jev attach to each decision. It yields an expected error for every decision; weighting these errors by each decision's contribution to the output (in the simplest case, its fan-out) gives the expected output quality of a plan without any labeled data, and the same computation in reverse turns an output-level accuracy target into a price on each base or intermediate tuple. Building on this, we define an oracle semantics for relational algebra with semantic operators, physical plans as pairs of a logical plan and a decision policy, declarative output-level targets, and a hierarchy of plan equivalence. We show that accuracy is plan-invariant under pointwise-deterministic policies, and that selection pushdown is not quality-sound when escalation bands are calibrated on the plan's own candidates. Expected quality can be computed in polynomial time under bag semantics; under set semantics it follows the dichotomy of tuple-independent probabilistic databases when every relation carries a semantic predicate. Choosing which tuples to drop is NP-hard, while the optimization problem decomposes into per-tuple decisions through two Lagrange multipliers. Simulations on a synthetic workload illustrate these effects; an evaluation on real engines is left for future work.

Abstract: We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive queries. We believe the algorithm and its analysis to be notably simple, indeed, together we believe they form a highly simple argument that conjunctive query evaluation can be performed in essentially submodular width time. In the case of Boolean conjunctive queries, the algorithm is based on interleaving three simple primitives: a subroutine for establishing a form of consistency; a subroutine for establishing global uniformity, which, briefly speaking, partitions relations as needed to control discrepancies between average degree and maximum degree; and, a simple step that joins pairs of existing relations to form new relations.

Abstract: We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed $k \ge 2$, every relational signature, and every fragment between $k$-variable primitive positive ($\mathrm{PP}^{k}$) and first-order ($\mathrm{FO}^{k}$) logic, we prove, assuming the Sparse MAX-$3$-SAT hypothesis, a dichotomy theorem for evaluation in $O(m^{k-\varepsilon})$ time, where $m$ is the number of tuples in the input structure. The only tractable cases fall into three families: (1) three-variable fragments, (2) two-variable fragments, and (3) fragments over unary signatures. On the hard side, for every fixed $k \ge 4$ and every $\varepsilon > 0$, there is a fixed sentence $\varphi_\varepsilon$ in $\mathrm{PP}^{k}$ over a single binary relation symbol, depending on $\varepsilon$ but not on the input structure, whose evaluation cannot be performed in $O(m^{k-\varepsilon})$ time. For the tractable cases, we show that the evaluation problem can be solved in $2^{O(|\varphi|)} \cdot m^{k-\varepsilon}$ time for some $\varepsilon > 0$. Moreover, every tractable fragment reduces, with a $2^{O(|\varphi|)}$ blowup in formula size under DAG representations, to one of the following query languages: (1) Tarski's calculus of relations, (2) a new Boolean modal logic for sparse model checking, and (3) one-variable counting logic.

Abstract: We study constant-delay enumeration for conjunctive queries with negation ($\texttt{CQ}^{\neg}$). Prior work defined \emph{signed-acyclicity}, which characterizes the class of queries where linear preprocessing time is achievable, but little has been known beyond this. We introduce a new hypergraph width measure for $\texttt{CQ}^{\neg}$, the \emph{signed fractional hypertree width} ($\textsf{sfhw}$), defined by requiring that a single variable order simultaneously handle every subset of the negative atoms. We show that $\textsf{sfhw}$ strictly generalizes signed-acyclicity (recovered when $\textsf{sfhw} = 1$) and fractional hypertree width (recovered on queries without negation). Our main algorithmic result is a variable-elimination algorithm that achieves constant-delay enumeration on input $I$ for any full $\texttt{CQ}^{\neg}$ query with preprocessing time $O(|I|^{\textsf{sfhw}})$. We further show that using multiple variable orders can improve this bound, exhibiting an $O(|I|^{3/2})$ algorithm for $k$-cycle queries with at least one negative edge.

Abstract: Document databases such as MongoDB are core infrastructure for modern applications, and natural-language interfaces to them---text-to-MQL---would let non-experts query complex, semi-structured data without mastering the query language. Progress on this task depends on high-quality benchmarks, which are most practically obtained by converting an existing text-to-SQL benchmark to the document setting. Unfortunately, existing efforts rely on heuristics for mechanical conversion: the document schema mirrors the relational foreign-key graph, and each query mirrors its source SQL. As a result in our experiments, these approaches fail to migrate 6 of 21 BIRD databases outright, silently drop up to 25.9\% of rows on others, and yield schemas whose ground-truth queries run over an order of magnitude slower as the data scales. We instead propose a conversion pipeline, driven by coding agents with human-in-the-loop verification, that designs each document schema from expected access patterns and rewrites queries to be MongoDB-native. Applying it to BIRD, we build an access-pattern-based text-to-MQL benchmark (AptMQL-Bench). It includes 21 document-oriented databases, 3,186 natural-language requests, and their associated MQL queries---whose databases are migrated from SQLite without data loss and scale efficiently. The strongest model, Claude Opus 4.5, achieves only 57.38\% accuracy without external knowledge evidence and 70.34\% with it. This indicates that realistic text-to-MQL generation remains challenging.

Abstract: NVMe SSDs are now widely deployed as the storage tier in data centers. As SSDs have evolved over the past decade, the commu- nity has continued to debate the interfaces they expose and how operating systems and storage systems should exploit them. The NVMe Flexible Data Placement (FDP) proposal is the latest point in this design space. FDP introduces an interface based on Reclaim Units that enables explicit data placement to reduce device write amplification without the software engineering costs of sequential- write constraints and host garbage collection. FDP-enabled SSDs are emerging in commercial products and early data center de- ployments. Their compatibility with conventional block I/O allows existing applications to run unchanged, allowing a frictionless adop- tion in industry. This paper presents an experimental evaluation of FDP SSDs to characterize their data placement guarantees over the raw device interface. We then revisit two widely deployed and distinct open- source storage systems, MySQL and RocksDB, and examine whether lifetime-based data separation and distinct write patterns built into their architectures can be mapped onto FDP SSDs without inva- sive changes. Our evaluation shows end-to-end WAF reductions at higher device utilization, along with QoS and throughput improve- ments under synthetic and real-world workloads. These results demonstrate that FDP provides a practical and deployable cross- layer mechanism for data placement with open-source ecosystem support on Linux. They also highlight why FDP SSDs are gaining traction in industry.

Abstract: We present SOLO, an index for approximate nearest-neighbor search in general metric spaces whose serving path contains no ranking heuristic of any kind: a query is routed to the $k_s$ nearest points of a random sample of the database, and every object in the touched posting lists is evaluated with the true distance. Because nothing must outrank anything, recall equals a coverage probability computable from the stored index: one ground-truth pass over a query sample certifies every operating point at once, without serving any of them -- a recall certificate, and for a navigable graph no analogous object exists at any price. The whole index is one recursive rule -- sample the collection, post each object to its $b$ nearest sample points, split any list that outgrows a bound, always scan the leaves -- and its operating surface obeys an equal-work law, recall $\approx f(b \cdot k_s)$, whose level is a one-scalar signature of the dataset. The same scan-only structure gives a serving floor no graph architecture reaches once the router is itself indexed by the same rule: Deep-100M served at recall 0.9977 from 1 GB of resident memory (enforced cap, 10.7 bytes per object) and at 0.9964 from 256 MB, Deep-1B at recall 0.9925 from 512 MB (and from 96 MB at depth 3), inserts that are one search, and deletes that are exact. Throughput is competitive where the hardware allows it -- up to $1.8\times$ a tuned HNSW at $10^8$ on a two-socket 32-core server, with operating points to the right of where that graph saturates -- and the tables report it against HNSW, DiskANN, GRAFT, NAPP, misi, and SPANN's assignment rule on the same hardware and ground truth.

Abstract: Semantic database systems extend SQL with foundation-model inference over unstructured data, but current engines rely heavily on autoregressive LLMs for discrete relational decisions, creating high latency and monetary cost. We present JEVDB, a scalable semantic database system that uses fast, typed decision models for semantic filters, joins, classification, and ranking, while selectively escalating uncertain cases to generative LLMs. To reduce semantic-join work, JEVDB combines exact Yannakakis-style semijoin reduction over relational structure with Semantic Bloom Filters (SBFs), which use registered necessary conditions to screen candidates across latent semantic edges. We evaluate JEVDB on SemBench and Shelob, a TPC-DS-derived semantic-join workload. On SemBench, JEVDB-Flash achieves the lowest latency on all 21 evaluated queries and the lowest cost on 19, while maintaining competitive answer quality. On Shelob, where joins scale to 540K candidate pairs, JEVDB completes all queries with 95.7%-97.5% mean F1. SBF screening removes 87.4% of candidate pairs before semantic evaluation, and reusable condition-index scoring further reduces reasoning-model escalations by 55.2%. An interactive query simulator, source code, and benchmarks are available at https://jevdb.org.

Abstract: Tabular foundation models achieve state-of-the-art performance on single-table tasks without any training. Recent work suggests that they are also well-suited for relational learning via deep feature synthesis (DFS), which flattens a relational schema into a single table by adding aggregates of the other tables' columns as features. This approach is appealing because it directly benefits from improvements to or customization of the underlying tabular foundation model. In this paper, we identify two key problems with DFS: feature explosion and interaction blindness. The first problem arises because the number of DFS features grows quickly as the schema becomes more complex, limiting scalability and performance. The second problem arises because column-wise aggregates do not account for feature interactions, limiting performance. We propose and explore an alternative method termed RelICL, which keeps the benefits of DFS but alleviates these two problems. At its heart, RelICL propagates and fuses information step by step through the schema graph, using the same tabular foundation model that is eventually used for prediction to do so. In our experimental study using RelBench tasks, RelICL was on par with the strongest approach based on deep feature synthesis.

Abstract: Relational foundation models (RFMs) are pretrained once on a collection of relational databases and prediction tasks, and then applied zero-shot to previously unseen databases and tasks. To make a prediction for a target row, an RFM samples a neighborhood of rows linked to that row through foreign keys and uses this neighborhood as its inference context. Lowering inference cost is an important goal for any foundation model, and for RFMs this cost grows with the size of the context. The simplest ways to shrink the context is to drop some of the sampled rows, but this ignores the semantics of the database schema, so it is as likely to discard informative rows as uninformative ones. We propose STEER, a sampling approach that shrinks the inference context by concentrating it on the tables most relevant to the prediction task at hand. STEER obtains relevance information by prompting a large language model to rank the foreign-key edges of the database schema into relevance tiers for the given task, and then maps each tier to a probability of following that edge during traversal. Because the ranking uses only the schema, it is computed once per task and reused across all subsequent predictions, amortizing its cost. We evaluate STEER on three state-of-the-art RFMs (RT, RT-J, and Griffin) and show that it reduces inference context size by about 40% on average while maintaining, and in some cases improving, prediction accuracy.

Abstract: Large language models (LLMs) have recently been applied in systems research as a tool to reduce human-intensive engineering effort through cost-efficient automation. Decades of research have produced a rich landscape of concurrency control (CC) protocols, each encoding distinct trade-offs in correctness, throughput, and abort behavior. However, most applications in practice default to 2PL or OCC, because selecting and adapting a protocol to a specific application requires expert knowledge that is rarely available to application designers. This is a wasted opportunity, as an application-specific CC protocol can yield significant performance advantages over a generic baseline, but designing one requires deep expertise in CC protocol design. In this paper, we propose HakiCC, an LLM-driven multi-agent pipeline that automatically designs, verifies, and optimizes concurrency control protocols tailored to a given target application. HakiCC provides a two-stage pipeline. In Stage 1, a multi-agent system takes a workload description as input and generates an application-specific CC protocol implementation, which is iteratively repaired and verified for conflict-serializability. In Stage 2, the verified protocol is further optimized for that application through an LLM-driven evolutionary loop targeting correctness and throughput. We evaluate HakiCC on TPC-C and AuctionMark as target workloads, producing and reporting ten application-specific CC protocols. All ten are conflict-serializable after Stage 1; Stage 2 improves throughput for every protocol, with average gains of +50.6% for TPC-C protocols and +92.2% for AuctionMark protocols.

Abstract: The Consensus technique marked a breakthrough in the construction of minimal perfect hash functions (MPHFs), reaching a linear tradeoff between construction time and space overhead relative to the optimum. Consensus provides a clever scheme to search for and encode seeds of tasks in random data structures. We apply Consensus to the related field of compressed static functions (CSFs). These data structures store a function $f: S \to Σ$ such that querying a key $x \in S$ returns $f(x)$ and querying $x \not \in S$ returns an arbitrary value. CSFs do not need to store the keys $S$ and only need space close to the zeroth-order empirical entropy of the multiset of values. Often, some values are much more common than others. In these cases, CSFs can use less space than their non-compressed counterparts. CSFs are a useful building block, for example in database design and bioinformatics. We introduce Consensus-CSF, which can reach arbitrarily close to the empirical entropy $n H_0$, with a construction time of $n \exp(\tilde{\cal{O}} (\sqrt{1 / δ}))$ for space usage of $n H_0 (1 + δ)$ when assuming some parameters of the value distribution to be constants. This tradeoff beats previously implemented approaches that can only reach some fixed threshold above the entropy lower bound. We enable Consensus in the setting of CSFs, which is less structured than MPHFs, with the introduction of task insertions. Our approach randomly distributes the keys into one-bit Consensus tasks and then strategically inserts additional tasks in places where the construction would get stuck otherwise. We provide an implemented version of our algorithm which reaches the same order of magnitude in space overhead as competitors but is not competitive in practice. Beyond these results, we present a new way to think and reason about Consensus, which may also be applied to other problems.

Abstract: We prove a rank-preserving version of Gaifman's Theorem. Compared to earlier rank-preserving locality theorems (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem is much simpler and yields formulas in exactly the same normal form as Gaifman's original theorem. Furthermore, it holds not only for first-order logic, but also for first-order logic with modulo-counting quantifiers and, more generally, for the first-order logic on weighted structures ngFOW+ that is introduced in this article. As an application of our theorem, we give a simplified proof of the algorithmic meta-theorem of [Grohe, Kreutzer, Siebertz, JACM 2017] stating that first-order properties of nowhere dense structures can be decided in almost-linear time. Our locality theorem for the weight logic ngFOW+ can be seen as an essential step toward such a meta-theorem for this logic.

Abstract: Datalog underpins reasoning tasks such as program analysis, but its programs are hard to write. Existing synthesizers automate this task but require users to state their intent as input-output examples. Large language models (LLMs) suggest a more natural route, text-to-Datalog synthesis from a natural-language question, yet how well they do so has not been systematically evaluated. We present DatalogBench, a benchmark of 136 text-to-Datalog synthesis tasks curated from existing Datalog-based artifacts. Synthesized programs are graded by execution on held-out inputs against an oracle validated by mutation analysis. Across six LLMs and four prompting configurations, exact match peaks at 68.4%, and relation descriptions or an input-output example have only modest, model-dependent effects. Under direct prompting, most failures occur at compile time, typically because a model invents auxiliary predicates that it never declares or types consistently. Two coding agents reach up to 83.8% and eliminate nearly all such failures, leaving mostly semantic errors concentrated in recursive tasks. DatalogBench thus identifies recursive reasoning and decomposition as open challenges for current LLMs and agents, and offers a reliable, execution-grounded measure of both.

Abstract: We describe KNDB, a PostgreSQL 18 table access method (TAM) that types every row with an engine-assigned epistemic kind (MEASURED, INFERRED, or DERIVED) and resolves per-slot conflicts inside every write-time heapam callback. Rows land as ordinary heap tuples; seven of the 44 TAM callbacks are overridden (tuple_insert, multi_insert, tuple_update, tuple_delete, tuple_insert_speculative, tuple_complete_speculative, relation_toast_am), the other 37 delegate to heap; we provide a completeness argument over the interface as a paper artefact. This paper reports the engineering behind that decision and the adversarial evaluation that motivated it. On a confidence-forgery workload where an attacker asserts INFERRED writes with confidence in [0.95,1.0] against honest MEASURED writes with confidence in [0.5,0.9], KNDB beats a confidence-only baseline by 63 percentage points on the Book-Author fusion dataset and 92.7 points on the Zheng crowdsourcing dataset. Both wins are proven load-bearing on the kind axis by a source-rebuild disable-and-test in which the lattice is neutralised and the win vanishes. Against four truth-discovery baselines (TruthFinder, CRH, CATD, ACCU) reimplemented from the original equations and validated to within 0.3 percentage points of the published numbers, KNDB is competitive below a per-dataset density-saturation cell and dominant at or above it. We formalise the cell as k* ~ rho_alg * h_top, where h_top is per-slot top honest surface-form support, and validate the prediction within +/-20% on Book-Author and +/-30% on Zheng. Because the kind axis is assigned by the engine from independent metadata and cannot be forged at write time, KNDB's k* is unbounded. The paper is honest about where KNDB loses: CRH and ACCU outperform KNDB below saturation on Zheng, and KNDB scores zero on three temporal knowledge-editing benchmarks whose ground truth is last-writer-wins.

Abstract: Repeated threshold queries may reuse selected identities without reusing stale reports, but cheaper certificates need not shorten the complete response. We study selected-lower, atomic-upper (SLA) certificates for fixed-rank conjunctive screening with explicit missing-information semantics. An endpoint characterization and a counterexample separate same-source containment from policy-dependent online behavior. The original 320-session experiment reduces summed construction medians by 31.18% against an exclusion-cover certificate, yet its Cover/SLA full-API geometric time ratio is 0.9682 (95% conditional blocked interval 0.9593-0.9769), and SLA takes 12.94% more summed time than uncached Bitmap. Three separately launched complete repeats preserve this adverse ordering, with Cover/SLA ratios of 0.9665-0.9718. An additional 720-configuration exploration varies catalogue size, construction period, requested count and query locality on empirically resampled tables. SLA is faster in 295 configurations against Cover and 271 against Bitmap, descriptive counts that do not establish universal superiority. Separately instrumented additive costs distinguish construction savings from retrieval and report costs. A plane-stress component case adds an independent analytical displacement check and 4,608 boundary-challenging queries: five implementations agree exactly, while medium- and fine-mesh selections differ at 459 positions. A state-stratified public bolt-record exercise preserves 185 incomplete positions among 1,479 requests. Raw timings, complete configuration results and a tested clean-environment package support reproducibility. The SLA construction was explored and refined through the self-evolving AI system ZiYor; the named authors specified, implemented and evaluated it. This is a bounded mechanics-to-query study, not physical joint qualification or universal speedup.

Abstract: Cross-modal hashing enables efficient retrieval by encoding heterogeneous data into compact binary codes. Recent methods exploit fine-grained relations encoded in multi-label training structure, yet none of them constrains how those relations survive as consistent candidate rankings in finite, multi-length Hamming spaces, which we term the relevance resolution bottleneck (RRB). To address the RRB, we propose MultiBit, which transfers relevance resolution from multi-label structure to multi-length Hamming spaces. MultiBit first constructs a scale-decomposable fractional relation teacher from dataset-level label co-occurrence and label specificity, and models dependencies from local to long-range over continuous diffusion scales. It then maps the discretized diffusion scales and their quadrature weights to scale-aware bit subblocks of the maximum-length code, organizes the target code lengths as nested prefixes, and aligns their Hamming candidate rankings with the teacher relations. Experiments on multiple benchmarks demonstrate improved retrieval accuracy. Code is available in the supplementary material.

Abstract: The semiring framework and its extensions form the basis of a rich collection of theoretical results and implementations for provenance tracking of database queries. Many real-world queries use aggregation and conditions on the aggregate values. Support for such queries has been proposed by introducing semimodule elements as aggregate values and formal comparisons between aggregate values as tuple annotations, which takes the approach outside the standard semiring framework. In this work, we show how to introduce a semantics for the provenance of such queries in arbitrary commutative semirings with monus (or m-semirings), without the need for additional operators. This semantics is shown to agree with the standard provenance of the aggregation-free self-join rewriting of HAVING COUNT(*) queries in semirings that are absorptive and where times distributes over monus. We derive algorithms for this semantics and implement them within the ProvSQL system, with viable performance on a real-world dataset for probabilistic query evaluation.

Abstract: As modern data analytics workloads become increasingly heterogeneous and hardware-intensive, achieving efficient multi-core performance across diverse applications remains an open challenge. We present Reffine, a compiler-based in-memory analytics engine that delivers high performance across a broad range of data analytics workloads. Reffine introduces a novel intermediate representation (IR), grounded in relational algebra and sparse iteration theory, that provides a unified abstraction for data and computation. This representation enables workload-agnostic, end-to-end optimizations such as operator fusion and automatic parallelization across diverse analytics applications. We further develop a sparse compiler backend that translates Reffine IR into hardware-efficient imperative code, achieving high multi-core performance without domain-specific implementations. On the TPC-H benchmark, Reffine outperforms the in-memory analytical database DuckDB by up to $24.9\times$ and the state-of-the-art compilation-based database Umbra by up to $3.2\times$. Reffine also achieves average speedups of $18.3\times$ and $47.9\times$ over Polars and NetworkX on streaming and graph analytics workloads, respectively. Source code: https://github.com/ampersand-projects/reffine

Abstract: A graph $G=(V,E)$ is called smooth (respectively, strongly smooth) if for any two vertices $u,v\in V$, the distance point-shadow $v|u := \{ x\in V: d(u,x)=d(u,v)+d(v,x)\}$, respectively, the point-shadow $v/u := \{ x\in V: v\in\mathrm{conv}(u,x)\}$, is geodesically convex. Smooth graphs have been introduced by Nebeský (2005) in the context of step systems. Graphs with convex point-shadows and convex distance point-shadows also naturally occur in convexity theory. Brešar et al. (2026) recently showed that several classes of graphs are smooth and that smoothness is preserved by Cartesian products, gated amalgams, and isometric subgraphs. Weakly modular graphs comprise the most important classes of graphs from Metric Graph Theory: median, modular, Helly, bridged, and dual polar graphs. In this note, we characterize smooth and strongly smooth weakly modular graphs in terms of forbidden isometric subgraphs on 5 and 7 vertices. This settles Problem 1 of the paper by Brešar et al. We also characterize prime strongly smooth weakly modular graphs, i.e., strongly smooth weakly modular graphs that cannot be obtained from smaller graphs by Cartesian products and gated amalgams.

Abstract: We address the problems of giving a semantics to a relational database (RDB) that has missing values (MVs). The causes for the latter are governed by a Missingness Mechanism that is modelled as a Bayesian Network (BN) that involves the DB attributes as variables. The BN is called a Missingness Graph (MG). Our approach considerable departs from the treatment of RDBs with NULL (values). The combination of the MG and the observed DB allows us to build a block-independent probabilistic DB. We identify two optimal classes of its possible worlds on which QA can be performed. Those classes jointly capture probabilistic uncertainty and statistical plausibility of the implicit imputation of MVs. We obtain tractability results for the computation of some optimal classes; and we also obtain complexity results that characterize the computational feasibility of our approach.

Abstract: Small open-weight language models are assumed to fail at agentic database work because they lack the reasoning capacity for it. We test that against a production system. Over eleven days we drove the agent mode of an open-source SQL client with 39 open-weight models served locally and one hosted control, across six task surfaces: 8,199 runs, 110,711 ledger events, 14,008 refused tool calls. Of the 2,100 model-attributed agent-mode losses, 1,590, or 75.7%, came from runs that had invoked at least one tool. That majority is what survives resampling models rather than runs: it holds in 99.7% of clustered resamples and in 15 of the 22 models with at least twenty losses. Within it, transport, a run that used the tools and never got a deliverable through, is the largest class at 36.2% and capability, a run that invoked no tool at all, the smallest at 17.3%; we report that ordering as a property of this corpus rather than a general finding, since clustered by model it holds in only 74.5% of resamples. Transport failures decompose into a few mechanical argument shapes. Production ledgers record refusal codes and never the model's arguments, so these were invisible for ten days; capturing them exposed five server defects, one of which demanded a field on one tool, forbade it on the sibling that composed it, then failed the run for its absence. Five server changes, touching no model, prompt or sampling setting, moved six models by 6 to 21 cells out of 30. We also report a confound we believe affects published local-model benchmarks, ours included: with no context cap, one 7.1 GB model was admitted at its full 262,144-token window and held 51 GB on a 64 GB machine, producing runs indistinguishable in any ordinary log from a model timing out. The corpus, the scorer and a verifier that regenerates every figure are released.

Abstract: We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database realizes each feasible tuple type, the goal is to compute the probability of a class of worlds specified by a given tuple multiplicity vector, thus grouping together worlds with the same bag (multiset) of realized tuple types. For this problem, we prove $\#\mathsf{P}$-hardness even for very restricted and structured inputs. On the other hand, we show that it admits an FPRAS, as well as $\mathsf{XP}$-time algorithms parameterized by the number of tuple types and the treewidth of an incidence graph modeling the connections between blocks and tuples. Finally, we show that augmenting the problem with certain compatibility constraints between block realizations renders it $\#\mathsf{XLP}$- and $\#\mathsf{XALP}$-hard parameterized by pathwidth and treewidth respectively, ruling out $\mathsf{FPT}$ algorithms under standard assumptions. We leave as an open question whether this also holds in the absence of compatibility constraints.

Abstract: State-of-the-art key-value stores built for persistent memory (PM) provide low latency as they allow application threads to directly access the data on PM and rely on hardware to manage multiple non-volatile DIMMs (NVDIMMs). While this provides low latency, it results in low throughput and scalability. Performance degrades because PM hardware requires fine-grained control over PM accesses; for example, throughput degrades if too many threads write to PM concurrently. We present SKYE, a write-optimized PM key-value store that achieves high throughput and scalability. SKYE builds on the central idea of maintaining fine-grained control over all PM accesses and obtains high PM write-bandwidth utilization. To achieve this, SKYE deviates from current practice and provides indirect access to applications; applications send requests to SKYE, which uses dedicated threads to access PM on their behalf. Instead of relying on hardware-managed PM, SKYE controls how data is placed on individual NVDIMMs. SKYE leverages multiple media to avoid overloading PM and limits remote NUMA accesses for scalable throughput. We show that on a single NVDIMM, SKYE outperforms state-of-the-art PM stores by 2.5-5x on the standard Yahoo Cloud Serving Benchmark (YCSB). With four NVDIMMs across four NUMA nodes, SKYE obtains about 86% of PM write bandwidth, and its write throughput scales by 3.9x.

Abstract: Relational table learning has gained increasing attention with the widespread use of relational databases. Existing methods typically rely on deep GNN or HGNN stacks, leading to high computational costs and limited performance on large real-world databases. We propose MetaRTL, a two-stage framework for scalable and expressive relational table learning. In the first stage, MetaRTL obtains initial table embeddings via lightweight pre-training. In the second stage, it performs non-parametric message passing to derive meta-path features, which are then aggregated by an attention module, MetaAttn. By shifting computation from deep message passing to efficient meta-path aggregation, MetaRTL captures rich relational semantics while maintaining high efficiency. Experiments on 10 real-world datasets across 24 tasks demonstrate the effectiveness of the proposed method.

Abstract: For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $φ(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing, whenever given a tuple $\bar{v} \in A^k$, the algorithm computes the number of tuples $\bar{w} \in A^\ell$ that satisfy $\mathcal{A} \models φ(\bar{v}, \bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.

Abstract: Distributed database management systems (DDBMSs) introduce new challenges for assessing their reliability due to distribution-specific characteristics that affect query execution and optimization. Existing testing approaches, largely designed for centralized DBMSs, often fail to explore diverse distributed execution behaviors and suffer from low executability of generated test queries, thereby limiting their effectiveness in bug detection. We propose DAT (Distribution-Aware Testing), a novel automated approach for detecting query-processing bugs related to distribution strategies and distributed optimizations in DDBMSs, by systematically leveraging distribution-aware information throughout the testing pipeline. DAT builds on a set of techniques that capture diverse combinations of logical schemas and data distribution strategies, and performs guided query mutation to trigger a wide range of distributed query execution behaviors and optimizations, while improving query executability via historical feedback. We implement our approach in a tool, DistRanger, and evaluate it on four widely used production DDBMSs. It uncovers 31 previously unknown bugs, including 28 related to distributed query processing and optimization, and outperforms state-of-the-art testers.

Abstract: We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.

Abstract: A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and a reference $\backslash i$. The substring matched by the reference must match the substring matched by the corresponding capturing group. Given a rewb $R$ and a string $Q$, the rewb matching problem is to decide whether $Q$ is one of the strings specified by $R$. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. In the paper, we focus on rewb containing a single capturing group and $k$ references. For this class, Uezato~[CPM 2026] gave an $O((k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-ε} \mathrm{poly}(m))$ for any $ε> 0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^2m)$ time and uses $O(nm)$ space. This improves the above results (by a factor of $km$ and $m$, respectively) and the former's space bound (by a factor of $nm$). We also show how to extend our algorithm to handle a slightly more general class of ordered and single-nested rewbs.

Abstract: In this work, we consider the problem of maintaining an approximate value of degeneracy of a given dynamic $n$-vertex graph $G$ updated by edge insertions and deletions. From the work of Christiansen and Rotenberg [ICALP 2022], it follows that one can design a dynamic data structure for this problem with worst-case update time $\text{poly}(d_{\mathrm{max}}, \log n)$ that maintains an integer between $d$ and $2d+3$ where $d$ is the degeneracy of $G$, under the assumption that $d$ never exceeds $d_{\mathrm{max}}$. We complement their result by providing a conditional lower bound: we prove that, unless SETH fails, for any $\varepsilon, δ> 0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)$-approximation of the degeneracy of $G$ with initialization time $f(d_{\mathrm{max}})\cdot n^k$ and amortized update time $f(d_{\mathrm{max}})\cdot n^{1-δ}$.

Abstract: Modern data systems compress data at rest and decompress it only when needed to preserve interconnect bandwidth. This design is often inefficient on GPU-based compute platforms because many conventional compression techniques exhibit serial data dependencies that limit GPU parallelism, leaving resources idle. Recent NVIDIA GPUs address this decoding deficiency through the Decompression Engine (DE), an on-die, fixed-function decompression accelerator for general-purpose compression formats such as Deflate, LZ4, and Snappy. Recent work has proposed string codecs that replace frequent substrings with fixed-width codes from a small, trained dictionary, making each code's lookup independent. While these lookups can run in parallel, the resulting scattered reads and short output writes still do not align well with GPU hardware, which handles contiguous memory accesses more efficiently. We present FastPair, a GPU decoder that optimizes the existing dictionary decoding process by reorganizing lookups and assembling decoded substrings for contiguous output writes. On a B300, FastPair decodes ten real-world columns 2.4 to 4.2x faster than the DE, reaching up to 1.6 TB/s.

Abstract: Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic tree data structures, including Euler tour trees, UFO trees, topology trees, and rake-compress trees, are all significantly outperformed in the sequential setting by link-cut trees, which have been the sequential state-of-the-art for over 40 years. Despite their excellent performance in the sequential setting, designing efficient batch-parallel link-cut trees has remained a major open problem. In this paper, we close this gap by introducing MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees. We exploit the fact that both Euler tour trees and link-cut trees rely on a common dynamic sequence abstraction that supports splitting and joining. We introduce a new batch-dynamic sequence built using treaps that achieves optimal work and depth, and outperforms existing parallel skip list and treap implementations for batch updates, queries, and memory usage. With MOJOS, we develop a new batch-parallel Euler tour tree algorithm that outperforms prior batch-dynamic tree implementations supporting subtree queries. Unlike prior batch-parallel Euler tour trees which rely on skip list's ability to represent cyclic sequences, MOJOS allows any batch-dynamic sequence data structure to be used as a drop-in replacement. Finally, we develop the first theoretically-efficient batch-parallel link-cut tree, which is also the first batch-dynamic data structure supporting path queries to achieve $O(\log n)$ depth for batch updates in the binary-forking model. Our link-cut tree implementation outperforms all known parallel batch-dynamic tree data structures supporting path queries.

Abstract: A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A dynamic dictionary also supports the insert and delete operations. The model with cells of bitsize $n + m + 1$ is used, where $n$ and $m$ are the bitsizes of keys and values. We give 2 dictionaries that use $(1+o(1))K$ cells to store $K$ pairs and in which query makes \emph{non-adaptive probes} to the data structure: a static one in which query makes $\smash{\widetilde O(n^2)}$ probes, and a dynamic one in which it makes $\smash{\widetilde O(n^2 \log K)}$ probes. Also, for the first time, a dictionary is given in which all 3 operations are non-adaptive, but the size is larger: $O(nK)$ cells. The constructions are explicit and, consequently, all operations run in time $\poly(n,m)$. 1-bitprobes storage schemes store a set $S \subseteq \{0,1\}^n$ and answer a membership query by reading a single bit. We introduce 1-bitprobes that are {\em dynamic}. Such a scheme is given whose size is smaller than in all previous constructions which are static. The \textsf{query} operation has runtime $n^{O(1)}$. The operations delete and insert have runtime $n^{O(\log n)}$. The proofs rely on a strategy for an online matching game played on a given bipartite graph. An opponent switches left nodes {\em on} and {\em off}. The strategy needs to assign an irrevocable match to a node when it is turned {\em on}. Such games were introduced in the companion paper~\cite{companion-Hall}. The applications in this paper rely on efficient strategies assuming that each node is turned {\em off} after a polynomial number of rounds. We present efficient strategies for (lossless) expanders.

Abstract: Log-Structured Merge-tree (LSM) aims to achieve high write throughput, but is known to experience the write stall problems when subjected to sustained write pressure. We quantify the occurrence probability and average duration of write stalls in LSM using a queuing model in the write--flush--compaction pipeline, moving beyond existing empirical analysis. The proposed model demonstrates that a monolithic LSM with a single pipeline cannot eliminate write stalls, revealing that internal sharding within the LSM offers an opportunity for fundamental write stall mitigation. To break this structural bottleneck, we propose DiaLSM, an internally shard-based LSM architecture. Instead of forcing all writes through one pipeline, DiaLSM splits the write--flush--compaction path into multiple independent shards and employs dynamic fallback redirection, allowing writes to proceed even when some shards stall. Implemented on RocksDB, DiaLSM achieves up to 2.4x higher throughput, 94% lower stalls, and significantly lower latency than state-of-the-art methods ADOC and Sub-Compaction, as demonstrated by db_bench, YCSB, and Sysbench OLTP evaluations.

Abstract: We revisit the implicit membership problem in Yao's full-table model [Yao, 1981] and obtain, to our knowledge, the first quantitative improvements to his 45-year-old Ramsey bounds, most notably reducing the two-probe bound from tower-type to polynomial. In this model, an $n$-set $S\subseteq\{1,\ldots,m\}$ is stored as a permutation in an $n$-cell table, and queries decide whether $x\in S$. Let $G_q(n)$ be the largest universe size admitting a $q$-probe membership scheme for all $n$-sets. Yao determined the one-probe case exactly, proving $G_1(n)=2n-2$ for $n>2$, but the behavior for $q\ge2$ remained wide open. Fiat and Naor [1993] constructed schemes for universes of size $\exp(n^c)$ for some constant $c>0$ and sufficiently large constant $q$. For the first adaptive case, $q=2$, we prove $G_2(n)=O(n^2(\log n)^2)$. For every fixed integer $q\ge3$, we show that $G_q(n)$ is at most a tower of height $q-1$ with top $n^{1+o(1)}$; in particular, $G_3(n)\le\exp(n^{1+o(1)})$. The two-probe proof avoids Ramsey theory altogether; for larger fixed $q$, we use Ramsey theory only to make the first $q-1$ probes follow a fixed pattern, and then handle the last probe by the same non-Ramsey argument. Somewhat surprisingly, for each fixed $q$, we also show that implicit membership is as hard as implicit search up to a polynomial loss in universe size. Implicit search must return the cell containing $x$ when present and reject otherwise. For the analogous search threshold $H_q(n)$, we prove $H_q(n)\le G_q(n)\le n^q(H_q(n)+1)^{q+1}$ for every $q,n$. Thus, for every fixed $q$, one threshold is at most $\exp(n^{O(1)})$ if and only if the other is. The proofs were first generated by ChatGPT 5.5 Pro without mathematical hints; the membership-search equivalence emerged while pursuing an improved four-probe bound. The authors have validated and edited the proofs and assume responsibility for all content.

Abstract: Agentic pipelines for structured-query generation are rapidly expanding, but it is unclear which part of the loop produces the gain. We use LAST-CQ -- a five-agent, training-free, execution-grounded Text-to-Cypher framework -- as an instrumented testbed, running three counterfactuals over 2,471 live-database queries and six backbones spanning three vendor scale tiers. Removing correction is worth between 3.1% aggregate execution-BLEU against the single-pass system and 12.3% against a no-refinement counterfactual (up to 80.7% for the weakest backbone). Replacing schema-grounded, LLM-synthesised feedback with raw database error strings costs almost nothing (20.9% vs. 19.9% naive exact match; <0.2% end-to-end; equivalent within $\pm 0.075$ set-F1 by two one-sided tests). Spending the same call budget on parallel sampling degrades quality by 10-11%. What works is detecting failure and routing it to a retry, not the feedback sophistication or number of samples. LAST-CQ itself recovers 91.7% of queries that fail under single-pass generation, while a query that succeeds first time still costs exactly one LLM call. We also show that n-gram overlap on serialised results is not a bound in either direction: it over-scores against set equivalence on 65.9% of results while under-scoring against judged semantics. Finally, we calibrate our LLM judge against blind human labels and find it optimistic by 9 points.

Abstract: Relational table learning has recently emerged as an important research direction for modeling multiple tables connected through primary key-foreign key (PK-FK) relationships. Despite recent advances, a principled modeling framework tailored to this task remains underexplored. In this paper, we propose Intra-Inter Relational Table Learning (InRTL), a unified framework that explicitly models dependencies both within and across relational tables. Specifically, InRTL formalizes two complementary interaction patterns: intra-table interactions, describing associations among rows within the same table, and inter-table interactions, describing dependencies between rows across PK-FK-linked tables. To model these dependencies, we develop a column-aware table encoder to generate initial row representations, followed by Transformer-based self-attention and cross-attention modules for intra-table and inter-table learning, respectively. To further improve scalability, InRTL incorporates linearized attention and heterogeneous graph neural networks to simplify the self-attention and cross-attention operations. Extensive experiments on ten datasets covering 24 real-world tasks demonstrate the effectiveness of our approach. Code is available at https://github.com/W1nterFloW/InRTL.

Abstract: With transciphering, a server converts symmetrically encrypted records into homomorphic ciphertexts without learning the records or the symmetric key. For the PASTA cipher, this conversion involves dense linear maps whose implementation depends on how record words are arranged in the ciphertext. We ask whether rearranging a fixed batch can reduce its conversion cost. Instead of storing each record's words in a contiguous block, our layout interleaves records so that cyclic word shifts preserve each record's positions, which form a coset of a cyclic subgroup. For direct evaluation as a sum of masked translations, we characterize the required displacements and relate their counts, 255 for the contiguous layout and 128 for the subgroup layout, to a prior transversal-difference invariant. We implement three equally batched schedules for complete PASTA-3 conversion and subsequent public subset-sum queries in HElib. Across twelve paired corpora under six homomorphic keys, all 24 direct and subgroup conversions and all 48 subsequent queries return the expected values and required zeroes. The median paired ratio of direct to subgroup server cost is 1.60, including fresh public generation, conversion and two queries. The reduction comes with less remaining noise capacity. These results establish a packing-dependent cost--noise tradeoff.

Abstract: Cardinality estimation is at the core of any commercial database system for efficient query processing. Over the decades, non-learning-based estimation techniques (e.g., histogram-based, sampling-based) have been widely used in both commercial and open-source database platforms. However, these techniques are only effective when the number of columns in a table is small, as they cannot properly capture dependencies between multiple attributes. Recently, learning-based approaches have been shown to perform significantly better than the heuristic methods that have been used for the past three decades. Despite this success, existing learned models often struggle to balance memory efficiency and accuracy when dealing with datasets that mix high and low cardinality attributes. In this paper, we propose a deep learning model formally called QEmbed. Our model is built upon the Masked Autoencoder for Distribution Estimation (MADE) auto-regressive framework to learn joint data distributions for selectivity estimation. To improve data representation and overcome the limitations of using a single encoding method, we design a hybrid encoding scheme that combines one-hot and embedding encodings. This hybrid design enables QEmbed to retain fine-grained attribute information for smaller domains while capturing compact semantic patterns for large, sparse domains. We capture attribute correlations by factoring the joint data distribution into a series of conditional probabilities. This approach naturally accommodates both point and range queries. Through extensive experiments, we show that while QEmbed faces a latency trade-off on extremely wide schemas, it provides highly reliable cardinality estimates overall. A key advantage of our model is that it reduces extreme tail errors (maximum Q-errors), avoiding catastrophic estimation failures on complex, highly correlated workloads.

Abstract: Large Language Models (LLMs) are increasingly used to generate structured outputs, but their reliability remains unclear when those outputs must satisfy database-level constraints. We study this issue through database normalization, involving reasoning about functional dependencies, lossless join decompositions, and inter-table constraints. We introduce a Database Normalization Benchmark (DNBENCH), comprising 3,275 samples for evaluating LLM-driven database normalization from 1NF to BCNF. DNBENCH uses a three-axis protocol to measure semantic equivalence, structural accuracy, and logical validity. Across Single, Complex, and Real World levels, DNBENCH uncovers recurring failures in dependency inference, schema decomposition, and inter-table constraint reconstruction. We further propose Multi-Agent Reasoning for Schemas (MARS), which separates evidence extraction, violation diagnosis, and decomposition planning from schema generation and verification. MARS improves the DNB-SCORE by 82.0% over the single-prompt baseline. All artifacts will be released upon acceptance.

Abstract: Long-running AI agents may read state, reason, wait for tools or human approval, and perform an external action much later. The state that justified the action can change in the meantime. For example, after an agent proposes an 80 GBP refund under a limit of 100, a customer-name change affects only presentation metadata, a new limit of 90 still permits the refund, a limit of 50 invalidates it, and a refund issued by another worker must prevent a duplicate. Standard optimistic concurrency control and version checks can detect that previously read state has changed, but by themselves do not determine whether that change invalidates the pending action's justification. We call any detected version change a version conflict; when that change invalidates the action's justification, it is also a decision conflict. ATR records the explicit, executable conditions that justify a pending action and rechecks only the conditions affected by a change before releasing the external operation. It can retain the action, refresh non-decisive metadata, require replanning, or block execution; a target-side transaction or compare-and-set binds checked state to commit. Across 210,000 controlled executions over 15 mutation cases, ATR matched every developer-specified outcome with no false allows or blocks. In ten durable SQLite checkpoint/resume cells, it evaluated 0.6 conditions per change versus 6.0 for FullScan. At 4,093 recorded reads, ATR took 9.3 microseconds versus 2595.9 microseconds for FullScan. These deterministic results establish controlled feasibility, not production generality or automatic extraction of the required conditions.