分布式数据库的数据分区与分配模型详解

### 分布式数据库的数据分区与分配模型详解 #### 1. 基础概念介绍 在分布式数据库中，矩阵和更新矩阵用于描述所有查询的检索和更新行为。站点信息描述了站点的相关信息以及可存储的片段限制，网络信息则定义了两个站点之间的通信成本。 初始分配借助检索矩阵完成。若某个站点检索了片段，该片段必须存储在该站点。在初始分配阶段，所有检索查询将在本地执行，但对于更新查询，通信开销会增加。这里提出了一种针对复制和非复制分布式数据库系统（DDBS）的动态数据重新分配模型，依据给定的片段更新矩阵和距离成本矩阵进行操作。迁移决策是通过选择对某个片段具有最高查询更新成本的站点作为候选存储站点来做出的。 #### 2. 垂直分区模型 在对表进行垂直分区之前，需要了解针对分布式数据库运行的查询信息。由于垂直分区会将经常一起访问的属性放在一起，因此需要一种技术来衡量这种“关联性”，即属性的亲和性。下面介绍相关的矩阵和算法。 ##### 2.1 属性使用矩阵（Attribute Usage Matrix，AUM） 属性使用矩阵用于指示查询所使用的属性。假设有一组用户查询 \(Q = \{Q1, Q2…QQ\}\) 在一组属性 \(\{A1, A2…AN\}\) 上运行，对于每个查询 \(QI\) 和每个属性 \(AJ\)，有一个属性使用值 \(USE (QI, AJ)\) 与之关联。矩阵中值为 1 表示属性被对应查询使用，值为 0 则表示未被使用。示例如下： | Query | A1 | A2 | A3 | A4 | | --- | --- | --- | --- | --- | | Q1 | 1 | 0 | 1 | 0 | | Q2 | 0 | 1 | 1 | 0 | | Q3 | 0 | 1 | 0 | 1 | | Q4 | 1 | 0 | 0 | 1 | ##### 2.2 频率矩阵（Frequency Matrix，FM） 仅依据属性使用值无法对关系中的属性进行分区，因为这些值不能反映属性被查询访问的频率。频率矩阵用于表示从某个站点发起查询的次数。每个站点 \(S = \{S1, S2… SM\}\) 执行一组查询 \(Q = \{Q1, Q2…QQ\}\)，查询 \(QK\) 可以以一定频率从任何站点执行。查询在 \(M\) 个站点的执行频率由一个 \(Q× (M + 1)\) 大小的矩阵表示，其中第 \((M + 1)\) 列表示查询访问次数。示例如下： | Query | S1 | S2 | S3 | Query Access | | --- | --- | --- | --- | --- | | Q1 | 15 | 20 | 10 | 45 | | Q2 | 4 | 0 | 0 | 4 | | Q3 | 25 | 25 | 25 | 75 | | Q4 | 2 | 0 | 0 | 2 | ##### 2.3 属性亲和矩阵（Attribute Affinity Matrix，AAM） 属性亲和矩阵的行和列都代表属性，矩阵元素表示两个属性之间的属性亲和值（aff）。该值是根据一组查询中两个属性一起被使用的次数计算得出的。例如，计算属性 \(A1\) 和 \(A3\) 的亲和值，可从属性使用矩阵中找出同时使用这两个属性的查询（这里只有 \(Q1\)），再从频率矩阵中获取 \(Q1\) 的查询访问次数。最终生成的属性亲和矩阵如下： | Attribute | A1 | A2 | A3 | A4 | | --- | --- | --- | --- | --- | | A1 | 47 | 0 | 45 | 2 | | A2 | 0 | 79 | 4 | 75 | | A3 | 45 | 4 | 49 | 0 | | A4 | 2 | 75 | 0 | 77 | #### 3. 聚类算法 此部分主要基于贡献对数据库表的属性进行聚类，采用的是 Bond Energy Algorithm（BEA）。 ##### 3.1 键矩阵（Bond Matrix） 键矩阵用于展示两个属性之间的关联强度，通过属性亲和矩阵中对应元素的乘积来衡量。示例如下： | Attribute | A1 | A2 | A3 | A4 | | --- | --- | --- | --- | --- | | A1 | 4238 | 330 | 4320 | 248 | | A2 | 330 | 11882 | 512 | 11700 | | A3 | 4320 | 512 | 4442 | 390 | | A4 | 248 | 11700 | 390 | 11558 | ##### 3.2 键能算法（Bond Energy Algorithm，BEA） 键能算法基于属性亲和矩阵对属性进行聚类，将具有高亲和值的属性聚为一类，低亲和值的属性聚为另一类，通过对属性进行排序以最大化全局亲和度量（Global Affinity Measure，GAM）。生成聚类亲和矩阵（Clustered Affinity Matrix，CAM）分三步： 1. **初始化**：将属性亲和矩阵的前两列直接放置到聚类亲和矩阵的相应列中。例如，将属性 \(A1\) 和 \(A2\) 分别放置到聚类亲和矩阵的第一和第二列，得到如下矩阵： | Attribute | A1 | A2 | | --- | --- | --- | | A1 | 47 | 0 | | A2 | 0 | 79 | | A3 | 45 | 4 | | A4 | 2 | 75 | 2. **迭代**：逐个选取剩余属性，尝试将其放置在聚类亲和矩阵的剩余位置，放置依据是对全局亲和度量贡献最大。以属性 \(A3\) 为例，它有三个可能的放置位置：\(A1\) 左侧、\(A1\) 和 \(A2\) 之间、\(