面向对象数据库系统：原理、实现与优化

# 面向对象数据库系统：原理、实现与优化 ## 1. 面向对象数据库基础 ### 1.1 对象变量 对象变量整合了数据库系统的面向集合访问和编程语言的单例访问。在声明时，若存在 `multiple` 选项，则该对象变量为集合变量。例如： ```plaintext PATIENT ps multiple, p; ``` 这里，`ps` 被声明为 `PATIENT` 类型的集合变量，`p` 为实例变量。通常，集合变量会被设置为语句右侧面向集合查询的结果集。用户可以使用系统定义的过程属性逐个访问对象，示例代码如下： ```plaintext ps = PATIENT where PATIENT.Disease == "cancer"; ps.openscan(); while (p = ps.next()) // 处理对象 p ps.closescan(); ``` 过程属性 `next` 每次调用时会返回一个对象，并将其赋值给实例变量 `p` 以供进一步使用。 ### 1.2 过程属性与查询 过程属性可以包含面向集合的查询。例如，`DEPARTMENT` 类的以下属性定义了在某个部门工作的实习生： ```plaintext Procedural DOCTOR intern() multiple { self.Doctor where self.Doctor.Status == "internship" }. ``` 可以在查询中使用该属性来检索儿科部门的实习生： ```plaintext DEPARTMENT.intern() where DEPARTMENT.Name == "pediatrics". ``` 系统不提供嵌套查询的特殊语法，而是通过查询定义的过程属性来模拟嵌套查询。关联查询可以通过将对象表达式作为参数传递给过程属性，或者通过系统定义的变量 `self` 隐式地进行表述。 ## 2. 系统实现架构 ### 2.1 分层架构选择 考虑到关系数据库已经积累了大量的实现技术，采用了由对象管理和数据管理组成的分层架构，并使用关系技术进行数据管理。然而，传统关系技术在有效支持面向对象概念（如对象标识符、复杂对象、类层次结构和方法）方面存在局限性。因此，对关系技术进行了扩展，以克服这些限制。 ### 2.2 扩展关系技术的应用 - **嵌套关系**：除了扁平关系，引入嵌套关系来高效存储和访问聚类复杂对象。 - **索引支持**：支持哈希和 B 树索引，以便通过对象标识符高效访问对象。 - **连接操作**：除了嵌套循环连接和排序合并连接，还提供哈希连接，以高效处理查询中的非聚类复杂对象。 - **查询优化**：扩展查询优化功能，以处理包含类层次结构和方法调用的面向对象查询。需要注意的是，这种优化由对象管理子系统而非数据管理子系统完成。 - **用户定义函数**：提供用户定义的操作和谓词函数，这些函数可以直接在页面缓冲区上进行评估。方法会被编译到这些函数中并得到高效处理。 - **缓冲机制**：除了页面缓冲，还设计了对象缓冲，并将这两种方案集成起来进行查询评估。 ## 3. 数据管理子系统 ### 3.1 数据结构 #### 3.1.1 支持的关系类型 数据管理子系统支持四种类型的关系，具体如下表所示： | 关系类型 | 描述 | | ---- | ---- | | 顺序关系 | 页面按顺序链接，元组按插入顺序存储，可在其上创建索引 | | B 树关系 | 具有 B 树结构，元组按用户定义的顺序函数存储在叶页面中，可用于创建非聚类或聚类索引 | | 哈希关系 | 使用线性哈希带部分扩展的动态哈希方案，由用户提供哈希函数 | | 内部关系 | 用于实现嵌套关系，存储在元组的可变长度字段中，可递归定义 | #### 3.1.2 元组结构 元组结构独立于关系类型，前两个字节包含元组长度，由固定部分和可变部分组成。固定长度字段存储在固定部分，可变长度字段存储在可变部分，可变长度字段的偏移量存储在固定部分。这种结构允许在不影响固定长度数据的情况下修改可变长度数据，但不支持空值压缩。 #### 3.1.3 TID 和字段访问 TID（元组标识符）可以存储在固定长度字段中，作为元组的指针，可用于实现各种数据结构。为了高效访问字段，提供了指针数组，每个指针指向页面缓冲区上元组中的相应字段。指针数组被传递给用户定义的函数（如操作和谓词函数）进行字段访问。 ### 3.2 哈希处理 #### 3.2.1 哈希连接方法 集合操作（如集合差和去重）需要基于 OID 的访问。面向对象查询通常基于 OID 进行等值连接。如果两个连接关系中的任何一个可以加载到主内存中，则可以使用哈希连接方法。即使两个关系都无法完全加载到主内存中，哈希连接方法通常也比基于排序的方法需要更少的 CPU 时间和 I/O 次数。 #### 3.2.2 内部哈希连接算法 ```mermaid graph TD; A[确定要分区的输入关系 A] --> B[确定分区数 p 和哈希函数 h]; B --> C[将关系 A 划分为 p 个子关系 Ai]; C --> D[扫描另一个关系 B 的每个元组 b]; D --> E[计算 b 的哈希值 k]; E --> F[比较 Ak 中的每个元组与 b]; F --> G[匹配时创建新元组并输出到结果关系 C]; ``` 具体步骤如下： 1. 确定要分区的输入关系，设为 A。 2. 确定分区数 `p` 和哈希函数 `h`。 3. 将关系 A 划分为 `p` 个子关系 `Ai = {a 属于 A | h(key of a) = i}`（`i = 0, ..., p - 1`）。 4. 对于另一个关系 B 的每个元组 `b`，计算 `k = h(key of b)`，并在连接键上比较 `Ak` 中的每个元组与 `b`。匹配时，从它们创建一个新元组并输出到结果关系 C。 #### 3.2.3 外部哈希连接算法 当两个输入关系都无法加载到主内存中时，使用外部哈希连接。其与内部哈希连接的主要区别在于使用递归和对两个输入关系进行分区。具体步骤如下： 1. 确定分区数 `p` 和哈希函数 `h`。 2. 将关系 A 划分为 `p` 个子关系 `Ai = {a 属于 A | h(key of a) = i}`（`i = 0, ..., p - 1`），将关系 B 划分为 `p` 个子关系 `Bi = {b 属于 B | h(key of b) = i}`（`i = 0, ..., p - 1`），每个子关系存储在二级内存中。 3. 对于每个 `i = 0, ..., p - 1`，如果 `Ai` 或 `Bi` 可以完全加载到主内存中，则使用内部哈希连接将它们连接起来；否则，递归执行步骤 1 到 3。 ### 3.3 用户定义函数 为了提高效率，将应用程序特定的部分（如方法）实现为用户定义的函数，并嵌入