标签约束可达查询的高效处理方法

来源：计算机研究与发展杂志2020年第9期北京时间：

作者：杜明,杨云,周军锋,陈子阳,杨安平,

摘要：基于标签约束的可达性查询s→\-Lt用于回答给定图中顶点s到顶点t是否存在路径标签属于L的有向路径.针对现有方法索引构建时间长、索引规模大、查询效率低的问题，首先基于k个点构建双向路径标签索引，并提出相应的优化措施减小索引规模，以此来加速可达查询的处理速度.由于其索引没有完全覆盖可达查询，虽然索引规模小，但仍然无法避免查询过程中的图遍历操作.为此，进一步提出覆盖所有可达信息的双向路径标签索引，基于该索引，查询处理时可以完全避免图上的遍历操作.最后，基于多个真实数据集进行测试，实验结果从索引大小、索引构建时间和查询响应时间方面验证了所提方法相对现有方法具有索引规模小、索引时间短且查询响应快的优势.

关键词：图数据管理, 有向图, 可达性查询处理, 标签约束可达性, 双向路径标签索引,