database administrators

Abstract: Join-aggregate queries count or sum matching rows for each pair of values, often over skewed sparse relations in which a few values are frequent and most pairs of values never co-occur. Conventional execution plans materialize billions of intermediate join rows, taking minutes to tens of minutes per query. Recent matrix-based solutions reformulate these queries as matrix multiplication to reduce or avoid this materialization. However, they remain slow because they either store result cells for non-matching pairs or still materialize intermediate join rows for infrequent values. We present Tessera, a skew-aware join-aggregate operator for database engines that avoids both sources of overhead. Specifically, Tessera computes a sparse matrix product directly over the engine's rows, emits only nonzero cells as result rows, and prunes values that cannot meet the query's threshold before multiplication begins. It also offloads the dense block formed by pairs of the most frequent values to a CPU matrix accelerator when that block is dense enough. Experimental results show that Tessera is faster than the fastest existing system by 2.8x to 18.8x. In addition, Tessera outperforms DuckDB's execution plans by up to 1,802x.

Abstract: Authentic records can support unauthorized narratives when their qualifications, query scope, or counterevidence are silently dropped. We present revision-bound evidence cuts, a framework for authenticating both supporting and opposing inference obligations across changing source versions. Signed complete-update frontiers permit transport of unaffected certificates, alternative-cut recovery, and an exact certified-reuse radius given by a frontier-hypergraph transversal number. Their source obligations induce an integral model of context-bound authorization. To secure database-derived claims, we introduce an authenticated relational query contract that binds original source records, complete selected bags, counting units, parameters, and aggregates independently of execution strategy. A full-source verifier checks 16,824 Chogha Mish records across SQLite scans, indexes, and materialized views; three valid strategies agree and eight contract/view mutations are rejected. A separate 340-row NISP cohort shows that changing the admitted weighting rule can reverse a comparison while preserving every source record. A frozen English text-to-frame compiler produces qualified evidence receipts, with linguistic accuracy evaluated separately from cryptographic integrity. We also separate logical-source from transport commitments so lossless re-encoding need not invalidate unchanged scientific evidence. The SCENE prototype evaluates signed revisions, authenticated queries, scoped disclosures, and adversarial mutations at scales reaching one million source records. These guarantees rely on declared policies and independently pinned trust roots; they authenticate specified computations and obligations, not historical truth, complete counterevidence, or institutional endorsement.

Abstract: Integrity constraints have been central to the relational model since its inception. However, beyond keys, single-row CHECKs, and referential integrity, most constraints are enforced by application layers today. SQL ASSERTIONs, standardized in SQL-92, remain poorly supported by major RDBMSs. This has become increasingly unacceptable due to two developments. First, LLM-driven applications and agents increasingly issue queries and updates directly against databases, bypassing application layers where invariants reside. Such code may be generated on demand and discarded afterwards, making the database the only durable component that can encode and enforce these invariants. Second, natural constraints in higher-level conceptual models, such as E/R and property graphs, become fragmented across relations under mappings chosen for performance. The resulting multi-relation constraints lack direct database support, and only some can be efficiently enforced using existing mechanisms such as triggers. These developments motivate an overhaul of how constraints are defined, mined, managed, and enforced in data management systems. As a first concrete step, we introduce constraint indexes, which represent constraints spanning multiple relations as transactional access paths, and implement a proof of concept as a PostgreSQL extension. Constraint indexes enforce constraints arising from distributed inheritance hierarchies, folded relationships, and folded weak entities, as well as cardinality bounds and functional dependencies, at low overhead relative to no enforcement. Across these workloads, they outperform the better of the correctness-preserving baselines by up to 2.41 times. We also show that LLM-driven writers frequently violate unenforced constraints and behave erratically when provided with a list of constraints to enforce. We close by discussing a few research challenges raised by this agenda.

Abstract: Entity matching is the task of deciding whether two records describe the same real-world entity. Current entity matching methods rely on pre-trained language models (PLMs) which require task specific fine-tuning or generative large language models (LLMs) which do not require task-specific fine-tuning but are slow and expensive at matching large record sets. Decision models are a new class of LLM-based models that return a probability for each predefined answer option rather than generate text. This paper investigates decision models as an alternative to generative LLMs and fine-tuned PLMs for entity matching. We evaluate six decision models in a zero-shot setting across eight benchmarks and compare their performance with that of the generative LLM GPT-6 Luna and the PLM-based matcher Ditto. Our experiments show that, without task-specific training data, the four strongest decision models achieve mean F1 scores close to that of GPT-6 Luna, with the best model slightly surpassing it. This model also outperforms Ditto on six of the eight benchmarks. All decision models are faster than GPT-6 Luna, and most are less expensive. For three of the four strongest decision models, the predicted match probabilities are well calibrated without requiring any task-specific recalibration. A model cascade that routes the least confident record pairs to an ensemble of generative LLMs improves the mean F1 scores of the four strongest decision models by 1.9-4.0 percentage points. Using the best decision model and its best-performing prompt for each benchmark, the cascade surpasses the highest published F1 scores from literature on four of the eight benchmarks.

Abstract: Enterprise sales-order systems rely on manually maintained configuration rules to determine fields such as payment terms, shipping points, and sales ownership. When these rules are incomplete or stale, operators must enter values by hand, and downstream errors spread into billing, logistics, and reporting. This paper studies whether missing or outdated rules can be recovered from historical transactions instead of being relearned as opaque statistical patterns. We introduce a knowledge-graph-guided workflow in which an LLM agent proposes candidate business keys, meaning column combinations such as customer and document type, validates them through SQL profiling, and compiles the resulting evidence into deterministic cascade lookups. The LLM is used only during offline rule discovery. At inference time, prediction is a transparent key lookup with no model-serving requirement. Experiments on enterprise sales-order prediction and public relational benchmarks show that cascades are most effective when fields follow stable business rules, while learned graph models remain preferable when prediction depends on temporal or neighborhood patterns. Drift analysis further turns residual errors into diagnostics for configuration maintenance. Code and data: https://github.com/Fireblossom/CascadER.

Abstract: The focus of this paper is on query processing and not search (approximate or exact). The goal is to find all or k answers and the expressiveness of a query (as opposed to a search expression which is typically simpler) is considered important. Although SQL query processing has matured over the last several decades, query processing over graph data has not received the same attention. Only recently, systems, such as Neo4J, and others have started using graphs for data representation on a large scale. Their approaches and algorithms remain proprietary. In this paper, we address the problem of answering graph queries and their efficient processing on arbitrary-sized graphs. We propose the partitioning of graphs and the use of the distributed paradigm to achieve efficiency and scalability. Our approach takes a subgraph as query input including wild cards and comparison operations. Our partitioned approach leverages focused exploration and distributed processing to achieve the desired parallelism and improve the response time. We also present heuristics to reduce the number of partitions loaded for query processing. We present our partitioning algorithm, distributed processing architecture used, and load balancing for computing query answers. We establish the correctness of the approach in the presence of partitions, compare heuristics for load balancing, and extensive experimental results over large synthetic and real-world graph data sets.

Abstract: Policy-as-Code (PaC) has emerged as a foundational paradigm in cloud-native systems. However, repairing Rego policies remains challenging due to their strict syntax, declarative semantics, and specific verification requirements. Existing automated program repair (APR) methods are mainly designed for mainstream languages and struggle to accommodate the unique policy logic and repair workflows of Rego. Thus, Rego policy repair remains a manual process driven by trial and error. To address this, we introduce RegoBench, the first automated Rego policy benchmark comprising 1,159 real-world defects, and propose RegoMender, a feedback-guided multi-agent framework. Collaborating via a shared blackboard and an atomic toolkit, RegoMender dynamically executes patching, rewriting, or rolling back, to resolve complex repair scenarios. Evaluated on RegoBench, RegoMender achieves syntactic and test-based semantic success rates of 82.9\% and 77.9\%, respectively, outperforming the strongest baseline by 13.4\%. Unlike other approaches whose performance drops in complex scenarios, RegoMender maintains effectiveness across single-step and chained repair tasks. Furthermore, it generalizes strongly across HCL and SQL and achieves an 86.4\% repair rate on 132 real-world CVE vulnerabilities, proving its robustness and practical utility for security.

Abstract: An LLM-generated repair action specifies which records to change and by how much. A failed action may still contain a useful target set or numerical update, depending on how the two are paired. We evaluate this problem in traffic networks and databases, where aggregate observations obscure the records that need correction. We examine the pairings by executing each combination from the same initial state, using a reference action that restores the affected records. In 76 of 114 traffic actions, the gain from correcting both parts exceeds the sum of the gains from correcting each part alone. Six of these actions become worse after either correction alone, but improve when both parts are corrected. In database repair, replacing only the proposed update with the reference update worsens 17 of 108 model actions, all of which select unaffected records. We also test whether parts of two proposals can be reused. On held-out observations, selecting among the proposals and their recombined target-update pairs recovers 61.6% of the reference action's loss reduction, compared with 58.0% from selecting between the proposals alone.

Abstract: Runtime query similarity identification supports several activities, including workload analysis, identifying recurring behaviour, auditing, debugging, and anomaly detection. Existing methods for evaluating query similarity mostly rely on SQL text, execution plans, or result values but do not account for input data or how results are derived during query execution. This paper proposes a novel approach using data provenance for query-template identification. We construct query-level profiles that capture explicit data dependencies, occurrence frequencies, and structural properties by aggregating tuple-level Lineage and Why-provenance across entire query results. We also derive Provenance Structural Descriptors (PSD), which summarise these profiles using a small set of numerical features. We evaluate our proposals using these profiles to identify query templates over \(12{,}500\) distinct query instances generated from parametrised TPC-DS query templates. The experimental evaluation shows that query templates can be identified solely from their provenance footprints, and that accuracy improves as more historical data becomes available. It also shows that PSD achieve high classification accuracy with limited training history and low test-processing cost.

Abstract: Cardinality estimation is fundamental for query optimization in database systems. Histogram-based estimators are widely used for their simplicity and efficiency but rely on point-centric partitioning that assumes record independence. This assumption breaks in trajectory data, where records from the same moving object show strong spatiotemporal dependencies. Conventional axis-aligned histograms therefore fragment trajectories across partition boundaries, leading to overestimation through duplicate counting. This error reflects a structural limitation of partition boundaries that are misaligned with trajectory-induced density patterns. To this end, we propose TraHist, a histogram-based estimator approximating density-aligned partitioning via efficient grid-based propagation. TraHist builds density-adaptive rectilinear buckets to preserve trajectory continuity and local density coherence while keeping histogram efficiency. Experiments on large-scale real-world datasets show that TraHist reduces estimation error by over 20x relative to the strongest competing estimator in query regimes where trajectory fragmentation is a dominant source of estimation error, while maintaining sub-millisecond query latency and competitive construction cost.

Abstract: We evaluate eviction policies that consider the lengths of the objects being cached for different cache sizes (cost) and different workloads. Workloads include the Independent Reference Model and real-world production traces. In particular, hybrid policies are considered for segmented caches. A working-set approximation is developed for SIEVE as well as its length-aware extension.

Abstract: Recent work has shown that LLMs can synthesize highly specialized database systems for fixed workloads, but these systems replace the DBMS's native storage and assume static data: users must migrate their data, often give up ad-hoc queries, and lose acceleration once the data changes. We present JetStream, which instead generates query-specific accelerators that extend an existing DBMS. Given a set of parametrized query templates, a staged agentic workflow synthesizes accelerators that run directly over the DBMS's native tables and may maintain custom auxiliary state, while the DBMS remains responsible for storage, transactions, recovery, and all other queries. A fixed, engine-neutral substrate handles engine-specific hooks and keeps auxiliary state transactionally consistent under writes. JetStream generates two kinds of accelerators: tested accelerators, which may use any optimization and are validated by differential testing, and verified accelerators which trade some performance for a machine-checked proof that every answer satisfies a trusted specification derived from the SQL. On TPC-H at SF=20, JetStream achieves a $315 \times$ geomean read speedup over DuckDB ($93 \times$ verified) and retains $120 \times$ under a continuous update stream of 10,000 modified rows per second.

Abstract: Reinforcement learning makes language models better at solving tasks, but the same mechanism also rewards guessing. When success is the only way to earn reward, opting for a safe fallback is always worse than a long-shot attempt. When a wrong action can corrupt a database or ship broken code, that incentive can be costly. Therefore, we propose training models to fail gracefully: to preserve successful behavior whenever possible while learning to execute a safe fallback policy when acting would be unreliable. However, naively using policy gradients with intermediate reward for fallback behavior is brittle due to unfavorable optimization dynamics. We address this challenge with GracefulRL, which reshapes the optimization landscape to promote graceful failure. Importantly, this behavior emerges directly from outcome-level reward signals, without annotations specifying when to fall back or additional inference-time machinery such as a verifier. Across a range of tasks and scales, we train models that largely preserve their task-solving capability while selectively falling back when acting would be unreliable. More broadly, our results show that reinforcement learning can not only incentivize models to succeed, but also to reason about the limits of their capabilities and change course when they determine that success is out of reach.

Abstract: Harness optimization improves LLMs by refining reusable prompts and scaffolding, yet requires further adaptation for program generation tasks such as text-to-SQL and text-to-Python. Existing methods often rely on LLM reflectors to propose harness updates, which can fix observed failures but also disrupt previously correct behavior. Text-to-code tasks offer a natural way to mitigate this issue: we can execute generated outputs, allowing us to evaluate and verify the effects of proposed updates directly. Building on this signal, we introduce \textsc{HERO} (\textbf{H}arnessing \textbf{E}vidence for \textbf{R}efinement and \textbf{O}ptimization), which combines offline and test-time harness optimization. At the first stage, \method{} learns reusable prompt updates from execution-verified successes and failures and validates candidate revisions before adoption. At test time, we treat the generated code as an instance-specific harness and refine it using execution feedback. Across four SQL, Cypher, and Python benchmarks, \method{} achieves the best offline performance, improving pass@1 by \(7.6\) points over the initial prompt, while test-time refinement adds another \(2.0\) points and improves execution efficiency.

Abstract: This paper proposes a methodology for decoupling the authorization logic of a relational database from its core data management engine, enabling specification of advanced access control policies with minimal changes to the code base. Our decoupled authorization architecture, which we call ARCADE, externalizes access request resolution to a formally verifiable policy engine (e.g., Cedar), while the database itself enforces those decisions. We showcase the capabilities of ARCADE on two widely popular open-source databases, namely MySQL and PostgreSQL. Purpose built lightweight plugins add an Attribute-based Access Control (ABAC) layer that augments the native discretionary and role-based access control capabilities of these databases. ARCADE supports highly expressive policies using attributes of subjects, objects, and the environment, and the use of Cedar enables easy auditing and verification of the specified policies. It follows a design principle that mitigates potential risks in segregating authorization from the database core through low footprint, network isolation, and a policy composition methodology that does not negate any native authorization. Experiments on TPC-C, TPC-B, and a custom workload show that ARCADE incurs negligible performance overhead, for instance, less than 3.9% throughput penalty for MySQL (1.3% for PostgreSQL) on industry standard TPC-C benchmark.

Abstract: A wide range of important cloud applications, e.g., database analytics, graph analytics, and genome analysis, spend a considerable amount of time performing bulk bitwise operations (e.g., AND, OR, XOR). These applications often operate on highly sensitive data, making data privacy a critical concern. Homomorphic encryption (HE) enables secure computation on encrypted data without requiring decryption, ensuring privacy in untrusted and shared environments. We analyze 13 end-to-end applications across three domains (healthcare, graph, and database analytics) and observe that bulk bitwise operations take 62-100% of the execution time of the healthcare and graph workloads. The key problem is that existing HE approaches perform them with high-latency homomorphic operations (e.g., multiplication or lookup tables) and significantly increase the data size. Our goal is to enable fast bulk bitwise operations on homomorphically encrypted data by designing an efficient HE algorithm that reduces the use of these costly operations. To this end, we propose HULK, which performs two key steps: (1) it constructs bulk bitwise operations using low-cost homomorphic additions, which compute the Hamming weight of the encrypted operand bits in every slot of a packed ciphertext without any homomorphic multiplication, and (2) it decodes the result of an AND, OR, or XOR from the Hamming weight with a single indicator polynomial, keeping the result in the standard encoding. Across 13 end-to-end applications in healthcare, graph, and database analytics, HULK improves performance over the arithmetic approach used by prior works by up to 7.26x (CPU) and 6.65x (GPU), and on average by 2.32x/1.78x/1.45x (CPU) and 2.08x/1.70x/1.51x (GPU) for healthcare/graph/database analytics. When we increase the reduction depth in a representative application, HULK's speedup grows to 10.10x over the state-of-the-art GPU baseline.

Abstract: We present the first dynamic maximal independent set (MIS) of a graph with $n$ vertices and up to $m$ edges under edge updates in the prediction model, where a predicted update sequence is available for offline preprocessing before the real updates arrive online. We consider the incremental (insertion-only), decremental (deletions-only), and fully dynamic (insertions and deletions) models. Without predictions, deterministic algorithms need worst-case update time of $O(n)$ for decremental and $O(m)$ for incremental and fully dynamic settings. Bernstein et al.~[SODA26] proved under the combinatorial BMM conjecture, combinatorial incremental algorithms against an adaptive adversary require $Ω(n^{1-o(1)})$ amortized update time. We present deterministic incremental, decremental, and fully dynamic algorithms whose update times depend on the prediction error. This error is measured by the number $η_e$ of mispredicted updates, and by the number $η_v$ and total degree $η_v^*$ of vertices whose MIS membership was mispredicted. With $O(mn)$ preprocessing, our decremental and incremental algorithms achieve worst-case update times $O(η_v)$ and $O(η_e+η_v^*)$, respectively. Our fully dynamic algorithm achieves $O(η_e+η_v^*)$ worst-case update time with $O(un)$ preprocessing for $u$ updates. We also give space-efficient variants using $O(m)$ space for the decremental and $O(m\sqrt{m})$ for the incremental setting, at the cost of a logarithmic overhead in worst-case update time. Our algorithms satisfy consistency, robustness, and smooth degradation, the required properties of algorithms with predictions. They can also utilize the general error correction framework of Khan et al.~[Arxiv26], relaxing the error measures from first point of difference to prefix matching (for partially dynamic) and set edit distance (for fully dynamic), maintaining the same bounds.

Abstract: Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of $Θ(\log k)$, where $k$ is the cache size. We study weighted caching with per-request predictions, where each page request is accompanied by a prediction of the next arrival time of the same page. For unweighted caching, such perfect predictions suffice to implement Belady's offline optimal rule. For weighted caching, however, previous work shows that a logarithmic lower bound persists even with perfect predictions on adversarial request sequences. Stochastic assumptions alone are also insufficient: the classical caching lower bounds already apply to uniform independent requests. In this work, we ask whether combining these two sources of additional information can overcome this barrier, and answer this question affirmatively. Specifically, we develop an efficient, deterministic cache eviction policy that achieves a competitive ratio of $15.75$ using perfect per-request predictions when page requests are drawn independently from an arbitrary, known static distribution in every step, and page costs are arbitrary. Our algorithm's performance degrades gracefully under erroneous predictions: we prove a bound of $O(\min\{1+E,\log k\})$ on the competitive ratio, where $E$ aggregates each page's average prediction error, and may be unknown to the algorithm.

Abstract: An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval graph by adding at most $k$ edges. Although the problem is fixed-parameter tractable when parameterized by $k$, whether it admits a polynomial kernel has long been an open question. We resolve this question by giving the first polynomial kernel for \textsc{Interval Completion}. Our main contribution is a parameter-preserving polynomial-time reduction from \textsc{Interval Completion} to \textsc{Odd Cycle Transversal} (OCT). Combining this reduction with the known randomized and deterministic polynomial kernels for OCT and a polynomial-time reduction back to \textsc{Interval Completion}, we obtain a randomized kernel with $\widetilde O(k^{18})$ vertices and $\widetilde O(k^{36})$ edges, and a deterministic kernel with $O(k^{36})$ vertices and $O(k^{72})$ edges. Here, $\widetilde O$ suppresses polylogarithmic factors in $k$.

Abstract: Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $Ω_{\varepsilon,δ}(\log h)$ or $Ω_{\varepsilon,δ}(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\varepsilon,δ)$-DP algorithm with an additive error margin of $O_{\varepsilon,δ}(\log\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.

Abstract: Modern DBMSs expose hundreds of configuration knobs, resulting in a high-dimensional and heterogeneous search space that makes automated tuning costly. Existing ML-based tuning systems typically treat the configuration domain as box-constrained and rely on workload feedback to implicitly capture inter-knob relationships. However, DBMS documentation specifies deterministic knob dependency constraints, particularly ordering constraints, that characterize structurally valid regions of the configuration space. We present CATune, a constraint-aware Bayesian optimization (BO) framework that models deterministic inter-knob ordering constraints as structural components of the search domain. Instead of learning feasibility boundaries through sampled violations, CATune performs optimization within a constraint-consistent subspace. We develop a topology-aware sampling strategy that respects dependency structure during exploration and avoids the inefficiencies of post-hoc constraint handling. To enable automated constraint discovery, we further design a precision-first extraction pipeline that combines LLM-based parsing with reliability safeguards to mitigate hallucinated dependencies. Experiments on PostgreSQL and MySQL using TPC-C and TPC-H workloads show that CATune substantially improves both sample efficiency and final tuning quality across surrogate models and BO frameworks. Under default ranges, CATune reaches the baseline optimum up to 12.5x faster and improves throughput by up to 63.37%. The improvements persist under knowledge-guided reduced ranges and alternative optimization implementations. These results demonstrate that explicitly modeling system-defined deterministic ordering constraints enhances optimization robustness and system stability.

Abstract: Approximate functional dependency (AFD) strength measures are commonly used to prioritize candidate dependencies, including when selected dependencies support downstream tasks such as error detection. This practice implicitly assumes that dependencies ranked higher by strength are also better candidates for the task they are intended to support. We test this assumption directly for error detection. We evaluate detection value through precision and recall without imposing a single weighting on different error types, and introduce an explicit false-positive/false-negative cost only when a single candidate-selection objective is required. Across three real-world relations from an established AFD benchmark, $1{,}155$ corruption-and-detection runs, and $513{,}480$ candidate-level evaluations, we find a clear asymmetry. Strength measures tend to track precision positively, but their associations with recall are substantially less stable, with both magnitude and direction varying across measures and experimental settings. Strength-based prioritization is also unreliable at the ranking level: top-$k$ sets chosen by strength often have little overlap with those favored by actual detection performance, and strength-based selections can incur substantial regret. An important part of the recall mismatch is associated with structural detection opportunity under the candidate equivalence-class partition, which tracks recall more consistently overall than the strength measures we evaluate. Corruption mechanism and several static structural properties account for selected effects but do not provide a common explanation across settings, leaving part of the mismatch unresolved. Overall, AFD strength and detection value are distinct and should be evaluated separately.

Abstract: The unprecedented computational scale of modern artificial intelligence depends on complex, multi-billion-transistor Systems-on-Chip, yet the workflows that verify these chips remain stubbornly manual. Although Large Language Models (LLMs) have made rapid inroads into Electronic Design Automation (EDA), approximately 74.6% of existing studies target static Register-Transfer Level (RTL) code generation, leaving post-simulation verification and interactive waveform debugging largely untouched. We introduce Back-to-the-Future (BTTF), an end-to-end agentic framework that closes this infrastructural gap. BTTF distills massive, unstructured simulation dumps into a normalized relational SQLite database and couples it with a collaborative multi-agent orchestration engine that translates natural-language verification queries into schema-aware SQL while correlating signal anomalies with versioned RTL repositories. Across a 150-query benchmark, BTTF attains 95.33% execution accuracy, charting a practical path toward autonomous EDA verification.

Abstract: LLM agents for clinical text-to-SQL applications reason autonomously over multiple steps but cannot assess whether their own reasoning or outputs can be trusted. In high leverage applications such as healthcare, this presents a critical risk where system mistakes can be costly. These reliability failures are also resource failures: an incorrect reasoning trajectory spends computation budget on outputs that must be discarded. We introduce Sentinel, a trajectory-derived, classifier-based confidence layer that analyzes an agent's reasoning, code and database outputs to decide at three points whether to stop: refusing unanswerable questions before the agent runs, halting doomed trajectories mid-run, and withholding untrustworthy answers at delivery. Here, utilizing Chow's rule, we optimize decisions under the EHRSQL shared task's Reliability Score, which penalizes incorrect answers given a utility weighting, and find on the benchmark EHRSQL that Sentinel raises this score from +0.08 to +0.24 when mistakes have a low utility weighting, well above the +0.03 earned by refusing every question, with delivered-answer accuracy rising from 54% to 69% as coverage falls from 84% to 55%. At higher stakes the agents we test rarely answer reliably enough to deliver, and Sentinel detects this on its own, abstaining to that same +0.03 where the unmonitored agent scores -3.02. The same stopping decisions cut computation: at low stakes, where the system still answers, Sentinel eliminates 13-28% of agent steps at little or no reliability cost.

Abstract: Modern query optimizers use analytical cost models to estimate the cost of a given query plan. Such cost models are typically functions of a set of "cost units" that specify unit CPU cost when processing a row or unit IO cost when accessing a disk page. These cost units are traditionally viewed as platform-dependent constants, that is, they require a one-shot calibration when a database is deployed on a hardware/software platform, but are fixed afterward regardless of the query being optimized for. Some very recent work has taken a different perspective by viewing these cost units as tunable parameters that we call "cost model parameters (CMPs)" in this paper. However, so far there is no approach that offers any optimality guarantee for the tuning results. We present a new approach to systematically explore the query plan space spanned by the CMPs and find the best plan in terms of execution time. Compared to alternative exploration approaches that use random search (RS) or Bayesian optimization (BO), our new approach is deterministic and, therefore, avoids the undesirable instability that is inevitable when applying RS or BO. Moreover, it is guaranteed to find all candidate plans in the query plan space without suffering from the overhead of an exhaustive enumeration. We also present a set of optimization techniques to reduce the overall evaluation time spent on executing the candidate plans found, a factor that is often overlooked by previous work but is critical from a practical point of view. Experimental evaluation on top of PostgreSQL and Microsoft SQL Server demonstrates the efficacy of tuning the CMPs, which can find query plans that are orders of magnitude faster in execution time than the ones found by RS or BO.

Abstract: Given a fixed set of pending deletion requests, retraining from scratch after each request is prohibitive, so a prescribed request-wise policy processes them sequentially. The resulting terminal model can depend on their order. Rather than prescribing an ordering rule, we study the permutation objective induced by the fixed policy and ask when it admits simpler structure. We identify two independent reductions: position additivity represents the objective by request--position costs, reducing optimization to assignment and, with a shared positional profile, sorting; suffix localization removes dependence on the distant prefix while retaining interactions among the surviving requests. Under shared affine updates, we characterize the quadratic interactions that obstruct additivity, prove the reductions' independence, and show that suffix-conditioned assignment improves the approximation rate from O(p^L) toO(p^(2L)). Experiments recover both structures in executed objectives. A controlled damped-Newton sweep shows that stronger contraction shifts the objective toward shorter, more suffix-specific dependence, while two full-network policies exhibit distinct positional and within-suffix structure. Structures identified from compact execution sets also predict unseen orders. These results frame deletion ordering as identifying the computational structure induced by the executed updates.

Abstract: We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial in $1/\varepsilon$ and independent of the number $n$ of vertices. Previously, the best bound known for this problem was the $\operatorname{poly}(\log n)$-query guarantee that follows from the general outerplanar-graph tester of Babu, Khoury, and Newman (2016) in the stronger $\textit{adjacency-list model}$, which provides exact degree queries and indexed access to neighbors. Our tester has $\textit{two-sided error}$, which is necessary in general: induced-$P_3$-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.

Abstract: Synthetic data generation is dominated by the fit-then-sample paradigm: a generative model is trained on a private dataset and then sampled from. Despite its widespread adoption, this paradigm faces three challenges: (1) a new training run is required for every dataset; (2) different data modalities, such as single tables, time series, and relational databases, require task-specific models and feature engineering; and (3) the resulting model is opaque, making its behavior under data constraints difficult to inspect. We propose GENSCRIPT, an inference-only pipeline that eliminates model training. GENSCRIPT computes a deterministic statistical profile of the source data (column types, ranges, missingness, categories, correlations, etc.) and passes it--rather than raw rows--to a language model to infer field semantics and cross-column integrity constraints. A coding agent then compiles the profile and constraints into an executable, auditable sampler. This unified approach supports single-table, temporal, and relational data without task-specific modeling. Across four single-table benchmarks, GENSCRIPT builds generators in 2 minutes and samples 50k rows within 6 seconds, while remaining within a few points of leading methods in marginal fidelity. Notably, it is the only method that perfectly preserves a 1-to-1 mapping between columns in the Adult dataset. On a smart-building dataset, it produces conditional time series that more closely match the real distribution than two baselines and perfectly preserves primary- and foreign-key relationships in the corresponding relational database.

Abstract: We design, implement, and evaluate KathDB-FAO, a new query evaluation subsystem for our KathDB multimodal DBMS. KathDB-FAO takes as input a query in natural language (NL) and converts it into a query execution plan where each operator is a function whose body is synthesized during query evaluation, which allows powerful query-specific optimizations. To generate accurate and efficient plans from NL, KathDB-FAO first extracts fine-grained atomic actions for correctness, then establishes contracts on the inputs and outputs of those actions and groups them for efficiency, and finally synthesizes the function for each group on the fly. On SemBench, KathDB-FAO cuts execution cost by 58.8% on average across scenarios compared with the next best system, at comparable or better quality.

Abstract: We describe the integration of io_uring into Oracle Database's storage layer and the architectural decisions required to deploy it in a production multi-process RDBMS. Our design uses per-process ring contexts that eliminate inter-process synchronization, a shared buffer registration mechanism now part of the mainline Linux kernel, and a transparent fallback to libaio on error. Evaluation on an internal development build of Oracle Database 26ai shows that io_uring's benefits concentrate on asynchronous batched I/O paths: on a mixed OLTP workload (TPC-C), io_uring delivers identical throughput while reducing server CPU utilization by 1.2 percentage points through more efficient background writes; on analytical queries (TPC-H), CPU per query drops by 8.5% (geometric mean). Isolating the write path alone shows 29% lower CPU per write and 34% higher throughput. Synchronous read paths -- the dominant I/O in OLTP -- show no improvement and even increased CPU usage for very large I/O sizes. These results motivate a hybrid I/O architecture that retains pread/pwrite for synchronous operations, adopts io_uring for asynchronous batched I/O, and falls back transparently to libaio -- a selective strategy that may also be relevant to other database systems facing the same integration question.

Abstract: The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $α$. The algorithm uses $O(\varepsilon^{-4/3}α^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $α$ and $\varepsilon$, this improves the best known previous space bound from $O(n^{4/5} \text{polylog} n)$ to $O(n^{2/3} \text{polylog} n)$. The algorithm is a linear sketch and requires no bounds on the number of deletions or on the arboricity of intermediate graphs.

Abstract: We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

Abstract: Multi-tenant tools commonly accept a tenant identifier and validate it against the caller's entitlement. For a large language model (LLM) agent, that pattern delegates resource selection to a process whose context may contain attacker controlled instructions. We formalize this stochastic deputy problem and present a structural defense: remove tenant identity from the Model Context Protocol (MCP) tool schema, bind scope to a verified credential, and enforce it below the agent. In a 373-trial ablation across eight model configurations and two transports, a correctly validated tenant parameter served every out-of-scope attempt: 26 of 26, or 26 of 41 plausible-pretext trials overall. With the parameter removed, no tool signature could express the read. Twelve of 56 trials instead escaped the interface by forging writable scope, showing that interface invariance requires cryptographically protected context. On a production dataset containing multiple GBs of data, set-valued scope caused a measured $57\times$ latency ratio under function-wrapped membership predicates; a JSON_TABLE lateral join recovered index access where the tenant key was indexed. The evaluation also exposes deployment limits, including an entitlement-size query-planner cliff and incomplete index coverage. The result is a tenant-isolation argument that depends on enforceable interfaces and credentials rather than model compliance.

Abstract: Set reconciliation, where two parties each holding a large set of elements aim to identify their set difference, is a fundamental task in many areas. There are two important metrics in this problem: time (computation cost) and space (communication cost). Most previous work focuses on optimizing one metric at the expense of the other. We present XYZ-Sketch, proving that it is possible to achieve near-minimal space and $O(1)$ time updates simultaneously. Specifically, for sufficiently large $d$, XYZ-Sketch reconciles sets with only $(1+\varepsilon)d$ elements for communication, while achieving $O(1)$ insertion time and $O(d\log V)$ decoding time. Here, $d$ and $V$ denote the size of the difference between two sets and the universe size, respectively. We further establish a broad fixed-support canonical model for the problem, showing that, under an open extremality conjecture, XYZ-Sketch is asymptotically optimal within this model. Experiments validate the predicted near-optimal performance of XYZ-Sketch. The source code is available at https://github.com/djwj233/XYZ-Sketch.

Abstract: Database management systems increasingly serve dynamic and exploratory workloads, yet many of their decisions still rely on low-level signals such as recency, frequency, and address locality. These signals capture how data was accessed, but not what is being examined or how an analytical focus evolves. We argue for treating workload semantics as a first-class control signal for anticipatory decision making. Central to this view, we introduce semantic locality and semantic trajectories, which capture relationships among nearby queries and how those relationships evolve across a session. We propose a framework that represents semantic context at the data, query, and session levels, models its evolution over time, and translates it into task-specific utility estimates. We instantiate this framework in semantic prefetching and semantic cache eviction, which share a semantic layer to make two separate decisions. Prefetching uses semantic trajectories to anticipate future accesses beyond what address-based locality can capture, while eviction uses semantic relevance to inform block replacement. These systems provide initial evidence that shared semantic context can support multiple DBMS components. We further outline how this principle can extend to other decisions and data systems, and discuss key challenges in representation, cost, adaptation, and evaluation.

Abstract: Knowledge graph foundation models such as ULTRA achieve zero-shot link prediction on unseen graphs through dedicated architectures that hard-code a transfer mechanism. In this work we move that mechanism out of the architecture and into the representation, by \emph{reifying} the input graph: every fact becomes a node, connected to its subject, object, and relation type through a fixed vocabulary of six meta-relations, with relation types as anonymous shared nodes rather than model parameters. On this representation, five textbook GNNs (GAT, GINE with sum and with mean+max aggregation, GraphSAGE, R-GCN), each trained on a single knowledge graph of 4,245 triples for 30 minutes on one NVIDIA A100, transfer zero-shot to 40 inductive link-prediction benchmarks. The best of them, an off-the-shelf GAT, matches ULTRA, a dedicated foundation model pretrained on three graphs, across ULTRA's own evaluation suite. The same fixed vocabulary extends to relational databases, a row becoming an entity and a foreign-key column a relation type; a preliminary probe on two unseen databases, with no cell values, schema text or in-context labels, shows a model of this family pretrained on three knowledge graphs ranking foreign-key targets far above random-initialization and degree controls. We release the code, the checkpoints, and the evaluation pipeline for all 40 benchmarks.

Abstract: Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $Θ(n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.

Abstract: Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvable in polynomial time whenever their length slices are preserved by a common fixed edge operation on a finite domain. The algorithm computes compact representations of the complete solution relation and its projections. Its main ingredient is a polynomial-time compilation of nondeterministic finite automata into the fork witnesses and small projections required by the few-subpowers algorithm. In the Mal'tsev case, a direct proof is polynomial also when the domain and operation table are supplied as input, answering the Mal'tsev tractability question for automatic constraint satisfaction. We also characterize all invariant relations of a family of 3-edge algebras with neither Mal'tsev nor near-unanimity terms. Their normal forms combine Boolean activity constraints with affine value spaces and yield canonical quadratic-bit representations constructible from NFAs or arbitrary generators. For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations. The quadratic boundary bounds are optimal in the worst case. A fixed three-state example separates polynomial-time recognition from hard exact counting.

Abstract: Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.

Abstract: By default, Apache Spark's tree aggregation primitives place the tree root on the driver, requiring the driver to participate in the same aggregation computation over intermediate aggregation state as executor nodes. For large aggregates, this can expose the single coordinator to substantial computation and memory requirements. Recent Spark versions optionally move the root to an executor, but the completed aggregate must still be returned to and materialized on the driver. We demonstrate this limitation using exact quantile computation and heavy-hitter identification, where the intermediate aggregation state can be substantially larger than the desired final result. We propose TreeRedux, a minimal extension that adds a terminal finalize operation, executed on an executor, that maps the aggregation state U to a compact result V, so that V rather than the potentially large U is materialized on the driver. For exact quantile computation, applying TreeRedux to GK Select removes the driver's epsilon-n memory term, reducing driver memory requirements to the same asymptotic order as Spark's GK Sketch. In our experiments, the default GK Select implementation encountered a driver out-of-memory error at 2.5 billion elements. Spark's executor-side final aggregation option extended this limit to approximately 16-18 billion elements but still required the final aggregation state to be materialized on the driver. Redux Select completed through 28 billion elements without a driver out-of-memory error. TreeRedux allowed Space-Saving sketches with up to 32x the capacity of the largest configuration that materializes a full sketch on the driver.