信息源查询的表技术

### 信息源查询的表技术 #### 1. 源集合的一致性 源集合可能存在不一致的情况。例如，源集合S包含两个源：⟨{V1(x) ←R(x, y), {open}, {V1(a)}⟩和⟨V2(u) ←R(u, w), {closed}, {V2(b)}⟩，此时poss(S)为空。这是因为V1的扩展要求每个可能的数据库的第一列都有一个a，而V2的扩展要求每个可能的数据库的第一列只有b。这样的源集合被称为不一致的。如果poss(S)非空，则源集合被称为一致的。源集合的一致性可以通过数据库模板和chase过程从语法上进行刻画。 - 若源集合S中没有封闭源，则S是一致的。 - 若源集合S中没有开放源，则S是一致的。 #### 2. 查询源集合 ##### 2.1 查询评估 设S为源集合，Q为合取查询，Q应用于S定义了以下可能答案集合： - \(Q(S) = \{Q(D) : D \in poss(S)\}\) - \(Q^*(S) = \bigcap_{D \in poss(S)} Q(D)\) - \(\overline{Q}(S) = \bigcup_{D \in poss(S)} Q(D)\) 为了计算源集合上查询的答案，我们首先要构建一个基于全局关系名的数据库模板T(S)，它代表了S的可能数据库集合。具体操作步骤如下： 1. 定义函数(T, C)，对于源\(S_i = ⟨\phi_i, labels, v_i⟩\)： - 若open∈labels，\(T(S_i) = \{t : t \text{ 在 } body(\phi_i)\theta \text{ 中且 } head(\phi_i)\theta = u, \text{ 对于某些 } u \in v_i \text{ 和赋值 } \theta\}\)；否则\(T(S_i) = \varnothing\)。 - 若closed∈labels，\(C(S_i) = (U, \Theta)\)，其中U由\(\phi_i\)体中的所有原子组成，\(\Theta = \{\theta : head(\phi_i)\theta = u, \text{ 对于某些 } u \in v_i\}\)；否则\(C(S_i) = \varnothing\)。 2. 最终，\(T(S) = (\bigcup_{S_i \in S} T(S_i), \bigcup_{S_i \in S} C(S_i))\)。 例如，考虑\(S = \{S_1, S_2, S_3\}\)，其中： - \(S_1 = ⟨V1(u, w) ←S(u, w), {open}, \{V1(b, c), V1(b', c)\}⟩\) - \(S_2 = ⟨V2(v) ←R(v, x), {open}, \{V2(a)\}⟩\) - \(S_3 = ⟨V3(z) ←R(a, z), {closed}, \{V3(b), V3(b')\}⟩\) 则\(T(S) = ⟨T_1, C⟩\)，其中\(T_1 = \{R(a, x), S(b, c), S(b', c)\}\)，\(C = \{(R(a, z), \{\{z/b\}, \{z/b'\}\})\}\)。 数据库模板T(S)具有性质：\(rep(T(S)) = poss(S)\)。 对于数据库模板\(T = ⟨T_1, ..., T_n, C⟩\)和查询\(Q = ans(x) ←R_1(x_1), ..., R_n(x_m)\)，查询评估步骤如下： 1. 令\(\{T'_1, ..., T'_s\} = \bigcup_{i \in [1,n]} C(T_i)\)。 2. 定义\(\hat{Q}(T) = ⟨T''_1, ..., T''_q, \varnothing⟩\)，其中每个\(T''_j\)（\(j \in [1, q]\)）等于某个\(\hat{Q}_\kappa(T'_i)\)，对于某些\(i \in [1, s]\)和替换\(\kappa\)。 3. \(\hat{Q}_\kappa(T'_i) = \{ans(x)\sigma : \sigma \text{ 是 }\{R_i(x_i)\}_{i = 1}^m \text{ 和 } T'_i \text{ 子集的最一般合一}，且 \sigma \text{ 与 } \kappa \text{ 兼容}\}\)。 查询评估会将约束追入表中，结果模板的约束为空，虽然会丢失一些信息，但查询结果与期望结果是共初始等价的，即\(rep(\hat{Q}(T))