Codd表约束蕴含问题与Armstrong表的深入解析

### Codd表约束蕴含问题与Armstrong表的深入解析 #### 1. 约束蕴含问题概述 在处理Codd表时，我们常常会遇到唯一约束（UCs）和函数依赖（FDs）在非空集（NFS）存在情况下的蕴含问题。为了深入理解这个问题，我们将从公理刻画、算法刻画和逻辑刻画三个方面进行分析。 #### 2. 公理刻画 - **基本概念**：设$\Sigma$是一组UCs和FDs，$\Sigma_{Ts}^* = \{ \phi | \Sigma \models_{Ts} \phi \}$是$\Sigma$的语义闭包。我们可以通过语法方法来确定语义闭包，例如应用表1中的推理规则。推理规则的形式为“前提 -> 结论（条件）”，没有前提的推理规则称为公理。 - **定理1**：集合$S$是在NFS存在情况下UCs和FDs蕴含的有限公理化。 |规则名称|规则内容| | ---- | ---- | |demotion|unique(X) -> X → Y| |reflexivity|XY → X| |decomposition|X → YZ -> X → Y| |null pullback|X → Y, unique(Y) -> unique(X) (Y ⊆ XTs)| |null transitivity|X → Y, Y → Z -> X → Z (Y ⊆ XTs)| |union|X → Y, X → Z -> X → YZ| - **示例3**：考虑模式Contact，其表头为Address、City和ZIP，NFS Contacts = {ZIP}，$\Sigma = \{ unique(Address, City), ZIP → City \}$。通过应用null pullback规则到unique(Address,City)和FD Address,City,ZIP → Address,City，可以从$\Sigma$推断出unique(Address, City, ZIP)。后者可以通过单次应用自反性公理推断得出。 #### 3. 算法刻画 - **问题提出**：数据工程师通常不需要集合$\Sigma$的完整语义闭包$\Sigma_{Ts}^*$，而是需要判断给定的UC或FD $\phi$是否在NFS Ts存在的情况下由$\Sigma$蕴含。枚举$\Sigma_{S}^+$的元素直到找到$\phi$或枚举完所有元素而未找到$\phi$通常是低效的。 - **算法思路**：对于表模式$T$的表头集合$X$，定义$X_{\Sigma,Ts}^* := \{ H | \Sigma \models_{Ts} X → H \}$为$X$相对于$\Sigma$和$Ts$的表头集合闭包。对于一组UCs和FDs $\Sigma \cup \{ \phi \}$，只需计算相对于$\Sigma_{FD} := \{ X → T | unique(X) \in \Sigma \} \cup \{ X → Y | X → Y \in \Sigma \}$和$Ts$的表头集合闭包。 ```plaintext Algorithm 2 (NFSClosure(X,ΣFD,Ts,T)) Input: header set X, FD set ΣFD, NFS Ts over table schema T Output: header set closure X∗ ΣFD,Ts of X with respect to ΣFD and Ts Method: (A0) CLOSURE := X; (A1) repeat OLDCLOSURE := CLOSURE; for all V → W ∈ ΣFD do if V ⊆ CLOSURE ∩ XTs then CLOSURE := CLOSURE ∪ W; endif; enddo; until OLDCLOSURE = CLOSURE; (A2) return CLOSURE; ``` - **定理3**：判断一个UC或FD $\phi$是否在NFS Ts存在的情况下由一组UCs和FDs $\Sigma$蕴含的问题可以在$O(||\Sigma \cup \{ \phi \}||)$时间内解决。 - **示例4**：考虑SQL表定义Contact，表头为Address、City和ZIP，NFS Contacts = {Address, ZIP}，$\Sigma = \{ unique(Address, City), ZIP → City \}$。则$\Sigma_{FD} = \{ \{Address, City\} → ZIP, ZIP → City \}$，{Address, ZIP}相对于$\Sigma_{FD}$和Contacts的列头闭包是{Address, City, ZIP}。由于$\Sigma$中不存在unique(Z)使得$Z \subseteq \{Address, ZIP\}$，根据引理1，UC unique(Address, ZIP)在Contacts存在的情况下不由$\Sigma$蕴含。 #### 4. 逻辑刻画 - **S - 3逻辑**：Schaerf和Cadoli引入了S - 3逻辑，它是一个语义上有良好基础的逻辑框架，用于合理近似推理。对于有限的命题变量集合$L$，$L_{\ell}$表示$L$上的所有文字集合。$S \subseteq L$，$L$的S - 3解释是一个全函数$\hat{\omega} : L_{\ell} → \{ F, T \}$，满足特定条件。 - **映射定义**：设$\phi : T → L$是$T$和对应于$T$的命题变量集合$L = \{ H' | H \in T \}$之间的双射。对于NFS $Ts$，$S = \phi(Ts)$。将$\phi$扩展为从$T$上的UCs和FDs集合到命题公式集合的映射$\Phi$。 - **定理4**：设$\Sigma \cup \{ \phi \}$是SQL表定义$T$上的一组UCs和FDs，$Ts$是NFS。则$\Si