数据模式与查询：技术解析与应用探讨

### 数据模式与查询：技术解析与应用探讨 在数据整合与转换的过程中，人们常常只对数据源中的部分数据感兴趣，这部分数据由查询来定义。例如，在整合系统中，一个查询会被拆分成多个组件，推送到各个数据源，只有相应的结果会被转换和整合。这里自然会出现一个问题：如何推导出查询结果的模式，这有助于对检索到的数据进行转换。反之，在数据源上进行查询评估时，利用模式信息可以缩小搜索范围。 #### 半结构化数据查询语言与路径表达式 半结构化数据的查询语言和传统的查询语言一样，有主体和头部。在主体部分，会引入节点变量，通过谓词对其进行操作，并通过边和路径建立它们之间的关系。这里重点讨论广义路径表达式，形式为 `x0 P1 x1 P2 x2 ... Pn xn`，其中 `xi` 是变量名，`Pi` 是正则表达式或路径变量。直观地说，给定一个数据图 `G`，这样的表达式会搜索节点 `v0, ..., vn`，使得 `vi - 1` 和 `vi` 之间的路径（`i = 1 ... n`）与 `Pi` 匹配，且 `v0` 是根节点。确定 `vi` 的可能类型，有助于确定查询结果的模式和缩小搜索范围。 形式上，考虑路径表达式 `P = x0 R1 x1 ... Rn xn`，其中 `xi` 是不同的变量名，`Ri` 是关于 `P` 中谓词的正则表达式。给定数据图 `G` 和路径 `p = u0 → u1 → ... → uk`，其中 `ui` 的标签是 `li`（`i = 0, ..., k`），当且仅当 `Ri` 定义的语言包含一个单词 `w = p0 ... pk`，且对于所有 `i = 0, ..., k`，`pi(li)` 成立时，我们说 `p` 与 `Ri` 匹配。如果数据图 `G` 中位于一条路径上的节点 `v0, v1, ..., vn` 满足广义路径表达式 `P = x0 R1 x1 ... Rn xn`，其中 `v0` 是根节点，并且对于所有 `i = 1 ... n`，存在从 `vi - 1` 到 `vi` 的路径与 `Ri` 匹配。 #### 可能的类型分配 在 `VScmDL` 模式 `S` 中，类型向量 `t0, t1, ..., tn` 分别是 `x0, ..., xn` 的可能类型分配，如果存在一个数据图 `G`，它根据类型分配 `h` 符合 `S`，并且节点 `v0, v1, ..., vn ∈ G` 满足 `P`，使得 `h(vi) = ti`（`i = 0 ... n`）。每个这样的可能类型分配描述了路径表达式某些出现中对象的类型。给定模式 `S` 和广义路径表达式 `P`，我们的目标是找到 `P` 中变量的所有可能类型分配。需要注意的是，答案的规模可能比模式大：如果模式非常宽松，每个变量可能与模式中的大多数类型相关联，因此答案的规模可能达到 `O(|P||S|)`，即与模式规模呈指数关系。所以，在衡量类型计算的复杂度时，除了考虑模式和查询的规模，还应考虑答案的规模。 #### 定理及证明 **定理 4**：给定模式 `S` 和路径表达式 `P`，`P` 中变量的可能类型分配可以在与 `S`、`P` 的规模以及可能类型分配的数量加 1 成多项式时间内计算出来。 **证明（概要）**：为了证明该定理，首先要说明对于 `S` 中的任意两种类型 `t′, t′′` 和任意正则表达式 `Ri`，可以（在多项式时间内）定义一个正则语言，该语言描述了所有从类型为 `t′` 的节点开始，到类型为 `t′′` 的节点结束，并且与 `Ri` 匹配的可能路径。然后利用这些语言来计算可能的类型分配。 #### 类型计算对查询评估的优化作用 接下来，考虑计算查询变量的可能类型如何有助于优化查询评估，即通过缩小搜索空间。 **定义 8**：给定模式 `S`、`S` 中的两种类型 `t′, t′′` 以及关于 `P` 的正则表达式 `R`，如果存在一个数据图 `G`，它根据类型分配 `h` 符合 `S`，并且在 `G` 中有一条路径 `p = v0 → v1 → ... → vn` 与 `R` 匹配，使得 `h(v0) = t′`，`h(vn) = t′′`，并且对于某个 `0 < i < n`，`h(vi) = t`，则称 `S` 中的类型 `t` 相对于 `t′, t′′, R` 是有用的。 **定理 5**：对于任意的 `t′, t′′, R`，相对于 `t′, t′′, P` 的有用类型集合可以在与 `S` 和 `R` 的规模成多项式时间内计算出来。 在计算广义路径表达式 `P` 的每一步中，会持有