路径表达式的索引结构

### 路径表达式的索引结构 #### 1. 引言 近年来，人们对管理不符合传统数据模型（如关系型或面向对象模型）的数据的兴趣日益浓厚。数据不符合传统模型的原因多种多样。一方面，数据在物理层面可能不符合，比如它可能以数据交换格式存储、从网络获取或存储为结构化文件；另一方面，在逻辑层面也可能不符合，例如数据可能存在缺失属性、不同数据项中的某些属性类型不同、存在异构集合，或者模式过于复杂或变化频繁。这类数据被称为半结构化数据，其数据模型由一个边带标签的图表示，其中节点对应对象，边对应属性或值。 关系型数据库传统上使用关联查询，根据某些属性的值检索元组。为了高效回答此类查询，数据库管理系统支持将属性值转换为元组 ID 的索引（如 B 树或哈希表）。在面向对象数据库中，路径查询取代了简单的关联查询，并且已经提出了几种数据结构来高效回答路径查询，如访问支持关系和路径索引。 对于半结构化数据，查询更为复杂，因为它们可能包含正则路径表达式。这种额外的灵活性是为了遍历结构不规则或用户部分未知的数据。例如，以下查询检索所有晚餐供应千层面的餐厅： ```sql select x from (∗.Restaurant) x (Menu.∗.Dinner.∗.Lasagna) y ``` 该查询从数据库 DB 的根开始，搜索满足正则表达式 `∗.Restaurant` 的路径，然后从检索到的节点 `x` 开始，搜索另一个正则表达式 `Menu.∗.Dinner.∗.Lasagna`。 对这类查询进行简单的全数据库扫描评估显然成本很高。与关系型和面向对象数据库一样，我们希望使用一些索引来加速评估。然而，为传统数据模型开发的索引结构依赖于预定义的模式，因此不适用于半结构化数据，因为这里没有可用的模式。全文索引系统则采取了相反的方法，在对信息结构一无所知的情况下对所有数据进行索引，但这对半结构化数据的作用有限，因为半结构化数据可能有一些（可能非常有限）结构知识可用于路径表达式。 近期的工作主要集中在推导和使用模式信息来重写查询和指导搜索，而几乎忽略了索引问题。一个例外是数据指南，它记录数据库中现有路径的信息并用作索引，但它仅限于单个正则表达式，在处理包含多个正则表达式的复杂查询时并不实用。 本文提出了一种新颖的、通用的半结构化数据库索引结构，称为模板索引（T - 索引）。它在多个方面优于以前的方法： - **空间与通用性的权衡**：T - 索引允许我们在空间和通用性之间进行权衡。与给定 T - 索引关联的路径类由路径模板指定。例如，可以构建一个 T - 索引来评估由模板 `P x P y` 描述的路径，这里 `P` 可以用任何正则表达式替换；另一个例子是 `(∗.Restaurant) x P y`，其中第一个正则表达式固定为 `∗.Restaurant`，这种 T - 索引占用空间较少但通用性较低。 - **高效构建**：T - 索引可以高效构建。数据指南需要对底层数据库进行幂集构造，最坏情况下成本可能呈指数级；而 T - 索引依赖于模拟或双模拟关系的计算，有高效的算法。 - **大小保证**：与单个正则表达式关联的 T - 索引的大小最多与数据库的大小呈线性关系，而数据指南在最坏情况下可能呈指数级。 - **优雅的泛化**：T - 索引是以前在各种上下文中考虑的索引结构的优雅泛化，包括半结构化数据的数据指南、全文索引的 Pat 树和面向对象数据库的访问支持关系。 我们的技术是将数据库对象分组到等价类中，这些等价类包含相对于由路径模板定义的一类路径不可区分的对象。计算这种等价关系可能成本高昂，因此我们考虑由双模拟或模拟定义的更细粒度的等价类，它们可以高效计算。T - 索引由这些等价类构建而成，通过构造一个非确定性自动机，其状态表示等价类，转换对应于这些类中对象之间的边。 每个 T - 索引是为特定类的查询（由一个模板给出）设计的，但它也可以用于回答更通用形式的查询。我们解决了确定给定的带正则路径表达式的查询是否可以重写以利用给定 T - 索引的问题。 #### 2. 回顾：数据模型和查询语言 - **数据模型**：半结构化数据被建模为一个带标签的图，其中节点对应数据库中的对象，边对应它们的属性。假设存在一个无限的数据值集合 `D` 和一个无限的节点集合 `N`。 - **定义 1**：数据图 `DB = (V, E, R)` 是一个带标签的有根图，其中 `V ⊂ N` 是有限的节点集合，`E ⊆ V × D × V` 是带标签的边集合，`R ⊆ V` 是根节点集合。不失一般性，假设 `V` 中的所有节点都可以从 `R` 中的某个根节点到达。 - **路径表达式**：假设存在一组基于数据值集合 `D` 的基本谓词 `p1, p2...`，用 `F` 表示这些谓词的布尔组合集合。定义正则路径表达式 `P` 如下： ```plaintext P ::= ∅ | ϵ | f | (P|P) | (P.P) | P∗ ``` 用 `L(P)` 表示由 `P` 定义的正则语言，用 `W(P)` 表示 `D∗` 中所有满足以下条件的单词 `w = a1 ... an` 的集合：存在一个单词 `w′ = f1 ... fn ∈ L(P)`，并且对于所有 `i = 1 ... n`，`fi(ai)` 成立。给定一个数据图 `DB` 和一条路径 `p = v0 a1 → v1 a2 → v2 ... vn−1 an → vn`，如果单词 `a1 ... an` 在 `W(P)` 中，则称路径 `p` 匹配路径表达式 `P`。 - **查询**：查询路径是形式为 `P1 x1 P2 x2 ... Pn xn` 的表达式，其中 `xi` 是不同的变量名，`Pi` 是路径表达式。给定一个图数据库 `DB = (V, E, R)`，如果节点 `v0, v1, ..., vn` 满足查询路径