XML模式语言与命令式XML程序分析

### XML模式语言与命令式XML程序分析 #### 1. 强线性模式基XML模式 在实际的XSD中，节点类型往往仅依赖于其父节点和祖父节点的标签。为了描述这一特性，我们引入了强线性正则表达式的概念。若正则表达式形式为 `w` 或 `Σ∗w`（其中 `w` 非空），则称其为强线性的。若一个基于模式的模式是不相交的，且其所有垂直表达式都是强线性的，那么该模式就是强线性的。我们用 `P∃(S-Lin)` 和 `P∀(S-Lin)` 分别表示存在语义和全称语义下的强线性模式基模式类。 在强线性模式中，所有水平表达式通常要求是确定性的或单义的，这与DTD和XML Schema的情况类似。这一要求对于实现多项式时间的可满足性和包含性检查是必要的，否则对于任意正则表达式，这些问题将是PSPACE完全的。不过，对于各种翻译问题，这一要求并非必需。因此，我们区分了上述定义的强线性模式和所有水平表达式必须是确定性的强线性模式，后者称为确定性强线性模式，分别用 `P∃(Det-S-Lin)` 和 `P∀(Det-S-Lin)` 表示。 以下是关于（确定性）强线性模式基模式的一些重要定理： | 序号 | 内容 | | ---- | ---- | | 1 | `P∃(S-Lin) poly → P∀(S-Lin)` 和 `P∃(Det-S-Lin) poly → P∀(Det-S-Lin)` | | 2 | `P∃(S-Lin) poly → EDTD` 和 `P∃(Det-S-Lin) poly → EDTD` | | 3 | `P∃(S-Lin) poly → EDTDst` 和 `P∃(Det-S-Lin) poly → EDTDst` | | 4 | `P∃(S-Lin)` 的简化问题是PSPACE完全的 | | 5 | `P∃(Det-S-Lin)` 的简化问题是多项式时间可解的 | | 6 | `P∃(S-Lin) poly ̸→ DTD` 和 `P∃(Det-S-Lin) poly ̸→ DTD` | | 7 | `P∀(S-Lin) poly → P∃(S-Lin)` 和 `P∀(Det-S-Lin) poly → P∃(Det-S-Lin)` | | 8 | `P∀(S-Lin) poly → EDTD` 和 `P∀(Det-S-Lin) poly → EDTD` | | 9 | `P∀(S-Lin) poly → EDTDst` 和 `P∀(Det-S-Lin) poly → EDTDst` | | 10 | `P∀(S-Lin)` 的简化问题是PSPACE完全的 | | 11 | `P∀(Det-S-Lin)` 的简化问题是多项式时间可解的 | | 12 | `P∀(S-Lin) poly ̸→ DTD` 和 `P∀(Det-S-Lin) poly ̸→ DTD` | 下面我们来证明其中的部分定理： - **证明 `P∃(S-Lin) poly → P∀(S-Lin)`**：关键在于以下引理。 - **引理20**：对于每个不相交的强线性表达式的有限集 `R`，可以在多项式时间内构造一个不相交的强线性正则表达式的有限集 `S`，使得 `∪s∈S L(s) = Σ∗ \ ∪r∈R L(r)`。 - 对于 `P = {(r1, s1), ..., (rn, sn)}`，设 `S` 是满足引理20条件的 `R = {r1, ..., rn}` 的强线性表达式集。令 `P ′ = P ∪ ∪s∈S{(s, ∅)}`。这里，`T∃(P) = T∃(P ′)`，并且由于 `P ′` 是不相交且完备的，根据引理12可得 `T∃(P ′) = T∀(P ′)`，从而 `T∃(P) = T∀(P ′)`。由引理20可知，集合 `S` 是多项式时间可计算的，因此 `P ′` 也是。 - **证明 `P∃(S-Lin) poly → EDTDst`**：给定 `P`，我们构造一个基于自动机的模式 `D = (A, λ)`，使得 `L(D) = T∃(P)`。根据引理7，我们可以在多项式时间内将 `D` 转换为等价的单类型EDTD。设 `P = {(r1, s1), ..., (rn, sn)}`。我们定义 `D` 使得当自动机 `A` 在读取 `w` 后处于状态 `q` 时，`λ(q) = si` 当且仅当 `w ∈ L(ri)`，否则 `λ(q) = ∅`。 构造自动机 `A` 的步骤如下： 1. 假设每个 `ri` 都具有 `Σ∗wi` 的形式，该构造可以扩展到处理 `wi` 形式的垂直表达式。 2. 定义 `S = {w | w ∈ Prefix(wi), 1 ≤ i ≤ n}`。 3. 定义 `A