数据集市集成中聚合层次结构的推断

### 数据集市集成中聚合层次结构的推断 在企业数据仓库的构建过程中，异构数据集市的集成是一个重要问题，而识别兼容维度对于成功集成尤为关键。传统的维度兼容性概念依赖于给定的精确维度层次结构信息，但在实际应用中，特别是在自主数据集市的情况下，维度的聚合层次结构并非总是可用。本文提出从数据库实例中推断维度的聚合层次结构，并将其用于数据集市的集成。 #### 1. 数据集市与聚合层次结构基础 数据集市基于星型模式，这是一种允许实现关系数据库以服务于多维数据库目的的数据模型。在该模型中，可聚合的定量数据（即事实）包含在事实表中，而用于聚合和过滤事实的信息（即维度属性）包含在维度表中。维度属性被分组到聚合层次结构的各个级别中，使得可以从较低级别的事实计算出较高级别的聚合事实，这种特性称为可汇总性。 例如，在一个简单的数据集市中，我们可以将商店的销售数据汇总得到地区的销售数据，再将地区的销售数据汇总得到城市的销售数据，即销售值从商店级别“上卷”到地区级别，再从地区级别“上卷”到城市级别。 大型企业多年来会开发许多自主的数据集市，将这些数据集市集成到企业仓库中进行企业级大规模分析是一个战略业务目标。而在线分析处理（OLAP）工具在集成后仓库中进行信息探索和汇总的成功，依赖于集成后仓库的维度和聚合层次结构准确反映集成前数据集市的情况。 #### 2. 聚合层次结构的定义 - **维度**：一个维度 $D$ 由一个层次的聚合层次结构 $H$ 组成。给定维度 $D$ 的两个级别 $l$ 和 $l'$，如果可以从级别 $l$ 的事实计算出级别 $l'$ 的聚合事实，则称级别 $l$ 上卷到级别 $l'$，记为 $l \preceq l'$。上卷关系 $\preceq$ 在级别上形成一个偏序。聚合层次结构 $H$ 是一个无环有向图，没有传递边，图的节点是级别，边是级别之间偏序覆盖关系中的上卷关系。 - **维度的关系表示**：维度 $D$ 可以由一个包含 $n$ 个属性的关系 $D(A_1, ..., A_n)$ 表示，其中一个或多个属性对应每个级别，使得这些级别将所有属性划分为不相交的子集。 - **维度表**：维度表 $T = \{t_1, ..., t_s\}$ 是表示维度的关系 $D(A_1, ..., A_n)$ 的一个实例，其中每个元组 $t_a = \langle v_{a1}, ..., v_{an} \rangle$ 包含 $n$ 个值，每个值 $v_{ai}$ 是属性 $A_i$ 对应域中的一个元素。 - **属性的偏序**：给定维度 $D(A_1, ..., A_n)$ 的一个实例 $T$，如果对于 $T$ 中的每对元组 $t_a = \langle v_{a1}, ..., v_{an} \rangle$ 和 $t_b = \langle v_{b1}, ..., v_{bn} \rangle$，$v_{ai} = v_{bi}$ 意味着 $v_{aj} = v_{bj}$，则称 $A_i \leq A_j$。$\leq$ 关系在维度属性集上形成一个偏序 $P$。 - **模式定义的聚合层次结构（SAH）**：SAH 是作为维度 $D$ 模式的一部分定义的聚合层次结构，它对 $D$ 的任何实例 $T$ 中的元组构成约束。 #### 3. 推断聚合层次结构 由于每个维度实例都受其 SAH 约束，数据可以作为推断聚合层次结构的可靠来源。不过，推断的聚合层次结构（IAH）可能与预期的 SAH 有所不同，这通常是因为维度表仅部分填充。推断 IAH 分为三个步骤： - **推断属性的偏序**：提出算法 1 来推断属性的偏序。以判断 $Country \leq City$ 为例，算法首先按 $Country$ 对元组进行排序，然后扫描 $Country$ 和 $City$ 的值。如果在整个表 $T$ 中，只要 $Country$ 的值在相邻元组中保持不变，$City$ 的值也保持不变，则上卷关系成立。对于示例数据，$Country \leq City$ 不成立，而 $Country \leq Region$ 成立。 ```plaintext Algorithm 1. Inferring the partial order relationships Input Tuples T = {t1, t2, ..., tp} in the instance of a dimension D(A1, A2, ..., An), and p is the number of tuples. Output Partial order P of attributes. 1: P := {} 2: for each attribute Ai do 3: Sort T on Ai 4: for each attribute Aj do 5: for each tuple do 6: if Ai on current tuple equals Ai on the previous tuple then 7: if Aj on current tuple does not equal Aj on the previous tuple then 8: exit this loop 9: end if 10: end if 11: end ```