半结构化数据查询、约束及元数据集成方案解析

# 半结构化数据查询、约束及元数据集成方案解析 ## 1. 半结构化数据模型基础 在现代信息系统中，处理结构不像传统数据库那样严格的数据的能力至关重要，在生物数据库、数字图书馆和数据集成等众多领域都有重要应用。近期提出的半结构化数据模型通常将数据表示为带标签边的图，图中同时保留了数据的值和模式信息。 这里以 bdfs 数据模型为基础，该模型用图来表示数据库的部分内容（称为基础图）和模式。基础图的边用数据标签，模式的边用可判定且完备的一阶理论 T 在固定有限宇宙 U 上的公式标签。基础图是根连接图，其边用 (self = a) 形式的公式标签；图模式也是根连接图，其边用 T 的一元公式标签，基础图是图模式的特殊情况。半结构化数据库是有限的图集合，每个图可以是基础图或图模式。 基础图 g 符合模式 S 的概念通过图之间的模拟关系来定义。给定基础图 g 和模式 S，从 g 到 S 的模拟是 g 的节点到 S 的节点的二元关系 ，如果 u  u′，则对于 g 中的每条边 u a→v，在 S 中存在边 u′ p→v′，使得 T |= p(a) 且 v  v′。若存在从 g 到 S 的模拟，且 root(g)  root(S)，则称基础图 g 符合模式 S，记为 g ⪯S。模拟的概念比通常的满足概念更灵活，能更好地处理不太严格的数据结构。 对于数据管理的一些任务，检查两个模式之间的包含关系很重要，即检查符合一个模式的每个基础图是否总是符合另一个模式。给定两个模式 S 和 S′，若对于每个基础图 g，g ⪯S 意味着 g ⪯S′，则称 S′ 包含 S，记为 S ⊑S′。若 S ⊑S′ 且 S′ ⊑S，则 S′ 和 S 等价。在相关文献中，提出了一种检查包含关系（和符合关系，因为基础图是模式的特殊情况）的算法，该算法本质上是寻找两个模式节点之间的最大模拟，并且相对于两个模式的大小，其时间复杂度为多项式。 ## 2. 带约束的模式 为了在模式中表达约束，对 bdfs 数据模型进行了扩展。将模式 S 的约束看作与模式节点 u 关联的公式，该公式用某种语言 L 表达，其作用是对于符合 S 的每个基础图 g，g 中模拟 u 的每个节点都必须满足该条件。 带有 L - 约束的模式（简称 L - 模式）是每个节点 u 都用约束语言 L 的公式 C(u) 标签的模式。给定基础图 g 和 L - 模式 S，从 g 到 S 的模拟是 g 的节点到 S 的节点的二元关系 ，若 u  u′，则 (1) u 满足 C(u′)；(2) 对于 g 中的每条边 u a→v，在 S 中存在边 u′ p→v′，使得 T |= p(a) 且 v  v′。除了模拟的新定义外，符合、包含和等价的概念保持不变。假设 L 包含公式 ⊤，它被每个基础图的每个节点满足，因此可以将基础图 g 视为 L - 模式，其中 g 的每个节点 u 的 C(u) = ⊤，这样符合关系再次成为包含关系的特殊情况。 由于约束可能相互矛盾，或者与图的结构不兼容，一致性的概念变得很重要（注意基础图总是一致的）。给定 L - 模式 S，若存在至少一个基础图符合 S′（S′ 与 S 相同，只是 root(S′) = u），则节点 u ∈Nodes(S) 是一致的；若 root(S) 是一致的，则 S 是一致的。此外，若没有基础图同时符合两个 L - 模式 S1 和 S2，则称它们是不相交的。 一般来说，向模式添加约束会导致推理的难解性。这里考虑一种语言 Ll，它允许表达有趣形式的约束，并且推理仍然是可处理的。主要是只允许表达局部约束，即对直接从节点发出的边的约束。Ll 中的公式语法如下（γ, γ1 和 γ2 表示约束，p 表示 T 的公式）： γ ::= ⊤ | ∃edge (p) | ¬∃edge (p) | ∃≤1edge (p) | γ1 ∧γ2 直观地说，节点 u 上形式为 ∃edge (p) 的约束（称为边存在约束）要求 u 至少有一条出边 u a→v，使得 T |= p(a)；形式为 ∃≤1edge (p) 的约束（称为功能性约束）要求 u 最多有一条这样的出边。 主要结果是，带有局部约束的模式的推理可以在多项式时间内完成： 1. 设计了一种检查 Ll - 模式 S 是否一致的算法。该算法基于一个函数，该函数首先移除不存在约束，然后从 S 中移除所有不一致的节点，该函数的运行时间相对于 S 的大小是多项式的。 2. 扩展了相关文献中的算法以处理局部约束。算法的基本思想是通过构造两个节点集的笛卡尔积作为关系 R，然后从 R 中移除不满足上述条件 (2) 的所有对 (u, u′)，以寻找两个模式之间的模拟。该算法相对于两个 Ll - 模式的大小的运行时间为多项式。 3. 展示了该技术还可以用于在多项式时间内执行以下两个任务：计算两个 Ll - 模式的最小上界（LUB），以及检查两个 Ll - 模式是否不相交。 以下是处理 Ll - 模式相关任务的流程： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B{选择任务}:::decision B -->|检查一致性| C(移除不存在约束):::process C --> D(移除不一致节点):::process D --> E{是否一致?}:::decision E -->|是| F([一致]):::startend E -->|否| G([不一致]):::startend B -->|检查包含关系| H(构造关系 R):::process H --> I(移除不满足条件的对):::process I --> J(确定包含关系):::process J --> K([完成]):::startend B -->|计算 LUB| L(执行 LUB 计算):::process L --> M([完成]):::startend B -->|检查不相交性| N(执行不相交性检查):::process N --> O([完成]):::startend ``` ## 3. 图选择查询 半结构化数据的查询语言通常由两部分组成：一部分用于选择图，另一部分用于重构所选图以产生实际答案。这里引入了一种基本形式的查询，称为图选择查询（gs - 查询），它只处理选择部分。gs - 查询语言可以表达图的复杂不动点属性，并且经过精心设计，使一些有趣的推理任务（如检查查询可满足性、检查查询之间的包含或不相交性以及比较查询和模式）是可判定的。 gs - 查询检索的单位是图，但无法进一步操作检索图中的特定数据，因此该语言不能被视为完整的查询语言，而应被