引言
　　图数据模型广泛应用于生物信息化 学 结 构语 义 互 联 网以及社交网络等开放 异构领域的数据建模 目 前图 结 构 数据规 模 日 益 增 大 使得大规模图数据管理成为数据库领域研究的重点问题之一 而 路 径 查 询 是 图 数 据管理的基本问题之一 在带标签的图上 通 常 通 过 标 签 对 路径 进 行 约 束 主要约束方法有基于语言的路径约束如 正 则 路径或上下文无关路径约束 即路径上的标签满足正则文法或上下文无关文法 近 年 来标签集路径约束 引 起 了 广泛 的 研 究 兴 趣 对 于 标 签 集 合 给 定 两 个 顶 点 其 是 否 存 在连通路径使得该路径上的标签均属于 如 果 存 在 这 样 的 路径这 两 顶 点 被 称 为 相 通这样的查询称为布尔查询 举例 来 说在 社 交 网 络 中 成员被映射为图顶点成 员 间 关 系 被映射为带标签的边 如父子关系可以将边的标签标为父 子表示该边的两个端点之间是父子关系 给 定 标 签 约 束 集父 子兄 弟姐 妹 如 果 两 个 成 员 和 之间存在一条路径并且该路径的标签都属于 则 可 以 判 断 和 具 有近 血 亲 关 系 这种布尔查询的结果要么是真 要 么 是假
　　从这个例子中不难看出标签集约束可以灵活表达近血亲 关 系但是正则路径或上下文无关路径并不方便表达这种近 血 亲 关 系 其 关 键 是基于语言的路径约束是非常精 细的 约 束像近血亲这样标签集约束需要分拆成语言描述的多个 近 血 亲 类 型 如 父 子兄 弟姐 妹的正则约束表达的是直接 血 亲 关 系 父 子 父 子兄 弟 兄 弟姐 妹 姐 妹表 达 两代之间的近血亲关系 如 此 等 等标签集约束需要将这些正则约束进行逻辑或运算列举 可 见即使是简单标签集约束路径 查 询 问 题 若采用正则表达式或无关文法描述查询路径信息都需要复杂的表达式结构 使得求解变得复杂
　　上述提出的标签集约束路径的布尔查询问题是 给 定 两个顶点和标签集约束 回答这两顶点是否 相 通 而 在 一些 应 用 中往 往 没 有 给 定 顶 点 信 息只 是 给 出 约 束 标 签 集搜 索 相通的所有顶点对 返 回 相通的顶点对集合 这 种集合查询有广泛的应用如顺应互联网而产生的针对网络安全监控的内容监视 监 视 过 程 中 监视方并不能事先获得异常事 件 的 发 生 点 而是通过事先给定的违法以及异常事件集 实时地对网络中的各种信息包括博客微 博日志以及邮件等的公开的信息进行扫描 来获得满足异常事件集的异常信息源点从而达到对潜在异常事件的网络监控 同 样如 今 在 社 交网络中交友的用户不再满足于在自己熟识的交友圈中寻找朋友更多是到互联的社交网中找寻满足用户自己提出的交友条 件如 性 别年 龄同城等的网络成员 沿用上述血亲关系图 来 说血亲关系查询也会有类似的集合查询即 给 出 近 血 亲标签 集 约 束 返回图中所有近血亲关系的成员从 而 获 得 社交网络中成员间的血缘关系
　　当 然集合查询可以直接简化为布尔查询问题的反复迭代如近血亲约束路径的集合查询可以简化为布尔查询 穷 举每对 成 员判 断 他 们 是 否 相 通 这种迭代时间消耗成为应用 障 碍 而 布 尔 查 询 方 面 通常采用生成树结构来压缩存储路 径 传 递 闭 包 这种压缩方法能够有效地处理布尔查询问题因为路径的两个端点是事先给定的 但 是在 集 合 查 询中路径的两个端点没有事先给定 因 此集 合 查 询 需 要 在 压缩结构上进行搜索 导致时间开销增加
　　为 此本文提出标签集约束路径的集合查询问题 拓 展 标签集约束路径的布尔查询 在 解 决 方 法 上 避 开 将 集 合 查 询问题简化为布尔查询 因此避开反复迭代布尔查询 同 时也避 开 两 个 极 端 的 解 决 方 案 要么高计算开销的在线搜索方 法要么高存储开销的物化路径传递闭包方法
　　本文采用高计算开销和高存储开销间的折中方法 技 术的关键是基于生成树的路径压缩结构搜索 相 通 顶 点 对 而这个问题简化为集合上的包含查询即返回所有的路径 其 上的 标 签 被 包 含 最 后在集合包含查询的过程中 应 用 倒排索引进一步压缩存储开销最终提高约束路径集合查询效率 现将本文的贡献描述如下提出标签集约束路径的集合查询问题拓 展 标 签 集 约束路径的布尔查询在基于生成树方法的压缩结构上通过倒排表加快相通顶点对搜索 并能够进一步压缩存储开销针对标签集约束路径的集合查询问题提 出 在 生 成 树压缩 结 构 上 搜 索 相通分枝的两个优化方法 从 而 避 开 将 集合问题简化为布尔查询 并且加快查询效率
　　实验部分实现了生成树算法倒 排 索 引 技 术 以 及 优 化 搜索 算 法并在测试数据集上将本文的方法与 物 化 路 径 传递闭包方法进行对比 测 试 表 明 本文的方法在时间开销与空间开销上都具有优势
　　相关工作
　　路 径 查 询 问 题 有 两 种 简 单 处 理 方 法 采 用等 图 遍 历 算 法 直至搜索到目标顶点为止 物 化 路 径 传 递闭 包回 答 查 询 问 题 这两个极端的方法都存在利弊算 法无 需 消 耗 存 储 空 间 但是时间开销为 在 处理大规模图查询时 时间代价难以忍受 物化路径传递闭包的方法无需在线搜索 但需事先存储全部的路径传递闭包空 间代 价 为 用来处理大图空间的代价过高 目 前许 多 算法 都 介 于 这 两 个 方 法 之 间采用压缩结构压缩路径传递 闭 包压缩的路径通过在线搜索获得 但 上 述 算 法 都 没 有考虑路径中的标签信息传递闭包中存储的路径也只是顶点信 息并不能直接应用到标签图上带有标签约束的路径连通性 问 题 文 献 提出了各自的解决方案文 献 提 出 了标签集约束路径查询问题并给出生成树压缩结构压缩标签图上的路径传递闭包 文 献 中通过重新定义路径距离提出求解标签路径传递闭包的改进算法文 献 提出的算法解决的是路经查询判断性问题如果用来处理集合查询问题 在没有事先给定顶点对的情况下只能先将集合查询简化为布尔查询 再通过穷举迭代列举出满足集合查询条件的所有顶点对 显然大规模图上的穷举会陷 入 困 境 针对路径描述信息的查询目 前 的 解 决 方 法 有 正则路径表达或上下文无关路径表达若 采 用 该 方 法 集 合 查 询问题需要用严格的正则表达式或上下文无关文法表示 而 正则路径查询能够 精 细地描述路径信息 也 是 问 题从而不能有效解决 灵 活的标签集约束集合查询问题因 此本文利用生成树压缩传递闭包并用倒排索引加快集 合 查 询 第 节 进 行 问 题 定 义 并给出解决集合查询的两个 基 本 方 法 第 节提出倒排索引以及优化算法第 节 通 过实验验证算法效率 最后进行总结与展望问题定义带标签的有向图 可以表示成四元组 其中 分 别 为 图 的 顶 点 集边 集 和 标 签 集 映 射表 示 对 边 加 上 标 签 其 中 图 中 一 条 从 到的 路 径 是一系列的点边相间隔的序列 即表 示 路 径 的 标 签 集 合 即定 义 标签集约束路径查询 在带标签的有向图中给 定 顶 点 以及约束标签集 如果 和 存 在 一 条 路 径 使 得 则 和 是 相 通的记 为定 义 标签集约束路径的集合查询 在 带 标 签 的 有 向图 中给定约束标签集 返 回 所 有 相 通 的 顶 点 对 查 询结 果 表 示 为全 文 采 用 图 作 为 示 例 用 图 下 面 给 出 图 上 标 签 集 约束路径查询和标签集约束路径集合查询实例 给 定 约 束 标 签集 以 及 顶 点 和 可 知对于标签集约束路径集合查询有 如 下 点 对 相 通所 以 标 签 集 约束路径的集合查询结果为图 例 图下面两节分别介绍解决标签集约束路径集合查询的两种不 同 方 法 其 中 节 给 出 算 法 节 给 出 标 签路径传递闭包存储的方法基于图遍历的集合查询标签集约束路径集合查询可通过图遍历方法求解图 遍历 方 法 中 又 以 方 法 最 为 常 见 下 面 以 为 例 描述集合求解问题从图中任意顶点 开 始以 方 法 搜 索 能 够 约 束可达的所有顶点 搜 索 结 果 构 成 一 个 连 通 分 枝 从 图 中 删去 由 导 出 的 连 通 分 枝 的 边 重 复 操 作直 至 图 中 没有 连 通 分 枝 该 算 法 的 时 间 复 杂 度 为 面 对 大 规模 图 数 据 时 会导致计算时间代价过高基于传递闭包的集合查询另一种方法是事先计算出图中所有顶点对的连通路径标签 信 息从而得到标签路径传递闭包存 储 开 销 为 同 样 在 遇 到 图 数据 很 大 时存储开销难以忍受目 前解决标签集约束路径查询问题的文献 中 提到全 部 的 中存在大量冗余信息 举 例 来 说图 中 的点 对 有 两 条 路 径 相 应 标 签 集 为对于任意给定的 如 果 必 然 有 路 径标签 信 息 完 全 能 够 回 答 的 约 束 查 询 问 题 下 面 给 出用以减少冗余路径标签信息的相关定义定义 完备路径标签集 设 为 点 对 之 间 的 路 径标 签 集 的 集 合 如 果 满足这样的条件 对于任意给定的标签 集 合 有 当 且 仅 当 中 存 在 一 个 路 径 标 签则 称 这 样 的 为 点 对 的完备路径标签集合点对之间的所有可达的路径标签集合当然是一个完备路径 标 签 集 合 但 没 有 减 少 任 何 冗 余 如 果 的元素有如下性质 不 存 在 或 者 则 称 之 为 最 小 完 备路 径 标 签 集 合 记 为 且所有点对的最小完备路径标签 集 合 记 为 目 前求 解 的算法的时间复杂度为空 间 复 杂 度 为索引和集合查询对 给 定 图 上 求 解 出 的 在进行集合查询时需 要 依 次搜索点对的路径信息 并进行包含关系判断 穷 搜 的 方 法 还 是不 能 加 快 查 询 为 此本文首先研究在 上建立倒排索引随后在考虑到树状压缩结构时对因无法压缩而必须存储的路径信息采用与 上相同的索引方法上的倒排索引结构倒 排 索 引 记 为 构 建 过 程 为 中的元素为标签集合对每一个标签集建立一个反向索引指向所有能够通过该标签集合相通的点对 索引项数总量为表 给 出 了 图 的 部分内容以作参考表 的 倒 排 表标 签 集 顶 点 对接下来通过对 与 之 间 压 缩 量 的 分 析 研 究进 一 步阐述倒排索 引 的 压 缩 优 势 已 知从 到 增 量 记 为引 理图 中 于是 有因 为 图 的 远 小 于 顶点对中的路径标签集重复的比较多 所以 较大 极端情 况 下当 即每条边上的标签都不重复时会 得 到倒排索引结构上的集合查询由 定 义 可 知如 果 点 对 路 径 标 签 集 被 给 定 标 签 集 包含则 该 顶 点 对 相 通 同 样在标签集约束集合查询问题中仍需满足该性质 根 据 这 一 性 质 给 出 引 理 描 述 利 用 倒排索引技术求解集合查询的过程引 理 给 定 约 束 标 签 集 路径的集合查询的解空间组 成 为可 以 看 出搜索倒排表中用到集合包含关系判断这 与 一般的集合包含关系查询类似可以应用已有的集合属性索引的方法来加快查询优 化基于 上的倒排索引技术 虽然压缩了冗余的路径标签信 息但 是 查 询 时 间 代 价 还 是 过 高 本节利用树状结构优化存储并 利 用 上的倒排技术处理因不能被压缩而被存储下来的剩余路径标签信息同时证明在树状结构下的倒排索引技术具有良好的压缩优势虽然 为标签图路径信息的最小完备路径标签集 但 是对于规模很大的图来说 的存储开销还是很大 文 献中利用生成树结构进一步压缩 将 转化为树上连通关系和 非 树 上 的 连 通 关 系 本 文 在 此 压 缩 结 构 基 础 上 利用上节的倒排技术对 表建立倒排索引 记 为 图的 表 对 应 的 如 表 所 列表 示 例 图 倒 排 表中 标 签 集 顶 点 对简 略 介 绍 的 生 成 过 程 为图中每条边赋予权值记 为表示集合笛卡尔乘积 利用生成树算法求得权值最大的生成树其值 记 为 得 到 后获 得 的 过 程描述 如 下 中存在一条路径 中 存 在 一 条路 径 使 得 则 从 表 中 的中删除该路径的标签信息依 次 操 作 直 至 不 能 再 删除标签信息为止 即 得 到 图 为例图的生成树图 例 图 的 生 成 树将 中 因 被 压 缩 的 路 径 标 签 用 来 表 示 本 文 研究 发 现 和 并 不 相 等 举 例 来 说 如 图 所 示边为 中 的 边假 设 则和 中存在路径标签 其 可 以 由和 分 别 加 上 边 中 的 标 签 恢 复出 但 是 中 存 在 一 条 路 径 它 的 始 边 经 过 可由 中的一条路径标签加上 的 标 签 得 到 但是生 成 过程中这一路径标签并没有删除 这 是 因为 计算的是路径中终边在树上的路径标签 而 此 例 中 的该条路径恰恰是始边在树上 同 时路径中存在连续多条边存 在 于 上的路径也没有被算在 中 于 是得 到 下 面 的引 理图 末 端 在 中 展 开引 理由 引 理 可 以 看 出 中存储的少量边能够带来超过的 压 缩 量 基 于 引 理 引 理 可 以 得 到同 时 中存储的边和标签又不会超过 进 一 步得 到如 下 定 理定理证明对于最左边的小于式 由 引 理 得 到对 于 可 将 它 分 为 和即 再 由 引 理从而进一步能够得到所以于是有 由 引 理 我 们 得 到所 以 有于 是得 到 同 理有 得 到 而定 理 得 证定 理 说 明 上的倒排索引能够进一步增加压缩存储 量 下 面 通 过 定 理 给出集合查询解的构成定 理使 得 其 中并 且则 为集合查询的解之一由 定 理 可 知在树状压缩结构之下求解标签集约束路径集 合 查 询 时 分 别 到 与 中搜索获得满足标签集限制的 部 分 解余下的解需要通过 与 连 接 而 得 对 于 例图给 定 标 签 集 从 中得到的解如下中 的 解 如 图 中加粗部分所示 与 连 接 的 解如 图 中虚线连接所示图 标 签 集 的 树 中 求 解而由标签集约束路径查询问题可知 只 有 在 获 知 源 点 信息 的 情 况 下 才 能 到 中 去 搜 索 但 是本文的集合查询问题并没有获知任何的源点信息所 以 需 要 来 给 出 的 解 并 不能用已有的方法轻易获得 下 面 重 点 讨 论 中 求 解记 为 中 能 够 连 通 的 分 枝 本文给出两种求解的 方 法分 别 为 和 建 立 的 倒 排 表得 到 连 通 的 顶 点 对 即 通 过 一 条 边 相 通 的 顶 点 对 得到 的 结 果 记 为 对 表 进 行 自 连 接 通 过 对 中 的 节点 区 间 标 号 将自连接得到的解中满足祖先关系的顶点对做适 当 的 删 除 深 度 优 先 遍 历 从 根 节 点 开 始 将 每 一 步遍历到的节点都存入栈中对 于 满 足 连 通 的 节 点 将 其 所在分枝的最大连通路径存入结果中 区间标记的具体技术参见 文 献 具 体 应 用 可 参 见 文 献 中 提 及 的 查 找 的 方法算 法 描 述 如 下先 序 遍 历 并进行区间标记 记 为搜 索 得 到连 通 与 进 行 连 接得 到 连 通 的 解利 用 区 间 标 记 删 除 中互相包含的顶点对算 法 描 述 如 下深 度 优 先 遍 历 遍历的同时将节点存入栈中遍 历 过 程 中 将 满 足 连通的分枝存入结果中堆 栈 中 的 元 素 利 用 递 归 算 法 即不断地调用上述深度优先遍历算法即 重 复 步 骤 至 直 至 栈 为 空其中 的主要计算代价是不断地进行连接而 需要栈来存储需递归处理的子树 栈的空间代价为我们将通过实验来比较二者的求解效率实验本节通过实验验证标签集约束路径的集合查询问题 分别在真实数据集和人造数据集上均 来 自 文 献 提 供 的 数 据集测 试 实验通过存储开销和时间开销两方面 对 传递 闭 包 存 储 以及生成树方法进 行 对 比 测 试 实验编写语言为 并 在上 测 试 测 试 用 的 主 机 为内 存 为存 储 代 价 对 比实 验 中因 方法未涉及到传递闭包存储所 以 只 考察传递闭包和生成树方法的存储代价 而 和 也 只在查询时间上存在差异存储上不做比较 本 节 树 中 搜 索 算法 均 采 用 传 递 闭 包 存 储 的 方 法 中 生成的传递闭包为 主 要 存 储 代 价 而生成树方法中 和 为 主 要 存 储 代价在人造数据集上 分别通过改变图的密度以及规模来 观察上述两种方法的存储开销变化参数变化情况如下固 定 以 及 的 大 小其 中 设 置 为 改变图 的 密 度使 得 从 到 之 间 变 化 分 别 观 察传 和 的 存 储 开 销固 定 的大小以及密度 的 情 况 下 其中 设 置 为 改 变 的 大 小使 得 从 到变 化分 别 观 察 传 和 的 存 储 开 销图 图密度对存储开销的影响 图 图 顶 点 数 对 存 储 开 销的 影 响从 图 图 中 可 以 看 出 图密度和顶点数的变化使得和 的存储开销均增大 但 相 对 增 长 较 缓 慢 相同 条 件 下 的存储开销少于时 间 代 价 对 比本节 实 验 中 给 出 和 在 图 密 度 以 及 图 规 模改变的情况下查询时间代价的对比 首先在人造数据集上测试 对 比固 定 以 及 密 度 的 情 况 下改变 的 大 小 从 占 整 个 的 到 变 化分 别 观察 和 的 存 储 开 销固定 以及 的大小改变图的密度使得从 到 之 间 变 化 分 别 观 察 和 的 存 储开 销表 标签数对查询时间 的 影 响表 图密度对查询时间 的 影 响从 表 表 中 可 以 看 出 查询时间逐渐增大 也随 之 逐 渐 增 大 在 相 同 条 件 下 的 查 询 时 间 仍 低 于同 样 优 于在 真 实 数 据 集 和 上通 过 的 改 变 来 测试上 述 种方法的完成查询的时间开销对 和 的处 理 参 照 文 献 数据中抽取出的图的节点为密 度 为 标 签 数 为 所 以 该 实 验 数 据 中 设 置 从 变化 到 观察查询时间的变化 上 抽 取 的 图 有 个 节点标 签 数 为 图 密 度 为 实 验 中 从 改 变 到 进行 测 验由图 图 可 以 看 出 标签集约束路径集合查询 随 着的增大 的查询时间逐渐增大 无 明 显 增 大 并 且容易看出 方法比 的 要 快 两 倍 和 之 间逐渐增大 比 快这与人造集上的测试结果一致图 数 据 集 对 查 询时 间 的 影 响图 数 据 集 上 对 查询 时 间 的 影 响
　　结 束 语
　　本文在标签集约束路径查询问题的基础上 提出标签集约束路径集合查询问题 给出求解的生成树压缩存储结构与倒排索引技术 同 时理论证明倒排索引存在良好的 压 缩 效 益 给出两个优化算法解决树结构上无源点信息的集合 查 询 问 题 实 验 证 明在 大 规 模 图 上 生 成 树 方 法 与 在 线的 和预存储标签路径传递闭包相比在时间和空间开销上都 有 优 势 下 一 步在本文的基础上 继续研究如何改进压缩路径标签的存储结构以及查询集合包含关系的算法 以 进一步减少时间和空间开销