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

推荐订阅源

Y
Y Combinator Blog
The GitHub Blog
The GitHub Blog
Vercel News
Vercel News
D
DataBreaches.Net
MongoDB | Blog
MongoDB | Blog
H
Help Net Security
小众软件
小众软件
美团技术团队
T
The Blog of Author Tim Ferriss
爱范儿
爱范儿
D
Docker
Martin Fowler
Martin Fowler
大猫的无限游戏
大猫的无限游戏
博客园 - 聂微东
Blog — PlanetScale
Blog — PlanetScale
H
Hackread – Cybersecurity News, Data Breaches, AI and More
罗磊的独立博客
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
V
V2EX
S
SegmentFault 最新的问题
云风的 BLOG
云风的 BLOG
B
Blog
雷峰网
雷峰网
The Cloudflare Blog

cs.DB updates on arXiv.org

Block-Sphere Vector Quantization GroupAffect-4: A Multimodal Dataset of Four-Person Collaborative Interaction CogScale: Scalable Benchmark for Sequence Processing TextAlign: Preference Alignment for Text Rendering with Hierarchical Rewards LogRouter: Adaptive Two-Level LLM Routing for Log Question Answering in Big Data Systems Agentic Cost-Aware Query Planning with Knowledge Distillation for Big Data Analytics Covariance Structure and Coordinate Heterogeneity Govern Binary Quantization of Contrastive Embeddings IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer Automatic Unsupervised Ensemble Outlier Model Selection--Extended Version A Generative AI Framework for Intelligent Utility Billing CO 2 Analytics and Sustainable Resource Optimisation Towards Foundation Models for Relational Databases with Language Models and Graph Neural Networks Gaussian Relational Graph Transformer Croissant Baker: Metadata Generation for Discoverable, Governable, and Reusable ML Datasets Reducing Hallucination in Vision-Language Models via Stage-wise Preference Optimization under Distribution Shift A Horn extension of DL-Lite with NL data complexity 3D Primitives are a Spatial Language for VLMs Enabling AI-Native Mobility in 6G: A Real-World Dataset for Handover, Beam Management, and Timing Advance A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination EpiCastBench: Datasets and Benchmarks for Multivariate Epidemic Forecasting FERMI: Exploiting Relations for Membership Inference Against Tabular Diffusion Models Toward Multi-Database Query Reasoning for Text2Cypher Autonomous FAIR Digital Objects: From Passive Assertions to Active Knowledge HOME-KGQA: A Benchmark Dataset for Multimodal Knowledge Graph Question Answering on Household Daily Activities Detect, Localize, and Explain: Interactive Hierarchical Log Anomaly Analytics with LLM Augmentation Open Ontologies: Tool-Augmented Ontology Engineering with Stable Matching Alignment Machine Learning-Based Pre-Test Risk Stratification for PCR-Confirmed Chlamydia Using Patient-Reported Data and Urine Biomarkers Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations PrepBench: How Far Are We from Natural-Language-Driven Data Preparation? Anatomy of a Query: W5H Dimensions and FAR Patterns for Text-to-SQL Evaluation Building informative materials datasets beyond targeted objectives
A Simple Algorithm for Consistent Query Answering under P...
Diego Figueira, Anantha Padmanabha, Luc Segoufin, Cristina Siran · 2023-01-20 · via cs.DB updates on arXiv.org

We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set $Δ$ of subsets of facts of the database of size at most k, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: (1) Initialize $Δ$ with all sets $S$ of at most $k$ facts such that $S\models q$. (2) Add any set $S$ of at most k facts to $Δ$ if there exists a block $B$ (i.e., a maximal set of facts sharing the same key) such that for every fact $a \in B$ there is a set $S' \subseteq S \cup \{a\}$ such that $S'\in Δ$. For an input database $D$, the algorithm answers "q is certain" iff $Δ$ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for self-join-free queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an under-approximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with self-joins) which are not identified as such by the algorithm.