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