对象范式、第四范式及其在数据库安全中的应用

# 对象范式、第四范式及其在数据库安全中的应用 ## 1. 相关工作概述 逻辑数据库模式设计一直是研究的重点。常见的范式，如第三范式、Boyce - Codd范式（BCNF）和第四范式（4NF），它们的成果和局限性都有过相关研究。Biskup提出了针对函数依赖的对象范式，并将其推广到包含和排除依赖。本文的第一个贡献是将对象范式扩展到多值依赖（MVD），这很重要，因为MVD为关系无损分解为两个投影提供了充分必要条件，是数据库规范化的重要基础。在实际应用中，许多处于BCNF的数据库模式实际上违反了4NF。 信息安全中，保证数据保密性是基础课题。推理控制能保证保密性但实现成本高，访问控制易实现但在推理攻击下无法保证保密性。许多计算机安全教材解释了访问控制的主要概念，也有相关研究探讨数据库中的推理问题、提出形式化安全模型以及研究如何声明结构化对象的分类以防止不必要的推理。本文的第二个贡献是将相关结果扩展到多值依赖的对象范式以及更具表达力的约束类。 此外，模式设计对每个数据模型都至关重要，在关系数据库中的模式设计工作会影响其扩展模型的模式设计。不同数据模型，如概念模型、SQL数据模型、嵌套数据模型等，都对模式设计进行了深入研究。从数据质量角度看，规范化可减少数据冗余，提高数据质量和数据驱动决策的有效性，近期也有工作将经典数据库规范化扩展到数据质量设计。 ## 2. 预备知识 在现实世界中，对象具有两个属性：在其领域内唯一，能独立于当前环境出现和存在。在关系数据库中，我们将对不同类型的数据依赖（包括函数依赖和多值依赖）对这些属性进行形式化。 ### 2.1 基本定义 - **关系模式**：关系模式R是一组有限的属性，代表表的列名。每个属性A∈R都关联一个域dom(A)，包含该列可能出现的值。 - **元组和关系**：R上的元组t为每个属性A∈R分配一个值t(A)∈dom(A)。R上的关系r是R上元组的有限集合。 - **投影**：对于属性子集X⊆R，t(X)表示元组t在属性集X上的投影。 - **数据依赖**：关系模式R通常带有一组数据依赖Σ，常见的有函数依赖（FD）和多值依赖（MVD）。FD表示为X → Y（X, Y ⊆ R），当关系r中所有在X属性上值匹配的元组对在Y属性上的值也匹配时，r满足该FD。MVD表示为X ↠ Y（X, Y ⊆ R），当关系r中所有在X属性上值匹配的元组对，存在一个元组在XY属性上与第一个元组值匹配，在R - XY属性上与第二个元组值匹配时，r满足该MVD。 - **依赖闭包**：对于给定类别的数据依赖集Σ，Σ+表示由Σ隐含的该类别依赖集，即满足Σ中所有依赖的每个关系也满足Σ+中的所有依赖。例如，每个FD X → Y 隐含MVD X ↠ Y，但反之不成立。 - **平凡依赖**：每个关系都满足的依赖为平凡依赖。如FD X → Y 为平凡依赖当且仅当Y ⊆ X，MVD X ↠ Y 为平凡依赖当且仅当Y ⊆ X 或XY = R。 ### 2.2 范式定义 - **Boyce - Codd范式（BCNF）**：(R, Σ) 处于BCNF当且仅当对于每个非平凡FD X → Y ∈Σ+，有X → R ∈Σ+，即非平凡FD的左部X是键，满足键X的关系中不会有在X属性上值匹配的不同元组。 - **第四范式（4NF）**：(R, Σ) 处于4NF当且仅当对于每个非平凡MVD X ↠ Y ∈Σ+，有X → R ∈Σ+。 例如，关系满足集合Σ = {P ↠ M, DM → P}，(MEET, Σ) 处于BCNF但不处于4NF，因为给定关系违反了FD P → D，即P不是键，对于MVD P ↠ M ∈Σ+，有P → R ∉Σ+。 ## 3. 弱对象 接下来两部分将回顾弱对象和弱对象范式（弱ONF）的概念，并证明模式处于弱ONF当且仅当处于4NF。 ### 3.1 弱对象定义 设 (R, Σ) 是关系模式R及其上的数据依赖集Σ，R的属性子集X是弱对象当且仅当满足以下条件： - **唯一性**：对于所有满足Σ的R上的关系r，对于所有t ∈ r，t(X) 是唯一的，即不存在t′ ∈ r - {t} 使得t(X) = t′(X)。 - **弱独立性**：对于所有满足Σ的R上的关系r，对于所有μ ∈ dom(X) 且μ ∉ r(X)，存在ν ∈ dom(R - X) 使得r ∪ {μν} 满足Σ。 在示例中，属性集DM是弱对象，而P不是。 ### 3.2 相关性质 - **性质1**：设X是 (R, Σ) 上的键，如果X满足弱独立性，则对于所有Y ⊂ X，有Y → R ∉Σ+。 - **证明**：设t是R上的元组，关系r = {t} 满足Σ。定义元组t′ 使得t′(Y) = t(Y) 且t′(X - Y) ≠ t(X - Y)，则μ := t′(X) ∉ r(X)。由于弱独立性，存在ν ∈ dom(R - X) 使得r′ = r ∪ {μν} 满足Σ，但r′ 不满足Y → R。 - **性质2**：设X是 (R, Σ) 上的键，如果X是最小键且 (R, Σ) 处于第四范式，则X满足弱独立性。 - **证明**：设r是满足Σ的R上的关系，μ ∈ dom(X) 且μ ∉ r(X)。由于有无限个常量，可找到元组ν ∈ dom(R - X) 使得ν(A) ∉ r(A) 对于所有A ∈ R - X。假设r ∪ {μν} 违反了Y ↠ Z ∈Σ+（Z ⊈ Y 且Z ⊈ R - Y），则t′(Y) = t(Y) 对于某个t ∈ r，且由ν的构造可知Y ⊂ X。由于X