基于模式映射的并行关系数据图构建方法GraphCon及其性能评估

《IEEE Transactions on Big Data》：GraphCon: A Parallel Graph Construction from Relational Data

为解决将大规模关系数据高效、准确地转换为属性图的挑战，本研究提出了一种基于模式映射的图构建方法GraphCon。该方法通过优化连接操作（InstanceJoin）来提升关系实例聚合的效率，并设计了并行算法、数据分区及负载均衡策略以增强可扩展性。实验基于TPC-H基准和真实数据集验证了GraphCon在效率和可扩展性方面的优势。这项工作为利用图算法进行关系数据分析提供了更高效的转化框架。

　　

在现实世界的应用中，海量信息丰富的数据通常以结构化形式存储在关系数据库中。为了分析关系数据中蕴含的实体及其相互关联的丰富信息，由于图算法的效率优势，从业者越来越倾向于将关系数据转换为图并利用图分析方法，而不是依赖直接的关系数据分析。然而，将关系数据转化为图以实现结构化知识分析时，这些元素（实体和关系）通常分散在多个关系表中。聚合它们通常需要复杂的连接操作，这在计算上是密集且耗时的，特别是在处理大规模数据时。顺序处理由于在节点构建过程中需要重复连接，进一步加剧了低效率问题。并行转换虽然提供了可扩展性，但确保可靠性（例如避免重复和保持数据完整性）仍然是一个关键挑战。因此，需要一个有效且可靠的框架来从关系数据中大规模构建图。

为解决上述问题，研究人员开展了一项名为“GraphCon: A Parallel Graph Construction from Relational Data”的研究，提出了一种模式驱动的图构建方法。该方法旨在克服传统方法在聚合跨表实例时的性能开销问题，并实现大规模数据的高效、并行转换。论文发表在《IEEE Transactions on Big Data》期刊上。

研究团队主要采用了几个关键技术方法：首先，提出了一种基于模式映射的机制，实现图模式与关系模式之间的等效映射。其次，优化了图构建过程中的复杂连接策略，即InstanceJoin，用于高效聚合关系实例。此外，为了处理大规模数据，引入了包含基于图模式的数据分区策略和负载均衡策略的并行算法，以提升可扩展性。

研究结果

3.1 基于实体的模式映射

与传统依赖外键生成边的模式方法不同，GraphCon根据图模式S建立关系，实现了模式映射M： (A, R_i)?(A′, V_S)，将关系表中的属性映射到图模式中的实体属性，并基于实体进行多表连接，减少了传统关系驱动方法的计算成本。

3.2 顺序图构建

顺序图构建算法seGraphCon包括节点构建和边构建两个主要阶段。节点构建阶段通过分区和InstanceJoin模块聚合实例以生成图节点；边构建阶段则基于索引标识符创建节点间的边。算法首先为实例分配标识符Ind，然后按图模式中的实体集进行分区。对于每个实体类型V∈V_S，采用InstanceJoin从相关分区集中聚合属性元组，生成节点并更新图G。最后，基于匹配的标识符和预定义的边类型创建边，最终形成属性图G。

3.2 (3) 节点构建

seGraphCon首先根据预定义的图模式实体集V_S对关系实例进行分区。每个分区可视为V_S中实体的关系实例集。受最坏情况最优连接技术在查询处理中高效性的启发，seGraphCon对每个关系实例集应用基于WCOJ的关系实例聚合方法（称为InstanceJoin）。该方法仅在外键上执行外连接，并使用基于超图的遍历来跨分区匹配属性值，通过递归探索非重复值集来增量生成实例元组，确保一致性同时高效处理不完整匹配。

3.2 (4) 基于索引的边构建

节点生成后，seGraphCon使用索引标识符Ind = R.rowId提取关系。对于一个关系R_j中的值元组(a₁, a₂, …, a_i)，其Ind相应定义。如果v_i.Ind ∧ v_j.Ind ≠ ?，则认为两个节点v_i和v_j匹配。在边构建过程中，每个聚合的元组用Ind更新其节点，并在具有匹配标识符的节点之间创建边。所有生成的节点和边被增量添加到图G中。

4. 并行图构建

为应对大规模数据集，研究提出了并行图构建算法parGraphCon。该算法采用主处理器P₀进行图构建，一组处理器P₁, P₂, …, P_n执行连接操作。其核心包括数据分区策略和工作负载平衡策略。数据分区策略根据实体构建成本（如涉及连接的属性数量c_attr(v_s)、候选实例集基数ins_card(v_s)和数据行数ins_cost(v_s)）将实例分配给处理器。工作负载平衡策略通过计算处理器S_i的倾斜度（S_i= cost(W_i)/avg_t∈[1,p]cost(W_t)）来识别和重新分配负载过重的分区，确保并行计算的可扩展性。算法计算每个实体的成本，根据成本及其与关系模式的关系将实体分配给处理器。初始分组后，重新计算成本，并对高工作负载的分区进行进一步划分以实现负载平衡。处理器随后获取数据并通过类似于seGraphCon的连接操作执行实例聚合。在时间间隔t内，工作负载平衡过程迭代进行，直到所有处理器完成聚合。每个处理器输出其节点v，发送到主处理器进行边连接和最终的图构建。

结论与重要意义

本研究提出了一种名为GraphCon的新型模式化图构建方法，用于将关系数据转换为属性图。与传统的基于模式的方法相比，GraphCon在关系实例聚合过程中利用了特定的复杂连接操作来提高图构建的效率；与基于查询的方法不同，它将整个关系实例转换为属性图，并采用最坏情况最优连接策略进行实例聚合。此外，研究还提出了一个专门为将大规模关系数据集转换为属性图而设计的并行框架，该框架结合了负载平衡和数据分区策略。

实验使用TPC-H基准和真实数据集验证了所提方法的效率和可扩展性。研究发现，平均而言，GraphCon映射框架在图构建方面是高效的，比现有方法快10%；其并行方法性能更好，当使用的处理器数量从2个变为8个时，速度提升了一倍。

这项工作的重要意义在于：它系统性地解决了从关系数据到图结构转换中的两个核心瓶颈——多表实例聚合的效率问题和大规模数据的可扩展性问题。通过创新的InstanceJoin策略和并行化设计，GraphCon能够更快速、更可靠地构建出可用于图分析的结构化知识图谱，为商业智能、推荐系统等依赖图分析的应用场景提供了强大的底层技术支持。其提出的成本模型和负载均衡机制也为后续大规模图数据处理系统的优化提供了有价值的参考。