数据库的可定义性与描述复杂度

### 数据库的可定义性与描述复杂度 #### 1. 树分解相关概念 在数据库研究中，树分解是一个重要的概念。我们可以将图视为基于 $\{V, E\}$ 的数据库，其中 $V$ 是一元关系，$E$ 是二元关系。树是一种连通且无环的图。 - **树分解的定义**：数据库 $D$ 的树分解是一个对 $(T, (B_t)_{t\in T})$，其中 $T$ 是树，$(B_t)_{t\in T}$ 是 $A_D$ 的子集族，满足 $\bigcup_{t\in T} \langle B_t \rangle_D = D$，并且对于每个 $a\in D$，$T$ 的子图 $\langle \{t | a\in B_t\} \rangle_T$ 是连通的。$B_t$ 被称为分解的块。 - **树分解的宽度**：$(T, (B_t)_{t\in T})$ 的宽度是 $\max\{|B_t| | t\in T\} - 1$。数据库 $D$ 的树宽度记为 $tw(D)$，是 $D$ 的树分解的最小宽度。 下面是树分解相关概念的总结表格： | 概念 | 定义 | | ---- | ---- | | 树分解 | $(T, (B_t)_{t\in T})$，满足特定条件的对 | | 块 | $B_t$，树分解中的子集 | | 树分解宽度 | $\max\{|B_t| | t\in T\} - 1$ | | 树宽度 | $tw(D)$，树分解的最小宽度 | #### 2. k - 预团相关引理 - **k - 预团的定义**：设 $k\geq1$ 且 $D$ 是数据库，$D$ 的 $k$ - 预团是一个由不同元素组成的 $(k + 1)$ - 元组 $\overline{a}\in D$，使得 $D$ 有一个宽度至多为 $k$ 的树分解 $(T, (B_t)_{t\in T})$，且存在 $t\in T$ 使得 $B_t = \{a_1, \ldots, a_{k + 1}\}$。 - **引理 2**：设 $k\geq1$ 且 $D$ 是树宽度至多为 $k$ 且大小至少为 $(k + 1)$ 的数据库。 - $D$ 有一个树分解 $(T, (B_t))$，对于所有 $t\in T$ 有 $|B_t| = k + 1$，并且对于所有不同的 $t, u\in T$ 有 $B_t \neq B_u$，这样的树分解称为正则树分解。 - 对于 $D$ 的每个 $k$ - 预团 $\overline{a}$，存在 $D$ 的一个正则树分解 $(T, (B_t)_{t\in T})$，使得存在 $t\in T$ 满足 $B_t = \{a_1, \ldots, a_{k + 1}\}$。 其证明过程如下： 为证明 (1)，设 $(T, (B_t)_{t\in T})$ 是 $D$ 的宽度为 $k$ 的树分解，且在所有宽度为 $k$ 的树分解中： - $|T|$ 最小。 - 在满足 (i) 的条件下，$\sum_{t\in T} |B_t|$ 最大。 显然 (i) 意味着不存在相邻的 $t, u\in T$ 使得 $B_t \subseteq B_u$，否则可以收缩 $T$ 中的边 $tu$ 得到更小的树。假设存在 $t\in T$ 使得 $|B_t| < k + 1$，设 $u$ 是 $t$ 的邻居且 $a\in B_u \setminus B_t$，可以将 $a$ 添加到 $B_t$ 得到一个新的树分解，使得 (ii) 中的和更大，这与 $(T, (B_t))$ 的选择矛盾。(2) 可以类似证明。 #### 3. 相关图论概念的转移 对于每个基于 $\tau$ 的数据库 $D$，我们关联其 Gaifman 图 $G(D)$，其顶点集 $V_{G(D)} = A_D$，如果在 $D$ 的某个关系中有一个元组 $\overline{c}$ 使得 $a$ 和 $b$ 都出现在 $\overline{c}$ 中，则顶点 $a$ 和 $b$ 之间有一条边。这样我们就可以将图论概念如连通分量或距离转移到任意数据库，只需参考 Gaifman 图中的相应概念。 - **连通分量**：用 $comp(D)$ 表示数据库 $D$ 的连通分量的活跃域集合，$D$ 的连通分量是子实例 $\langle C \rangle$，其中 $C\in comp(D)$。 - **相关集合定义**：设 $l\geq1$，$D$ 是数据库，$\overline{a}\in D$ 是 $l$ - 元组的顶点。对于 $b\in D$，$C_{-\overline{a}}^b$ 表示 $comp(D \setminus \overline{a})$ 中包含 $b$ 的唯一集合；如果 $b\in \{a_1, \ldots, a_l\}$，则 $C_{-\overline{a}}^b$ 为空集。并且 $C_{+\overline{a}}^b = C_{-\overline{a}}^b \cup \{a_1, \ldots, a_l\}$。 - **元组操作**：对于 $l$ - 元组 $\overline{a}$，$i\leq l$ 和任意 $c$，$\overline{a}/i$ 表示从 $\overline{a}$ 中删除第 $i$ 个分量得到的 $(l - 1)$ - 元组，$\overline{a}(c/i)$ 表示将 $\overline{a}$ 的第 $i$ 个分量替换为 $c$ 得到的 $l$ - 元组。 下面是相关图论概念转移的流程图： ```mermaid graph LR A[数据库 D] --> B[关联 Gaifman 图 G(D)] B --> C[转移图论概念到 D] C --> D[定义连通分量等概念] ``` #### 4. k - 预团的判定引理 - **引理 3**：设 $k\geq1$，$D$ 是数据库，$\overline{a}\in D$ 是由不同元素组成的 $(k + 1)$ - 元组。 - $\overline{a}$ 是 $D$ 的 $k$ - 预团当且仅当对于所有 $b\in D$，$\overline{a}$ 是 $\langle C_{+\overline{a}}^b \rangle$ 的 $k$ - 预团。 - 对于所有 $b\in D \setminus \overline{a}$，$\overline{a}$ 是 $\langle C_{+\overline{a}}^b \rangle$ 的 $k$ - 预团当且仅当存在 $i\leq k + 1$ 和 $c\in C_{-\overline{a}}^b$ 使得 $\overline{a}/i$ 在 $\langle C_{+\overline{a}}^b \rangle$ 中隔离 $a_i$（即 $a_i$ 在 $D$ 的 Gaifman 图中不与 $C_{-\overline{a}}^b$ 中的任何 $d$ 相邻），并且 $\overline{a}(c/i)$ 是 $\langle C_{+\overline{a}/i}^b \rangle$（即 $\langle C_{+\overline{a}}^b \rangle \setminus a_i$）的 $k$ - 预团。 - 对于所有 $b\in \{a_1, \ldots, a_{k + 1}\}$，$\overline{a}$ 是 $\langle C_{+\overline{a}}^b \rangle$ 的 $k$ - 预团。 证明过程： 首