paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Infinite Probabilistic Databases

无限概率数据库
LMCS vol.Volume 18, Issue 12022匹配度 2/10 · 论文研究无限概率数据库的形式语义与查询可测性,属于概率数据库、逻辑与形式语义方向;虽涉及 Datalog 和形式化,但与用户关注的静态分析、Agentic/LLM、浮点程序分析及贝叶斯程序分析均无直接交叉,且无工程落地或 LLM 相关贡献。引用 5 inbox
Martin Grohe, Peter Lindner
crossref: 2026-09-10

AI 速览

一句话:提出用有限点过程为无限概率数据库建模,并证明关系代数、聚合与 Datalog 查询在不可数概率空间中的可测性。

概率数据库通常定义为关系数据库实例上的有限概率空间,但这种有限性限制了对查询直觉行为以及连续概率分布场景的建模。作者此前在 PODS 2019 提出无限概率数据库,主要处理可数无限空间;本文进一步突破可数限制,处理一般概率空间。为系统构造合适的(不可数)数据库实例概率空间,论文论证有限点过程是合适的概率论模型。核心结果是为关系代数查询、聚合查询以及 Datalog 查询建立可测性,从而确保查询在这些无限概率数据库上具有明确定义的语义。

问题
经典概率数据库框架将不确定性建模为关系实例上的有限概率空间,难以支持查询的直觉行为与连续分布应用;将空间扩展到不可数无限时,查询事件的可测性和语义良定义成为基础难题。
方法
论文采用有限点过程作为概率论基础,系统构造数据库实例上的(不可数)概率空间,并在该框架下分析关系代数、聚合和 Datalog 查询的可测性。
评估
评估以理论证明为主:证明关系代数查询、聚合查询和 Datalog 查询在构造的无限概率数据库语义下是可测的,从而保证查询语义良定义。
原文摘要(Abstract)

Probabilistic databases (PDBs) model uncertainty in data in a quantitative way. In the established formal framework, probabilistic (relational) databases are finite probability spaces over relational database instances. This finiteness can clash with intuitive query behavior (Ceylan et al., KR 2016), and with application scenarios that are better modeled by continuous probability distributions (Dalvi et al., CACM 2009). We formally introduced infinite PDBs in (Grohe and Lindner, PODS 2019) with a primary focus on countably infinite spaces. However, an extension beyond countable probability spaces raises nontrivial foundational issues concerned with the measurability of events and queries and ultimately with the question whether queries have a well-defined semantics. We argue that finite point processes are an appropriate model from probability theory for dealing with general probabilistic databases. This allows us to construct suitable (uncountable) probability spaces of database instances in a systematic way. Our main technical results are measurability statements for relational algebra queries as well as aggregate queries and Datalog queries.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1720,
  title = {Infinite Probabilistic Databases},
  author = {Martin Grohe and Peter Lindner},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 1},
  year = {2022},
  doi = {10.46298/lmcs-18(1:34)2022}
}