概念数据库的新型范式研究

### 概念数据库的新型范式研究 #### 1. 引言 自1970年关系数据库系统被提出以来，因其简单性和坚实的理论基础，已成为行业标准。关系数据库使用中，数据的正确结构和设计至关重要。为确保数据库无处理困难，提出了多种范式作为关系模式应满足的条件。其中，函数依赖是最重要的一类完整性约束，会导致数据冗余和更新异常等问题。为克服这些困难，提出了Boyce - Codd范式（BCNF），且已证明BCNF能避免冗余和更新异常。 近年来，出现了许多新的数据模型，概念数据模型是其中重要的一类，其典型代表是实体 - 关系模型。而高阶实体 - 关系模型（HERM）是该模型的一个有趣扩展，它不仅是概念设计的直观工具，还可作为构建数据库管理系统的数学模型。在HERM中，函数依赖同样会导致数据冗余，因此需研究适用于HERM的范式。 #### 2. 预备知识 HERM的一个关键特性是属性的嵌套。其起始于一组基本类型（如STRING、INTEGER等）、一组域以及一个域分配函数。通过类型构造器（如记录、有限集等）可获得新的类型。 嵌套属性集MA是满足特定条件的最小集合，包含扁平属性名、空属性等。类型分配函数从扁平属性名扩展到嵌套属性，进而诱导出嵌套属性的域分配。 HERM模式是一组有限且非空的数据库类型，实例为每个数据库类型分配一个有限集。例如，为跟踪相扑比赛，定义了HERM模式OZUMO，包含RIKISHI、BASHO和BOUT三个数据库类型，并给出了相应的实例。 嵌套属性存在子属性的概念，子属性集Sub(X)具有Brouwerian代数结构。例如，对于数据库类型BASHO对应的嵌套属性，其结构可通过图展示。一些特殊的子属性（如BASHo(Participating{A})等）对概念建模有重要影响，且与其他嵌套属性处理方式不同。 #### 3. HERM中的函数依赖 在HERM中，函数依赖定义为嵌套属性上的表达式X -> y，其中X、y是子属性的非空集合。一个有限集满足该函数依赖的条件是，对于任意两个元组，当X中所有子属性的值相等时，y中所有子属性的值也相等。 例如，对于HERM模式OZUMO中的数据库类型BOUT，定义了一组函数依赖，包括表示键的依赖、确定静态信息的依赖等。 对于函数依赖的蕴含和可推导性，可类比关系数据模型中的定义。目标是找到一组推理规则，使其既健全又完备。一般情况下，子属性X和Y的值不能确定X U Y的值，但当X和Y半不相交时，可确定。 已证明广义Armstrong公理对于HERM中函数依赖的蕴含是健全且完备的。 #### 4. HERM中的冗余和范式 ##### 4.1 准备工作 定义了嵌套属性的子属性基SubB(N)，它是满足特定条件的最小集合，其中的元素称为基属性，分为最大基属性和非最大基属性。例如，对于嵌套属性N = A(B,C{D(E,F{G})})，可确定其基属性。 在HERM中，定义了超键和最小键的概念。超键是满足函数依赖X -> N的子属性集合，