数据库查询与问答系统技术解析

### 数据库查询与问答系统技术解析 #### 1. 数据库查询相关概念与计算 在数据库查询领域，有一些重要的概念和计算方法。首先是关于查询的计数与分数的讨论。对于一个固定的自连接自由合取查询（SJFCQ）$q$，$\sigma_{CERTAINTY}(q)$ 问题的输入是多基 $(db, μ)$，目标是确定 $\sigma_{rset}(db, μ, q)$。 这里有几个关键的计算公式： - $\sigma_{rset}(db, μ, q) = \sum_{\{σ(r, db, μ) | r \in rset(db, q)\}}$ - $\sigma_{frac}(db, μ, q) = \frac{\sigma_{rset}(db, μ, q)}{\sigma_{rset}(db, μ)}$ 并且，对于多基 $(db, μ)$，$\sigma_{rset}(db, μ)$ 可以通过以下方式计算： 设 $r$ 是 $db$ 的一个修复，$\sigma_{rset}(db, μ) = \prod_{g \in r} \sigma_{block}(g, db, μ)$（空积定义为 1）。可以在时间 $O(n \log n)$ 内确定 $\sigma_{rset}(db, μ)$，其中 $n$ 是 $db$ 的基数。具体操作步骤如下： 1. 对 $db$ 的每个关系按主键值排序。 2. 对于每个块，确定该块的支持计数。 3. 将这些数字相乘。 由于 $\sigma_{rset}(db, μ, q) = \sigma_{frac}(db, μ, q) \times \sigma_{rset}(db, μ)$，如果能在时间 $O(f(n))$ 内确定 $\sigma_{frac}(db, μ, q)$，那么就能在时间 $O(f(n) + n \log n)$ 内确定 $\sigma_{rset}(db, μ, q)$。所以，当对于每个多基 $(db, μ)$ 都能在多项式时间内确定 $\sigma_{frac}(db, μ, q)$ 时，$\sigma_{CERTAINTY}(q)$ 问题属于 P 类。因此，我们可以专注于确定分数 $\sigma_{frac}(db, μ, q)$ 而非计数 $\sigma_{rset}(db, μ, q)$。 #### 2. 相关工作对比 与其他工作相比，当前的研究有其独特之处。它对以往的工作进行了推广，允许存在多重性。而之前的数据模型没有多重性，相当于对每个数据库事实 $g$ 都设置 $\mu(g) = 1$。 块独立不相交概率数据库使用概率而非多重性。如果要求每个块内的概率之和为 1，那么多重性和概率的差异就无关紧要。但这些数据库的作者并不要求块内概率之和为 1，这可能导致非空数据库有一个空修复，这与当前的数据模型不同，在当前模型中，除非原始数据库为空，否则修复不会为空。例如，Dalvi 等人对于查询 $q = \{R(x, y), S(y)\}$ 得到了难处理性结果，而在当前设置中 $\sigma_{CERTAINTY}(q)$ 是可处理的。 此外，当前工作也可以看作是一致查询回答的一种变体。以往关于主键违规的工作关注查询是否在每个修复中都为真，而当前文章则是要确定查询为真的修复的加权数量。Greco 等人研究了计算满足查询的修复的分数，他们的约束是函数依赖，并且通过更新获得修复，还提出了一种在多项式时间内计算近似概率答案的方法，而当前工作则是对能在多项式时间内获得精确分数的查询进行特征描述。 #### 3. 可处理性边界 为了确定查询的可处理性，定义了一类语法受限的 SJFCQ 查询，称为安全查询。通过一系列引理和算法来判断查询是否安全。 引理 2（SE0a）表明，对于查询 $q = \{g\}$（$g$ 是一个事实），有： $\sigma_{frac}(db, μ, q) = \begin{cases} 0, & \text{如果 } g \notin db \\ \frac{\mu(g)}{\sigma_{block}(g, db, μ)}, & \text{如果 } g \in db \end{cases}$ 引理 3（SE0b）指出，如果查询 $q$ 的复杂部分 $[[q]] = \emptyset$，那么： $\sigma_{frac}(db, μ, q) = \begin{cases} 0, & \text{如果 } db \not\models q \\ 1, & \text{如果 } db \models q \end{cases}$ 引理 4（SE1）说明，若 $q = q_1 \cup q_2$，$q_1 \cap q_2 = \emptyset$，且 $Vars(q_1) \cap Vars(q_