半结构化数据类型检查与查询语言详解

### 半结构化数据类型检查与查询语言详解 #### 1. 树的表示与半结构化数据实例 为了表示树，我们使用一种简单的语法： ```plaintext T ::= σ(F) | σ′ F ::= T | T, F ``` 其中 `σ ∈Σ` 且 `σ′ ∈Σ ∪D`。 例如，下面是一个半结构化数据实例，其树表示如图 1 所示： ```plaintext catalog(product(name("Widget"), mfr-price(55), color("Red")), product(name("Gizmo"), mfr-price(99), sales-price(79)), product(name("Super-Widget"), color("Green"), color("Blue"))) ``` #### 2. 类型相关内容 ##### 2.1 有秩树和树自动机 - **有秩字母表与有秩树**：有秩字母表 `Ω` 是一个划分为 `k` 个子集的集合，即 `Ω = Ω0 ∪ ... ∪ Ωk`。在 `Ω` 上的有秩树是一个有限的、有序的树，其中每个有 `i` 个孩子的节点都用 `Ωi` 中的一个符号标记。我们用 `TΩ` 表示有秩 `Ω` - 树的集合。 - **树自动机**：树自动机是一种接受或拒绝有秩树的设备。非确定性自顶向下的树自动机 `A = (Ω, Q, q0, P)`，其中 `Q` 是一个有限的状态集，`q0 ∈ Q` 是初始状态，`P ⊆ ⋃i = 0,k Ωi × Q × Qi`。当 `(a, q, q1, ..., qi) ∈ P` 时，我们写成 `(a, q) → q1q2 ... qi`。 - **自动机计算过程**：给定 `t ∈ TΩ`，自动机通过为 `t` 中的节点分配状态来进行计算。首先将 `q0` 分配给根节点。当某个带有符号 `a` 的节点 `u` 被分配了状态 `q`，并且在 `P` 中存在一个转移 `(a, q) → q1 ... qi` 时，状态 `q` 从 `u` 中移除，状态 `q1, ..., qi` 被分配给其孩子。如果 `u` 是叶子节点（`i = 0`），则只从 `u` 中移除状态。如果我们可以从树中移除所有状态，则该树被接受。`L(A)` 表示被 `A` 接受的树的集合，称为正则树语言。 树自动机的一些性质如下： |性质|描述| |----|----| |自动机等价性|自底向上和自顶向下的树自动机定义了相同的正则树语言集合| |布尔运算封闭性|正则树语言在布尔运算（并、交、差）下是封闭的| |包含关系可判定性|可以判定一个正则语言是否包含在另一个正则语言中| ##### 2.2 正则无秩树语言 Brüggemann - Klein 等人将树自动机扩展到无秩树。问题在于符号 `a ∈ Σ` 没有秩，因此我们需要为所有 `n ≥ 0` 指定可能无限多的转移 `(a, q) → q1 ... qn`。无秩树自动机的定义与之前类似，但现在 `P` 是 `Σ × Q × Q∗` 的子集，可能是无限的，但对于每个 `a ∈ Σ` 和 `q ∈ Q`，集合 `{w | (a, q, w) ∈ P} ⊆ Q∗` 是一个正则集。这允许我们将 `P` 描述为三元组 `(a, q, E)` 的集合，其中 `E` 是字母表 `Q` 上的正则表达式。对于每个 `a ∈ Σ`，`q ∈ Q`，`P` 中恰好需要一个对 `(a, q, E)`。无秩正则树语言是被某个无秩树自动机接受的集合 `τ ⊆ UΣ`。 ##### 2.3 XDuce 类型 XDuce 是一种用于 XML 的函数式编程语言，它以实用的语法定义 XML 类型。假设 `Integer` 和 `String` 是预定义类型，以下定义了三种新类型： ```plaintext CatalogType = catalog(ProductsType) ProductsType = (product(ProductType))* ProductType = (name(String), mfr-price(Integer), (sales-price(Integer))?, (color(String))*) ``` 也可以使用更简洁的语法： ```plaintext CatalogType = catalog(ProductsType) ProductsType = product(name(String), mfr-price(Integer), sales-price(Integer)?, color(String)*)* ``` 形式上，我们有一个类型标识符集合 `Q`。单元类型是一个对 `(σ, q)`，其中 `σ ∈ Σ` 且 `q ∈ Q`，记为 `σ(q)`。然后考虑单元类型上的正则表达式： ```plaintext E ::= σ(q) | ϵ | E, E | (E|E) | E∗ | E? ``` 类型定义 `TD` 是对 `(q, E)` 的集合，其中 `q ∈ Q` 且 `E` 是正则表达式，对于每个 `q ∈ Q`，`TD` 中恰好存在一个对 `(q, E)`。 ##### 2.4 DTD 和 XML - Schema - **DTD**：在 DTD 中，如果两个具有相同标签的单元类型 `σ(q)` 和 `σ(q′)` 出现在类型定义 `TD` 中，那么它们的类型标识符必须相同，即 `q = q′`。DTD 是一组对 `(σ, E)`，其中 `σ ∈ Σ` 且 `E` 是 `Σ` 上的正则表达式。 - **XML - Schema**：在 XML - Schema 中，对于每个对 `(q1, E1) ∈ TD`，如果两个具有相同标签的单元类型 `σ(q)` 和 `σ(q′)` 出现在 `E1` 中，它们的类型必须相同，即 `q = q′`。同一标签在不同上下文中可能有不同的类型。 ##### 2.5 专门化 DTD 专门化 DTD 由两个字母表 `Q` 和 `Σ`、一个关于 `Q` 的 DTD 以及一个从 `Q` 到 `Σ` 的函数 `f` 组成。它定义的集合由第一个 DTD 在函数 `f` 下的同胚图像组成。 ##### 2.6 类型定义的等价性 上述三种不同的类型定义是等价的，它们定义了相同类别的无秩正则树语言。并且，它们与正则（有秩）树语言有两种不同的对应方式。可以将有秩字母表 `Ω` 视为无秩字母表，定义一个函数 `u : TΩ → UΩ` 来忽略秩；也可以将无秩树编码为有秩树。 以下是一种特定的编码方式： 给定无秩字母表 `Σ`，关联有秩字母表 `Ω`：`Ω0 = {|}`，`Ω2 = Σ ∪ {−}`。定义树的 “编码” 函数 `e : UΣ → TΩ` 和森林的编码函数 `f : U∗Σ → TΩ`： ```plaintext e(σ) = σ(|, |) e(σ(F)) = σ(f(F), |) f(T, F) = −(e(T), f(F)) f(T) = e(T) ``` 解码函数 `d : TΩ → U∗Σ` 定义如下： ```plaintext d(−(T1, T2)) = d(T1), d(T2) d(σ(T1, T2)) = σ(d(T1), d(T2)) (σ ∈ Σ) d(|) = ε ``` 以下是关于无秩和有秩树正则语言关系的定理： 1. 设 `Σ` 是无秩字母表，`τ ⊆ UΣ`。以下是等价的： - (a) `τ` 被无秩树自动机接受。 - (b) `τ` 可由 XDuce 类型定义。 - (c) `τ` 可由专门化 DTD 定义。 2. 给定无秩字母表 `Σ`，设 `Ω` 是其关联的秩为 2 的字母表，`τ ⊆ UΣ`。则以下是等价的： - (a) `τ` 是无秩正则树语言。 - (b) `e(τ)` 是正则树语言。 3. 给定有秩字母表 `Ω`，集合 `τ ⊆ TΩ` 是正则的当且仅当 `u(τ)` 是无秩正则树的集合。 ```mermaid graph LR A[无秩树自动机接受的语言] -->|等价于| B[XDuce 类型定义的语言] B -->|等价于| C[专门化 DTD 定义的语言] D[有秩树语言] -->|忽略秩| E[无秩正则树语言] F[无秩树语言] -->|编码| G[有秩树语言] ``` #### 3. 查询语言 处理 XML 数据有两种不同的范式：声明式和函数式。 - **声明式语言**：如 XML - QL 和 XQuery 是用于将 XML 映射到 XML 的声明式语言，像 Xperanto 和 SilkRoute 等系统有用于将关系数据库映射到 XML 的声明式语言。声明式语言的评估分两步进行：首先找到所有变量的绑定，然后为每个绑定计算一些结果片段。 - **函数式语言**：在 XSL 和 XDuce 中，XML 到 XML 的转换通过使用递归函数遍历输入文档来表达。例如在 XSL 中，通常从根开始向下进行，在任何时候都可以继续处理当前节点的父节点，甚至可以重新从根开始。 ##### 3.1 TreeQL TreeQL 是一种用于将关系数据库映射到树的语言。它使用合取查询来构造树。 - **基本概念**：用 `CQ` 表示合取查询的集合。给定 `q ∈ CQ`，`headVar(q)` 表示其自由变量；如果 `¯X ⊆ headVar(q)`，则 `Π ¯X(q)` 表示 `q` 在变量 `¯X` 上的投影。对于某个数据库实例 `DB = (D, R1, ..., Rk)`，`q(DB)` 表示 `q` 在 `DB` 上的结果。 - **TreeQL 程序**：TreeQL 程序 `P` 是 `UΣ×CQ` 中的一棵树。每个节点 `u` 在 `P` 中都用一个标签和一个合取查询 `qu` 标记。形式上，TreeQL 程序 `P ∈ UΣ×CQ` 满足：当 `u` 是 `v` 的父节点时，`headVar(qu) ⊆ headVar(qv)` 且 `ΠheadVar(qu)(qv) ⊆ qu`。 - **示例程序**：考虑关系数据库模式 `product(pid, name, mfrprice), colors(cid, pid, color), sales(sid, pid, price)`，以下是一个 TreeQL 程序： ```plaintext catalog() :- product(pid) :- product(pid, _, _) name(pid, name) :- product(pid, name, _) mfr-price(pid, price) :- product(pid, _, price) sales-price(pid, sprice) :- product(pid, _, _), sales(_, pid, sprice) color(pid, color) :- product(pid, _, _), colors(_, pid, color) ``` ##### 3.2 RecQL RecQL 是一种将输入树映射到输出树的函数式语言。一个程序由一个表达式 `E` 组成，其中有几个相互递归的函数。函数以单个节点作为输入参数，可以构造结果森林、测试谓词或递归调用其他函数。 RecQL 的定义如下： ```plaintext E ::= let fun f1(x) = E1 fun f2(x) = E2 ... fun fn(x) = En in F | F F ::= x | σ(F) | tag (x)(F) | F1, F2 | () | (∗) if P then F1 else F2 | f(x) | f(down (x)) | f(up (x)) | f(left (x)) | f(right (x)) P ::= (tag (x) = σ) | x = y | hasDown (x) | hasUp (x) | hasLeft (x) | hasRight (x) ``` 我们对函数调用施加了一个限制：变量 `x` 必须在与 `f` 相同的块或其周围的块中定义。程序是一个具有唯一自由变量 `t` 的表达式。 ### 半结构化数据类型检查与查询语言详解 #### 4. 类型检查相关性质 类型检查在半结构化数据处理中是一个重要的环节，其中一个关键性质是对于任意两种半结构化数据类型 `τ1` 和 `τ2`，判断 `τ1 ⊆ τ2` 是否成立是可判定的。这一性质源于与正则树语言的联系，因为 `τ1 ⊆ τ2` 等价于 `e(τ1) ⊆ e(τ2)`，而正则树语言的包含关系是可判定的。 下面我们通过一个表格来总结前面提到的各种类型和自动机的重要性质： |类型/自动机|定义特点|重要性质| |----|----|----| |有秩树自动机|非确定性自顶向下 `A = (Ω, Q, q0, P)`，`P ⊆ ⋃i = 0,k Ωi × Q × Qi`|自底向上和自顶向下定义相同正则树语言集合；正则树语言在布尔运算下封闭；包含关系可判定| |无秩树自动机|`P` 是 `Σ × Q × Q∗` 的子集，对每个 `a ∈ Σ` 和 `q ∈ Q`，`{w | (a, q, w) ∈ P} ⊆ Q∗` 是正则集|接受无秩正则树语言| |XDuce 类型|基于类型标识符 `Q` 和单元类型 `σ(q)` 定义正则表达式|可定义无秩正则树语言| |DTD|单元类型相同标签对应相同类型标识符，是 `(σ, E)` 的集合|可表达部分 XDuce 类型| |XML - Schema|同一上下文中相同标签单元类型相同|可表达部分 XDuce 类型| |专门化 DTD|由字母表 `Q`、`Σ`，`Q` 上的 DTD 和函数 `f` 组成|与 XDuce 类型、无秩树自动机定义相同无秩正则树语言类| #### 5. TreeQL 程序执行流程 TreeQL 程序将关系数据库映射到树，其执行流程如下： 1. **定义程序结构**：TreeQL 程序 `P` 是 `UΣ×CQ` 中的树，每个节点 `u` 有标签和对应的合取查询 `qu`。 2. **节点关系约束**：当 `u` 是 `v` 的父节点时，需满足 `headVar(qu) ⊆ headVar(qv)` 且 `ΠheadVar(qu)(qv) ⊆ qu`。 3. **处理数据库实例**：对于有序数据库 `DB`，`P(DB) ∈ UΣ` 的节点是 `(u, ¯x)`，其中 `u ∈ nodes(P)` 且 `¯x ∈ qu(DB)`。节点 `(u, ¯x)` 的标签与 `u` 相同。 4. **确定父子关系**：若 `u` 是 `v` 的父节点且 `¯x = ΠheadVar(qu)(¯y)`，则 `(u, ¯x)` 是 `(v, ¯y)` 的父节点。 5. **节点排序**：节点按字典序排序，使用 `P` 和 `DB` 中的顺序。 以之前的示例程序为例，其执行过程如下： ```plaintext catalog() :- product(pid) :- product(pid, _, _) name(pid, name) :- product(pid, name, _) mfr-price(pid, price) :- product(pid, _, price) sales-price(pid, sprice) :- product(pid, _, _), sales(_, pid, sprice) color(pid, color) :- product(pid, _, _), colors(_, pid, color) ``` - 首先计算 `catalog()` 的查询，返回单个值（空元组），对应根节点。 - 接着计算 `product(pid)` 的查询，为每个结果元组构造一个 `product` 节点。 - 然后计算 `name(pid, name)` 的查询，为每个结果构造一个 `name` 节点，其父节点是具有相同 `id` 的 `product` 节点，以此类推。 ```mermaid graph LR A[开始] --> B[计算 catalog() 查询] B --> C[计算 product(pid) 查询] C --> D[为每个 product 结果构造节点] D --> E[计算 name(pid, name) 查询] E --> F[为每个 name 结果构造节点并确定父节点] F --> G[计算 mfr - price(pid, price) 查询] G --> H[为每个 mfr - price 结果构造节点并确定父节点] H --> I[计算 sales - price(pid, sprice) 查询] I --> J[为每个 sales - price 结果构造节点并确定父节点] J --> K[计算 color(pid, color) 查询] K --> L[为每个 color 结果构造节点并确定父节点] L --> M[结束] ``` #### 6. RecQL 语言特点与使用注意事项 RecQL 是一种将输入树映射到输出树的函数式语言，其特点和使用注意事项如下： - **语言结构**：程序由表达式 `E` 组成，包含多个相互递归的函数。函数以单个节点为输入参数，可构造结果森林、测试谓词或递归调用其他函数。 - **森林构造方式**： - 变量 `x` 表示的树。 - 单节点树 `σ(F)`，其中 `σ ∈ Σ`。 - `tag (x)(F)`，`tag (x)` 表示节点 `x` 的标签。 - 森林拼接 `F1, F2`。 - 空森林 `()`。 - **递归调用方式**：可对节点 `x` 或其邻居（`down (x)`、`up (x)`、`left (x)`、`right (x)`）进行递归调用。 - **谓词测试**：包括 `tag (x) = σ` 检查节点标签，`x = y` 检查节点是否相同，`hasDown (x)`、`hasUp (x)`、`hasLeft (x)`、`hasRight (x)` 测试节点是否有相应邻居。 - **函数调用限制**：变量 `x` 必须在与 `f` 相同的块或其周围的块中定义。例如，在 `fun f(x) = let fun g(y) = let fun h(z) = Fh in Fgg′(y′) = Fg′ in Ff` 中，`Fg` 可包含 `g(Up(y))`、`g′(Down(x))`、`h(y)` 和 `f(Up(x))`，但不能包含 `f(y)`。 以下是 RecQL 语言的结构总结： ```plaintext E ::= let fun f1(x) = E1 fun f2(x) = E2 ... fun fn(x) = En in F | F F ::= x | σ(F) | tag (x)(F) | F1, F2 | () | (∗) if P then F1 else F2 | f(x) | f(down (x)) | f(up (x)) | f(left (x)) | f(right (x)) P ::= (tag (x) = σ) | x = y | hasDown (x) | hasUp (x) | hasLeft (x) | hasRight (x) ``` 通过以上对 TreeQL 和 RecQL 两种查询语言的详细介绍，我们可以看到它们在处理半结构化数据时各有特点。TreeQL 适合将关系数据库映射到树结构，而 RecQL 则通过递归函数实现树到树的转换，为半结构化数据的处理提供了不同的解决方案。在实际应用中，我们可以根据具体的需求选择合适的语言和方法。