惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

腾讯CDC
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
P
Proofpoint News Feed
D
DataBreaches.Net
D
Docker
云风的 BLOG
云风的 BLOG
大猫的无限游戏
大猫的无限游戏
月光博客
月光博客
J
Java Code Geeks
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
罗磊的独立博客
Martin Fowler
Martin Fowler
U
Unit 42
Engineering at Meta
Engineering at Meta
IT之家
IT之家
Vercel News
Vercel News
B
Blog RSS Feed
人人都是产品经理
人人都是产品经理
博客园 - Franky
博客园 - 【当耐特】
Stack Overflow Blog
Stack Overflow Blog
G
Google Developers Blog
MongoDB | Blog
MongoDB | Blog

cs updates on arXiv.org

Beyond Binary Edits Robust Multimodal Knowledge Editing with Adversarial Subspace Alignment Agentic Proving for Program Verification MemAudit: Post-hoc Auditing of Poisoned Agent Memory via Causal Attribution and Structural Anomaly Detection OpenSkillEval: Automatically Auditing the Open Skill Ecosystem for LLM Agents One Policy, Infinite NPCs: Persona-Traceable Shared RL Policies for Scalable Game Agents How Human-Like Are Large Language Models? A Register-Aware Linguistic Evaluation Framework Benchmarking Google Embeddings 2 against Open-Source Models for Multilingual Dense Retrieval and RAG Systems Structure-Guided Entity Resolution: Fine-Tuning LLMs for Robust Name Matching in Complex Linguistic Contexts Solving the Aircraft Disassembly Scheduling Problem Co-ReAct: Rubrics as Step-Level Collaborators for ReAct Agents CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem Asking For An Old Friend: Diagnosing and Mitigating Temporal Failure Modes in LLM-based Statutory Question Answering EDGE-OPD: Internalizing Privileged Context with Evidence Guided On-Policy Distillation ARES: Automated Rubric Synthesis for Scalable LLM Reinforcement Learning SSDAU: Structured Semantic Data Augmentation for Joint Entity and Relation Extraction Naturalistic measure of social norms alignment Articulatory strategy as a source of variation in acoustic vowel dynamics When Planning Fails Despite Correct Execution: On Epistemic Calibration for LLM-Based Multi-Agent Systems EquiSumm : A Gender Bias-Aware Framework for Inclusive Tweet Summarization Metacognition as Reward: Reinforcing LLM Reasoning via Knowledge and Regulation Signals From Correctness to Preference: A Framework for Personalized Agentic Reinforcement Learning Cultural Adaptation in Large Language Models for Political Discourse Emotion Recognition in Sign Language Conversation ClimateChat-300K: A Multi-Modal Facebook Dataset for Understanding Diverse Perspectives in Climate Communication AraHopeCorpus: Annotation Guidelines and Dataset for Hope Speech in Arabic Social Media Crisis Discourse Human-in-the-Loop Multi-Agent Ventilator Decision Support with Contextual Bandit Preference Learning Convergence Without Understanding: When Language Models Agree on Representations but Disagree on Reasoning DART: Semantic Recoverability for Structured Tool Agents Ontological Knowledge Blocks: Executable Compliance and Profile-Based Validation for Trustworthy AI Systems Parallel Context Compaction for Long-Horizon LLM Agent Serving
The Role of Semirings in Incremental View Maintenance
Eden Chmielewski, Andrei Draghici, Dan Olteanu, Haozhe Zhang · 2026-06-06 · via cs updates on arXiv.org

We study the problem of incremental view maintenance (IVM) under inserts to $K$-databases, where $K$ is a commutative semiring without additive inverse. The key observation put forward in this paper is that the complexity of the IVM problem depends fundamentally on the underlying semiring. We introduce a class of conjunctive queries called $p$-hierarchical and show that for any $p$-hierarchical query with fractional hypertree width $\fhtw$ and any insert-only update sequence of length $N$ to an initially empty $K$-database over an arbitrary semiring $K$ without additive inverse, we can construct a data structure that can be updated in amortized $\bigO(N^{\fhtw-1})$ time and can support constant delay enumeration of the query result. In particular, the amortized update time for any $α$-acyclic $p$-hierarchical query is constant. We also give conditional lower bounds showing that any conjunctive query without self-joins that is not $p$-hierarchical cannot be maintained with amortized constant update time and constant enumeration delay under inserts to $K$-databases. Here, $K$ can be the natural semiring and its generalizations to the provenance and covariance semirings or any idempotent and strictly ordered semiring such as the tropical semiring. When put together, our upper and lower bounds imply a dichotomy for the insert-only maintenance of conjunctive queries without self-joins and the aforementioned semirings: A query can be maintained with amortized constant update time and constant enumeration delay if and only if it is $α$-acyclic $p$-hierarchical.