一种基于局部重计算的动态图数据库增量构建与索引更新方法与流程

本发明数据库，具体涉及一种基于局部重计算的动态图数据库增量构建与索引更新方法。

背景技术：

1、动态图数据库是一种用于存储和查询图结构数据的数据库系统，其中图结构由节点和连接节点的边构成，随着时间推移，动态图数据库持续接收新增数据，需要对已有图谱进行更新，在动态图数据库的实际应用中，新增数据不断到达，图谱结构持续演化，增量更新是动态图数据库的核心操作之一。

2、在动态图数据库中，节点嵌入向量是图神经网络等算法进行图计算的基础输入，当图谱发生增量更新时，新增节点和边会改变图谱的拓扑结构，受影响节点的嵌入向量需要重新计算以反映更新后的图结构信息。现有动态图数据库的增量更新方法主要采用以下技术路径：

3、一种现有方法是在每次增量更新时对全图重新执行嵌入向量计算，该方法将新增数据与已有图谱合并后，对整个图谱的所有节点重新进行嵌入向量的计算。然而，全量重计算方法存在计算开销大的问题，随着图谱规模的持续增长，全量重计算所需的时间成本和计算资源呈线性增长，在大型动态图数据库中，频繁的全量重计算导致增量更新的实时性难以保证；

4、另一种现有方法是将图谱按时间窗口切分为多个快照，在每个时间窗口内对全图执行一次嵌入向量计算，该方法通过降低更新频率来减少计算次数，但牺牲了增量更新的实时性，在两个快照之间的时间窗口内，新增数据无法及时反映到节点的嵌入向量中，导致图谱数据与嵌入向量之间存在滞后；

5、在向量索引维护方面，动态图数据库通常采用基于图的向量索引结构来加速向量相似度检索，现有向量索引大多针对静态数据场景设计，索引构建完成后不支持数据更新。当图谱中节点的嵌入向量发生更新时，需要对整个向量索引进行重建。全量索引重建需要遍历全部节点的嵌入向量并重新构建索引结构，导致索引更新延迟高、输入输出开销大。有研究指出，在百万级顶点环境下，全量索引重建的时间可达小时级。部分现有方案采用周期性全量重建的策略，即在累积一定数量的更新后统一执行一次索引重建，但该方法在两次重建之间索引数据与图谱数据不一致，查询结果的准确性无法保证；

6、在查询缓存维护方面，动态图数据库通常设置查询缓存区以加速高频查询请求的响应。当图谱发生增量更新后，缓存中涉及已更新节点的查询结果将失效。现有方法在检测到图谱更新后，通常采用全量缓存刷新策略，即清空全部缓存条目并在后续查询中逐步重建。全量缓存刷新导致缓存命中率在刷新后急剧下降，大量查询请求需要重新执行完整的向量检索和图遍历操作，查询响应延迟显著增加；

7、综上，现有动态图数据库在增量更新过程中存在全量嵌入向量重计算导致计算开销大、更新实时性差；全量向量索引重建导致索引维护成本高、更新延迟大；全量缓存刷新导致缓存命中率下降、查询响应延迟增加。上述问题均源于现有方法在增量更新时采用全量处理策略，未能根据图更新的实际影响范围进行局部化处理。该领域亟需一种能够识别增量更新实际影响范围并仅对受影响区域执行局部更新的技术方案，降低动态图数据库增量更新过程中的计算开销、索引维护开销和缓存刷新开销，提高动态图数据库的增量更新效率、索引一致性及查询响应速度。

技术实现思路

1、为了克服上述现有技术的问题，本发明公开一种基于局部重计算的动态图数据库增量构建与索引更新方法。

2、为解决上述技术问题，本发明的技术方案如下：

3、第一方面提供一种基于局部重计算的动态图数据库增量构建与索引更新方法，包括以下步骤：

4、s1，采集新增数据，新增数据包括应用程序编程接口的结构化描述数据、系统配置文件数据和操作日志数据；

5、对新增数据进行实体抽取及关系抽取，生成增量实体集合和增量关系集合；

6、将增量实体集合和增量关系集合按照时间戳写入动态图数据库的增量缓存区；

7、s2，比较增量实体集合中的各实体与动态图数据库中已有图谱的节点，确定匹配节点和未匹配节点；

8、以未匹配节点及增量关系集合中涉及的关联边为中心，在已有图谱中沿边向外扩展预设跳数，将扩展所覆盖的子图区域确定为受影响子图；

9、s3，保持已有图谱中位于受影响子图之外的节点的嵌入向量不变；

10、对受影响子图内的未匹配节点，执行节点嵌入计算生成初始嵌入向量；

11、将初始嵌入向量沿受影响子图的边向邻域节点进行传播，更新受影响子图内各节点的嵌入向量；

12、s4，根据更新后的嵌入向量，对动态图数据库中与受影响子图对应的向量索引执行局部更新；

13、s5，将更新后的嵌入向量及更新后的向量索引写入动态图数据库，完成增量构建。

14、优选地，步骤s2中预设跳数为2跳。

15、优选地，步骤s2中以未匹配节点及增量关系集合中涉及的关联边为中心，在已有图谱中沿边向外扩展预设跳数，将扩展所覆盖的子图区域确定为受影响子图，具体包括：

16、从未匹配节点出发，沿关联边遍历一跳邻域节点；

17、从一跳邻域节点继续沿边遍历二跳邻域节点；

18、将未匹配节点、一跳邻域节点、二跳邻域节点以及连接上述节点的边所构成的子图作为受影响子图。

19、优选地，步骤s3中对受影响子图内的未匹配节点执行节点嵌入计算，采用关系图卷积网络生成初始嵌入向量；

20、关系图卷积网络通过对未匹配节点及其邻域节点的特征进行聚合操作生成初始嵌入向量。

21、优选地，步骤s3中将初始嵌入向量沿受影响子图的边向邻域节点进行传播，具体包括：

22、将初始嵌入向量沿边传递给一跳邻域节点，更新一跳邻域节点的嵌入向量；

23、将更新后的一跳邻域节点的嵌入向量沿边继续传递给二跳邻域节点，更新二跳邻域节点的嵌入向量；

24、传播范围不超过受影响子图的边界。

25、优选地，步骤s4中向量索引为hnsw索引或ivf索引。

26、优选地，步骤s4中对动态图数据库中与受影响子图对应的向量索引执行局部更新，具体包括：

27、仅对受影响子图内节点的向量索引条目进行重新计算和写入，受影响子图之外的节点的向量索引条目保持不变。

28、优选地，还包括索引预构建步骤：

29、根据动态图数据库中各子图的历史访问频率和节点增长率，预测未来时间窗口内的热点子图区域；

30、对热点子图区域提前建立向量索引和缓存。

31、优选地，还包括查询缓存更新步骤：

32、获取查询缓存中与受影响子图内节点对应的缓存条目，将缓存条目标记为待更新状态；

33、在受影响子图更新完成后，重新计算并写入缓存条目。

34、优选地，还包括图谱增量更新步骤：

35、当采集到新增数据时，重复执行步骤s1至s5；

36、将更新后的实体和关联关系增量写入动态图数据库，生成更新后的图谱，记录每次增量更新的操作日志，支持版本追溯与回滚。

37、本发明的有益效果为：

38、与现有技术相比，本发明具备以下有益效果：

39、通过以未匹配节点及其关联边为中心，在已有图谱中沿边向外扩展预设跳数确定受影响子图，将增量更新的操作范围从全图缩小至局部子图，避免了全量嵌入向量重计算，降低了动态图数据库增量更新过程中的计算开销；

40、通过保持受影响子图之外节点的嵌入向量不变，仅对受影响子图内的节点执行嵌入向量重计算和沿边传播更新，使嵌入向量的更新范围与图谱的实际变化范围相匹配，减少了增量更新过程中需要重新计算的节点数量，提高了增量更新的实时性；

41、通过对动态图数据库中与受影响子图对应的向量索引执行局部更新，使向量索引的更新范围与嵌入向量的更新范围保持一致，避免了全量向量索引重建，降低了索引维护开销和输入输出开销；

42、通过对受影响子图内节点的向量索引条目进行重新计算和写入、对受影响子图之外的节点的向量索引条目保持不变，使向量索引在增量更新过程中保持与嵌入向量的一致性，避免了周期性全量重建导致的数据不一致问题；

43、通过将初始嵌入向量沿边依次传递给一跳邻域节点和二跳邻域节点，使未匹配节点的影响沿图结构逐层传播至其二跳邻域，传播范围与受影响子图的边界一致，在保证二跳邻域内节点的嵌入向量能够反映新增数据影响的前提下，控制了传播范围的有界性；

44、通过查询缓存更新步骤，获取查询缓存中与受影响子图内节点对应的缓存条目并标记为待更新状态，在受影响子图更新完成后重新计算并写入缓存条目，使缓存更新范围与图更新范围匹配，避免了全量缓存刷新导致的缓存命中率下降和查询响应延迟增加；

45、通过索引预构建步骤，根据动态图数据库中各子图的历史访问频率和节点增长率预测未来时间窗口内的热点子图区域，并对热点子图区域提前建立向量索引和缓存，使热点子图区域的向量索引和缓存在查询请求到达之前已准备就绪，降低了查询响应延迟；

46、通过图谱增量更新步骤，在每次采集到新增数据时重复执行增量构建流程，并记录操作日志支持版本追溯与回滚，使动态图数据库在持续增量更新的过程中具备数据可靠性和可恢复性。