XML发布：理论与实践的桥梁

### XML 发布：理论与实践的桥梁 在当今数字化的时代，数据的存储和交换方式多种多样。关系型数据库作为数据存储的主流方式，存储着大量的数据。然而，在数据交换和构建数据库接口时，XML 格式的数据变得越来越重要。这就引出了将关系型数据转换为 XML 数据的需求，也就是 XML 发布。 #### 1. XML 发布的背景与需求 目前，大部分数据存储在关系型数据库中，但以 XML 格式交换数据或构建数据库的 XML 接口变得越来越普遍。为了满足这一需求，各种 XML 发布语言应运而生，并迅速应用于商业产品中。这些语言本质上是视图定义语言，用于指定关系型数据的 XML 视图。 与关系型视图定义语言类似，XML 发布语言也面临着一些基本问题，如复杂度和表达能力。这些问题不仅具有理论意义，对于用户和设计者来说也非常重要。用户需要决定选择哪种语言来表达 XML 视图，以及哪种语言在评估成本方面更优。数据库供应商则需要了解是否需要升级数据库管理系统（DBMS）来支持某些高级功能。 #### 2. XML 发布的示例与影响因素 为了更好地理解 XML 发布，我们来看一个具体的例子。假设有一个关系型模式 `R0`，包含 `course` 和 `prereq` 两个关系。我们可以定义不同的 XML 视图，如 `τ1`、`τ2`、`τ3` 和 `τ4`。 | 视图 | 描述 | | ---- | ---- | | `τ1` | 深度为 2 的树，包含 `D0` 中所有没有以 `db` 为直接先决条件的课程列表 | | `τ2` | 包含 `D0` 中所有课程的列表，每个课程下显示其标题、直接先决条件的 `cno` 列表，以及下一级先决条件，直到列出所有先决条件 | | `τ3` | 深度为 2 的树，包含 `D0` 中所有课程的列表，每个课程下显示其 `cno` 和所有先决条件的 `cno` 列表 | | `τ4` | 一个需要符合特定 DTD `d0` 的 XML 树 | 在实践中，我们可能会发现某些视图难以用某些 XML 发布语言表达。这可能是因为我们对语言不够熟悉，也可能是语言本身的局限性。为了回答这个问题，我们需要研究影响 XML 发布语言表达能力的各种因素。 这些因素包括： - **CQ、FO 与 FP**：用于表达对关系型数据的查询的关系型查询语言，如连接查询（CQ）、一阶查询（FO）和（膨胀）不动点查询（FP）。例如，`τ1` 需要 FO 查询，不能仅用 CQ 查询的语言表达。 - **关系与元组**：存储中间结果的寄存器。有些语言在寄存器中存储有限关系，而有些则允许单个元组。`τ2` 只能在支持关系寄存器的语言中定义。 - **虚拟与正常节点**：节点的类型。语言可能允许或不允许从输出树中移除的虚拟节点。在不支持 FP 的语言中，`τ3` 只有在允许虚拟节点的情况下才能定义。 - **递归与非递归**：视图是否可以递归定义。例如，`τ2` 和 `τ4` 是递归定义的，因为这些视图中课程子树的深度由其在 `D0` 中的先决条件层次结构决定。 - **是否由 DTD 指导**：输出的 XML 树是否保证符合预定义的 DTD。在实践中，XML 发布通常由类型（通常是 DTD）指导。 不同的参数组合会产生具有不同表达能力和复杂度的 XML 发布语言。 #### 3. 发布转换器 为了刻画现有 XML 发布语言的复杂度、表达能力、等价性和分离性，我们引入了发布转换器。 ##### 3.1 发布转换器的定义 发布转换器是一个有限状态机，给定一个关系型数据库实例 `I`，它从根节点开始自上而下生成一个元素标签来自 `Σ` 的 XML 树。对于 XML 树中每个标签为 `a` 的元素，它关联一个寄存器 `Rega`，用于存储固定arity 的关系作为中间结果。在每个 `a` 节点 `v`，转换器通过 `L` 中的查询从底层数据库 `I` 和 `Rega` 中提取数据，并使用这些数据生成 `v` 的子节点。 发布转换器的定义如下： - 对于关系型模式 `R`，发布转换器 `τ = (Q, Σ, q0, δ)`，其中 `Q` 是有限状态集，`Σ` 是有限标签字母表，`q0` 是与根标签 `r` 关联的起始状态，`δ` 是有限的转换规则集。 - 对于每个 `(q, a) ∈ Q × Σ`，有一个唯一的规则 `(q, a) → (q1, a1, φ1(¯x1; ¯y1)), ..., (qk, ak, φk(¯xk; ¯yk))`，其中 `k ≥ 0`，`a1, ..., ak` 是 `Σ` 中的不同标签，`(qi, ai) ∈ Q × Σ`，`φi ∈ L` 是从 `R` 和 `Rega` 到 `Regai` 的关系型查询。 ##### 3.2 发布转换器的基本属性和语义 - **确定性**：发布转换器是确定性的，对于每个 `(q, a) ∈ Q × Σ`，有一个唯一的转换规则，除了起始状态 `q0` 只有 `(q0, r)` 的规则被定义。此外，`q0` 和 `r` 不会出现在任何规则的右侧，`text` 是一个特殊标签，其规则的右侧为空。 - **元组与关系寄存器**：`L` 查询 `φi(¯xi; ¯yi)` 从 `I` 和 `Rega` 中提取数据，查询结果按属性 `¯xi` 分组，为每个组 `Sj` 创建一个不同的 `ai` 子节点，并将 `Sj` 作为其寄存器 `Regai` 的内容。当 `|¯yi| = 0` 时，每个寄存器 `Regai` 持有单个元组，即为元组寄存器。 - **转换过程**：初始时，`τ` 构建一个由单个标签为 `(q0, r)` 且寄存器为空的节点组成的树 `t`。在每一步，`τ` 同时操作 `t` 的叶节点，通过查找规则、执行查询并生成子节点，直到满足停止条件。停止条件包括： - 从根节点到叶节点的路径上存在一个节点 `v`，使得 `v` 和叶节点具有相同的状态 `q`、标签 `a` 和 `Rega(v) = Rega(u)`。 - 所有查询 `φj(¯xj; ¯yj)` 的评估结果为空。 - 规则的右侧为空，特别是对于 `a = text` 的情况。 当树无法进一步扩展时，通过移除所有寄存器和状态，生成一个 XML 树，这就是转换器 `τ` 的输出 `τ(I)`。 下面是一个发布转换器的示例： ```plaintext δ1(q0, db) = (q, course, φ1(n, t; ∅)), where φ1(n, t) = ∃tp (course(n, t, tp) ∧¬∃n1, t1, tp1 (prereq(n, n1)∧course(n1, t1, tp1)∧t1=‘db’)) δ1(q, course) = (q, cno, φ2(n; ∅)), (q, title, φ3(t; ∅)), where φ2(n) = ∃t Regc(n, t), and φ3(t) = ∃n Regc(n, t), δ1(q, cno) = (q, text, φ4(n)), where φ4(n) = Regn(n) (similarly for δ1(q, title)) δ1(q, text) = . (empty right-hand side.) ``` 这个转换器用于生成图 1(a) 中的视图。 ##### 3.3 递归转换器与虚拟节点 递归转换器的定义基于其依赖图 `Gτ`。对于每个 `(q, a) ∈ Q × Σ`，在 `Gτ` 中有一个唯一的节点 `v(q, a)`，如果 `(q′, a′)` 在 `(q, a)` 的规则右侧，则存在从 `v(q, a)` 到 `v(q′, a′)` 的边。如果 `Gτ` 中存在循环，则转换器 `τ` 是递归的。 为了包含虚拟节点，我们将转换器推广为 `τ = (Q, Σ, q0, δ, Σe)`，其中 `Σe` 是 `Σ` 的指定子集，`r ∉ Σe`，称为 `τ` 的虚拟标签。在处理关系型数据库 `I` 时，转换器的行为与正常转换器相同，但在生成 XML 树 `τ(I)` 时，如果节点 `v` 的标签在 `Σe` 中，则将其替换为其子节点。 下面是一个递归转换器的示例： ```plaintext δ2(q0, db) = (q, course, ψ1(n, t; ∅)), where ψ1(n, t) = ∃tp course(n, t, tp) δ2(q, course) = (q, title, ψ2(t; ∅)), (q, cno, ψ3(n; ∅)), (q, next-level, ψ4(∅; n)), where ψ2(t) = ∃n Regc(n, t), ψ3(n1) = ∃n, t(Regc(n, t) ∧prereq(n, n1)) δ2(q, next-level) = (q, cno, ψ5(n; ∅)), (q, next-level, ψ5(∅; n)) ``` 这个转换器用于生成图 1(b) 中的视图，并且是递归定义的。 通过以上内容，我们对 XML 发布的背景、需求、影响因素以及发布转换器有了更深入的了解。这些知识将帮助我们更好地选择和使用 XML 发布语言，以及设计和实现相关的系统。 下面是发布转换器工作流程的 mermaid 流程图： ```mermaid graph TD; A[开始] --> B[创建根节点]; B --> C[评估查询]; C --> D[生成子节点]; D --> E{是否满足停止条件}; E -- 否 --> C; E -- 是 --> F[移除寄存器和状态]; F --> G[生成 XML 树]; G --> H[结束]; ``` 这个流程图展示了发布转换器从开始到生成 XML 树的整个过程。首先创建根节点，然后评估查询并生成子节点，不断重复这个过程直到满足停止条件。最后移除寄存器和状态，生成最终的 XML 树。 ### XML 发布：理论与实践的桥梁 #### 4. 用发布转换器刻画 XML 发布语言 我们可以利用发布转换器来刻画现有的 XML 发布语言，评估它们的表达能力和复杂度。以下是一些常见的 XML 发布语言及其对应的发布转换器特征： | 语言 | 关系查询语言 | 寄存器类型 | 是否支持虚拟节点 | 是否递归定义 | 是否支持 DTD 指导 | | ---- | ---- | ---- | ---- | ---- | ---- | | sql/xml（IBM DB2 XML Extender、Oracle 10g XML DB） | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | | for - xml 和 xsd（SQL Server 2005） | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | | dad（DB2 XML Extender） | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | | dbms xmlgen（Oracle 10g XML DB） | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | | XPERANTO | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | | TreeQL（SilkRoute） | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | | ATG（PRATA） | 可能支持 CQ、FO、FP | 可能支持关系或元组寄存器 | 可能支持 | 可能支持 | 可能支持 | 通过这种方式，我们可以清晰地看到不同语言在各个方面的特点，从而根据具体需求选择合适的语言。例如，如果需要表达递归定义的视图，就需要选择支持递归转换器的语言；如果要保证输出的 XML 树符合特定的 DTD，就需要选择支持 DTD 指导的语言。 #### 5. XML 发布的增量更新和视图更新问题 由于 XML 发布实际上定义了关系型数据的 XML 视图，因此对于数据库视图来说重要的增量更新和视图更新问题，对于 XML 发布同样值得关注。 ##### 5.1 增量更新 增量更新的目标是在关系型数据库发生变化时，高效地更新相应的 XML 视图。目前，只有一些研究原型系统（如 PRATA）支持这一功能，商业系统中尚未广泛实现。实现增量更新可以按照以下步骤进行： 1. **监测数据库变化**：实时或定期监测关系型数据库中的数据变化，记录插入、删除和修改的元组。 2. **确定受影响的视图**：根据数据库变化和视图定义，确定哪些 XML 视图会受到影响。 3. **计算视图更新**：根据受影响的视图和数据库变化，计算需要对 XML 视图进行的更新操作。 4. **应用更新**：将计算得到的更新操作应用到 XML 视图上，生成更新后的 XML 树。 ##### 5.2 视图更新 视图更新是指当用户对 XML 视图进行修改时，将这些修改反映到关系型数据库中。这是一个更具挑战性的问题，因为 XML 视图和关系型数据库之间的映射可能是复杂的。实现视图更新可以按照以下步骤进行： 1. **解析用户修改**：解析用户对 XML 视图的修改操作，确定修改的位置和内容。 2. **反向映射到数据库**：根据 XML 视图的定义和映射规则，将用户的修改反向映射到关系型数据库中的相应操作。 3. **执行数据库更新**：将反向映射得到的数据库操作应用到关系型数据库中。 4. **更新 XML 视图**：根据数据库的更新结果，更新 XML 视图，确保视图与数据库保持一致。 下面是 XML 发布更新流程的 mermaid 流程图： ```mermaid graph TD; A[数据库变化或用户修改] --> B{变化类型}; B -- 数据库变化 --> C[监测数据库变化]; B -- 用户修改 --> D[解析用户修改]; C --> E[确定受影响的视图]; D --> F[反向映射到数据库]; E --> G[计算视图更新]; F --> H[执行数据库更新]; G --> I[应用更新]; H --> J[更新 XML 视图]; I --> K[完成更新]; J --> K; ``` 这个流程图展示了无论是数据库变化还是用户对 XML 视图的修改，都可以通过一系列步骤实现 XML 视图和关系型数据库的同步更新。 #### 6. 开放研究问题 尽管我们对 XML 发布有了一定的了解，但仍然存在一些开放的研究问题： - **更高效的发布转换器**：目前的发布转换器在处理大规模数据时可能效率较低，需要研究更高效的算法和数据结构来提高其性能。 - **更好的视图更新策略**：视图更新问题仍然是一个具有挑战性的问题，需要研究更有效的反向映射算法和更新策略，以确保 XML 视图和关系型数据库之间的一致性。 - **支持更多的数据模型**：随着新兴数据模型（如流数据、图数据等）的出现，需要研究如何将 XML 发布扩展到支持这些新的数据模型。 - **标准化 XML 发布语言**：目前存在多种 XML 发布语言，缺乏统一的标准。需要推动 XML 发布语言的标准化，以提高不同系统之间的互操作性。 通过解决这些开放研究问题，我们可以进一步完善 XML 发布的理论和实践，使其在数据交换和数据库接口构建中发挥更大的作用。