XML文档XFD验证与属性文法方法解析

### XML文档XFD验证与属性文法方法解析 #### 1. 引言 在处理XML文档时，确保其数据的完整性和一致性至关重要。为了实现这一目标，常常需要对XML文档进行完整性约束验证。本文将介绍使用有限状态自动机（FSA）和属性文法来验证XML文档中的XML函数依赖（XFD）的方法。 #### 2. 有限状态自动机用于XFD路径建模 为了对XFD的路径进行建模，我们使用有限状态自动机（FSA）或转换器（FST）。有限状态机的使用带来了以下好处： - 能够清晰地区分每条路径（例如上下文路径），从而定义所需属性的计算。 - 可以轻松处理符号`//`，以应对唯一路径的不同实例化情况（例如，路径`a//b`的实例`a.b`和`a.x.b`）。 有限状态机的输入字母表是XML标签的集合，转换器的输出字母表由相等符号组成。通常，FSA用5元组`A = (Θ, V, Δ, e, F)`表示，其中： - `Θ`是有限状态集。 - `V`是字母表。 - `e ∈ Θ`是初始状态。 - `F ⊆ Θ`是最终状态集。 - `Δ: Θ × V → Θ`是转移函数。 FST是6元组`A = (Θ, V, Γ, Δ, e, F, λ)`，满足： - `(Θ, V, Δ, e, F)`是FSA。 - `Γ`是输出字母表。 - `λ`是从`F`到`Γ`的函数，表示与每个最终状态相关联的输出。 在XFD中，路径表达式`C`、`Pi`和`Q`（`i ∈ [1, k]`）分别指定约束上下文、决定因素路径（LHS）和依赖路径（RHS）。为了验证路径实例是否对应于这些路径之一，我们使用以下自动机和转换器： - 上下文自动机`M = (Θ, Σ, Δ, e, F)`表示路径`C`，字母表`Σ`由XML文档标签组成。 - 决定因素转换器`T ′ = (Θ′, Σ, Γ ′, Δ′, e′, F ′, λ′)`表示路径`Pi`（`i ∈ [1, k]`）。输出符号集`Γ ′ = {V, N}×N∗`，其中`V`（值相等）和`N`（节点相等）是要与每个路径关联的相等类型。每个路径都有编号，因为LHS中可能有多个路径。输出函数`λ′`将一对（相等性，编号）关联到`T ′`的每个最终状态`q ∈ F ′`。 - 依赖转换器`T ′′ = (Θ′′, Σ, Γ ′′, Δ′′, e′′, F ′′, λ′′)`表示路径`Q`。输出符号集`Γ ′′ = {V, N}`，输出函数`λ′′`将一个符号`V`或`N`关联到`T ′′`的每个最终状态`q ∈ F ′′`。 以下是不同XFD对应的自动机和转换器示例： | XFD编号 | 自动机/转换器 | 说明 | | ---- | ---- | ---- | | XFD1和XFD2 | 上下文自动机和决定因素转换器相同 | XFD1的依赖转换器应用节点相等，XFD2应用值相等 | | XFD3 | 自动机`M3`和转换器`T ′3`、`T ′′3` | 决定因素转换器`T ′3`收集`@sname`和`@cname`的属性值，共同决定组件的数量 | #### 3. XFD验证：属性文法方法 属性文法是上下文无关文法的扩展，它不仅可以指定语言的语法，还可以指定其语义。通过为上下文无关文法的每个产生式附加一组语义规则来实现这一点。在语义规则中，可以找到两种类型的属性：综合属性和继承属性。综合属性将信息从树的叶子传递到根，而继承属性则相反，从根传递到叶子。 属性文法定义为三元组`GA = (G, A, F)`，其中： - `G = (VN, VT, P, B)`是上下文无关文法。 - `A`是属性集。 - `F`是附加到产生式的语义规则集。 对于`X ∈ VN ∪ VT`，有`A(X) = S(X) + I(X)`，即`A(X)`是`X`的综合属性集`S(X)`和继承属性集`I(X)`的不相交并集。如果`a`是`A(X)`的属性，则表示为`X.a`。对于产生式`p : X0 → X1 ... Xn`，`p`的属性集表示为`W(p) = {Xi.a | a ∈ A(Xi), i ∈ [0 ... n]}`。每个产生式`p : X0 → X1 ... Xn`的集合`Fp`包含处理`p`的属性集的语义规则。 在XFD验证的上下文中，我们使用一个通用的上下文无关文法`G`，它包含以下三个通用产生式规则： - 根元素规则：`ROOT → α1 ... αm`，`m ∈ N`。 - 内部元素节点规则：`A → α1 ... αm`，`m ∈ N∗`。 - 包含数据的元素和属性规则：`A → data`。 文法`G`通过与完整性约束相关的属性和动作组成的语义规则进行扩展。读取XML文档意味着先自上而下访问XML树，打开标签，然后自下而上关闭标签。在自上而下的访问过程中，验证过程（借助FSAs）指定每个节点相对于给定XFD的角色，并将此角色存储在继承属性中。到达叶子节点后，开始自下而上的访问，以提取与完整性约束相关的值，并将这些值存储在不同的综合属性中。 #### 4. 继承属性的计算 我们首先考虑继承属性`conf`，它表示`XML`树`t`中每个节点相对于给定`XFD`的角色。其值是一组`FSA`配置。除了数据类型的节点外，`t`中的所有节点都绑定到`conf`属性，但对于某些节点，`conf`的值为空集，这意味着该节点不在`XFD`的任何路径上。 以下是计算`conf`属性的语义规则： - **根节点规则**： ```plaintext Production Attributes ROOT → α1 ... αm ROOT.conf := { M.q1 | δM (q0, ROOT) = q1} for each αi (1 ≤ i ≤ m) do αi.conf := { M.q′ | δM (q1, αi) = q′ } if (q1 ∈ FM) then αi.conf := αi.conf ∪ { T ′.q′1 | δT ′(q′0, αi) = q′1 } ∪ { T ′′.q′′1 | δT ′′(q′′0, αi) = q′′1 } ``` - **内部节点规则**： ```plaintext Production Attributes A → α1 ... αm for each αi (1 ≤ i ≤ m) do for each M.q in A.conf do αi.conf := { M.q′ | δM (q, αi) = q′ } if (M = M) ∧ (q ∈ FM) ```